日志结构合并树.docx

Log-Structured Merge Tree,近年来，随着互联网数据的日益增长，管理分布式数据需求的日益增加，Bigtable[1]等一系列NoSQL数据库开始涌现。Bigtable是一个分布式的结构化数据存储系统，它被设计用来处理海量数据，其在提供Tablet服务时使用内存中的memtable和GFS[2]中的SSTable来相互配合着来存储数据更新，其中存储和更新的方法与日志结构的合并树[3]（Log-Structured Merge-Tree，LSM-tree）类似，并以其为基础。Log-Structured的思想最早由 Rosenblum和Ousterhout[4]于1992年在研究日志结构的文件系统时提出。他们将整个磁盘就看做是一个日志，在日志中存放永久性数据及其索引，每次都添加到日志的末尾；通过将很多小文件的存取转换为连续的大批量传输，使得对于文件系统的大多数存取都是顺序性的，从而提高磁盘带宽利用率，故障恢复速度快。 ONeil[3]等人受到这种思想的启发，借鉴了Log不断追加（而不是修改）的特点，结合B-tree的数据结构，提出了一种延迟更新，批量写入硬盘的数据结构LSM-tree及其算法。LSM-tree努力地在读和写两方面寻找一个平衡点以最小化系统的存取性能的开销，特别适用于会产生大量插入操作的应用环境。LSM-treeLSM-tree是由两个或两个以上存储数据的结构组成的。最简单的LSM-tree由两个部件构成。一个部件常驻内存，称为C0树（或C0），可以为任何方便键值查找的数据结构，另一个部件常驻硬盘之中，称为C1树（或C1），其数据结构与B-tree类似。C1中经常被访问的结点也将会被缓存在内存中。如下图所示：图1：两部件的LSM-tree当插入一条新的数据条目时，首先会向日志文件中写入插入操作的日志，为以后的恢复做准备。然后将根据新条目的索引值将新条目插入到C0中。将新条目插入内存的C0中，不需要任何与硬盘的I/O操作，但内存的存储代价比硬盘的要高上不少，因此当C0的大小达到某一阈值时，内存存储的代价会比硬盘的I/O操作和存储代价还高。故每当C0的大小接近其阈值时，将有一部分的条目从C0滚动合并到硬盘中的C1，以减少C0的大小，降低内存存储数据的代价。C1的结构与B-tree相似，但其结点中的条目是满的，结点的大小为一页，树根之下的所有单页结点合并到地址连续的多页块中。图2：多页块的结构及其结点的结构事实上，除了在多页块中不必从左至右填充结点外，C1与SB-tree[5]几乎相同。如图所示。J-1层结点包含连续的指向J层结点（node1，node2，...nodeK）的指针（P1，P2，...，PK）和分割指针的键（S1，S2，...，SK-1）。J层结点连续存放在多页块的K页中，并且不必按照键的大小排列。如果J层的两个结点存放于同一个多页块中，那这两个结点的键值之间的所有结点也存放在多页块中。M是多页块分割的标记，表示直到下一个M标记或空结点之内的所有后续结点都存放在同一个多页块中。M中包含了多页块开始的硬盘页号和多页块中结点的数量。树根始终是以一个单页存储的。可以看出多页块可用于范围检索，而多页块中结点可用于精确的键值匹配的检索。假设C0也是一种B-tree，设想在滚动合并时，C0和C1都有一个指向相等键值的游标，游标指向下一个将要合并的叶子结点中的条目。从根结点到达这个位置的路径将C1上所有正在进行滚动合并的多页块分成两部分。一部分是游标还未到达的结点，合并时读入清空块（emptying block），另一部分是游标已经过的结点，即滚动合并的结果，合并时写入填充块（filling block）。这样的过程如下：从C1中读入未合并的叶子结点，存储于内存的清空块中；从C0中读取叶子结点，并与清空块中的叶子结点进行合并排序；将合并排序的结果写入填充块中，并从C0中删除用于合并排序的旧叶子结点；不断地重复步骤2和3，当填充块被合并排序的结果填满时，将填充块追加到硬盘的新位置，并从C1中删除用于合并排序的旧叶子结点，当清空块被全部读取完时，再从C1中读入未合并的叶子结点；当C0和C1的所有叶子节点都被读入内存进行合并，并产生新的叶子结点之后，C0和C1的一次滚动合并就结束了。图3：C0与C1之间的滚动合并C0并不将所有的条目都拿来滚动合并。由于C0存储在内存之中，所以C0可以保留最近插入或最常访问的那些数据，以提高访问速率并降低I/O操作的次数。C1的旧多页块可用于崩溃恢复，所以为了不覆盖旧多页块，滚动合并产生的新多页块将被写入硬盘的新空间。一般来说，每次合并之后，会剩下一些不满的没有写入硬盘的填充块，没有填入填充块的叶子结点，这些结点会和它们的目录结点一样暂时缓存在内存中，等待下次滚动合并时，再写