Paper Reading (1)

Posted on

HiKV

  • A persistent key-value store, constructing a hybrid index in hybrid memory
    1. well-performed scalability
    2. crash consistency guaranteeing
  • Hybrid memory (DRAM and NVM) systems are byte-addressable – providing similar performance for sequential and random access
  • Issue:
    1. Either hash-index or B+Tree cannot efficiently support all (Put/Get/Update/Delete/Scan) operation.
    2. Scan operation becomes important, scan operation is slow in Hash index (without sorted)
  • Features:
    1. A hybrid index consisting of a hash index
      in NVM and a B+-Tree index in DRAM which supports rich KV operation
    2. Concurrency schemes => high scalability
    3. Ordered-write consistency + specific hash design => atomic write => crash consistency with reduced NVM write
  • Operation procedure:
    1. writing KV items to NVM
    2. writing newly-added index entry to hash index(NVM)
    3. insert Put request to updating queue in memory
    4. back-end thread gets the request and operates the B+tree in background

RAIAD

  • persistent single machine
  • based on Log-Structured Merge(LSM Tree)
  • Three Components: Memory(C) / Disk(L) / Commit Log(CL)
  • Three motivations:
    1. Data skew unawareness
    2. Premature and iterative compaction, data skew increases the probability that multi L file has the same key
    3. Duplicate writes: CL => L + C => L
  • Two operations:
    1. Flushing, when C or CL is full
    2. Compaction, Merge files(SStables) in background, overlapping key ranges
  • Fit with different workloads
    1. Skewed => Triad-Mem => Flushing and Compaction
    2. In-Between => Triad-Disk => Compaction
    3. Uniform => Triad-Log => Flushing
  • optimization techs
    1. Keep hot keys in memory / Flush only cold keys / Keep hot keys in Commit Log (hots => Duplicate keys)
    2. Defer file compaction until the overlap between files becomes large enough, merge lots of duplicate keys
    3. Convert CL to a special L0 SSTable(CL-SSTable). Avoid flushing the memory together, play in LSMs and using them in a manner similar to SSTables.

Soft Updates Made Simple and Fast on Non-volatile Memory

NV-Tree: Reducing Consistency Cost for NVM-based Single Level Systems

Octopus

  • Design
    1. Shared persistent memory pool => reduce data copy
    2. self-identified meta-data RPC => reduce response latency
    3. Client-active data I/O => rebalance CPU/network overhead
    4. Collect-dispatch transaction efficient CC (RDMA CAS lock)

REWIND: Recovery Write-Ahead System for In-Memory Non-

Volatile Data-Structures