第7章 闪存数据库索引

大数据之门

《闪存数据库概念与技术》

厦门大学数据库实验室  林子雨  编著

本网页是第7章内容,全书内容请点击这里访问本书官网,官网提供本书整本电子书PDF下载

第7章 闪存数据库索引

索引是数据库系统组织管理数据的一种重要方式,可以有效提升数据库查询的性能。当前主流的商业化数据库管理系统,大都采用了B-树及其变种索引结构,但是,如果把这些索引结构直接移植到闪存数据库上,将无法获得好的性能,因为,闪存具有和传统磁盘截然不同的物理特性。闪存采用异地更新的方式,每个B-树中节点的更新,都会引起闪存写操作,而且,某个节点的更新可能会不断传播扩散到其他节点,引起其他节点的更新,从而导致更多的闪存写操作。因此,必须针对闪存特性设计相应的索引结构。

本章介绍修改索引模块的相关代表性研究,包括基于日志的B-树索引[WuCK03][LeeL10]、B+-树索引[OnHLX09][WuKC07]和自适应B+-树索引、FD-树[LiHLY09]以及LA-树[AgrawalGSDS09]等。

7.1    基于日志的B-树索引

7.1.1      B-树

B-树是一种平衡的多路查找树,主要用于文件的索引。B-树结构特性:一棵m阶B-树,或为空树,或为满足下列特性的m叉树(m≥3):

(1)根节点只有1个,键(key)的个数的范围是[1,m-1],分支数量的范围是[2,m];

(2)除了根节点以外的所有非叶子节点,每个节点包含分支数范围是[[m/2],m],即键的个数范围是[[m/2]-1,m-1],其中,[m/2]表示取大于m/2的最小整数;

(3)非叶子节点是由叶子节点分裂而来的,所以,叶子节点的键的个数也满足[[m/2]-1,m-1];

(4)所有的非叶子节点包含信息:(nA0K1A1K2A2,……,KnAn),其中,Ki为键,Ai为指向子树根节点的指针,并且Ai-1所指向子树中的键均小于Ki,而Ai所指的键均大于Ki(i=1,2,……,n)。n+1表示B-树的阶,n表示键的个数;

(5)所有叶子节点都在同一层,并且指针域为空。

图[B-tree]给出了一棵3-阶B-树的实例,从中可以看出,被索引的键值分散在所有节点中,可以为每个节点中的每个键值增加一个指向该键值所对应的数据记录的指针,从而可以在B-树索引中找到某个键值以后,根据该指针找到对应的数据记录。由此也可以看出,在数据库或文件系统中,B-树索引和被其索引的数据记录是分开存放的。

图[B-tree]一棵3-阶B-树的实例

图[B-tree] 一棵3-阶B-树的实例

B-树中的查找、插入和删除操作的基本过程如下:

  • 查找:从根节点出发,自顶向下遍历,当到达一个节点时,如果该节点中不存在查找值,就根据查找值和键值的关系确定一棵子树,继续到子树中查找,直到找到为止。
  • 插入:首先,选择一个合适的叶子节点u,在u中添加要插入的键值,如果u中键的个数不超过m-1个,则插入成功。否则,就需要把u分裂为两个节点,并把中间的一个键拿出来插到节点u的父节点中去。父节点也可能是满的,就需要再分裂,继续再往上插。在最坏的情况下,这个过程可能一直传递到根节点,如果需要分裂根节点,由于根节点是没有父节点的,这时就需要建立一个新的根节点。由此可以看出,插入操作可能导致B-树朝着根节点的方向生长。
  • 删除:B-树中的删除操作与插入操作类似,但要稍微复杂些。如果删除的键不在叶子节点层,那么,就需要先把此键与它在B-树里的后继对换位置,然后再删除该键。如果删除的键在叶子节点层,则把它从它所在的节点里去掉,这可能导致此节点所包含的键的个数小于[m/2]-1。这种情况下,考察该节点的左或右兄弟,从兄弟节点移动若干个键到该节点中来,使两个节点所含的键的个数基本相同。如果兄弟节点的键个数也很少,刚好等于[m/2]-1时,这个移动就不能进行。在这种情况下,要把将删除键所在的节点、它的兄弟节点以及它们的父节点中的一个键,合并为一个节点。

可以看出,B-树中进行插入和删除操作,都可能会引起节点的分裂或合并。

7.1.2      闪存中基于日志的B-树索引

大多数主流的基于磁盘的DBMS产品都采用了B-树作为索引结构,因为B-树的特点就是适合在磁盘等存储设备上组织动态查找表。采用B-树索引时,B-树索引结构自身和被其索引的数据,是分开存储的,并且都保存在磁盘上。

闪存的特性与磁盘具有很大的区别,当前的DBMS中所用的索引都是针对磁盘设备设计的,如果直接应用到采用FTL机制的闪存设备上,不仅会导致数据库性能的恶化,也会降低闪存设备的可靠性(不合理的频繁擦除操作会让闪存变得不稳定),因此,索引机制就会成为数据库性能的瓶颈。比如,在B-树中,记录插入、记录删除和B-树重组织,都会引起相关的写操作。如图所示,假设现在要在这棵B-树中插入新的键值22、49、83、120、168和260,这些键值会被分别插入到节点D、E、F、H、I和J中,因此,一共有六个节点的内容发生了更新。由于B-树索引和被其索引的数据记录是分开存放的,因此,这里只关注B-树索引。假设每个B-树节点都单独存放在一个页中,那么,上述六次更新操作,修改了六个B-树节点,因此,就需要对六个页进行更新。在一些情形下,如果因为插入操作导致节点的分裂,则会涉及更多的节点更新,那么就需要更新更多的页。

图[B-tree-insert]在一棵B-树中插入新的键值

图[B-tree-insert] 在一棵B-树中插入新的键值

由于闪存采用异地更新方式,就需要把那些没有发生变化的数据和相关节点中的树指针,也一起复制到新的闪存页中,这会导致大量的数据复制操作。而且B-树常常会在同一个位置发生频繁更新,这进一步恶化了闪存的性能,因为,这会导致很多代价高昂的擦除操作。FTL机制虽然可以隐藏闪存特性,但是,其核心功能是提供逻辑地址到物理地址的映射,当B-树索引对某些逻辑地址空间进行频繁更新时,FTL机制也无法避免闪存整体性能的恶化[LeeL10]。

因此,文献[WuCK03]提出了面向闪存的、基于日志的B-树索引,该工作的目的就在于尽量减少索引结构造成的冗余的闪存写入操作,从而改进系统性能并且降低电能消耗。基于日志的B-树索引方法不仅可以用于DBMS的索引,也可以应用在其他采用B-树索引的应用系统中。

在闪存上直接建立B-树索引,面临的一个棘手的问题就是级联更新[Xiang09]。闪存通常采用异地更新的方式,当B-树中的某个节点被更新时,并非使用新版本的数据来覆盖旧版本的数据,而是把新版本的数据写入到一个新的空闲闪存页中,然后,修改上层节点指向该节点的指针,让它指向最新版本的数据。但是,当上层节点指针发生修改时,又会导致再上层节点的指针的修改,依此类推,直到最终修改了根节点的指针,也就是说,每次某个节点的更新操作,都会导致从该节点到根节点的路径上的所有节点都发生更新,这就是“级联更新”。可以看出,级联更新会引发多次闪存写操作,代价较大。针对级联更新的问题,Kang等人[KangJKK07]提出了的一种可行的策略,即µ-树索引,其核心思想是:把B-树中属于同一条路径上的所有节点都存储在闪存的同一个页中,这样,每次更新这条路径上的某个节点时,就只需要写入一个闪存页,从而在一定程度上避免了节点的级联更新问题,同时也减少了索引的更新代价。但是,B-树中存在很多条路径,因此,这种方法的存储空间开销较大,管理起来也比较复杂。

图[BFTL]给出了一种基于日志的B-树索引方法的体系架构——BFTL[WuKC03],该方法可以被封装成一个单独的、可插拔的模块,因为该模块处于FTL层之上,并且基于B-树索引结构,因此被命名为BFTL。BFTL模块可以为那些采用B-树索引的应用提供服务,因此,也可以用在现有的采用B-树作为索引结构的DBMS产品中,改善DBMS在闪存平台上的性能。如图[BFTL]所示,上层应用提出的数据访问请求,会被BFTL处理和转换后发送到FTL。BFTL包含了一个保留缓冲区和一个节点转换表。保留缓冲区是一个为脏记录设置的缓冲区空间,可以避免在记录更新时引起B-树索引结构对闪存的频繁写操作,减小了闪存开销。当上层应用执行插入、删除或修改记录的操作时,新生成的记录会被保存到BFTL的保留缓冲区,由于保留缓冲区只能容纳一定数量的记录,因此,必须及时刷新到闪存中,同时更新节点转换表。为了把保留缓冲区中的脏记录刷新到闪存中,BFTL为每个脏记录构建了相应的索引单元。索引单元的大小比一个闪存页要小很多,如果每个索引单元都分开存储,会浪费大量的闪存空间。因此,作者设计了提交策略(Commit Policy),可以把许多索引单元会智能地封装成一些页,从而减少物理页的数量,减低了闪存读写开销。但是,封装操作会使得属于同一个B-树节点的多个索引单元被分散存储到不同的闪存页中。BFTL中的节点转换表的作用,就是帮助BFTL识别来自同一个B-树节点的索引单元,如图[BFTL-node-translation-table]所示,转换表中记录了B-树中每个节点所对应的页的逻辑页号,在执行B-树的查询时,只需要查找节点转换表就可以直接查询到节点被存储到的所有页面的逻辑页号,并通过FTL机制找到相应的物理页,依次读取每个闪存物理页就可以获得相应的B-树节点,不需要到闪存中进行遍历,从而提高了闪存数据库B-树索引的性能。

图[BFTL-node-translation-table]BFTL的节点转换表

图[BFTL-node-translation-table] BFTL的节点转换表

图[BFTL-node-translation-table](b)给出了一个可能的节点转换表实例,从中可以看出,每个B-树节点都可以包含若干个索引单元,这些索引单元可能来自不同的页,这些页的逻辑页号被组织成一个链表,被链接到与该节点对应的转换表条目中,比如节点B的索引单元链表中包含了42、34和53三个链表元素,与节点B对应的转换表条目就保存一个指向该链表的指针。当访问某个B-树节点时,通过扫描各个链表中所保存的逻辑页号,就可以获得属于该节点的所有索引单元。例如,为了构建图[BFTL-node-translation-table](a)中的关于节点C的逻辑视图,就可以通过扫描节点转换表,获得逻辑页号23和100,并通过FTL机制找到相应的物理闪存页,然后读取相应的索引单元,从而最终构建得到节点C的逻辑视图。由此也可以看出,一个逻辑页中可以包含若干个来自不同B-树节点的索引单元,比如,逻辑页号为100的逻辑页,包含了来自B-树节点C和I的索引单元。

BFTL的提交策略在设计时追求的另一个目标就是,让属于同一个B-树节点的多个索引单元被分散存储到尽可能少量的闪存页中,从而提高索引单元的访问效率。从以上论述可以看出,BFTL通过采用缓冲区和提交策略,有效减少了记录更新引起的B-树索引结构对闪存的读写开销。

图[BFTL]基于日志的B-树索引方法的体系架构

图[BFTL] 基于日志的B-树索引方法的体系架构

在BFTL方法中,读取记录的过程如下:

  • 一个应用发起一个读取某个记录的请求;
  • 如果能够从保留缓冲区中找到这个记录,就把这个记录返回给应用;
  • 否则,在节点转换表中,从根节点开始遍历整个B-树,来搜索这个记录
  • 如果找到这个记录,就把这个记录返回给应用。

BFTL方法通过在应用层和FTL之间增加一个B-树转换层,有效降低了闪存数据库中建立B-树索引时存在的级联更新问题,减少了由于B-树节点更新而引起的大量闪存写入问题。但是,基于日志的B-树索引方法也存在一些缺陷,具体如下:

(1)虽然BFTL中的节点转换表可以记录B-树节点及其对应的闪存页,但是,在查询某个B-树节点时,由于一个B-树中的节点可能被分散存储到不同的闪存页中,因此,为了访问一个节点,就需要进行多次读操作来访问多个闪存页,而且,由于闪存页中的索引记录对应的键值不是按照顺序存储的,无法采用二分法查找,需要遍历闪存页才能找到对应的索引记录。

(2)需要使用额外的开销来管理节点转换表,尤其是保留缓冲区中内容变化比较频繁时,需要更多的节点转换表管理维护开销。此外,对闪存数据库的B-树索引进行查询操作时,读取转换表对于提高查询效率的作用并不是很大。

(3)BFTL中的缓冲区也仅仅起到了缓冲的作用,当缓冲区被索引单元填满时,仍然需要把缓冲区中所有的索引单元都刷新写入到闪存中。

(4)保留缓冲区中可能会包含冗余的数据,这也增加了刷新到闪存时的开销。比如,某索引记录先执行了插入操作,然后又执行了删除操作,此时,该索引记录在B-树中并不存在,因此,与插入和删除相对应的两个索引单元不需要写入到闪存,而BFTL并无法避免这种冗余数据。

(5)没有对所有可用的各类闪存设备和负载类型进行优化。对于板上闪存芯片而言,或者在写负载比较集中时,该方法会表现出较好的性能。但是,当负载类型是读写类型时,或者应用在一个CF卡类型的闪存存储设备上时,该方法的性能就很差。

为了克服上面的第四个缺陷,文献[NathK07]提出了采用自适应B+-树索引的FlashDB(在下文将会介绍)。为了克服上面的前三个缺陷,文献[LeeL10]提出了针对BFTL的改进方法——IBSF,它的核心思想是:(1)把所有属于同一个B-树节点的索引单元都写入到同一个页中,因此,IBSF就不再需要节点转换表,也就省去了节点转换表的管理维护开销;(2)删除了保留缓冲区中冗余的索引单元,这就可以有效减少刷新到闪存时所涉及的写操作的数量。和BFTL一样,IBSF也是一个位于存储层和应用层之间的一个软件模块,因此,也可以以可插拔的方式应用于DBMS中。

7.2   B+-树索引

7.2.1      B+-树

B-树索引在随机查询方面具备较好的性能,但是,无法提供较好的顺序查询性能,而作为B-树的变种,B+-树则既可以具备较好的随机查询性能,也可以提供较好的顺序查找性能,因为,在B+-树中,叶子节点是连接到一起的,很容易实现顺序查询。

B+-树是在B树基础上改进得到的动态数据结构,可以很好地适应应用结构的变化,不仅易于管理,而且具有较高的效率,通常用于数据库和操作系统的文件系统中。如图[B+-tree]所示,在B+-树中包含两类节点,即叶子节点和内部节点(非叶子节点)。所有的内部节点可以看成是索引部分,起到指引的作用,用来定位找到某个叶子节点。每个内部节点的元素充当分开它的子树的分离值。例如,在图[B+-tree]中,对于内部节点x而言,有三个子节点(或子树),那么x的两个分离值是14和42。在x的最左子树中所有的值都小于14,在中间子树中所有的值都在 14和 42之间,而在最右子树中所有的值都大于42。叶子节点中包含了记录的键的值、指向记录的指针和指向下一个叶子节点的指针,叶子节点本身按照键的大小自小而大顺序链接。叶子节点中包含了指向记录的指针,记录会被保存到磁盘的其他区域,因此,B+-树索引的存储和被其索引的记录的存储是分离的。B+-树可以支持顺序查找和随机查找。在进行顺序查找时,只需要从相应的叶子节点出发(比如从图[B+-tree]中sqt指针指向的叶子节点出发),沿着每个叶子节点中包含的指向下一个叶子节点的指针,逐个进行查找。在进行随机查找时,需要从根节点(图[B+-tree]中root指针指向的节点)出发,沿着内部节点中包含的指针,一步步定位至下一层节点,直至到达叶子节点。

图[B+-tree]一棵3-阶B+-树实例

图[B+-tree] 一棵3-阶B+-树实例

B+-树的查询、插入和删除操作的基本过程如下:

  • 查询:B+-树的所有叶子节点包含了所有记录的键,因此,要查询一个记录是否存在,只需要看是否能够最终在叶节点中找到待查询的记录的键。
  • 插入:插入一个数据d时,首先需要找到d所属的叶子节点,如果叶子节点有多余的存储空间,就直接把d插入到该叶子节点,否则,就将该叶子节点进行分裂,由一个叶子节点分裂成两个叶子节点,并重新分配相关数据。如果根节点发生了分裂,由于一棵树中只能有一个根节点,则会产生一个新的根节点,树的高度增加1。
  • 删除:删除一个数据d时,同样需要首先找到d所属的叶子节点,然后删除该叶子节点。在删除该叶子节点以后,如果该叶子节点包含的键的数量过少,则会发生相邻叶子节点的合并或者在相邻叶子节点之间重新分配数据。

7.2.2      闪存中的B+-树索引

通常情况下,B+-树节点会保存在辅助存储介质上,同时,为了避免重复从辅助存储介质上读取数据,一般会把最近访问的节点缓存在内存中,这样,在某段时间内,节点的更新就可以一起被提交。但是,内存容量是有限的,只能缓存少量节点,因此,被缓存的节点通常在接收到足够多的请求一起提交之前就会被交换出内存。因而,仅仅依赖于这样一个缓存机制不大可能节省许多写操作。

文献[OnHLX09]提出了惰性更新B+-树来高效地利用内存资源。在这种方法中,内存被分成两个部分:一部分用来缓存被访问的B+-树节点的相应的页面(被称为页缓存),另一部分用来缓存更新请求(被称为惰性更新池)。

while a request R arriving do

if R is an update request then

if lazy-update pool is full then

Use a commit policy to select a group of requests as victims;

Commit victims to the B+-tree in bulk;

Buffer R in the lazy-update pool;

Use cancel-out policy to eliminate redundant requests;

else

/*R is aquery request*/

Searching over lazy-update pool to get query result Q1;

Apply traditional algorithm on B+-tree to get query result Q2;

Merge Q1 and Q2 to get the final query result;

 

算法[lazy-update-B-tree]描述了惰性更新B+-树方法。当一个更新请求到达时,并非立即提交到B+-树,而是临时保存到惰性更新池中。在惰性更新池内,如果新到达的请求与池中已经存在的更新请求具有相同的键值但是具有不同的动作类型,就会采用一定的策略来消除冗余。此外,更新请求会被组织成不同的分组,每个更新相同叶子节点的请求构成一个分组。当惰性更新池无法容纳更多更新请求时,就会产生一个提交操作,选择其中一个组作为牺牲品,提交到B+-树中,然后释放空间。对于查询而言,除了搜索惰性更新B+-树以外,还需要搜索惰性更新池。

采用惰性更新池可以节省写操作数量。考虑一个更新顺序{U1,U2,U3,U4},其中,U1U3将会插入到叶子节点a中,U2U4将会插入到叶子节点b中。在传统的方法下,两个叶子节点分别会更新两次。在惰性更新B+-树中,这些更新请求将会被临时存储在惰性更新池中,这样做可以带来两个方面的收益:第一,被缓存的更新请求可以在后来某个时刻以批量的方式提交到B+-树中,因此,可以在多个更新请求之间分摊定位被更新的叶子节点的读取代价;第二,更新顺序可以被重新排序成不同的分组,比如,把{U1,U3}分成一组,把{U2,U4}分成一组。然后,通过基于分组的提交,叶子节点ab都只需要被更新一次。也就是说,可以节省一半的写操作。

对于惰性更新B+-树而言,当一个新的更新请求到达并且惰性更新池已满时,应该采取一个提交策略,来选择一组更新请求来提交,从而为新的请求腾出空间。对于惰性更新B+-树而言,一个高效的提交策略是很重要的,因为它对更新分组的效果的影响很大。比较理想的情况是,一个最优的提交策略应该总是选择满足下面条件的分组:这些分组没有更多后续的更新请求可以提交。这样做可以导致写操作数量的最小化。但是,这在实践中是不可能实现的,原因包括两个方面:第一,没有后续更新请求的分组并不是总是存在的;第二,后续的更新请求是无法预先知道的。因此,必须设计一个在线提交策略,使得它对更新分组的影响和写代价都达到最小化。可以考虑采用两种启发式在线提交策略:

(1)最大分组策略:对于一个新到达的更新请求而言,如果惰性更新池中已经存在一个它可以加入的分组,那么,我们就说发生了“命中”。为了提高命中率,就应该在惰性更新池中保存尽可能多的分组。因此,把最大分组驱逐出惰性更新池,相对于驱逐许多较小分组而言,可以获得更多的收益。而且,由于较大的分组包含了更多的更新请求,那么分摊到每个更新请求上面的代价就会比较小。

         (2)基于代价的策略:最大分组策略是为了最大化命中率,基于代价的策略则目的在于使得驱逐分组引起的代价最小化。

7.2.3      自适应B+-树索引

7.2.3.1       FlashDB概述

文献[NathK07]提出了一个针对闪存的DBMS——FlashDB,它是一个为传感器网络而优化的、自适应的数据库。FlashDB使用了一个新的、自适应的B+-树索引,可以动态地根据负载和底层的存储设备来调整它的树结构。在这种自适应的B+-树中,包含两种类型的节点,即日志节点和磁盘节点,可以满足不同的性能要求。在不同类型的负载下,为了取得最好的性能,一个树节点可以在日志节点和磁盘节点之间进行切换,作者把这个切换问题建模成一个“双状态”任务系统,并提出了高效的在线算法。

如图[FlashDB]所示,FlashDB包括两大功能组件:数据库管理系统(DBMS)和存储管理器(Storage Manager)。DBMS组件负责实现数据库管理的各项功能,比如查询编译和索引;存储管理器组件负责实现基于闪存的高效存储功能,比如数据缓冲区和垃圾回收。索引管理器(Index Manager)是DBMS组件中的核心模块,它负责实现自适应的B+-树。因此,作者在文中重点介绍了存储管理器和索引管理器。

存储管理器组件中各个模块的功能如下:

  • 逻辑存储(Logical Storage):负责实现逻辑扇区地址到物理闪存地址的映射。
  • 节点转换表(Node Translation Table: NTT):记录了自适应B+-树中的逻辑节点的类型信息(日志节点还是磁盘节点)和物理地址信息。
  • 缓冲区:专门为日志节点设置,当日志节点发生了更新时,首先被记录到缓冲区中。
  • 垃圾回收:回收闪存中的无效页,执行擦除操作,得到一些可用的空闲块。

索引管理器组件中各个模块的功能如下:

  • 设备配置(Device Configuration):负责获得底层设备的信息,因为设备类型多种多样(比如闪存芯片、SD卡、CF卡、固态盘等),不同设备类型需要采用不同的算法配置。
  • 节点切换算法(Node Switch Algorithm): 负责执行节点模式的切换,即在日志节点和磁盘节点这两种模式之间切换。
  • 节点尺寸调整器(Node Size Tuner):负责根据不同的设备来调整节点的大小,从而获得最佳性能。

 图[FlashDB]FlashDB的体系架构

图[FlashDB] FlashDB的体系架构

 

7.2.3.2     自适应B+-树

FlashDB的最重要创新点就是自适应B+-树。文献[NathK07]分析了两种不同类型的B+-树,即磁盘B+-树和日志B+-树:

(1)磁盘B+-树:主要是面向磁盘设备,自然也就可以用在采用FTL的闪存设备上(可以看成是一个虚拟的磁盘)。根据B+-树的节点大小,每个节点会被保存到若干个连续的闪存页中。读取节点时,只要找到闪存中相应的页面读取即可。更新一个节点时,需要首先把相应的闪存页面读取到RAM中,进行更新,然后写回到闪存中。磁盘B+-树的优点是:兼容性较好,可以不作任何修改直接应用到采用了FTL的闪存设备上。它的缺点也很明显,就是需要高昂的更新代价。

(2)日志B+-树:基本思想是,把索引组织成事务日志的形式。当对一个树中的节点进行更新,首先把更新作为一个日志条目写入到缓冲区中,等缓冲区的日志可以写满一个闪存页时,再一次性把缓冲区中的日志条目全部写入到闪存中。很显然,日志B+-树的更新代价要比磁盘B+-树小很多,但是,读操作的代价较高。为了获得最新版本的数据,就必须对分散在不同闪存页中的日志条目进行扫描,然后和之前版本的旧数据进行合并更新得到最新版本的当前数据。

通过进一步分析,该文的作者发现,对于不同的负载类型和设备类型,同一棵B+-树中的不同节点可以使用不同的B+-树节点类型(磁盘B+-树节点和日志B+-树节点),从而获得最优性能。比如,对于写操作集中的负载以及那些写操作代价明显高于读操作代价的设备(比如SD卡)而言,就比较适合采用日志节点,因为,日志B+-树节点可以减少闪存的写入次数,虽然这会增加闪存读操作的次数,但是,减少了总体读写代价;而对于读操作比较集中的节点,则适合设置为磁盘节点。如果使用SD卡或者写操作负载比较集中,采用日志B+-树节点的效率要比采用磁盘B+-树节点的效率高80%。但是,如果负载类型或者设备类型发生了变化,结果就可能截然不同,前者效率甚至可能不如后者。比如,CF卡的读写代价是相当的,如果采用CF卡,即使仍然是写负载比较集中,采用磁盘B+-树节点的效率还是要比日志B+-树节点的效率高32%,因为,后者减少写入次数产生的收益可能小于该机制自身所增加的读取操作的代价。实验结果显示,当写操作次数大于读操作次数,并且每次写操作代价都是读操作代价的5倍以上时,采用日志B+-树节点的效率更高,否则,应该选用磁盘B+-树节点。

此外,负载类型和设备类型都可能会随着时间动态变化,因此,需要动态调整B+-树中节点的类型。一般而言,数据库负载类型和设备类型都无法提前得知,而且,一个数据库上可能会同时接收到不同类型的工作负载,工作负载在不同时间点的模式也会发生变化,比如,某个时刻读操作比较集中的负载,到了另一个时刻可能就变成写操作集中的负载。因此,如果采用固定的B+-树节点类型,就无法适应不断变化的负载类型和设备类型,会严重影响到数据库的总体性能。

实际上,这种B+-树节点类型的动态调整机制,不仅对于固定负载类型和设备类型而言,可以获得较好的数据库性能,而且对于固定的负载和设备特性而言,同样可以获得较好的性能。比如,数据库负载是比较固定的写操作集中的负载,闪存的写代价远高于读代价。对于这种情形,按照前面的分析,很自然地应该采用日志B+-树节点。但是,这里实际上还应该考虑另外一个因素,那就是每次写操作都需要通过一系列的查询(读操作)来确定插入点的位置,因此,这个过程会伴随着大量的读操作。由于查询操作都是从根节点开始的,因此,根节点附近的节点会被频繁地读取,这些节点就不适合采用日志B+-树节点,而更应该采用磁盘B+-树节点。综上所述,如果能够对每个树节点都进行独立的、动态的节点类型调整,就可以让数据库获得最优的整体性能。

         自适应B+-树节点类型切换问题,可以被建模成一个“双状态”任务系统[BlackS89]。如图[FlashDB-two-task-system]所示,一个节点可以有两种模式,即磁盘B+-树节点模式和日志B+-树节点模式。一个读操作R或者写操作W,可以采用任何模式的节点来为它们提供服务,但是,不同节点提供服务的代价是不同的。一个节点可以从一种模式切换到另一种模式,但是,切换操作需要一定的代价。节点模式切换问题,就是使用一种在线算法,可以让节点动态改变模式,并且使得节点切换和服务于读写操作的总代价达到最小化。这个问题就是一种经典的双状态任务系统的实例。

图[FlashDB-two-task-system]在两种B+-树节点模式之间的切换

图[FlashDB-two-task-system] 在两种B+-树节点模式之间的切换

节点模式动态调整算法,需要完成B+-树节点在不同模式之间的切换:

  • 当节点从日志模式切换到磁盘模式时,需要读取这个节点相关的日志内容,构造得到逻辑节点,然后作为磁盘模式写回闪存。
  • 当节点从磁盘模式转换到日志模式时,就需要把逻辑节点改写成一系列的日志记录,存放在日志缓冲区中。

根据前面的分析,对于写操作集中的负载,比较适合采用日志节点,而对于读操作集中的负载,则比较适合采用磁盘节点。当负载类型发生变化时,为了获得最优性能,应该进行节点模式切换。但是,这里必须注意一个问题,节点转换会包含一定的开销,有时候这种开销甚至会大于转换操作带来的收益,对于这种“得不偿失”的转换操作应该尽量给予避免,因此,必须设计合理的节点模式切换算法。下面算法描述了节点模式切换的过程。

算法:节点模式切换

(下面的算法过程会针对每个B+-树节点都执行一遍)

1. S←0; //当迁移到当前的模式时,就初始化S

2. 对于每个读操作O

假设c1是当前模式下服务操作O的代价,c2是其他模式下服务操作O的代价;

SS+(c1c2);

3. 假设M1M2是在两种模式之间进行转换的代价,如果SM1+M2,那么就切换到其他模式;

 

7.2.3.3       B+-树节点大小的选择

7.2.3.3.1        B+-树节点大小对性能的影响

对于数据库而言,不仅B+-树节点类型是影响其性能的一个因素,B+-树节点大小也会对性能产生影响。采用较大的B+-树节点的优势是,可以减小树的高度,从而缩短了从根节点到叶子节点的路径长度,加快了查找过程。但是,较大的B+-树节点的劣势也同样明显,它会增加单个节点存储的数据,增加了每次读取闪存的开销。因此,必须选择一个比较合适的B+-树节点。在理论上,一个B+-树节点可以使用任意数量的页,但是,实际上,通过一些实验测试还是可以确定一个比较合理的大小取值的。对于磁盘数据库而言,Gray[GrayG97]通过研究显示,采用16KB的节点大小可以获得较好的性能。对于闪存数据库而言,B+-树节点大小的最优值可以采用下面的方法加以确定。

崔斌等人[CuiLC10]分别采用固态盘、磁盘和闪存模拟器等存储介质,对B+-树节点大小的变化进行了性能影响测试。测试环境为Fedora10,并使用闪存模拟器nandsim模拟了512MB的闪存,闪存页的大小为2KB,块大小为128KB,读、写和擦除操作的时间分别为25us、200us和2ms。测试对象是一棵包含20万条数据的B+-树,并采用2万条数据对这棵B+-树进行顺序或随机的插入和查询操作。

图[cuibin-test-01]B+-树节点大小对插入操作性能的影响

图[cuibin-test-01] B+-树节点大小对插入操作性能的影响

测试之前需要关闭缓存,从而确保所有的数据操作都是针对外存进行的。图[cuibin-test-01]给出了在磁盘、固态盘和闪存模拟器上采用不同的B+-树节点大小时对插入操作性能的影响。从图中可以看出,磁盘和固态盘上面的性能变化趋势比较一致,插入操作所需要的时间,随着节点大小的增加,表现出先减少后增加的特点,当节点大小为4KB时,插入时间达到最小值。这个测试结果比较符合前面的理论分析,因为,采用较大的B+-树节点可以减小树的高度,缩短路径长度,从而加快了插入操作过程。但是,节点增大,也意味着它会增加单个节点存储的数据,增加了每次更新操作的开销,因此,节点大小超过一定程度后,节点越大,插入时间反而会不断增加。图[cuibin-test-01]也表明了另外一个重要的结果,即在闪存模拟器上面,插入时间会随着节点大小的增加表现出单调增加的趋势。因此,对于闪存模拟器而言,最优的树节点大小要比磁盘小得多。

         图[cuibin-test-02]给出了B+-树节点大小对查询操作性能的影响。在实验中使用2万个顺序查询对B+-树进行性能测试,从图中可以看出,在固态盘、磁盘和闪存模拟器上的测试结果都表现出了大致相同的规律。采用较大的B+-树节点可以减小树的高度,从而缩短了从根节点到叶子节点的路径长度,加快了查找过程,因此,三者的查找时间都随着节点大小的增加而不断减小。但是,查找时间减小到一定程度以后,又开始表现出上升的趋势,也就是说,当节点大小在16KB附近时,查询时间达到了最小值,此后又开始不断增加。这是因为,较大的B+-树节点,会增加单个节点存储的数据,增加了每次读取节点中的数据的开销。

图[cuibin-test-02]B+-树节点大小对查询操作性能的影响

图[cuibin-test-02] B+-树节点大小对查询操作性能的影响

 

7.2.3.3.2        FlashDB中确定B+-树节点大小的方法

FlashDB中B+-树节点的大小是通过以下方法确定的。假设一个B+-树索引有N个数据单元,一个B+-树节点大小为NodeSize,每个节点可以包含EntiresPerNode个索引条目,那么,这棵树的高度就是:

Height=log2 ( N ) / log2 ( EntriesPerNode)

首先,来定义一个节点的“有用性”,它被定义为这个节点可以把一个查询指引到距离目标叶子节点多近的距离,计算公式如下:

NodeUtility = log2(EntriesPerNode)

例如,如果每个索引条目(index entry)是16个字节,那么,对于一个只有七成满的索引页而言,就会包含44个索引条目。这样一个节点的有用性就是5.5(即log244),只有一个48KB节点的有用性的一半。因此,从直观上看,节点越大,树的高度越小,到达底层叶子节点所需要访问的节点数目就越少。

         然后,再来考虑一下访问一个节点的代价。假设所有的B+-树操作都是写操作,并且所有的节点都是磁盘B+-树节点。一个写操作需要读取从根节点到叶子节点的路径上面的所有节点,然后至少需要写入叶子节点,当叶子节点的更新传播到其他节点时,则还需要写入更多的其他非叶子节点。因此,对于一个单个节点而言,分摊后的访问代价就是:

公式COST

最后,就可以计算得到一个节点的“有用性/代价”的值,用来作为性能评测指标。图[FlashDB-utility-cost]显示了针对三星闪存产品进行的性能测试,这里的B+-树具有30000个16字节的索引条目,每个索引节点是7成满。从图中可以看出,对于闪存芯片而言,节点越小,性能越好(即有用性/代价的值越大);对于CF卡而言,当节点大小为4KB时,可以获得最好的性能。

 图[FlashDB-utility-cost]采用不同的B+-树节点大小时有用性除以代价的值

图[FlashDB-utility-cost] 采用不同的B+-树节点大小时,有用性/代价的值

因此,对于不同的设备而言,需要采用不同的B+-树节点大小,以期获得最好的性能。比较好的做法是,让B+-树节点大小随着设备特性的不同而自动调整其大小。

7.3   FD-树

FD-树[LiHLY09]的设计目标是最小化小数据量的随机写操作的数量,同时维持一个较高的搜索效率,它采用了对数方法[Bentley79]和分散层叠技术(fractional cascading)[ChazelleG86]来实现高效地搜索和更新。一棵FD-树包含了多个级别,被称为L0,L1,…,Ll-1,其中,l表示级别的数量。最顶层L0是一个小的B+-树,称为“头树”。每个其他的级别Li,是一个存储在连续的页中的有序段。为了加快在多个有序段中的搜索速度,FD-树采用了分散层叠技术。图[FD-tree]显示了一棵FD-树的结构,这棵FD-树有三个层次:头树和两个有序段。头树是一棵两层的B+-树。采用分散层叠技术后,头树的叶子节点具有指向有序段L1的指针。每个非叶子节点,也都有指针指向相邻的下一层的有序段。

FD-树的每层都有一定的容量(能够容纳的元素的个数),FD-树根据对数方法在不同的层采用阶梯式的容量,即||Li+1||=k.||Li||(0≤i≤l-2),其中,||Li||表示第Li层的容量,kLiLi+1之间的对数尺寸比。因此,存在如下关系:||Li||=ki*||L0||。更新操作最先针对头树进行,然后当每层的容量达到上限时,就会被逐渐批量迁移到下面层的有序段中。头树的最大尺寸||L0||远远小于可用的内存容量,因此,可以放入内存。如果设置||L0||为闪存的擦除块的大小,就可以使得头树可以被保存到一个擦除块中。因为头树可以放置到内存中,许多针对闪存盘的随机写操作,就可以通过合并操作转换成顺序写操作,从而减少了小数据量的随机写操作的数量。

FD-树设计了索引项(Index Entry)和栅栏(fence):

(1)索引项:一个索引项包含三个字段,即索引键key、记录号和类型,“类型”字段用来确定它在“对数删除”FD-树中的角色。

 (2)栅栏:一个栅栏包含了指向更低层次的有序段中的页的指针,具有三个字段,即键值、类型和pid,pid是紧邻的更低层次的页的ID,用来指导进行搜索。采用栅栏以后,一个FD-树的搜索操作,就可以首先在一个更小的树上执行,然后,在栅栏的引导下,向下一层一层地进行搜索。

图[FD-tree]FD-树的实例

图[FD-tree] FD-树的实例

在一棵FD-树上进行搜索,需要从顶向下搜索每个层。首先在头树上进行查找,这和在传统的B+-树中查找类似。接着,沿着栅栏的pid在每个级别上进行查找。在级别Li的一个页的内部,会采用二分法搜索来寻找到第一个匹配的索引项。然后,可以扫描有序段,从第一个匹配的索引项开始,找到所有匹配的索引项。然后继续扫描,直到发现一个栅栏的键值等于或者大于搜索的键值。所有匹配的键值都会被加入到结果中。图[FD-tree-b]显示了在图[FD-tree]的FD-树中进行查找key=48的记录的过程。在每个层次都会搜索整个页,一旦碰到栅栏,就去搜索在下一个层次的有序段中的页。

图[FD-tree-b]在FD-树中进行查找

图[FD-tree-b] 在FD-树中进行查找

7.4    LA-树

基于日志的B-树索引[WuCK03]和FlashDB[NathK07]中的自适应B+-树索引等面向闪存的索引结构的设计思想,都是采用页级别的写优化策略。也就是说,这些方法并没有执行一个代价高昂的、针对原始闪存页的就地更新操作,而是把数据页发生变化的部分,以日志的形式存储到闪存中一个单独的位置。这种方式有效地降低了页写操作的代价,但是,与此同时也大大增加了读操作的代价,因为,当一个页需要被读回到内存中时,需要读取原始页和日志页,然后重构得到最新版本的数据页。因此,Agrawal等人[AgrawalGSDS09]认为这种优化方式并不是非常适合面向闪存的索引结构,他们提出了一种新的面向闪存的索引结构——LA-树(Lazy Adaptive tree),它采用了完全不同于其他方法的思路,即惰性更新技术,它借鉴了批量更新索引树缓冲区的相关研究工作[ArgeH02]。

7.4.1      LA-树的设计思想

LA-树的主要思想是,使用了基于级联缓冲区的惰性更新技术,来减少更新一个面向闪存的树结构索引所产生的高昂代价,把树结构的高昂更新代价在多个更新操作之间进行分摊,使得单个更新操作具有较低的代价,同时还采用了一种自适应的在线算法,可以根据工作负载动态调整缓冲区大小,从而可以同时为更新和查询都获得较好的性能。

(1)级联缓冲区

为索引树的多个层次上的每个节点都附加一个缓冲区,每个缓冲区包含了将要在这个节点及其后代节点上执行的操作。选择一个合适的时机,缓冲区中的所有元素都会以批量的方式,被推到下一层的缓冲区中。这个操作可能会继续向下一层缓冲区传播,直到被推到叶子节点,因此,取名为“级联缓冲区”。由于LA-树缓冲区中缓存了多个更新操作,因此,多个更新操作之间共享从根节点到叶子节点的访问代价,也就是说,每个更新都只需要分担一部分代价,从而使得每个更新都具有较低的代价。

(2)在线自适应算法

惰性更新技术需要设计级联缓冲区,但是,采用固定大小的缓冲区设置,会引起更新和查询性能之间的矛盾,即提高更新操作性能可能意味着查询性能的降低。这里考虑一个具备固定尺寸B的根缓冲区。当缓冲区中已经累积了B个条目时,它就会被清空,把条目分发给下一层的缓冲区。清空代价包括两个部分:(a)对缓冲区和子树的一次扫描,和(b)把缓冲区元素写入到下一级的缓冲区中。因此,在所有更新操作之间分摊清空代价(尤其是分摊的子树读取代价),是和B成反比的。相反,在一个查询操作中,必须扫描一个缓冲区中的所有条目,引起的代价和B成正比。因此,缓冲区的大小设置,在更新操作和查找操作之间表现出了矛盾性。针对这个问题,一些其他方法都是以较高的查询开销为代价,换取较低的更新代价。相反,LA-树使用一个在线算法动态地自适应任意的工作负载,可以根据工作负载的特性控制缓冲区的大小,从而可以为更新和查询同时提供较高的性能。

7.4.2      LA-树索引结构

和B+树类似,LA树是一棵出度为F的平衡树。B+树不同的地方在于,在LA-树中,每个第K层上的节点都附加了一个常驻闪存的缓冲区,这个缓冲区用来批量地执行将要在这个节点及其后代节点上执行的更新操作(插入或删除)。在一棵LA-树中,一棵“子树”是指树中的一个片段,它从附加了缓冲区的节点开始,到下一个附加了缓冲区的节点所在的层之上结束,因此,一个子树有K层。

图[Lazy-adaptive-tree]显示了当K=2时的一棵LA-树的实例。A是根节点,A、B、C、D、E、F、G、H是非叶子节点,I、J、K、L是叶子节点,由节点A、B、C和D这四个节点构成一个一棵根子树,由节点E、I和J构成一棵子树S1,由节点H、K和L构成一棵子树Si。可以看出,每棵子树都包含两层。这棵LA-树一共包含了4层,第1层中的根节点A,以及第3层中的所有节点(比如E、F、G和H),都附带了一个缓冲区。

图[Lazy-adaptive-tree]LA-树的一个实例

图[Lazy-adaptive-tree] LA-树的一个实例

1)惰性插入和删除

LA-树采用了惰性更新技术,也就是说,与新的插入和删除相对应的缓冲区条目,只会简单地被插入到根节点的缓冲区中。然后,在线自适应算法会被调用,用来判断是否需要清空缓冲区。如果决定需要清空缓冲区,就会唤醒缓冲区清空进程,以批量的方式把缓冲区中的所有条目,都推动到处于LA-树中下一个层级的缓冲区中。这个过程会产生级联效果,直到这些缓冲区条目最终到达叶子节点。

2)即时查找

当一棵LA-树接收到一个查找请求时,它会从上自下查找索引树。LA-树和B+树的一个主要区别是,如果在从根节点到叶子节点的路径上的某个节点被附加了缓冲区,LA-树会同时扫描缓冲区,寻找是否存在还没有被传播到叶子节点的更新操作。当执行一个缓冲区扫描时,在线自适应算法会综合考虑历史的工作负载,从而判断清空缓冲区的操作是否可以改善性能。如果缓冲区清空操作被判定为可以带来收益,缓冲区中的所有条目都会被推动到下一个层级的缓冲区中;否则,会扫描缓冲区,来寻找和搜索谓词匹配的结果。这个过程会一致持续,直到到达叶子节点。

(3)关于清空缓冲区的动态操作

在线自适应算法是LA-树的核心智能模块,它记录了针对每个缓冲区的更新和查找操作序列,并且通过决定何时清空缓冲区来控制缓冲区的大小,从而使得缓冲区的大小始终可以保证获得较好的更新和查找操作性能。更新请求不会引发一个缓冲区清空操作,除非缓冲区大小超过了预先定义的上限值。对于查找操作而言,在线自适应算法会同时记录扫描缓冲区的代价和清空缓冲区的预估代价,然后,它会衡量下面事项:(1)在这个时间点清空缓冲区的代价;(2)由于清空操作导致的后续的查询操作可能获得的收益。经过衡量以后,如果收益超过清空代价,那么就会决定清空缓冲区。

4)缓冲区清空操作

在决定清空缓冲区时,在线自适应算法会唤醒缓冲区清空函数。在一个中间子树中的缓冲区清空操作过程如下:在搜索完这棵子树以后,对缓冲区条目进行排序,以排序后的顺序把缓冲区中的所有条目都发送到下一个级别的缓冲区中。在叶子子树中的缓冲区的清空操作,也是从排序缓冲区条目开始的,然后,缓冲区的条目会以排序后的顺序被发送到叶子节点。叶子节点会从左到右被一次性处理,对于每个叶子节点N,接收到的缓冲区条目会被合并到N中,即执行这些条目中包含的插入和删除操作。如果N溢出了,它就会被分裂成两个或多个节点。这种分裂可能会传播到它的祖先节点;附加在这些节点上的非空的缓冲区也会相应地发生分裂。由于在实际工作负载中,插入和删除操作是混合的,因此,N很少会发生溢出。但是,当确实发生溢出时,N首先采用的调整方式是,从隔壁节点借用条目,然后,如果有需要,它会和B+树一样,和邻居节点发生合并。在很少发生的合并操作中,除了被合并的节点的缓冲区也会被相应地合并之外,父节点和祖先节点的调整和B+树一样。

7.5    本章小结

本章内容首先指出了针对闪存特性设计相应的索引结构的必要性;然后,介绍了基于日志的B-树索引,给出了一种基于日志的B-树索引方法的体系架构——BFTL,该方法可以被封装成一个单独的、可插拔的模块,并且该模块处于FTL层之上;接下来,介绍了面向闪存的B+-树索引,包括惰性更新B+-树方法和自适应B+-树方法;然后,又介绍了FD-树,它的目标在于最小化小数据量的随机写操作的数量,同时维持一个较高的搜索效率,它采用了对数方法和分散层叠技术来实现高效地搜索和更新;最后,介绍了FA-树,它使用基于级联缓冲区的惰性更新技术,来减少更新一个面向闪存的树结构索引所产生的高昂代价,把树结构的高昂更新代价在多个更新操作之间进行分摊,使得单个更新操作具有较低的代价,同时还采用了一种自适应的在线算法,可以根据工作负载动态调整缓冲区大小,从而可以同时为更新和查询都获得较好的性能。

7.6    习题

  • 说明针对闪存特性设计相应的索引结构的必要性。
  • 在闪存上直接建立B-树索引,面临的一个棘手的问题就是级联更新,请说明什么是级联更新。
  • 阐述BFTL方法中的节点转换表的作用。
  • 分析磁盘B+-树和日志B+-树的各自不同特点。
  • 阐述惰性更新B+-树方法中采用的两种在线提交策略。