Simple key-value database

The log-based storage design from our messaging system can be extended to support a simple key-value database.

• Create: Append a new record to the log file.
• Read: Use an in-memory index to locate the record, then seek to that position in the file.
• Update: Append a new record with the same key to the end of the log segment. Update the index to point to the latest record.
• Delete: Append a tombstone record to mark a key as deleted.

An update operation appends a new record with the existing key to the end of the log segment. The index is updated to reference the latest record position. This results in duplicate keys in the log file, but the index always points to the most recent version.

Deleting a record is more complex than the other operations. In messaging systems, we delete entire segments after all messages are consumed. However, this assumption does not hold for general databases.

In typical databases, some records are deleted while others remain. Therefore, we cannot rely on deleting entire segments to free disk space.

To address deletion, we append a tombstone record to the data file when a key is deleted. This record signals that the value is no longer valid.

When a query is made for a deleted key, the system checks for a tombstone record. If one exists, no value is returned.

• Disk Space Exhaustion: Records are continuously appended, leading to unbounded growth.
• Index Scalability: With many keys, in-memory indexing becomes insufficient. Disk-based indexes introduce random access overhead.
• Range Query Inefficiency: The design supports point queries only. Range queries—like finding all employees with more than five years of service—require scanning every record.

To mitigate unbounded growth, we implement log compaction. This process retains only the most recent record for each key, removing all previous versions.

Log compaction ensures that only the latest value for each key is preserved, while all older records are deleted.

This approach prevents disk space exhaustion by eliminating redundant records over time.

The design remains effective for point queries but is limited in handling range queries and large-scale indexing.

These limitations point to the need for a more advanced design in future videos.

A background thread runs periodically to manage segment files. It creates a new segment file and copies records from the old segment to the new one.

While copying records, the process identifies and removes duplicate keys. This ensures each key appears only once in the new segment.

During log compaction, deleted records are eliminated. All previous versions of a deleted key are discarded entirely.

Once all records from the old segment are copied to the new file, the old segment is replaced by the new one. The old segment is then deleted from disk.

Compaction reduces segment size by removing duplicates and deleted records. Smaller segments result from this process.

Smaller segments can be merged together to reduce the total number of segments in storage.

Fewer segments mean fewer hash table indexes. During key lookups, fewer indexes need to be checked, improving performance.

BitCask, the default storage engine in React, implements these principles. It is designed for fast reads and writes.

Writes are fast because appending to the end of a file is efficient, and updating the in-memory hash table index is quick.

Reads are fast because they require only a single disk seek to retrieve a value.

Complex problems can be solved with simple, combined ideas. Designing a storage backend for a distributed key-value data store initially seems daunting.

With foundational concepts applied correctly, such problems become manageable and less intimidating.