大数据存储：键值、容错与一致性

目录
前言
第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