ASPLOS'20
Youmin Chen♭†, Youyou Lu♭†, Fan Yang♭†, Qing Wang♭†, Yang Wang‡, Jiwu Shu♭†∗
Department of Computer Science and Technology, Tsinghua University♭Beijing National Research Center for Information Science and Technology (BNRist)†The Ohio State University‡
本文是清华大学舒继武团队发表在ASPLOS 2020上的一篇文章，主要内容是针对当前小KV+write intensive的workload以及基于最新的Intel Optane DC / Infiniband设计一个KV Store。这个KV Store采用的是NVM Log Structure + 内存索引的结构，数据先写入NVM Op log，再更新内存索引。其中NVM log structure针对Optane DC的特性设计了Compacted Oplog以及Lazy-Persisted Allocator，并提出Pipelined Horizontal Batch技术优化了batch写入的过程。
背景
Workload的特征
现有的各种生产环境的workload中，小KV占比越来越多，文中指出Facebook ETC Memcached pool中40%的item都小于13B，70%的item都小于300B。另一个特征是workload从read-intensive逐渐变成write-intensive，对KV Store也要求能够处理write-intensive的workload。
现有的索引结构的写放大问题
现有的各种索引结构都会造成写放大，比如对于树结构，shift / split / merge都会对数据进行额外的读写，对于哈希，搬动item以及resize同理。而这些数据结构再NVM上之后，一次put可能造成多次的NVM写造成写放大：1）更新kv数据；2）更新allocator数据；3）对index结构的更新。
Optane DC Persistent Memory
CPU Cache line的粒度为64B，但是Optane DC的写粒度是256B，如果只flush一个cache line则造成了Optane带宽的浪费，文中对FAST&FAIR进行了测试，（a）图显示，Optane裸盘的带宽是FAST&FAIR带宽的17倍，背后的原因就是FAST&FAIR产生大量的小写，是对带宽的浪费。
本文还提出了两点Optane DC的特性：
1） 在高并发下，随机顺序访问性能接近
测试结果可以看图（b），Optane的随机顺序写带宽随着线程数增加，其性能逐渐接近，主要原因是在高并发的情况下，顺序写基本也就算是随机写了。
2） 对同一个cache line的重复flush会被延迟
测试结果如图（c），其中in-place update是对同一个cache line的就地更新，其延迟相比另外两种情况有很大的增加。文中猜测其原因可能有两个方面，一是clwb是异步执行，后面的clwb需要等前面的执行完；二是可能受Optane内部的磨损均衡管理的影响。
现有的Log Structure的问题
上面提到的index的问题，一个直观的解决办法就是使用日志结构。但是在NVM上使用日志结构仍存在一些挑战：
1）NVM的写粒度限制了batch的大小
一般来说采用日志结构都会将entry通过batch的方式，将多个entry组合成存储设备的写粒度然后再写下去，这在传统的块设备上使用较多。但是NVM的写粒度只有256B大小，这样能batch的entry数目就受到了限制。而如果batch太大，在多线程下就没有顺序写优势了，还不如不batch。同时日志结构对空间管理也需要额外的元数据，这也增加了需要写NVM的次数。
2）batch会增加写延迟
日志结构需要先等待请求达到batch数目之后才写下去，等待的过程无疑也是增加延迟，尤其是在现在采用NVM以及高速NIC的情况下，更多系统采用的是polling + 每个核单独处理各自请求的情况下，每个核需要达到batch数目的请求需要更多的等待时间。
设计
Overview
针对上面提到的各种问题，本文希望构建一个最小化写开销、低延迟以及多核扩展的KV Store，于是提出了FlashStore。总体结构上FlashStore分成了内存中的volatile index和PM上的op log，这个结构倒没有多大的创新，本文的重点也在PM的log的设计上，主要提出了Compacted OpLog，Lazy-persist Allocator以及Pipelined Horizontal Batch这三项主要技术。内存中的结构分成了两种实现，分别用了哈希表和B+树（MassTree）结构。
对于Update操作，FlashStore将操作以entry的形式存储到OpLog中，其中小KV和元数据直接存储到log中，大KV则单独通过allocator存，最后更新内存索引。读操作则直接从内存索引中获取对应kv的位置。
Compacted OpLog
目的：尽量减小log entry的大小，让一次batch能处理更多的请求
设计：
OpLog中每个entry为一次更新操作，各个域的含义为：
1）Op：操作类型，2bit
2）Emd：标示KV的存储位置，2bit
3）Version：更新的不同版本的数据，用于协助log clean，20bit
4）key：FlashStore目前支持8字节的inline key，也可以通过out-of-place的方式支持更长的key
5）value / ptr：对于小于256B的value直接存储到log entry，否则通过lazy-persist allocator存储而此处只记录ptr
Padding：采用batch的时候，不可能总是刚好能够让batch跟cache line对齐，比如下面这种情况：
这个时候flush玩Batch1就可能会导致Batch2的flush被延迟（背景里面提到的Optane的特性之一），所以为了解决这个问题，FlashStore会在log后面添加padding，使得batch能够cache line对齐。
Lazy Persisted Allocator
背景与原理：一般来说allocator内部都需要维护一些元数据来记录空间分配的情况，比如bitmap等，在数据分配之后，需要更新这些元数据结构，带来写NVM的开销。本文观察到，在数据被写入并记录到log之后，ptr就已经记录了value的位置，这就已经足够作为allocator的元数据，因此allocator中的元数据就不必要立刻flush，就算此时crash了，也可以通过ptr中记录的数据进行恢复，也就是lazy-persist
Allocator设计：
整个NVM空间分成4MB大小的chunk，chunk内分成大小相同的data block，data block有不同的粒度，chunk头部会记录当前chunk的block大小以及一个记录分配情况的bitmap。
分配的时候选择最合适的block进行分配，然后更新bitmap，此次更新不进行flush。
恢复的时候可以通过ptr中记录的offset记录data block所在的chunk，以此来恢复chunk的bitmap。
基本操作
Put
1）在allocator中分配空间，写入数据并持久化（只有大KV执行这一步
2）更新log，并更新log的tail pointer
3）更新内存索引
对于update操作，采用的是out-of-place更新的方法，同时FlashStore中key按照key的hash交给不同的核处理，因此不存在read-after-delete的问题，所以旧数据的占用空间可以立刻被回收。
这样一次put只会执行3次flush，如果是小kv则是2次。
Pipelined Horizontal Batch
Vertical Batch
通过batch可以更进一步减少flush的次数，提升Optane的带宽利用率，对于一个N条put的batch，flush次数从3N减少到了N+2次，如上图中的（a）和（b）。
Vertical Batch是指每个core只batch自己core上的数据的方式，这种方式的缺点是需要等待足够数量的log才能提交，因此增加了延迟，如上图中的（b）。
Horizontal Batch
为了优化这种情况，FlashStore首先提出了Horizontal Batch的方式，核心思想就是core在构造batch的时候可以将其他core的entry“偷取”过来，减少等待的时间。将put操作分成3个阶段：1）l-persist：空间分配以及持久化KV；2）g-persist：persist log entry；3）volatile：更新内存索引。
Horizontal Batch的具体步骤：
- 各个core完成l-persisit阶段；
- 将待持久化的log entry的地址写到自己的request-pool中；
- 尝试获取global lock；
- 成功获取global lock的core成为leader，leader从其他core（follower）的pool中获取log entry；
- 释放global lock，通知其他核持久化完成；
- 同时更新内存索引；
具体过程可以如上图（c）
这种Batch策略有一个缺点就是，当leader在处理请求的时候，其他核什么也干不了，浪费了CPU cycle，所以为了解决这个问题，本文更进一步提出了Pipelined Horizontal Batch。
Pipelined Horizontal Batch
核心思想：leader core处理log的时候，其他的core立刻继续去poll请求，仅异步地等待leader core完成log持久化的通知。
可能存在的问题：紧接着一个正在被leader处理的put后面的get请求会失败。
解决：维护一个conflict queue，存在冲突的key的请求会进行排队。
可能存在的问题：multi-socket下只用一个global lock的开销较大。
解决：将server core分组，每个组单独执行各自的pipeline，目前比较优化的配置是每个socket一个锁。
其他的还有空间回收和恢复，空间回收是通过每个core发起一个单独的回收线程进行，将有效数据读出来并搬到新的chunk。恢复分成两种情况，正常退出的时候会将内存索引也写到NVM，然后将allocator的元数据都flush一次并设置一个正常退出的flag。意外退出则需要遍历数据来恢复。
最后的测试结果也是比LevelHash / CCEH / FAST&FAIR & FPTree都要高很多，而且从测试结果来看pipelined HB对性能提升还是很大的
