Key-Value 系统LSM 模型实现技术的研究

杨明芽 厦门大学ATR实验室福建厦门 361005

【文章摘要】

随着时代的进步，社交网络的普及，Web2.0 时代的到来，互联网的数据量呈现出爆炸式的增长。传统的数据库模型在高并发性、可扩展性等方面表现不佳，对于一些大数据的应用，传统的数据库模型无法胜任。为了解决这方面的需求，近些年来NoSQL 技术快速的发展。其中Key-Value 存储系统是最常见和简单的NoSQL 系统，本文就将对Key-Value类型的系统实现技术进行研究和讨论。

【关键词】

LSM-Tree ; NoSQL; Key-Value; 存储器层次结构

0 引言

NoSQL 是非关系型数据库的广泛定义，它打破了长久以来关系型数据库与ACID 大一统的局面。NoSQL 数据存储不需要固定的表结构，其存储的数据具有多样性特点。根据数据模型进行分类，长久的NoSQL 有Key-Value 存储系统、面向列的存储系统、面向文档的存储系统和图数据管理系统等等。其中Key-Value 存储系统是最简单的NoSQL 存储系统。本文主要是针对Key-Value 类型的存储系统的实现技术上进行研究和讨论。目前，研究者常用的系统模型有LSM-Tree 模型和COLA模型。其中LSM-Tree 模型是目前的主流方案，本文以LSM-Tree 模型为基础，对实现LSM-Tree 模型的Key-Value 系统进行研究和讨论。

1 LSM-Tree 模型

PO’Neil 等人在1996 年正式提出的LSM 树，而LSM 的思想早期被应用于文件系统的设计和实现上，由于其只是一种简单的设计思想与模式，并常与主流的B树联合使用。LSM 树的核心思想是存储器的层次结构，主要针对于那些修改频率远远高于查询频率的场景，通过牺牲读取性能来获取较高的写性能，将那些频繁修改且耗时的操作置于容量较小但速度较高的内存中进行，而外存则负责数据的存储，通过尽力消除离散读写带来的高额磁盘寻道、旋转时间组成，来从整体上提升整个系统的性能。

通常LSM-Tree 是由两个以上的树形组件数据结构组成的，最简单的LSM-Tree含有两个组件，分别为CO 树和C1 树，这种情况下CO 树为存储在内存的索引数据结构，而C1 树则是存储在磁盘上的索引数据结构。目前，市上主流的存储器有内存、闪存和机械硬盘等，而研究者基本上就是通过这些存储器的组合来进行系统的设计，其中不同类型的存储器，需要对应的数据结构，才能够最大程度的发挥对应存储器的作用。下面的部分将对不同的组件上采取的数据结构的设计进行讨论和分析。

2 CO 树

目前，市上能够比内存更快的就是CPU 内部的Cache，但是这部分的存储器是用户无法涉及的，因此一般的LSM-Tree设计里，内存往往就是CO 树的首选方案，而内存的索引数据的设计是LSM-Tree 系统设计的第一部，也是至关重要的一部。下面，将对三种类型的索引数据结构进行分析和讨论，分别是跳表和数字树。

2.1 跳表

William Pugh 于 1990 年发表了关于跳表的论文，在论文里，他提出了跳表这种新型的数据结构，这种另类的设计和优秀的操作复杂度立刻引起了人们的广泛关注。如今，跳表以其优越的表现成为数据索引领域的一个重要的数据结构之一。跳表是在线性链表的基础上进行改进的，原本的线性链表上的元素添加上多个指针信息，每个指针信息具体的指向哪一层则是由这个指针所在的那一层来决定的：例如某个链表元素的第i 层的指针（0 ≤ i <M, 其中M 为所设置的层数的最高层）指向右侧层数大于等于i 的最近链表元素节点。一般的我们将最右侧不含键信息的节点的键视为+ ∞，而将最左侧的不含键信息的节点的键视为- ∞。且头尾两个节点的指针层数都是M，而这样子就构成一个由指针信息驱动的加速有序链表。上述的是跳表的构造基础，其次对于跳表的每一个节点的指针层数是随机确定的：从第0 层开始构造跳表元素的指针信息，每一层在第i 层的时候，以概率为p的几率判断是否要添加第i+1 层的指针信息，直到M - 1。

2.2 数字树

数字树是一种很优秀的数据结构，尤其对于字符串的存储特别有效。数字树的主要思想是由节点存储以其为根的多个字符串的公共前缀，而从该节点分发出去的不同边存储着不同的下一个字符，同时节点上有一个标志用来标明当前节点是否是一个完整单词。如图1 所示，为数字树的一个实例，例子里包含了i、if、ill、in 和ink 五个单词。

图.1. 数字树

在一颗数字树上查询一个单词，就是顺着根节点，一个节点顺着一个节点查找下去，对于长度为L 的字符串的查询，其时间复杂度为O（L），同样的，数字树上的插入和删除操作其实也是跟查询一样子的过程，因此复杂度依旧也是O（L）。这个复杂度跟散列表最优的情况下的均摊值是一样的，只不过说散列表没有最坏情况的保障，散列表的最坏情况为O（N），而数字树的最坏情况是O（L）。

3 Ci 树

对于Ci 层的组件（i > 0)， 目前基本上是在闪存存储器和机械硬盘上进行研究。下面将会对闪存和硬盘存储上的存储数据结构进行讨论。

3.1 机械硬盘

传统的机械硬盘有着价格低廉，容量巨大的明显优势，但是在读写延迟上是一个严重的硬伤。然后传统的硬盘在连续的读写的时候却有着优越的性能，因此在硬盘上设计的结构经常的是要考虑着尽量进行的是连续的读写操作，而去避免随机读写的操作。

在硬盘上很流行的存储数据结构是B 树及其变种，自从1972 年B 树被发明以来，B 树就成了文件系统和数据库的主要存储结构。而B 树本质上是是一颗多叉树，在实际的应用中，每个B 树的节点数目一般会设置到一个很大的值，至少一个B 树节点会覆盖一个磁盘块，当然实际应用时，会设置为更大，因为这样子可以充分的利用出磁盘的连续读写的性能，又可以降低整棵B 树的高度，从而又可以加速B 树的索引速度。

对于B 树，其索引的性能还是不错的，但是B 树的插入过程就比较麻烦了。若想要在一颗B 树上进行插入的操作，首先需要对待插入的键进行索引，在找到插入的位置之后，若待插入的节点的键数量没有达到限制的数量的时候，则直接插入，但是若达到了限制之后，就必须对B树的节点进行分裂并且要递归向上插入，使得符合B 树的条件为止。假若说B 树的节点存储的键数量可以动态变化的话，分裂节点对B 树性能影响不大，但是在实际设计的时候，往往为了取址和访问的方便，会将节点的键数量设为固定的，因此插入引起的分裂对于B 树的影响一般会比较大。然而，目前的对于磁盘主流的索引数据结构依旧是B 树，当然，有很多的研究者针对B 树的不足提出了B 树的一些变种版本，以提高数据索引插入的性能。

3.2 闪存

闪存，是一种电子式可清除程序化只读存储器的形式，运行在操作中被多次擦或写得存储器，具有低延迟、体积小、质量轻、无噪声，抗震动等优点。闪存有两种主要的类型，一种是NOR 型Flash，另一种是NAND 型Flash，Nand 型的价格相比于Nor 型的闪存，有着较低的芯片成本、较大的容量和较高的存储密度，因此更加适合于大规模的存储。Nand 型闪存在写入的时候需要在空白页进行，若是非空白的，则需要先进行擦除，而擦除是延迟比较大的，且擦除是以块为单位进行的，其次对于每一块都有着擦除的次数限制。因此研究者在设计数据结构的时候往往是需要着重考虑这些因素。

由于闪存的写延迟、擦除延迟和擦除次数限制等因素，对于闪存的合适的数据结构一般是日志型的存储结构，即对于任何插入的数据都是顺序的写入闪存里，而更新或者闪存等操作也是顺序的写入闪存里，这样子的结构设计可以使得所有的操作均衡的分布于整个的闪存中，从而提高闪存的稳定性和延迟使用的寿命。由于是顺序写入闪存里，因此必然的元数据与数据在闪存的设计里是分开的，则既要能够通过元数据的信息去找到对应的数据，也要能够通过数据去找到对应的元数据。而元数据存储既可以存储在内存，也可以存放在闪存里面，一般的设计是先存放在内存，而到一定的时间之后再写入闪存，以避免对于闪存的频繁修改。除了上述的存储结构的特点之外，闪存的设计里还需要一个必要的设计：闪存需要一个垃圾回收的机制，即对于闪存里的垃圾数据进行回收，从而腾出空余的空间来存储新的数据。

在闪存的索引结构的设计里头，数据的查询是先通过查找元数据，然后再通过元数据，找到数据的存储位置，一般的，元数据是先存放在内存，因此在内存进行索引的速度是很快的，而在获得数据的位置之后，就是要进行闪存的随机读的操作。由于闪存随机读的性能比较好，因此日志型结构在闪存里可以获取到较好的索引性能。插入和删除的操作都是以顺序写的方式进行的，从而避免了擦除延迟的影响。

4 总结