数据库系统的混合存储管理

陈凌潇   2015/06

【摘要】

       固态硬盘在存储系统中应用的普及成为趋势，但SSD带来性能提升的同时，也会带来一些问题，比如当前缓冲池算法能否适应等。这片文章用SSD和HDD构成混合存储系统，用于数据库管理。本文的三大要点是：

一、             提出了cost-aware替换算法，使DBMS和SSD都能够充分意识到SSD和HDD各自的长短，并扬长避短。

二、             SSD的物理存取依赖于DBMS缓冲池。基于对缓冲池缓存策略的研究，设计了cost-adjusted缓冲策略，以便有效管理SSD。

三、             最终，在MySQL的innodb存储引擎中实现了上述算法，并通过TPC-C测试，证明上述算法的性能比之前的算法更优。

Tips1：

SSD（固态硬盘）：用固态电子存储芯片阵列而制成的硬盘，由控制单元和存储单元（FLASH芯片、DRAM芯片）组成。固态硬盘在接口的规范和定义、功能及使用方法上与普通硬盘的完全相同，在产品外形和尺寸上也完全与普通硬盘一致。基于闪存的固态硬盘是固态硬盘的主要类别，其内部构造十分简单，固态硬盘内主体其实就是一块PCB板，而这块PCB板上最基本的配件就是控制芯片，缓存芯片（部分低端硬盘无缓存芯片）和用于存储数据的闪存芯片。

主控芯片是固态硬盘的大脑，其作用一是合理调配数据在各个闪存芯片上的负荷，二则是承担了整个数据中转，连接闪存芯片和外部SATA接口。不同的主控之间能力相差非常大，在数据处理能力、算法，对闪存芯片的读取写入控制上会有非常大的不同，直接会导致固态硬盘产品在性能上差距高达数十倍。

主控芯片旁边是缓存芯片，固态硬盘和传统硬盘一样需要高速的缓存芯片辅助主控芯片进行数据处理。这里需要注意的是，有一些廉价固态硬盘方案为了节省成本，省去了这块缓存芯片，这样对于使用时的性能会有一定的影响。

固态硬盘具有传统机械硬盘不具备的快速读写、质量轻、能耗低以及体积小等特点，同时其劣势也较为明显。尽管IDC认为SSD已经进入存储市场的主流行列，但其价格仍较为昂贵，容量较低，一旦硬件损坏，数据较难恢复等；并且亦有人认为固态硬盘的耐用性（寿命）相对较短。

Tips2：

       TPC-C：是指事务处理性能委员会，TPC不给出基准程序的代码，而只给出基准程序的标准规范，任何厂家或其它测试者都可以根据规范，最优地构造出自己的系统（测试平台和测试程序）。为保证测试结果的客观性，被测试者（通常是厂家）必须提交给TPC一套完整的报告。TPC已经推出了四套基准程序，被称为TPC－A、TPC－B、TPC－C和TPC－D。其中A和B已经过时，不再使用了。TPC－C是在线事务处理(OLTP)的基准程序，TPC－D是决策支持(Decision Support) 的基准程序。TPC即将推TPC－E，作为大型企业(Enterprise)信息服务的基准程序。

【引言】

       闪存凭借其低能耗的有点，在便携式设备的存储界混得如鱼得水。现在基于闪存的SSD在服务器环境中也越来越普遍。对于每比特的存储，SSD比HDD贵很多，但对于I/O操作，SSD则便宜很多。所以数据中心的服务器往往同时兼备SSD和HDD，前者用于少量频繁存取的数据，后者用于大量不频繁存取的数据。本文呢，就是着眼于数据库管理中这种混合存储系统的使用。这两种存储设备对于数据库管理系统(DBMS)都是可见的，所以数据库管理系统可以根据相应的信息来决定是用SSD还是HDD。如下图所示，是写数据时DBMS决定是用SSD还是HDD。

之前的相关工作都主要是解决数据在混合存储系统中放置位置的问题。本文在第七章中对之前的工作做了一个总结，并提供了一个更开阔的视角。我们把两个相关的问题放在一起考虑：

一、              哪些数据应该被放在DBMS缓冲池中？解决这个问题时必须考虑SSD回收块比HDD快得多，所以我们设计的cost-aware缓冲管理法就考虑到了这个因素；

二、              由于SSD不够大，不足以承担起整个数据库存储系统，所以需要决定哪些数据应该被放置在SSD上。这个就取决于数据库存储系统的工作量和缓冲池的管理方法。

本文同时研究了两个相互依存的问题：缓冲池的管理和混合存储系统的管理，而且通过付出设计并实现一个DBMS的代价，本文有更大的空间和视野对前人的工作进行优化。SSD或HDD页的位置决定了缓冲池的替换决策，因为页的位置影响着回收和重载的代价。截然不同的是SSD页的定位则完全取决于该页使用的频率，而这又反过来取决于缓冲管理。把一个页从HDD移到SSD可以显著提高该页的物理读写速率，这篇文章提议的GD2L替换策略倾向于快速回收缓冲池中的SSD页。

我们利用anticipatory预测方法将这些依赖关系运用于SSD管理。通过CAC预测一个从HDD到SSD的移动会对物理I/O造成什么影响，只有当预测结果是好的时才会将该页放在候选中。然后DBMS再据此作出cost-aware的替换决定。

这篇文章的贡献总结为三点：

一、              提出了GD2L，一种用于混合存储系统的数据库系统的缓冲池管理的cost-aware算法。特点是根据混合存储系统的特点，在前人的基础(GreedyDual算法)上进行改进，并在数据库中进行了实现；

二、              提出了CAC，一种用于SSD管理的基于开销的预测技术。特点是它是专门用以和GD2L一类的cost-aware缓冲池管理算法一起工作的，它用于预期将一个页移入或移出SSD导致的该页的获取模式发生的改变，这些预测的改变将影响SSD安置决定；

三、              通过实验对GD2L和CAC做了评估。通过将两者在MySQL的innodb存储引擎中实现，并将GD2L和innodb原有的不重视在混合存储系统中页的位置因素的缓冲管理算法进行对比，以及将CAC和LRU-2、MV-FIFO进行对比。全部评估实验都是以TPC－C为基准。

【概述】

DBMS有SSD和HDD两种存储设备。而数据库中的所有页，都是根据DBMS的二次存储布局策略放置在HDD设备上特定位置。此外，还有一些页的副本存放在SSD设备和缓冲池中。

一言以蔽之，当DBMS需要读取一个页，首先检查最快的缓冲池中有没有该页，若没有就检查稍慢的SSD中有木有(这里要求SSD管理器要跟踪监控SSD中有哪些页)，再没有就只能从最慢的HHD中获取了。

这里有一个问题就是当缓冲池满了，那要读取一个新页进去怎么办，那就要求缓冲池管理器根据替换策略回收缓冲池中原有的一个页出来。而被回收出来的页如果原来没有在SSD中，SSD管理器就根据“许可策略”先把它放进SSD。而这时如果SSD也满了，那SSD管理器就需要根据回收策略回收一个SSD原有页腾地儿。这是需要注意，在将一个从SSD移回HDD前需要检查该页是否有更新，如有则要先复制新页写入一个临时存储空间，再写回HDD否则会造成数据丢失。

假定DBMS缓冲池管理器对页是异步刷新的，从而掩盖DBMS应用程序的写延迟。当缓冲池需要将一个脏页刷新回去时，就检查该页是否在SSD中，若在就刷新SSD中的该页，若不在就先将该页写入SSD，与回收页的方式严格一致。注意一个页要进入SSD的前提是通过SSD管理器的admission。

特别注意两点：

一、           只有当缓冲池中的页被回收或缓冲池中的脏页被刷新时才会触发SSD管理器的admission检测，可以允许一个页进入SSD；而当直接从HDD中获取某页进缓冲池时是不允许该页进入SSD的。这样做是为了将页的缓存降到最低，也就是缓冲池和SSD中页的副本。

二、           缓冲池中的脏页被刷新时只可以进入SSD或HDD中的一个，不可以兼而有之。

【缓冲池管理】

       这部分主要就是讲替换算法GD2L。

       现有的cost-aware算法都是针对文件缓存的，一般在做置换决定时会考虑文件大小和获取开销，而且会考虑不同的情况：统一大小任意成本、任意大小统一成本、任意大小任意成本。GD算法属于后者。一句话总结，GD2L算法就是包含了Qs和Qh两个LRU队列的GD算法，其中GD算法，实际上就是一系列众所周知的缓冲算法的统称，比如LRU和FIFO。用H表示找到一个页p并将其放入缓存的花销。这里需要说明的是，在回收一个页时，剩余页的H值需要相应地减少，通常的GD算法是通过k减函数来实现的，这样的计算开销较大。而GD2L中是采用Cao et al.技术L值实现的，通过L可以抵消设置所有H值的开销。

       直奔主题，看一下GD2L读取页p的算法：

说人话就是当要读取页p进行缓存时，对比SSD的LRU队列和HDD的LRU队列中H值更小的那个页q，将L设置为q的H值并将p放入缓存，这里要考虑p是SSD页还是HDD页。

再接下来的3.1部分，就是介绍GD2L算法在MySQL的innoDB存储引擎中的实现。如下图所示，为了实现GD2L将innoDB的LRU列表分为Qs和Qh两个队列。接下来这篇文章用了两段文字介绍了innoDB的脏页刷新机制，这里既不赘述了。

另外，对于传统的GD算法而言，页的检索开销是不变的，而GD2L中根据页是放入SSD还是从SSD中取出，其检索开销是不同的。因此，将页从HDD中读入SSD中时，GD2L直接将新缓存页放在SSD中间点位置，并将其H值设置为与前一个中间点页的H值相同。同理将页从SSD中读入HDD中时，亦然。

【COST-AWARE缓存的影响】

       像GD2L一类的cost-aware算法都会考虑页的位置，位置不同读写速率也会随之不同。这里是要回答两个问题：当采用GD2L算法，将页放入SSD后其读速度如何改变？GD2L又给脏页刷新带来了什么影响？这些影响又是如何影响写速率的？为此，通过工作量为TCP-C的InnoDB做实验证明，页的不命中率和物理写几率在采用SSD存储时比在HDD设备上要高，因为前者的成本大大降低。实验结果如下图所示：

【SSD管理】

      实际上，SSD管理包括三部分内容：       SSD的页管理、替换策略、基于check-point的SSD元数据恢复机制。

       当决定是否要将一个页p放入SSD时，需用CAC(即cost-adjusted cashing)策略。这里需要引入一个参数B，用以表征从SSD上获取一个页时所能节省的能耗值。对于传统的存储系统，该值的计算方法如下：

其中r(p)和w(p)是通过实验获取的物理读写请求数，其余参数在上文表1中有说明。

       但对于GD2L一类的存储系统，由于SSD改变了其I/O路径，所以该公式无法使用。故而对于GD2L的B值，计算方法如下：

其中，各参数的计算方法如下：

       这里必须讲一下参数α，即未命中率扩大因子。它是用来表征，如果一个页被允许进入SSD之后，其物理读写率的变化情况。α定义为：

其中，Ms表示SSD上页的读请求的总体未命中率，而Md表示非SSD上页的读请求的总体未命中率。例如，α=3就表示SSD上页的读请求的总体未命中率是非SSD上页的读请求的总体未命中率的三倍。

       但这个公式太过粗糙。如下图所示的实验表明，不同的页的组群拥有不同的α因子：

所以必须根据不同的数据库对象，定义不同的α因子，具体方法如下：

然后，来说一下顺序I/O。事实证明，对于硬盘而言，时序读比随机读的性能要好。因此只有在估计B值的时候才会用到随机读。这也就要求SSD管理器可以分类识别一个读请求是顺序的还是随机的。关于这里用到的分类方法，最近的相关工作有两项进展：Canim et al.以及Do et al.。

       最后说一下，故障处理。既然SSD能够带来比HDD更优的性能，那么在故障恢复时就要求系统能够识别那些页是在SSD中的。对于Do et al.提出的TAC方法是没有这个问题的，因为它采用Lazy cleaning方法，即check point时将所有SSD脏页全部刷新回HDD。而CAC与之不同，CAC假定SSD的内容会在故障中幸存，故障后只要页还在，它就会从SSD中读取一个最新版本。这种方法的困难在于，故障发生时，SSD管理器的标志着哪些页是SSD页的哈希映射表丢失了。这个问题可以通过checkpoint哈希映射表来解决，并同时记录SSD的所有写操作。在恢复过程中，根据最后一个写的哈稀图和日志，哈希映射表可得以重建。

【评价机制】

       通过实验数据来评估GD2L和CAC的优劣。实际上就是回答两个问题：一、相较于non-cost aware缓冲管理，GD2L的优势？二、当把GD2L应用于缓冲池管理时，一个可预见的SSD管理器，例如CAC，的重要性？这里的可预见性是指，当页在SSD和HDD之间移动时，SSD管理器能够意识到页获取模式的变化。

       为了回答上述两个问题，本文设计了一个多样性选择的算法，使得DBMS缓冲池有两种选择：LRU和GD2L。且SSD管理器有四个候选项：CAC、CC、LUR2、MV-FIFO。其中，CC是cost-based，而非可预知的；LRU2和MV-FIFO既不是cost-based的也非可预知的。缓冲池和SSD管理器的候选项之间可以以X+Y的形式任意搭配。

       思路说清楚之后，就来看一下具体的实现方法。

实验环境说明à  带InnoDB存储引擎的MySQL数据库管理系统  5.1.45版本

                服务器（6个2.5GHz IntelXeon cores；

4GB 主存；

Ubuntu 10.10Linux 内核版本2.6.35-22；

两个500GB RPM SCSI 硬盘；

一个32GB Intel X25-E SATA SSD）

需要说明的是，两个500GB RPM SCSI 硬盘，一个用以存放所有软件，包括MySQL和数据库测试集；另一个用以存放事务日志。此外，数据库的SSD缓存是作为一个单独的文件放在SSD上的。InnoDB上所有文件皆采用无缓存I/O。工作量依旧是TCP-C。

       实验沿着三个有代表性的路线展开：数据库远远大于SSD缓存；数据库稍微大于SSD缓存；数据库小于SSD缓存。SSD缓存大小分别设置为1G/2G/4G；数据库大小分别设置为8G/15G/30G。对于CAC和CC的对比实验，将输出队列的条目数设置为SSD缓存可放入的数据库页数一样。并将输出队列所占空间从可用空间中去除，以保证两者有相等的空间基础。其他情况下，CAC会取10%的SSD缓存空间作为回收空间。

       这里说一下参数校准问题。在做替换决定时，GD2L和CAC都依赖于设备的读写花费参数。实验中使用diskstats(一个用于记录磁盘状态、统计I/O时间的Linux工具)跟踪统计磁盘的read和write情况。并据此将实验参数校准为：RS = 1,RD = 70, WS = 3, and WD = 50。

       最后，来进行实验数据的分析：

通过上图所示的实验数据可以得出的结论，条分缕析如下：

       1：当数据库远远大于SSD缓存时，GD2L的性能远远优于LUR；

       2：当数据库大小并非远远大于SSD缓存时，GD2L和LUR的性能相似；

       3：对于超大型数据库，相较于LUR而言，GD2L将工作量提升了40%-75%；

       4：对于30G以及更大的数据库，GD2L+CAC的性能显著优于其他算法

       ……

       数据分析得出的结论太多不一条一条列了，重点就是数据库越大，GD2L+CAC的性能优势越显著；若数据库不够大，GD2L+CAC也没啥优势。如下表格显示的数据的结论也是一样。实验中设备的利用率、缓冲池的未命中率、I/O开销情况体现在如下三个表格中：

    此外，补充说明两点：一、通过对GD2L+CAC设置不同的回收空间进行实验，结果表明回收空间大小不会对TCP-C工作量带来什么影响；二、checkpoint哈希表所带来的开销可以忽略不计。

【相关工作】

       把hot数据放在快的存储介质中，把cold数据放在慢的存储介质中已经不是什么新鲜事了，但HSM（即混合存储管理系统）的提出使得“Tape is dead, disk is tape, flash is disk”的说法即将成为现实。然后作者找了十多个学着的相关工作进行分析对比，太烦，不说了。

【总结】

       总而言之，本文提出并实现了两种算法：GD2L和CAC，用于管理缓冲池和数据库系统中的SSD。并将其与其他算法进行对比，证明了其在大型数据库中的优越性。其局限性体现在它受制于HDD的带宽。