第10章 基于混合存储系统的数据库

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

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

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

第10章 基于混合存储系统的数据库

闪存凭借其优良的特性，已经在企业级存储系统中得到了广泛的应用，大有取代磁盘之势。但是，在目前这个阶段，完全用闪存取代磁盘作为底层存储介质还不现实，主要是因为：（1）磁盘作为存储系统的主要介质已经有很久的历史，里面保存了大量的企业数据，从节约成本的角度而言，大量磁盘仍有继续发挥“余热”的必要；（2）从性能的角度而言，虽然闪存的随机存取速度要明显优于磁盘，但是，就顺序存取速度而言，磁盘仍然具有一定的优势；（3）从价格方面而言，当前闪存的价格仍然要比磁盘高出许多。

因此，在未来较长的一段时期，都会出现闪存和磁盘共存的情形，即由闪存和磁盘一起作为存储介质，数据库既不是单独运行在磁盘上，也不是单独运行在基于闪存的存储设备（比如固态盘）上，而是运行在基于闪存和磁盘的混合存储系统上。但是，由于闪存和磁盘具有明显不同的特性，因此，在混合存储系统中二者将会扮演不同的角色，以期获得最好的投资收益。从闪存和磁盘在存储系统中扮演的角色而言，可以大致包括以下三种情形：（1）闪存代替磁盘作为特种数据的存储介质；（2）闪存和磁盘并列构成混合存储系统；（3）闪存作为介于磁盘和内存之间的缓存。

本章内容将首先分别介绍闪存和磁盘在存储系统中扮演的不同角色，然后介绍一种基于语义信息的系统框架hStoreage-DB，它可以根据收集到的语义信息，把访问请求分成不同的类型，并为每种类型分配一个合适的QoS(Quality of Service)策略，这些策略是被底层的混合存储系统所支持的，从而使得每个请求都可以由混合存储系统中合适的存储设备来为之提供服务。

10.1    闪存代替磁盘作为特种数据的存储介质

在混合存储系统中，闪存代替磁盘作为特种数据的存储介质，继续使用磁盘存储作为其他普通数据的存储介质。

10.1.1      存储事务日志

同步事务日志是指，在事务提交之前要求必须把日志“强制写入”到稳定的存储介质上（目前一般采用磁盘），然后，事务才能提交完成，它是DBMS为了保证数据一致性和可恢复性的核心机制。

10.1.1.1       同步事务日志成为数据库性能的瓶颈

但是，硬件技术发展的两道“鸿沟”，使得事务日志“强制写入”过程的性能受到严重制约，从而最终严重制约了数据库的整体性能：

（1）CPU、DRAM内存性能与磁盘性能之间的鸿沟。在过去的这些年里，CPU和DRAM内存的带宽都已经增长了指数倍，但是，磁盘的性能改进的步伐却显得远远落后，磁盘的随机访问延迟和带宽，自从1980年以来只提升了3.5倍[AthanassoulisACGS10]。这道鸿沟使得数据库中的大量事务日志的“强制写入”过程，都会在与磁盘发生I/O操作时遭遇第一道性能瓶颈。

（2）磁盘延迟和磁盘带宽之间的鸿沟。磁盘带宽是由接口决定的，接口的速率一般是指理论最大传输速率，但是，接口提供的带宽远远高于当前的磁盘速度，因为，磁盘内部传输速率制约了整体的速度，而磁盘延迟又是内部传输速率的决定因素。由于磁盘包含磁头、碟片和转轴等机械部件，读写数据都需要一个寻址的过程，因此，磁盘延迟往往较大。在过去的十多年里，磁盘延迟改进的步伐，已经远远落后于磁盘带宽的改进速度，延迟和带宽之间的鸿沟，在未来将会变得更加明显[Patterson05]。这就意味着，磁盘延迟会成为事务日志的“强制写入”过程的第二道瓶颈，也是最大的瓶颈。可以说，事务型数据库应用的性能，更多地是受到磁盘延迟的限制，而不是磁盘带宽或容量[ZhangYKW02]。

此外，磁盘的技术特性和同步事务日志的访问模式，也使得同步事务日志无法获得好的性能。在OLTP系统中，存在大量的事务，因此，会不断生成日志并被强行写入到磁盘上，也就是说，同步事务日志会生成很多小的顺序写操作。这种写操作模式很不适合磁盘，因为在前后写操作之间，磁盘的碟片会连续旋转，写完一个日志条目后，需要碟片转过完整的一圈，然后再在后面的位置写入下一个条目，所以在两个不同的写操作之间会存在一个完整的旋转延迟，这就带来了较大的日志“强制写入”延迟。

另外，数据库事务机制的特性也带来了较大的日志强制写入延迟。每个要提交事务都必须等到所有属于自己的日志记录被强制写入到日志中以后才能提交，而某个事务的日志写入操作，还必须等待队列中排在它之前的所有其他事务的日志写入操作都已经完成，然后才能开始执行。因此，随着并发事务数量的增加，日志强制写入延迟就会增加，通常不会少于几个毫秒。

随着处理器的速度变得越来越快以及内存容量的增加，由于同步日志“强制写入”而导致的提交时间延迟，会越来越成为获得事务处理高性能的一个严重瓶颈。

10.1.1.2       用闪存存储事务日志可以明显改进事务吞吐量

闪存固态盘具有明显低于磁盘的延迟，可以大大加快同步日志的“强制写入”过程速度，降低平均事务提交时间，从而明显改进事务吞吐量。文献[LeeMPKK08]通过大量的实验表明，通过把磁盘替换成闪存固态盘，会极大缓解在事务提交时间方面的瓶颈，数据库在事务吞吐量方面可以获得指数级的提升。这将会有助于加速在企业数据库应用中采用闪存固态盘，并且帮助数据库从业者重新审视数据库设计的需求和数据库服务器的调优方法。

但是，文献[AthanassoulisACGS10]的研究指出，虽然把磁盘替换成固态盘解决了磁盘的性能瓶颈问题，但是，也带来了新的挑战，因为，大量的随机写操作会恶化性能，并且会很快让闪存磨损老化掉。为了解决这个挑战难题，作者提出了一个A/P（Append/Pack）设计技术[StoicaAJA09]，它不对DBMS做任何修改，可以避免对闪存的随机写操作，同时提出了FlashLogging[Chen09]来利用闪存进行同步地写入日志。

图[FlashLogging] FlashLogging的体系架构

图1显示了FlashLogging的体系架构，它采用了闪存阵列，即可以利用多个闪存设备进行日志记录和恢复性能，当闪存中的日志数据到达一个指定的大小时，这些日志数据会被刷新到磁盘中，因此，磁盘可以看成是一个归档磁盘。闪存阵列可以采用多个低端的USB闪存设备，或者也可以是一个高端的固态盘中的多个分区。FlashLogging要实现两个目标：（1）在常规操作中优化顺序写操作的性能；（2）在恢复过程中优化顺序读操作的性能。当日志写入操作被分配到一个闪存上执行，发现闪存正在进行其他管理操作，比如擦除操作，就需要让日志写入操作处于等待状态，这会增加日志写入过程的延迟。为此，FlashLogging一旦发现这些异常写操作情况发生，就会把它引导到其他已经准备好的闪存设备中，减少延迟。

10.1.2      存储回滚段

目前有非常多的DBMS产品采用了多版本并发控制技术（比如Oracle、SQL Server 2005、PostgreSQL、 Firebird、InnoDB、Falcon、PBXT和Maria等等），而不是采用单版本加锁的方法实现并发控制。多版本并发控制技术保存了某一时刻数据的一个快照，对于一个事务而言，无论运行多久，都可以保证它能够看到一致的数据。

多版本并发控制技术中使用了一个非常重要的设计——回滚段，必须存放在稳定的存储介质上，用于存放数据修改之前的值。一个事务只能使用一个回滚段来存放它的回滚信息，而一个回滚段可以存放多个事务的回滚信息。需要特别指出的是，多版本并发控制技术中的回滚段，和数据库的事务日志具有很大的区别，前者只用于多版本并发控制，不用于事务的恢复，而后者主要用于事务恢复。在多版本并发控制下，更新一个数据对象时，需要把它之前的旧版本写入到一个回滚段，同时还要为这次更新书写相应的重做日志。

当一个事务被创建时，它会被分配给一个特定的回滚段，然后，这个事务就会把数据对象的旧版本按照追加模式顺序地写入到这个回滚段。多个并发事务会同时生成并行的回滚段写操作数据流。在当前的区间中（分配给对象的任何连续块，称为“区间”，也可称为“扩展”），如果回滚段耗尽了空间，就会给这个回滚段分配一个新的区间。因此，针对回滚段的连续写请求，对应的物理地址空间往往是不连续的。如果采用磁盘驱动器来存储回滚段，那么，针对回滚段的许多连续写请求，很可能必须把磁头移动到不同的磁道上面去执行。因此，对于多版本并发控制而言，由于磁盘寻址存在大量延迟，记录回滚数据的代价就会比较高。

另外，在多版本并发控制技术中，如果采用磁盘作为存储回滚段的介质，读取一个数据对象也具有很高的代价。当一个数据对象更新时，就要把该数据对象的旧版本写入回滚段，如果发生过多次更新，就会在回滚段中记录多个旧版本，这些旧版本构成一个数据链表，从而加速查找遍历旧版本的速度。当读取这个数据对象时，需要首先检查它是否被更新过，如果曾经发生了更新，就需要到回滚段中查找旧版本链表，找到正确版本的旧数据。可以想象得到的是，当这个数据对象被频繁更新时，旧版本链表会很长，而且，由于回滚段采用了顺序追加模式写入旧版本数据，这些旧版本会被分散到不同的磁盘物理空间内，遍历旧版本链表会带来大量的磁头移动开销，恶化数据库性能。

从上面论述可以看出，采用磁盘存储回滚段时，由于存在较高的寻址延迟，写入和读出操作的代价都很高，影响了数据库的性能。闪存的随机访问延迟很低，很适合作为回滚段的存储介质，而且，数据对象的旧版本是以追加的方式顺序写入到回滚段中的，这种方式非常符合闪存异地更新的特性。文献[LeeMPKK08]通过大量实验研究，从两个方面讨论了采用闪存盘作为回滚段的存储介质带来的性能收益：

• 对写操作的性能改善有限：虽然闪存固态盘的写延迟要比磁盘的写延迟低很多，但是，在回滚段写操作性能方面，采用固态盘和磁盘的性能差异不大。导致这个问题的主要原因在于固态盘空间有限，存在垃圾回收过程，会产生大量代价昂贵的合并操作（包含擦除操作和写操作）。
• 对读操作的性能改善较为明显：闪存的随机访问速度和顺序访问速度是一致的，比磁盘块许多，因此，读取保存在固态盘中的回滚段数据时，虽然这些数据分散在不同的物理空间，但是，仍然可以获得较快地读取这些数据。

10.1.3      存储中间结果

基于闪存的固态盘可以成为一种比较理想的中间结果的临时数据存储介质。例如，在数据库中的分析查询经常需要运行连接算法，在连接算法执行过程中，会生成大量的中间结果，这些中间结果存取的快慢会直接影响到连接算法生成最终结果的速度，从而影响查询的响应速度。在“内存-磁盘”的存储体系架构下，连接操作的大量中间结果通常需要保存到磁盘中，因为，内存空间有限，无法容纳大量的中间结果。固态盘具有很高的性价比，相比磁盘而言，具有更高的I/O带宽，也不会受到机械部件的限制。因此，固态盘非常适合用于临时存储中间结果。尤其对于非阻塞连接算法而言，它的全部外部I/O都是从临时存储中读取数据的I/O，采用固态盘作为临时存储，可以大大减少从临时存储中读取数据的时间，从而加快了算法完成速度。

10.1.3.1       连接算法介绍

数据库系统中采用的连接算法主要包括：块嵌套循环连接、归并排序连接和哈希连接。

10.1.3.1.1        块嵌套循环连接

块嵌套连接算法的伪代码如下：

JoinResult={};/*初始化结果集合*/ Buffer=M;/*内存缓冲区大小为M个块*/ for each M-1 blocks in S /*每次从外关系S中读取M-1个块到内存缓冲区中*/ Read M-1 blocks of S into Buffer; for each block in R /*每次从内关系R中读取1个块到内存缓冲区*/ Join M-1 blocks of S and 1 block of R in Buffer;/*在内存中对块中元组执行连接*/ Output the join results into JoinResult; endfor endfor Return JoinResult;

         可以看出，块嵌套连接算法包含了一个二重循环，通常把处于外循环中的关系S称为“外关系”，而把处于内循环中的关系R称为“内关系”。采用块嵌套循环连接算法执行两个关系R和S的连接操作时，通常把较小的关系S作为“外关系”，把较大的关系R作为“内关系”。图[join(a)]给出了块嵌套循环连接方法的原理。假设内存空间大小为M个块，算法为关系R和S分配内存空间时，会把其中的M-1个块的内存分配给关系S，把1个块的内存分配给关系R。外关系S会按照M-1个块的大小，被切分成若干个子片段，即每个子片段（除了最后一个子片段）的大小都是M-1个块。当连接操作开始执行时，首先把外关系的第一批的M-1个块（即S₁）读入内存，然后，读入关系R的第1个块（即R₁），在内存中对S₁和R₁进行连接，把连接结果放入输出缓冲区中（当输出缓冲区满时，缓冲区中的连接结果会被刷新到底层的辅助存储器中，比如磁盘）。接下来，再读入关系R的第2个块（即R₂），在内存中对S₁和R₂进行连接，把连接结果放入输出缓冲区中。依此类推，分别顺序读入关系R的其他块R_i，在内存中对S₁和R_i进行连接。这个过程结束后，就完成了子片段S₁和关系R的连接操作，然后，就可以再次读入外关系S的第二批的M-1个块（即S₂），重复上述过程，完成子片段S₂和关系R的连接操作。依此类推，可以完成每个子片段S_j和R的连接操作，从而最终完成整个外关系S和内关系R的连接操作。

图[join(a)] 块嵌套循环连接方法

10.1.3.1.2   归并排序连接

归并排序连接算法包括两个步骤（如图[join(b)]所示），即归并排序和连接。在归并排序这个步骤中，需要对参与连接的关系R和S在连接属性上进行排序。在连接这个步骤中，需要按照连接属性的顺序扫描两个关系，同时对两个关系中的元组执行连接操作，具体方法如下：把已经在连接属性上排序的关系R和S的第一个块R₁和S₁，都读入内存，R₁和S₁都包含了若干个元组，在内存中对R₁和S₁中的元组按照顺序执行连接操作，如果R₁和S₁的参与连接比较的两个元组相等，则把连接结果输出到缓冲区，如果两个元组不相等，则废弃值较小的元组并从该元组所属的块（R₁或者S₁）中输入下一个元组参与连接的比较。当R₁或者S₁中的某个块中的元组消耗殆尽时，就从该块所属的关系（R或S）中顺序读入下一个块，继续执行连接操作。最终，当来自关系R和S的所有块都消耗殆尽时，连接过程结束。

图[join(b)] 归并排序连接算法

归并排序连接算法的第一个步骤归并排序，是一种外部排序。外部排序是数据库中的一种常见操作，是指针对大数据集的排序，即待排序的元组存储在外存储器（比如磁盘）上，大量待排序的元组无法一次性放入内存，需要在内存和外部存储器之间进行多次数据交换，最终实现对整个数据集进行排序的目的。如图[join(c)]所示，外部排序一般包括两个阶段：

（1）第一阶段：得到初始归并段。根据内存容量的大小，把大数据集切分成若干个数据块，每个数据块都可以单独放入内存，即把图[join(c)]中的关系R切分成若干个块R₁,R₂,…,R_n，然后，采用有效的内存排序算法（比如快速排序和堆排序等）进行排序，由此可以得到若干个初始归并段，每个归并段内部的元组都是已经经过排序的；对于图[join(c)]中的关系R而言，经过内存排序后的初始归并段为R₁*,R₂*,…,R_n*。

（2）第二阶段：归并排序。进行逐趟归并，比如，假设有10个初始归并段，如果采用2-路归并，那么第一趟由10个归并段得到5个归并段，第二趟由 5 个归并段得到3个归并段，第三趟由 3 个归并段得到2个归并段，第4趟（最后一趟）归并得到整个元组集合的有序序列。在执行每趟归并时，把初始归并段R₁*中的第1个块b₁，R₂*中的第1个块b₂，……，R_n*中的第1个块b_n，都读入内存中，每个块都包含了若干个元组，然后，在内存中，对b₁, b₂,…, b_n第一个元组进行比较，假设这里按照降序排序，则经过比较后，把具有最大值的元组放到输出缓冲区，并从内存中删除该元组；同理，可以进行后面的若干次元组比较，每次比较后，都会把具有最大值的元组放到输出缓冲区，并从内存中删除该元组，从而使得b₁, b₂,…, b_n这些块中的元组会越来越少，当某个块的元组消耗殆尽时，就从该块所属的初始归并段中读入下一个块到内存中，这就会使得初始归并段剩余的块数越来越少，直至最终每个初始归并段的所有块都被消耗殆尽时，这一趟的归并排序阶段就彻底完成，继续进入下一趟归并排序过程，再重复上面的步骤。

 

图[join(c)] 归并排序

10.1.3.1.3        哈希连接

哈希连接有两种输入关系，即生成输入和探测输入，查询优化器会指派这些角色，一般而言，为了能够让生成输入的哈希桶能够放入内存，通常把两个输入关系中元组较少的关系作为生成输入。这里假设生成输入是元组数量较少的关系S，探测输入是关系R。

哈希连接包括多种形式，主要有：内存中的哈希连接、Grace哈希连接、递归哈希连接和混合哈希连接。生成输入和内存大小的关系，决定了采用哪种哈希连接方法。当生成输入可以一次性放入内存时，可以使用内存中的哈希连接；当生成输入大大超过内存大小时，则采用Grace哈希连接；当生成输入只是略微大于内存大小时，就可以采用混合哈希连接。数据库系统的查询优化器在执行具体的连接运算时，通常无法确定始终使用一种方法，比如，可能在开始阶段使用的是内存中的哈希连接，然后根据生成输入的大小逐渐转换到Grace哈希连接和递归哈希连接。

10.1.3.1.3.1        内存中的哈希连接

当生成输入可以一次性放入内存时，可以使用内存中的哈希连接，它的执行过程包括两个阶段：第一个阶段是生成阶段，首先在内存中生成哈希表，然后扫描生成输入S，使用哈希函数把S中的每个元组在连接属性上进行映射，分别放入相应的哈希桶中；第二个阶段是探测阶段，每次从输入关系R中顺序读取一个元组，首先在连接属性上计算该元组的哈希键的值，然后，把该元组和内存中相应的、具有相同键值的、属于S的哈希桶中的元组进行比较连接，并输出结果。

10.1.3.1.3.2        Grace哈希连接

当生成输入大于内存，无法一次性放入内存时，需要采用Grace哈希连接算法，它的执行过程包括两个阶段：第一个阶段是，使用相同的哈希函数f₁把参与连接的两个关系R和S，在连接属性上分别映射到不同的哈希桶中，这个过程结束后，所有在连接属性上具有相同的键值的元组，都会被放入到同一个哈希桶中，由此可以得到关系R和S的若干个哈希桶R₁,R₂,…,R_n和S₁,S₂,…,S_n，这些哈希桶分别被存放在磁盘的不同文件中，每个哈希桶对应一个分区文件，从而可以有效减少单个输入的元组数量，另外，对关系R和S采用相同的哈希函数，可以保证关系R和S中在连接属性上具有相同值的元组，一定会分别被放入到配对的哈希桶<R_i, S_i>中；第二个阶段，对关系R和S中对应的哈希桶中的元组进行连接操作，即对每个配对的哈希桶<R_i, S_i>中的元组执行连接操作，需要首先读入关系S的一个分区文件S_i，使用一个哈希函数f₂在内存中为S_i构建一个哈希表h，然后，依次顺序读入分区文件R_i中的每个元组t，使用元组t在哈希表h上进行探查，输出连接结果。在第二个阶段，如果要求每个配对的哈希桶<R_i, S_i>中的元组能够只需要一次读入内存就可以完成连接操作，那么，就必须使得S_i能够一次性放入内存，这就要求必须采用一个合适的哈希函数，使得哈希得到的每个哈希桶S_i的大小不超过内存的大小。当S_i能够一次性放入内存时，可以首先把S_i全部读入内存，然后，把R_i中的元组依次顺序读入内存，每读入一个R_i中的元组t，就把t和S_i中的全部元组都进行一次比较连接，输出连接结果，然后丢弃t，再继续从R_i中读入下一个元组。当R_i中的元组全部消耗殆尽，就完成了<R_i, S_i>中的元组的连接。

需要注意的是，Grace哈希连接中，分区文件的构建（每个分区文件包含了一个哈希桶）和连接被放入两个不同的阶段，在执行连接操作时，需要再次把这些分区文件从磁盘读入内存。

10.1.3.1.3.3        混合哈希连接

当生成输入只是略微大于内存大小时，则可以采用混合哈希连接，即把内存中的哈希连接和 Grace 哈希连接的元素结合在一个步骤中。

在第一个阶段中，首先，需要把较小的关系S顺序地读入内存，对于每个元组，都在连接属性上对其使用合适的哈希函数，把元组映射到相应的哈希桶S_i中。与Grace哈希连接不同的是，混合哈希连接并非把所有的哈希桶都写入到磁盘文件中，由于一部分内存缓冲区本来就是用来在第二个阶段（连接阶段）为每个哈希桶S_i构建哈希表的，因此，关系S的最后一个哈希桶S_n，就可以不用写入到磁盘文件中，只需要把其他n-1个哈希桶写入文件。然后，需要把关系R的每个元组顺序读入内存，并在连接属性上对每个元组使用合适的哈希函数，把元组映射到相应的哈希桶R_i中，在这个过程中，每个读入内存的关系R的元组，都可以直接和那些没有写入文件而是保存在内存中的哈希桶S_n中的元组进行连接操作，这个过程完成后，既可以完成关系R和S_n的连接操作，同时，也可以得到关系R的n-1个分区文件。

         混合哈希连接的第二个阶段和Grace哈希连接的第二个阶段完全相同。

10.1.3.2       采用固态盘存储连接算法的临时结果

文献[ChenGN10]提出了一个非阻塞连接算法PR-join，并探讨了把固态盘作为临时存储的可行性和优势。PR-join可以取得近似最优的性能，它利用固态盘作为临时存储来存放分片后的数据。PR-join可以支持在线聚合和数据流处理。文献[LeeMPKK08]提出采用闪存固态盘存储临时表空间，主要是存储外部排序和哈希连接查询生成的临时结果，可以明显提高数据库性能。文献[DoP09]在一个单线程、轻量级的数据库引擎上，分别采用闪存固态盘和磁盘，对四个流行的即席连接算法进行了性能测试，包括块嵌套循环连接、归并排序连接、Grace哈希连接和混合哈希连接，通过对实验结果的分析得到如下结论：

（1）在闪存固态盘上的连接操作的性能，更有可能会受到CPU性能的限制，而不是受限于I/O的性能，因此，改变CPU性能的方法（比如更好的缓存利用方式），对于固态盘而言非常重要；

（2）对于闪存固态盘而言，设计更多随机读操作，尽量减少随机写操作，可能是一个比较好的设计选择；

（3）和顺序写操作相比，随机写操作在闪存上产生了更多的I/O变化，这使得连接操作的性能更加难以预测。

当把磁盘替换成闪存固态盘时，对于上述四种连接算法而言，在性能改进方面，文献[DoP09]的测试结果给出了如下结论：

（1）把磁盘替换成固态盘，对于所有四种连接算法都是有益的。块嵌套循环连接算法的I/O模式是顺序读，因此，具有最大的性能改进。其他连接算法在固态盘上的性能也都要好于在磁盘上面的性能，但是改进幅度要小于块嵌套循环连接算法，这是因为在闪存固态盘上面，写传输速率要比读传输速率慢，无法预料的擦除操作可能会进一步恶化写操作的性能。

（2）混合哈希连接，无论是在磁盘上还是在固态盘上面，都要比其他连接算法的性能要好。

（3）采用固态盘时，对于较大的缓冲池尺寸而言，块嵌套循环连接比归并排序连接和Grace哈希连接的性能都要好，但是，比混合哈希连接要慢，因为，混合哈希连接的CPU效率更高（虽然需要更多的I/O代价）。

（4）Grace哈希连接在所有阶段的I/O加速比，都要比归并排序算法低。对于Grace哈希连接而言，主要I/O模式是第一个阶段的随机写操作和第二个阶段是顺序读操作。Grace哈希连接的第二个阶段是顺序读操作，因此，可以取得较高的加速比，但是，第一个阶段是随机写操作，在闪存上会伴有昂贵的擦除操作，因此，第一个阶段的I/O加速比很低。对于归并排序算法而言，第一个阶段是顺序写操作，性能要比Grace哈希连接好（第一阶段是随机写），第二个阶段是随机读操作，按理说，性能应该和Grace哈希连接的第二阶段一样，因为，闪存上面的顺序读和随机读操作具有一致的性能，但是，Grace哈希连接在第一阶段的随机写操作，产生的闪存性能的负面影响会持续一段时间，因此会影响到第二个阶段的顺序读操作的性能，这就导致Grace哈希连接的第二个阶段的I/O加速比仍然要比归并排序算法比。这就说明，那些强调随机读并且尽量避免随机写操作的算法，在闪存固态盘上面可能获得更大的性能改进。

10.1.3.3       采用固态盘可以提升归并排序连接算法性能的原因分析

这里将分析采用闪存固态盘作为中间结果的临时存储介质是如何提高归并排序连接算法性能的，对于哈希连接查询时采用固态盘存储中间结果，也具有类似的性能提升效果，将不再赘述。

归并排序连接算法包含一个外部排序的过程，对于外部排序整个过程而言，在数据存储方面可以大致划分成三个子过程：（1）初始大数据集的存储；（2）多个数据块的外部排序中间结果的存储；（3）排序后的大数据集的存储。用闪存固态盘取代磁盘存储外部排序的中间结果，发生在第2个存储子过程，其他两个存储子过程的外存储器仍然采用磁盘，因此，这里只对第2个存储子过程所具备的I/O模式的特点进行简单分析，它的I/O模式特点可以概括为：顺序写操作和随机读操作[GraefeLS94]。每次把内存中的排序结果写入外存储器就是顺序写操作，每次从外存储器读取数据就是随机读操作。

如果采用闪存固态盘存储外部排序的中间结果，由于固态盘具有较低的读写延迟，并且随机读和顺序读操作同样快，所以，可以明显提升外部排序过程的性能。文献[LeeMPKK08]在商业数据库上运行外部排序，测试了分别采用固态盘和磁盘存储中间结果时的排序性能，这里假设大数据集被分成n个数据块，得到n个初始归并段以后，采用n-路归并排序，这样，归并排序阶段只需要从外存储器中进行一次随机读操作（读入n个排序后的归并段），从而使得整个外部排序的第2个存储子过程的I/O模式，就会呈现出明显的两阶段特征，即第一个阶段的顺序写操作和第二个阶段的随机读操作。

文献[LeeMPKK08]中得到了图[external-sort]中的实验结果，其中，横坐标轴表示时间，纵坐标轴表示读写操作对应的逻辑地址空间。图[external-sort](a)和(b)这两个子图的左边，是第一个阶段生成每个初始归并段后写入外存储器时的逻辑地址空间分布情况，可以看出，对于固态盘和磁盘而言，都呈现出一条逐渐向上的“斜线段”，这正好符合顺序写操作的特征，因为初始归并段后写入外存储器就是一个顺序写操作过程；图[external-sort](a)和(b)这两个子图的右边，代表了第二个阶段归并排序时从外存储器读入数据时的逻辑地址空间分布情况，可以看出，对于固态盘和磁盘而言，都覆盖了较大范围内的逻辑地址空间，即读操作是随机分布在这些逻辑地址空间上，这正好符合归并排序时的随机读的特征。从图[external-sort]中可以看出，在第一个阶段的顺序写操作方面，采用两种不同存储介质时的时间开销差异不大，但是，在第二个阶段的随机读操作方面，采用闪存固态盘时的时间开销，明显要比采用磁盘时的时间开销少很多，这说明固态盘确实可以大幅度提升外部排序的性能。

图[external-sort] 外部排序的I/O模式

10.2    闪存作为介于磁盘和内存之间的缓存

在过去的这些年里，CPU和DRAM内存的带宽都已经增长了指数倍，但是，磁盘的性能却没有获得同步的增长，磁盘的随机访问延迟和带宽，自从1980年以来只提升了3.5倍[AthanassoulisACGS10]。因此，在带宽和随机访问延迟方面，磁盘和内存之间的鸿沟越来越大，磁盘已经成为数据库应用的性能瓶颈。基于闪存的固态盘很好地填补了磁盘留下来的这道鸿沟。相对于磁盘而言，固态盘读写速度快，每字节价格也在逐渐降低；相对于DRAM内存而言，固态盘的价格更低，容量更大。因此，随着固态盘技术的不断发展和成熟，将这种闪存设备纳入到存储体系架构中将会带来较大的收益，即把“CPU高速缓存(cache)-内存-磁盘”这种传统的三层存储体系架构扩展为“CPU高速缓存(cache)-内存-闪存-磁盘”。

10.2.1      典型应用

把基于闪存的固态盘作为介于磁盘和内存之间的缓存，典型的应用包括：

• 作为数据库系统的二级缓存
• 作为数据仓库的更新缓存

此外，FlashStore[DebnathSL10]也是一种用于在磁盘和内存之间的缓存设备，它采用“键/值”形式存储数据。

10.2.1.1       作为数据库系统的二级缓存

文献[CanimMBRL10]提出在数据库管理中，把闪存固态盘作为磁盘和内存之间的缓存层，如果内存视为数据库系统的“一级缓存”，那么，固态盘就可以视为数据库系统的“二级缓存”（和CPU的二级缓存不是一个概念）。在固态盘中缓存频繁被访问的数据，可以减少磁盘I/O。

当前的数据库系统中，内存的配置容量越来越高，数据库服务器中配置几十GB内存已经比较常见。这可能会给人造成一种错觉，认为内存已经足够大，足以用来存储数据库中被频繁访问的数据。实际上，这种错觉的形成是因为忽略了另外一个重要事实，那就是磁盘中保存的数据也在迅速膨胀。在电信、金融、气象、物流、零售等领域，每天都有海量的数据生成，包括中国移动在内的各个电信企业的日常运营数据都在TB级别以上。可以说，内存容量增加的步伐远远落后于海量数据的增加步伐，面对磁盘中的海量数据，内存空间仍然显得捉襟见肘。当需要缓存的、频繁访问的数据集的大小，超过内存中为数据库开辟的缓冲区大小时，物理I/O就会稀疏地分布到大量不同的磁盘页中，这就意味着，没有什么数据局部性可以让缓存得以有效利用来改善数据库性能。因此，在内存作为“一级缓存”的基础上，采用容量更大、价格更低的固态盘作为数据库系统的“二级缓存”，具有很强的必要性，可以给数据库系统系能带来明显收益。

当前已经有一些主流商业数据库采用闪存固态盘作为数据库系统的缓存。例如，当数据从磁盘中读取出来时，Oralce Exadata会把热数据页缓存在闪存中[Oracle10]。热数据选择是根据数据类型进行静态选择的，索引比日志和备份具有更高的优先级。类似地，IBM DB2的扩展缓存原型系统[CanimMBRL10]，提出了一个基于温度感知的缓存策略TAC（Temperature Aware Caching）机制，它依赖于数据访问频率。TAC监测器会连续监测数据访问模式来确定热数据页。热数据页在从磁盘到DRAM缓冲区的路上，会被缓存在闪存缓存中。TAC采用了“贯穿写”（write-through）策略，即当一个脏页被从DRAM缓冲区中驱逐出来时，它会被同时写入到闪存缓存和磁盘中。

         Canim等人[CanimMBRL10]在IBM DB2数据库上面运行TPC-C负载，并且跟踪记录了物理I/O请求在磁盘页中的位置分布情况（如图[warm-cold-page]所示）。根据对记录结果的观察，他们发现一个比较有趣的结果：如果数据访问被分组成连续的、固定尺寸的物理存储区域（或称为数据区域），那么，就会存在“温区”和“冷区”。温区对应着的数据会被适度频繁地访问，但是不足以频繁到需要放入到RAM缓存中，能够进入RAM缓存的数据都是被非常频繁访问的热数据。冷区中的数据，或者是访问不频繁，或者是数据太大以至于单位区域内的访问频度就显得相对较低。

图[warm-cold-page] 在TPC-C负载下一个磁盘页的访问情况统计

作者对温区和冷区进行实时的温度监控，也就是统计每个数据区域的访问频度、最后访问时间等信息，用作固态盘缓存的替换算法的依据。如果一个页来自温区，就把它放入到固态盘缓存中。一个来自冷区的页也有可能会被放入到缓存中，但是前提是它不能替换缓存中来自温区的页。由于温区和冷区是以一个区域为统计单位，而不是以单个页为统计单位，因此，某个页的相关访问信息都会统计到它所属的区域上面。以区域为单位统计访问信息，相对于以页为单位统计访问信息的优点是：（1）统计信息消耗的空间更小；（2）同一个区域中，对某个页面p的相邻页面q的访问，可能会增加对p访问的机会，把p提前放入缓存会带来收益，但是，采用传统的基于页的统计方法时，由于p没有被访问过，就会一直是个冷页，无法进入缓存；采用基于区域的统计方法后，访问p的相邻页q后，访问次数是增加到区域上面，这会使得区域温度升高，由此，属于该区域的页p也会成为温区中的页，从而获得更多的进入固态盘缓存的机会。

图[SSD-as-second-level-cache]显示了采用固态盘作为数据库系统的二级缓存的体系架构，由磁盘存储数据库的所有数据，用内存缓冲区存储最频繁访问的热数据，用固态盘缓冲区存储被适当频繁访问的温数据，并设置一个基于温度的替换模块实现对两个缓冲区中的数据的管理和替换。当CPU需要读取数据页p时，首先需要查找内存缓冲区，如果p在内存缓冲区中，就直接从内存读取数据。如果p不在内存缓冲区中，这个读请求会被转交给固态盘缓冲区代理。代理去到内存中查找哈希表来判断p是否在固态盘缓冲区中，如果在，p就会被读入到内存缓冲区中；如果不在，就从磁盘中读取p，并同时把p的一个副本传送给基于温度的替换模块。替换模块会确定是否用p来替换固态盘缓冲区中的页（假设之前缓冲区已经填满），如果p比固态盘缓冲区中当前最冷的干净页的温度还要高，则把它写入到固态盘缓冲区中。内存中保存了一个哈希表，记录了每个数据区域的温度信息，替换模块可以快速获得各个页所属区域的温度信息。为了迅速找到最冷的页，系统为所有在缓存中的页维护一个堆栈，以温度为基础组织堆栈中的页，这样，寻找最冷页的平均时间就是堆栈中页的数量的对数。数据页的更新会首先发生在内存缓冲区中，当内存缓冲区中的页被更新时，它会被标记为脏页。一旦脏页被驱逐出内存缓冲区，则必须把它同时写入到磁盘和固态盘缓冲区中。

         基于温度的替换模块需要根据温度统计信息来确定被驱逐的页，温度信息是以数据区域为单位进行统计，并以哈希表的形式保存在内存中，哈希表中记录了在过去时间内所有访问过的数据区域的温度信息。系统会实时维护各个数据区域的温度信息，每当一个页被从固态盘或磁盘中读取时，它的标识符也会被传输给基于温度的替换模块，从而更新温度信息。为了能够反映负载访问模式随着时间变化的情况，作者对温度信息采用了标准的老化策略[ZhouCL04]，即在经过一定次数的访问以后，就对所有页的温度值进行折半处理，从而使得历史数据的重要性要比近期新鲜数据的重要性低一些。

图[SSD-as-second-level-cache] 把固态盘作为数据库系统的二级缓存时的体系架构

10.2.1.2   作为数据仓库的更新缓存

         文献[AthanassoulisACGS10]提出了采用固态盘作为数据仓库的更新缓存，用来存储数据仓库的实时更新数据。随着市场竞争的加剧和企业应用的不断发展，传统的数据仓库已经无法很好地满足企业的日常应用需求。在传统数据仓库中，OLTP系统中的数据是以一定的周期（每周一次或每月一次）批量加载到数据仓库中的，分析人员对大量历史数据进行汇总后得到有价值的信息，从而辅助管理者做出企业决策。但是，目前快速变化的市场环境，要求管理者必须能够及时获得各种OLTP系统中的数据，做出实时决策，尽量避免错过商机。因此，实时数据仓库已经成为越来越多的企业的必然选择。实时数据仓库要求采用CDC（变化数据捕捉）方法，从OLTP系统中实时捕捉变化数据，并立即传播到数据仓库中。数据仓库当前主要保存在磁盘中，而且，数据仓库拥有海量的数据，在未来一段时间内，仍然会把磁盘作为首要存储设备。磁盘将会同时承受来自实时数据仓库应用的两种典型负载：查询负载和更新负载。查询负载主要是对数据表的顺序扫描，而更新负载则是大量的随机写操作。这两种负载同时存在于磁盘中，而且磁盘采用的是就地更新的方式，这必然会导致数据的读写冲突，恶化查询性能和更新性能。因此，把更新操作单独保存到独立于磁盘的其他存储介质上，可以很好地解决该问题。由于内存容量有限而且价格昂贵，不适合作为大量更新操作的缓存。而且，如果把大量的内存分配给数据仓库作为更新缓冲区，会明显恶化查询操作的性能，因为，这意味着能够用作频繁访问数据和中间临时数据的缓存会变得更少，而为频繁访问数据和中间临时数据提供缓存，是提升数据仓库性能的关键措施。因此，闪存设备很自然就成为一种理想的选择。文献[AthanassoulisACGS10]提出采用闪存设备对更新进行缓冲，核心思想是：(1)在一个闪存的缓冲区中对到达的更新进行缓存；（2）在查询过程中即时考虑这些被缓存的更新，从而使得查询可以看到最新的数据；（3）当缓冲区满的时候，把缓存的更新数据迁移到磁盘中。

10.2.2    5分钟规则

当把闪存固态盘作为磁盘和内存之间的缓存时，需要把一些数据放置到固态盘中。一般而言，把数据放到固态盘中是基于以下其中一种考虑因素：

（1）保证响应时间：固态盘比磁盘的访问速度快许多，对于一些对响应速度要求比较高的数据，可以考虑放入到固态盘中，从而提高针对这些数据的读写速度；

（2）获得经济收益：在一个存储设备上的数据访问代价可以用“每秒每次访问的价格”来衡量，而固态盘的数据访问代价要比磁盘低许多，因此，把频繁访问的数据放入到固态盘中，可以明显降低数据访问代价，带来经济收益。

出于第一种考虑因素的情形，相对较少，大部分情形都是基于第二种考虑因素，即目的在于获得经济收益。以获得经济收益为目的时，需要把频繁访问的数据放入到固态盘中，那么，到底应该把什么访问频度（即多长时间访问一次）的数据放入固态盘呢？著名的“5分钟规则”[GrayP87]可以很好地回答这个问题。“5分钟规则”解决了把什么访问频度的数据放入内存的问题，其中，内存被视作存储在磁盘中的数据的缓存。当我们把固态盘视作存储在磁盘中的数据的缓存时，“5分钟规则”同样可以解决把什么访问频度的数据放入固态盘的问题。

“5分钟规则”是由Gray和Putzolo在1987年提出的[GrayP87]，并在1997年做了修改和更新[GrayG97]。在Gray和Putzolo的方法中，首先比较两个方面的代价：（1）把一个记录（或者页）永久存放在内存中需要的代价；（2）每次访问这个记录（或者页）进行磁盘I/O操作的代价。在比较之后就可以做出决定，把什么访问频度的数据放入内存，从而进一步确定合理经济的设备购买预算，即在总的设备购买预算中，为内存和磁盘分配多少购买预算。Gray和Putzolo的方法的计算结果，与磁盘和内存的价格、带宽、容量等参数的具体值有关，不同的设备性能和价格参数，会得到不同的结果。二人当时在1987年采用的是Tandem公司的计算机设备，根据这些设备性能和价格参数得到的结果是400秒，即把那些访问频度超过“每400秒被访问1次”的数据放入内存，为了便于问题阐述，二人把400秒简化成5分钟，由此得到“5分钟规则”。下面简单了解一下Gray和Putzolo在1987年是如何计算得到“5分钟规则”的，计算过程采用的是当时的设备性能和价格参数[GrayP87]。

一个磁盘一般每秒钟可以处理15个随机访问，磁盘的价格在15K美元左右，因此，每秒钟每个磁盘访问的价格就是1K美元，即磁盘访问代价是1K美元/访问/秒。为了支持磁盘数据访问所需要的额外的CPU和通道的开销大约是1K美元，即1K美元/访问/秒。因此，磁盘访问的实际代价是2K美元/访问/秒。一个1MB的内存的开销大约是5K美元，因此，1KB内存的开销大约是5美元。如果把1KB的数据保存到内存中，就不再需要访问磁盘，可以每秒节省一次磁盘访问（Tandom中一次磁盘访问可以传输4KB数据，因此，从磁盘读取1KB数据只需要一次磁盘访问），也就节省了2K美元的开销，所需要的开销只是5美元的内存开销。由此，可以计算得到收支平衡点是：每隔2000/5=400秒访问一次。因此，对于任何1KB的记录，如果被访问的频度大于每400秒（或简化成5分钟）被访问一次，就应该放入内存。

收支平衡点不仅和设备的性能和价格相关，而且与页的大小相关，页越大，收支平衡点越小，反之，则越大，比如对于100字节的页，收支平衡点是1个小时，对于4KB的页，收支平衡点是2分钟。当页的大小超过磁盘每秒传输数据量时，比如，一个页是100KB，而磁盘每秒只能传输4KB数据，这个时候就必须采用实际的磁盘传输数据量作为计算收支平衡点的依据，而不是采用页的大小作为计算依据。

Gray和Putzolo在1997年对“5分钟规则”进行了修改补充，并给出了收支平衡点的计算公式[GrayG97]：

BreakEvenIntervalinSeconds= (PagesPerMBofRAM / AccessesPerSecondPerDisk) × (PricePerDiskDrive / PricePerMBofRAM)。

其中，PagesPerMBofRAM表示1MB的RAM内存所包含的页的数量，AccessesPerSecondPerDisk表示计算机设备中每个磁盘每秒钟可以处理的随机访问次数，PricePerDiskDrive表示每个磁盘的价格，PricePerMBofRAM表示1MB的RAM内存的价格。

Gray和Putzolo采用1997年的DELL TPC-C测试基准的相关设备参数进行了收支平衡点的计算，具体参数如下：

PagesPerMBoIRAM = 128 pages/MB（每页大小是8KB）

AccessesPerSecondPerDisk = 64 access/sec/disk

PricePerDiskDrive = 2000美元/disk (9GB + controller)

PficePerMBofRAM = 15 $/MB_DRAM

基于上述设备性能和价格参数计算得到的收支平衡点是266秒（大约是5分钟）。

“5分钟规则”是和具体的设备性能和价格参数相关的，只有在特定参数下，收支平衡点才会是5分钟。随着制造工艺的不断提高，磁盘和内存的性能在不断改善，价格也在不断下降，导致设备性能和价格参数都在不断变化，因此，5分钟规则适用的情形也会不断变化。当要求收支平衡点大约是5分钟时，在不同时期，需要采用的页面大小也不同。在1987年，以当时的设备性能和价格，页面大小是1KB时，收支平衡点大约是5分钟；在1997年，页面大小是8KB时，收支平衡点大约是5分钟；而在2007年，Graefe 根据当时的设备性能和价格参数，计算得到的结果是，当页面大小是64KB时，收支平衡点大约是5分钟（334秒）[Graefe07]。Graefe认为，5分钟规则对于页面大小在64KB以上的闪存固态盘是可以适用的。

“5分钟规则”只是一种确定数据放置策略的理论名称，并非一定要求收支平衡点是5分钟，在实际应用中，可以根据“5分钟规则”理论的收支平衡点计算公式，计算出把什么访问频度的数据放入闪存固态盘。

10.2.3      FaCE

Kang等人[KangLM12]提出了FaCE（Flash as Cache Extension），它把闪存作为一个可恢复数据库的扩展缓存，不仅可以改进事务吞吐量，而且可以缩短从系统失败中恢复的时间。FaCE采用了两种新的算法来管理闪存缓存中的数据页，即多版本FIFO（First In First Out）和小组二次机会策略。FaCE是在开源数据库PostgreSQL的基础之上实现的，在TPC-C测试基准的大量实验发现，对于一个OLTP应用而言，如果使用少量闪存作为数据库系统的缓存，甚至要比把数据库内容全部存放到闪存中具有更高的性能。

10.2.3.1       相关研究工作的不足之处

Canim等人[CanimMBRL10]针对IBM DB2数据库提出的扩展缓存原型系统，采用了贯穿写的策略，当一个脏页被从DRAM缓冲区中驱逐出来时，它会被同时写入到闪存缓存和磁盘中，由此可以看出，闪存缓存只是为读操作提供了缓存效果，却并没有减少磁盘写操作的数量。此外，在闪存中持久性地维护缓存元数据的高昂代价，也恶化了系统整体性能。

惰性清洗方法——LC（Lazy Cleaning），是另外一种可以考虑的缓存方法。在这种方法中，在数据页从DRAM缓冲区出来到磁盘的路上，会被拦截下来放置到闪存缓存中，如果该数据页是脏的，就采用“回写”（write-back）策略，即采用一个后台进程，当脏页的数量超过预设的门槛值的时候，就把脏页从闪存刷新到磁盘。LC方法使用LRU-2替换算法来管理闪存缓存，因此，替换闪存缓存中的一个数据页，会引起许多随机读和随机写操作。此外，由于不能把闪存缓存融入到数据库恢复机制中，因此，就需要采用检查点机制不断把闪存缓存中的脏页更新到磁盘。而已有研究显示，检查点的额外代价是非常高的。

另外，上述方法通常需要探测确定冷热数据，或者通过静态统计工具，或者采用运行时监测方法，但是，无论哪种方法都存在一些缺点。静态方法无法处理访问模式的变化；动态方法具有较高的运行时开销，并且需要在磁盘和闪存之间迁移数据，而且，当工作负载是更新操作比较集中时，动态方法不会取得好的效果。

10.2.3.2       FaCE的设计思想

FaCE的基本设计思想是，使用一种统一的方式而不需要人工方法（比如使用静态统计工具）或者算法（比如运行时监测）的干预，来确定把哪些数据放置到哪个设备上，从而构建一个有效的、由磁盘和闪存构成的混合存储系统。因此，FaCE提出把闪存固态盘用作DRAM缓冲区的一个扩展缓存，这样它就可以和DRAM缓冲区自身的数据页替换机制一起工作，而不需要提供额外的机制来区分确定冷数据和热数据，也不需要监测数据访问模式，因此，只需要很少的运行时开销，未来数据访问模式的预测质量也不会对结果产生影响。

FaCE可以克服上面介绍过的其他方法存在的两个不足之处：（1）其他方法没有减少磁盘写操作的数量；（2）其他方法没有把闪存缓存纳入数据库恢复机制。具体而言，FaCE可以做到以下三点：

第一，FaCE实现了闪存写操作优化以及磁盘访问的减少。DRAM缓冲区通常会为写操作和顺序访问操作提供同样的性能。和DRAM不同的是，闪存的性能会随着操作类型（读或写）和数据访问模式（顺序访问呢或随机访问）的不同而表现出较大的差别。对于许多现在的闪存固态盘而言，随机写操作要比顺序写操作慢大约一个数量级。FaCE提供了闪存感知的策略来管理闪存缓存，它可以被设计成完全独立于DRAM缓冲区管理策略。FaCE会把小的随机写转换成大的顺序写，因此可以充分利用闪存的高顺序带宽和内部并行性，从而实现高吞吐量。在FaCE中，当一个冷数据页被驱逐出DRAM缓冲区的时候，它可能获得第二次机会，继续停留在闪存缓存中一段时间。如果这个冷数据页停留在闪存缓存中时再次变得热起来，就可以快速地从闪存缓存中直接交换回DRAM缓冲区，而不需要从磁盘中读取。如果一些数据页确实是冷的，并且长期内都没有再被访问，那么，它最终就不会被DRAM缓冲区或者闪存缓存所保存。可以看出，FaCE可以有效减少磁盘访问，并且可以优化写操作性能。

第二，FaCE充分利用了闪存的非易失性，对数据库持久性的范畴进行了扩充，包含了闪存缓存中的数据页的情形。一个数据页被从DRAM缓冲区中驱逐出来，如果进入闪存缓存中，则也会被认为已经被持久地保存到数据库中。因此，闪存缓存中的数据页，可以用来最小化系统恢复开销，加速系统从失败中恢复的过程，并且以最低的代价获得事务原子性和持久性。在恢复期间需要访问到的大多数数据页，都可以在闪存缓存中得到，这就可以明显减少系统恢复时间。FaCE恢复管理器提供的机制，可以完全支持数据库恢复和持久性元数据管理。

第三， FaCE是一个具有较低开销的框架，因为，它使用闪存驱动器作为DRAM缓冲区的扩展，而不是作为磁盘的替代品。闪存的这种使用方式是和DRAM缓冲区紧密耦合的，闪存缓存管理和DRAM缓冲区管理可以很好地一起工作。FaCE不需要人工或者算法的方法从冷数据中剥离出热数据，因此，运行时的开销是非常低的。FaCE并不会增加磁盘的通信量，因为，它不会为了更高的缓存命中率而在闪存和磁盘之间迁移数据。

10.2.3.3       FaCE的基本框架

图[FaCE-overview]给出了FaCE的基本框架，从中可以看出，在这种混合存储系统中，闪存充当了DRAM缓冲区的扩展缓存。FaCE的不同组成部分之间的交互情况，具体如下：

• 当数据库服务器请求一个数据页时，如果该页不在DRAM缓冲区中，就到闪存缓存中搜索。DRAM缓冲区维护了一个关于闪存缓存中所有页的列表信息，可以支持快速查找。如果这个页在闪存中，就从闪存中读取；否则，就从磁盘中读取。
• 当一个页被交换出DRAM缓冲区的时候，需要根据不同的情形采取不同的动作，这主要取决于这个页是脏页还是干净页。如果它是干净页，就会被直接丢弃或者被保存到闪存缓存中。如果它是一个脏页，就会被回写到闪存或者磁盘，或者同时回写到闪存和磁盘中。
• 当一个页被交换出闪存缓存时，也需要根据不同的情形采取不同的动作，主要取决于该页是脏页还是干净页。如果它是干净页，这个页就会直接被丢弃；如果是脏页，就会被写入到磁盘，除非它在从DRAM缓冲区驱逐出来时早已经写入到磁盘。

         很显然，从上面描述的主要交互过程可以看出，FaCE需要解决的基本问题是，什么时候以及哪些数据应该暂时停留或者离开闪存缓存。有许多方式可以解决这个问题，而且对于数据库的整体性能可能具有很大的影响。例如，当一个数据页发生DRAM缓冲区“脱靶”时（即无法在DRAM缓冲区中找到该页），这个页会从磁盘中被读取出来放入到DRAM缓冲区时，这个时候就不用把该页同时放入到闪存缓存中，因为，当DRAM缓冲区中存在数据副本时，闪存缓存中的副本是不会被访问的。由于这个原因，只有当一个数据页从DRAM缓冲区中被驱逐出来时，才有可能进入到闪存缓存中。可以看出，在这一点上，FaCE和其他把闪存作为缓存的方法具有很大的不同，在其他方法中，一些“温数据页”（不是热数据页）被从磁盘中读取出来以后，可能会被首先保存到闪存缓存中，如果在闪存缓存中停留期间，这个温数据页变成热数据页，该页会从闪存缓存调入到DRAM缓冲区。而在FaCE中，这是不行的，FaCE不允许把一个数据页在从磁盘到DRAM缓冲区的道路上被拦截下来放入到闪存缓存，而只允许一个数据页从DRAM缓冲区到磁盘的道路上被拦截下来放入到闪存缓存，也就是说，当DRAM缓冲区中的一个数据页变成冷数据页的时候，可能会在离开DRAM缓冲区后被拦截下来放入到闪存缓存中。而且，只有通过这种方式进入到闪存缓存中的数据页，以后才可能有机会被再次交换回到DRAM缓冲区中，也就是说，当闪存缓存中的数据页再次变成热数据页的时候，会获得机会被交换回DRAM缓冲区。

图[FaCE-overview] FaCE的基本框架

10.2.3.4       FaCE的设计策略

FaCE必须要解决三个方面的设计问题：第一，当一个被从DRAM缓冲区驱逐出来以后，必须同时写入到闪存缓存和磁盘，还是只需要写入到闪存呢？第二，采用什么样的闪存缓存管理策略？第三，当一个数据页被从DRAM缓冲区驱逐出来时，是否要对脏页和干净页进行区分对待？

（1）采用回写策略而不是贯穿写策略

当一个脏页被从DRAM缓冲区中驱逐出来的时候，可以选择两种写入策略，即贯穿写（write-through）和回写（write-back）。所谓的贯穿写是指，把该页同时写入到磁盘和闪存缓存中，而回写则是指只被写入到闪存缓存中。当采用贯穿写方式时，可以保证磁盘和闪存缓存二者都获得最新版本的数据页；当采用回写方式时，只有闪存缓存获得了最新版本的数据页，而磁盘中的数据页原始版本并没有发生变化，这意味着磁盘中包含的是过期的数据页，直到闪存中的数据页被驱逐出来写入到磁盘中时，磁盘才可以获得最新版本的数据页。

对于读操作而言，上面这两种方式在效果上是等价的。但是，对于写操作而言，在许多情形下，贯穿写的代价明显要高于回写的代价。这里分两种情形来讨论：

第一种情形：在一段时期内，一个脏页只被读入DRAM缓冲区中一次，然后被驱逐出DRAM缓冲区以后，再也没有被访问。在这种情形下，如果采用贯穿写，当该脏页被从DRAM缓冲区中驱逐出来时需要写入到闪存和磁盘，就会包含一个闪存写操作和一个磁盘写操作；而如果采用回写方式，则需要暂时把该该脏页放入闪存缓存，这时需要一个闪存写操作，由于此后一段时间都没有被再次使用，该页变成冷页，会被驱逐出闪存缓存，写入到磁盘，这时又会产生一个磁盘写操作。可以看出，在这种情形下，两种写方式都包含一个闪存写操作和一个磁盘写操作，二者代价是相同的，只不过对于回写方式而言，磁盘写操作并没有和闪存写操作同时发生，而是延迟一段时间才执行磁盘写操作。

第二种情形：在一段时期内，一个脏页被驱逐出DRAM缓冲区，后来又变成热数据页再次被读入DRAM缓冲区，而且这种情况反复发生多次，最后一次才彻底变成冷数据页被最终写入到磁盘，假设总共被从DRAM缓冲区中驱逐了N次。对于这种情形，如果采用贯穿写策略，每次当这个脏页被从DRAM缓冲区中驱逐出来时，都需要一个磁盘写操作和一个闪存写操作。而如果采用回写策略，它会把数据页先放入闪存缓存，变成热页时，直接从闪存缓存交换回DRAM缓冲区，如此多次反复，直到最终彻底变成冷数据页后才被从闪存中驱逐出来写入到磁盘。可以看出，采用回写方式，只需要N次闪存写操作和一次磁盘写操作，而贯穿写则需要N次闪存写操作和N次磁盘写操作。也就是说，采用回写方式明显减少了写操作代价。出于这个原因，FaCE采用了回写策略，而不是贯穿写策略。

（2）基于多版本FIFO的替换

闪存缓存空间是有限的，在对闪存缓存进行管理时，很容易想到利用LRU（Least Recently Used）替换算法。尽管LRU算法是一种被DBMS广泛采用的缓存管理策略，但是，对于闪存缓存而言，并不能获得好的性能。LRU算法会为闪存缓存中的所有数据页构建一个LRU链表，链表的MRU位置存放了最近被访问过的页，链表的LRU位置存放了距离当前时间最远的被访问过的页。在选择驱逐页时，算法会在LRU链表的LRU位置选择一个页作为驱逐页，而不会考虑该页在闪存中的物理位置。这就意味着，每个页替换都会引起一个闪存随机写操作。对于闪存而言，随机写这种模式相对而言是效率较低的，涉及较大的执行代价，通常比顺序写操作慢一个数量级，因为，随机写操作会引起后续的许多垃圾回收和块擦除操作。

因此，FaCE没有采用LRU算法来管理闪存缓存，而是采用了FIFO（First In First Out）策略的一个变种——多版本FIFO。虽然FIFO策略通常被认为性能不如LRU算法，但是，FIFO策略有其自己独特的优点，使得它被应用到闪存缓存机制中时可以获得较好的性能。因为，在FIFO策略中，所有新到达的数据页都会追加的方式、被顺序地压入到闪存缓存队列的尾部，这就意味着，所有的闪存写操作都是顺序写操作。FIFO所表现出来的这种独特的写模式，和闪存特性非常匹配，可以帮助闪存缓存产生较好的性能。

多版本FIFO和传统的FIFO策略不同的地方在于，FIFO策略只允许在队列中存在同一个数据页的唯一副本，而多版本FIFO策略则允许一个数据页的一个或者多个版本同时存在于闪存缓存中。在多版本FIFO中，当需要替换闪存缓存中的数据页时，会从闪存缓存队列头部选择一个驱逐页，新进来的数据页直接放入到闪存缓存队列的尾部。接下来，一个页是干净页还是脏页，会引起不同的操作。如果进来的数据页是脏页，那么，它就会被无条件地压入队列，不会采取额外的操作来移除可能存在的之前的版本，从而不会引起随机写操作。如果进来的数据页是干净页，那么，只有闪存缓存中还不存在这个页的同样副本，才可以把这个页放入队列。一个数据页从闪存缓存队列中移除时，它被写入到磁盘的前提条件是，该页是脏页，并且是闪存缓存中的最新版本，这样做可以避免冗余的磁盘写操作。

多版本FIFO还采用和二次机会同样的策略，即当一个有效页被驱逐出闪存缓存时，如果这个页在停留在闪存缓存期间时已经被访问过，它会被给予第二次机会，而不是被丢弃（对于干净页而言）或者刷新到磁盘（对于脏页而言）。

（3）缓存干净页和脏页

实际上，对于一个数据页而言，如果它是干净页，被放置到闪存缓存中以后，只要被访问过一次以上，就可以获得收益。比如说，对于一个干净页p而言：

（a）把页p放入闪存缓存时的读取代价：在采用回写策略时，数据页p被驱逐出DRAM缓冲区时，首先被放入闪存缓存，需要一个闪存写操作，读取数据页时需要一次闪存读操作，最终在某个时刻被驱逐出闪存缓存时，由于是干净页，可以直接丢弃，不用写入磁盘。因此，总代价是一个闪存写操作和一个闪存读操作。

（b）不采用闪存缓存的读取代价：当数据页p被驱逐出DRAM缓冲区时，由于是一个干净页，则可以直接丢弃，不用写入到磁盘，当需要读取这个页时，需要从磁盘中读取该页，需要一个磁盘读操作。因此，总代价只包括一个磁盘读操作。

对于现在的绝大多数闪存固态盘产品和磁盘产品而言，一个磁盘读操作的代价，要高于一个闪存写操作和闪存读操作代价之和。所以可以得出结论，干净页被放置到闪存缓存中以后，只要被访问过一次以上，就可以获得收益。

由此可以认为，是否缓存一个干净页，应该根据这个页被缓存以后到它被驱逐出缓存之前，再被访问至少一次的可能性有多大。

对于一个脏页而言，当它被驱逐出DRAM缓冲区时，把它保留在闪存缓存中总是可以带来收益的。因为，如果不保存到闪存缓存，就会立即引起一个磁盘写操作。此外，上面曾经讨论过一种情形，即在一段时期内，一个脏页被驱逐出DRAM缓冲区，后来又变成热数据页再次被读入DRAM缓冲区，而且这种情况反复发生多次，最后一次才彻底变成冷数据页被最终写入到磁盘。对于这种情形而言，采用回写策略把脏页缓存到闪存中，可以把许多次磁盘写操作转变成闪存写操作，大大提高了系统整体性能。因此，当采用回写策略时，脏页应该比干净页具有更高的优先级进入到闪存缓存中。因此，FaCE采用了多版本FIFO策略，允许一个数据页的多个版本进入闪存缓存。

10.2.3.5       FaCE的恢复

对于数据库系统而言，一旦发生系统失败，必须保证数据库能够恢复到一致的状态，从而保证事务的原子性和持久性。数据库恢复机制中的关键技术就是“写前日志”，即在事务提交之前要求必须把日志“强制写入”到稳定的存储介质上。对于FaCE而言，当一个脏页被从DRAM缓冲区中驱逐出来的时候，它的所有日志记录都会被写入到稳定的存储器上（闪存或者磁盘）。就事务的持久性而言，一旦一个脏页被写入到磁盘或者闪存中，这个页就被认为已经永久性地保存到了数据库当中，因为，磁盘和闪存都是非易失性的存储介质。对于FaCE系统而言，闪存的非易失性保证了，在发生系统失败的时候，总是有可能从闪存缓存中恢复数据。因此，FaCE利用了存储在闪存缓存中的数据页，来服务于双重目的，即缓存扩展和数据库恢复。

在FaCE中，当发生数据库的恢复时，存储在闪存缓存中的数据页可能比磁盘中的页的版本更新，这个时候，恢复数据库一致性就必须使用闪存缓存中的数据页。即使闪存和磁盘中的数据页是完全同步的，也应该使用闪存缓存中的数据页，因为闪存比磁盘的访问速度更快。

图[FaCE-recovery] FaCE的元数据维护

这里唯一需要处理的问题就是，要保证在系统发生失败的时候，与闪存缓存相关的元数据能够存活下来。否则，如果丢失了元数据，当系统重启的时候，将无法从闪存缓存中获得相应数据，数据库就无法恢复到一致性状态。

图[FaCE-recovery]显示了FaCE的元数据维护方法。在FaCE中，每条元数据包含了三个属性，即page_id, pageLSN和flag，其中，page_id表示页编号，pageLSN表示页的逻辑扇区编号，flag是一个标记位，用来表示该页是否在闪存缓存中。元数据的变化会被收集在内存中，并且作为一个个较大的分段持久性地写入到闪存缓存中。这种类型的元数据管理对于FaCE而言是比较高效的，因为，进入一个闪存的数据页总是以时间顺序被放入到队列的末端，它的元数据目录也是如此，而且，元数据是以分段的形式批量更新到闪存中，而不是一条条元数据分次更新。但是，需要指出的是，由于系统发生失败的时候，仍然会有少量元数据在内存中，这些内存中的元数据就会发生丢失。不过这个不会成为问题，因为，这部分元数据只对应着闪存缓存中的少量数据页，因此，只需要扫描闪存中的一少部分数据页，就可以快速恢复系统。

10.3    基于数据访问模式的混合存储系统

在未来较近一段时期内，磁盘仍将是企业应用的主要数据存储介质，但是，随着闪存技术的不断发展，闪存设备已经表现出逐步取代磁盘的趋势。在这个取代的过程中，一种比较大的可能性是，闪存设备和磁盘在一段时期内共存，在存储的层级结构中处在同一个级别上，共同构成混合存储系统。

10.3.1      基于对象放置顾问的混合存储系统

文献[CanimBMLR09]指出，如果固态盘和磁盘一起组成混合存储系统，把随机访问的数据转移到固态盘中，留在磁盘中的数据通常都是顺序访问的，那么，就可以获得明显的性能收益，主要包括以下几个方面：

（1）提高了数据库系统的整体性能：通过把那些频繁地、以随机方式被访问的数据存储到固态盘上面，可以大幅改善随机操作的性能，因为，固态盘不存在机械部件，随机访问速度要比磁盘快。

（2）提高了采用“短行程”策略的磁盘的空间利用率：在一些企业级的数据库系统实施方案中，为了提升数据库的性能，会采用 “短行程”（short-stroking）策略，即有意只使用磁盘存储空间的一部分来存储数据库数据，从而使得寻址时间尽量小，保证系统响应时间，这种以牺牲存储空间来换取高性能的做法在特定应用场合下是比较经济高效的。如果需要更多的存储空间，就需要不断增加磁盘，而不是使用磁盘中剩余的可用空间。由于多个磁盘的磁头可以并行寻址，因此，仍然可以获得较好的性能。很显然，采用 “短行程”（short-stroking）策略后，磁盘空间利用率较低。如果采用固态盘和磁盘的混合存储系统，则可以有效改善磁盘空间利用率。因为磁盘中保留下来的数据大都是顺序访问的，而磁盘具有很高的顺序访问吞吐量，顺序访问数据不需要增加额外的寻址开销，因此，在限定的系统响应时间内，就可以顺序访问更多的数据，从而可以更多地利用“短行程”策略中剩余的磁盘空间，提高了采用“短行程”策略时的磁盘空间利用率。

（3）减低了能耗：随机负载被分流到固态盘以后，就减轻了磁盘的负担，继而降低了系统总体能源开销，因为固态盘比磁盘更加节能。

虽然把数据存放到固态盘中可以带来明显的收益，但是，毕竟固态盘空间是有限的，只能把一部分数据存储带固态盘中，因此，就涉及到数据放置策略问题，即把哪些对象放置到固态盘中可以最大程度地改进系统的性能。文献[CanimBMLR09]提出了一个工具称为“对象放置顾问”，用来明智地确定数据对象的存放位置。通过收集负载信息，对象放置顾问会使用启发式算法（比如贪婪算法或动态规划算法），来确定需要放置到固态盘中的对象的列表。

         对象放置顾问生成最优的数据放置策略的过程包括两个阶段：特征提取阶段和决策阶段。在特征提取阶段可以获得数据对象在运行时的访问特征统计信息，利用这些统计信息就可以计算出把一个数据对象从磁盘转移到固态盘中可以带来的性能收益。决策阶段根据这些性能收益数据生成对象放置计划。图[object-placement-advisor]给出了对象放置顾问的工作原理。数据库引擎负责处理来自各种应用的查询负载，附着在数据库引擎上面的缓冲区监控工具，执行特征提取任务，它会不断监控记录各种性能指标，包括一个页从磁盘读取到内存缓冲区所消耗的时间，以及把一个脏页写回到磁盘所消耗的时间等等。各种监控到得性能指标数据（特征信息）会被传送给对象放置顾问。对象放置顾问就会根据这些特征信息，生成一个“代价-收益图”，显示在不同的存储空间容量限制下不同的放置策略所带来的相应的性能收益。数据库管理员就可以参考“代价-收益图”来决定需要购买多大容量的固态盘。对象放置顾问还可以生成候选放置对象列表，具体方法是：根据提取到得工作负载的特征信息和设备的特性信息，计算每个对象的预期的性能收益，除以对象的尺寸后得到单位尺寸的性能收益，对不同的对象按照单位尺寸性能收益进行降序排序；然后，使用一个启发算法从高到低依次选择数据对象，直到没有更多的对象可以放置到固态盘空间中；最终，这些被选中的对象就构成了候选放置对象列表。数据库管理员可以根据候选放置对象列表，把相关的数据对象从磁盘转移到固态盘上面，从而获得较好的性能收益[CanimBMLR09]。

图[object-placement-advisor] 对象放置顾问示意图

但是，正如作者在其后续研究工作[CanimMBRL10]中指出的那样，基于对象放置顾问的混合存储系统具有下面的缺陷：

• 用户必须运行一个负载特征提取工具来获得统计数据，并且，随着数据在固态盘上的反复进出，又要重新进行代价昂贵的特征提取；
• 对象放置决定是以整个表或索引为粒度，而在一些情况下，只有表中的一部分数据是被频繁访问的，我们可能只希望把表中的一些片段放入固态盘。

10.3.2      基于双状态任务系统的混合存储系统

文献[KoltsidasV08s]提出在存储层次结构的同一个层面同时使用闪存和磁盘的混合存储系统。图[flash-and-HDD-hybrid-system]显示了闪存和磁盘混合存储系统的体系架构。缓冲区管理负责对分配给数据库使用的内存缓冲区进行管理和维护，这个过程需要调用高效的替换算法。存储管理器负责根据具体的负载情况来确定一个页的最优存放位置，或者放入磁盘中，或者放入闪存设备中，但是，在某一个时刻，一个数据页只能存在于其中一种存储介质中。其中，如果一个页具有比较集中的读操作负载，它会被写入到闪存中，而对于具有比较集中的写操作负载的页，则会被写入到磁盘中。通过这种方式，读操作的速度要比只采用磁盘的系统快，写操作的速度要比只采用闪存的系统快。作者设计了一系列在线算法，可以确定一个页的最优放置方式，从而可以根据工作负载的变化动态决定数据页的存放位置。

图[flash-and-HDD-hybrid-system] 闪存和磁盘混合存储系统的体系架构

混合存储系统中需要解决两个关键难题：（1）如何根据历史负载模式来预测一个页的未来负载，如果预测不准，就会带来大量不合理的I/O开销；（2）当一个页的负载模式发生变化时（比如，从读操作比较集中的负载变成写操作比较集中的负载，或者反过来），如何自适应地调整这个页的放置位置。

对于未来负载模式预测问题，作者为一个页建立了负载跟踪记录，并设计了相应的缓冲区替换策略，可以根据历史负载情况合理确定替换页，从而让未来可能使用到的页最大可能性地保留在缓冲区中。

         对于把一个页放置在闪存还是磁盘中这个问题，作者把它建模成一个双状态任务系统[BorodinLS87]。如图[two-state-task-system]所示，双状态任务系统包含了两个状态f和m，其中，f表示数据页在闪存中，m表示数据页在磁盘中。从闪存和磁盘中读取一个页的代价分别是r_f和r_m，把一个页随机写入闪存和磁盘的代价分别是w_f和w_m。从一个状态转移到另一个状态的代价，等于把一个页写入到另一个存储介质的代价，这里之所以不用考虑读取代价，是因为当状态转移发生的时候，即在决定把一个页写入到另一个存储介质的时候，这个页已经被读取出来。对于双状态系统的状态转移问题，已经有不少成熟的研究成果，比如文献[BorodinLS87][BlackS89]，作者采用了和文献[NathK07]类似的在线算法。

图[two-state-task-system] 双状态任务系统示意图

这个混合存储系统的缺陷是：（1）它假设固态盘可以容纳整个数据库，但是，在当前的企业应用中，往往可以提供足够容量的磁盘，而能够提供的固态盘的容量还是有限的；（2）没有区分顺序和随机访问模式。对于磁盘而言，顺序访问模式的代价要比随机访问模式的代价小得多，因此，把所有的访问模式都假设为随机访问模式，会导致数据更容易被存储到固态盘而不是磁盘中；（3）没有考虑垂直分区，而实践已经证明，即使对于传统的磁盘而言，垂直分区都可以明显获得数据库性能的提升。针对这些问题，Clementsen 等人[ClementsenH10]提出了一种基于垂直分区的混合存储系统。

10.3.3      基于垂直分区的混合存储系统

10.3.3.1       系统概述

基于垂直分区的混合存储系统[ClementsenH10]可以有效克服基于双状态任务系统的混合存储系统的一些缺陷，它包括两个分离的子系统，即离线分区系统和在线系统（如图[vertical-partition-for-SDD-HDD]所示）。离线分区系统负责确定应该把数据库的每个列放置在固态盘还是磁盘中。在离线系统确定的分区的基础上，在线系统可以运行查询，但是不会转移数据。在线系统也会收集工作负载的统计信息，在后续进行分区操作时提供给离线系统使用。Clementsen 等人只研究了离线分区，而没有研究实时动态分区，也就是没有设计在线算法根据实时负载特征在磁盘和固态盘之间动态迁移数据库的列。离线系统的主要任务就是确定数据库的列在磁盘和固态盘这两种存储介质上的放置位置，并且在某一时刻，只能存储在其中一种存储介质上。

离线分区系统把数据库和负载统计信息作为输入，然后使用这些信息来把每个数据库列分配给某个存储介质。系统的输出是一个的列到存储介质的映射集合。当后续到达的工作负载和先前用于统计的负载的类型比较类似时，系统就可以获得最优的IO性能。分区算法运行结束后，系统会根据列到存储介质的映射集合，把各个列放置到相应的存储介质中。离线算法运行的频率，取决于许多因素，比如工作负载的变化、数据表的变化以及特定环境的性能需求等。

图[vertical-partition-for-SDD-HDD] 基于垂直分区的混合存储系统

10.3.3.2       离线分区系统

10.3.3.2.1       工作负载统计

为了把数据库分区到两个驱动器中，就需要获得数据库工作负载的统计信息。为了获得关于哪个请求需要IO操作的准确信息，只看数据库事务是不够的，必须同时考虑系统使用的缓存策略，因为，并非所有的读操作都会引发一个磁盘读操作。而且，离线分区系统将会考虑每个列的放置策略，因此，统计信息的粒度是列。换句话说，所需要的统计负载的信息将会包括每个列上的IO请求操作的不同类型的数量。

此外，数据库内容是动态变化的，这也让问题变得更加复杂。例如，一个存储在固态盘上的列可能会随着时间增长。由于固态盘的容量是有限的，因此就很有必要考虑列增长的问题。系统应该尽可能地避免把一个列同时分散在两种存储介质上。列的扩充可以通过在存储介质上扩充列文件来实现。但是，如果列是存储在固态盘上面，并且固态盘已经完全满了，那么，该列后续的扩充内容就会被存储到磁盘上面。这就意味着，一个随着时间不断增加的列，可能会被分散存储到两种存储介质上面，尤其是新增的数据（即那些从数据库被分区以后新增加的数据）可能会被保存到磁盘上，即使离线系统最初把这个列保存到固态盘上。因为一个列新增的页可能会被保存到磁盘上，而这个列原来的数据页被保存在固态盘上，因此，对原来页和新增页进行读写的代价就会不同。为了解决这个问题，系统需要获得每个列原来数据和新增数据的工作负载统计信息。

10.3.3.2.2        NP-完全问题的证明

现在来证明分区问题是一个NP-完全问题，证明的思路是把分区问题转换成背包问题，即证明在分区问题和背包问题二者之间存在一个多项式的映射，而背包问题已经被证明是一个NP-完全问题，因此，可以证明分区问题也是一个NP-完全问题。

这里首先描述一下背包问题，然后说明如何把分区问题映射到背包问题。一旦这个映射构建完成，就可以使用背包问题的已有解决方案来解决分区问题。

（林子雨注：证明内容都是公式，无法粘贴到网页，证明过程略，详细证明过程请参见本专著的PDF文档）

10.3.3.2.3        解决分区问题的动态规划算法

         分区问题就是要确定数据库的列最佳放置位置，即放置到磁盘上还是固态盘上。采用动态规划算法解决分区问题的基本思想是“分而治之”。首先，把一个问题分解成可能的最小子问题，并解决这个较小的问题；然后，使用最小子问题的解，来构建下一个较大问题的解；这个过程一直重复，直到找到原来问题的解。采用这种思路确定数据库列的最佳放置位置的问题，就可以采用下面的方法来解决。首先，把固态盘容量限制为1个页，然后在其中放入一个列集合，并且使得这个集合中的列可以在给定的工作负载下面具有最低的IO总代价。在许多情形下，这时的列集合中可能包含0个列，因为，通常所有的列都大于1个页。然后，我们把固态盘容量增加到2个页，再去做同样的事情。这个过程一直持续，直到我们到达实际的固态盘容量。采用从最小到最大的固态盘容量这种渐进的方式来求解的原因是，当求解更大固态盘容量下的问题时，可以利用基于较小的固态盘容量得到的结果。

10.4    基于语义信息的系统框架hStoreage-DB

Luo等人[LuoLMCZ12]为DBMS存储管理设计和实现了一个基于语义信息的混合存储系统框架hStorage-DB，它定义了对于存储IO而言至关重要的语义信息（比如内容类型和访问模式），并且传递给存储管理层。存储管理层根据收集到的语义信息，把访问请求分成不同的类型，并为每种类型分配一个合适的QoS(Quality of Service)策略，这些策略是被底层的存储系统所支持的，从而使得每个请求都可以由合适的设备来为之提供服务。

10.4.1      其他混合存储系统的不足

混合存储系统需要在闪存和磁盘两种存储介质之间分配数据，可以采用两种方法：（1）基于数据库管理员的方法，根据数据库管理员的知识和经验，在不同的设备之间分配数据；（2）基于访问模式的方法，设计监测程序，探测发现数据访问模式，并根据访问模式确定数据在不同设备之间的分配，前面已经介绍过的多种基于数据访问模式的混合存储系统就采用这种方法。但是，上述两种方法都具有一定的不足之处。

对于基于数据库管理员的方法而言，具有以下局限性：

（1）需要大量的人工操作。数据库管理员必须根据经验知识来人工确定数据在不同设备之间的分配，比如，索引会被频繁地随机访问，有一些小表也会被频繁地使用，由于闪存固态盘具有较高的随机读性能，因此，数据库管理员通常会把索引和小表存储到固态盘中，而其他数据则存放在相对廉价的磁盘设备中。

（2）数据粒度会变得非常粗糙，无法获得好的性能。数据库管理员会同等地对待所有被分配同一个表的请求，但是，对于一个表的不同部分的访问，可能具备不同的访问模式，因此，以表为粒度无法很好地区别一些访问模式。为了改进这一点，数据库管理员可能会尝试把一个表分割成多个分区，对每个分区加以区别对待，但是，这种分区方式往往是一种静态的结果，而实际应用负载的访问模式是不断变化的，因此，这种改进仍然无法保证获得最优的性能结果。

（3）根据负载的访问模式来配置数据放置策略，是一种静态的策略，很难适应IO需求的动态变化。

对于基于数据访问模式的方法而言，特定的访问模式，只有通过一段时间的监测才能观察到，因此，当数据库负载表现出较长时间的稳定性的时候，它可以表现出较好的性能。但是，基于数据访问模式的方法在以下情况下不能获得好的性能：

（1）对于高度动态变化的负载和公用的短生命周期的数据（比如临时数据）来说，根本没有足够长的时间来收集数据和发现正确的访问模式；

（2）在共享缓存设备上的并发数据流之间存在比较复杂的交互，会引起一些不可预测的访问模式，数据访问模式监测方法很难探测发现访问模式，或者探测得到的模式的准确性较低；

（3）无法确定一些重要的信息，比如内容类型和数据生命周期，这些信息是和访问模式无关的，但是，这些信息在混合存储系统中对于做出正确的数据放置策略而言是非常重要的。

10.4.2      hStoreage-DB的设计思路

hStoreage-DB在设计混合存储系统时，采用了不同的思路——基于语义信息的方法，可以克服基于数据库管理员的方法和基于数据访问模式的方法的局限性。

一个数据库的IO请求有不同的语义信息，比如内容类型和访问模式等信息可能都不尽相同。hStoreage-DB会根据请求的语义信息对请求进行分类，然后，为不同类型的请求关联不同的QoS策略，并根据这个请求的QoS策略来选择合适的设备为之提供服务。比如，如果把hStoreage-DB设计成一个包含两级存储架构的系统，即最低层是磁盘，位于磁盘上面的一层是固态盘，作为磁盘的缓存，那么，对于hStoreage-DB而言，为了实现缓存优先级的目的，可以按照以下方式对语义信息进行分类：

• 内容类型：这里主要关注三种内容类型，即常规表、索引和临时数据。常规表定义了数据库的内容，它们消耗了大部分数据库存储空间，索引可以用来加速对常规表的访问，临时数据（比如哈希表）是在一个查询过程中产生的，在查询完成的时候就会被删除掉。
• 访问模式：它指的是一个IO请求所具备的特征，是由查询优化器来决定的。对一个表的访问模式可以是顺序扫描，也可以是随机访问的。对一个索引的访问模式通常是随机访问的。

hStoreage-DB会把对于存储IO而言至关重要的语义信息（比如内容类型和访问模式），和请求一起传递给存储管理层。存储管理层根据收集到的语义信息，会把请求分成以下几个类型：（1）顺序请求；（2）随机请求；（3）临时数据请求；（4）更新请求。然后，上述四种不同类型的IO请求，会被分配不同的QoS策略。

图[hStorage-DB]给出了hStoreage-DB的体系架构，从中可以看出，hStoreage-DB的具体实现过程如下：

• 首先，把那些对于存储IO而言至关重要的语义信息（比如内容类型和访问模式），和请求一起传递给存储管理层。
• 其次，存储管理层接收到一个请求以后，会先查看语义信息，然后根据预先定义的一个规则集合，为不同语义的请求分配不同的QoS策略，并且底层的存储系统可以支持这些QoS策略。然后，一个请求和与之关联的QoS策略一起被发送到底层的混合存储系统。
• 最后，在收到一个请求的时候，存储系统首先提取得到与之关联的QoS策略，然后使用一个正确的机制，根据这个请求的QoS策略来选择合适的设备为之提供服务。

图[hStorage-DB] hStorage-DB的体系架构

10.4.3      hStoreage-DB的技术挑战和解决方案

要向实现上述的设计思路，hStoreage-DB会面临以下两个方面的主要挑战：

• 如何为每个QoS关联一个合适的QoS策略？为了使得混合存储系统能够采用正确的机制为一个请求提供相应的服务，需要设计一些规则来完成从语义信息到QoS策略的高效的映射，即根据收到的请求中包含的语义信息就可以立即找到与之匹配的合适的QoS策略。这里必须系统地考虑多个因素，包括查询类型的多样性，不同查询计划的复杂性，以及并发执行多个查询带来的问题。
• 如何把每个请求的QoS策略传递到底层的混合存储系统？一个DBMS存储管理器通常是一个接口，这个接口会把一个DBMS数据请求转换成一个IO请求。在转换期间，所有的语义信息（比如内容类型和访问模式等）都会被剥离，只会留下一个请求的物理布局信息，包括逻辑块地址、类型（读或写）、大小和实际数据（如果是一个写操作）。这就意味着，在现有的DBMS存储管理器实现方式下，在DBMS和存储系统之间存在一个“语义鸿沟”，无法传递语义信息。

         为了解决第一个挑战，hStoreage-DB针对不同的语义类型设计了5种规则，可以实现从语义信息到QoS策略的快速映射。针对第二个挑战，hStoreage-DB把QoS策略嵌入到原来的IO请求中，并通过一个块接口分发给底层的混合存储系统，存储系统收到请求后，首先提取得到与该请求关联的QoS策略，然后使用一个正确的机制，根据这个请求的QoS策略来选择合适的设备为之提供服务。

10.4.4      QoS策略

10.4.4.1       QoS策略概述

QoS策略为一个存储系统提供了一个高层次的服务抽象。通过一个良好定义的QoS策略，一个存储系统可以有效地提供自己的能力，同时不需要对用户暴露设备层次的细节。一个QoS策略，或者可以是性能相关的，比如延迟和带宽需求，或者也可以是性能无关的，比如可靠性需求。一个存储系统的所有QoS策略，取决于它的硬件资源和这些资源的组织形式。与请求关联的QoS策略必须能够被底层的存储系统所理解和支持，如果使用一个存储管理系统无法理解的QoS策略，那就是毫无意义的。这就意味着，如果一个DBMS被转移到另外一个采用了完全不同QoS策略的存储系统上面，那么，就必须采用一个不同的存储管理模块，设计不同的语义信息和QoS策略之间的映射。

10.4.4.2       混合存储系统的QoS策略

这里以一个实例来演示hStoreage-DB是如何支持自动存储管理的。在本实例中，hStoreage-DB是一个包含两级存储架构的系统，最低层是磁盘，位于磁盘上面的一层是固态盘，作为磁盘的缓存。由于是一个两级存储架构，就需要确定数据被存放到缓存（固态盘）中的优先级，因此，QoS策略被定义为一个关于缓存优先级的集合。

具体而言，可以把QoS策略定义成一个三元组{N,t,b}，其中，N>0，0≤t≤N，并且0%≤b≤100%，参数N定义了优先级的总数量，更小的值意味着更高的优先级，即获得更好地被缓存的机会。参数t是一个针对“不缓存”的优先级门槛值，也就是说，被一个优先级大于等于t的请求所访问的块，将不会有任何被缓存的机会，这里需要注意的是，优先级的值越大，优先级越低。如果把“不缓存”的优先级门槛值设置为t=N-1，那么，就会存在两种不缓存的优先级，即N-1和N，这里称优先级N-1为“不缓存和不驱逐”，称优先级N为“不缓存和驱逐”。参数b是和一个特定的优先级相关的配置参数，这个特定优先级被称为“写缓冲区”优先级。注意，写缓冲区优先级和写缓冲区不是一个概念，写缓冲区是一个缓存空间，而写缓冲区优先级并不是一个专用的空间，而是一个专门的优先级，在这种优先级下，一个更新请求可以比其他类型的请求更加优先获得缓存空间。参数b用来决定把多少缓存空间用来作为写缓冲区，当更新操作占用的数据空间超过b时，写缓冲区中的所有内容都会被刷新到磁盘中。对于OLAP类型的工作负载，可以设置b为10%。对于每个到达的请求，存储系统首先抽取出与之关联的QoS策略，然后调整所有被访问块的放置位置。例如，如果一个块被一个关联了高优先级的请求所访问，那么，如果这个块还不在缓存中，它就会被调入缓存，当然，这个过程也会取决于已经在缓存中的其他块的优先级。因此，在实际应用中，一个请求的优先级会被最终转换成为所有被访问的块的优先级。

10.4.4.3       针对不同类型的请求的QoS策略

前面讲过，如果把hStoreage-DB设计成一个包含两级存储架构的系统，为了实现缓存优先级的目的，可以把语义信息分成四类：（1）顺序请求；（2）随机请求；（3）临时数据请求；（4）更新请求。下面介绍如何为四种不同类型的IO请求分配不同的QoS策略。

10.4.4.3.1        顺序请求

在混合存储系统hStoreage-DB中，缓存设备是一个固态盘，底层的存储是磁盘，磁盘可以提供较好的顺序访问性能，这意味着，把接受顺序访问的块放入缓存就不会有什么收益。因此，针对顺序请求，hStoreage-DB按照规则1为之分配QoS策略。

规则1：所有的顺序请求都会被分配一个“不缓存和不驱逐”优先级。

一个请求具备“不缓存和不驱逐”优先级，具有两个方面的含义：（1）如果被访问的数据不在缓存中，就不会把它分配到缓存中；（2）如果被访问的数据已经在缓存中，它的优先级是由之前的请求确定的，不会受到本次请求的影响。换句话说，具备这种优先级的请求，不会影响现有的存储数据布局。

10.4.4.3.2        随机请求

随机请求可以从缓存中获得收益，但是，最终收益的大小取决于数据重用的可能性。如果一个块被一次随机访问以后，就再也不会被随机访问，那么，就不应该为它分配缓存空间。因此，针对随机请求，hStoreage-DB按照规则2为之分配QoS策略。

规则2：在查询计划树当中的较低层次的操作发出的随机请求，要比在查询计划树当中的较高层次的操作发出的随机请求，具备更高的缓存优先级。

10.4.4.3.3        临时数据请求

临时数据是在查询执行过程中生成的，查询结束以后就会被删除，生命周期较短。临时数据包含两个阶段：生成阶段和消费阶段。在生成阶段，临时数据会被一个写数据流生成；在消费阶段，临时数据会被一个或多个读数据流所访问。在消费阶段的结束，临时数据会被删除，以释放存储空间。因此，对于临时数据的这个两阶段特点，应该在临时数据被生成的时候就立即把它放入缓存，并且在生命周期结束时候立即把它驱逐出缓存。因此，针对临时数据请求，hStoreage-DB按照规则3为之分配QoS策略。

规则3：所有针对临时数据的读写请求，都被给予最高优先级。删除临时数据的命令，被分配“不缓存和驱逐”优先级。

一个请求具备“不缓存和驱逐”优先级，包含两个方面的含义：（1）如果被访问的数据不在缓存中，它就不会被加入到缓存中；（2）如果被访问的数据已经在缓存中，它的优先级会被改变成“不缓存和驱逐”优先级，从而使之在以后的时间里会及时被驱逐。因此，具备“不缓存和驱逐”优先级的请求，不允许数据进入缓存，只让数据尽快离开缓存。

10.4.4.3.4        更新请求

hStoreage-DB为写操作分配一部分缓存，从而使得这些写操作不需要直接访问磁盘。使用一个写操作缓冲区以后，所有的写数据将会被首先存储到固态盘缓存中，并被异步地刷新到磁盘中。因此，针对更新请求，hStoreage-DB按照规则4为之分配QoS策略：

规则4：所有更新请求将会被分配“写缓冲区”优先级。

10.5    本章小结

本章内容首先介绍了闪存代替磁盘作为特种数据的存储介质，包括存储事务日志、回滚段、中间结果；然后，介绍了闪存作为介于磁盘和内存之间的缓存，包括作为数据库系统的二级缓存和作为数据仓库的更新缓存，并介绍了“5分钟规则”，可以用来确定把哪些数据放入固态盘；接下来，介绍了基于数据访问模式的混合存储系统，包括基于对象放置顾问的混合存储系统、基于双状态任务系统的混合存储系统和基于垂直分区的混合存储系统；最后，介绍了基于语义信息的系统框架hStoreage-DB，它定义了对于存储IO而言至关重要的语义信息，并且传递给存储管理层。存储管理层根据收集到的语义信息，把访问请求分成不同的类型，并为每种类型分配一个合适的QoS策略，从而使得每个请求都可以由合适的设备来为之提供服务。

10.6    习题

• 分析用闪存来存储事务日志为什么可以明显改进事务吞吐量。
• 分析当把磁盘替换成闪存固态盘时，对于块嵌套循环连接、归并排序连接、Grace哈希连接和混合哈希连接这四种连接算法而言，在性能方面分别会带来什么影响。
• 说明闪存作为数据库仓库的更新缓存时的主要作用。
• 阐述5分钟规则的含义。
• 阐述FaCE的设计思想。
• 阐述基于语义信息的混合存储系统框架hStorage-DB的设计思路。