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经常查询又查不到怎么办。
