# 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了怎么办
