Serializable Snapshot Isolation

[ysono]

(Scroll down to see the latest version.)

The first diagram is a documentation of basically what we have so far. We have secondary indexes and serial execution, and it resembles the box on the third row in the diagram. Also presented is a simple concurrently executed design, which provides no isolation; this design has not been implemented.

The second diagram is a proposal for adding Serializable Snapshot Isolation (SSI) on top of what we have so far.

Motivation

If we are to add concurrent execution, I believe it is optimal to jump straight to SSI. Because we have secondary indexes, data are distributed across indexes, and it is wise to synchronize comitting across them. And, if we want to synchronize committing, a snapshot-based isolation seems natural (Read Uncommitted and Read Committed depend on per-PrimaryKey lock; and I believe secondary indexes are not locked). And, if we use snapshots, we only need to add conflict checks and retries in order to guarantee SSI.

Correctness

There has been no formal check on the correctness of any of the design. However, there are several perspectives by which correctness can be assessed (in a non-rigorous way).

• Impossibility of deadlocks
• Logical flow within each operation
• Shared usage of db_min_concurr_ver and VersionState
• Shared usage of SI flags is_built and is_deleted
• Feasibility of AtomicallyPushableQueue (singly linked linked list, AtomicPtr, unsafe rust)

Future evolution

Some ideas are included in the bottom of the SSI diagram. IMO either we add more async/await concurrency, using asynchronous file I/O (io_uring), or we partition operations by data and run single-thread (actor) per core.

etc

(I have a suspicion that this design is better utilized on multiple different tables or datastores, and it's fine to stick with serial execution per table. But since this is a learning project, I want to implement this design anyway.)

[ysono]

Changes:

• Clarification of the logic to put delta onto a secondary index.

---

Changes above:

• Added secondary index's state transition analysis.
• Ensured secondary index can be deleted without relying on future transactions. In the old design, it would hang for arbitrarily long.
• Many cosmetic cleanups.

Further changes:

• Look over the state transition analysis and impl.
• Try to merge SI's AtomicBool flags is_readable and is_deleted with Job's local variables built_but_not_readable and soft_deleted. It feels kludgy.

[ysono]

Changes:

• The flow of the Job is more unified.

[ysono]

Closing in favor of https://github.com/ysono/pancake/issues/59. Delta between this design and that design:

• The index structure is lockless.
  • This removes a lot of concern for accessing + deleting of individual indexes, which this design iteration focused on.
  • A lot more focus is put on the correctness of lockless access + modification, as well as how job reads data.
• The "Resource Allocation Diagram"-style description of code is too inefficient. Going w/ pseudocode.