第1篇 键值存储系统
　　第1章 键值存储
　　本章主要围绕当前大数据的存储需求，概要介绍键值存储系统的主流架构、读写流程、研究热点。本章主要内容安排如下：首先介绍当前大数据的特征以及对存储系统带来的新挑战，键值存储的数据模型与访问接口；然后介绍当前主流的键值存储系统架构，并分析存在的问题与系统设计方面的挑战；*后概述该领域的国际研宄现状与热点。
　　1.1 大数据特征及存储挑战
　　1.1.1 数据存储的发展趋势
　　随着网络与通信技术的飞速发展以及网络终端接入的普及，博客、即时通信、短视频分享等新型服务平台不断涌现，获取网络服务的用户越来越多。根据 WeAreSocial与Hootsuite公司联合发布的Digital 2020[11的统计，截至2020年1月，全球互联网用户数量已超过45亿人，其中社交媒体用户高达38亿人。同时，医疗、交通、金融等行业也纷纷开始利用大数据处理技术进行数据分析等工作。因此产生了大量的数据存储需求，并呈现出以下特征。
　　（1）数据规模大且快速增长。由于Web 2.0技术倡导由用户主导生产数据内容，用户在享用网络应用带来便利的同时，也积极向互联网上传了大量的数据。同时，传统行业在数字化发展过程中，也产生了大量的数据存储需求。例如，医疗卫生领域利用大数据技术，对居民的海量医疗及健康数据进行统计分析[2]。根据国际数据公司IDC的统计，到2025年全球每年产生的数据总量将从2018年的33ZB 增长到175ZB [3]。
　　（2）存取速度要求高。网络服务平台对数据的存取速度也提出了更高的要求。以社交网络为例，知名社交网站Facebook每天都会新增数十亿条内容，对数据的访问也达到了每秒钟几亿次[4]。为了使用户获得良好的体验，这些频繁的数据存取请求需要得到系统的快速响应。
　　（3）非结构化数据占主导。非结构化数据指不方便使用二维逻辑表示的数据，如长文本、图片、音频、视频等。网络应用以及传统行业利用大数据技术产生的数据大多是非结构化数据，如用户在社交网络发布的博文和短视频，医疗领域的健康档案和CT图像等。根据IDC公司的统计，网络和医疗数据中约80%都是非结构化数据[5，6]。
　　综上所述，基于当前的发展趋势，数据存储领域面临着以非结构化数据占主导的海量数据存储需求，网络服务商需要为这些数据提供高效的存取支持，对数据存储系统设计与实现提出了新的挑战。
　　1.1.2 数据存储面临的挑战
　　面对数据的新特征，特别是非结构化数据的高速发展，需要设计针对非结构化数据友好的存储系统，提高非结构数据的存取性能以及系统的扩展能力，以满足用户日益提升的数据存储需求和处理需求。要实现这个目标，面临着以下几个问题。
　　1.可扩展性问题
　　当数据存储系统的数据规模与访问量持续增加，系统性能无法继续满足用户数据存储需求时，就需要对存储系统进行扩展。数据存储系统的扩展方式分为横向扩展与纵向扩展两类，横向扩展指的是利用分布式技术增加更多的存储节点，与当前节点组成一个更大的存储系统；纵向扩展指的是提高当前存储节点的硬件性能，如升级内外存设备和CPU等。
　　当数据存储和访问量显著增大时，为了增强存储节点的负载能力，不得不为其配置核数更多、频率更高的CPU和容量更大、读写性能更强的存储设备。然而，计算机硬件的性能提升与其价格增长并非线性关系，为单台服务器提高配置会带来昂贵的硬件成本，性价比很低。另外，受制于计算机硬件发展水平，纵向扩展能力也存在一定的上限。
　　相比于纵向扩展，存储系统可以通过增加存储节点的方式实现横向扩展，通过添加相对廉价的服务器，便能在理论上对系统的性能和存储容量进行无限扩展，性价比高。但是，横向扩展会带来系统管理上的挑战。
　　2.非结构化数据处理问题
　　对非结构化数据的处理也是数据存储面临的挑战之一。在关系型数据库中，数据遵守严格的数据库存储范式，在添加数据前需要预定义数据格式，难以灵活修改，因此无法快速容纳新的数据类型，也无法高效处理难以用二维逻辑表示的数据。由于非结构化数据的格式缺少明显规律，组成形式灵活，若使用关系型数据库存储，当应用为数据添加新的属性时，需要修改整张关系表的模式，有时甚至需要将原关系表中的所有数据迁移到新表中，显著影响整个系统的服务性能，同时还会大幅增加运维难度。
　　综上所述，传统的关系型数据库不能适应海量非结构化数据的存取需求，在数据存储领域的当前发展趋势下，需要探索新型的数据存储结构。
　　1.2 键值数据模型及访存接口
　　为了应对海量非结构化数据存储的挑战，非关系型数据存储系统开始得到广泛关注和使用[7]，这些系统一般具有以下特征[8]。
　　（1）不要求强一致性的事务支持，有较强的灵活性。
　　（2）对数据存储格式约束较少，容易处理各种类型的数据。
　　（3）访问接口简单易用，减少了对网络应用中不常用复杂查询的支持。
　　这些特征使得非关系型数据存储系统能够处理非结构化数据，拥有高效的数据存取性能。其灵活的数据模型能很好地适应非结构化数据多变的数据特征，同时由于数据之间没有严格的约束关系，也没有强一致性要求，容易横向扩展，扩大系统规模。
　　键值（key value）存储系统就是一个典型的非关系型数据存储系统，其采用扁平化的数据模型和简单灵活的访问接口，具有很好的泛用性，同时还保证了高读写性能与易扩展能力，为海量非结构化数据的存储提供了一个优秀的解决方案。因此，键值存储系统作为后端存储引擎被广泛部署在如分布式文件系统[9]、电子商务系统社交网络等数据密集型应用中，成为数据存储领域的重要组成部分。此外，一些关系型数据库也开始使用键值存储系统为其提供底层存储支持[12]。所以，研究优化键值存储系统的性能，对数据存储领域的发展有重要意义。
　　键值存储系统的数据模型类似于哈希表（Hash table），—个键数据（key）对应一个值数据（value），将键数据和其对应的值数据合称为键值对（key-value pair）。键数据由字符串表示，值数据可以是任意类型，系统内部并不关心值数据具体表示的数据类型，只是将值数据视作二进制串处理，因此非常适合存储类型多变的非结构化数据。基于这种扁平化数据模型，键值存储系统支持以下接口，用于存取数据。
　　（1） Put （key， value）:写操作，将键值对（key， value）写入系统，写入新数据和更新已有数据均使用相同的接口。
　　（2） Delete （key）:删除操作，从系统中刪除键对应的键值对。
　　（3） Get （key）:点查询操作，读取键对应的值数据。
　　（4） Scan （start_key， end_key）:范围查询操作，按用户定义的顺序关系（一般为字典序）读取键在区间[start_key， end_key]内的所有键值对。
　　可以看出键值存储系统支持的存取操作非常简单，不同键值对间不存在访问依赖，于是，每个键值对都可以独立地存储在任意存储节点上，因此随着数据规模的增大，系统容易进行横向扩展。
　　1.3系统架构及关键问题
　　键值存储系统中常见的数据结构有哈希表和日志结构合并树（LSM-tree）。其中，基于哈希表的系统支持对键值对的快速点查询，但是难以进行高效范围查询，并且内存开销很高。正是由于这些特性，哈希表主要应用在数据库索引与缓存系统中。基于日志结构合并树将随机写入转化为顺序写入，能够充分利用设备的带宽，具有高效的写入性能，因此在大规模持久化键值存储中广泛应用。本篇介绍的键值存储技术与系统都是基于日志结构合并树的键值存储系统。
　　1.3.1 常见数据结构
　　1.哈希表的结构
　　图1.1展示了一个简单的哈希表，它是一种可以将键数据映射到值数据的结构。哈希表在进行映射的过程中，以键数据作为输入，使用哈希函数将其计算为哈希码，以此作为表中位置的索引。常见的哈希算法有除留余数、随机数法、平方取中法等。
　　图1.1 哈希表的结构
　　理想情况下，哈希函数会为每个键数据生成唯一的哈希码作为索引，但大多数哈希表设计并不能达到完美哈希的程度，无法避免哈希冲突的发生，即多个键数据产生了相同的哈希值。为了应对这些冲突，有以下几种常见的方法：①开放地址法，当发生地址冲突时，按照某种方法继续探测哈希表中的其他存储单元，直到找到空位置；②链地址法，产生哈希冲突后在存储数据后面加一个链表，管理发生冲突的数据；③公共溢出区法，建立一个特殊存储空间，专门存放冲突的数据。若通过这些方法仍然无法解决哈希冲突，则需要对哈希表进行扩容。
　　基于哈希表的索引具有以下特点：①点查询速度快，通过键数据就能直接计算值数据的存储地址，查询效率极高；②存在空间浪费，随着哈希空间利用率的

目录
前言
第1篇键值存储系统
第1章键值存储 3
1.1 大数据特征及存储挑战 3
1.1.1 数据存储的发展趋势 3
1.1.2 数据存储面临的挑战 4
1.2 键值数据模型及访存接口 5
1.3 系统架构及关键问题 6
1.3.1 常见数据结构 6
1.3.2 基于日志结构合并树的键值存储系统 7
1.3.3 写放大问题 11
1.3.4 读放大问题 11
1.4 相关研究 12
1.4.1 写性能优化 12
1.4.2 读性能优化 12
1.5 本章小结 13
附录专业名词中英文对照表 13
第2章 HashKV：基于哈希分组的键值系统 15
2.1 键值分离关键问题分析 15
2.2 HashKV的主要设计思路 17
2.3 HashKV的核心技术简介 18
2.3.1 存储管理 18
2.3.2 垃圾回收 20
2.3.3 冷热感知 21
2.3.4 选择性键值分离 22
2.3.5 崩溃一致性 22
2.4 优化实现 22
2.5 实验评估 24
2.5.1 实验设置 24
2.5.2 性能比较 24
2.6 本章小结 27
第3章 ElasticBF：弹性布隆过滤器 29
3.1 静态布隆过滤器的不足 29
3.1.1 布隆过滤器 29
3.1.2 键值存储系统访问特征 30
3.1.3 布隆过滤器的动态和静态分配策略对比 32
3.2 ElasticBF的设计与实现 33
3.2.1 细粒度布隆过滤器分配模块 35
3.2.2 热度管理模块 37
3.2.3 布隆过滤器内存管理模块 38
3.2.4 系统实现 39
3.3 实验评估 40
3.3.1 实验设置 40
3.3.2 实验性能分析 41
3.4 本章小结 45
第4章 UniKV：统一索引的键值存储 46
4.1 哈希索引与日志结构合并树对比分析 46
4.2 UniKV设计 48
4.2.1 差异化的索引设计 49
4.2.2 键值数据的部分分离存储 51
4.2.3 基于键范围的数据动态分区 52
4.2.4 范围查询优化 54
4.2.5 崩溃一致性 54
4.3 实验评估 55
4.3.1 实验设置 55
4.3.2 基准测试 56
4.3.3 混合工作负载下的性能 57
4.3.4 YCSB工作负载下的性能 58
4.4 本章小结 59
第5章 DiffKV：差异化键值分离管理 60
5.1 现有优化技术缺点分析 60
5.2 DiffKV的概要结构 62
5.2.1 系统架构 62
5.2.2 数据组织结构 63
5.3 DiffKV的优化实现 64
5.3.1 合并触发 merge 64
5.3.2 merge过程的进一步优化 65
5.3.3 垃圾回收 67
5.3.4 崩溃一致性 68
5.4 细粒度的键值分离策略 68
5.4.1 差异化的值管理 68
5.4.2 冷热感知的 vLogs 69
5.5 实验性能 70
5.5.1 实验设置 70
5.5.2 基准测试 71
5.5.3 YCSB测试 72
5.6 本章小结 74
第6章应用案例 76
6.1 开源系统 76
6.2 图处理系统 78
6.2.1 图分析场景 78
6.2.2 基于键值的图存储管理 80
6.3 分布式数据库 83
6.4 本章小结 85
第2篇基于纠删码的容错存储
第7章容错存储系统 89
7.1 海量数据存储 89
7.1.1 数据规模 89
7.1.2 大规模数据存储系统 90
7.2 容错存储系统 90
7.2.1 存储系统容错的重要性 90
7.2.2 容错存储技术概要 91
7.3 主流容错存储技术简介 91
7.3.1 多副本 91
7.3.2 RAID 92
7.3.3 纠删码 96
7.3.4 再生码 96
7.4 本章小结 97
第8章 RDP编码单磁盘故障修复过程优化 98
8.1 RDP码简介 98
8.2 RDP码传统的单盘故障恢复方法 100
8.3 行校验与对角线校验混合的单盘故障恢复方法 101
8.3.1 问题描述 101
8.3.2 数据读取量的理论下界 103
8.3.3 修复过程中的负载均衡问题 106
8.4 RDP码的单盘故障混合修复算法 113
8.5 实验结果 114
8.5.1 数据块大小的影响 114
8.5.2 磁盘个数的影响 116
8.6 本章小结 118
第9章故障修复任务的分批优化调度 120
9.1 故障分批修复的负载不均衡问题 120
9.2 分批修复故障数据的性能瓶颈分析 121
9.2.1 故障修复的网络瓶颈 122
9.2.2 修复批次内数据非均匀分布 123
9.3 分批修复模型 125
9.3.1 替换节点图 125
9.3.2 源节点图 126
9.3.3 一批修复任务选择算法 126
9.4 SelectiveEC的设计 127
9.4.1 单节点故障修复 128
9.4.2 异构环境 132
9.4.3 多节点故障修复 132
9.5 实现 133
9.6 性能评估 133
9.6.1 单节点故障修复 134
9.6.2 多节点故障修复 137
9.6.3 Amazon EC2中的修复性能 138
9.6.4 模拟大规模分布式存储系统 138
9.7 本章小结 139
第10章多副本到纠删码的转换 141
10.1 相关背景 141
10.2 传统三副本到纠删码的静态转换方法问题分析 143
10.3 动态条带构建技术 145
10.3.1 基本思路 145
10.3.2 示例 146
10.4 动态条带构建算法 147
10.4.1 算法 147
10.4.2 性能与实现复杂度分析 148
10.5 动态条带构建方法的系统集成 149
10.6 实验与性能分析 152
10.6.1 实验环境 152
10.6.2 1000Mbit/s网络实验结果 152
10.6.3 100Mbit/s网络实验结果 153
10.6.4 编码转换对前台读写请求的影响 153
10.6.5 编码转换对前台应用的影响 155
10.7 本章小结 157
第11章容错存储系统扩容 158
11.1 CRS码简介 158
11.2 CRS码的扩容问题 160
11.3 基于 CRS纠删码扩容优化的基本思路示例 162
11.3.1 优化编码矩阵 162
11.3.2 优化迁移策略 163
11.3.3 校验解码数据 163
11.4 CRS扩容算法 164
11.4.1 设计编码矩阵 164
11.4.2 设计迁移策略 165
11.4.3 校验解码数据 167
11.5 实验结果 169
11.5.1 五种扩容策略的比较 169
11.5.2 域参数
w的影响 171
11.5.3 扩容后的编码性能 172
11.6 本章小结 172
第12章基于热度的在线扩容优化机制 174
12.1 已有扩容算法简介 174
12.2 基于热度扩容的必要性分析 176
12.3 热度感知的在线扩容优化机制 177
12.3.1 概要流程 177
12.3.2 详细流程 180
12.4 实验评估 183
12.5 本章小结 185
第3篇数据一致性
第13章分布式一致性 189
13.1 蓬勃发展的互联网服务 189
13.2 异地备份与系统模型 189
13.3 一致性与系统性能的矛盾 191
13.4 异地备份面临的挑战 191
13.5 本章小结 192
第14章 RedBlue一致性模型 193
14.1 已有的一致性模型简介 193
14.1.1 强一致性与弱一致性 193
14.1.2 多种一致性模型的共存 195
14.1.3 其他的相关工作 195
14.2 RedBlue一致性 196
14.2.1 RedBlue一致性的定义 196
14.2.2 状态收敛 197
14.3 副作用的复制 199
14.3.1 影子操作的定义 199
14.3.2 RedBlue一致性再讨论 199
14.3.3 不变式保证 200
14.3.4 操作分类方法 201
14.4 Gemini异地备份系统的设计与实现 202
14.4.1 系统概述 202
14.4.2 事务的排序与复制 203
14.5 应用程序的迁移与适配 204
14.5.1 编写生成操作和影子操作 204
14.5.2 TPC-W影子操作分类 205
14.6 实验结果 206
14.6.1 实验设置 206
14.6.2 TPC-W和RUBiS的测试结果 207
14.6.3 Quoddy的测试结果 209
14.7 本章小结 211
第15章 PoR一致性模型 212
15.1 RedBlue一致性模型的局限 212
15.2 偏序限制一致性 214
15.3 限制的推导 216
15.3.1 状态收敛 216
15.3.2 不变式保证 217
15.3.3 发现限制的算法 218
15.4 Olisipo的设计与实现 219
15.4.1 并发控制协议 220
15.4.2 实现细节 221
15.5 实验评估 222
15.5.1 案例研究 222
15.5.2 实验设置 224
15.5.3 平均用户感知延迟 225
15.5.4 吞吐峰值 225
15.5.5 单个请求的延迟 226
15.5.6 不同并发控制协议的影响 227
15.6 本章小结 228
参考文献 230