本申请要求于 2012 年 05 月 24 日提交中国专利局、 申请号为 201210165053.X、发明名称为 "基于 SSD的 Key- Value型本地存储方法及系统" 的中国专利申请的优先权， 其全部内容通过引用结合在本申请中。 技术领域

该发明涉及本地数据存储管理系统， 尤其涉及基于 SSD (固态硬盘） 的 Key-Value (键值）型本地存储方法及系统。 背景技术

数据的组织管理主要分为三步，一是数据的在 线存取， 主要指的是获得数 据和提供读取服务， 即面向传统的 OLTP型负载， 二是数据的组织， 传统上指 的是将 OLTP型数据库中的数据转为适合数据仓库的数� �格式， 即称为 ETL的 过程。 三是数据分析， 指的是进行长时间， 复杂的数据挖掘等工作来发现数据 中的联系和潜在价值， 也就是 OLAP型任务。 本文中， 我们关注的是数据的在 线存取部分。

传统的方案中， 满足数据在线存取任务的是以 MySQL为代表的关系型数 据库。 关系型数据库是上世纪 70年代的产物， 产生伊始的主体架构沿袭至今。 关系型数据库是数据存储管理发展史上的里程 碑，其特点是擅长严格事务处理, 提供数据安全性保障等。但对于大数据时代的 新型负载， 关系型数据库体现出 了其固有的局限性：

其一， 大数据负载的规模变化快， 当新业务上线时， 相关的数据量往往急 速上升， 而当业务调整时， 数据量又可能会快速收缩， 转移到别的业务上去。 而在传统数据库面向的应用场景一般都是在比 较静态的用户群体中进行，扩展 和收缩会牽涉到数据库的分库分表操作。这些 复杂的行为一是会耗费大量人力 物力，二是可能导致相关业务的暂时下线， 这是目前的互联网服务商很难接受 的。

其二， 大数据负载的形式变化快。 传统的数据库在线事务处理中， 一般面 向的文书，报表等，都具有比较固定的格式内 容，而正如上文已经提到的那样， 现今面临的负载中，越来越多的却是没有固定 范式，或者经常根据业务需要进 行调整的的非结构化数据或半结构化数据。这 种灵活性是传统的关系型数据库 所不具备的。

其三， 事务性支持的需求与以往有变化。传统关系型 数据库都提供了严格 的 ACID事务支持，但目前来说这种事务支持从两� �方面引起人们的重新考量。 第一是因为现在以互联网应用为典型的新型业 务需求中， 相对来说对 ACID的 特性并没有严格遵循的需求， 比如对于博客文章， 相关评论， 相册图片， 甚至 网上店铺的库存， 暂时的不一致状态对于用户来说都是可以接受 的。 第二， 严 格的 ACID特性限制使得数据库整体的性能和扩展性� �以提高， 这主要是复杂 的锁机制， 日志机制等造成的。

正是由于关系型数据库存在的这些问题 ,使得被称为 NoSQL类型的新一代 存储系统渐渐崛起，并被广为使用。 NoSQL这个名称意味着它和关系型数据库 有截然不同的地方， 一般不再支持 SQL语句的复杂功能， 同时另一个重要区别 的是大多数的 NoSQL系统放弃了 ACID的完整支持， 它们的特点可以大致归纳 如下：

因为放弃一些复杂的但是不实用的特性， NoSQL系统得以规避了很大一部 分复杂的设计实现。

NoSQL系统可以提供明显高于传统数据库的数据� ��吐能力。

具有良好的水平扩展能力， 并适合运行在一般的廉价 PC服务器硬件上。 Key-Value型存储系统固然具有这些优势， 但数据负载的增长一直保持着 迅猛的态势， 同时也对存储系统层面造成越来越大的压力。 我们可以看到， 计 算机硬件特别是 CPU和内存容量一直保持着高速发展的态势，而 作为持久化存 储设备的硬盘的读写能力却一直都没有突破性 的进展，这是由于磁盘的结构涉 及到机械运动的本质决定的，随机读写中机械 寻道动作造成的响应速度限制恐 怕是传统磁盘结构中无法解决的问题。 这样一来， 随着计算速度快速提高， 磁 盘读写能力的瓶颈问题越来越突出。

有部分的 Key-Value型系统使用全内存的架构， 避免磁盘读写瓶颈来获得 极高的性能。 但在实际应用中， 这种系统只被用来作为数据库的前端緩存， 难 以成为数据的最终落脚之处。内存型数据库的 局限之处在于放置在内存中的数 据容易在系统崩溃等意外中丟失， 安全性得不到保障， 另外内存的价格和能耗 依然远高于磁盘， 出于数据访问的二八原则，将其全部放置于内 存不符合经济 方面的考量，将冷数据放置在磁盘等二级存储 可以做到不大幅降低性能的同时 降低系统的整体成本。

SSD的出现有利于这个问题的解决， SSD存储介质相比较磁盘的优势和劣 势都很明显，优势是随机读写性能大大提高， 劣势是单位存储容量的成本大大 高于磁盘。但从另一个角度来说，单位随机读 写性能的成本 SSD却比磁盘更低。 所以在要求高随机 IOPS(每秒读写请求响应数）的场景中， SSD有应用的价值， 从实际情况来看，各大互联网公司已经开始在 存储架构中大量使用 SSD来提高 系统的整体性能。 但从 SSD的特点来说， 小粒度随机写的性能较差， 而且从实 测性能来看， FTL (闪存翻译层）的技术并无法完全解决这个问� �。 小粒度随 机写造成性能下降的原因主要是： 所以为了最大程度地发挥出 SSD的性能优势, 存储系统的读写模式需要针对其进行优化。

现有的同类系统中， Flashstore和 FAWN等系统， 利用的是 Hash式数据索引 的机制，这种索引方式主要存在两个问题，一 是 Hash式数据索引需要在内存占 用量和硬盘读取次数之间做权衡，难以获得两 者兼得的效果。二是 Hash式数据 索引难以实现范围查找的操作。

对于以 Berkeley DB为代表的许多利用传统 B+树索引机制的系统来说， 在

SSD上使用主要面临的问题其数据插入会造成 大量的原地更新写入操作，这是 不利于 SSD性能的 10模式， 另一方面， 对于并发支持来说， B+树索引需要引 入复杂的锁机制， 不利于系统的整体性能。

而较晚出现的 LSM-tree索引结构被应用在 LevelDB等系统中， 其优势在于 写入模式为大粒度连续写， 非常利于 SSD的性能发挥， 但 LSM-tree作为一种倾 向于写优化的机制， 读操作因为引入的读硬盘次数较多， 使得其性能较低。

综上所述， 现有的 Key-Value系统不能满足当前的应用需求， 主要体现在 以下两点：

第一， 以锁机制为基础的并发控制技术难以满足高并 发读写负载的要求； 第二， 现有系统的写入模式不适应 SSD的特性。 发明内容

为了应对非结构化数据的管理这一突出需求的 问题，本发明实现一个面向 高并发负载， 基于 SSD的 Key- Value型本地存储方法及系统。

本发明公开一种基于 SSD的 Key- Value型本地存储方法， 包括：

步骤 1 , 对于数据采用内存快照 B+树索引结构， 进行内存中的读写分离操 作；

步骤 2, 经过索引后的数据， 针对 B+树页面使用 FIFO队列管理緩存； 步骤 3 , 对所述数据页面追加写入 SSD, 通过空洞文件机制在日志型追加 写入的数据中实现逻辑页号和物理位置的映射 管理。

所述的基于 SSD的 Key- Value型本地存储方法， 所述步骤 1包括：

步骤 21 , 根节点 A为 B+树根节点， 如对首节点 D做一次更新操作； 首先将 首节点 D页面进行拷贝， 拷贝的副本页面为首节点 D，， 然后在首节点 D， 页面 中进行所需要的更新；

步骤 22, 进行完这个操作以后， 需要对中间节点 B中对首节点 D， 的索引 也做更新， 根据内存快照的原则， 为了防止读写竟争， 需要先对中间节点 B进 行拷贝， 然后在副本中间节点 B， 中进行更新操作； 依次操作， 所述拷贝过程 也在根节点 A上发生；

步骤 23 , 当整个更新操作完成时， 形成了一棵以根节点 A， 为根节点的新 B+树， 根节点 A， 相比较 A, 指向 B， 的索引有变化， 而其他索引仍然不变； 步骤 24, 中间节点 B， 更新了指向首节点 D， 的页面， 其他索引没有变化。 所述的基于 SSD的 Key- Value型本地存储方法， 所述步骤 2包括：

步骤 31 , FIFO页级写緩存的设计使用环形队列的结构，� �个环划分为 write 区域和 read区域， write区域中为正在进行写操作， 尚未提交的页面， read区域 中为已经完成写操作并提交的页面， 可以供读操作从緩存中获得；

步骤 32, write指针指向 write区域的末尾，该指针也是下一个写操作向� ��緩 存申请新页面时装载的位置，在系统运行时， write指针位置不断获得新页面并 沿着环形队列前移， 同时完成写操作的页面提交为 read区域， 并由 read指针指 向新近提交的页面位置；

步骤 33 , 在这个过程中， 后台异步写入线程将以适合应用需求的速度将 read区域依次持久化到 SSD中， 已经完成持久化的页面区域称为 flush区域， 一 个 flush指针指向下一个要做持久化的页面， flush区域为 read区域的一部分， 供 write指针获得新页面的区域；

步骤 34, 在后台异步写入线程将相应页面写入 SSD中的过程中， 已经在环 形队列中存在更新拷贝的页面属于冗余页面， 不需要进行写入，本方法中将跳 过该种页面， 同时在 SSD的数据文件中制造同样大小的文件空洞， 该文件空洞 不占用实际空间也不进行实际写入操作，但保 持了逻辑页号和数据页面在文件 中位移的对应关系。

所述的基于 SSD的 Key- Value型本地存储方法， 所述步骤 3读出操作包括： 步骤 41 , 获得当前的 B+树根节点， 作为 B+树索引查找的起点； 读操作无 需对页面进行加锁；

步骤 42, 对于包括根节点在内的中间节点页面进行页面 内部的折半查找， 取得正确的索引项， 获得下一个需要进行查找的页面逻辑页号， 这一查找过程 直到获得叶子节点后终结； 因为内存快照技术的使用，读操作无需对页面 进行 加锁；

步骤 43 ,通过逻辑页号获得物理页面的操作通过调用� �存池管理模块完成; 内存池管理模块将该页号与 FIFO队列中最小的页号相比较， 判断是否在队列 中， 如果比最小页号大， 也就是緩存命中的情况， 直接返回内存池管理中的页 面引用；

步骤 44, 如果没有命中緩冲， 则需要分配额外页面空间， 然后到 SSD中读 取； 用逻辑页号获得 SSD中的数据需要通过调用日志型数据管理模块 的功能来 完成； 因为文件空洞机制的作用， 日志型数据管理模块此时的任务非常筒单， 只需要用逻辑页号乘以页面大小， 然后读取相应页面即可；

步骤 45 ,最后在叶子节点页面中完成最终的 Key- Value对查找，返回结果。 所述的基于 SSD的 Key-Value型本地存储方法， 所述步骤 3写入操作流程还 包括：

步骤 51 , 通过 B+树的查找来确定要插入新数据记录的正确位� ��， 获得当 前的 B+树根节点， 作为 B+树索引查找的起点； 读操作无需对页面进行加锁； 对于内存池管理模块中的 FIFO环形队列 Read Region的改变全部发生在写线程 中， 所以写线程本身对于页面緩存命中的判断就不 需要进行加锁； 步骤 52, 完成查找正确插入位置的操作时， 写线程将根节点到插入位置页 面整条路径的页面压入一个栈结构中，该栈结 构中除了保存指向对应页面的指 针外， 还保存了路径中的中间节点指向子节点的页内 索引号；

步骤 53 , 写入页面的过程将会依次弹出栈中页指针， 这里使用内存快照的 技术来避免加锁保护，对一个页面的修改， 需要先调用内存池管理的接口来请 求一个新的页面， 然后将源页面的内容拷贝到新页面中， 再进行修改操作； 在 随后弹出的父节点页面中，需要将原先指向子 节点的索引页号修改为新的逻辑 页号；

步骤 54, 父节点页面中， 需要将原先指向子节点的索引页号修改为新的 逻 辑页号， 这个修改也同样是利用内存快照完成； 如果子节点发生了分裂， 则还 需要插入分裂点；

步骤 55 , 当整个写操作完成后， 进行提交， 需要进行的操作是将已经完成 写入或者更新的所有页面并入 Read Region中， 然后修改新的 B+树根节点为当 前的索引 B+树根节点。

本发明还公开一种基于 SSD的 Key- Value型本地存储系统， 包括： 内存快照 B+树索引模块， 用于对于数据采用内存快照 B+树索引结构， 进 行内存中的读写分离操作；

内存池管理模块， 用于经过索引后的数据， 针对 B+树页面使用 FIFO队列 管理緩存；

日志型数据管理模块， 用于对所述数据页面追加写入 SSD, 通过空洞文件 机制在日志型追加写入的数据中实现逻辑页号 和物理位置的映射管理。

所述的基于 SSD的 Key- Value型本地存储系统， 所述内存快照 B+树索引模 块包括：

首节点更新操作模块， 用于根节点 A为 B+树根节点， 如对首节点 D做一次 更新操作； 首先将首节点 D页面进行拷贝， 拷贝的副本页面为首节点 D，， 然后 在首节点 D， 页面中进行所需要的更新；

中间节点更新操作模块， 用于进行完这个操作以后， 需要对中间节点 B中 对首节点 D， 的索引也做更新， 根据内存快照的原则， 为了防止读写竟争， 需 要先对中间节点 B进行拷贝， 然后在副本中间节点 B， 中进行更新操作； 依次 操作， 所述拷贝过程也在根节点 A上发生；

更新完成模块， 用于当整个更新操作完成时， 形成了一棵以根节点 A， 为 根节点的新 B+树， 根节点 A， 相比较 A, 指向 B， 的索引有变化， 而其他索引 仍然不变；

页面指向模块， 用于中间节点 B， 更新了指向首节点 D， 的页面， 其他索 引没有变化。

所述的基于 SSD的 Key- Value型本地存储系统， 所述内存池管理模块包括： 形成队列结构模块， 用于 FIFO页级写緩存的设计使用环形队列的结构， 整个环划分为 write区域和 read区域， write区域中为正在进行写操作， 尚未提交 的页面， read区域中为已经完成写操作并提交的页面， 可以供读操作从緩存中 获得；

指针位置前移模块，用于 write指针指向 write区域的末尾，该指针也是下一 个写操作向写緩存申请新页面时装载的位置， 在系统运行时， write指针位置不 断获得新页面并沿着环形队列前移， 同时完成写操作的页面提交为 read区域， 并由 read指针指向新近提交的页面位置；

持久化模块， 用于在这个过程中，后台异步写入线程将以适 合应用需求的 速度将 read区域依次持久化到 SSD中， 已经完成持久化的页面区域称为 flush区 域， 一个 flush指针指向下一个要做持久化的页面， flush区域为 read区域的一部 分， 供 write指针获得新页面的区域；

对应写入模块，用于在后台异步写入线程将相 应页面写入 SSD中的过程中, 已经在环形队列中存在更新拷贝的页面属于冗 余页面， 不需要进行写入， 本系 统中将跳过该种页面， 同时在 SSD的数据文件中制造同样大小的文件空洞， 该 文件空洞不占用实际空间也不进行实际写入操 作，但保持了逻辑页号和数据页 面在文件中位移的对应关系。

所述的基于 SSD的 Key- Value型本地存储系统，所述日志型数据管理模� ��包 括：

索引入口模块，用于获得当前的 B+树根节点，作为 B+树索引查找的起点； 获得索引项模块，用于对于包括根节点在内的 中间节点页面进行页面内部 的折半查找， 取得正确的索引项， 获得下一个需要进行查找的页面逻辑页号， 这一查找过程直到获得叶子节点后终结； 因为内存快照技术的使用，读操作无 需对页面进行加锁；

调用内存池管理模块，用于通过逻辑页号获得 物理页面的操作通过调用内 存池管理模块完成； 内存池管理模块将该页号与 FIFO队列中最小的页号相比 较， 判断是否在队列中， 如果比最小页号大， 也就是緩存命中的情况， 直接返 回内存池管理模块中的页面引用；

分配页面空间模块， 用于如果没有命中緩冲， 则需要分配额外页面空间， 然后到 SSD中读取； 用逻辑页号获得 SSD中的数据需要通过调用日志型数据管 理模块的功能来完成； 因为文件空洞机制的作用， 日志型数据管理模块此时的 任务非常筒单， 只需要用逻辑页号乘以页面大小， 然后读取相应页面即可； 完成查找模块， 用于最后在叶子节点页面中完成最终的 Key- Value对查找， 返回结果。

所述的基于 SSD的 Key- Value型本地存储系统，所述日志型数据管理模� ��还 包括：

插入位置模块， 用于通过 B+树的查找来确定要插入新数据记录的正确位 置， 获得当前的 B+树根节点， 作为 B+树索引查找的起点； 读操作无需对页面 进行加锁； 对于内存池管理模块中的 FIFO环形队列 Read Region的改变全部发 生在写线程中， 所以写线程本身对于页面緩存命中的判断就不 需要进行加锁； 页面压入模块， 用于完成查找正确插入位置的操作时， 写线程将根节点到 插入位置页面整条路径的页面压入一个栈结构 中 ,该栈结构中除了保存指向对 应页面的指针外， 还保存了路径中的中间节点指向子节点的页内 索引号；

页面修改模块， 用于写入页面的过程将会依次弹出栈中页指针 ， 这里使用 内存快照的技术来避免加锁保护，对一个页面 的修改， 需要先调用内存池管理 模块的接口来请求一个新的页面， 然后将源页面的内容拷贝到新页面中，再进 行 4爹改操作； 在随后弹出的父节点页面中， 需要将原先指向子节点的索引页号 修改为新的逻辑页号；

修改逻辑页号模块， 用于父节点页面中， 需要将原先指向子节点的索引页 号修改为新的逻辑页号， 这个修改也同样是利用内存快照完成； 如果子节点发 生了分裂， 则还需要插入分裂点；

提交模块， 用于当整个写操作完成后， 进行提交， 需要进行的操作是将已 经完成写入或者更新的所有页面并入 Read Region中， 然后修改新的 B+树根节 点为当前的索引 B+树根节点。

本发明的有益效果为：

1 : 内存快照 B+树索引结构与基于 FIFO (先入先出） 队列页级緩存结合 使用。

B+树索引是磁盘上存储数据常用索引机制， 可以提供按页聚合有效减少 读写次数， 同时因为数据局部性方面的优势，相比较 Hash类索引在范围检索上 有更好的性能。 但是， 过去的基于磁盘的 B+树索引， 需要大量小粒度的就地 更新操作 ( in place updates ), 这种读写模式是不合适 SSD的。 因为这样不仅写 入性能低， 而且加速 SSD磨损。 本发明采用内存快照技术， 在内存中实现数据 的读写分离， 提高系统的读写并发度。 而内存快照的特性使得使用 FIFO緩存 策略可以有效体现数据时间局部性的特点，免 去额外的緩存替换算法， 并且使 得命中判断更加筒单和快速。

2: 追加写入数据与空洞文件相结合。

使用 FIFO型緩存的换出页直接写入 SSD中， 不覆盖原有数据，使用的是追 加的写入方式， 利用标准输出库的用户态緩存聚合写粒度， 实现大粒度写入的 目的， 并且由于追加写入的天然特性决定了适合实现 数据一致性， 可靠性。 本 发明使用不间断快照的技术保障数据的高可靠 性，并提供高效的故障恢复机制。

但追加写入需要在写入时去除冗余数据，使得 页面逻辑编号与实际位置不 相对应，如果另外加一层映射管理势必增加了 元数据负担和不一致的风险， 本 发明中利用文件系统本身具有的空洞文件机制 ，使得页面逻辑编号与实际位置 建立起筒单对应的关系， 大大降低了数据放置的管理难度。

总的技术效果

系统利用内存快照 B+树的数据索引结构可提供高读写并发性能。 利用基 于追加写入的 10模式， 并使用文件空洞， 不间断快照机制， 可以提供适合 SSD 特性， 并提供数据高可靠性的数据放置机制。

附图说明 图 1为本发明系统整体存储组织架构；

图 2为本发明页级写緩存结构图；

图 3为本发明内存快照 B+树示例说明；

图 4为本发明 LogManager工作原理示意图；

图 5为本发明读出操作流程；

图 6为本发明写入操作流程。 具体实施方式

下面给出本发明的具体实施方式， 结合附图对本发明做出了详细描述。 ( Tree Index ) 内存快照 B+树索引模块： 利用内存快照 B+树技术， 实现 数据索引机制。

( Memory Pool )内存池管理模块：进行 B+树页面的空间分配，緩存管理。 ( Log Manager ) 日志型数据管理模块： 对数据持久化功能进行具体的读 写操作， 并通过空洞文件机制实现逻辑页号和物理位置 的映射管理。

内存快照 B+树索引

B+树是数据库和文件系统中常用的数据索引结� ��， 优点是保持存储数据 稳定有序， 插入和修改拥有较稳定的对数时间复杂度。本 发明使用内存快照机 制改进传统 B+树数据索引机制来满足新的需求。

B+树的结构以页为单位， 各个页为树结构中的节点。 B+树种存在中间节 点和叶子节点两类节点， 中间节点由 B+树根节点开始向下延伸， 各个节点的 页中记录子节点的页索引， 根节点在 B+树末端， 根节点对应页中存放实际 key-value数据。 B+树节点页面的组织包括页头保持的页面元数� ��信息， 已经 页面其余部分保持的数据列表， 其中叶子节点的数据列表为存储在系统中的 Key- Value对， 中间节点的数据列表存储 Key-Index对， Index项指向该条记录指 向的子节点页面， Key项保存该条记录指向的子页面中最小的 Key作为子树的 分离值。任意 Key在 B+树中的位置可以由根节点开始顺着分离值索� ��到叶子节 点找到。 随着 Key-Value对的插入， 某页面放满数据时会进行分裂操作， 并加 深 B+树， 这样来保证 B+树的平衡性， 提供稳定的插入和检索性能。

本小节将叙述如何利用内存快照技术来改进 B+树索引结构， 实现高并发 特性。

图 3展示了内存快照技术的运作机理。 图中标明 B+树的一部分， A节点为

B+树根节点， 现在需要对 D节点做一次更新操作。 则我们首先将 D节点页面进 行拷贝， 拷贝的副本页面为 D' , 然后在 D' 页面中进行所需要的更新。 进行完 这个操作以后，需要对 B中对 D， 的索引也做更新，那么根据内存快照的原则， 为了防止读写竟争，也需要先对 B进行拷贝，然后在副本 B， 中进行更新操作。 依次类推， 这个拷贝也在根节点 A上发生了。

当整个更新操作完成时， 形成了一棵以 A， 为根节点的新 B+树， 值得注意 的是， A， 相比较 A来说， 指向 B， 的索引有变化， 而其他索引仍然不变。 同样 的， B， 更新了指向 D， 的页面， 其他索引没有变化， 如图中的 C页面， 依然可 由 B， 中的索引项找到。

若以 A， 页面为根节点则当前形成了一个新的 B+树结构， 当更新操作完成 时， 要提交该操作达到新的一致状态， 只需要将存储系统索引的 B+树索引根 节点变更为 A， 节点即可。 后续操作将从 A， 为起点进入 B+树索引中， 然后开 始查找， 当然可以成功地体现出对 D页面的更新效果。 而在提交 A， 成为新的

B+树根节点之前， 并发的读操作线程将从 A节点页面进入到 B+树索引中， 它 们进行的查找操作均不会受到在拷贝页面中进 行的更新操作的影响，不会发生 读写竟争。

上图中演示的是最筒单的快照技术应用， 实际中的情况要更为复杂。 比如 当对 D页面的操作引发了页面分裂， 则 B， 中不仅需要更新索引， 还需要插入 新的索引项。 同样， 对 B， 页面的插入操作也可能会造成 B， 页面的分裂， 这 种具体的情形和传统 B+树操作的情况基本类似， 也就不在此赘述。

总结而言， 本章节阐述了内存快照技术在改进 B+树索引结构并发性上的 设计和实现，通过该技术的应用，使得处理读 请求的线程不需要对索引中的数 据结构进行加锁而可以做到直接访问，这种技 术在读占优的负载中可以显著提 高系统整体的并发性。

FIFO页緩存管理机制

本发明提出的緩存管理策略是面向内存快照 B+树页面的， 其本身具有负 载特殊性。 我们知道， 在 B+树索引结构中， 所有的读写操作都需要从 B+树的 根节点页面进入索引结构， 进行查找定位的工作。 从这个特性可以看出， B+ 树中访问最频繁的恰恰是树结构中位于较高层 次的节点页面。与内存快照技术 相结合来看， 每次的更新写入操作都会引起重新为对应的 B+树路径上的页面 分配新页面以进行拷贝操作。 这种特点造成的结果是， 经常处于 B+树查找路 径上的页面，也就是较高层次的页面，会经常 因为被拷贝而出现在新分配的页 面中。 也就是说， 在内存快照的 B+树索引结构中， 页面的分配顺序本身就体 现出了很强的访问时间局部性特征。

在这种特征下，基于 FIFO替换算法的緩存管理成为一种可能的选择� � FIFO ( First-In First-Out )算法， 即是由一个先进先出的队列来对緩存页面的替 换进 行管理。 每次分配新的页面时， 都会将其放入 FIFO队列中， 队列满时， 发生 替换的原则就是选择队尾页面进行替换。这也 就是实现了驻留緩存中的页面是 新分配的页面， 根据前一段中的论述， 分配顺序体现了内存快照 B+树索引页 面的时间局部性。

FIFO页级写緩存的设计使用环形队列的结构， 整个环划分为 write区域和 read区域， write区域中为正在进行写操作， 尚未提交的页面， read区域中为已 经完成写操作并提交的页面，可以供读操作从 緩存中获得。 write指针指向 write 区域的末尾， 该指针也是下一个写操作向写緩存申请新页面 时装载的位置，在 系统运行时， write指针位置不断获得新页面并沿着环形队列� ��移， 同时完成写 操作的页面提交为 read区域， 并由一 read指针指向新近提交的页面位置。 在这 个过程中， 一个后台异步写入线程将以适合应用需求的速 度将 read区域依次持 久化到 SSD中， 已经完成持久化的页面区域称为 flush区域， 一个 flush指针指向 下一个要做持久化的页面， flush区域为 read区域的一部分， 也是可以供 write指 针获得新页面的区域。

利用空洞文件机制的追加写

对于 SSD来说， 追加写入方式的优点主要是不会产生原地更新 操作， 以及 容易进行大粒度聚合的写入。这可以更加充分 地利用写入带宽， 同时减少小粒 度随机写类型的操作对于垃圾回收和数据碎片 化带来的压力。所以追加写入方 式是一种适合 SSD特性的写入模式优化。

另外， Log-Structured日志型追加方式进行写入内存快照 B+树这种解决方 案可以保证 B+树中的父节点页面总是要在子节点页面之后� ��进行写入。 每次 实际写入 B+树的根节点， 即表明一个完整而且一致的 B+树索引结构以及被持 久化到 SSD中。 在发生系统崩溃， 而需要进行故障恢复的时候， 只需要在日志 型写入的数据文件中， 找到最靠近末尾的 B+树根节点， 就可以顺利恢复一个 全局一致的索引和数据结构。 也就是说， 我们通过一种不间断快照的手段， 达 到了数据高可靠的目的， 避免了数据损坏的场景， 而且使得故障恢复的时间与 总数据集大小无关。

内存快照技术分配产生的所有内存页面如果全 部由 Log-Structured型写入 持久化到 SSD中， 则会产生过多的冗余数据， 使得 SSD写入带宽的利用率过于 低下。 为了解决这一问题， 我们在实际写入的时候对页面必须进行过滤。 已经 被快照的页面，也就是说更新的版本的版本存 在于内存中，那么在一般情况下， 就不需要将其写入到 SSD中去。

在 B+树型索引结构中， 父节点页面对子节点页面的索引是由逻辑页号 来 表示的。 对于内存快照 B+树结构来说， 逻辑页号就是页面分配的顺序编号， 如果将所有分配的页面依次写入 SSD, 则页面在 SSD上的物理位移与逻辑页号 就建立了一种筒单的——对应关系，即可以由 索引子节点页面的逻辑页面直接 计算获得物理位移，冗余页面过滤的过程实际 上也就跳过了部分分配的页面而 没有将其真正写入，那么前文提到的分配页面 的逻辑页号和写入 SSD的物理位 移之间的筒单对应关系也就不存在了。那么我 们必须要对这个对应关系进行一 些额外的管理以使得可以顺利通过逻辑页号找 到物理的页面位置。

我们提出利用文件系统空洞文件的支持来管理 逻辑页号和实际物理位置 的关系， 大大降低了系统的实现和逻辑复杂度， 并且通过对内核级功能支持的 灵活运用， 保证了实现的性能。

持久化写入的具体事项通过在页级緩存中运行 的后台异步 Flush线程完成, 该线程持续将页面写入 SSD。 而根据内存快照的特性， 每个提交的根节点都代 表了一个一致的数据视图， 只要确保将当前的 B+树根节点 Flush到 SSD中， 并 记录下根节点所在位置， 就相当于建立了一个数据快照。 Flush线程需要跳过 已被拷贝的页， 这样的跳过使得逻辑的页编号与实际的页物理 位置不相对应， 故本系统中利用文件系统的空洞文件机制，跳 过页面时写入空洞，保持了两者 的对应的逻辑对应关系， 这样就不必引入额外的页面映射管理层。 页面索引号 实际就是顺序写入 SSD的序号，通过索引号的计算可以直接判断该 页是否在写 緩存中， 如果没有命中（页框已经被写请求回收）则根 据索引号可以找到该页 在 SSD中的位置， 然后读取。

操作示例

1、 后台异步写入线程的运行过程说明

图 4显示图 3中发生的写入操作在实际物理写入层面的视� �。 因为发生 D页 面的写入，拷贝生成 3个新页面 D，， Β' , Α' ,按照分配的次序出现在右边的 FIFO 页面緩存队列中（实际上是用环形队列实现， 这里做了筒化， 但不影响原理说 明）。

后台有并发的异步写入线程会在 FIFO队列上顺着页面分配顺序运行， 将 相应位置上的页面写入到 SSD中去。

我们在写入 A, B , D页面的时候，已经知道它们是冗余页面（已� �被拷贝）， 不应该实际将其写入存储设备中。这里我们引 入文件空洞的机制，检查到冗余 页面时， 虽然不进行数据写入，但是利用 lseek系统调用在目前的 Log-Structured 数据文件末尾形成一个页面大小的文件空洞， 依次类推， 直到非冗余页面的时 候， 才真正写入数据。 比如在例子中， 后台 Flush线程首先跳过 D页面， 形成一 个页面大小的空洞， 随后发现 C页面是有效数据， 就将其写入空洞之后， 随后 又需要兆过 A和 B页面， 形成又一个空洞， 大小为两个页面， 随后的 Α，， Β，， C， 页面则正常进行写入。 在这些页面分配的过程中， 逻辑页号都是顺次递增 分配的， 在使用文件空洞机制之后， 我们可以发现， 所有页面还是可以由逻辑 页号乘以页面大小产生的位移来直接进行访问 ，而实际写入文件的量却减少为 4个页面， 起到了过滤冗余写入的作用。

2、 读出操作流程

读出记录操作指给定一个 Key的情况下， 存储系统返回该 Key对应的 Value

( Key和 Value均以字符串表示）。 如图 5 , 读操作的流程大致如下：

1、 从系统获得出当前的 B+树根节点， 作为 B+树索引查找的起点。 因为前 文所述的内存快照技术的运用， 读操作无需对页面进行加锁。

2、 对于包括根节点在内的中间节点页面进行页面 内部的折半查找， 取得 正确的索引项， 获得下一个需要进行查找的页面逻辑页号。这 一查找过程直到 获得叶子节点后终结。

3、 通过逻辑页号获得物理页面的操作通过调用 Memory Pool模块完成。 Memory Pool模块将该页号与目前 FIFO队列中最小的页号相比较， 判断是否在 队列中。 如果比最小页号大， 也就是緩存命中的情况， 可以直接返回 Memory Pool中的页面引用。

4、 如果没有命中緩冲， 则需要分配额外页面空间， 然后到 SSD中读取。 用逻辑页号获得 SSD中的数据需要通过调用 Log Manager模块的功能来完成。 因为文件空洞机制的作用， Log Manager模块此时的任务非常筒单， 只需要用 逻辑页号乘以页面大小， 然后读取相应页面即可。

5、 最后在叶子节点页面中完成最终的 Key-Value对查找， 返回结果。

(3) 写入操作流程

写入记录操作指的是将一个 Key值和一个 Value值以数据对的方式写入到 存储系统中， 供以后的读取。 存储系统采用单写多读的线程模型， 写线程进入 索引结构时始终面对最新的 B+树根节点， 这点不同于读线程面对的情况。

如图 6, 写操作的流程大致如下：

1、 写操作需要进行的第一步和读操作是一致的， 是通过一次 B+树的查找 来确定要插入新数据记录的正确位置， 所进行的操作与读操作基本一样， 就不 再赘述。 有一点不同的是， 因为对于 Memory Pool模块中的 FIFO环形队列 Read Region的改变全部发生在写线程中，所以写线程 本身对于页面緩存命中的判断 就不需要进行加锁了。

2、 完成查找正确插入位置的操作时， 写线程将根节点到插入位置页面整 条路径的页面压入一个栈结构中 ,该栈结构中除了保存指向对应页面的指针外 , 还保存了路径中的中间节点指向子节点的页内 索引号。

3、 写入页面的过程将会依次弹出栈中页指针， 这里使用内存快照的技术 来避免加锁保护， 对一个页面的修改， 需要先调用 Memory Pool的接口来请求 一个新的页面， 然后将源页面的内容拷贝到新页面中， 再进行修改操作。 在随 后弹出的父节点页面中，需要将原先指向子节 点的索引页号修改为新的逻辑页 号。 4、 父节点页面中， 需要将原先指向子节点的索引页号修改为新的 逻辑页 号， 这个修改也同样是利用内存快照机制完成的。 如果子节点发生了分裂， 则 还需要插入分裂点。

5、 当整个写操作完成后， 进行提交， 需要进行的操作是将已经完成写入 或者更新的所有页面并入 Read Region中， 然后修改新的 B+树根节点为当前的 索引 B+树根节点。

本发明还公开一种基于 SSD的 Key- Value型本地存储系统， 包括： 内存快照 B+树索引模块， 用于对于数据采用内存快照 B+树索引结构， 进 行内存中的读写分离操作；

内存池管理模块， 用于经过索引后的数据， 针对 B+树页面使用 FIFO队列 管理緩存；

日志型数据管理模块， 用于对所述数据页面追加写入 SSD, 通过空洞文件 机制在日志型追加写入的数据中实现逻辑页号 和物理位置的映射管理。

所述的基于 SSD的 Key- Value型本地存储系统， 所述内存快照 B+树索引模 块包括：

首节点更新操作模块， 用于根节点 A为 B+树根节点， 如对首节点 D做一次 更新操作； 首先将首节点 D页面进行拷贝， 拷贝的副本页面为首节点 D，， 然后 在首节点 D， 页面中进行所需要的更新；

中间节点更新操作模块， 用于进行完这个操作以后， 需要对中间节点 B中 对首节点 D， 的索引也做更新， 根据内存快照的原则， 为了防止读写竟争， 需 要先对中间节点 B进行拷贝， 然后在副本中间节点 B， 中进行更新操作； 依次 操作， 所述拷贝过程也在根节点 A上发生；

更新完成模块， 用于当整个更新操作完成时， 形成了一棵以根节点 A， 为 根节点的新 B+树， 根节点 A， 相比较 A, 指向 B， 的索引有变化， 而其他索引 仍然不变；

页面指向模块， 用于中间节点 B， 更新了指向首节点 D， 的页面， 其他索 引没有变化。

所述的基于 SSD的 Key- Value型本地存储系统， 所述内存池管理模块包括： 形成队列结构模块， 用于 FIFO页级写緩存的设计使用环形队列的结构， 整个环划分为 write区域和 read区域， write区域中为正在进行写操作， 尚未提交 的页面， read区域中为已经完成写操作并提交的页面， 可以供读操作从緩存中 获得；

指针位置前移模块，用于 write指针指向 write区域的末尾，该指针也是下一 个写操作向写緩存申请新页面时装载的位置， 在系统运行时， write指针位置不 断获得新页面并沿着环形队列前移， 同时完成写操作的页面提交为 read区域， 并由 read指针指向新近提交的页面位置；

持久化模块， 用于在这个过程中，后台异步写入线程将以适 合应用需求的 速度将 read区域依次持久化到 SSD中， 已经完成持久化的页面区域称为 flush区 域， 一个 flush指针指向下一个要做持久化的页面， flush区域为 read区域的一部 分， 供 write指针获得新页面的区域；

对应写入模块，用于在后台异步写入线程将相 应页面写入 SSD中的过程中， 已经在环形队列中存在更新拷贝的页面属于冗 余页面， 不需要进行写入， 本系 统中将跳过该种页面， 同时在 SSD的数据文件中制造同样大小的文件空洞， 该 文件空洞不占用实际空间也不进行实际写入操 作，但保持了逻辑页号和数据页 面在文件中位移的对应关系。

所述的基于 SSD的 Key- Value型本地存储系统，所述日志型数据管理模� ��包 括：

索引入口模块，用于获得当前的 B+树根节点，作为 B+树索引查找的起点； 获得索引项模块，用于对于包括根节点在内的 中间节点页面进行页面内部 的折半查找， 取得正确的索引项， 获得下一个需要进行查找的页面逻辑页号， 这一查找过程直到获得叶子节点后终结； 因为内存快照技术的使用，读操作无 需对页面进行加锁；

调用内存池管理模块，用于通过逻辑页号获得 物理页面的操作通过调用内 存池管理模块完成； 内存池管理模块将该页号与 FIFO队列中最小的页号相比 较， 判断是否在队列中， 如果比最小页号大， 也就是緩存命中的情况， 直接返 回内存池管理模块中的页面引用；

分配页面空间模块， 用于如果没有命中緩冲， 则需要分配额外页面空间， 然后到 SSD中读取； 用逻辑页号获得 SSD中的数据需要通过调用日志型数据管 理模块的功能来完成； 因为文件空洞机制的作用， 日志型数据管理模块此时的 任务非常筒单， 只需要用逻辑页号乘以页面大小， 然后读取相应页面即可； 完成查找模块， 用于最后在叶子节点页面中完成最终的 Key- Value对查找， 返回结果。

所述的基于 SSD的 Key- Value型本地存储系统，所述日志型数据管理模� ��还 包括：

插入位置模块， 用于通过 B+树的查找来确定要插入新数据记录的正确位 置， 获得当前的 B+树根节点， 作为 B+树索引查找的起点； 读操作无需对页面 进行加锁； 对于内存池管理模块中的 FIFO环形队列 Read Region的改变全部发 生在写线程中， 所以写线程本身对于页面緩存命中的判断就不 需要进行加锁； 页面压入模块， 用于完成查找正确插入位置的操作时， 写线程将根节点到 插入位置页面整条路径的页面压入一个栈结构 中 ,该栈结构中除了保存指向对 应页面的指针外， 还保存了路径中的中间节点指向子节点的页内 索引号；

页面修改模块， 用于写入页面的过程将会依次弹出栈中页指针 ， 这里使用 内存快照的技术来避免加锁保护，对一个页面 的修改， 需要先调用内存池管理 模块的接口来请求一个新的页面， 然后将源页面的内容拷贝到新页面中，再进 行 4爹改操作； 在随后弹出的父节点页面中， 需要将原先指向子节点的索引页号 修改为新的逻辑页号；

修改逻辑页号模块， 用于父节点页面中， 需要将原先指向子节点的索引页 号修改为新的逻辑页号， 这个修改也同样是利用内存快照完成； 如果子节点发 生了分裂， 则还需要插入分裂点；

提交模块， 用于当整个写操作完成后， 进行提交， 需要进行的操作是将已 经完成写入或者更新的所有页面并入 Read Region中， 然后修改新的 B+树根节 点为当前的索引 B+树根节点。

本领域的技术人员在不脱离权利要求书确定的 本发明的精神和范围的条 件下，还可以对以上内容进行各种各样的修改 。 因此本发明的范围并不仅限于 以上的说明， 而是由权利要求书的范围来确定的。