跟着云服务基础架构以及微服务技能的日益老练，许多大型体系能够分解为依据运用 workload 需求的多个子体系，再通过网络交互组装在一起协同作业。

Nova-LSM，一个将依据LSM-Tree的散布式KV 存储体系分解为运用RDMA进行通讯的组件的作业。这些组件将存储与处理分隔，使处理组件能够共享存储带宽和空间。处理组件将文件块 (SSTable) 涣散到恣意数量的存储组件中，并通过必定机制平衡它们之间的负载，在运行时动态构建规模以并行化紧缩并进步功用。Nova-LSM 具有很好的可伸缩性，在一些场景下功用优于其单机版别（LevelDB 和 RocksDB）几个数量级。

本期DB洞见将由腾讯云数据库专家工程师唐彦，从前沿学术的视点深度解读Nova-LSM，要点介绍Nova-LSM的特性、重要规划及带来的启示。以下为共享实录：

直播回放完整版链接：www.bilibili.com/video/BV1tS…

直播回放完整版+文字版搭配，作用更佳

视频内含课件获取办法哦～

一、LSM-Tree根本概念

1.1 LSM-Tree存储体系

LSM-Tree全称为“Log Structured Merge-Tree”，它是一种依据磁盘存储的数据结构。

在以前，数据库的索引根本上选用B+树办法来作为索引结构，在此状况下，随机写功用常被他人诟病。LSM-Tree则主打将离散的随机写恳求转换成批量的次序写操作。而无论是在机械硬盘还是在固态硬盘，次序的读写功用永久好于随机读写。因而LSM-Tree作为一种高效的KV存储结构，被许多业界的老练体系所运用，比方腾讯云数据库TDSQL新敏态引擎也是依据LSM-Tree进行开发。

LSM-Tree结构有较多优点：写功用强大、空间利用率高、较高的可调参特性、并发控制简单、有齐备的修正计划等。

1.2 LSM-Tree的前史

在数据库更新方面，LSM-Tree与B+树的差异能够理解为：一个是in-place update，一个是out-place update。

依据B+树的更新，咱们称之为in-place update。如下图所示，k1本来的值是v1，随后咱们想在k1写下新值v4，这时需求找到k1，再把v4写进去。因而，在B+树的索引结构里对数据进行更新或许刺进，会引起实时的I/O。在B+树的场景下，写功用会遭到必定影响，但由于B+树能够支持较好的检索功用，因而读功用会较好。

相比之下，在LSM-Tree结构里，假如这时对k1进行v4的更新，咱们不会马上把k1改成v4，而是将它转化成次序写，把它写到内存里，追加在（k3，v3）后边，由于次序写的功用远比随机写高，但这种办法则会献身读功用及导致空间扩展。

下图展现的是1996年LSM-Tree最原始的结构。C0代表的是在内存里的状况，每当有数据写入，它就会逐步往下merge。当第i层满时，它会把底下的叶子精简，从Ci到Ci+1去往下merge。层数越大则标明数据写入越早。每一层开端的版别的头部是B+树，C0是在内存的节点，接受最新的数据更新，C1层到Ck层都存在于磁盘。

1.3 LSM-Tree根本结构

现在干流的LSM-Tree根本架构如图所示。咱们会在内存中保存memtable结构，用于接受最新的数据更新操作，memtable结构里的数据查找则通过跳表skiplist或许B+树完结。当memtable到达必定巨细时，咱们会进行flush操作，中止写入，再把memtable刷到磁盘上，变成静态文件即SSTable。

SSTable L0层与memtable保持一致，从L0层到L1层则会进行归并排序。排序意味着L1层到Lk层都处于有次序的状况，因而在每一层往下沉时，内部的数据会在物理上保持有序。每个数据再往下沉时，会进一步依据不同的key range来转化成一个个互相不堆叠的SSTable。

1.4 LSM-Tree在RocksDB中的完结

下图展现的是依据LSM-Tree数据结构进行二次开发的RocksDB。当遇到写恳求时，RocksDB会先写一个log，即Write-Ahead Log (WAL)日志。当memtable还没有刷到磁盘上时，假如机器产生毛病，Write-Ahead Log (WAL)日志则能够用于毛病恢复。这是十分重要的功用。对TDSQL等金融运用场景数据库而言，可靠性永久排在榜首位，写日志有必要成功，才能把最新的数据刺进到内存（memtable）里。

memtable还有阈值控制机制。在实践的出产环境中，一般将阈值设置为1G，到1G后则会冻结成immutable memtable。当活跃的memtable被冻结成 immutable memtable后，原来的memtable则能够清空内存，从头接受数据的写入。immutable memtable则不会再接受写入，会预备被flush到磁盘上。

跟着越来越多的immutable memtable被flush到L0层，L0层的文件个数会逐步到达一个阈值，这时会触发体系的compaction。由于L0层的SST文件之间呈现的是无序的状况，它们包括的key规模有或许堆叠，这时需求把L0层的文件从磁盘上从头读取并进行归类排序，进而往下生成L1层的文件。从L1层到Ln层（出产环境中一般装备成7层），一切的文件的 key range 现已互不堆叠，且依照 key 的次序进行排放。

当咱们要读取一个比较旧的数据，假如该数据不在内存也不在L0层时，咱们会从L1层到Ln层去读取该SST文件。由于SST文件数量较多，在实践中咱们会选用bloom filter来加快读取。

1.5 LSM-Tree查询

依据LSM-Tree的查询可分为点查与规模查询两大类，对应的执行办法如下：

●点查：从上往下进行查询，先查memtable，再到L0层、L1层。由于上层的数据永久比下层版别新，所以在榜首次产生匹配后就会中止查询。

●规模查询：每一层都会找到一个匹配数据项的规模，再将该规模进行多路归并，归并进程中同一key只会保存最新版别。

1.6 LSM-Tree之空间/读/写扩展

LSM-Tree功用的衡量首要考虑三个要素：空间扩展、读扩展和写扩展。

一是空间扩展。LSM-Tree的一切写操作都是次序追加写，对数据的更新并不会当即反映到数据既有的值里，而是通过分配新的空间来存储新的值，即out-place update。因而冗余的数据或数据的多版别，仍会在LSM-Tree体系里存在必定时间。这种实践的占用空间大于数据自身的现象咱们称之为空间扩展。由于空间有限，为了削减空间扩展，LSM-Tree会从L1往L2、L3、L4不断做compaction，以此来清理过期的数据以及不同数据的旧版别，然后将空间释放出来。

二是读扩展。假定数据自身的巨细为1k，由于存储结构的规划，它所读到的值会触发屡次IO操作，一次IO意味着一条读恳求，这时它所读取到的则是在后端所需求做大的磁盘读的实践量，现已远大于目标数据自身的巨细，然后影响到了读功用。这种现象咱们称之为读扩展。为了减轻读扩展，LSM-Tree选用布隆过滤器来避免读取不包括查询键值的SST文件。

三是写扩展。在每层进行compaction时，咱们会对多个SST文件进行反复读取再进行归并排序，在删掉数据的旧版别后，再写入新的SST文件。从作用上看，每条key在存储体系里或许会被屡次写入，相当于一条key在每层都会写入一次，由此带来的IO功用丢掉即写扩展。

LSM-Tree开端的理念是用空间扩展和读扩展来交换写扩展的下降，然后完结较好的写功用，但也需求做好三者的平衡。以下是两种假定的极点状况。

榜首种极点状况是：假如彻底不做compaction，LSM-Tree根本等同于log文件，当memtable不断刷下来时，由于不做compaction，只做L0层的文件，这时假如要读一条key，读功用会十分差。由于假如在memtable里找不到该条key，就要去扫描一切的SST文件，但与此一起写扩展现象也将不存在。

第二种极点状况是：假如compaction操作做到极致，完结一切数据全局有序，此刻读功用最优。由于只需求读一个文件且该文件处于有序状况，在读取时能够很快找到对应的key。但要到达这种作用，需求做十分多的compaction操作，要不断地把需求删的SST文件读取兼并再来写入，这会导致十分严峻的写扩展。

二、Nova-LSM的简介与特性

2.1 Nova-LSM架构规划一览

Nova-LSM是依据LSM-Tree结构的架构体系，其首要组件包括三部分：

榜首部分是写日志的组件，将WAL写成功后再往LSM-Tree的memtable中查询新的数据。

第二部分是自身处理LSM-Tree写入的线程，其缩写为LTC(LSM-Tree Component)，代表着将该线程单独组件化。

第三部分则是底层的存储，担任把接收到的上层LTC组件下发下来，并供给规范的文件接口。

Nova-LSM是一个存算别离的架构。上面处理LSM-Tree的是核算节点，它们要写磁盘时，需求用flush操作将memtable写到磁盘，compaction时要先从存储节点读取上来，接着进行归并排序并再次写回，再写下去时则由底下的散布式存储节点来进行。

它的架构借用了当下较好的数据库产品理念。在核算节点和存储里，存储节点会依照彼此的功用去区分独立的线程池，每个线程池的线程数能够装备。这相当于在核算节点里将线程的功用分为四种：榜首种线程与client相关，担任收发客户恳求；第二种线程担任RDMA、网络IO的相关操作；第三种线程与compaction相关，会不断扫描当时的SST是否符合compaction及推进compaction的进行；第四种线程与Drange相关，担任不断整理当时Drange的重排、重组织。

该作业的首要亮点之一，是在于把本来LSM-Tree这样的单机体系明确地区分出核算层、存储层，通过必定办法处理了在核算层本来会产生的停写、缓写现象。

2.2 Nova-LSM所处理的核心问题

Nova-LSM所处理的核心问题首要有两个。

榜首个核心问题是：依据LSM-Tree结构的存储体系，例如LevelDB、RocksDB等，都会不可避免地遇到缓写或许停写的问题。比方内存里的memtable，在装备时最多能够写8个，由于写入多，需求悉数flush到磁盘上。与此一起，当时L0层的SST文件十分多，L0层行将开端做compaction。但compaction会涉及到磁盘IO，在还没做完时，就会堵塞内存中的memtable对L0层SST进行flush的进程。当flush无法进行时，就会产生缓写，跟着阈值的推进，在实在写不进时乃至会停写，这种现象体现在客户端便是恳求掉零。

为了处理LSM-Tree结构存储体系中的缓写、停写问题，该文章提出了两个处理办法：

榜首种办法是规划了存算别离的架构体系，详细如上图所示。该架构的重要作用之一，是把处理写入和处理磁盘IO的两大主力模块拆分，核算存储别离，哪个部分慢就为哪个部分添加节点以此来进步该部分的才能，这是比较亮眼的突破。

第二种办法是引入了动态分区，即Drange机制。该机制的意图是为了让事务的写入压力，在LTC即核算层的memtable上进行区间区分，每个range都有自己的memtable，通过区间区分，然后完结多个range之间进行并行compaction。以L0层为例，咱们能够把L0层变成没有互相堆叠的状况，这时咱们就能够对L0层进行并行的compaction，能够加快L0层的文件的消化，然后减轻对memtable flush到磁盘上的进程的影响。

第二个核心问题是：在这种办法下需求区分许多不同的Drange，每个range都会添加必定的memtable数量，memtable数量的添加会影响scan和get的功用。假定有一个主恳求，在原来一切数据都写在一个memtable里的状况下，在读取时，索引只需求面向这个memtable，再依据跳表进行get，假如get到则能够马上返回。现在区分成不同的Drange，memtable数量添加，因而需求查找的memtable以及L0层的SST也会变多。处理办法是：完结了一个索引，能够查询到一个key在memtable或L0 SST中的最新值（若存在）。

2.3 Nova-LSM论文首要作用

这篇文章将本来独立的单节点存储体系做成了一个存算别离、能够恣意扩展的散布式架构。这种存算别离的架构体系，在扩展时对总吞吐量、总的呼应和恳求的才能有明显进步。下图是对该作用的详细展现。

左下角选用了最原始的装备，只要1个存储节点和1个核算节点，核算节点只装备了32M的内存，这也意味着memtable相对较少，在这种状况下它的总吞吐量只要9k，相对较低。然后咱们从纵轴来看，把核算才能向上扩展，通过垂直扩容把内存从32M变成4G，这时总吞吐量现已从9k进步到50k。

但从图中也能够看到，这时功用曲线中心有空隙的当地越来越多，这些便是前面所说到的恳求掉零。核算才能的加强意味着能够进行更多的写入，内存变大意味着memtable的数量变多，L0层的SST文件生成速度也会加快。当L0层的生成文件速度加快后，就会对存储层compaction的才能形成压力，由于它在默认装备下只要1个节点。这时虽然它的峰值现已进步到了5k，但恳求掉零的状况也更多了，即产生了停写。由于L0 SST现已来不及compaction，这时只能等候，相当于核算节点在等存储节点。

为了处理这个问题，咱们需求对存储节点进行扩容，比方将1个存储节点扩到10个。这时能够明显看到总吞吐量从5万进步到了约250万。虽然某些当地恳求也会骤降，稳定性还有待进步，但从全体上看，几乎现已没有恳求掉零现象呈现了。

这也体现了传统单机单节点LSM-Tree存储体系与Nova-LSM之间的差异。在传统单机单节点LSM-Tree存储体系中，假如核算才能十分好可是磁盘才能不行，这时很难在单节点上进行扩展。但在Nova-LSM中，假如发现哪部分才能不行就能够进行扩展，核算才能不行就扩核算节点，存储才能不行则扩存储节点。这也遵从了当时散布式数据库里比较常见的存算别离、核算层和存储层能够独立扩容的理念。

三、Nova-LSM若干重要规划

3.1 LTC和StoCs之间的写数据流程

榜首个比较重要的规划是LTC和StoCs之间的写数据流程。该流程展现的是：当在客户端建议写恳求时，核算节点和存储节点是以怎样的办法将数据写进去的进程。

首要是核算节点的客户端建议一个新的写恳求操作。存储节点在接收到该恳求后，依据RDMA交互，它会在buffer区域分配一个内存区域，并且为这块内存和偏移量（当时哪块内存能够写）分配一个id，告知StoC。客户端接到呼应后就会开端写数据，完结后会告诉存储节点。存储节点接收到信号后，将数据耐久化并且再告知客户端。

上述流程是写一个数据文件即SSTable。写完后，咱们要以相同的流程将元数据文件更新。由于底层是散布式架构，需求知道哪些文件写在哪里以及每个SST的规模、版别号。

3.2 动态区间区分

第二个比较重要的规划是动态区间区分。假定事务的恳求规模为0-1万，当时有10个核算节点，将这10个核算节点的区间区分为10等份，比方榜首个key的空间规模为0-1000。在担任0-1000的核算节点里，它会再进行区分，这一层区分事务无感知。这就叫动态区间区分，简称Drange。其作用首要有以下几点：

首要，每个range都是一棵LSM-Tree，依照数据区间，不同的Drange都有自己的memtables。比方0-1000区间又能够区分为10个Drange，10个Drange之间的memtable相互独立。这样做的优点是这些Drange之间的key互不堆叠，例如0-100、100-200、200-300。

其次，在Dranges下还有一层Tranges。假如发现Drange里的部分range比方890-895存在热门现象，而旁边的range并非热门，则能够用Tranges进行细粒度的复杂重均衡，完结动态均衡负载。

最终，在此基础上，由于Drange的key规模互不相交，当memtable变成immutable，不可再写后，它们需求独登时flush到磁盘上。这时，在L0层的SSTable来自不同的Drange，它们之间的key彻底不相交，咱们就能够进行并行的compaction。

3.3 Compactions

文章还将没有Drange区分和有Drange区分两种状况进行了对比。

在没有Drange区分的状况下，L0的compaction无法很好并行。在这种状况下，假如遇到最坏的状况，L0层的某一个SST有或许覆盖了整个key空间，假定key规模为0-600，L0层的SST文件的规模是0-1000，当产生compaction时，它有必要要跟其他4个SST做归并，这时不但要把L0层的其他SST悉数读取比较一遍，还要把L1层一切的SST都读一遍再做归并排序。这时写扩展会较为严峻，意味着L0层到L1层的compaction会变慢，flush也会变慢，乃至flush不了时，前端就会呈现缓写、停写现象。

有Drange区分后，相当于compaction能够分隔区间，如下方的示意图所示。在0-100区间，L0到L1能够独立去compaction，100-200区间也能够独立去compaction，能够较好地完结并行compaction。而在原生的RocksDB里，只要从L1开端compaction，才能进行并行compaction操作。

假如和谐者发现当时存储层的节点资源十分充足，compaction操作能够由存储层自动建议，不需求核算层去发现当时有哪些能够做compaction，这是这篇文章中说到的另一个想法。

至于考虑下沉的原因，由于文章并未深化打开，个人猜测首要是考虑到在这种架构体系里，存储层比较简单扩展，而核算层较难扩展。由于核算层相当于分库分表，假如扩展则会涉及到必定的路由重散布，需求告诉前端恳求路由的改变。但存储层则十分简单扩展，假如能将这些十分耗时的操作放到存储层，能够极大地削减在核算节点跟存储节点之间数据的开销。存储层做完后，能够直接把更新后的元数据告诉核算层。

3.4 索引查找以及Scan操作

由于区分了许多不同的动态区间，memtable的数量也会添加，意味着查询操作的耗时也会添加。所以要怎么在原来的基础上保护好读功用？这篇文章提出了以下处理思路：

每个LTC保护了一个lookup index。假如这些数据存在于memtable和L0层的SST上，通过lookup index咱们就能够快速查找到想要的数据。当某一个L0层SST被compaction到L1层时，索引上就会移除掉对应的key。

LTC一起还保护了一个规模索引即range index。由于知道每个Drange的规模，所以当一个scan恳求所涉及到的key，都能够在memtable和L0层SST中找到时，该规模索引就能快速呼应scan操作。

3.5 SSTable的散布

最终一个比较重要的规划涉及到存储层。当某个SST文件要写到存储节点时，散布式体系首要要确保负载均衡，要确保数据避免单点毛病不可恢复的场景。

该文章提出依据必定策略，将数据文件即SST打散写入到多个存储节点里。考虑到存储成本，每个SSTable选用纠删码（Erasure Coding）的办法进行编码然后散布式寄存。默认状况下对每个 SSTable 选用 “3+1”的 EC 装备，将一个SSTable切分为3个数据块，依据必定算法，在这3个数据块里去核算出一个校验块，变成了“3+1”的形式。这种办法比传统的多副本能够节约更多空间。假定一个SSTable是3M，这种“3+1”的办法最终所占空间为4M，并且能容忍一个节点的丢掉，与占用6M空间的双副本计划拥有相同的毛病容忍等级。而元数据文件由于体积比较小，所以直接选用多副本存储的办法，比方1个元数据文件能够写3个副本。

四、Nova-LSM功用作用展现

在本篇论文中，Nova- LSM具有较好的功用数据表现。以自身调参测验为例，数据标明，Nova- LSM能够通过调整不同的参数到达较好的扩展作用。文中别离运用Uniform均匀散布和Zipf散布来打散数据，存在热门（比方80%的拜访概率都会集在20%的数据上）的状况下，试验结果数据标明，在读写份额、数据拜访概率不一样的各种场景下，Nova- LSM都能获得较好的功用结果。

下图所示为Nova-LSM在自身调参下几组不同参数的比较：

下图展现了Nova-LSM自身扩展性的作用：

下图所示为Nova-LSM吞吐量扩展性测验：

以上测验是Nova- LSM自身不同参数下的对比。除此之外，该文章还将Nova- LSM与LevelDB以及RocksDB进行功用对比。

在小数据场景下，Nova- LSM的功用表现比RocksDB要更优异，特别在Zipf散布且热门数据存在、读写各占一半的状况下，测验出来的功用数据要比RocksDB高4倍。但跟着数据量的扩展，在某些workload下 Nova-LSM 的优势逐步变得不明显。比方在上图中的（d）状况，一个10节点、2T的数据库，RocksDB将其分为10份，在这种写较多的场景下，Nova- LSM与原生的RocksDB距离不明显。

另外，上图中的蓝色数据项RocksDB-tuned，它是RocksDB进行调优后产生的数据项，赤色数据项则没有通过RocksDB调优，而赤色项却获得了比蓝色项更好的功用数据。

通过较多场景的验证，像Nova-LSM这种依据LSM-Tree结构的存储体系，实践上并不存在某一组参数能够让它在一切不同性质的workload下都获得较好功用。如上图（d）组，即中心100%写、均匀散布的测验组，RocksDB通过调优后比没通过调优、用原始参数的对照组的吞吐量更低。由于Nova-LSM自身需求有十分多的调优参数，因而很难存在一套参数在一切的场景里都为最优。

五、Nova-LSM带来的启示和评论

一般状况下，依据LSM-Tree结构去进行优化的作业都面临以下问题——读扩展、写扩展及空间扩展。

假如彻底不做compaction，LSM-Tree将会退化为Log文件，此刻读功用最差，需求扫描一切SSTable文件，但不存在写扩展。假如通过compaction操作将一切SSTable文件维持为一个sorted run，即始终保持一切kv数据的全局有序，则退化为sorted array，此刻读功用最优，查询时只需读取一个SSTable中的一个数据块，但频频的compaction操作会导致严峻的写扩展。所以咱们不能走极点，需求在两者之间提出新的改善办法，在读扩展、写扩展及空间扩展之间做好平衡。

Nova-LSM便是在这三个要素之间做取舍，它的规划原理之一是将本来单机单节点的体系用散布式组件化的办法，将本来一份代码里边的不同模块拆分出来，然后令每一个模块具有可扩展性，打破原先单机资源的约束。此外，该文章还创新性地提出，将不定期的compaction对磁盘IO形成的短期冲击剥离出去。

与此一起，该篇文章在试验验证及工程实践上仍有许多当地需求完善和优化。

榜首，试验运用的每个KV的默认巨细是1KB。依据原理判别，Drange这种规划在该场景下比较占优势。在详细完结中，当一个memtable包括的unique key 小于必定阈值时，不同的Drange之间会将memtable进行兼并，其意图都是为了削减磁盘的写入。因而运用1KB这种不算小的测验数据，对它而言是占有优势的。而其他原生的RocksDB则需求不断地写磁盘，由于每一条key的体积都不小，1000条可到达1兆，100万条就能到达1G，这时Drange机制所带来的削减磁盘写入的优势就会被扩展了。

第二，Drange和Tranges机制的建立，能够确保一个核算节点在不同的memtable写入之间存在动态均衡。从工业界落地的视点出发，这会涉及到较多的数据一致性确保。但文章并没有进一步论说数据的移动是否会形成没写或许双写。

第三，工程实践上仍存在不少流程细节有待深化琢磨，比方在LTC和StoC的写入流程交互中，文中说到先更新数据文件block再更新元数据文件block的流程，但假如在这两次写入中心产生了毛病，怎么处理？StoC运用erasure code办法确保数据可靠性时，怎么确保n+1个数据块和校验块写入一起成功？毛病时怎么回滚？单个数据块产生丢掉时怎么发现以及从头生成？这些问题都值得咱们进行琢磨。

第四，N个LTC会担任N个区域数据的写入。比较传统的依据中心件的散布式数据库，会存在一个中心件，中心件知道其下的存储节点以及担任写入的节点别离担任哪一部分数据，此刻路由改变的灵活性会存在必定约束。

第五，一切的功用测验中根本只描绘功用的最大值。最大值、最大吞吐量这些目标很重要，它代表着一个体系的才能上限。但在真实的事务场景中，除了才能的最大值，另一个十分重要的考察目标是稳定性。而Nova-LSM依据散布式架构，它一切的读写数据一直在进行网络交互。compaction自身由于磁盘的IO，给总体功用带来了不稳定性，现在又加入了网络之间的开销，网络颤动就愈加频频，功用的颤动也是咱们有必要考虑的要素。

Nova- LSM并非只要理论，它在LevelDB的源码基础上新增了2万多行代码，完结了一套核心的规划，上图所示为其源码地址，感兴趣的同学能够尝试进行二次开发。

关于讲师

唐彦，腾讯云数据库专家工程师、浙江大学博士。研究范畴首要关注散布式存储、大规模数据密集型体系相关的关键技能，曾以榜首作者身份在范畴Top类期刊和会议上宣布多篇论文。博士毕业后来到腾讯从事基础研究与技能工程化作业，现在首要担任散布式数据库 TDSQL 的元数据管理与集群管控调度相关作业。