Please enable JavaScript.

Coggle requires JavaScript to display documents.

Storage and Retrieval - Coggle Diagram

- - - - binary file format instead of CSV
      - deleting records via tombstoning
      - crash recovery, rebuilding in-memory hash maps vs loading stored snapshot of hash map on disk
      - partially written record detection via checksums
      - concurrency control via single writer thread
    - - sequential writes (appending and merging) are fast
      - concurrency and crash recovery much simpler with immutable segment files
    - - must fit in memory
      - range queries not efficient
  - - - mergesort segments; simple and efficient; segment files can be bigger than available memory
      - sparse in-memory index is enough; one key for every few KBs of segment file; courtesy sorted on-disk segment files
      - compressible blocks; save disk space and I/O bandwidth
    - - maintaining sorted structure on disk is possible; in memory easier
      - handle write by adding to in-memory balanced tree; memtable
      - size-capping; write to disk as as SSTable file; efficient as tree maintains key-value pairs sorted by key
      - reads find first in memtable, then in most recent on-disk segment
      - merging and compaction in background
      - crash recovery; maintain on-disk append-only log for memtable
    - - KV Storage Engines LevelDB and RocksDB do this
      - Cassandra and HBase use similar storage engines
      - LSM Storage Engines "merge and compact sorted files"
      - Lucene (ElasticSearch and Solr) uses LSM for Term Dictionary
    - - Slowness in finding missing keys; use Bloom Filters
      - Compaction strategies
        
        Size Tiered; HBase, Cassandra
        
        Level Tiered; LevelDB, RocksDB, Cassandra
  - - - overwriting stark contrast to appending without modifying files
      - corrupted index if overwrite fails; esp. during splitting operation
      - resilience via WAL on disk to restore BTree to consistent state
      - concurrency control must to avoid threads seeing inconsistency
    - - copy-on-write (LMDB) instead of overwriting; concurrency control
      - pack more keys by abbreviating; in interior tree; act as boundary
      - adding additional pointers; sibling pointers in leaf pages to avoid jumping back while scanning ranges.
      - layout BTree so leaf pages appear in sequential order on disk. Easier to maintain sequential order in LSM trees b/c of rewrite on merge