NovaLSM

感谢作者，原文链接：https://zhuanlan.zhihu.com/p/385151808?utm_source=wechat_timeline&utm_medium=social&utm_oi=640093381867606016

本文核心思想在于研究把LSM KV store进行存算分离，计算和存储分为不同的组件并通过RDMA通信。为了充分利用多存储节点的多disk带宽，memtable的数量会比传统的耦合lsm storage engine要更多，为了解决带来的写放大，通过引入Drange来做compaction的并行化，同时也引入相应索引来解决point/range query的性能问题。与PolarDB Serverless/LegoOS思想类似使用RDMA来做远程数据通信。

Intro

NovaLSM分为三个组件：

LSM-tree Component (LTC)

Logging Component (LogC)

Storage Component (StoC)

LTC和LogC通过StoC做share storage，LTC和LogC可以部署在计算资源丰富/优化过的server；而StoC可以部署在存储资源丰富/优化过的server。

那怎么做SSTable和Stoc之间的映射呢？理论上有以下做法：

1.一个存储节点存储一个range的所有SSTable

2.SStable文件级别散列：一个range由多个存储节点存储，不同的SSTable可以存储在不同节点

3.Block级别的散列：一个range由多个存储节点存储，一个SSTable的Block可以存储在不同节点

而LogC可能是个单点的服务，或者是作为library与LTC一起部署；通过把Logs data复制到内存来提高访问效率；通过把Logs data落盘到StoC层来做持久化。

而StoC则是SSD和disk的层级架构用做缓存和持久化。

和PolarDB Serverless的思路一样，使用RDMA来让LTC来共享StoC层的带宽，从而解决存算分离中因为网络通信而带来的性能下降。

下图是两种架构下的一个吞吐量比较：

挑战和解决方法

Challenge1:Write Stall问题

write stall指的是当所有memtables写满或者某一level的SStable大小达到阈值时要进行compaction，从而在后台中占用大量的IO（落盘）和CPU（排序），导致写入性能在这个时间段会下降。

Nova-LSM的解决方法

通过Divide And Conquer的方法来在运行时构建动态的range：Dranges

目标是用来对写入的负载做均衡，结合并行的compaction来尽可能减少write stall的影响

Challenge2:

当内存容量扩大（memtables数目增加），意味着需要搜索的memtable和sstable也会变多，会使得scan和get操作的效率下降。

本文通过维护额外的索引，标记最新key的value到底是存储在memtable还是在level 0的sstable，如果命中的话就直接省去scan的逻辑，来做查询的剪枝。

Challenge3:

在做SSTable在StoC的散列时，可能会产生一个存储节点同时接受多写的情况，这样多写请求就会在同一个节点排队造成延迟。

解决方法是：

在做存储层的散列时，进行block级别的散列，即一个SSTable的多个blocks会哈希在多个存储节点上，我理解这样的话一个SSTable的compaction或者memtable的落盘就可以尽可能分散在尽量多的存储节点上。

2.使用一种叫power-of-d的写策略：

LTC会把单个SStable划分为p个fragment，并且使用RDMA将这些fragment分别传输到StocC节点，如果存储节点的个数也为p，一对一的哈希就可以消除上面的问题。

但如果p的个数太多的话，带来的disk seek次数和寻道延迟也会增多，会影响share disk的bandwidth，因此一般划分fragment的数目 < 存储节点个数，具体策略在下文介绍。

RDMA

本文和PolarDB Serverless一样通过RDMA来解决存算分离架构中网络的延迟开销所带来的性能下降问题。RDMA核心思想是：Kernal Bypass， ZeroCopy和无需CPU 参与数据的赋值。

传统的网卡上做服务端之间的数据通信，首先CPU要把数据从用户空间拷贝一份到内核空间的socket buffer中，然后内核的TCP/IP协议栈给数据添加头部和校验信息，物理层的网卡通过DMA从内核中copy数据后在发送到别的服务器的网卡上。

而RDMA简单来说就是省去了数据从用户态拷贝到内核态的步骤，不需要CPU参与，报文的组装和解析在硬件层完成。而对于数据库加速来说，通常使用的是READ/WRITE的语义。两个server之间通过一对分别在server的队列（QP）进行异步通信。

线程模型

上面提到节点之间通过RDMA通信是通过QP来实现的，但是RDMA的性能随着QP数量增多会下降，本系统通过每个节点会设置有若干个交换的线程(xchg)来最小化QP的数量。

一个在节点i的xchg线程k负责维护节点i上的QP，并且与其他节点进行通信。

LTC有四种线程：

client worker thread：

接受外界请求

compaction thread：

把immutable memtables flush入StoC，然后协调StoC之间的compaction操作

exchange thread:

负责与StoC的通信

reorganization thread:

负责动态ranges的负载均衡

StoC有三种线程：

exchange thread：

负责与本节点上的其他xchg线程通信和其他StoC/LTC节点上的通信

compaction thread：

进行sstable的compaction操作与文件的落盘

storage thread：

负责block数据的读写

NOVA-LSM的组件

LTC

每个LTC为存储数据划分若干个range，每个range由LSM Tree维护，每个range的视图如下:

其中包括三个约束：

1.memtable内和sstable内的kv数据按照key排序

2.level1以上的数据，数据按照key在多个sstable之间顺序排序

3.level0的数据比以上的数据更up-to-date

Dynamic Ranges：Drange

LTC在内存中维护了大量的Memtable使得大量插入数据都可以暂时存储在内存中减少对磁盘的IO压力，但这也带来了几个挑战：

1.immutable memtable落盘后直接就是level0的sstable，那么这也意味着level0的sstable数量也会相应增多，导致compaction到level1+的时候造成的写放大会更严重。

2.读放大也会相应变大，因为需要scan所有的memtable和level 0的sstable

因此本系统通过Dynamic Range来均衡写入来解决上述问题，可以理解为在原LSM上把memtable数据划分为更小粒度的range称为drange，不同range之间的compaction/write操作相互独立因此可以并行操作，并且还可以根据查询的热点写入的流量负载来对range范围做动态的调整。

以上图为例：

每个Drange的memtable的数量都是相同的，写操作将数据插入到包含其key的drange的memtable中，以避免相同key的不同记录分散在所有的memtable中造成compaction时候的写放大。这样也保证了由不同drange落盘的sstable是互斥不会相互影响，因此可以并行进行compaction。

那么dynamic体现在哪里呢？LTC的reorg thread负责对range进行minor/major reorganizaiton：

minor reorg

通过构造特别小的Tranges在不同Dranges进行传输来调整区间范围，如把热点dranges的部分区间数据转移到临近的dranges

major reorg

通过采样的写入负载频率数据来重新构建Dranges和Tranges

如果某个key是一个写入热点，那么Drange可以为这个单点的range做duplicate，以上图为例key 0拥有两个drange，写入操作可以写到任意一个drange下的memtable中，减少了由同步写入一个memtable产生的开销，也分摊了单个drange的写入负载压力。

本系统针对point query和range query分别做了优化：

Get操作

每个LTC会维护一个lookup index，来维护key的最新value具体保存在哪个level 0的SStable或者memtable。如果index中没有相关记录才去查询更高level的SSTable。并且LTC为每个SStable在内存中维护bloom filter来剪枝。除此之外更高level的SStable的查询操作也可以并行化。

为何如此设计？

为了避免get操作查询所有的memtables和level 0的sstable造成的读放大。

如何更新lookup index？

当写操作插入一条新数据到memtable m的时候，会更新【key, mid】映射，mid用来唯一标记一个memtable。LTC会额外维护一个映射结构：MIDToTable，维护mid到一个memtable的指针或者level 0的sstable的file number。

当compaction操作将immutable memtable从sstable flush到StoC的时候，就会原子地更新这个MIDToTable结构中mid到sstable file number的映射，同时把对应的指向memtable的指针设为无效。

当sstable从level 0compaction到level1的时候，会列举这个sstable的所有key，然后删除MIDToTable中相应的记录。

Scan操作

为每个Drange的memtable和level 0 sstable维护range index，scan操作首先用binary search定位到scan的start key和end key在哪些分区范围，然后搜索第一个分区内所有的memtable和l0 sstable，找不到就再去照l1+的sstable，当一个分区搜索完后在搜索另外一个分区。

Flushing Immutable Memtable的优化

简单来说就是更精细化的阈值设置来尽可能减少落盘数据，尽可能把数据维护在内存的memtable中。

Level0 SStables的并行Compaction

Drange一个很重要的优势就是把原来level 0的compaction task划分为多个并行独立的子任务

LTC会有一个coordinator thread来进行compaction任务的调度，把热点StoC节点上的任务分发给别的空闲的StoC节点。存储节点首先pre fetch所有compaction job中的sstable到memory中，合并完后新的sstables可能会写到本地或是其他存储节点上。compaction完成后，存储节点会向coordinator thread返回所有包含新生成的sstables列表，由其负责删除原来的sstable和更新元数据文件。

SStable Placement

本系统的SStable会划分为更小的粒度data block fragment来分片在不同的存储节点中存储，好处是落盘的时候将disk io开销分摊到不同的存储节点的disk上

每当创建一个sstable，如何决定其划分的粒度以及文件由哪几个存储节点来存储呢？

策略有random和power-of-d，后者指的是假设粒度为p，则在2*p个disk io queue最短的节点中挑选p个节点。

然后p个fragment将会并行写入到不同的存储节点中，然后把index和bloom filter blocks写入到存储节点中。

那可用性如何保证呢？假如其中一个存储节点挂了，那么其中一个fragment就会挂掉，整个sstable也无法对外提供服务。因此要做fragment级别的备份。

本系统为data fragments构建一个“parity block”并且通过复制metadata block来做高可用。

读取请求可以从任意的replica中读取metadata block。

Fragments以及他们的备份和parity block会分布在不同的存储节点上，对应的相关信息则保存在metadata block。

LogC

作为Libaray整合在LTC组件中，提供相应负责Log数据的刷盘和数据恢复的接口。

LogC会为每个Memtable构建log file，每个log记录包括：

（log record size，memtable id，key size，key，value size，value和sequence number）

每个log file要么保存在内存中，通过复制来保证高可用；要么保存在持久化设备中

StoC

提供多种存储介质支持（内存/disk/ssd等），数据以变长block来存储；每个block下划分为更小的粒度：data block fragments。

每个文件由一个全局唯一的文件id来做标识,文件分为两种：

1.In-Memory StoC FIles

当client打开一个文件的时候流程如下：

1.在内存中分配一块buffer，并且把文件的句柄返回给客户端。文件的句柄包括文件id，对应的buffer偏移量和大小

2.client写入数据时client通过RDMA WRITE接口直接把block数据插入到memory的buffer中

3.读取数据时client（如LTC）会在本地内存分配一个buffer，然后由StoC调用RDMA READ把block数据写入到client的buffer中

2.Persistent StoC FIles

会在节点维护一个全局的file buffer。流程和上述相似

当client插入一条block数据的时候，首先用RDMA WRITE把block数据写到buffer中，当client读取block的时候，由Stoc负责把持久化的block加载到buffer然后调用RDMA WRITE接口来将block数据写到client的memory中。

上图展示了把一个data block fragment写到StoC文件的时候的流程：

1:client发送写请求打开一个新的StoC文件

2:StoC节点在buffer分配一个内存区域，大小等于block大小。然后给该区域分配一个唯一的id，向客户端返回该memory zone的偏移量以及唯一id，客户端就调用RDMA WRITE来写入block数据

3:buffer的block数据刷盘

4:向客户端返回确认

5:用上述相同步骤写metadata block

上述组件之间通过RDMA通信，除此之外还有一个协调者角色：

Coordinator

采用如Zookeeper的中间件；负责维护StoC，LTC的列表；分区的映射信息（那些分区被映射在哪些LTC组件中）

数据查询请求首先需要获取该信息然后定向到相应的LTC中获取数据。

本系统还使用Lease机制来减少对协调组件的开销。具体来说，每个Lease会有一个可以调整的超时时间，协调者会为每个range数据给LTC/StoC分配一个Lease；LTC和StoC组件会从coordinator获取或者接受lease延长的请求，只要LTC和StoC和协调组件的心跳通信保持健康，那么就可以这段时间一直取得对range数据的处理权限，不用每次操作都走一遍协调组件来减轻其读写压力。

如果一个LTC挂机了，那么由协调者来负责将原LTC管理的range的租约分配给别的LTC；那些不能够更新租约的LTC将会停止对外服务。

在后台进行compaction的时候，需要时刻改变StoC存储metadata信息，包括SSTables的Level和分区映射信息；如果有的StoC挂了，其对应的metadata信息就会过期。于是本系统通过版本号来区分过期的和最新的metadata 文件。然后StoC重启的时候会把本机上的metadata版本号发送给协调者，由协调者来进行过期metadata的删除。

弹性

StoC节点的scaling需要涉及到data搬迁

而LTC节点的scaling涉及到in memory memtables和metadata的搬迁

上述都使用RDMA来进行加速，细节看论文

相关工作&总结

存算分离

LTC和StoC节点的解耦合实现弹性，SSTable划分为更小粒度多盘存储来提高多disk的带宽利用率；结合parity和复制机制来做数据高可用，通过power-of-d+RDMA来做data block的hash但本系统的存算分离也不是shared-disk的，扩缩容还是得涉及到数据的搬迁，只不过使用rdma来进行加速

LSM 引擎

本系统和传统耦合的LSM Tree系统相比，使用了更多数量的Memtable来提高多个存储节点的disk资源利用率。通过引入Dranges来解决其带来的写放大问题同时引入并行compaction将写放大开销分摊，提高comapction性能。其次还有引入lookup index和range index来对point/range query进行剪枝。