(ASPLOS '20) FlatStore: An Efficient Log-Structured Key-Value Storage Engine for Persistent Memory

2020/09/16 Storage

PM+KVS+Log. FlatStore提出了一个新的Persistent Memory上KV store的优化方案。通过对PM硬件粒度的完全利用,来提升throughput。

story: PM的bandwidth带宽有256B,老是写小键值数据就没办法完全利用。所以很自然一个想法就是把index放在DRAM上,数据的维护用log structure + batch write的方式来提升带宽【类似的,在HDD、SSD上这种粒度更大的,也使用这样的方法来利用带宽】。

但是如果直接用batch(指单核上,vertical),因为核心在flush时会阻塞,使得其他核不能flush,又产生更高的latency。所以本文最中心的方法论就是,跨多核并行(horizontal)的实现batch flush:
leader core可以在获得了lock之后,从其他核心的log queue上获得log压入自己的queue,然后做batch flush。

Pipelined Horizontal Batching的示意图 image.png

第一列是每次写log后直接flush,第二列是单核上做batch flush,第三列是有核心等待的horizontal batch,第四列是通过锁避免核心等待的pipelined horizontal batch。

然后要做的就是压缩batch内entries的大小,增大数量。一个就是大的数据上做键值分离;另一个就是让entries上不存value,存指向数据的指针,使得访问时,有两阶段的映射(从DRAM上的index到log,再到键值数据)

另外的,有几个地方值得提一下。同一个cacheline在重复被写的时候,会产生一个内部的高延迟。log写的方式能够做到异地更新。为了防止连续的两个flush用了同一个cacheline,做padding来补齐。

然后,PM的allocator也通过log来实现lazy-persist:

  1. 从 Lazy-persist Allocator 分配对应保存 value 的空间,并写入数据,然后将这些数据持久化;
  2. 持久化一个 log entry,记录下这个操作和之前写入的数据的信息。然后写入 log,确保持久化之后更新 log 的 tail 信息;
  3. 更新内存中的 index。

如果CPU核心数太多,但单个batch(256B)还是最多放16个entries,就引入grouping分组的策略,组内内部做pipelined horizontal batch。

性能对比: image.png image.png 感觉是不是缺一个和无batch直接写入的latency/throughput对比?

Ref

[1] Chen, Youmin, et al. “FlatStore: An Efficient Log-Structured Key-Value Storage Engine for Persistent Memory.” Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems. 2020.

[2] Several Papers about KV Stores(2) from nan01ab

[3] ASPLOS’20 - Session 12A - FlatStore: An Efficient Log-Structured Key-Value Storage Engine for Persis on Youtube

Search

    Table of Contents