Please enable JavaScript.

Coggle requires JavaScript to display documents.

Storage & Retrieval (OLTP: Online Transaction Processing…

- - - - Hash Indexes
        
        In-memory hash map - every key is mapped to a byte offset in the data file, the location where the value can be found. Location on disk. Pairs appear in the order written, values later in log take precedence over values for same key written earlier
        
        When new key value appended, update hash map to reflect offset
        
        Only append, log broken into segments
        
        Compaction - throws away duplicate keys, keeps only most recent update for key. Merge several segments together during compaction. So values on disk are also deleted during compaction process
        
        File Format: Binary - first encodes length of string in bytes followed by raw string
        
        Deleting records - to delete key and value, append a special deletion record called tombstone. When segments are merged, tombstone tells merging process to discard previous values for key
        
        Crash Recovery - db restarted, in-memory maps lost. Can store snapshot of each segments hash map on disk and can be loaded to memory.
        
        Partially written records - use checksums to detect and ignore corrupted records
        
        Concurrency control - writes are sequential, so have a single writer thread. Segments are immutable, can have multiple reader threads
        
        E.g. - Bitcask
        
        Disadvantages
        
        Hash table must fit in memory, large keys, becomes issue. On disk hash map is not efficient
        
        Range queries are not efficient - need to look up each key individually
      - SSTables and LSM-Trees (LSM Storage Engines)
        
        Sequence of key-value pairs is sorted by key - Called SortedString Table
        
        Advantages over Hash Index
        
        Merging segments is simple and efficient - use merge-sort algorithm
        
        Finding keys - need not keep index of all keys in memory. Can keep sparse index, find the offsets for two keys that encompass the key being searched and scan the range
        
        Since records have to be scanned, can group records in range to a block, compress and write to disk. Each entry in sparse in-memory index then points to start of compressed block
        
        Constructing and Maintaining SS Tables
        
        When write comes in, add it to in-memory balanced tree data structure - for e.g. red-black tree or AVL tree. This tree is called memtable
        
        When memtable gets larger than threshold, few MB, write it to disk as SSTable. New SSTable becomes most recent segment of db
        
        In order to serve a request, first try to find key in memtable, then in most recent on-disk segment, then in the next older segment etc
        
        Periodically, run a merging and compaction process in background to combine segment files and to discard overwritten or deleted values
        
        To handle crashes, keep log of most recent writes
        
        Making LSM Tree out of SSTables
        
        Above algorithm is called Log-Structured Merge Tree
        
        E.g. - LevelDB, RocksDB, Cassandra, HBase
        
        Lucene - Full Text Search - key is word and value is list of IDs of all documents containing that word
        
        Performance & Optimizations
        
        For keys that do not exist in db - would have to search memtables and all segments. To avoid - use a Bloom Fitler
        
        Bloom Filter - memory efficient data structure that approximates contents of a set. Can tell you if a key does not appear in the db
        
        Strategies for order and timing of how SSTables are compacted and merged
        
        Size-Tiered compaction
        
        Newer and smaller SSTables are successively merged into older SSTables
        
        HBase, Cassandra (supports level-tiered too)
        
        Leveled compaction
        
        Key range is split into smaller SSTables and older data is moved into separate levels which allows the compaction to proceed more incrementally and use less disk space
        
        LevelDB and RocksDB
    - - Use BTrees for index/. Relational as well as Non-Relationsl
      - Log structured indexes write sequentially to variable size segments which could be in the order of MB. BTrees write to fixed size blocks usually of 4 KB and usually read and write to one page at a time. Corresponds to hardware which have fixed size blocks
      - One page is designated as the root of the B-tree; whenever you want to look up a key in the index,you start here. The page contains several keys and references to child pages.Each child is responsible for a continuous range of keys, and the keys between the references indicatewhere the boundaries between those ranges lie.
      - If you want to update the value for an existing key in a B-tree, you search for the leaf pagecontaining that key, change the value in that page, and write the page back to disk (any referencesto that page remain valid). If you want to add a new key, you need to find the page whose rangeencompasses the new key and add it to that page. If there isn’t enough free space in the page toaccommodate the new key, it is split into two half-full pages, and the parent page is updated toaccount for the new subdivision of key ranges
      - In order to make the database resilient to crashes, it is common for B-tree implementations toinclude an additional data structure on disk: a write-ahead log (WAL, also known as a redo log).This is an append-only file to which every B-tree modification must be written before it can beapplied to the pages of the tree itself. When the database comes back up after a crash, this log isused to restore the B-tree back to a consistent state
      - As a rule of thumb,LSM-trees are typically faster for writes, whereas B-trees are thought to be faster for reads .Reads are typically slower on LSM-trees because they have to check several different data structuresand SSTables at different stages of compaction.
      - An advantage of B-trees is that each key exists in exactly one place in the index, whereas alog-structured storage engine may have multiple copies of the same key in different segments. Thisaspect makes B-trees attractive in databases that want to offer strong transactional semantics: inmany relational databases, transaction isolation is implemented using locks on ranges of keys, andin a B-tree index, those locks can be directly attached to the tree[5]. InChapter 7 we will discuss this point in more detail.
  - - - Primary
      - Secondary
        
        Crucial for joins
        
        Indexed values are not unique. Can be handled by making each value in the index a list of rmatching row identifiers or appending a unique id such as row number to it
        
        Key is what is searched on, the value can be one of two things - the row itself (clustered index) or a pointer/reference to the location (heap) where the row is stored. Makes it useful when multiple secondary indexes are present
        
        Compromise between the two - covering index which stores part of the row with the index
      - Multi-Column index - The most common type of multi-column index is called a concatenated index, which simply combinesseveral fields into one key by appending one column to another (the index definition specifies inwhich order the fields are concatenated)