4.Concurrency and Recovery in the LSM-tree
本节我们来研究下用于LSM-tree并发访问和恢复的技术。为此，我们需要更深入地描述出rolling merge过程。我们将该并发访问和恢复算法正确性的形式化证明作为以后的工作，目前只是在此处简单地描述下它们的具体过程。
4.1 Concurrency in LSM-tree
通常，一个具有C0,C1,C2…Ck-1和Ck K+1个组件的大小不断增长的LSM-tree，其中C0组件是放到内存中，其他组件都是磁盘驻留的。当Ci-1大小超过其阈值时，会由(Ci-1,Ci)之间的异步的rolling merge过程负责将记录从小的组件移到更大的组件中。每个磁盘组件都是由以B-树类型的结构组织的page-sized的节点组成，同时在根节点下的各层的节点都是按照key的大小顺序排列的，同时这些节点又会被放置到muti-page block中。该树结构中的目录信息可以对用户访问所需经过的节点进行指引，同时还会标识出某muti-page block包含了那些页面节点(single page nodes)。在大多数情况下，每个muti-page block都装满了页面节点(single page nodes)，但是也有些情况一个muti-page block只有少数的节点组成。在这种情况下，LSM-tree的活动节点将会由该muti-page block的一个连续的页面集组成，同时它们也不一定是该block开始的那部分页面。除此之外，LSM-tree组件的结构与[21]中的SB-tree结构并无二致，读者可以参考该论文以获取更多细节。
在执行等值匹配查询时，磁盘组件Ci的一个节点可能是存在于单独的一个内存页中，或者是通过它所在的muti-page block而缓存在内存中。一个muti-page block要么是因为一个long range查询要么是因为rolling merge游标正在穿过该block。在任何情况下，所有未被锁住的Ci组件的节点都是可以始终被访问的，磁盘访问也可以执行以定位内存中的节点，即使该节点是正在进行rolling merge的muti-page block的一部分。考虑到各种因素，针对LSM-tree的并发访问方法必须解决如下三种类型的物理冲突：
1. 查询操作不能同时去访问另一个进程的rolling merge正在修改的磁盘组件的节点内容
2.针对C0组件的查询和插入操作也不能与正在进行的rolling merge的同时对树的相同部分进行访问
3.从Ci-1到Ci的rolling merge的游标有时需要越过从Ci到Ci+1的rolling merge的游标，因为数据从Ci-1移出速率>=从Ci移出的速率，这意味着Ci-1所关联的游标的循环周期要更快。因此无论如何，所采用的并发访问机制必须允许这种交错发生，而不能强制要求在交会点，一个进程(移出数据到Ci的那个)必须阻塞在另一个进程(从Ci移出数据的那个)之后。
节点是LSM-tree中用于避免基于磁盘的组件的并发访问冲突的加锁单位。正在因rolling merge而被更新的节点会被加上写锁，同时正在因查询而被读取的节点将会被加上读锁。同时用于防止死锁发生的目录锁机制也已经被充分研究过(比如，参见[3])。C0中所采用的锁机制则取决于所采用的数据结构。比如，在(2-3)-树的情况下，我们可以用写锁锁住一个包含了merge到C1中的某个节点的受影响的边界内的所有记录的(2-3)树目录节点下的子树；同时用读锁锁住查找操作所涉及的查找路径上的所有节点，这种不同类型的访问就是互斥的。同时与[28]类似，我们只考虑在最底层的多级锁机制上的并发机制。关于更抽象的锁，比如用于提供事务隔离性的key range锁，以及关于phantom update的问题，请参考[4],[14]的讨论。只要正在被查找的叶级节点被扫描后读锁就会释放。在游标下的节点的写锁，在节点被merge到更大的组件后也会被释放。这就为long range find或者是让一个更快速的游标越过一个慢速游标，这样就能解决上面提到的第3点。
假设我们正在执行一个在两个磁盘组件间的rolling merge，将记录从Ci-1(又称为该rolling merge过程的内组件)移到Ci(又称为该rolling merge过程的外组件)。Rolling merge游标总会有一个准确的位于Ci-1的叶节点的内组件位置，它会指向将要被移出到Ci的下一条记录，同时在Ci-1的更高层的目录上沿着到达该叶子节点的访问路径都有一个对应位置。同时在Ci组件的叶子节点及到达该叶子节点的访问路径中，该游标也有一个外部组件位置，该位置也对应着将要参与到merge中的那条记录。在merge游标穿过外部和内部组件的后续记录时，由该merge过程新创建出来的叶子节点将会按照从左到右的顺序立即放置到新的缓存中的multi-page block中。因此在当前游标位置附近的Ci组件中的节点通常会被分割到内存中的两个未满的multi-page block中：”emptying”block(记录已经用尽但是仍包含一些当前游标未到达的信息)和”filling” block(反映了此刻的merge结果，但是还未全满所以未被写到磁盘)。为了能够并发访问，”emptying”block和”filling” block都包含整数个C1树中的page大小的节点，同时这些节点都是驻留在内存中的。在merge步骤中的操作对节点进行重组时，相关的节点会被加上写锁，以阻止对这些记录的其他类型的并发访问。
在rolling merge的最普通实现方式中，我们可能希望保留Ci-1组件中的某些记录，而不是将游标所经过的所有记录都移出到Ci中。在这种情况下，merge游标附近的Ci-1组件中的节点依然会被分到内存中的两个multi-page block中，包含了merge游标还未到达的Ci-1的节点的”emptying”block，以及从左到右放置的，由merge游标最近经过的和仍然要保留在Ci-1中的节点组成的”filling” block。在最常见的情况下，merge游标的位置一次将会影响四种不同的节点：在”emptying”block中的内组件和外组件节点(对于它们来说，merge即将进行)，在” filling”block中的内组件和外组件节点(对于它们来说，随着光标的行进，新的信息正被写出)。很明显，在某个时刻这四种节点可能都处于未满的状态，对于包含它们的block来说也是这样的。在merge真正修改节点结构时，会在这四个节点上加上写锁，同时会在特定的时间会释放这些锁以允许更快的游标来超过它；我们会在当外组件的”emptying”block中的节点已经完全被用尽，而其他三个节点还很空的时候对这些锁进行一次释放。这是可以的，因为我们可以在一个节点还很空以及blocks还很空的树进行所有的访问操作。一个游标越过另一个的情况需要仔细考虑，因为通常被绕开的rolling merge在它的内组件中的游标位置将会变得无效，同时这就要求能够重新调整游标。同时上面的这些，也必须应用到两个组件的上层目录节点。通常上层目录节点可能不是驻留在内存中的，这样就需要使用一个稍微不同的算法，但是在任意时刻都还会有filling node和emptying node。我们将这些复杂的需要考虑的地方留到以后的工作中，在实现一个真正的LSM-tree后将会提供更多的经验。
目前为止，我们还没有考虑从C0到C1的这一个特殊的rolling merge过程。实际上，与基于磁盘的组件间的merge相比，这个是相对简单的。与其他的merge步骤一样，需要一个单独的CPU来负责该任务，这种其他的访问因写锁所耽误的时间就会尽可能的少。参与merge的C0记录的range必须预先计算，同时像前面所说的那样，需要提前在该记录边界上加上一把写锁。除此之外，还可以通过批量从C0组件中删除记录来节省CPU时间，这样就不需要在每条记录删除后进行一个rebalance；在merge步骤完成之后，再对C0进行完整的调整。
4.2 LSM-tree中的恢复
当新的纪录被插入到LSM-tree的C0组件中后，rolling merge进程会将纪录逐步迁移到后面更大的组件中，这项工作是发生在内存中的multi-page block上。由于在内存中缓存了一些变更，这样在它写入到磁盘之前对于系统失败来言它就不是安全的。我们就面临了一个经典的恢复问题：重构那些已经存在于内存中的而在系统crash丢失的内容。正如我们在第2章的开头提到的，我们不需要创建特殊的日志来恢复新创建的这些记录上的索引值：针对这些新记录的事务型插入日志已经被常态性地写出到一个顺序性的日志文件中，因此只需要简单地将这些插入日志(日志里包含了所有field的值插入记录所对应的RID)作为索引值恢复的基础即可。这种用于索引恢复的新方式必须内建到系统恢复算法中，同时它也会影响到对于这种事务型插入历史日志的存储空间回收时间，在恢复发生时回收会被延迟。
对于LSM-tree的索引恢复来言，最重要的是要仔细定义checkpoint的格式，以及需要知道从顺序型日志的何处开始，如何回放后续的日志，从而能够准确地重现那些需要恢复的针对索引的更新。我们采用了如下的模式。当在T0时刻启动了一个checkpoint后，我们会完成所有正在进行的merge步骤，保证所有节点的锁会被全部释放，然后会将所有的新记录的插入延迟直到checkpoint完成；与此同时，我们会通过下面的步骤创建一个LSM-tree checkpoint。
l 将C0组件的内容写入到一个已知的磁盘位置；之后，针对C0组件的记录插入就又可以开始了，但是merge步骤将会继续被延迟
l 将所有磁盘组件在内存中的脏页flush到磁盘
l 创建一个具有如下信息的特殊的checkpoint日志：
n 日志序列号，LSN0，即T0时刻最后插入的索引行
n 所有组件的根节点的磁盘地址
n 上面这些组件中的所有merge游标的位置
n 当前关于新的multi-page block的动态分配信息
一旦checkpoint信息被存入磁盘，就可以恢复LSM-tree的正常操作了。在crash发生或者重启时，就可以找到这个checkpoint，将保存过的组件C0以及其他组件需要进行rolling merge的缓存的block内容加载回内存。然后，从日志中LSN0之后的第一个LSN开始读入内存，将它们相关联的索引值加入到LSM-tree。在进行checkpoint时，包含了所有索引信息的所有磁盘组件的位置信息已经被记录到checkpoint日志中。这些信息都还没有被后续的multi-page block的写入擦除，因为这些新的写入在checkpoint过时之前，总是会被安排到新的位置上。我们开始恢复索引行的插入日志，将新记录加到C0组件；此时，rolling merge过程也重新开始，会覆盖在该checkpoint之前写入的那些multi-page block，但是只有当所有最近插入的行已经被索引及恢复完成后，所有的新索引值才会恢复。
这个恢复方法很明显是可以工作的，唯一的缺点在于各种发生在checkpoint执行时的磁盘写入操作可能会经历一个比较大的暂停。但是这个暂停并不是特别严重，因为当我们将C0组件快速写入磁盘后，就可以恢复针对C0的插入；这可能导致新插入到C0中的索引值被merge到更大的磁盘组件的时间有所延迟。一旦checkpoint完成，rolling merge过程就可以继续干活。需要注意的是，上面提到的checkpoint日志里的最后一类信息“当前关于新的multi-page block的动态分配信息”。是因为在crash发生时，我们需要知道对于我们的动态磁盘存储分配算法来说，在恢复时哪些multi-page block是可用的。这个问题并不难解决；实际上[23]解决了一个关于垃圾收集更负责的问题。
关于恢复的另一个细节是如何处理目录信息。需要注意在rolling merge过程中，每当一个multi-page block或者一个高层目录节点被磁盘中读入以清空，它必须立即安排一个新的磁盘位置以应对checkpoint在emptying完成之前发生的情况，同时剩余的缓存信息必须强制写到磁盘。这意味着指向下层emptying节点的目录节点必须立即修正以指向新的节点位置。类似地，我们必须立即为新创建的节点安排一个磁盘位置，这样树中的目录节点就能够立即指向对应的磁盘位置。每时每刻，我们都要确保那些包含指向被rolling merge缓存的底层节点的指针的目录节点也已经被缓存；只有通过这种方式，我们才能迅速做出必要的修改以保证checkpoint不会因等待修正目录节点的IO而被挂起。此外，在checkpoint发生只之后，以及multi-page block被读回内存以继续rolling merge时，所有相关的blocks必须被安排一个新的磁盘位置，因此所有指向附属节点的目录指针都必须被修正。这听起来好像需要大量的工作，需要注意的是实际上这不会产生额外的IO需求，同时每个缓存的block所涉及的指针数大概是64。另外假设checkpoint的频率只需要保证恢复时间不会超过数分钟即可，这些修改将会平摊到大量的被merge的节点上；这也意味着两个checkpoint之间大概相隔数分钟。
5. 与其他访问方式的性价比对比
在例1.2中，我们考虑了针对History文件上的Acct-ID||Timestamp索引的B-树实现，因为它是用于商业系统中的最常见的基于磁盘的访问方式。现在我们希望说明的是，不存在一个可以提供更好的IO性能的磁盘索引结构。为了说明这一点，我们论述如下。
假设我们正在处理一个任意的索引结构。假设索引具有20天的生命周期，并以每天8小时每秒1000条记录的速率产生，索引条目的大小为16字节(4字节用于Acct-ID，8字节用于Timestamp，4字节用于History表的RID)，这就意味着将会有9.2GB的记录规模，在不存在空间浪费的情况下大概要2.3个million的4KB索引页面。这些结论适用于任何一种索引模式。B-树具有一些叶子节点，以及上层目录节点带来的空间浪费，但是一个可扩展的hash表可能会有不同程度的空间浪费，同时也没有目录节点，但是这两种结构都必须能够放得下上面提到的9.2GB的记录数据。现在如果我们要将一条新的索引记录插入到索引结构中，需要计算出该记录需要被插入到那个页面中并保证该页面已经在内存中。自然地引出了一个问题：新插入的记录通常是不是可能会被放置到现有9.2GB索引记录的中间的任意位置？对于大多数经典访问结构来说，答案是肯定的。
定义5.1 如果一个基于磁盘访问方式的索引结构能够为它的新插入的索引记录基于Key-value的最终排序规则，即时地安置到现有的记录中，我们就认为它具有连续性结构(Continuum Structure)这一属性。
下面的TPC benchmark应用中的Acct-ID值是从100,000,000个可能取值中随机生成的。根据定义1.1，针对Acct-ID||Timestamp索引的每个新插入的记录将会被放置到现存记录组成的2.3个million页面中非常随机的一个位置上。比如对于B-树来说，总共576,000,000的总记录数，对于每个Acct-ID来说将会包含大概5.76(5.76=576,000,000/100,000,000)个记录；可假定具体相同Acct-ID的记录具有不同的时间戳。每个新插入的记录将会被放置到具有相同Acct-ID的记录的右侧。但是这仍然还是具有100,000,000个随机选择地插入点，这也意味着每个插入将会随机地落入现有的2.3million个page中。与之相比，在一个可扩展hash模式[9]中，新的记录的排列规则是根据从Acct-ID||Timestamp计算出来的hash值进行的，很明显这与将一个新记录放到现有记录中是类似地。
2.3million个page是一个能够容纳下9.2GB大小的记录的Continuum Structure的最小可能值了。假定每秒1000个插入，那么这样一个结构的每个page大概需要间隔2300秒才会被访问一次；根据五分钟法则，将所有的page缓存起来是不划算的。如果我们考虑像Bounded Disorder文件[16]用更大的节点来保存记录，这不会带来什么好处，是因为尽管访问频率变大，但是缓存节点的内存开销也在变大，这两者相互抵消了。通常，一个page会因为某条记录的插入而读入内存，后面又会因为为了给其他page腾出空间而挤出内存。在事务型系统中，在将磁盘page从内存清除之前原地更新，这种更新会对每个索引插入产生额外的一次IO。因此可以这样说，对于不会延迟更新的Continuum Structure来说针对每个索引插入将会需要至少两个IO操作，这与B-树基本上是一致的。
大部分现有的基于磁盘的访问方式都属于Continuum Structure，包括B-树[5]，以及它的很多变种比如SB-树[21]，Bounded Disorder文件[16]，各种hash模式比如可扩展hashing[9]，以及很多其他类型。但是，也有一些访问方式会将它们的记录从某一部分迁移到另一部分：Kolovson和Stonebraker的MD/OD R-树，Lomet和Salzburg的Time-Split B-树([17],[18])。Differential File[25]也会先将变更收集到一个小的组件中，然后将更新应用到全局结构中。我们下面会稍微深入地解释下这些结构。
首先我们来分析下为何LSM-tree可以在某些情况下降低近两个数量级的磁盘磁臂负载，而在IO性能上完胜Continuum Structure。LSM-tree的优势主要源于如下两个因素：(1)能够保证组件C0是内存存放的，(2)细致的延迟放置策略。原始插入可以作用于一个基于内存的组件是很关键的。在Continuum Structure上的新记录的插入需要两次IO原因是：本身索引大小没法很经济地缓存在内存中。如果LSM-tree的C0组件的内存驻留属性是无法保证的，仅仅是一种概率上的，随着内存驻留情况的恶化，随着新记录插入所引起的IO开销的增加将会导致LSM-tree性能的退化。在保证初始插入不会产生任何IO的情况下，第二个因素为LSM-tree提供了更高性能的支持。一个经过仔细设计的延迟放置策略，可以将C0的大小有效地控制在合理地范围内。实际上，多组件LSM-tree提供了一系列地延迟放置策略来最小化总开销。
Time-Split B-tree
我们先来看下Lomet和Salzburg的Time-Split B-tree(TSB-tree)。TSB-tree是一个二维搜索结构，它通过时间戳和keyvalue两个维度来定位记录。每当具有给定keyvalue值的记录被插入时，老的那条记录就会变成过时的；然而会保存一条记录的所有历史状态，无论是过期还是未过期的，都会被索引。当一个新记录被插入到TSB-tree中的当前节点时，如果该节点空间不足，它可以根据key-value或者时间戳进行分裂，具体取决于环境设置。如果节点是根据时间t进行分割的，那么时间戳小于t的所有记录将会进入该次分裂的历史节点中，在时间t之后的那些记录则会作为当前节点。最终那些过时的记录将会被迁移到一个廉价的write-once存储设备中。所有的当前记录和当前节点存于磁盘中。
可以看到TSB-tree的这个模型与我们的模型有些不同。在具体相同Acct-ID的记录被写入后，我们不会对现存的老的记录做任何地过期假设。很明显，TSB-tree的当前节点集承担着延迟更新到长期存储组件的角色。但是当前tree不会像LSM-tree的C0那样，被保证保存在内存中。实际上，当前tree是基于磁盘的，而历史tree是存于write-once存储设备的。没有证据表明TSB-tree可以提高插入性能，它的设计目的在为整个时间轴上的所有记录提供一个历史索引。并不保证新的插入一定会发生在内存中，因此每次记录插入会需要两次IO。
MD/OD R-tree
Kolovson和Stonebraker的MD/OD R-tree[15]，与TSB-tree不同，它使用了一个二维访问模式(R-tree) 的变种来通过时间区间和keyvalue来索引历史记录。MD/OD R-树中引入的这个R-tree变种是跨越磁盘(MD)和光盘(OD)的；最终的目的，与TSB-tree类似，是要将过期记录移到一个保存在廉价write-once光盘存储设备上的具有叶子页面和目录页面的归档R-tree上进行保存。这种迁移是通过VCP(Vacuum Cleaner Process)进行。但磁盘上的R-tree索引到达一定阈值，VCP会将其中一部分最老的叶子节点移到光盘上的R-tree中。与TSB-tree类似，MD R-tree存于磁盘组件，OD R-tree存于write-once存储设备，同时也没有证据表明MD/OD R-tree可以提高插入性能。很明显OD中排除了rolling merge技术。由于并不保证新的插入一定会发生在内存中，因此每次记录插入也会需要两次IO。
Differential File
Differential File[25]以一个长期保持不变的主数据文件作为起点，新增加的记录会被放置到一个称为Differential File的特殊区域。在未来的某个时刻，它将会与主数据文件进行合并，之后重新产生一个新的Differential File。这篇论文的很多内容都是关于更小的动态区域的优势以及避免重复访问的方法，因为根据唯一记录标识符的查找首先需要查找differential 文件(通过某些索引)，然后查找主数据文件(通过另一份索引)。Bloom Filter推荐作为避免重复访问的主要机制。同样的，Differential File也不保证Differential File一定是存在于内存中的。只是在3.4节里提到，在Differential File被dump，以及后面被合并到主数据文件时，可以将一个”differential-differential”文件存于内存以允许在线的重组织。但是没有对这种方式进行更多分析。它有些类似于LSM-tree中在C1与C进行merge的同时，在内存中维护一个C0组件的策略，但是论文里的描述看起来假设插入速率相对低些，在3.2节的例子中，它假设一个10,000,000条记录的文件每小时有100个变更。它没有建议将”differential-differential”文件一直存于内存，也没有提到针对插入操作所能节省的IO。
Selective Defered Text Index Updates
Dadum，Lum，Praedel和Schlageter[7]提出的文件索引维护方法也是设计用于提高系统索引更新性能的，通过延迟实际的磁盘写入。索引更新会被缓存在内存中，直到产生查询冲突或者后台任务触发时才会被强制写入。首先这是一个文本系统，这里的冲突将会发生在文档关联的关键字正在进行的更新操作以及与被修改的关键字相关联的查询操作之间。更新之后，查询将会运行在磁盘索引上。因此与LSM-tree不同，内存缓存并不是索引的一部分。这种延迟策略，允许进行批量的更新。但是这种更新模式依然类似于Continuum Structure。
6. Conclusions and Suggested Extensions
B-tree，由于它最常用的目录节点是缓存在内存中的，实际上是一种混合数据结构，它使用廉价的磁盘存储设备来保存主要数据，而对于那些访问最多的数据则使用昂贵的内存提供访问能力。LSM-tree将这种结构扩展到了多个层次，同时引入了执行multi-page磁盘读取的merge IO的优势。
图6.1，是对图3.1的一个扩展，它绘出了对于通过B-树以及两组件LSM-tree的两种数据访问模式中，”每Mbytes访问开销”与” 每Mbytes访问频率”之间的关系。在比较低的数据访问频率下，”cold”数据比较适合放到磁盘存储中，以典型的开销来看，在0.04IO/秒/Mbytes的情况下(即”freezing point”)，磁盘访问开销是$1/MByte。”freezing point”之后就是”warm”数据区域，此时磁盘磁臂会成为数据访问的限制因素，同时磁盘存储空间处于未完全利用状态；以例3.3来说，1 page IO/s/Mbyte的开销是$25/Mbyte。最后，当数据访问频率高到B-tree访问数据都应该缓存到内存中时，就是”hot”数据了；由于内存开销是$100/MByte，这样访问开销就是$100/MByte，同时这也意味着4 IO/s/Mbyte的访问频率，也就是”boiling point”。
B-树的缓存机制的效果是在Hot数据区域随着访问频率的增加曲线依然很平坦，这样当曲线越过Warm数据的上升阶段后即使访问频率变得再高也不会导致更高的开销。稍微思考一下，可知LSM-tree可以降低那些可merge的操作的访问开销，比如插入和删除，同时对于Cold数据会更明显。此外，很多需要全内存B-树来解决的访问场景，可以通过大部分驻留在磁盘上的LSM-tree就可以实现。在这些场景下，由于LSM-tree批量处理的影响，以逻辑访问频率(inserts/秒)来看数据是hot的，但是如果以物理磁盘的访问频率来衡量的话仅仅是warm的。这也是那些具有大量可merge操作的应用的一个极大的优势。6.1 LSM-tree应用的扩展
很明显，LSM-tree记录可以直接包含记录内容，而不是通过RID指向存储在磁盘上的记录。这就意味着记录本身可以根据它们的keyvalue进行聚集。这样做的开销在于更大的记录大小，以及带来的每秒插入速率R(以字节为单位)的增长，也会因此影响到游标移动以及总的IO频率H。然而，正如我们在例3.3所看到的，一个三组件LSM-tree能够以磁盘存储空间的开销提供存储记录和索引的需求，同时这里所有的磁盘空间是以一种非聚簇的模式对行进行存储的。
聚簇的优势会对性能具有重要的影响。比如，考虑Escrow transactional method[20]，由于长生命期更新的非阻塞属性使得它可以很好地支持工作流管理。在Escrow method中，一个长生命期事务会产生大量的针对Escrow字段的增量更新。我们需要保存针对这些Escrow quantities的日志，可以考虑使用两种类型的聚簇索引：事务ID(TID)，和发生Escrow quantities的字段的字段ID(FID)。在一段时间内，针对一个TID可能就会有20多条Escrow日志，同时根据TID进行聚集在事务进行提交或abort时会显得更为重要，这些都决定了这些日志所应采取的结构。在commit时，发生在字段上的quantities将会被持久化，因此日志可以简单地被丢弃，但是在abort发生时，我们希望可以根据日志里的FID返回针对该field的quantity。同时对速率也有一定的要求。在处理一个abort时，被abort的事务的日志需要能够被访问(通过TID进行聚簇是一个很大的优势)，同时对应FID的字段需要被修正。但是，如果这个字段不在内存中，那就需要读取包含了根据FID进行聚集的对应日志的记录。之后当Escrow字段被读入到内存后，我们就可以尝试访问根据FID聚集的包含了可能需要的更新的所有日志；这就又需要大量的日志访问，因此将这些日志在LSM-tree中进行聚集将会节省很多开销。使用LSM-tree来对Escrow日志首先根据TID，然后根据FID进行聚集，在相关联的字段不在内存时，将会节省大量的IO。这种策略是在[20]中的”extended field”的一个改进。
另一个针对LSM-tree算法的可能修改是在2.2节所提到的，保留一些最近的记录在组件Ci中，而不是将它们全部移入到Ci+1中。根据这个想法可以产生更多的改进。比如在游标循环移动过程中，可以生成一个基于时间-key的索引。通过对基于时间-key的索引进行一些控制，Rolling merge过程可以用来为新版本的插入操作提供很高的效率，同时多组件结构意味着可以将最后一个组件改成一个write-once存储设备。这种策略会在未来深入研究，同时它已做为一篇会议论文的主题。
关于未来的研究思路还有如下的一些：
(1) 对定理3.1中的成本分析方法以及例3.3进行扩展，使得它们可以适用于查找操作必须和merge过程进行IO平衡的情况下。由于磁盘还有其他的额外负载，那么将所有的磁盘能力都用于rolling merge过程就是不现实的，因此需要针对这种情况进行优化。磁盘能力的一部分必须要分给查找操作。其他的一些扩展成本分析的方式比如允许删除优先于向组件Ck的迁移，同时考虑在(Ci-1,Ci)merge中的内组件Ci-1的最近的记录比例。
(2) 很明显我们可以停下CPU的其他工作让它专门维护LSM-tree，这样CPU就不需要负责产生日志记录。我们只需要将日志工作交给其他CPU，然后与它通信查看完成状况。在共享内存的情况下，这几乎不会增加额外的开销。这种分布式工作方式的设计需要经过仔细地思考。
致谢
感谢Jim Gray和Dave Lomet的帮助，他们两位阅读了该论文的早期版本，并提出了宝贵的改进建议。此外，这篇文章的审稿人也提出很多有价值的建议。
参考文献
[1] Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, "The Design and Analysis of
Computer Algorithms", Addison-Wesley.
[2] Anon et al., "A Measure of Transaction Processing Power", Readings in Database Systems,edited by Michael Stonebraker, pp 300-312, Morgan Kaufmann, 1988.
[3] R. Bayer and M Schkolnick, "Concurrency of Operations on B-Trees", Readings in Database Systems, edited by Michael Stonebraker, pp 129-139, Morgan Kaufmann 1988.
[4] P. A. Bernstein, V. Hadzilacos, and N. Goodman, "Concurrency Control and Recovery in Database Systems", Addison-Wesley, 1987.
[5] D. Comer, "The Ubiquitous B-tree", Comput. Surv. 11, (1979), pp 121-137.
[6] George Copeland, Tom Keller, and Marc Smith, "Database Buffer and Disk Configuring and the Battle of the Bottlenecks", Proc. 4th International Workshop on High Performance Transaction Systems, September 1991.
[7] P. Dadam, V. Lum, U. Praedel, G. Shlageter, "Selective Deferred Index Maintenance &
Concurrency Control in Integrated Information Systems," Proceedings of the Eleventh
International VLDB Conference, August 1985, pp. 142-150.
[8] Dean S. Daniels, Alfred Z. Spector and Dean S. Thompson, "Distributed Logging for
Transaction Processing", ACM SIGMOD Transactions, 1987, pp. 82-96.
[9] R. Fagin, J. Nievergelt, N. Pippenger and H.R. Strong, Extendible Hashing — A Fast Access Method for Dynamic Files, ACM Trans. on Database Systems, V 4, N 3 (1979), pp 315-344
[10] H. Garcia-Molina, D. Gawlick, J. Klein, K. Kleissner and K. Salem, "Coordinating Multi-Transactional Activities", Princeton University Report, CS-TR-247-90, February 1990.
[11] Hector Garcia-Molina and Kenneth Salem, "Sagas", ACM SIGMOD Transactions, May 1987,pp. 249-259.
[12] Hector Garcia-Molina, "Modelling Long-Running Activities as Nested Sagas", IEEE Data Engineering, v 14, No 1 (March 1991), pp. 14-18.
[13] Jim Gray and Franco Putzolu, "The Five Minute Rule for Trading Memory for Disk
Accesses and The 10 Byte Rule for Trading Memory for CPU Time", Proceedings of the 1987 ACM SIGMOD Conference, pp 395-398.-32-
[14] Jim Gray and Andreas Reuter, "Transaction Processing, Concepts and Techniques",
Morgan Kaufmann 1992.
[15] Curtis P. Kolovson and Michael Stonebraker, "Indexing Techniques for Historical
Databases", Proceedings of the 1989 IEEE Data Engineering Conference, pp 138-147.
[16] Lomet, D.B.: A Simple Bounded Disorder File Organization with Good Performance, ACM Trans. on Database Systems, V 13, N 4 (1988), pp 525-551
[17] David Lomet and Betty Salzberg, "Access Methods for Multiversion Data", Proceedings of the 1989 ACM SIGMOD Conference, pp 315-323.
[18] David Lomet and Betty Salzberg, "The Performance of a Multiversion Access Method",Proceedings of the 1990 ACM SIGMOD Conference, pp 353-363.
[19] Patrick O’Neil, Edward Cheng, Dieter Gawlick, and Elizabeth O’Neil, "The Log-Structured Merge-Tree (LSM-tree)", UMass/Boston Math & CS Dept Technical Report, 91-6, November,1991.
[20] Patrick E. O’Neil, "The Escrow Transactional Method", TODS, v 11, No 4 (December
1986), pp. 405-430.
[21] Patrick E. O’Neil, "The SB-tree: An index-sequential structure for high-performance
sequential access", Acta Informatica 29, 241-265 (1992).
[22] Patrick O’Neil and Gerhard Weikum, "A Log-Structured History Data Access Method
(LHAM)," Presented at the Fifth International Workshop on High-Performance Transaction
Systems, September 1993.
[23] Mendel Rosenblum and John K. Ousterhout, "The Design and Implementation of a Log Structured File System", ACM Trans. on Comp. Sys., v 10, no 1 (February 1992), pp 26-52.
[24] A. Reuter, "Contracts: A Means for Controlling System Activities Beyond Transactional Boundaries", Proc. 3rd International Workshop on High Performance Transaction Systems,September 1989.
[25] Dennis G. Severance and Guy M. Lohman, "Differential Files: Their Application to the
Maintenance of Large Databases", ACM Trans. on Database Systems, V 1, N 3 (Sept. 1976), pp256-267.
[26] Transaction Processing Performance Council (TPC), "TPC BENCHMARK A Standard Specification", The Performance Handbook: for Database and Transaction Processing Systems,Morgan Kauffman 1991.
[27] Helmut W?chter, "ConTracts: A Means for Improving Reliability in Distributed
Computing", IEEE Spring CompCon 91.
[28] Gerhard Weikum, "Principles and Realization Strategies for Multilevel Transaction
Management", ACM Trans. on Database Systems, V 16, N 1 (March 1991), pp 132-180.
[29] Wodnicki, J.M. and Kurtz, S.C.: GPD Performance Evaluation Lab Database 2 Version 2 Utility Analysis, IBM Document Number GG09-1031-0, September 28, 1989.