WiscKey: Separating Keys from Values in SSD-conscious Storage

WiscKey is an LSM-tree-based key-value store with a performance-oriented data layout that separates keys from values to minimize I/O amplification. The design of WiscKey is highly optimized for SSDs, leveraging both the sequential and random performance characteristics of the devices. The paper also discusses some of the challenges with this design and proposes feasible solutions to solve them.

Transcript

1. Paper: WiscKey: Separating Keys from Value in SSD-Conscious Storage Authors: Lanyue Lu, Thanumalayan Sankaranarayana Pillai, Andrea C. Arpaci-Dusseau, and Remzi H. Arpaci-Dusseau, University of Wisconsin—Madison Presenter: Arjun Sunil Kumar
2. Agenda 1. Motivation & Use Case 2. Introduction a. LSM Tree b. Write and Read Amplification c. SSD 3. WiscKey a. Key Idea b. Data Flow c. Challenges 4. Variants a. CouchBase b. TerarkDB
3. Motivation & Use Case 3
4. 1950 2011 2017 2021 2006 2008 DB Storage Evolution 4
5. 1950 2011 2017 2021 2006 2008 Storage Data Structure Evolution 5
6. Motivation - Large write/read amplification on LSM-trees of Key-Value Stores holding large Values - LSM-trees are optimized for HDDs; not optimal for SSDs
7. Use Case: Large Values Typically, - Values are not very huge. - For large values, we prefer to store large data(PDF document/Images) in object store and metadata (URL) in the db. But there are use cases where we store - large JSON stored as BLOB in Database - Vector Embeddings stored as BLOB in Database
8. Introduction: LSM Tree 8
9. BTree LSM KV Storage Engine Classification 9
10. In-place vs Out-of-place updates 20 15 25 12 18 20 25 15 12 18 Single Data Structure Collection of Data Structures 10
11. In-place vs Out-of-place updates 20 15 25 12 18 Delete 12 20 25 15 12 18 11
12. In-place vs Out-of-place updates Traverse and update the leaf node inplace. (Might require coarse-grained or fine-grained locking) 20 15 25 12 18 20 25 15 12 18 12 Insert 12 with TombStone Entry (Relatively faster update) Delete 12 12
13. In-place vs Out-of-place updates 20 15 25 18 Read 12 20 25 15 12 18 12 13
14. In-place vs Out-of-place updates 20 15 25 18 Reads are faster as update is applied in-place Read 12 20 25 15 12 18 Merge On Read Reads are slower due to MoR 12 14
15. LSM Tree - Components Memtable Immutable Memtable Disk Memory WAL SST SST SST SST SST SST SST SST L0 L1 L7 15
16. LSM Tree - Components Memtable Immutable Memtable Disk Memory WAL SST SST SST SST SST SST SST SST L0 L1 L7 16
17. LSM Tree - Components Memtable Immutable Memtable Disk Memory WAL SST SST SST SST SST SST SST SST L0 L1 L7 17
18. LSM Tree - Components Memtable Immutable Memtable Disk Memory WAL SST SST SST SST SST SST SST SST L0 L1 L7 18
19. LSM Tree Ops Memtable Immutable Memtable Disk Memory WAL SST SST SST SST SST SST SST SST L0 L1 L7 Write Compaction Read 19
20. LSM Tree Ops - Write Memtable Immutable Memtable Disk Memory WAL SST SST SST SST SST SST SST SST L0 L1 L7 Write 20 <k,v>
21. LSM Tree Ops - Write Memtable Immutable Memtable Disk Memory WAL SST SST SST SST SST SST SST SST L0 L1 L7 Write 21 <k,v>
22. LSM Tree Ops - Write Memtable Immutable Memtable Disk Memory WAL SST SST SST SST SST SST SST SST L0 L1 L7 Write 22 <k,v>
23. LSM Tree Ops - Write Memtable Immutable Memtable Disk Memory WAL SST SST SST SST SST SST SST SST SST L0 L1 L7 Write 23 <k,v>
24. LSM Tree Ops - Compaction Memtable Immutable Memtable Disk Memory WAL SST SST SST SST SST SST SST SST SST L0 L1 L7 Compaction 24
25. LSM Tree Ops - Compaction Memtable Immutable Memtable Disk Memory WAL SST SST SST SST SST SST SST SST SST L0 L1 L7 Compaction 25
26. LSM Tree Ops - Compaction Memtable Immutable Memtable Disk Memory WAL SST SST SST SST SST SST SST SST SST L0 L1 L7 Compaction SST 26
27. LSM Tree Ops - Compaction Memtable Immutable Memtable Disk Memory WAL SST SST SST SST SST SST SST L0 L1 L7 Compaction SST 27
28. LSM Tree Ops - Read Memtable Immutable Memtable Disk Memory WAL SST SST SST SST SST SST SST SST SST L0 L1 L7 Read 28 [1,5] [3,5]
29. LSM Tree Ops - Read Memtable Immutable Memtable Disk Memory WAL SST SST SST SST SST SST SST SST SST L0 L1 L7 Read 29 [1,5] [3,5]
30. LSM Tree Ops - Read Memtable Immutable Memtable Disk Memory WAL SST SST SST SST SST SST SST SST SST L0 L1 L7 Read 30 [1,5] [3,5]
31. Introduction: SSD 31
32. SSD vs HDD HDD SSD Magnetic platters on rotating disk Flash Memory Chip Random reads were slower due to seek Random reads are faster as there is no rotating disks Slower read/writes (100MB/s) Faster read/writes (500MB/s) No limitations Limited number of write cycles New Write can overwrite the Soft Deleted data blocks. Flash SSDs, must erase the Soft Deleted data blocks before new data can be written. No good for random writes due to seek time. No good for random writes due to GC. Img: https://www.backblaze.com/blog/ssd-vs-hdd-future-of-storage/
33. Introduction: W/R Amplifications 33
34. Write Amplification Write amplification occurs when the amount of physical data written to a storage medium is greater than the amount of logical data intended to be written. Image Ref: https://www.usenix.org/system/files/conference/fast16/fast16-papers-lu.pdf
35. Write Amplification Image Ref: http://csl.snu.ac.kr/courses/4190.568/2019-1/30-wisckey.pdf
36. Read Amplification Read amplification refers to the phenomenon where the amount of data read from the storage system is greater than the actual amount of data requested by a read operation. In the case of LSM trees, multiple versions of a record exist across different levels or SSTs. As a result, a single Read operation may require reading multiple data blocks or files to retrieve the most recent version of the requested record.
37. Introduction: Core Problems 37
38. High R/W amplification Image Ref: http://csl.snu.ac.kr/courses/4190.568/2019-1/30-wisckey.pdf
39. Not optimized for SSD Image Ref: https://www.usenix.org/sites/default/files/conference/protected-files/fast16_slides_lu.pdf
40. WiscKey: Key Idea 40
41. Design Goals 1. Low Write Amplification 2. Low Read Amplification 3. SSD optimized (sequential writes and parallel random reads) 4. Feature rich API - Get/Put/Delete, Scan, Snapshot 5. Realistic Key Value Size
42. Key Idea Image Ref: http://csl.snu.ac.kr/courses/4190.568/2019-1/30-wisckey.pdf
43. WiscKey: Improvement #’s 43
44. Inserts - 100 GB data Intensive Compaction + Repeated R/W + Stall Foreground IOs Many Levels Small LSM-tree: less compaction, fewer levels to search, and better caching Image Ref: http://csl.snu.ac.kr/courses/4190.568/2019-1/30-wisckey.pdf
45. Random Lookup - 100K Image Ref: http://csl.snu.ac.kr/courses/4190.568/2019-1/30-wisckey.pdf
46. WiscKey: Design/Challenges 46
47. 1. WiscKey Ops - Write Memtable Immutable Memtable Disk Memory WAL SST SST SST SST SST SST SST SST SST L0 L1 L7 Write 47 <k,vptr> VLOG <k,v> <k,vptr> 1 2 3
48. 2. WiscKey Ops - Delete Memtable Immutable Memtable Disk Memory WAL SST SST SST SST SST SST SST SST SST L0 L1 L7 Write 48 <k,nil> VLOG <k,nil> 1 2
49. 3. WiscKey Ops - Read Memtable Immutable Memtable Disk Memory WAL SST SST SST SST SST SST SST SST SST L0 L1 L7 Read 49 [1,5] [3,5] VLOG 1 2
50. 3. WiscKey Ops - Read Memtable Immutable Memtable Disk Memory WAL SST SST SST SST SST SST SST SST SST L0 L1 L7 Read 50 [1,5] [3,5] VLOG 1 2
51. 3. WiscKey Ops - Read Image Ref: http://csl.snu.ac.kr/courses/4190.568/2019-1/30-wisckey.pdf
52. 3. WiscKey Ops - Read Memtable Immutable Memtable Disk Memory WAL SST SST SST SST SST SST SST SST SST L0 L1 L7 Read 52 [1,5] [3,5] VLOG 1 2 Buffer
53. 4. WiscKey Ops - Key Compaction Memtable Immutable Memtable Disk Memory WAL SST SST SST SST SST SST SST SST SST L0 L1 L7 Compaction SST 53 VLOG
54. 4. WiscKey Value Compaction/GC Image Ref: http://csl.snu.ac.kr/courses/4190.568/2019-1/30-wisckey.pdf
55. 4. WiscKey Value Compaction/GC Image Ref: http://csl.snu.ac.kr/courses/4190.568/2019-1/30-wisckey.pdf
56. 4. WiscKey Value Compaction/GC Image Reference: https://www.skyzh.dev/blog/2023-12-31-lsm-kv-separation-overview/#terarkdb
57. Separation of Key and Value bring concerns on consistency 1. What if value was written and before writing key we crashed? 2. Can vlog have corrupted value? (ie random values) NOTE: - Values are appended sequentially. - We store <K,V, KSz, VSz> 5. Crash Consistency
58. 5. Crash Consistency Image Ref: http://csl.snu.ac.kr/courses/4190.568/2019-1/30-wisckey.pdf
59. Further Optimizations 1. VLog Buffer a. Not for synchronous inserts. b. Buffer writes in Memory and then all fsync() c. During lookup we check VLog Buffer first. 2. Reuse VLog as WAL. a. Record head of VLOG periodically in LSM Tree as <K,V> <head, vptr>
60. Variants 60
61. Magma - From Couchbase Image Ref: https://www.vldb.org/pvldb/vol15/p3496-lakshman.pdf
62. Terrark - From Bytedance In the LSM tree, TerarkDB only stores the keys corresponding to the large values and the file number where the value is located, <key, fileno>, without storing the offset of the large value. Read first needs to find the v-SST file corresponding to the key in the LSM tree. Then, it accesses the latest v-SST based on the dependency relationship and finds the corresponding key in the index of v-SST, and then accesses the value. Image Reference: https://www.skyzh.dev/blog/2023-12-31-lsm-kv-separation-overview/#terarkdb
63. Thank you! Icons: - flaticon.com - thenounproject.com 63
64. WiscKey: Implementation 64
65. Parallel Read
66. GC
67. Extra 67
68. VLOG Rewrite Issue Image Reference: https://www.skyzh.dev/blog/2023-12-31-lsm-kv-separation-overview/#terarkdb