Design KV Store

Design KV Store

1. Scenario

a. Storage Estimate: 100TB, QPS Estimate: 100k (sharding is necessary)

b. Architecture Selection (High Availability: Peer to Peer, 因为如果用master slave pattern，当master down了需要重新选择master的时候，写变得不available, High Consistency: Master-Slave)

2. Service

a. Read

同样是Big Table的方法

• 先检查内存的skiplist有没有

• 通过bloom fileter(false is always false)检查是否在sstable里

• 然后利用index找sstable的data

b. Write

• 用Bigtable的写方法,先写到log，再写到内存，然后size到达一个阈值则将内存的memtable flush到disk。disk的数据定期通过merge sort做一个compaction

c. Detele

用tombstone mark 被delete的record，在compaction的时候才将不需要的数据删除

d. Tunable Consistency

3. Storage

4. Scale

a. 如何sharding: Consistent Hashing

b.怎么做replication: Consistent Hashing

c. node down了怎么办