Skip to content

NovKV-2021-3-19.md

Latest commit

 

History

History
63 lines (33 loc) · 2.37 KB

NovKV-2021-3-19.md

File metadata and controls

63 lines (33 loc) · 2.37 KB

Title: NovKV: Efficient Garbage Collection for Key-Value Separated LSM-Stores

Source: MSST'20

Authors: Chen Shen, Youyou Lu, Fei Li, Weidong Liu and Jiwu Shu

Summary

  • The problem the paper aims to solve

    • Key-Value Separated LSM-Stores (WiscKey) introduces extra query and insert overhead in KStore while doing Garbage Collection.

  • How can the paper address the problem? What is the main idea of this paper?

    • Observation

      ① WiscKey runs the KStore compaction and the VStore garbage collection independently, but there are some useful data in the KStore can be used to facilitate the VStore garbage collection.

      ② VStore garbage collection may insert valid value handles into the KStore many times during the entire run time.

    • KStore: Collaborative Compaction

      (1) While doing compaction, KStore creates DropKeys-Map to store the invalid keys and later writes these DropKeys to VStore.

    • VStore: Efficient Garbage Collection

      (1) By using the DropKeys-Map, there is no need for VStore validity checking to query the KStore frequently.

      (2) Design of VTable & SVTable.

    • Selective Handle Updating

      (1) Update on request, while NovKV searches for a value, updates the KStore (Key-Value Handle) in the MemTable.

      (2) Cost of a completely memory write is substantially low.

  • Validations

    KStore Compaction and VStore Garbage Collection have positive feedback interactions. By the elimination of validity checking and handle updating, KStore Compaction is reduced, and then VStore Garbage Collection is further reduced. Finally it leads to Better throughput & Lower write amplification.

    The results of experimentation and analysis show that NovKV indeed achieves higher performance compared to WiscKey.

Strengthens

  • It is an inspiration for the key-value separation system, KStore and VStore are not completely independent, some collaborative information may bring higher performance.
  • Sometimes frequent updates are not necessary, updating on request can reduce some extra overhead.

Weaknesses

  • The idea is straightforward.
  • There may be some contingency in the experiment of random read.

Comments

  • The problem NovKV aiming to solve is clear. It's worth learning the clear analysis of the existing systems.