This article covers transaction isolation in TokuDB. The source implementation is complex; for clarity, we focus on the most essential parts and omit minor details.
Background
In traditional relational databases (Oracle, MySQL, SQL Server, and others), transactions are central to both engineering and discussion. The core properties of a transaction are ACID. A (atomicity) means a transaction’s sub-operations have only two outcomes: all succeed on commit, or all are undone on rollback. C (consistency) means commit or rollback must not violate integrity constraints such as uniqueness or referential integrity. I (isolation) applies to concurrent transactions: at a given moment, transactions T1 and T2 should see isolated data—as if each were in its own hotel room, unaware of the other. D (durability) means once a transaction commits successfully, its effects survive process or OS crashes as long as disk data is intact.
TokuDB fully supports ACID. Because TokuDB uses a fractal tree for indexing while InnoDB uses a B+ tree, transaction implementation differs substantially. This article focuses on transaction isolation—multi-version concurrency control (MVCC). InnoDB maintains redo and undo logs: redo records physical page changes for durability; undo stores logical versions of a row under concurrent transactions for isolation (MVCC) and rollback.
Because TokuDB’s fractal tree applies updates via messages—each message is one version of a change to a record—the source has no separate undo log. Instead it manages multiple messages per record. Multiple messages per record can implement MVCC but not rollback by themselves, so TokuDB adds a tokudb.rollback log file to support transaction rollback.
Transaction Representation in TokuDB
In TokuDB, a user-level transaction is broken into many small transactions at the storage engine layer (called txn). For example:
begin;
insert into hello set id = 1, value = '1';
commit;
The corresponding redo-log records are:
xbegin 'b': lsn=236599 xid=15,0 parentxid=0,0 crc=29e4d0a1 len=53
xbegin 'b': lsn=236600 xid=15,1 parentxid=15,0 crc=282cb1a1 len=53
enq_insert 'I': lsn=236601 filenum=13 xid=15,1 key={...} value={...} crc=a42128e5 len=58
xcommit 'C': lsn=236602 xid=15,1 crc=ec9bba3d len=37
xprepare 'P': lsn=236603 xid=15,0 xa_xid={...} crc=db091de4 len=67
xcommit 'C': lsn=236604 xid=15,0 crc=ec997b3d len=37
The transaction tree is shown below:
A more complex example with savepoints:
begin;
insert into hello set id = 2, value = '2' ;
savepoint mark1;
insert into hello set id = 3, value = '3' ;
savepoint mark2;
commit;
The corresponding redo-log records:
xbegin 'b': lsn=236669 xid=17,0 parentxid=0,0 crc=c01888a6 len=53
xbegin 'b': lsn=236670 xid=17,1 parentxid=17,0 crc=cf400ba6 len=53
enq_insert 'I': lsn=236671 filenum=13 xid=17,1 key={...} value={...} crc=8ce371e3 len=58
xcommit 'C': lsn=236672 xid=17,1 crc=ec4a923d len=37
xbegin 'b': lsn=236673 xid=17,2 parentxid=17,0 crc=cb7c6fa6 len=53
xbegin 'b': lsn=236674 xid=17,3 parentxid=17,2 crc=c9a4c3a6 len=53
enq_insert 'I': lsn=236675 filenum=13 xid=17,3 key={...} value={...} crc=641148e2 len=58
xcommit 'C': lsn=236676 xid=17,3 crc=ec4e143d len=37
xcommit 'C': lsn=236677 xid=17,2 crc=ec4cf43d len=37
xprepare 'P': lsn=236678 xid=17,0 xa_xid={...} crc=76e302b4 len=67
xcommit 'C': lsn=236679 xid=17,0 crc=ec42b43d len=37
The transaction tree:
TokuDB records txn dependencies with a pair {parent_id, child_id}. From root to leaf, a sequence of IDs uniquely identifies a txn; this sequence is called xids—a transaction id. For example, txn3 has xids = {17, 2, 3}, txn2 has xids = {17, 2}, txn1 has xids = {17, 1}, and txn0 has xids = {17, 0}.
Every operation (xbegin/xcommit/enq_insert/xprepare) carries an xids identifying its txn. Each message (insert/delete/update) in TokuDB also carries this xids, which plays a central and intricate role in the implementation.
Transaction Manager
The transaction manager tracks all storage-engine transactions and mainly maintains:
- Active transaction list. Only root transactions are listed; from a root, the entire transaction tree can be recovered. This list holds all root transactions that have started but not yet finished.
- Snapshot read transaction list.
- Referenced xids list for active transactions. If a transaction starts at
begin_id(xbegin) and commits atend_id(xcommit), referenced_xids maintains the pair(begin_id, end_id), which maps a transaction’s lifetime to all active transactions at that time—mainly used for full GC described later.
Fractal Tree LeafEntry
A previous post described the fractal tree structure. On insert/delete/update, messages from root to leaf are applied to the LeafNode. To explain apply in detail, we first introduce LeafNode storage.
A LeafNode is a collection of leafEntry records. Each leafEntry is a key-value structure {k, v1, v2, ...} where v1, v2, … are multiple versions of the value for one key. See here for LeafNode layout. The structure of a single leafEntry for one key:
A leafEntry is a stack. The bottom segment [0~5] holds values from committed transactions. The top segment [6~9] holds values from active, uncommitted transactions. Each stack element is a quadruple (txid, type, len, data) describing that transaction’s value. More generally, [0, cxrs-1] holds committed transactions. Committed versions would normally not remain on the stack, but they persist when other transactions reference them via snapshot read. Until every transaction referencing [0, cxrs-1] commits, those entries are not reclaimed (see Multi-Version Record Reclamation below). [cxrs, cxrs+pxrs-1] holds active uncommitted transactions; on commit, cxrs advances toward the top.
MVCC Implementation
Write operations
We treat three write types: insert, delete, and commit.
For insert and delete, push one element onto the top of the LeafEntry stack:
For commit, move the top element to the cxrs position and shrink the stack top:
That maintains multi-versioning for writes. The real implementation has many details and optimizations, such as ule_do_implicit_promotions.
Read operations
Databases support multiple isolation levels. MySQL InnoDB supports Read Uncommitted (RU), Repeatable Read (RR), Read Committed (RC), and Serializable (S). RU allows dirty reads (reading uncommitted data). RC, RR, and Serializable address phantom reads (a transaction’s update affecting rows committed by another transaction).
TokuDB supports the same four levels. In ft-index, reads are classified into three snapshot categories:
- TXN_SNAPSHOT_NONE: No snapshot read; Serializable and Read Uncommitted fall here.
- TXN_SNAPSHOT_ROOT: Repeatable Read. The transaction only needs data committed before its root transaction’s xid.
- TXN_SNAPSHOT_CHILD: Read Committed. A child transaction A must read the version appropriate to its own xid, because other transactions may have committed updates after A started; A must see those committed changes.
Multi-Version Record Reclamation
Over time, more old transactions commit and new ones start. Committed transactions in LeafNodes accumulate. Without reclamation, BasementNodes would grow and the data file would hold useless data. TokuDB calls cleanup Garbage Collection (GC). InnoDB has a similar process: multiple versions of a key live in undo log pages, and a background purge thread reclaims expired versions to reuse undo pages and bound undo growth.
TokuDB has no dedicated purge thread like InnoDB. Expired versions are reclaimed opportunistically during updates—on insert/delete/update, each LeafEntry is checked for GC eligibility; if so, expired transactions are removed and memory is compacted. TokuDB implements two GC types:
Simple GC
Each apply of a message to a leafEntry carries gc_info, including oldest_referenced_xid. Simple GC clears the committed transaction list in one pass (keeping one committed record so the row remains findable). Simple, blunt, and efficient.
Full GC
Full GC has more complex trigger conditions and flow, but the goal is the same: remove expired committed transactions. We omit details here.
Summary
This article outlined TokuDB transaction isolation: transaction representation, LeafEntry structure, MVCC read/write flow, and multi-version reclamation. TokuDB has no undo log because fractal-tree update messages already record versions. Expired transaction cleanup is amortized into update paths rather than a background thread. Because transactions sit on top of the fractal tree, the design diverges from InnoDB in many ways—that is part of TokuDB’s innovation.
Finally, welcome discussion from anyone interested in ft-index. My day job does not involve ft-index; curiosity drove me to read the code, and I occasionally enjoy glimpsing its engineering elegance.
