大數(shù)據(jù)存儲：鍵值、容錯與一致性

目錄
前言
第1篇鍵值存儲系統(tǒng)
第1章鍵值存儲 3
1.1 大數(shù)據(jù)特征及存儲挑戰(zhàn) 3
1.1.1 數(shù)據(jù)存儲的發(fā)展趨勢 3
1.1.2 數(shù)據(jù)存儲面臨的挑戰(zhàn) 4
1.2 鍵值數(shù)據(jù)模型及訪存接口 5
1.3 系統(tǒng)架構(gòu)及關(guān)鍵問題 6
1.3.1 常見數(shù)據(jù)結(jié)構(gòu) 6
1.3.2 基于日志結(jié)構(gòu)合并樹的鍵值存儲系統(tǒng) 7
1.3.3 寫放大問題 11
1.3.4 讀放大問題 11
1.4 相關(guān)研究 12
1.4.1 寫性能優(yōu)化 12
1.4.2 讀性能優(yōu)化 12
1.5 本章小結(jié) 13
附錄專業(yè)名詞中英文對照表 13
第2章 HashKV：基于哈希分組的鍵值系統(tǒng) 15
2.1 鍵值分離關(guān)鍵問題分析 15
2.2 HashKV的主要設(shè)計思路 17
2.3 HashKV的核心技術(shù)簡介 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)化實(shí)現(xiàn) 22
2.5 實(shí)驗(yàn)評估 24
2.5.1 實(shí)驗(yàn)設(shè)置 24
2.5.2 性能比較 24
2.6 本章小結(jié) 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的設(shè)計與實(shí)現(xiàn) 33
3.2.1 細(xì)粒度布隆過濾器分配模塊 35
3.2.2 熱度管理模塊 37
3.2.3 布隆過濾器內(nèi)存管理模塊 38
3.2.4 系統(tǒng)實(shí)現(xiàn) 39
3.3 實(shí)驗(yàn)評估 40
3.3.1 實(shí)驗(yàn)設(shè)置 40
3.3.2 實(shí)驗(yàn)性能分析 41
3.4 本章小結(jié) 45
第4章 UniKV：統(tǒng)一索引的鍵值存儲 46
4.1 哈希索引與日志結(jié)構(gòu)合并樹對比分析 46
4.2 UniKV設(shè)計 48
4.2.1 差異化的索引設(shè)計 49
4.2.2 鍵值數(shù)據(jù)的部分分離存儲 51
4.2.3 基于鍵范圍的數(shù)據(jù)動態(tài)分區(qū) 52
4.2.4 范圍查詢優(yōu)化 54
4.2.5 崩潰一致性 54
4.3 實(shí)驗(yàn)評估 55
4.3.1 實(shí)驗(yàn)設(shè)置 55
4.3.2 基準(zhǔn)測試 56
4.3.3 混合工作負(fù)載下的性能 57
4.3.4 YCSB工作負(fù)載下的性能 58
4.4 本章小結(jié) 59
第5章 DiffKV：差異化鍵值分離管理 60
5.1 現(xiàn)有優(yōu)化技術(shù)缺點(diǎn)分析 60
5.2 DiffKV的概要結(jié)構(gòu) 62
5.2.1 系統(tǒng)架構(gòu) 62
5.2.2 數(shù)據(jù)組織結(jié)構(gòu) 63
5.3 DiffKV的優(yōu)化實(shí)現(xiàn) 64
5.3.1 合并觸發(fā) merge 64
5.3.2 merge過程的進(jìn)一步優(yōu)化 65
5.3.3 垃圾回收 67
5.3.4 崩潰一致性 68
5.4 細(xì)粒度的鍵值分離策略 68
5.4.1 差異化的值管理 68
5.4.2 冷熱感知的 vLogs 69
5.5 實(shí)驗(yàn)性能 70
5.5.1 實(shí)驗(yàn)設(shè)置 70
5.5.2 基準(zhǔn)測試 71
5.5.3 YCSB測試 72
5.6 本章小結(jié) 74
第6章應(yīng)用案例 76
6.1 開源系統(tǒng) 76
6.2 圖處理系統(tǒng) 78
6.2.1 圖分析場景 78
6.2.2 基于鍵值的圖存儲管理 80
6.3 分布式數(shù)據(jù)庫 83
6.4 本章小結(jié) 85
第2篇基于糾刪碼的容錯存儲
第7章容錯存儲系統(tǒng) 89
7.1 海量數(shù)據(jù)存儲 89
7.1.1 數(shù)據(jù)規(guī)模 89
7.1.2 大規(guī)模數(shù)據(jù)存儲系統(tǒng) 90
7.2 容錯存儲系統(tǒng) 90
7.2.1 存儲系統(tǒng)容錯的重要性 90
7.2.2 容錯存儲技術(shù)概要 91
7.3 主流容錯存儲技術(shù)簡介 91
7.3.1 多副本 91
7.3.2 RAID 92
7.3.3 糾刪碼 96
7.3.4 再生碼 96
7.4 本章小結(jié) 97
第8章 RDP編碼單磁盤故障修復(fù)過程優(yōu)化 98
8.1 RDP碼簡介 98
8.2 RDP碼傳統(tǒng)的單盤故障恢復(fù)方法 100
8.3 行校驗(yàn)與對角線校驗(yàn)混合的單盤故障恢復(fù)方法 101
8.3.1 問題描述 101
8.3.2 數(shù)據(jù)讀取量的理論下界 103
8.3.3 修復(fù)過程中的負(fù)載均衡問題 106
8.4 RDP碼的單盤故障混合修復(fù)算法 113
8.5 實(shí)驗(yàn)結(jié)果 114
8.5.1 數(shù)據(jù)塊大小的影響 114
8.5.2 磁盤個數(shù)的影響 116
8.6 本章小結(jié) 118
第9章故障修復(fù)任務(wù)的分批優(yōu)化調(diào)度 120
9.1 故障分批修復(fù)的負(fù)載不均衡問題 120
9.2 分批修復(fù)故障數(shù)據(jù)的性能瓶頸分析 121
9.2.1 故障修復(fù)的網(wǎng)絡(luò)瓶頸 122
9.2.2 修復(fù)批次內(nèi)數(shù)據(jù)非均勻分布 123
9.3 分批修復(fù)模型 125
9.3.1 替換節(jié)點(diǎn)圖 125
9.3.2 源節(jié)點(diǎn)圖 126
9.3.3 一批修復(fù)任務(wù)選擇算法 126
9.4 SelectiveEC的設(shè)計 127
9.4.1 單節(jié)點(diǎn)故障修復(fù) 128
9.4.2 異構(gòu)環(huán)境 132
9.4.3 多節(jié)點(diǎn)故障修復(fù) 132
9.5 實(shí)現(xiàn) 133
9.6 性能評估 133
9.6.1 單節(jié)點(diǎn)故障修復(fù) 134
9.6.2 多節(jié)點(diǎn)故障修復(fù) 137
9.6.3 Amazon EC2中的修復(fù)性能 138
9.6.4 模擬大規(guī)模分布式存儲系統(tǒng) 138
9.7 本章小結(jié) 139
第10章多副本到糾刪碼的轉(zhuǎn)換 141
10.1 相關(guān)背景 141
10.2 傳統(tǒng)三副本到糾刪碼的靜態(tài)轉(zhuǎn)換方法問題分析 143
10.3 動態(tài)條帶構(gòu)建技術(shù) 145
10.3.1 基本思路 145
10.3.2 示例 146
10.4 動態(tài)條帶構(gòu)建算法 147
10.4.1 算法 147
10.4.2 性能與實(shí)現(xiàn)復(fù)雜度分析 148
10.5 動態(tài)條帶構(gòu)建方法的系統(tǒng)集成 149
10.6 實(shí)驗(yàn)與性能分析 152
10.6.1 實(shí)驗(yàn)環(huán)境 152
10.6.2 1000Mbit/s網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果 152
10.6.3 100Mbit/s網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果 153
10.6.4 編碼轉(zhuǎn)換對前臺讀寫請求的影響 153
10.6.5 編碼轉(zhuǎn)換對前臺應(yīng)用的影響 155
10.7 本章小結(jié) 157
第11章容錯存儲系統(tǒng)擴(kuò)容 158
11.1 CRS碼簡介 158
11.2 CRS碼的擴(kuò)容問題 160
11.3 基于 CRS糾刪碼擴(kuò)容優(yōu)化的基本思路示例 162
11.3.1 優(yōu)化編碼矩陣 162
11.3.2 優(yōu)化遷移策略 163
11.3.3 校驗(yàn)解碼數(shù)據(jù) 163
11.4 CRS擴(kuò)容算法 164
11.4.1 設(shè)計編碼矩陣 164
11.4.2 設(shè)計遷移策略 165
11.4.3 校驗(yàn)解碼數(shù)據(jù) 167
11.5 實(shí)驗(yàn)結(jié)果 169
11.5.1 五種擴(kuò)容策略的比較 169
11.5.2 域參數(shù)
w的影響 171
11.5.3 擴(kuò)容后的編碼性能 172
11.6 本章小結(jié) 172
第12章基于熱度的在線擴(kuò)容優(yōu)化機(jī)制 174
12.1 已有擴(kuò)容算法簡介 174
12.2 基于熱度擴(kuò)容的必要性分析 176
12.3 熱度感知的在線擴(kuò)容優(yōu)化機(jī)制 177
12.3.1 概要流程 177
12.3.2 詳細(xì)流程 180
12.4 實(shí)驗(yàn)評估 183
12.5 本章小結(jié) 185
第3篇數(shù)據(jù)一致性
第13章分布式一致性 189
13.1 蓬勃發(fā)展的互聯(lián)網(wǎng)服務(wù) 189
13.2 異地備份與系統(tǒng)模型 189
13.3 一致性與系統(tǒng)性能的矛盾 191
13.4 異地備份面臨的挑戰(zhàn) 191
13.5 本章小結(jié) 192
第14章 RedBlue一致性模型 193
14.1 已有的一致性模型簡介 193
14.1.1 強(qiáng)一致性與弱一致性 193
14.1.2 多種一致性模型的共存 195
14.1.3 其他的相關(guān)工作 195
14.2 RedBlue一致性 196
14.2.1 RedBlue一致性的定義 196
14.2.2 狀態(tài)收斂 197
14.3 副作用的復(fù)制 199
14.3.1 影子操作的定義 199
14.3.2 RedBlue一致性再討論 199
14.3.3 不變式保證 200
14.3.4 操作分類方法 201
14.4 Gemini異地備份系統(tǒng)的設(shè)計與實(shí)現(xiàn) 202
14.4.1 系統(tǒng)概述 202
14.4.2 事務(wù)的排序與復(fù)制 203
14.5 應(yīng)用程序的遷移與適配 204
14.5.1 編寫生成操作和影子操作 204
14.5.2 TPC-W影子操作分類 205
14.6 實(shí)驗(yàn)結(jié)果 206
14.6.1 實(shí)驗(yàn)設(shè)置 206
14.6.2 TPC-W和RUBiS的測試結(jié)果 207
14.6.3 Quoddy的測試結(jié)果 209
14.7 本章小結(jié) 211
第15章 PoR一致性模型 212
15.1 RedBlue一致性模型的局限 212
15.2 偏序限制一致性 214
15.3 限制的推導(dǎo) 216
15.3.1 狀態(tài)收斂 216
15.3.2 不變式保證 217
15.3.3 發(fā)現(xiàn)限制的算法 218
15.4 Olisipo的設(shè)計與實(shí)現(xiàn) 219
15.4.1 并發(fā)控制協(xié)議 220
15.4.2 實(shí)現(xiàn)細(xì)節(jié) 221
15.5 實(shí)驗(yàn)評估 222
15.5.1 案例研究 222
15.5.2 實(shí)驗(yàn)設(shè)置 224
15.5.3 平均用戶感知延遲 225
15.5.4 吞吐峰值 225
15.5.5 單個請求的延遲 226
15.5.6 不同并發(fā)控制協(xié)議的影響 227
15.6 本章小結(jié) 228
參考文獻(xiàn) 230