Point updates want rows. Scans want columns. An HTAP engine has to serve both, and the tempting answer — keep one copy of each — means keeping two versions of the truth in sync, which is the problem you were trying to avoid.
Base pages and tail pages
L-Store splits storage in two:
- Base pages are immutable. Written once, never mutated.
- Tail pages are append-only. Every update writes a new version here.
An indirection column on each base record points at its latest version in the tail pages. Reading a record means following that pointer.
Because a write appends rather than mutates, a reader is never blocked by a writer touching the same record. The old version is still there and still valid to read.
The cost, and the merge
The cost of append-only is that reads get slower over time. A record updated a thousand times sits behind a thousand-entry chain, and a scan pays for all of it.
A background merge compacts tail updates back into fresh read-optimized base pages. It runs out of band, so the compaction cost is not paid by whoever happens to be reading. This is the piece that makes the design viable rather than merely elegant — without it, analytical performance degrades until the engine is unusable.
Bufferpool
An LRU bufferpool with dirty-page write-back sits between the engine and disk. Eviction writes dirty pages before dropping them; clean pages are dropped free.
The subtlety is that correctness depends on eviction order interacting properly with the merge. A page being compacted must not be evicted out from under the merge, and a dirty page must not be lost because the merge rewrote its base.
Concurrency
Transactions run multithreaded under record-level two-phase locking. Record-level rather than page-level matters: page-level locking would serialize transactions that touch unrelated records that happen to share a page, which on a columnar layout is common.
Two-phase locking gives serializability. Every transaction acquires all its locks before releasing any, so no transaction observes a partial commit.
What validated it
Three autograded milestones covering correctness, throughput, and concurrent transaction behavior. Built with a five-person team.
The engine is not fast by production standards — it is Python. But the layered design is the real content: the interaction between append-only storage, background compaction, buffer management, and locking is where the actual difficulty lives, and none of it is visible from a description of the data structures alone.