Please enable JavaScript.

Coggle requires JavaScript to display documents.

Storage Engines - Coggle Diagram

- - - - db_set
        
        Writes to append log
        
        Extremely write efficient
        
        Updated values are appended
      - db_get
        
        Terrible performance for large n of records
        
        Has to scan the entire DB from end to start
        
        O of n
  - - - Affects query performance
      - Doesn't change DB contents
    - - Maintaining such incurs overhead, esp. on W
  - - - Update upon each KV pair append
    - - Old log entries not deleted -> may run out of space
      - Hash map
        
        Not persisted
        
        Have to rebuild on DB restart
        
        -> DB restart is slow for large datasets
        
        Must fit in memory
        
        If on disk
        
        ^ random IO -> bad performance
        
        Expensive to grow if full
        
        Hash collisions fiddly logic
      - Range queries ineff
        
        Have to lookup each key individually
    - - Sorted by key
      - Sorted Strings Table
      - Stores KV pairs
      - Each key only once in the file
      - Not all keys in memory
        
        Group KV pairs into blocks of few KB
        
        Store first key of each block in (sparse) index
        
        Index is stored as separate part of the SSTable
        
        Immutable B-tree
        
        Trie
        
        Compressed blocks
        
        Reduce storage
        
        Reduces I/O bandwidth use
        
        A little ^ CPU use
      - Better for reading than append-only log
      - Memtables
        
        Examples
        
        Red-black tree
        
        Skip list
        
        Trie
        
        Save incoming writes into it
        
        Reaches treshold
        
        A few MB
        
        Flushes to a new SSTable/segment
        
        Each segment own index of contents
        
        Segments are stored in
        
        Local disk
        
        Object storage
        
        Delta Lake
        
        SlateDB
        
        Also write to a log as backup
      - Read order
        
        Memtable
        
        Newest SSTable
        
        Older SSTables
        
        (4.) Not in DB
      - Compaction
        
        Periodically merge SSTables into 1 new table
        
        Using mergesort
        
        Done in a background thread
        
        Types
        
        Leveled
        
        Tables have fixed sizes
        
        Are grouped into increasing levels (0,...,N)
        
        L0 is newest
        
        L1-LN are range-partitioned
        
        Each level is larger than the preceding one
        
        More incremental compaction
        
        Uses less disk space
        
        More read-eff as there are fewer SSTables
        
        Best for mostly R and fewer W
        
        Better if you W small n of keys freq and large n of keys rarely
        
        Size-tiered
        
        Merges similarly-sized SSTables into larger ones
        
        Can handle ^^ W throughput as data rewritten only a few times in larger sequential merges
        
        Best for mostly W and fewer R
        
        Most LSM-tree implementations provide a var of compaction strategies for various workloads
      - Tomstones
      - Algorithm
        
        Log-Structured Merge-tree (LSM-tree)
        
        Examples
        
        Cassandra
        
        HBase
        
        ScyllaDB
        
        RocksDB
        
        LSM storage engines
      - Immutable = simple crash recovery
      - Bloom filters
        
        Extremely fast check using bitwise operators
        
        Is a key contained in a certain SSTable
        
        Contained in the SSTable itself
        
        Procedure
        
        Key is hashed
        
        Split into numbers
        
        Interpreted as indexes in the array of bits
        
        False positive
        
        When all indexes are set to 1 by other keys
        
        1% probability = 10 BF bits per key in SSTable
      - Fewer large Ws (sequential Ws)
  - - - RocksDB
      - SQLite
      - KuzuDB
  - - - Has a page number
      - Can refer to another (like on-disk pointer)
      - Page number * page size => byte offset of the page location in the file
      - Root
        
        You start here when looking up a key
        
        Has several keys and refs to child pages
      - Child
        
        Each is responsible for a range of keys
      - Leaf
        
        Page containing individual keys
        
        Search for it when updating values
    - - Refs to the n of other pages in a single page
  - - - Can become fragmented with unused pages in the file
      - Solved with cleanup processes like vacuuming
    - - Temporarily use extra-space until compaction finishes
  - - - They can repeat
      - Combine them with the row ID
      - Or store a list of IDs for relevant rows
    - - Data stored in the index directly
    - - Index stores a ref
        
        Primary key
        
        Disk location
      - Actual data lives in a heap file
    - - Middle ground
      - Storing extra columns in the index
      - -> Some queries answered without having to look up the actual data
- - - - works well for large DS analyzing
    - - Examples
        
        Snowflake
        
        Redshift
        
        BigQuery
      - Integrate easily with other cloud solutions
        
        -> simpler to build pipelines
      - Modern architectures split system into parts to make it ^ flexible
        
        Query engine
        
        Storage format
        
        Table format
        
        Data catalog
  - - - Data warehouses
      - Embedded DBs
      - File formats
      - TimeSeries DBs
    - - Techniques
        
        Bitmap encoding
        
        n col values -> n bitmaps
        
        Run-length encoded - store info on consecutive equal bits
        
        Use bitwise ops
    - - In-mem row buffer
      - Batch write and merge w/ col-encoded files
  - - - High disk I/O throughput
      - CPU cost
      - Broken down into query plan
        
        Consists of stages/operators
        
        Query compilation
        
        Generate and compile machine code for that query
        
        Vectorized processing
        
        Apply built-in operations to batches of column values and bitmaps
        
        Both approaches are very eff in terms of taking advantage of modern CPU
        
        Preferring sequential memory access over random
        
        Most of the work in tight inner loops
        
        Making use of parallelism
        
        Operate directly on compressed data
  - - - -> Faster reads
      - Have to be rewritten upon data updates
      - Extra work on writes but worth it when many queries use same
      - Tables storing precomputed results from a query
      - Data Cubes (OLAP Cubes)
        
        Precomputes aggregates across multiple dimensions
        
        Make those aggregate queries super fast but less flexible than raw data
  - - - Answer range queries across multiple dimensions at once
      - -> Crucial for geo-spatial data
    - - Search a collection of docs by keywords that might be anywhere in the text
      - Each term is treated like a dimension
      - Inverted index maps each term to the documents containing it
  - - - Flat
      - Inverted File (IVF)
      - Hierarchical Navigable Small World (HNSW)