Concurrent

• Run compaction on a separate thread.
• Offers a concurrent search over sstables using mutliple threads. Since we are concerned about recent values (as key-value pairs may get updated multiple times) we also terminate threads when a later partition discovers the key.
• We deprecate the previous scan method that had the following flaws:
  • Loads the sstable to memory. This is a problem as sstables may grow as large as 100G.
  • Searches linearly even though sstable entries are sorted on keys.
• We introduce binary search.

Persistence

Introduce SStables to store key-value pairs on the disk. An SSTable is a sorted string table which manifests as a binary file with the following format:

80000000test_key50000000value
30000000urlA0000000github.com

1. The first 8 bytes tell us the length of the key, followed by the contents of the key.
2. The next 8 bytes tell us the length of the value, followed by the contents of the value.
3. Here we have 2 key value pairs. Where the keys are test_key and url of lengths 8 and 3. We also have two keys value and github.com of length 5 and 10.

We have means to:

1. Add key value
2. Read key value
3. Delete key value
4. Flush a memtable to sstable.
5. Compact many tables into a larger fewer tables.