[storage] Store data on disk

[ndragazis]

I need to define how the key-value store shall persist data on disk. I also need to explore the API that seastar provides for disk IO operations.

Things to consider:

• Must use an LRU cache
• Data sharded among CPU cores based on their keys
• File format
• API must support key updates
• API must support querying sorted list of all keys

[ndragazis]

Popular Strategies

Reading from Martin Kleppmann's book "Designing Data Intensive Applications" (Chapter 3), there are two categories for storage engines:

• log-structured
• page-oriented

The log-structured storage engines store the data in log-structured files on disk and construct in-memory indexes to accelerate lookups.

The page-oriented storage engines store data in sorted order in fixed-size pages on disk and maintain a persistent B-tree for fast lookups.

The main difference is that page-structured storage engines perform updates in-place, whereas log-structured storage engines perform append-only operations and remove stale values in later stages (log merging, log compaction).

[ndragazis]

I will follow the LSM-tree approach, which is closer to Scylla.

High-level Plan:

• [X] Start from the Memtable. Connect the endpoints to the memtable.
• [X] Add a write-ahead log for the memtable. Restore the memtable from the WAL after a crash.
• [X] Add SSTables to the mix.
  • [X] Flush memtable into an SSTable when it reaches some size.
  • [X] Create new memtable and WAL to server new writes.
  • [X] Server reads from the old memtable.
  • [X] Delete old WAL and memtable when flushing finishes.
  • [X] If search on memtable fails, traverse all SSTables.
  • [X] Implement deletions with tombstones, since we don't know if a key already exists in an SSTable.
  • [ ] Support recovery from a partial flush.
• [ ] Add an LRU cache on top of the memtable.
• [ ] Add indexes to the SSTables.
• [ ] Add compaction for SSTables.
• [ ] Add bloom filters to prevent some disk searches.

[ndragazis]

Memtable Flushing

When the memtable reaches some size, the storage engine will be doing the following:

1. Create a new mutable memtable and WAL to serve writes.
2. Mark the old memtable as immutable to only serve reads.
3. Start an asynchronous operation to flush the old memtable to the disk as an SSTable.
4. When flushing finishes, delete the old memtable and WAL.

What happens if the new memtable gets full before the old one is fully flushed? One strategy is to support having more than one immutable memtables, see [1]. However, it is crucial to flush immutable memtables in-order since memtables are searched before SSTables.

[1] https://github.com/facebook/rocksdb/wiki/RocksDB-Tuning-Guide

[ndragazis]

File Naming Strategy

Let's assume we allow the system to have multiple immutable memtables and WALs being flushed in parallel. What names should I use for the WAL files?

Requirements:

• Prevent collisions.
• Be sortable in chronological order, to support key searches.

Same problem applies to SSTables as well.

---

Cassandra used to solve this using natural numbers, and later they switched into Time UUIDs.

source: https://cassandra.apache.org/_/blog/Apache-Cassandra-4.1-New-SSTable-Identifiers.html

---

As a first iteration, I will suffix WAL and SSTable filenames with a counter. So, the file structure should look like this:

.tinykv/
├── sstable_1
├── sstable_2
├── wal
└── wal_1

[ndragazis]

Deleting Keys

Deleting keys in LSM-trees is not trivial.

If a key lives only in the mutable memtable, then we can just remove it from the memtable and we are done. However, it could be that it also appears in an immutable memtable or an SSTable.

The solution is to record deleted keys via a deletion marker, also called a "tombstone".