Storage Engine

I recently read Microsoft’s 2015 VLDB paper, Real-Time Analytical Processing with SQL Server [1]. SQL Server was among the earlier products to ship and productionize an HTAP row/column update design. Row-store (row-wise index) tradeoffs for OLTP are well understood; efficient millisecond-scale column store updates have several designs in the wild—Kudu [2], Positional Delta Tree [3], and others—but they receive far less discussion than row stores. After a careful review of SQL Server’s approach, I find it worth sharing....

I joined TiDB’s Hackathon 2019 and finally have time to write this recap. A 48-hour hackathon around TiDB: build a demo, present in six minutes. Scoring weights practicality, ease of use, and performance for TiDB (40%), completeness (30%), innovation (20%), and presentation (10%). Our team of three: captain Yi Wu from PingCAP’s US office (ex-Facebook RocksDB, now RocksDB at PingCAP), and Bokang Zhang in Beijing (TiKV). All three work on storage, so we aimed at the bottom of the stack....

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....

This article analyzes TokuDB’s index structure—the fractal tree—from an engineering implementation perspective. It describes the on-disk storage layout of ft-index in detail, how ft-index implements point queries, range queries, and insert/delete/update operations, and throughout the discussion attempts a detailed comparison with InnoDB’s B+ tree from multiple angles. Introduction to the Fractal Tree The fractal tree is a write-optimized on-disk index data structure. In general, fractal trees offer good write performance (insert/update/delete) while still providing read performance close to that of a B+ tree....

Basic LevelDB constraints With the default options, LevelDB follows these basic constraints: LevelDB has 7 levels: 0, 1, 2, 3, 4, 5, and 6. SSTables on level 0 are about 4 MB each. On level i (i > 0), each SSTable is at most 2 MB. Level 0 ideally has 4 SSTables, should stay within 8, and must not exceed 12. The total storage used by all SSTables on level i (i > 0) should stay around 10^i MB....