Will the Guru

Designing a simple key-value database using Log Compaction

• Create
  • Append new record to the list of records
• Read
  • Read the record’s location from Index and retrieve from the list of records
• Update
  • Append new record and update the record’s location on Index
• Delete
  • Append new dummy record(e.g. tombstone) and update the record’s location on Index

While read and write is both fast for the above design, as Create/Update/Delete operation keeps add new record to the list and consumes memory, we need to improve the memory usage.

To achieve that, we can use ‘Log Compaction’ to improve it.

Log Compaction

• The most recent record for a key is retained, while older records for the same key are deleted
• Background thread will copy the segment and clean up the deleted/old records
  • This process allows to make the segments smaller as we get rid of duplicates and deleted records.

---

Reference

• https://leetcode.com/explore/interview/card/system-design-for-interviews-and-beyond/727/data-store-internals/4770/