大數據存儲：鍵值、容錯與一致性

目錄
前言
第1篇鍵值存儲系統(tǒng)
第1章鍵值存儲 3
1.1 大數據特征及存儲挑戰(zhàn) 3
1.1.1 數據存儲的發(fā)展趨勢 3
1.1.2 數據存儲面臨的挑戰(zhàn) 4
1.2 鍵值數據模型及訪存接口 5
1.3 系統(tǒng)架構及關鍵問題 6
1.3.1 常見數據結構 6
1.3.2 基于日志結構合并樹的鍵值存儲系統(tǒng) 7
1.3.3 寫放大問題 11
1.3.4 讀放大問題 11
1.4 相關研究 12
1.4.1 寫性能優(yōu)化 12
1.4.2 讀性能優(yōu)化 12
1.5 本章小結 13
附錄專業(yè)名詞中英文對照表 13
第2章 HashKV：基于哈希分組的鍵值系統(tǒng) 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 優(yōu)化實現 22
2.5 實驗評估 24
2.5.1 實驗設置 24
2.5.2 性能比較 24
2.6 本章小結 27
第3章 ElasticBF：彈性布隆過濾器 29
3.1 靜態(tài)布隆過濾器的不足 29
3.1.1 布隆過濾器 29
3.1.2 鍵值存儲系統(tǒng)訪問特征 30
3.1.3 布隆過濾器的動態(tài)和靜態(tài)分配策略對比 32
3.2 ElasticBF的設計與實現 33
3.2.1 細粒度布隆過濾器分配模塊 35
3.2.2 熱度管理模塊 37
3.2.3 布隆過濾器內存管理模塊 38
3.2.4 系統(tǒng)實現 39
3.3 實驗評估 40
3.3.1 實驗設置 40
3.3.2 實驗性能分析 41
3.4 本章小結 45
第4章 UniKV：統(tǒng)一索引的鍵值存儲 46
4.1 哈希索引與日志結構合并樹對比分析 46
4.2 UniKV設計 48
4.2.1 差異化的索引設計 49
4.2.2 鍵值數據的部分分離存儲 51
4.2.3 基于鍵范圍的數據動態(tài)分區(qū) 52
4.2.4 范圍查詢優(yōu)化 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 現有優(yōu)化技術缺點分析 60
5.2 DiffKV的概要結構 62
5.2.1 系統(tǒng)架構 62
5.2.2 數據組織結構 63
5.3 DiffKV的優(yōu)化實現 64
5.3.1 合并觸發(fā) merge 64
5.3.2 merge過程的進一步優(yōu)化 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 開源系統(tǒng) 76
6.2 圖處理系統(tǒng) 78
6.2.1 圖分析場景 78
6.2.2 基于鍵值的圖存儲管理 80
6.3 分布式數據庫 83
6.4 本章小結 85
第2篇基于糾刪碼的容錯存儲
第7章容錯存儲系統(tǒng) 89
7.1 海量數據存儲 89
7.1.1 數據規(guī)模 89
7.1.2 大規(guī)模數據存儲系統(tǒng) 90
7.2 容錯存儲系統(tǒng) 90
7.2.1 存儲系統(tǒng)容錯的重要性 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編碼單磁盤故障修復過程優(yōu)化 98
8.1 RDP碼簡介 98
8.2 RDP碼傳統(tǒng)的單盤故障恢復方法 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章故障修復任務的分批優(yōu)化調度 120
9.1 故障分批修復的負載不均衡問題 120
9.2 分批修復故障數據的性能瓶頸分析 121
9.2.1 故障修復的網絡瓶頸 122
9.2.2 修復批次內數據非均勻分布 123
9.3 分批修復模型 125
9.3.1 替換節(jié)點圖 125
9.3.2 源節(jié)點圖 126
9.3.3 一批修復任務選擇算法 126
9.4 SelectiveEC的設計 127
9.4.1 單節(jié)點故障修復 128
9.4.2 異構環(huán)境 132
9.4.3 多節(jié)點故障修復 132
9.5 實現 133
9.6 性能評估 133
9.6.1 單節(jié)點故障修復 134
9.6.2 多節(jié)點故障修復 137
9.6.3 Amazon EC2中的修復性能 138
9.6.4 模擬大規(guī)模分布式存儲系統(tǒng) 138
9.7 本章小結 139
第10章多副本到糾刪碼的轉換 141
10.1 相關背景 141
10.2 傳統(tǒng)三副本到糾刪碼的靜態(tài)轉換方法問題分析 143
10.3 動態(tài)條帶構建技術 145
10.3.1 基本思路 145
10.3.2 示例 146
10.4 動態(tài)條帶構建算法 147
10.4.1 算法 147
10.4.2 性能與實現復雜度分析 148
10.5 動態(tài)條帶構建方法的系統(tǒng)集成 149
10.6 實驗與性能分析 152
10.6.1 實驗環(huán)境 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章容錯存儲系統(tǒng)擴容 158
11.1 CRS碼簡介 158
11.2 CRS碼的擴容問題 160
11.3 基于 CRS糾刪碼擴容優(yōu)化的基本思路示例 162
11.3.1 優(yōu)化編碼矩陣 162
11.3.2 優(yōu)化遷移策略 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章基于熱度的在線擴容優(yōu)化機制 174
12.1 已有擴容算法簡介 174
12.2 基于熱度擴容的必要性分析 176
12.3 熱度感知的在線擴容優(yōu)化機制 177
12.3.1 概要流程 177
12.3.2 詳細流程 180
12.4 實驗評估 183
12.5 本章小結 185
第3篇數據一致性
第13章分布式一致性 189
13.1 蓬勃發(fā)展的互聯(lián)網服務 189
13.2 異地備份與系統(tǒng)模型 189
13.3 一致性與系統(tǒng)性能的矛盾 191
13.4 異地備份面臨的挑戰(zhàn) 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 狀態(tài)收斂 197
14.3 副作用的復制 199
14.3.1 影子操作的定義 199
14.3.2 RedBlue一致性再討論 199
14.3.3 不變式保證 200
14.3.4 操作分類方法 201
14.4 Gemini異地備份系統(tǒng)的設計與實現 202
14.4.1 系統(tǒng)概述 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 狀態(tài)收斂 216
15.3.2 不變式保證 217
15.3.3 發(fā)現限制的算法 218
15.4 Olisipo的設計與實現 219
15.4.1 并發(fā)控制協(xié)議 220
15.4.2 實現細節(jié) 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 不同并發(fā)控制協(xié)議的影響 227
15.6 本章小結 228
參考文獻 230