LSM-tree for write-intensive storages

LSM, or Log-structured Merge-Tree is used to improve the performance for write-intensive storages.

1. Writes are merged in memory using red-black tree, then flushed to disk sorted — SSTable or Sorted Strings Table.

2. For reads, we use Sparse Index to speed up the seeks, and Bloom Filter to speed up the non-present keys checks.

3. For deletes, we save the key as usual with a special value — tombstone.

4. To decrease volume size on disk, periodical compactions are run. They merge data to filter out duplicates.

Similar Posts