掃一掃
關(guān)注中圖網(wǎng)
官方微博
本類五星書更多>
-
>
全國計算機等級考試最新真考題庫模擬考場及詳解·二級MSOffice高級應(yīng)用
-
>
決戰(zhàn)行測5000題(言語理解與表達)
-
>
軟件性能測試.分析與調(diào)優(yōu)實踐之路
-
>
第一行代碼Android
-
>
JAVA持續(xù)交付
-
>
EXCEL最強教科書(完全版)(全彩印刷)
-
>
深度學(xué)習(xí)
大數(shù)據(jù)存儲--鍵值容錯與一致性 版權(quán)信息
- ISBN：9787030730626
- 條形碼：9787030730626 ; 978-7-03-073062-6
- 裝幀：一般膠版紙
- 冊數(shù)：暫無
- 重量：暫無
- 所屬分類：>
大數(shù)據(jù)存儲--鍵值容錯與一致性 內(nèi)容簡介
本書分為三篇，分別涉及大數(shù)據(jù)處理中的鍵值存儲、容錯存儲、數(shù)據(jù)一致性三個領(lǐng)域。每篇首先簡要介紹相關(guān)領(lǐng)域的基礎(chǔ)知識、系統(tǒng)優(yōu)化的關(guān)鍵技術(shù)以及主流的系統(tǒng)等，然后介紹作者在相關(guān)領(lǐng)域的部分研究成果。具體來說，在鍵值存儲方面，介紹了動態(tài)布隆過濾器設(shè)計、哈希分組與鍵值分離技術(shù)相結(jié)合的存儲結(jié)構(gòu)設(shè)計、哈希索引與日志結(jié)構(gòu)合并樹相結(jié)合的索引結(jié)構(gòu)設(shè)計等方面的優(yōu)化方法，旨在降低讀、寫放大，提升讀、寫與范圍查詢的性能；在容錯存儲方面，介紹了糾刪碼的數(shù)據(jù)布局、故障數(shù)據(jù)恢復(fù)算法、源數(shù)據(jù)節(jié)點與恢復(fù)節(jié)點選擇以及系統(tǒng)擴容等方面的優(yōu)化方法，旨在降低I/O數(shù)據(jù)量與負載均衡，加速故障恢復(fù)；在數(shù)據(jù)一致性方面，介紹了RedBlue和PoR細粒度一致性模型及其使用方法，為在備份系統(tǒng)中安全使用低延遲的弱一致性同步、提升系統(tǒng)性能提供理論依據(jù)和實踐基礎(chǔ)。 本書可供從事鍵值存儲、數(shù)據(jù)存儲與數(shù)據(jù)一致性等計算機系統(tǒng)領(lǐng)域研究的科研工作者與研究生參考，也可以作為相關(guān)課程的輔助參考資料。
大數(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)化實現(xiàn) 22
2.5 實驗評估 24
2.5.1 實驗設(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è)計與實現(xiàn) 33
3.2.1 細粒度布隆過濾器分配模塊 35
3.2.2 熱度管理模塊 37
3.2.3 布隆過濾器內(nèi)存管理模塊 38
3.2.4 系統(tǒng)實現(xiàn) 39
3.3 實驗評估 40
3.3.1 實驗設(shè)置 40
3.3.2 實驗性能分析 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 實驗評估 55
4.3.1 實驗設(shè)置 55
4.3.2 基準測試 56
4.3.3 混合工作負載下的性能 57
4.3.4 YCSB工作負載下的性能 58
4.4 本章小結(jié) 59
第5章 DiffKV：差異化鍵值分離管理 60
5.1 現(xiàn)有優(yōu)化技術(shù)缺點分析 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)化實現(xiàn) 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 實驗設(shè)置 70
5.5.2 基準測試 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 行校驗與對角線校驗混合的單盤故障恢復(fù)方法 101
8.3.1 問題描述 101
8.3.2 數(shù)據(jù)讀取量的理論下界 103
8.3.3 修復(fù)過程中的負載均衡問題 106
8.4 RDP碼的單盤故障混合修復(fù)算法 113
8.5 實驗結(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ù)的負載不均衡問題 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é)點圖 125
9.3.2 源節(jié)點圖 126
9.3.3 一批修復(fù)任務(wù)選擇算法 126
9.4 SelectiveEC的設(shè)計 127
9.4.1 單節(jié)點故障修復(fù) 128
9.4.2 異構(gòu)環(huán)境 132
9.4.3 多節(jié)點故障修復(fù) 132
9.5 實現(xiàn) 133
9.6 性能評估 133
9.6.1 單節(jié)點故障修復(fù) 134
9.6.2 多節(jié)點故障修復(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 性能與實現(xiàn)復(fù)雜度分析 148
10.5 動態(tài)條帶構(gòu)建方法的系統(tǒng)集成 149
10.6 實驗與性能分析 152
10.6.1 實驗環(huán)境 152
10.6.2 1000Mbit/s網(wǎng)絡(luò)實驗結(jié)果 152
10.6.3 100Mbit/s網(wǎng)絡(luò)實驗結(jié)果 153
10.6.4 編碼轉(zhuǎn)換對前臺讀寫請求的影響 153
10.6.5 編碼轉(zhuǎn)換對前臺應(yīng)用的影響 155
10.7 本章小結(jié) 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 校驗解碼數(shù)據(jù) 163
11.4 CRS擴容算法 164
11.4.1 設(shè)計編碼矩陣 164
11.4.2 設(shè)計遷移策略 165
11.4.3 校驗解碼數(shù)據(jù) 167
11.5 實驗結(jié)果 169
11.5.1 五種擴容策略的比較 169
11.5.2 域參數(shù)
w的影響 171
11.5.3 擴容后的編碼性能 172
11.6 本章小結(jié) 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 本章小結(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 強一致性與弱一致性 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è)計與實現(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 實驗結(jié)果 206
14.6.1 實驗設(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è)計與實現(xiàn) 219
15.4.1 并發(fā)控制協(xié)議 220
15.4.2 實現(xiàn)細節(jié) 221
15.5 實驗評估 222
15.5.1 案例研究 222
15.5.2 實驗設(shè)置 224
15.5.3 平均用戶感知延遲 225
15.5.4 吞吐峰值 225
15.5.5 單個請求的延遲 226
15.5.6 不同并發(fā)控制協(xié)議的影響 227
15.6 本章小結(jié) 228
參考文獻 230
前言
第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)化實現(xiàn) 22
2.5 實驗評估 24
2.5.1 實驗設(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è)計與實現(xiàn) 33
3.2.1 細粒度布隆過濾器分配模塊 35
3.2.2 熱度管理模塊 37
3.2.3 布隆過濾器內(nèi)存管理模塊 38
3.2.4 系統(tǒng)實現(xiàn) 39
3.3 實驗評估 40
3.3.1 實驗設(shè)置 40
3.3.2 實驗性能分析 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 實驗評估 55
4.3.1 實驗設(shè)置 55
4.3.2 基準測試 56
4.3.3 混合工作負載下的性能 57
4.3.4 YCSB工作負載下的性能 58
4.4 本章小結(jié) 59
第5章 DiffKV：差異化鍵值分離管理 60
5.1 現(xiàn)有優(yōu)化技術(shù)缺點分析 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)化實現(xiàn) 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 實驗設(shè)置 70
5.5.2 基準測試 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 行校驗與對角線校驗混合的單盤故障恢復(fù)方法 101
8.3.1 問題描述 101
8.3.2 數(shù)據(jù)讀取量的理論下界 103
8.3.3 修復(fù)過程中的負載均衡問題 106
8.4 RDP碼的單盤故障混合修復(fù)算法 113
8.5 實驗結(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ù)的負載不均衡問題 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é)點圖 125
9.3.2 源節(jié)點圖 126
9.3.3 一批修復(fù)任務(wù)選擇算法 126
9.4 SelectiveEC的設(shè)計 127
9.4.1 單節(jié)點故障修復(fù) 128
9.4.2 異構(gòu)環(huán)境 132
9.4.3 多節(jié)點故障修復(fù) 132
9.5 實現(xiàn) 133
9.6 性能評估 133
9.6.1 單節(jié)點故障修復(fù) 134
9.6.2 多節(jié)點故障修復(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 性能與實現(xiàn)復(fù)雜度分析 148
10.5 動態(tài)條帶構(gòu)建方法的系統(tǒng)集成 149
10.6 實驗與性能分析 152
10.6.1 實驗環(huán)境 152
10.6.2 1000Mbit/s網(wǎng)絡(luò)實驗結(jié)果 152
10.6.3 100Mbit/s網(wǎng)絡(luò)實驗結(jié)果 153
10.6.4 編碼轉(zhuǎn)換對前臺讀寫請求的影響 153
10.6.5 編碼轉(zhuǎn)換對前臺應(yīng)用的影響 155
10.7 本章小結(jié) 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 校驗解碼數(shù)據(jù) 163
11.4 CRS擴容算法 164
11.4.1 設(shè)計編碼矩陣 164
11.4.2 設(shè)計遷移策略 165
11.4.3 校驗解碼數(shù)據(jù) 167
11.5 實驗結(jié)果 169
11.5.1 五種擴容策略的比較 169
11.5.2 域參數(shù)
w的影響 171
11.5.3 擴容后的編碼性能 172
11.6 本章小結(jié) 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 本章小結(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 強一致性與弱一致性 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è)計與實現(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 實驗結(jié)果 206
14.6.1 實驗設(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è)計與實現(xiàn) 219
15.4.1 并發(fā)控制協(xié)議 220
15.4.2 實現(xiàn)細節(jié) 221
15.5 實驗評估 222
15.5.1 案例研究 222
15.5.2 實驗設(shè)置 224
15.5.3 平均用戶感知延遲 225
15.5.4 吞吐峰值 225
15.5.5 單個請求的延遲 226
15.5.6 不同并發(fā)控制協(xié)議的影響 227
15.6 本章小結(jié) 228
參考文獻 230
展開全部
大數(shù)據(jù)存儲--鍵值容錯與一致性 節(jié)選
第1篇 鍵值存儲系統(tǒng) 第1章 鍵值存儲 本章主要圍繞當(dāng)前大數(shù)據(jù)的存儲需求，概要介紹鍵值存儲系統(tǒng)的主流架構(gòu)、讀寫流程、研究熱點。本章主要內(nèi)容安排如下：首先介紹當(dāng)前大數(shù)據(jù)的特征以及對存儲系統(tǒng)帶來的新挑戰(zhàn)，鍵值存儲的數(shù)據(jù)模型與訪問接口；然后介紹當(dāng)前主流的鍵值存儲系統(tǒng)架構(gòu)，并分析存在的問題與系統(tǒng)設(shè)計方面的挑戰(zhàn)；*后概述該領(lǐng)域的國際研宄現(xiàn)狀與熱點。 1.1 大數(shù)據(jù)特征及存儲挑戰(zhàn) 1.1.1 數(shù)據(jù)存儲的發(fā)展趨勢 隨著網(wǎng)絡(luò)與通信技術(shù)的飛速發(fā)展以及網(wǎng)絡(luò)終端接入的普及，博客、即時通信、短視頻分享等新型服務(wù)平臺不斷涌現(xiàn)，獲取網(wǎng)絡(luò)服務(wù)的用戶越來越多。根據(jù) WeAreSocial與Hootsuite公司聯(lián)合發(fā)布的Digital 2020[11的統(tǒng)計，截至2020年1月，全球互聯(lián)網(wǎng)用戶數(shù)量已超過45億人，其中社交媒體用戶高達38億人。同時，醫(yī)療、交通、金融等行業(yè)也紛紛開始利用大數(shù)據(jù)處理技術(shù)進行數(shù)據(jù)分析等工作。因此產(chǎn)生了大量的數(shù)據(jù)存儲需求，并呈現(xiàn)出以下特征。 （1）數(shù)據(jù)規(guī)模大且快速增長。由于Web 2.0技術(shù)倡導(dǎo)由用戶主導(dǎo)生產(chǎn)數(shù)據(jù)內(nèi)容，用戶在享用網(wǎng)絡(luò)應(yīng)用帶來便利的同時，也積極向互聯(lián)網(wǎng)上傳了大量的數(shù)據(jù)。同時，傳統(tǒng)行業(yè)在數(shù)字化發(fā)展過程中，也產(chǎn)生了大量的數(shù)據(jù)存儲需求。例如，醫(yī)療衛(wèi)生領(lǐng)域利用大數(shù)據(jù)技術(shù)，對居民的海量醫(yī)療及健康數(shù)據(jù)進行統(tǒng)計分析[2]。根據(jù)國際數(shù)據(jù)公司IDC的統(tǒng)計，到2025年全球每年產(chǎn)生的數(shù)據(jù)總量將從2018年的33ZB 增長到175ZB [3]。 （2）存取速度要求高。網(wǎng)絡(luò)服務(wù)平臺對數(shù)據(jù)的存取速度也提出了更高的要求。以社交網(wǎng)絡(luò)為例，知名社交網(wǎng)站Facebook每天都會新增數(shù)十億條內(nèi)容，對數(shù)據(jù)的訪問也達到了每秒鐘幾億次[4]。為了使用戶獲得良好的體驗，這些頻繁的數(shù)據(jù)存取請求需要得到系統(tǒng)的快速響應(yīng)。 （3）非結(jié)構(gòu)化數(shù)據(jù)占主導(dǎo)。非結(jié)構(gòu)化數(shù)據(jù)指不方便使用二維邏輯表示的數(shù)據(jù)，如長文本、圖片、音頻、視頻等。網(wǎng)絡(luò)應(yīng)用以及傳統(tǒng)行業(yè)利用大數(shù)據(jù)技術(shù)產(chǎn)生的數(shù)據(jù)大多是非結(jié)構(gòu)化數(shù)據(jù)，如用戶在社交網(wǎng)絡(luò)發(fā)布的博文和短視頻，醫(yī)療領(lǐng)域的健康檔案和CT圖像等。根據(jù)IDC公司的統(tǒng)計，網(wǎng)絡(luò)和醫(yī)療數(shù)據(jù)中約80%都是非結(jié)構(gòu)化數(shù)據(jù)[5，6]。 綜上所述，基于當(dāng)前的發(fā)展趨勢，數(shù)據(jù)存儲領(lǐng)域面臨著以非結(jié)構(gòu)化數(shù)據(jù)占主導(dǎo)的海量數(shù)據(jù)存儲需求，網(wǎng)絡(luò)服務(wù)商需要為這些數(shù)據(jù)提供高效的存取支持，對數(shù)據(jù)存儲系統(tǒng)設(shè)計與實現(xiàn)提出了新的挑戰(zhàn)。 1.1.2 數(shù)據(jù)存儲面臨的挑戰(zhàn) 面對數(shù)據(jù)的新特征，特別是非結(jié)構(gòu)化數(shù)據(jù)的高速發(fā)展，需要設(shè)計針對非結(jié)構(gòu)化數(shù)據(jù)友好的存儲系統(tǒng)，提高非結(jié)構(gòu)數(shù)據(jù)的存取性能以及系統(tǒng)的擴展能力，以滿足用戶日益提升的數(shù)據(jù)存儲需求和處理需求。要實現(xiàn)這個目標，面臨著以下幾個問題。 1.可擴展性問題 當(dāng)數(shù)據(jù)存儲系統(tǒng)的數(shù)據(jù)規(guī)模與訪問量持續(xù)增加，系統(tǒng)性能無法繼續(xù)滿足用戶數(shù)據(jù)存儲需求時，就需要對存儲系統(tǒng)進行擴展。數(shù)據(jù)存儲系統(tǒng)的擴展方式分為橫向擴展與縱向擴展兩類，橫向擴展指的是利用分布式技術(shù)增加更多的存儲節(jié)點，與當(dāng)前節(jié)點組成一個更大的存儲系統(tǒng)；縱向擴展指的是提高當(dāng)前存儲節(jié)點的硬件性能，如升級內(nèi)外存設(shè)備和CPU等。 當(dāng)數(shù)據(jù)存儲和訪問量顯著增大時，為了增強存儲節(jié)點的負載能力，不得不為其配置核數(shù)更多、頻率更高的CPU和容量更大、讀寫性能更強的存儲設(shè)備。然而，計算機硬件的性能提升與其價格增長并非線性關(guān)系，為單臺服務(wù)器提高配置會帶來昂貴的硬件成本，性價比很低。另外，受制于計算機硬件發(fā)展水平，縱向擴展能力也存在一定的上限。 相比于縱向擴展，存儲系統(tǒng)可以通過增加存儲節(jié)點的方式實現(xiàn)橫向擴展，通過添加相對廉價的服務(wù)器，便能在理論上對系統(tǒng)的性能和存儲容量進行無限擴展，性價比高。但是，橫向擴展會帶來系統(tǒng)管理上的挑戰(zhàn)。 2.非結(jié)構(gòu)化數(shù)據(jù)處理問題 對非結(jié)構(gòu)化數(shù)據(jù)的處理也是數(shù)據(jù)存儲面臨的挑戰(zhàn)之一。在關(guān)系型數(shù)據(jù)庫中，數(shù)據(jù)遵守嚴格的數(shù)據(jù)庫存儲范式，在添加數(shù)據(jù)前需要預(yù)定義數(shù)據(jù)格式，難以靈活修改，因此無法快速容納新的數(shù)據(jù)類型，也無法高效處理難以用二維邏輯表示的數(shù)據(jù)。由于非結(jié)構(gòu)化數(shù)據(jù)的格式缺少明顯規(guī)律，組成形式靈活，若使用關(guān)系型數(shù)據(jù)庫存儲，當(dāng)應(yīng)用為數(shù)據(jù)添加新的屬性時，需要修改整張關(guān)系表的模式，有時甚至需要將原關(guān)系表中的所有數(shù)據(jù)遷移到新表中，顯著影響整個系統(tǒng)的服務(wù)性能，同時還會大幅增加運維難度。 綜上所述，傳統(tǒng)的關(guān)系型數(shù)據(jù)庫不能適應(yīng)海量非結(jié)構(gòu)化數(shù)據(jù)的存取需求，在數(shù)據(jù)存儲領(lǐng)域的當(dāng)前發(fā)展趨勢下，需要探索新型的數(shù)據(jù)存儲結(jié)構(gòu)。 1.2 鍵值數(shù)據(jù)模型及訪存接口 為了應(yīng)對海量非結(jié)構(gòu)化數(shù)據(jù)存儲的挑戰(zhàn)，非關(guān)系型數(shù)據(jù)存儲系統(tǒng)開始得到廣泛關(guān)注和使用[7]，這些系統(tǒng)一般具有以下特征[8]。 （1）不要求強一致性的事務(wù)支持，有較強的靈活性。 （2）對數(shù)據(jù)存儲格式約束較少，容易處理各種類型的數(shù)據(jù)。 （3）訪問接口簡單易用，減少了對網(wǎng)絡(luò)應(yīng)用中不常用復(fù)雜查詢的支持。 這些特征使得非關(guān)系型數(shù)據(jù)存儲系統(tǒng)能夠處理非結(jié)構(gòu)化數(shù)據(jù)，擁有高效的數(shù)據(jù)存取性能。其靈活的數(shù)據(jù)模型能很好地適應(yīng)非結(jié)構(gòu)化數(shù)據(jù)多變的數(shù)據(jù)特征，同時由于數(shù)據(jù)之間沒有嚴格的約束關(guān)系，也沒有強一致性要求，容易橫向擴展，擴大系統(tǒng)規(guī)模。 鍵值（key value）存儲系統(tǒng)就是一個典型的非關(guān)系型數(shù)據(jù)存儲系統(tǒng)，其采用扁平化的數(shù)據(jù)模型和簡單靈活的訪問接口，具有很好的泛用性，同時還保證了高讀寫性能與易擴展能力，為海量非結(jié)構(gòu)化數(shù)據(jù)的存儲提供了一個優(yōu)秀的解決方案。因此，鍵值存儲系統(tǒng)作為后端存儲引擎被廣泛部署在如分布式文件系統(tǒng)[9]、電子商務(wù)系統(tǒng)社交網(wǎng)絡(luò)等數(shù)據(jù)密集型應(yīng)用中，成為數(shù)據(jù)存儲領(lǐng)域的重要組成部分。此外，一些關(guān)系型數(shù)據(jù)庫也開始使用鍵值存儲系統(tǒng)為其提供底層存儲支持[12]。所以，研究優(yōu)化鍵值存儲系統(tǒng)的性能，對數(shù)據(jù)存儲領(lǐng)域的發(fā)展有重要意義。 鍵值存儲系統(tǒng)的數(shù)據(jù)模型類似于哈希表（Hash table），—個鍵數(shù)據(jù)（key）對應(yīng)一個值數(shù)據(jù)（value），將鍵數(shù)據(jù)和其對應(yīng)的值數(shù)據(jù)合稱為鍵值對（key-value pair）。鍵數(shù)據(jù)由字符串表示，值數(shù)據(jù)可以是任意類型，系統(tǒng)內(nèi)部并不關(guān)心值數(shù)據(jù)具體表示的數(shù)據(jù)類型，只是將值數(shù)據(jù)視作二進制串處理，因此非常適合存儲類型多變的非結(jié)構(gòu)化數(shù)據(jù)。基于這種扁平化數(shù)據(jù)模型，鍵值存儲系統(tǒng)支持以下接口，用于存取數(shù)據(jù)。 （1） Put （key， value）:寫操作，將鍵值對（key， value）寫入系統(tǒng)，寫入新數(shù)據(jù)和更新已有數(shù)據(jù)均使用相同的接口。 （2） Delete （key）:刪除操作，從系統(tǒng)中刪除鍵對應(yīng)的鍵值對。 （3） Get （key）:點查詢操作，讀取鍵對應(yīng)的值數(shù)據(jù)。 （4） Scan （start_key， end_key）:范圍查詢操作，按用戶定義的順序關(guān)系（一般為字典序）讀取鍵在區(qū)間[start_key， end_key]內(nèi)的所有鍵值對。 可以看出鍵值存儲系統(tǒng)支持的存取操作非常簡單，不同鍵值對間不存在訪問依賴，于是，每個鍵值對都可以獨立地存儲在任意存儲節(jié)點上，因此隨著數(shù)據(jù)規(guī)模的增大，系統(tǒng)容易進行橫向擴展。 1.3系統(tǒng)架構(gòu)及關(guān)鍵問題 鍵值存儲系統(tǒng)中常見的數(shù)據(jù)結(jié)構(gòu)有哈希表和日志結(jié)構(gòu)合并樹（LSM-tree）。其中，基于哈希表的系統(tǒng)支持對鍵值對的快速點查詢，但是難以進行高效范圍查詢，并且內(nèi)存開銷很高。正是由于這些特性，哈希表主要應(yīng)用在數(shù)據(jù)庫索引與緩存系統(tǒng)中。基于日志結(jié)構(gòu)合并樹將隨機寫入轉(zhuǎn)化為順序?qū)懭耄軌虺浞掷迷O(shè)備的帶寬，具有高效的寫入性能，因此在大規(guī)模持久化鍵值存儲中廣泛應(yīng)用。本篇介紹的鍵值存儲技術(shù)與系統(tǒng)都是基于日志結(jié)構(gòu)合并樹的鍵值存儲系統(tǒng)。 1.3.1 常見數(shù)據(jù)結(jié)構(gòu) 1.哈希表的結(jié)構(gòu) 圖1.1展示了一個簡單的哈希表，它是一種可以將鍵數(shù)據(jù)映射到值數(shù)據(jù)的結(jié)構(gòu)。哈希表在進行映射的過程中，以鍵數(shù)據(jù)作為輸入，使用哈希函數(shù)將其計算為哈希碼，以此作為表中位置的索引。常見的哈希算法有除留余數(shù)、隨機數(shù)法、平方取中法等。 圖1.1 哈希表的結(jié)構(gòu) 理想情況下，哈希函數(shù)會為每個鍵數(shù)據(jù)生成唯一的哈希碼作為索引，但大多數(shù)哈希表設(shè)計并不能達到完美哈希的程度，無法避免哈希沖突的發(fā)生，即多個鍵數(shù)據(jù)產(chǎn)生了相同的哈希值。為了應(yīng)對這些沖突，有以下幾種常見的方法：①開放地址法，當(dāng)發(fā)生地址沖突時，按照某種方法繼續(xù)探測哈希表中的其他存儲單元，直到找到空位置；②鏈地址法，產(chǎn)生哈希沖突后在存儲數(shù)據(jù)后面加一個鏈表，管理發(fā)生沖突的數(shù)據(jù)；③公共溢出區(qū)法，建立一個特殊存儲空間，專門存放沖突的數(shù)據(jù)。若通過這些方法仍然無法解決哈希沖突，則需要對哈希表進行擴容。 基于哈希表的索引具有以下特點：①點查詢速度快，通過鍵數(shù)據(jù)就能直接計算值數(shù)據(jù)的存儲地址，查詢效率極高；②存在空間浪費，隨著哈希空間利用率的
書友推薦
- >
羅庸西南聯(lián)大授課錄
- >
我從未如此眷戀人間
- >
大紅狗在馬戲團-大紅狗克里弗-助人
- >
上帝之肋:男人的真實旅程
- >
中國歷史的瞬間
- >
龍榆生：詞曲概論/大家小書
- >
伯納黛特,你要去哪(2021新版)
- >
我與地壇
本類暢銷
