Chapter 9 KV Store

Refer:

• https://soulmachine.gitbooks.io/system-design/content/cn/key-value-store.html (github: https://github.com/henrywoo/system-design)

• https://github.com/xuchongfeng/kvstore

Industry Examples:

• DynamoDB: https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf
• S3
• BigTable/HBase/Hypertable
• Cassandra
• Redis
• Memcached

9.1 HashTable/HashMap, Concurrency HashMap

9.2 B-Tree

9.3 LSM-Tree

Sequential Write ==> Sorted String Table

Hashing: Hash from key to offset in log file! Not key to value.

Compaction: throw duplicated key in the log and keep the latest version of record.

Bloom filter

9.4 DHT(Distributed HashTable)

9.5 Eviction

9.5.1 LRU

http://sde.quant365.com/augmented-data-structure.html#lru-cache

list.emplace_front(), list.erase(), list.pop_back(), list.back(), list.splice()

https://www.geeksforgeeks.org/list-splice-function-in-c-stl/

map.at(), map.erase()

Java:

LinkedHashMap

https://www.geeksforgeeks.org/linkedhashmap-removeeldestentry-method-in-java/

9.5.2 LFU

http://sde.quant365.com/augmented-data-structure.html#lfu-cache

list.emplace()

Java:

LinkedHashSet

9.5.3 LFU Variant

http://sde.quant365.com/augmented-data-structure.html#all-o1-data-structure

http://sde.quant365.com/bloomberg-2017.html#marathon-ranking-topk

9.6 Durability

9.6.1 Gossip and failure detection

9.6.2 Commit log

9.6.3 Hinted Handoff

9.6.4 Read Repair

9.6.5 WAL, Btree, COWs

https://cwiki.apache.org/confluence/display/HUDI/Design+And+Architecture#DesignAndArchitecture-ReadOptimizedQueries

9.7 2PC (2 Phase Commit)

Problem:

https://cs162.eecs.berkeley.edu/static/lectures/25.pdf

9.8 Reference

• Distributed Systems 2: Distributed Key-Value Stores

• https://www.microsoft.com/en-us/research/uploads/prod/2018/03/faster-sigmod18.pdf

• https://www.usenix.org/conference/fast20/presentation/chen-jiqiang

• https://developer.aliyun.com/article/756819

• https://zhuanlan.51cto.com/art/202003/612496.htm

• http://www.ayqy.net/blog/nosql/