KVell: the Design and Implementation of a Fast Persistent Key-Va
1.Background
传统的存储设备和CPU之间存在巨大的速度差异，随机访问和顺序访问之间也存在巨大的速度差异。
访存速度是KVs的瓶颈。为此通过投入一些CPU时钟周期去优化访存的速度是一种良好的策略。为了提高访存速度，传统的KVs通过投入一些消耗CPU的操作，避免随机访问实现顺序访问，如数据在磁盘上的有序性和同步等操作。
现代的块寻址的SSD设备提供了非常高的带宽，相似的随机和顺序读写性能。
2.Problem
1.传统的KVs没有考虑新型SSD的新特性，原有的一些优化反而加重了CPU的负担，得CPU成为了KVs的瓶颈。
RocksDB：CPU的60%的时间都需要花费在Compaction上(合并：28%；构建索引：15%；剩下的时间用于：读写磁盘数据 )
B-tree：CPU的主要开销在同步操作上，47%的时间用于等待日志的插槽（全局的序列号更新的不够快）；12%的时间用于从page cache中evication dirty data；5%的时间用于管理commit log；25%的时间用于内核读写调用；18%的时间用于执行客户端请求；
B∈ tree：CPU的主要开销在同步操作上，30%的时间用于锁或者原子操作用于保护共享页；多于20%的时间用于将数据从buffer移动到在磁盘上所在的位置。
2.LSM 和 B tree KVs会有显著的性能波动(延迟也会波动，可能导致尾延迟大)，也会导致性能和尾延迟不好预测。
LSM tree：updates 需要等待compactions完成（第一层满，原因还是在于compaction消耗大量cpu，cpu是瓶颈）
B tree：evictions 操作不够快。
LSM 和 B tree其根本原因都在于其维护操作不够快从而导致客户端请求阻塞。
3.Motivation
1.针对新设备的特性设计出一种能够充分利用磁盘带宽的KVs设计准则。
2.新的KVs应该更加关注如何充分利用CPU
4.KVell design principles
强调CPU的低开销
4.1Share nothing
目的：不共享有助于并行和最小化各个线程之间通信的CPU开销；
实现机制：每个线程独立的处理读写请求，每个线程只负责处理给定keys集合的一个子集，每个线程维护了一个私有的数据结构去管理这个key的子集。
数据结构包括：
在内存中的轻量级索引：B-Tree索引用于追踪key在持久化存储上的位置
I/O队列：有效地存储和从持久存储器中检索信息。
Free list：在内存中的磁盘块列表，其中记录了适合存储项的空闲位置。
page cache：使用自己的页面缓存，不使用OS的。
扫描操作是唯一需要线程同步的操作
Share nothing 通过分区来实现，但分区的请求可能导致负载不均衡。
4.2Do not sort on disk，but keep indexes in memory
目的：减少key插入(不需要先找到合适的位置)的开销，消除维护磁盘上的数据结构的CPU开销。
每个工作线程不需要对它工作集中的key进行排序，直接将它存储到磁盘上的最终位置，可以有效降低写操作的延迟。
4.3Aim for fewer syscalls，not for sequential I/O
目的：使用批处理随机I/O，随机I/O是为了消除原有为了实现顺序I/O而浪费的CPU时钟周期，批处理是为了减少系统调用次数从而减少CPU开销。
批处理随机I/O：在新型SSD上顺序I/O≈随机I/O，所以采用随机I/O。批处理需要在peak IOPS和latency之间进行权衡。
每个工作线程只能将文件存储在一个磁盘上。这样做的考虑是限制每个磁盘上的请求数量。
因为share nothing的设计，所以各个工作线程之间不会通信，他们不能知道其它工作线程给某个磁盘发送了多少请求。
如果每个工作线程只能将数据存储到一个磁盘上，那这个磁盘上的最多请求数为batch size * 该磁盘上的工作线程数。
如果每个工作线程能将数据存储到所有的磁盘上，那一个磁盘上的最多请求数为batch size * 所有的工作线程数。
请求分发给工作线程是根据他们的key值，此外工作线程只访问一个磁盘，可能存在一个倾斜的工作负载（大部分data都访问同一个磁盘，从而让其它磁盘空闲）
4.4No commit log
KVell:只有当数据持久化到磁盘上以后才会承认更新，所以不需要提交日志。
不采用提交日志可以充分利用磁盘带宽去处理客户端处理请求。
5.KVell implementation
https://github.com/BLepers/KVell
5.1Client operations interface
writes: Update(k,v); reads: Get(k);Scan(k1,k2);
5.2On-disk data structures
目的：为了避免磁盘碎片化，将item放入与item大小想匹配的file/slab中。
KVell以块粒度访问slabs，它的大小跟page一样大(4KB)。
如果item size 小于 page size，KVell会在slab的item前添加时间戳、key size和value size等信息。
如果item size大于 page size，在其所使用的每个块的开始位置添加时间戳头。
对于更新操作：
item size < page size： 就地更新
item size > page size: 将更新追加到slab中，然后在原来的位置写入tombstone。
item size发生改变：首先在新的slab中写入item，接下来删除旧的item。
5.3 In-memory data structures
Index
目的：查询item在磁盘上的位置。
KVell为每个工作线程创建了一个在内存中的索引（用来存储磁盘上项的位置）。
Items通过它们的前缀进行所以，没有采用hash的原因是为了方便扫描操作。
对于中型和大型的items，B树的性能差，占据过多的内存空间。
prefix、location information、B-tree structure
Page cache
目的：避免频繁访问持久化存储设备。
页面缓存会记录缓存了索引中那个page和那些page按照LRU的顺序从cache中被驱逐。
Free list
free list = slab's free list，一些已经释放的slab list/stack。
当删除一个item时，它所在的slab会被插入每个slab在内存中的堆栈(slab's free list)，同时在item 在disk上的位置写入tombstone。
限制在内存中的大小，同时保留批处理I/O一次重用多个块的能力(不需要额外的磁盘访问)。
5.4 Efficiently performing I/O
采用AIO，通过批处理的方式，可以决定队列深度，通过多个请求来摊分系统调用的开销。
MMap I/O依赖于OS级的page cache、所以当数据集不能全部装入RAM中时，内核需要进行频繁的map和un-map页面替换，影响CPU性能。
单线程：一次只能发出一个磁盘读请求；脏页定期刷新到磁盘上会导致I/O的爆发，SSD队列深度大部分时间处于次优状态；
多线程：当页面LRU时，需要lock；使TLB条目无效；使所有访问过该page的核上的虚拟地址到物理地址的映射无效，产生显著的IPI通信开销。
Direct I/O：同步的I/O，不需要处理复杂的map和un-map问题。
5.5 Client operation implementation
update：modify就地modify；delet的value = tombstone，将其slab加入free list中；add有空闲块则重用，没有则append。
scan：1从索引中获取keys的位置；2读相应的页；KVell需要扫描所有线程的索引，对所有索引进行加锁，然后轮流解锁。
5.6 Failure model and recovery
当系统崩溃时，通过扫描所有的slab块然后重新构建在内存中的索引。
如果一个item被扫描到两次，选择将most recent item保存在内存索引中，另一个释放掉。
5.Evaluation
详见原文
6.写在最后的话
以上内容为阅读完的自我总结，英文原文请自行搜索，中文翻译版可参考：
[KVell: the Design&Implementation of Persistent KVs - 知乎 (zhihu.com)](https://zhuanlan.zhihu.com/p/328243422)
