设计一个Key Value Store

---

Scenario

Set a key to a value,
get a value given a key
和面试官澄清数据量有多大。

Service

Api:
Put(K Key, V value)
V get(K key);
Delete(K Key);
这个不是web服务器， 所以先不用画web server了。
因为这就是一个data base， 所以这一步先不画图了， 没什么图可以画。

最基本的实现

写在本地文件里面，实现了持久化。
每次get的时候遍整个文件把它读出来
每次delete的时候 遍历整个文件，把它删掉。（删的时候移动或者不移动都可以，最好是不移动）
Bottle neck在哪里：
每次都要遍历整个文件，太慢了， 不scalable。
硬盘读取太慢。

第一步优化。

在硬盘里进行二分排序， 可以加快查找速度。
Bottle neck在哪里：
查找虽然提高了， 但是写入的时候为了保持有序性就太慢了。

第二步优化

写在内存里面，同时写一份log保证数据不会丢。
内存里排序可以加快速度，避免硬盘读写。也可以用treeMap或者skip list的数据结构。
Bottle neck ： 内存太小了， log可能有点大。

第三步优化

一里内存写满了，我就把多出来的部分写到硬盘里面去。硬盘上的数据都是有序的。内存里的数据也是有序的。硬盘上可以进行二分查找。 内存里查找速度本来就很快也不是个事。
Bottle neck: 硬盘上不好修改 + 可能有很多小块。

第四步优化。

不修改。只写。有重复的数据过来时每次只是快速写入内存和log，不修改。同时对每一个数据加一个time stamp。
查的时候找timestamp最近的那个。
查找的时候需要对每个block 进行二分查找，其实可以从最后的block开始找起，一旦找到就不再找了。

第五步优化。

内存又满了。重新开一块硬盘再写进去。硬盘上的小块越来越多，可以进行external merge sort操作把小块合并成大块。
现在已经有一个working solution了
现在可以improve的地方有：硬盘二分查找还是很慢，单机容量太小。

第六步优化。

对硬盘上的每一个block建index， 同时建bloom filter
index： 我们只有一个key， 就按这个key建index , 每个block都要建一份。
bloom filter: 如果bloom filter 判断这个key不在这个block里面，就不要找了。
index和bloom filter保存在硬盘上和内存里。

第七步优化，解决单机存不下的问题。

单机存不下，就用多台机器，进行水平切割。
依据什么进行水平切分： 根据key来进行。因为我们是根据key来查询。而且只有这么一个东西其实。
如何进行水平切分：Hash partition or range partition? Range partition的话，因为key无法预见， 所以还是要用hash partition. Hash Partition的话，可以通过随机的方式把key放在不同的机器上。如果数据量足够大，可以实现的比较均匀。
引入consistent hashing的概念.
当机器少的时候，可能还是不均匀，引入virtual node的概念。

第八步优化：解决数据安全问题

进行replica，一式三分，存在三个不同的机器上。

第九步： 备份多了，如何写？

Master slave。
选队长。

问题1： node 挂了怎么办。

node发heart beat给master
master发现谁挂了，就首先不给它分摊读请求，然后把它上面的数据放在其他node上。

问题2： 一个node 挂了，然后他又醒过来，怎么。。

他上面的数据是过时的，可是他自己并不知道， 这时应该怎么办？
对每个node保存一个version number，醒过来之给服务器汇报一下自己的version number, version number旧的就不对了。

---

三月份的笔记
内存用TreeMap? 红黑树
同时用Write ahead log备份
满了写到硬盘上开一个新的文件。
可能有很多新的文件， 每个文件都最排好序的。
查找的时候在每个文件里面进行二分查找，先从最近的文件开始查到。
设计bloom filter， 设计index. 放在内存里面
定时整理硬盘,

更改

直接append到最后

Sharding:

按key sharding, 一致性哈希

其他问题

如果一个key经常查询又查不到怎么办。