This is the 8th day of my participation in the August Text Challenge.More challenges in August

  1. Update in place → B+Tree
  2. Non-in-place update → LSMTree

LSM is designed with high performance of sequential write and becomes the basis of write intensive database system.

LSM problem

Sequential write problems:

  1. Records of operations performed on a key each time<key, value, operation>One key occupies multiple storage space
  2. How to ensure query speed

How to solve these problems becomes the essence of LSM design.

Storage redundancy

Merge operation records of multiple keys, save the last one

New problem: Each merge requires traversing disk files, similar to STW, affecting user writes.

Crooked file segmentation, multiple files to do a key de-merge algorithm – multi – way merge algorithm

Multiway merging will involve merging multiple groups that are internally sorted and put in disk to merge, IO costs are relatively large, then sort directly in memory and drop disk

Tail then data in memory form → skiplist

Skiplist is a complexity balancing tool for reading and writing

To sum up:

  1. Merge file data
  2. A file that is too large is not conducive to merging tail file segments
  3. Multi – file merge optimizes multi – file internal guaranteed sort
  4. When the user inserts, the memory is sorted, and then the disk is dropped
  5. The merger strategy adopts hierarchical merger

Query optimization

How to reduce read magnification:

  1. Reduce the number of files in an Sstable by continually major compaction to find the desired results within a single layer of queries
  2. Fast filtering to determine whether a key is in an Sstable

When an upper-layer Sstable reaches a threshold, it compains the merge. It’s like multiple merge

MemTable

  1. Ensure the insertion is orderly and easy to follow down after the merge skiplist

  2. Frequent memory allocation costs performance, especially in small memory areas, which are prone to memory fragmentation

    A large memory can be allocated directly, and pointer references can be changed if necessary.

    Flicker memory can be recycled directly from memtable.

    Flicker memtable → Immutable

  3. MemTable encodes

    in a string and inserts that string as a key
    ,>

WAL

Leveldb /log_format.md at Master · Google/Leveldb

SSTable

Compaction

  1. MinorCompaction immutable memtable persists to an SST file
  2. Major Compaction Is a Compaction between SST files