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

本書分為三篇，分別涉及大數據處理中的鍵值存儲、容錯存儲、數據一致性三個領域。每篇首先簡要介紹相關領域的基礎知識、系統優化的關鍵技術以及主流的系統等，然後介紹作者在相關領域的部分研究成果。具體來說，在鍵值存儲方面，介紹了動態布隆過濾器設計、哈希分組與鍵值分離技術相結合的存儲結構設計、哈希索引與日誌結構合並樹相結合的索引結構設計等方面的優化方法，旨在降低讀、寫放大，提升讀、寫與範圍查詢的性能；在容錯存儲方面，介紹了糾刪碼的數據佈局、故障數據恢復算法、源數據節點與恢復節點選擇以及系統擴容等方面的優化方法，旨在降低I/O數據量與負載均衡，加速故障恢復；在數據一致性方面，介紹了RedBlue和PoR細粒度一致性模型及其使用方法，為在備份系統中安全使用低延遲的弱一致性同步、提升系統性能提供理論依據和實踐基礎。

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