Ch3 Storage and Retrieval

Two engines:

• log-structured storage engine

  • basically appending in a log and keep indexes in a hash map
  • pros:
    • appending & segment merging are sequential write, faster than random write
  • cons:
    • hash table has to be in memory
    • range queries difficult, k1234-4455
  • SSTables & LSM-Trees
    • SST(sorted string table), sparse in-memory index table, memtable before saving on disk as SSTable,
    • one can use red-black trees / AVL trees to maintain the order
    • log-structured merge-tree
    • very painful to search as it has to go through, memtable, segment maybe disk, can be mitigated using bloom filter
    • advantages: sequential -> reduce write amplification, compaction makes storage smaller

• page-oritented storage engines (e.g., B-tree)

  • balanced trees

• Transcation processing / analytics

  • OLTP (online transcation processing)
  • OLAP (online analytic processing)

• Datawarehousing

  • ETL (extract, transform, load)
  • Star and snowflake: schemas for analytics

• Column-oriented storage

  • faster to query

Ch4, Encoding and Evolution

• backward: newer code can read data written by older code
• forward: older code can read data written by newer code

---

Part II, distributed data

---

Replication

Goal

• reduce latency (close to the user)
• increase availability (some cluster may fail)
• increase read throughput