Replace rocksdb with relational database (eg sql) for queue and state db

[Zannick]

Having a relational database with indexes might be better for #141. The new structure I'm envisioning would keep the statedb and use that as the queue by way of indexes:

Mode	state	progress	score	elapsed	remaining	hist	prev	next	in-memory-queue	won
lookup	= x
insert	...	...	...	...	...	...	...	...	...	...
update	= x		set min	set	set	set	set
process	= x							set	set false
evict	= x								set true
retrieve		= x	sort	sort	sort				= false, set true
recover									set false if true
solutions				sort						= true

• Our statedb lookups are for data at the primary key (state).
• As we process states, we insert the new states (or update the ones we've found faster routes to), and update the processed states with the next steps.
• Evicting from the in-memory-queue simply flips the bit.
• Retrieving states looks for states with the in-memory-queue bit set to false (and then sets them to true)
• On recovery, we can either retrieve all the elements marked as being in the memory queue, or set them all back to false and perform a retrieve.
• And we can retrieve solutions directly on recovery as well.

[Zannick]

For speed, the import mechanism will probably be reduced to just recreating the actual states and not processing each state along the way, though we might include that as an option. It's fairly simple to enter this way, we just don't set next or processed.

Retrieving the full history of a state can be done in one go with a recursive common table expression that works from the target state back to the start, but this is presently not completing due to having a state cycle in the test data I imported (I imported the same route twice, and the second time it processed 8 new states).

I note we'll also need to consider how to update existing states in the db as predecessors are improved. Our existing solution is a cleanup thread which looks for states to update. To make a recursive CTE be able to handle that we'll need to a) add a step time column or b) update next to be an Array of (hist, step time) pairs. Since next doesn't include the subsequent raw states (as it cannot), we would already be joining on y.prev = x.raw_state to add y as a downstream state. And further, the downstream states would not have prev updated, so we can guarantee that step_time would be still the same without needing the step replayed.

[Zannick]

Here's another small potential optimization: currently the encode step that sets up the inserts has to estimate the remaining time, which can be expensive (even with a cache). It might be feasible to check first if a state already exists in the db, and if so we only need to perform an update on those states without performing that calculation, and only when there's a race do we calculate it twice.

[Zannick]

In fact, the majority of the time importing into mysql is spent estimating the remaining time, so we ought to parallelize that and skip it for any states already computed.