随着云服务基础架构以及微服务技术的日益成熟，很多大型零碎可能合成为依据利用 workload 需要的多个子系统，再通过网络交互组装在一起协同工作。
Nova-LSM，一个将基于LSM-Tree的分布式KV 存储系统合成为应用RDMA进行通信的组件的工作。这些组件将存储与解决离开，使解决组件可能共享存储带宽和空间。解决组件将文件块 (SSTable) 扩散到任意数量的存储组件中，并通过肯定机制均衡它们之间的负载，在运行时动静构建范畴以并行化压缩并进步性能。Nova-LSM 具备很好的可伸缩性，在一些场景下性能优于其单机版本（LevelDB 和 RocksDB）几个数量级。
本期DB·洞见将由腾讯云数据库专家工程师唐彦，从前沿学术的角度深度解读Nova-LSM，重点介绍Nova-LSM的个性、重要设计及带来的启发。以下为分享实录：
直播回放完整版链接：[https://www.bilibili.com/vide...]()
直播回放完整版+文字版搭配，成果更佳
视频内含课件获取形式哦～
一、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 的元数据管理与集群管控调度相干工作。