Concurrency Control

Optimistic Concurrency Control (OCC)

Tarantool uses one single thread for processing all transactions of a database instance, which is called 'transaction processor thread'. Thus the design is lock-free. Transactions occur in fibers on that single thread. A fiber is a set of instructions that may contain “yield” signals (yield can be either explicit or implicit, e.g., system calls). The transaction processor thread will execute all computer instructions until a yield, and then schedule a switch to another potentially ready fiber. This scheduling scheme is called cooperative scheduling. It means that unless a running fiber deliberately yields control, it cannot be preempted by other fibers. Thus, a transaction's author has the responsibility not to write long-running computations without a yield.

When transaction commits, a yield happens and changes are written to WAL. A simple optimistic scheduler is used: the first transaction to commit wins. Any active transaction that has read a value modified by a committed transaction will be aborted. Moreover, Tarantool's cooperative scheduler implementation ensures that, in absence of yields, a multi-statement transaction is not preempted and thus will never be aborted.

Checkpoints

Non-Blocking

Tarantool uses write ahead logging (WAL), thus checkpoints are necessary. In the docs, checkpoints are mentioned as snapshots. Users can either force the DBMS to take a snapshot, or enable automatic creation of snapshot files. Users can control the number of snapshots stored and the snapshot interval.

During a snapshot, copy-on-write and multi-version concurrency control is used. When the master process changes part of a primary key, the snapshot process obtains an old copy of the page.

Indexes

B+Tree BitMap R-Tree