DB洞见#2|基于LSM-Tree存储的数据库性能改进原创

啊，各位老师同学，嗯，大家下午好，欢迎来到我们啊DB建啊第二期的技术分享啊，然后我是腾讯语云数据库高级工程师韩硕啊，我本科的博士分别毕业于北京大学，呃，北京云大学和北京大学，呃，在2019年毕业之后呢，就加入了我们腾讯的计费，呃，腾讯计费团队目前主要是负责TT数据库呃，新一代敏引擎的研发。啊，我本人的研究，呃。诶，你好。诶，好。啊。还没有开是吧，好，我是我这个声音可以吗？就是声音大小可以好好好好没事你再你你说开，我们重新再开。嗯嗯。呃，现在可以了，哎，好的啊，各位同学啊，老师同学大家下午好啊，欢迎来到我们DB洞见分享啊这第二期啊，我是腾讯云数据库高级工程师韩硕，我的本科和博士分别毕业于北京云林大学和北京大学，然后在2019年毕业之后呢啊就加入了我们的腾讯TV费团队，目前我主要是负责TD circle数据库新一代每台引擎的研发。

呃，我本人的研究方向包括分布式数据库图、数据库和存储引擎优化等。然后呃，我们今天分享主题是基于lsm的存储存储，呃，基于基于lsm存储的数据库性能改进。然后我会重点介绍近年来学术界对RSM的性能改进工作，并且探讨这些改进措施在工业界数据库产品的一些应用情况和以及未来落地的一些可能性。我的分享大致分为四个部分。首先，呃，首先我会介绍一下lsm的基本结构，然后我会讲一下LSMM中的一个核心的一个一个呃，一个compassion任务的一个优化策略与分析，然后我会介绍一下，呃呃。呃，最近的一些降低写，在降低写放放大这样的一个，呃呃，这样的一个点上的一些优化，然后最后我会讲一些其他的一些优技术优化点。首先来我们来看一下第一部分，首先是背景知识部分，就是RRSM的一个基本结构。

呃，L SM tree的话，它的全称是叫做log structure mer tree，它是一种基于磁磁盘存储的一个数据结构，它的首次提出是在1996年，啊，是有这个Patrick o在信息系统期刊上发表了一篇一篇题名就叫做这个the log structure tree这样的一篇论文，然后呃，RM tree的话，相比于传统的B毕加书来说，它具有更好的写性能。呃，它是将一个离散的随呃随机写请求转换成一些批量的顺序写操作，因此无论是在RAM还是说我们的硬盘上，还有还有这个SSD上，它它的它的读写，它的写都是更好的。然后IM作为一个高效的KY6的存储结构，它也会也已经被广泛的应用，呃到了这个工业界的数据库系统，比如说经典的这个单KB数据库DBDB，以及许多呃被其他许多分布式new作为底层存储引擎，然后在我们的TT米态引擎的存储模块，也是用到了这样的一个RM结构。然后呃，LLSM结构的话，它有很多优点，比如说它的写性能非常强大，然后它的空间利用率非常高，呃，然后它的那个呃，它具有很高的可呃可调参的这样的一个一个特性，并且它的并发访问，它并发控制的话是比较简单的，而且它有完备的一个呃，SH之后的一个恢复方案。

呃RM它本质上是基于out place update的啊，我们把这边我们中文叫一般把它叫做呃不在原地更新，呃这个地方展示了这个in place update，就是说原地更新和auto place update，呃不在原地更新的这样的一个区别，呃in place update的它的数据的更新操作是将呃数据的新址直接覆盖到这个旧址上去。然后它带来的最大一个问题就是随机读写。然后out place update的话，它是将一个新址的顺，呃，将我们的新址顺序的去追加到文件的一个末尾，通常会有带有一个版本号，呃，我们把它称作six number，然后来标记这个区分是新址还是旧址。然后out out out please update的话，它一般都是顺序写的，所以说它的写性能是更好的，但是带来的的缺点就是说它可能会有荣誉的数据，它在读性能上和空间利用率上可能不如这个in place update更好。

嗯，这张图是展现了一个1990年最初的一个LM的结构，这里C0到CK表示了L的不同的层，层数越大的话，它的写入的数据就越早，每一层在最早的时间中，它其实每层是一个必加数，然后C0层也是最新的这个数据它是位于内存的，它接受一个最新的一个数，数据更新，然后C1到CK的话，把它我们把它存到磁盘上。当每一层这个CI满了的时候，就会触发一个合并的操作，它把这个CI中的一部分业节点向它的下一层CI加一层，进行一个合并，然后层和层之间它有一个容呃容量的一个阈值之比，也就是我们把称定义为一个叫做放大力的这样的一个东西，呃，PI。然后最初的1996年的时候，这个lsm税的时间上其实比较复杂的，而且而现在我们现在的RSM税中，其实每层也就都也已经不用了这个必加税的这个结构，然后我们可以看接下来这张图，这是目前主流的一个lsm的一个实现的一个基本的结构。

它分为两部分，就是内存和磁盘，内存中它是维护了一个叫做table的一个呃，一个数据结构，呃通常它的实现上可以是一个加数，也可以是一个呃跳表，然后这个mm table，它是用来接受最新的数据更新操作。呃，他维护他在内部的话，维护了一个这个内部数据像的一个逻辑上的一个有序。然后磁盘部分的话，磁盘部分中中的这个数据的存储其实是物理上也是部分有序的，简单来讲的话就是数据是按照层序进行堆放的，然后层层次越深，越往下数据写入的时间就越早，然后每一层内部我们把我们按照它的是否有序，把它划分成了一个或者多个wrong，一个wrong内部的数据一定有序的。而且这个地方有序，我们通常意义上指的是这个物理上也是有序的。然后一个的话中，数据可以进一步划分成不不重叠的一。然后当这个中的数据写满的时候，就是内存中的数据写满的时候，它会向L0进行落盘操作，然后我们通常把它称之为一个flash操作。

然后接接下来lsm的某一层，如果说也是达到它的一个容量阈值的话，它会向下合并，然后合并的过程中会把同样的K的一些过期版本给它清除，我们通常把它称之为complexion操作。呃，这是rock cb的一个基本结构，然后它是一个基于SM的的存储引擎，呃可以看到相比于刚才介绍的ML的基本结构，它呃大致上主体上是一致的，只播过它的，在内存的中，它除了之外还有一个呃都增加了一个I的部分，然后这个地方的话，它是用于这个flash操作的一个一个写缓存的一个机制，就是说我一个数据先把的话，我是先把它暂存到一个able，然后通过一个后台的异步线，再把慢慢的给它刷落盘，到这个落盘成从磁盘的这样的一个SST文件。它还增加了一个叫WL这样的一个日志，这个日志就是为了恢复的嘛，就是为了SH的时候能够进行一个数据恢复啊，然后每次发生在磁盘中，每次发生一个，它会维护一个SSSST集合的一个version，然后这个version的话，它又有它的一个恢复的一个记录，我们把它叫做一个man manifest。

呃，然后把RSM税支持的查询，我们把它分为两大类，一是点查，一类是范围查询。这简单说一下这些查询是怎么执行的，对点查来讲，它就是从上到下的一个结果，先去查table，如果说然后再一层一层从SSST的LEVEL0LEVEL，一层一层往下探查，只要找到这个数据就立刻返回，因为我返回的一定是最新的数据。这个地方有一个有一个约束，就是说上层的数据一定是要比下层数据的版本是更新的。然后第二类我们把它称之为呃，范围查询，或者叫一个range lookup，就说这个range lookup，相对点上来讲，它是在每一层都要做匹配的，然后在每一每一层都会找到一个匹配的数据项的这样的一个范围，然后再把这些范围进行一个多路归并。

规定的过程中，同一个K的话，我只会保留一个K的它的有效的一个最新的版本。然后对于l SM tree的性能来讲，我们通常来讲我们会有三个，呃主要的一个衡量的概念啊，或者说是三个主要考虑的呃三方面的因素吧，这面是空间放大，读放大和写放大，这里呃首先我们说一下空间放大的含义，呃空间首先我们知道l SM tree它所有的写操作都是一个数据追加写，所以说对于数数据的更新操作，它不会把这个新的数据给覆盖到旧址上，而是说我们通过创建一个新的空间来存储，来存储性质就是我们刚才说的auto place update，然后这的话就会产生一个相对于荣誉的一个数据，就会产生一个，呃这样的话就职不会被马上删除，也是就职也是占有空间的，这种实际就是实际会导致一种占用空间的，就呃实际数据的的占用的空间的的大小要比本要比数据本有效数据本身的大小还要大，这样的一个现象，我们把它称为空间放大，然后lsm通过这个comp操作来清理过的数据，从而从而来降低这个空间的一个放大这样的一个这样的样的过。

第二类，呃，概念叫做不放大。就是我们像B税，呃，不不只是L层税法，比如说B加数读这些其他或者一些其他的一些外索引，外层的索引结构的话，你在读操的时候，你要从上到下一层层的去读取索引节点，这样的话就会造成你想读一条数据的时候，可能会触发多次IO操作，也就是说你一次读操作所读到的数据量实际上是要大于你真正真正的读数据这个这目标数据的本身的个大小的，然后会导致这个毒性呢，会比较呃从而影响到这个毒，毒性呢，我们把它从这样的一个现象，我们通常把它称之为毒放大。第三类，我们把它做做写放大。就是说我们对于l SM tree而言的话，呃，我们后台每进行这样的一个comp操作，它会反复的将多个SST文件进行读取，然后又合并重新写入磁盘，这样的话就会导致我们实际在写入一条KB1条数据之后，它在之后的卡操作中还会对这条数据反反复的进行IO进行写入磁盘，从而从而就会影响这个IO的整体的性能。

这样带来的一个损失，我们把它称之为写放大。然后LM l SM tree，它最初的设计理念呢，也是说想用这个空间放大来和读放大来换取一个写放大降低，从而打致到一个极致的血性的。但其实这个地方也会呃，要做三方面的一个权衡。呃，这里有一篇EDBT2016的一篇论文，其实首先提出一个叫做这个rum的一个猜想，这个rum的话是三个，呃，三个方面的缩写，R的话就是这个read，就是这个读性能，呃，U的话是update，就是我们刚才说的这个写性能，然后M的话就是memory usage，就是我们这样的一个空间，呃，空间利用率。然后他指出了这三呃，这三个呃。这三者之间的话，它是有一个，呃，是有一个权衡关系的，就是我们不可能说找到一种非常理想的方案，将这三个三个方面性能都达到最优，只是说我在这样两个方面最优的时候，第三个第三个性能可能会变差。

因此我们在这个地方，也就是说通过这篇论文的这个理论进行指导的话，就说我们必须要在这三者之前做好一个有效的一个权衡。比如说我们刚才说的这个compassion的一个操作，它的目的本身是为了保证这个数据的局部有序和清理掉一些过去的数据。那发生一次卡发生之后的话，那一个round内部的多个ST文件它是有序的，从而就会降低读放大，因为对于在查询一个在查询的时候，在一个状内部，因为它是有序的，所以说他最多只会读取一次这个数据块。但是如果说我们在SRSM处中，我完全就扔掉这个compion动作，我完全不做compasion，那这个RM因为它一直顺序写的话，我们就可以认为它是一个log文件，这个时候它写性是最好的，因为你什么都不需要做，只需要顺序的去写log就可以了。但是它的读性能是最差的，因为你没有任何的索引，没有任何的有序性，你每次想读到一个固定的一个数据像的时候，你需要扫描所有的这个SSSST文件。也就是说这个comp操作的话，它其实想是想将部分的SST文件维护成一个sal wrong就维护成一个局部有序的这样的一个一个结构，但是如果说是我这comp wrong这这个的这个动作，如果说我们给它做到极致的话，就是我可以把它做到所有的K数据一达到一个全部全局的一个有序，那我可以把它理解成这样的话，就变成了一个啊排好序的一个一个数组，就是它是一个全局有序了，这样的话，读的话，我只需要通过索引和二分就就很快的找到这个你要读的这个键值的位置，那你查的时候只需要以次操作就可以了，但是你。

带来的代价，就说你会频繁的进行卡来维护这样的一个群游戏，从而会造成造成一个严比较严重的一个小放大，就说它的血性呢会变差。然后也就说我们从这个图下面这张图中其实看到两个方向，就说如果说我完全不做comp。那其实就退化成一个log，然后我们把这个方向的compassion的风格，我们把它做做T，还有一种就是我更频繁的去做compasion，然后尽可能维护，让这个有效有序性更强一些，那强到极端就是说全局有序，那它就是一个排好的数组，那我呃，在这个方向上去做一个comp的这样的一个策略的话，我们把它叫做一个levelly，呃，我们之后，呃，接下来我们会看一下这两种compasion的策略。

首先是这个leveling compfesion leveling compfesion的话，它让这个LM的每一层只有只允许有一个sal wrong。也而1STEM我们知道它的内部是保持这个数呃数据呃STEM内部的数据是保存一个物理保保持一个物理有序的，那在一个这个具体实现上的话，我们以个CB为例，它一个状的话，其实就是一个多个K不重KV不重叠的，然后一个一些呃一个一个有序的这样的ST。ST文件来组成的。然后每当DL层的这个呃容量满的时候，在DL层我们会选取一部分这个SST文件，跟下面的这一层的L加一层的这个一部分有重叠的S文件进行一个合并，然后这个合并操作就是我们刚才说的。然后a level compassion的最大的限制就是说它要求每一层只能有一个wrong，就是每一层它是完全有序的。

而刚才说的另一种风格叫ting ting的话，它其实是这样的，它是让每一层可能它允许每一层有多个sort wrong，然后sort wrong内部当然还是有序的，但是相当于每一层它是就不是一个完全有序的了。然后这个时候当DL层满的时候，我会把L层的选取，选取T个wrong，一起把它向L加一层的某一个run进行合并，这样的这样一来的话就是我们相当于方宽这个限制，我们要求哦，我们允许每一层都可以有多个。呃，因此在实现上的话，一呃在每一层可能会有在位于不同的S文件之间可能就会有数据范围的一个重叠，那这样的话，它发生的compion的频率就会更低，呃，写性呢会更强一些，但是它的因为它的不是那么有序了，所以它的读它的读操作代价会更高一些。接下来会有一个论文上的一个理论分析。呃，还是刚才对，刚才一个总结，就是两种风格或者两种comp策略，它是各有优劣的，然后的话是空间放大，因为的compion频率低，然后过期数据版本没有被清除，所以空间利用率带来好处就是空间利用率也低，但是它它因为呃只维护一个局部有序，它有序性比较差，所以它查询代价就比较高。

然后level，呃，Leveling的话，它就是更频繁做compaion，呃，数据更趋向于这样的一个有序性，当然极端情况它就是一个全球有序，它的极端就是一个thought，这个时候它的查询性能和风险利用率，呃，就是就是比较好的。然后在C目的2018的一篇论文，就会对这两种卡策略进行一个详尽的理论分析，然后这是一个分析的一个理论结果，可以看到这个分析的结果跟刚才讲的其实是一致的，这个地方有几个参数，重要参数一个是LL的话，表示这个LM税的一个总层数，P的话，代表每一层层层之间的一个放大率，就是说我这这一层，呃，下一层和这一层是是一个它的容量是一个梯倍的关系。然后B的话是一个block大小，因为我们IO的话都是以block为进本单位的，那我们一次O的话，我们认为可以，我们认为一次IO读一个block，然后这个block里面是有B调数据项，我平均有B调数据项的。

然后这个地方的N就是总的一个数据项的总数，总的数据项的一个一个数量，这个地方数据项，注意我们要包含到一个过期版本就没有被con掉的这样的的数据，然后M啊，这个M的话是指一个呃，M是一个呃是后面我会讲到一个lom filter，就是为了增强毒性的话，又我们会给它，通常我们会建立一个lo filter这样的一个结构，然后我们给这个lo filter分布分配的一个内存大小，我们把它标记为M。然后这个小S，小S是指范围查询返回到这个KV的数量啊，这地方注意到是一个有效KV条数，也就说是规定之后，就是我们去掉这个过去版本数据之后的一个KV的数量。然后这个地方我会简单的介绍一下那个他们的两种两种策略的它的一个它的一个理论分析结果，首先我们看这个updates就是一个写入的这样的一个操作复杂度，那对于一条K来讲，我们知道写一次磁盘代价，因为我们意思是一次落盘是落B条，落一个block嘛，它是B条数据意思，意思只写一条的话，我们认为它代价一个基本代价是B分之一。

那么对于刚才我们说这个leveling这种风格的话，因为第层像第呃像下面的一层应该呃第二加一层，我们可能最多合并是批次的话啊，这地方PPT应该写错了，因为下面的D加一层啊，它会最多会合并七层。因此而呃而在第J层合并到第层的时候，我们可以被后被后面的这个被后面的呃那个数据项可能会反复的进行T减机次的这样的一个合并，然后最初我们给他进行一个求和操作，我们发现每每一条KV在第在第二层，就是在任何一层的平均被平均comp就被平均L的读写次数是一个二分次，所以我们是O。然后一个数据的话，最坏情况它是从map table一直往下合并，合并到数据的最后一层就是DL层，那得到我们会得到一个平均的一个落盘的一个，呃，一个值就是T乘以L，然后除以B的这样的一个，这样的一个，呃，复杂这样的一个复杂度。

呃，这是刚才的一个例子，就是说我们每合并一次的话，Di层的重量都不会超过1/7，然后第层从空到满的话，它可能最多向下合并论梯次。所以说每一条KV的话，它在每一层都平均下来，它相当于被合并了二分之T次。而对于这个ting compassion来而言的话。因为每条K在。第层的时候，它只会被合并一次，因此这个地方它会它的写性，它的更新性能就会要比leveling它更有，它是一个L除以B的这样的一个平行写盘的一个次数。可以看到这张图，我Di减一层向D层合并的时候，只会会在Di层直接产生一个新的wrong。也就是说每层这样情况下，每层KV呃呃通就是平均意义上每层KV在每一层，每一条KV在每层只会被合并一次。

然后接下来我们看一下这个空间放大率，空间放大率这地方我们给它一个定义，就是说我们认为是一个过期版本的KV数和真实有效的和有效的就是最新的这个KV数的一个占的一个比例，一个比例，那对于我们这个l leveling comp来讲的话，它的最坏情况就说填L减一层的每每一条KV，每条数据在最后一层，就说DL层都有一条它的没有被清除的一个过期的版本。然后我们我们刚才又定义说每一层容量之比就是那个放大率是T，它是一个等比数列，那我们可以用这个等比数列求和公式去推一下，然后会发现它的呃，L减一层的的这个数据项的。啊，L减一层的这个数据的总量只呃最它的数据的大小只占数据总量T分之一，然后最后一层的话，最后一层它其实占了一个最大的比例，它是T分之T减一，因此这个地方它的空间我们只考虑这个过去数据与真实数据的这样比例之比的话，它的空间放大率其实不高的，是T分之一。

然后T2来讲的话，因为我们允许最后一层或者说每一层嘛，它都是有最多有七个wrong，然后每个每个最坏情况下，每个的内部都可以保存一个KV的过期的版本，那这样的话，在最后一层可能会最多会出现T一个不同的。过期的白板一次空压放大率是一个OT这样的一个复杂。然后从这张图中可以看到，其实leveling它的空间放大率利用率是是是比较高的，因为它的呃空间放大的系数是一个T分之一，然后这ting的话，你可以最坏情况下后面的每一层，最后最后面每一层的每一个都是一个荣誉的数据，然后它的发率是比较差的。空间化率是比较高的，空间利用率是比较差的。然后接下来是对于查询，首先我们看一下点查询，点查询的话，我们这地方，我们的这地方分析的一个技术，就是我们都使用一个不M过滤器来进行过滤了，然后把它分成两类，一类叫做there，就是说这个穿透，就是说这个查询数据不存在。

然后我们呃知道就是这个不呃布隆过滤去它发生假阳性，假阳性它有概率就是这个呃呃E的负N分之M次方，OK，我们我们假设知道了这样的一个每一次假的这样概率，那么知道如果说不非的判定，判定结果是次假象假性的话，那我们就需要去真的去探查一下这个数据的这个数据块，那就要做磁盘。那对于我们刚才说的T来讲的话。诶，稍等，这个levelly还没有讲稍等啊，我们看一下看一下前项PPT，不好意思，这个对于levelly来讲的话，因为我们每层是有只有一个s wrong，它每一层完全有序，因此在每一层我们只需要查用一次这个补充过滤器就可以了，然后我们拿这个二项分布期望公式来推一下它的期望读盘次数，就是这个，因为它有L层，就L乘以这个E的呃，E的负N分之M次方。然后tea的话，它因为呃每层都有最多有T个forty wrong，然后它最多可能查询t from filter，因为它在刚才基础，在刚才那个结果基础上，我们再要给它乘以一个T的系数，所以说我们看到这个T，呃T的它的检查在有不容过滤器的基础上，其实它的查运查用性能是要比level更差的。

那如果说产验数据存在的话，我们知道，我们知道这个发生假象性的概率，它这个O的呃，E的负N分之M次方，它是一个非常小的一个数，它是原小于一的，所以说所以说大部分情况下，它其实只需要不管是level还T，它其实需要读一次磁盘，所以说我们这边它的其实它都是一个OE的一个。那接下来是一个范围查询，范围查询的话，这篇论文中又把它分成了短范围查询和长范围查询。首先我们看一下短范围查询，短范围查询的话，它是指这个啊，查询出来的这个数据，数据的规模，呃，返回的这个block的数量的大小不超过最大层数的这样的一个范围的一个两倍，这样的一个就是它有一个阈值，当这个返回的这个block返回的数据这个block数没有超过最大层数的这个大小的两倍的时候，我们认为它是个短范围查询，如果返回数量数量比较多，超过了这个最大层数的这个数据量两倍的话，我们认为是一个长范围查询，然后根据这个统，我们通过这个呃统计呃统计呃统计的这样的分布公式的话，我们会发现对短范围查询而言，它在短发短范围产品在归并之前的各个数据版本，其实它是趋趋近于趋向于呃于分布在在RRM的各个层的in level。它的。

查询的这样的一个。呃，复杂这样的一个复杂度都是，呃，是分别是OL和一个T乘L这样的一个这样的一个代价，那如果是长长长方的查询的话，我们会发现对于这个统计的这个公式，我们发现它的大部分的数据其实都是来自于这个RSMC的最后那一层。因此这个这两种它的代价分别是，呃，就是这个返回这个block数的大小，然后和这个大小再乘以一个T的这样的一个。这样的一个一一个复杂性，然后总的来讲就是说我们level，我们会发现levelly比ting的话，它都是少了一个，少了一个代价，少了一个，呃，少了一个L。就说，呃，实际上lively比T的毒性能是更好的。

啊，这个地方是关于刚才短发生查询，刚发生查询的一个概率分分布的一个计算。然后这篇论文的话，其实他讲了一些，呃，讲了他给出了一些理论的一些分析，但其实总的来讲的话，我们可以把它总结出一些，呃，一些结论就是这两种啊，Compasion策略的一些结论，呃，首先这个ting的话，它是写放大低，然后就是写性能更优，它compassion放的频率低，但是它的缺陷就是说它空间空间放大率高，而且它查询效率比较低。也就是说ting这种compassion策略，它是更利更有利于这个update更频繁的这样的一个负载的。那对于levelly compassion来讲，它的写放大会比较高，它发生compassion的频率是更加频繁的，但是它的好处就是空间放大率低，它的产生效率也比较高。这是第一条结论。我。然后第二个。

第二个结论就是说，尽管这个T和level的空间放大它是空间大率是不同的，但是我们知道这个导致空间放大率的最后最主要原因，其实都是就是最最后面那一层，就最底层的国际版本的数据。也就是说越往下的层，它做一次compassion l代价是越高的，但是它发生频率相对来讲它也是也是更低的啊，总体而言就是说不能层直接做compassion的期望代价，它它的这样的期望代价它是一致的，就是说虽然下面的层它compassion一次代价很高，但它频率是更低的。然后对于各种查询而言呀，检查呀，查分查询，还有包括空间发率等等这些它的性能瓶颈，其实刚才看到了，其实它都是在这个RM税的最下面的一层。而更新操作的话，它是更加均匀的分布在每一层的，因此这个地方有一个得出来一个结论，就是说我们减少非最后一层compion的频率，可以有效降低更新操作的一个代价，然后它在这个更新降低更新操作代价的同时，它会对点查空间放大，长范围查询的性能是比较小的，然后接下来这篇论文呢，会有一个改进的一个comp的混合comp策略，其实就是利用，其实就是利用这特性来进行一个整体的一个性能优化。比如说接下来我会讲一下呃，就是一些相关的工作，就是关于呃降低空间，降低写放大的一些相关的一些工作。

呃，还是刚才那篇分析的论文，这篇论文的话，它给它起的名字叫呃，Do给这样的一个名字，然后他提出了一种混合compion策略，就是他把这个leveling和tellinging给它结合起来了，把它叫做刚开始把它叫做一个lazy leveling，那这个lazy leveling的话，其实它其实策略是非常简单的，它其实就是说在最后一层用leveling策略，其他层都用ting策略。也就说只有最后一层是有序，完全有序，它是一个唯一的wrong，其他层的话，它它是一个局部有序，就是它可以维护多个。然后这个是它优化后，就是采取这个呃lazy levelly就是混合comp策略之后汇总的一个它的性能的一个表，然后最后一行这个lazy levelly就是它的它的一些代价，然后标绿的部分，就是说它是表现比较好的，然后标红的就是它表现不差的，然后黄颜色是代表居中，那我们在这张表中我们看可以它呃可以看到它的lazy leveling，它的更新操作就updates，它其实呃是优于leveling的，但是它要比T要差一点。

呃，但是它是也是趋近于接下接接近于这个T的，这是因为它的前L减第一层维护这个ting策略，它看做compion的频率会更低，它写放大是相对来说比较低的，然后接下来我们会发现这个呃，Lazy leveling的策略，它的空间放大率。是最优的，它基于level，然后远好于T，因为它相当于结合了两种策略的优势，然后对于查询来讲，对于检查。检查的话，论文中它其实分析了两种，就是查询呃，就是there result和no result这两种情况，然后它基于呃，然后它这个bloom filter的话，它可接下来还可以做一些优化，然后它会达到这个level的策略。呃，后面我会讲到就不能过滤器，后面有一篇论文叫monkey，会给它进行一个呃，对不能过滤器的这个呃，设置设置不能过滤器大这个B的大小的一个这样的一个这样的一个一个优化这样的优化策略，那么结合了这篇论文的一个这样对不能filter就不容过滤器的优化这样的一个优化策略相结合之后，我可以达到这个lazy levelly跟这个呃呃。

Level跟leveling达到一个，呃，就是几几乎是一致的这样的一个点查的性能。那对于长范围查询的话，这个lazy level它可以做到与level一致的性能，而短范围查询的话，就退化到了更这样的一个水平。因此这个这篇论文其实它有一一个总结，就是说我们不可能使用一种单一的compaion策略，能够在上面所有操作中达到一个性能最优的这样的一个影响状况，因此这个LA a lazy level这样的一个混合策略，它本质上是把ting和leveling的两种策略的做一个折中和调优。然后再更加侧重于侧重于更新操作点查长范围查询的，这样的无lo上面可能性能比较好。

那。那如果说我们单纯使用level的话，它可能就会，嗯。比较适用于这种查询位置的和load，而如果说我是呃更新更新操作位置和load的话，可能用T相对来说应该是比较好的。然后这篇论文的话，它其实建立了一个代价模型。呃，然后把这个level lazy level做了一个推广，把它称为一个flu，然后就说我现在可以。我给它加两个参数，一个叫Z，一个叫K，形面个Z的意思说我最后一层，我也不只是说让它就是唯一的一个wrong了，我可以允许做它最多有Z个再wrong，然后其他层的话，呃，我还是允许它有多个s wrong，然后把这个这个给它加一个限制，限制参数叫做K，就是我每层最多限制它有K个wrong，然后当每个so run的尺寸达到K分之七的时候，就会向下做一层。啊，这样的话就是相当于他把把这个laz level做了一个泛化推广了，然后他这就通过不同的这个workload可以来调节这个参数Z和K，然后这个是把这个Z和K添加进去的这个loid的LM tree的一个它的一个一个代价的一个理论分析的一个结果。

然后这个地方我个人的感觉就是说，呃，它的，那那我们接下来一个问题就是我们怎么去选，根据我去选取这个自由的和K，然后这篇论文的话，它是采取了一个就是搜索，就是类似于great search，就是这种。这种这样的一个搜索，去找到一个针对于某个后漏的最小的一个，就是让这个呃总的代价模型最小的这样的一个参数K和Z，我感觉这个其实呃就写论文可以这么写，但是真正实现就是我们的工程实践上，可能说我事先我不知道乌克的什么样的，或者说我对乌lo的已知的呃是比较有限的，那这时候我我去空呃空去那个优化这K和Z其实很难的，所以说。呃，而且这样的这样总体的话，它的那个模型也是比较复杂的，就是感觉它的时间性其实不是特别的好。而我们看L，呃在ROCB赛具体实践中，其实我的理解是它也是某种意义上也是采取了这样的一个混合comp一个策略，呃，最简单的就是说你可以认为L0层，因为L0层我们在比如L0层sat之间是K，呃，K是可以允许互相重叠的，那这样的话相当于我们认为在L0层它其实多个S，它其实是个T的一个策略，那为什么L0做T呢？就是因为它这个落盘的flash的性能更好。

啊，然后再下LL层的话，其实就是个就是够及时过然让这个空间的利用率会更高一些。然后在实践上，呃，其实刚才有讲过了，就是rock cb还是把每个so wrong，它是存存，呃把它给切割成了多个这样的SST文件，每个SST文件它有个大小的阈值，比如说我们设置他们的预值可能是64兆，我们超过64兆就会新开一个ST，就继续写，但是一个S内部的ST文件它都是有序的。这样的话，把这每个run分割成多个固定大小S table的话，它有它有它有它有一些好处。

那一个最显而易见的好处就是说我每次发生compfesion的时候，我只需要选取呃一个或者少量的s table与下层的呃有KV重叠的这样的一个s table进行一个合并，这样的话，我合并的这个是就是每次compa我我我所涉及到这个合并的数据量，有效数据量，其实它是它是比较，它是能，它是有一个可控的范围的，它跟这个SST的固定大小这个阈值是有关的。然后为了进一步的将你写放大的话，呃，近年来还有一些论文，比如说这个sosp，呃，2017有一篇论文，它的给他提起的名字叫做peb DB，然后它其实提出了一种compassion guard的概念，它的论文的目标是说我进我进一步的就在已有这词类上，我进一步去降低写放大，这样的话，它是把每一层给它这compsion guard的概念什么呢？就说每一层我给它分割成多个分片，然后分片之间的这个分隔的这个我们把它它叫做一个compsion guard，就是说我一次comp操作，我不会跨越，跨越这样的一个分界线，然后在每个分界线内部的话，我们的ST之间允许是有是允许K重叠的，就是说内部的我可以认为每个呃，每个GA之间，也就说每个。

三片内部的，它其实就是一个ting competition，因为它是其实是有多个sort wrong。呃，这样的话它有什么什么好处的话，它最大一个好处就是说，它这样的话，保证数据项从第层向L加一层进行compassion的时候，它保证了它的写入只会只会有一次。然后这个地方，因为它把这个原始的，呃，原生的这个SM是给它进行了一个fragment，就是做了一个分割，然后它把它称作称作一个LSLSFLSM这样的一个结构，但是这地方坏处的话，其实也比较容易理解，就是说它坏处是毒性的变差了，因为你在你找到了对应的这个分片之后，你在分片内部的，如果它它有多个SST，那你是不知道这个数据它真正的是在存存在于哪个ST的，这时候可能每个SST都需要借助借助于它的不同过滤区来做一个探查。

也就是说，即使用我们用不用过滤器，它那个发生假假阳性的，就发生假阳性的期望次数也会增加。那我们在实践中过程中的话，我们其实会发现比较就是较新版本的Rose DB的话，它其实提供这样一个叫SST这样一个类。这个类的话，我们通过这个类的话，其实我们可以在实际实现上，就是在代码实现上，我们可以是可以保证分分片，就是就是每一层还是做这样的一个分割的这样一个操作，就是它还是会划分成了多个数据分片，但是跟刚才的这个DB，就是这个FLSM的一个最大的区别，就是说在分片内部我们。仍然让SSD不重叠，就是分辨内容仍然是一个呃，是一个leveling compassion这样的一个策略，这样的话它的好处就读性能不变，但它写写性能其实没有没有变得更好，但是它有另外两个收益，一个就是说我们现在很多的那个new circle它都是分布式的，然后分布式的话，它不像Rose DB，它Rose cb它只是一个单机的存储引擎，那你在一个分布式的呃这样的一个new s引擎上面，它最大的一个场景就是说我可以弹性扩容，那这个弹性扩容的话，就涉及到这个迁移和这个和和迁移之后的这个数据的一个物理删除。

啊，比如说这个地方，拿我们这个TTSO狗新品太引擎价格为例的话，比如说。我们这个新敏态引擎的话，就是说它一个非常重要特性，就是刚才讲的这个扩容，弹性扩容，然后它的每一简单说一下它，诶，它的每一层存储节点，我们把它称之为一个t store，那一个t store的一个它的真实的数据存储，其实就是维护了一个RSM的这样的结构，它的存储，呃每把它存储KV数据，然后我们把这些KV按照区间给它划分成不同的region，那当扩容的时候，我会增加若干个提存节点，然后把原来节点上的一部分region给它搬迁过去，那这个region搬迁的话，要设及到region数据的搬迁，那如果说我们用刚才的这样的一个分割策略，我把RM trade的每一层基于这个region的边界给它进行一个分割之后，那对于region数据迁移来讲，那性能上会有个提升，就是说我们可以把这个region从这个SST中，就是从一些相对完整的SS。

的的就数据从相对完整的SS文件中给它，给它捞取出来，然后给它，并且把它插入到新的这个新增的这个成节点上，那这样的话，这个迁移的代价还是有这个数据删除，因为你那个搬迁完之后，在旧的T上这部分数据因为已经被搬迁走了，我要把这数据给它进行一个物理删除，那这个整个过程的话，它是有一个性能上的提升的，因为你在你的sat都是根据编辑来进行分割的，那你可以相对完整的把这一把这个region内部的数据给它搬走，或者给它删掉。呃，最后一部分的话，会讲一下那个其他的一些优化点，就是说我们刚才重点讲了这个写放大，降低写放大，我们当然我们知道SM tree的本质来讲，它就是为了降低写方法，但是。除此之外的话，除此我除了我们要达到一个比较好奇性能以外的话，其实我们接下来的这个其他优化点，主要会讲一下读性能，空间利用率，它是怎么来进行优化的，而且我们也知道这两种，这两个也是非常重要的一个性能优化的考虑因素。

本来读放大讲读放大的话，绕不开的一个一个最重要的一个一个结构，叫做就布隆过滤器了嘛，就是降低读放大的一个最重要措施，就是煤层给它搞一个布隆过滤器，然后通过布隆过滤器来做一个过滤，然后来减小这个无效的读磁盘block这样的一个次数。那呃，还是刚才那个结论表嘛，就是检查的话，如果使用不溶过滤器过滤，那当属据查性不存在，就毒发生毒穿透的时候，呃发生假阳假假阳性的话，它是一个E的，呃E的负N分之M次方这样的一个概率。那我们知道只要发生一次假象性，那我就要真的去读一下这个数据，数据块就要做一次读磁盘的操作。那对于levelly来讲，它每一层只有一个负数，那它产一次不分filter，呃，概率就是E的负N分之M次方，那根据这个切换公式，我给它推导出，呃。对level这种comp levelly compaion这样的一个策略的话，它的期望读盘次数就是L乘以E的负N分之M次方。呃。

如果T2的话，我就是一个T乘以L的一个一次分N分之M次方，这是原始的，如果说我们每一层都给它建，建立一个不同过滤器，然后不同过滤器的，呃，那个它是一个固是一个固定的这样的一个be词的话。那在smo的2017的话，有一篇叫做monkey这样一篇论文，它就是优化了这样的一个布过滤器，就是说我给这个LM trade的不同的层设置不同不同的不同过滤器的这个beats。然后这样的话就可以有效的减小一个L的开销，然后从而达到一个优化这个穿透的这样的一个希望次数。呃，这篇论文呃没有展开讲，它最后分那个结论，就是说我第层我给它设置一个DA加B乘以L减I的这样的一个B子，然后这样的话，最后一层，因为最后一层数据量最大，其实它就是约约约等于最后一层只对每个因数来讲，它其实只用了一个bit来来来做一个这样的一个呃。多来把它哈哈希到这样的一个种过滤器上，那这样的话我会优化掉一个这个L的一个系数，就是像你刚才这样的一个呃，L乘以一的负N分负N分之M次方和这个T乘L乘以一的负N分之M次方，优化完之后，然后我们会发现两个收益，一个收益就像这种，像这样这样表上我们这个减减小了一个L这样的一个系数，这样说就是说它的这个b filter，它因为是要在内层中持有的，那这个内存整体的因为每一层呃，在这个monkey中的每一层的bes是不一样的，大价是不一样的，所以说总体上是降低了这个不用过滤区的内存开销。

就是说，呃。在这进行这样的一优化过程中，它的点查，点查性能和整体的filter的这样的一个空间利用率都是有一个提升的。啊，然后我们知道，我们还知道这个最近呃呃最近的话有一个布呃布公呃布谷鸟过滤器，然后它的话是对于这个布隆过滤器的一个有效的替代。然后也是达到一个更好的过滤的效果，然后呃，达到了一个更好的一个读性能。啊，然后这边有一篇文文章叫做超，然后这个应该是发表了今年的这个就C20121的这样的一篇文章，其实它就是用这样的一个布，呃布谷鸟过滤器给它代替了原来这个布隆过滤器，然后它的我们知道这个布隆过滤器是刚才讲了嘛，它是每一层SM的每一层，或者甚至说每个ST文件，它都会维护一个布隆filter，这样的话，你对于你一个查询来讲，它还是要从mm table，然后在L01到L1层一层去线下探查，只是说每次探查的时候，它先过滤，先走一遍那个相应的不能过滤器，那在这个超这个这样片论的话，它首先它做了一个替代，就是说我不要每层都去维护一个不能过滤器了，我维护一个全局的一个。

全局的一个这这样的一个一个布谷鸟过滤器，也就说如果说我们先查这个全局的这个布谷鸟过滤器，如果说告诉你不存在那个数据就真的。数据就真的不存在了，如果说它存在的话，但是它可能会发生假阳性，那这样的话我们就去查，去查具体的数据文件，那这样的话我们也在这个超这篇论文中，我们会发现我不用在每一层一一层一层向下去查了，因为我这个全集的这个布谷鸟过滤器里面，我记录了level ID，就是说我如果说有一个match，在这个布谷鸟过滤器中有一个match，那这个时候我会。

继续向下啊，我就不用继续向下去查了，我就直接就可以找到它对应的level ID，然后找到对应的层，找到对应wrong去给它进行一个读它的磁盘，然后看一下数据是否真的是存在的。也就说是在这样的一个不公过语题中，它其实不记得两部分，一个部分就是这个K，这一个哈SH，其实就是它的一个has，呃，一个一个has map，或者说我们把它称作一个呃，Fingerprint，就是说一个一个一个签名吧，然后再加上它的位置，一个位置的ID，我把它称之为level ID。然后布公鸟过滤器的话，简单来讲的话，它说它的那个它的一个呃，工作原理就是说它其实维护了两个桶，然后这两个桶的桶的位置，对于每一个产询，对于每个K来讲，我们都会通过两次哈希来算去算，呃来算出来它所。这个K所所它所要插入的这个具体的位置，我们把它这呃所对应的两个桶，我们把它称为B1和B2，然后我们发现B1的话，我们直接拿K来进行擦洗，然后B2的话，我们就不需要再用K的原始值了，我们就可以拿这K刚才算上的它的一个fingerprint，就拿它的一个签名或指纹，然后来再做一次做哈希，这样的话，每个K的话，每个K它就会有两个K放的位置，比如说上面这张图啊，右上角这张图，比如说我们现在要插入一个it X，那么H1的话，算出来它的位置是二，就是B1等于二，然后算出来这个。

然后第二个哈希值的话，后来它的位置是六。那根据这个，因为它有两个位置嘛，首先我们要把它往第一个位置上去放，如果第一位置能放下的话，我们就放下，果第一位置被别人占了，这时候再看这个它的第二个位置就是B2，如果说B2没有被占，OK，那你就直接放下，如果说B2也被占了，那这个时候有个叫做啊，Re relocate的一个过程，就是我。第二个位置如果也被占，那我这个新插入的值，我还是要把它放到第二个位置，只是说原来它要踢踢掉，让这个就是占据第二个位置当中，原来这个值，比如说A吧，这个这个AA这个元素，就是对于这个六六下边六的这个A这个位置它要会被踢走，那这个A去踢到哪儿就踢到它的。

呃，它的两个8K中的另一个8K的。然后如果说另一个buck中呢，他也被占了，那被占的元素也会继续被踢走，直到踢到。踢到所有的所有的那个元素都有一个空，空白，新的空白的位置放下之后，这个T的过程就结束了，比如说我们A下A，我们把我们把at的时候，A发现它的位置被C占了，那C就会C选择C的另一个bucket，然后它是一，然后发现一没有。这地方一是没有，呃是没有被占用的，就是是可以放到我们俩，就相当于最后把C给踢到了A的位置，然后A被放到了原来IC的位置，然后X就插入到它的啊B2这样的一个位置，然后这是一个那个不过了过滤器的这样的一个卡西的呃，数据的插入的过程。那在我们这个。这篇论文中里面的话。我们我们就是这样的一个扒之后，我们不不不仅记录了他的一个这样的一个签名，这个签名是为了那个确定一下是不是这个K吧，但然如果呃签名可能会有冲突，签名冲突的话，就会造成一个假阳性，除此之外的话，我还记得呃那个记录一下它的leveld，就下面这张读这个level ID，比如145这都它live ID，这个live ID的话，它其实记录了它是位于哪个S，然后我就可以去具体的里面去查或者去更新。

这样的话就相当于是我拿这个talk这样的一个过滤器去替代了一个filter，这过滤器它的读性能是更好的。呃，最后一个优化点就是空间放大，然后空间放大的话，首先DB它本身它提提出了一个叫做动态，就是动态的这每一层的这个预值的这样的一个一个，呃，这样的一个机制。首先说CB我们默认是采用leveling compassion，但是它也也提供了类似于t compassion这样的一个选项，那假如说我们如果采取leveling compassion的话，它这个地方提供一个叫dynamic dynamic dynamic level side adaption这样的一个机制。就是我们通过刚才的分析，我们知道这个level compassion的空间放大率，它它其实不大，它是1/7，但是有个前提就是这个分析是最后一层数据是在充满的情况下，那我们知道在实际情况下，我们最后一层数据可能是很有可能充不满。

那比如说我们每层的这个容量与呃，就放大比例是T吧，那它每一层容量阈值就是一个乘以T的这个关系，它是一个TT系数的一个等比系，等比系列，呃，一个等比数列，那根据这个等比数列给它做一个求和的话，我们发现最后一层数据量是占绝大多数，它是占总大小的T，呃，T分之T减一，而前面所有的层只占总大小的T分之一，也就是说这时候主力的数据量是前面所有层数据量的一个。一个比值，它只是占一个T减1/1的。那比如说呃肉体并中，假设我们这个T是十，放大率是最大器是十，那零到四的啊，因为放大比例是十嘛，假第零层是预值是一呃呃一个G，然后接下来第呃L1到L4就是实G100G千个G。那如果说我们。L4全写满的话，它容易率就是全加起来再除以整体的数据，它是一个1.1的话，它就是呃，一加上1/7嘛，就是这样的一个放大系数。

好像这个T分之一或者T减1/1，它的总力量好好像是不高的，但实际情况中，大多数情况下，其实最后一层的实实际量其实都是没有达到，远远没有到这个预知的，那比如说我们当前L4，如果按照这个静态的这种这种阈值的话，那可能当前L4中数据没有写很多，它可能就200个这个数据，那这时候它的放压放大率就不会太好看。就这时候可能前面就会有大量的这样的一个荣誉数据。因此这个RODB的这个动态，它会提出一种机制，就是动态的调整每次容量阈值，这地方给出了一个一一个例子，就是说每次我L0充满了之后，我它的数据不是先往L1去写，而是说先往最深的最空的那个数据，比如说我们先往LL5去给它进行合并。然后这时候让L1到L4都是一个空的，一个都当前都是空的，那我们直到这L5的实际数量达到一个比较小的一个阈值，假如说刚开始最初的那个呃，容量的阈值是十十兆。那当这个L5的实际数量要超过达到预值的时候，就达到最初的预值十兆的时候，那我们的呃compassion呢，就是L0往下落的这个目标层，把它切到L，切到L4，然后并且让L4的阈值保持，保持为一个最初的一个最初始的一个预值，就是说十兆，那然后再把L5的L5的这个日值给它乘以一个T，就乘以一个放大系数，就说就说L4和L5之间的这个容量阈值还是保存了，保持了一个保持一个TVB之间的关系。

那比如说L5的实际数量到达到11兆的时候，那L4的预值其实只是一个1.1兆。然后数据接下来会不断的往L4去写，然后当L，然后L5的，然后L4再向L5进行com，那L4逐渐呢也会达到一个阈值，那L4达到阈值的话就会以此类推嘛，就把就把L3也打开，然后把L3作为这个合并的首要目标层，然后L2L3的初始的那个阈值是十兆，那L4把它嗯，这时候就扩大了100兆，然后L5就扩成。扩充到了这个1000兆就是一个G，那这个时候数据落下来的话，首先要从L0就会向L2，向最新的目标，向二层进行合并。

OK，那我们看到这种这样的一个动态调整一个一个一个一个大小策略的话，就可以说始终会将这个数据的这个容量保持在这个T减1/1，就是说始终会保持到这个，就即使我们刚才例子T等于十的话，它空大空间放大率就始终不会超过这个1.11这样的一个像就始终会被会这样一个一个理想的一个呃风空间放大率。嗯，然后建立空间放大的话，其实还有其他的其他一些实践措施，比如说逻DB目前已经实现了包，包括比如说这个呃，Key profit including啊，就说它可以让相应的这个K的前能共享一次就只存一次，这样的话可能会节省10%左右的这样的一个空间开小，还有一些具体的的一些一些时间措施吧，比如说这个six ID garbage collection，就是说它可以有一个there out，一个优化，就是说当1k six number它小，它要比最老的snapshot这个safe number还要小的时候，那我就把它强，在下一次的时候把它强改成零。

那这样的话，它会不会影响到这个数据多版本的一个正确性，但同时的话，因为是这个零的，这个在在入加了压缩之后，这个six number等于零的话，它压缩率非常高的。呃，从而提升了这个，呃，提高了这样的空间利用率，然后接下来就是压缩，就是。嗯，目前如DB来讲的话，它也支持了很多压缩算法，呃，就是一些第三方的一些缩算，比如LZ啊，Snap等等这些，然后可以以SST这个为S文件作为一个单元来进行那个设置不同的压缩算法。那注意到这个其实对这个KB数据进行压缩，其实在降低空间消耗的同时，会增加一个，首先会增加这个毒的开销，而且而且你本身你在压缩的过程中，它会消耗一定的CPU资源，而且你读的过程中还要进行一个解压，所以说这地方就要做一个折中考虑。因此我们就可以在那个一个时间一个时间的一个通常一个一个优化的策略，就是L0到L2层，它因为那个往下落盘的那个比较频率比较高，那这时候我就不用加压缩，而且它数据然数据量也不太大，我就不用任何压缩。

啊，然后呢，在在更下面的层使用一些比较轻量的一些压缩的算法，比如一些中间层的话，我可以用一些轻量级的压缩啊，比如snap r z这样的话，其实综合考虑了压缩带来的空间开销和这个性能的一个。然后在最下面一层的话，我可以用更重那些压算了，因为它都它对读的这个它读到的概率会比较低，因为它数据比较老，再一个就是呃，它的就最往下的层，它的容量，容量越是越大，它可能存储的数据也就越多，你这样加一个压缩的话，它的那个空间开销，空间开销上可能会有一个比较大的一个节省。然后关于filter的话，DB的话还有一个时间就是说。啊，布filter本身的话，它也会引入线样的内存靠销，因为你要把这些布filter的要把它导到内存里面去进行一个啊探查。那在内存有限的情况下的话，我们可以减小不用非的内存的占用啊，一个一个一个基本策略就是这个可以catch，就是把它做一个缓存，再一个就是说我可以就干脆就粗暴一点，我让RM税在下面的层，就比较深的层，因为被查到概率比较低，我们就不再进行filter，这真的去读就可以了。

然后这这呃，也是考虑到最后的层因为数量比较大，它不用非套，本身呢，占用的那个空间也比较大，它会消耗比较多内存，再一个就是它数据比较老了，本身被访问到的概率本身也比较小，因此我把最后面的层，或者说最后面那几层的不用filter给它直接去掉，就是我不用不用filter进行过滤了，那它对读的性能其实影响也是，嗯，不会太大，但是它对啊，这个内存的消耗来讲，它会有一个，呃，就是会有一个一个较多的节省。嗯，还有一些其他的一些一些方法，比如说compassion并发，我们我们如果去看DP代码的话，其实它它的它是做了一个compassion的一个并发的，就是如果说两个compass job之间，呃，Comp它是在一个后台，后台异步形程来来出发的，呃来进行执行的，执行过程中它把它划分成不同comp job，然后每个comp，如果两个comp job之间的ST的这样的一个集合互相不重叠的话，那显然这两个卡job是可以完全先升级去并发的。

然后我们知道L0层的sat文件通常是互相有重叠的，那这是这个的话，Rose DB也提了一个优化，就是它有一个sub compassion的一个概念，嗯，这地应该时间关系我们也不会展开讲，这个就是具体还可以看一些相关的些它的一些文档，就是就是这样的话，我们把L0的这样有有SST重叠这样的一个情况也给它做了一个并发，还有一个就是呃，有一篇那个呃一个呃IPDPS20141篇论文，就是说这个comp之间它可以做一个流水线。嗯，最后是那个。我这篇分享参考了一些相关的一些论文。呃，最后呃，今天的技术分享到这里就结束了，呃，首先感谢，呃最后也感谢大家的参与，然后也欢迎大家去继续关注我们后续的这个DB动建的一些相关的技术，技术相关的一些活动。

好，谢谢大家。