C#/Unity SDK - Double-buffer client cache indices on the parser thread

[kazimuth]

Currently, the SDK parsing thread can't fully prepare insert/update/delete information because it can't see the current state of the client cache. For example, the parsing thread may see 2 deletes of a row, but it can't know whether these will actually result in a delete callback being called. This is because the client cache might have 3 copies of the row!

This means that some information about state changes has to be computed on the main thread. This includes building lists of rows that need callbacks, and a lot of index maintenance work.

We could fix this by maintaining a relatively lightweight copy of the client cache on the parsing thread. This wouldn't store copies of rows, only copies of indices. This is thread-safe because we treat rows as immutable.

Benefits of this are:

• Pre-build lists of rows that need callbacks off the main thread
• Prepare operations on indexes off of the main thread. Ideally, for BTreeIndexes this means building a Dictionary<IndexKey, (HashSet<Row> adds, HashSet<Row> deletes) off of the main thread.
• Simplify MultiDictionary logic by getting rid of MultiDictionaryDelta

Drawbacks:

• More memory usage. We don't need to store multiple copies of each row, since rows are immutable in the SDK; but we would need to store a second copy of all indexes and primary key -> row maps.

Alternatives:
A lighter-weight solution would be just pre-building HashSets for BTreeIndexes for insert-only transactions off of the main thread. This speeds up one case that we spend a lot of time on with less complexity.

[kazimuth]

On further discussion, we've decided to just completely double-buffer these -- that is, move them back and forth between threads. Then it's much faster to apply changes on the main thread, it becomes just a pointer swap per-table, plus user callbacks. It requires some amount of extra compute on background threads, and some multiple of space usage -- but less than 2x, because we can share row objects between the two client cache copies.

[kazimuth]

Work to do:

• Start from https://github.com/clockworklabs/com.clockworklabs.spacetimedbsdk/pull/346/files
• Modify Table.cs to contain two copies of Entries, one for the main thread and one for the background thread. It should also have two copies of each index (this probably means updating *IndexBase to contain two copies?)
• Update ParsedTableUpdate to have:
  • a Dictionary<object, Row> of removed rows
  • a List of added rows
  • a List of updated rows
• Modify IRemoteTableHandle.Parse / IRemoteTableHandle.ParseInsertOnly / IRemoteTableHandle.ParseDeleteOnly to modify the background copy of Entries and record removed / added / updated rows. A row is updated if it has been removed, then added. Removes, adds, and updates should be propagated to the background copies of indices (i.e. by calling OnInternalInsert and OnInternalDelete)
• Update:
  • PreApply to call OnBeforeRemove with the removed rows
  • Apply to swap the foreground and background Entries. It should also swap foreground and background indices.
  • PostApply to call other callbacks

At some point the background thread will need to update the second copy of the cache (entries + indices) as well. That will take some careful thinking about the plumbing, I'm not quite sure how it should work yet.

The way plumbing works for indices will also need to be reworked.

Testing:

• unit tests
• blackholio
• bitcraft (we'll want to specifically test that https://github.com/clockworklabs/SpacetimeDBPrivate/issues/1585 does not re-emerge. In theory, it was fixed server-side by Remove redundant rows from subscription updates #2654)

[kazimuth]

Notes:

• the ParseMessages loop is the "parse thread". It pulls messages from the _parseQueue and puts them on the _applyQueue once they're ready.
• The main thread FrameTick method pulls from _applyQueue and applies updates.
• When applying an update:
  • all tables call PreApply, to call OnBeforeDelete callbacks
  • all tables call Apply, to actually perform the update
  • all tables call PostApply, to call OnDelete, OnInsert, OnUpdate callbacks
• (At some places in the code, we use the word "remove" rather than "delete". We should probably standardize on "delete"...)
• Currently, the parse thread only synchronizes with the main thread by sending it messages; it never waits for the main thread. To make this change work, we'll need the parse thread to have a way to wait for the main thread to Swap the cache, and then re-do its work on the newly-backgrounded copy of the cache. (Here "cache" refers to the Entries table and indices for all tables.) We may want to think of this as a single shared state machine. This would maybe mean getting rid of the _applyQueue and replacing it with a variable _state, guarded by a lock.
• This change will decrease apply latency on the main thread, but may increase overall latency from reducer call -> user sees effects of reducer calls. In particular, this change means that only one database update can be applied per frame. If there are many database updates coming in, this might lead to unbounded queue growth...

[kazimuth]

I'm concerned that the bolded text in the last message makes this unworkable. I'd like to measure how many database updates are being applied per-second in a loaded BitCraft environment. If it's more than one per frame, this won't work. It's not possible to queue up multiple changes for application if we're double-buffering.