掃一掃
關注中圖網
官方微博
本類五星書更多>
-
>
全國計算機等級考試最新真考題庫模擬考場及詳解·二級MSOffice高級應用
-
>
決戰行測5000題(言語理解與表達)
-
>
軟件性能測試.分析與調優實踐之路
-
>
第一行代碼Android
-
>
JAVA持續交付
-
>
EXCEL最強教科書(完全版)(全彩印刷)
-
>
深度學習
大數據存儲--鍵值容錯與一致性 版權信息
- ISBN：9787030730626
- 條形碼：9787030730626 ; 978-7-03-073062-6
- 裝幀：一般膠版紙
- 冊數：暫無
- 重量：暫無
- 所屬分類：>
大數據存儲--鍵值容錯與一致性 內容簡介
本書分為三篇，分別涉及大數據處理中的鍵值存儲、容錯存儲、數據一致性三個領域。每篇首先簡要介紹相關領域的基礎知識、系統優化的關鍵技術以及主流的系統等，然后介紹作者在相關領域的部分研究成果。具體來說，在鍵值存儲方面，介紹了動態布隆過濾器設計、哈希分組與鍵值分離技術相結合的存儲結構設計、哈希索引與日志結構合并樹相結合的索引結構設計等方面的優化方法，旨在降低讀、寫放大，提升讀、寫與范圍查詢的性能；在容錯存儲方面，介紹了糾刪碼的數據布局、故障數據恢復算法、源數據節點與恢復節點選擇以及系統擴容等方面的優化方法，旨在降低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
前言
第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
展開全部
大數據存儲--鍵值容錯與一致性 節選
第1篇 鍵值存儲系統 第1章 鍵值存儲 本章主要圍繞當前大數據的存儲需求，概要介紹鍵值存儲系統的主流架構、讀寫流程、研究熱點。本章主要內容安排如下：首先介紹當前大數據的特征以及對存儲系統帶來的新挑戰，鍵值存儲的數據模型與訪問接口；然后介紹當前主流的鍵值存儲系統架構，并分析存在的問題與系統設計方面的挑戰；*后概述該領域的國際研宄現狀與熱點。 1.1 大數據特征及存儲挑戰 1.1.1 數據存儲的發展趨勢 隨著網絡與通信技術的飛速發展以及網絡終端接入的普及，博客、即時通信、短視頻分享等新型服務平臺不斷涌現，獲取網絡服務的用戶越來越多。根據 WeAreSocial與Hootsuite公司聯合發布的Digital 2020[11的統計，截至2020年1月，全球互聯網用戶數量已超過45億人，其中社交媒體用戶高達38億人。同時，醫療、交通、金融等行業也紛紛開始利用大數據處理技術進行數據分析等工作。因此產生了大量的數據存儲需求，并呈現出以下特征。 （1）數據規模大且快速增長。由于Web 2.0技術倡導由用戶主導生產數據內容，用戶在享用網絡應用帶來便利的同時，也積極向互聯網上傳了大量的數據。同時，傳統行業在數字化發展過程中，也產生了大量的數據存儲需求。例如，醫療衛生領域利用大數據技術，對居民的海量醫療及健康數據進行統計分析[2]。根據國際數據公司IDC的統計，到2025年全球每年產生的數據總量將從2018年的33ZB 增長到175ZB [3]。 （2）存取速度要求高。網絡服務平臺對數據的存取速度也提出了更高的要求。以社交網絡為例，知名社交網站Facebook每天都會新增數十億條內容，對數據的訪問也達到了每秒鐘幾億次[4]。為了使用戶獲得良好的體驗，這些頻繁的數據存取請求需要得到系統的快速響應。 （3）非結構化數據占主導。非結構化數據指不方便使用二維邏輯表示的數據，如長文本、圖片、音頻、視頻等。網絡應用以及傳統行業利用大數據技術產生的數據大多是非結構化數據，如用戶在社交網絡發布的博文和短視頻，醫療領域的健康檔案和CT圖像等。根據IDC公司的統計，網絡和醫療數據中約80%都是非結構化數據[5，6]。 綜上所述，基于當前的發展趨勢，數據存儲領域面臨著以非結構化數據占主導的海量數據存儲需求，網絡服務商需要為這些數據提供高效的存取支持，對數據存儲系統設計與實現提出了新的挑戰。 1.1.2 數據存儲面臨的挑戰 面對數據的新特征，特別是非結構化數據的高速發展，需要設計針對非結構化數據友好的存儲系統，提高非結構數據的存取性能以及系統的擴展能力，以滿足用戶日益提升的數據存儲需求和處理需求。要實現這個目標，面臨著以下幾個問題。 1.可擴展性問題 當數據存儲系統的數據規模與訪問量持續增加，系統性能無法繼續滿足用戶數據存儲需求時，就需要對存儲系統進行擴展。數據存儲系統的擴展方式分為橫向擴展與縱向擴展兩類，橫向擴展指的是利用分布式技術增加更多的存儲節點，與當前節點組成一個更大的存儲系統；縱向擴展指的是提高當前存儲節點的硬件性能，如升級內外存設備和CPU等。 當數據存儲和訪問量顯著增大時，為了增強存儲節點的負載能力，不得不為其配置核數更多、頻率更高的CPU和容量更大、讀寫性能更強的存儲設備。然而，計算機硬件的性能提升與其價格增長并非線性關系，為單臺服務器提高配置會帶來昂貴的硬件成本，性價比很低。另外，受制于計算機硬件發展水平，縱向擴展能力也存在一定的上限。 相比于縱向擴展，存儲系統可以通過增加存儲節點的方式實現橫向擴展，通過添加相對廉價的服務器，便能在理論上對系統的性能和存儲容量進行無限擴展，性價比高。但是，橫向擴展會帶來系統管理上的挑戰。 2.非結構化數據處理問題 對非結構化數據的處理也是數據存儲面臨的挑戰之一。在關系型數據庫中，數據遵守嚴格的數據庫存儲范式，在添加數據前需要預定義數據格式，難以靈活修改，因此無法快速容納新的數據類型，也無法高效處理難以用二維邏輯表示的數據。由于非結構化數據的格式缺少明顯規律，組成形式靈活，若使用關系型數據庫存儲，當應用為數據添加新的屬性時，需要修改整張關系表的模式，有時甚至需要將原關系表中的所有數據遷移到新表中，顯著影響整個系統的服務性能，同時還會大幅增加運維難度。 綜上所述，傳統的關系型數據庫不能適應海量非結構化數據的存取需求，在數據存儲領域的當前發展趨勢下，需要探索新型的數據存儲結構。 1.2 鍵值數據模型及訪存接口 為了應對海量非結構化數據存儲的挑戰，非關系型數據存儲系統開始得到廣泛關注和使用[7]，這些系統一般具有以下特征[8]。 （1）不要求強一致性的事務支持，有較強的靈活性。 （2）對數據存儲格式約束較少，容易處理各種類型的數據。 （3）訪問接口簡單易用，減少了對網絡應用中不常用復雜查詢的支持。 這些特征使得非關系型數據存儲系統能夠處理非結構化數據，擁有高效的數據存取性能。其靈活的數據模型能很好地適應非結構化數據多變的數據特征，同時由于數據之間沒有嚴格的約束關系，也沒有強一致性要求，容易橫向擴展，擴大系統規模。 鍵值（key value）存儲系統就是一個典型的非關系型數據存儲系統，其采用扁平化的數據模型和簡單靈活的訪問接口，具有很好的泛用性，同時還保證了高讀寫性能與易擴展能力，為海量非結構化數據的存儲提供了一個優秀的解決方案。因此，鍵值存儲系統作為后端存儲引擎被廣泛部署在如分布式文件系統[9]、電子商務系統社交網絡等數據密集型應用中，成為數據存儲領域的重要組成部分。此外，一些關系型數據庫也開始使用鍵值存儲系統為其提供底層存儲支持[12]。所以，研究優化鍵值存儲系統的性能，對數據存儲領域的發展有重要意義。 鍵值存儲系統的數據模型類似于哈希表（Hash table），—個鍵數據（key）對應一個值數據（value），將鍵數據和其對應的值數據合稱為鍵值對（key-value pair）。鍵數據由字符串表示，值數據可以是任意類型，系統內部并不關心值數據具體表示的數據類型，只是將值數據視作二進制串處理，因此非常適合存儲類型多變的非結構化數據。基于這種扁平化數據模型，鍵值存儲系統支持以下接口，用于存取數據。 （1） Put （key， value）:寫操作，將鍵值對（key， value）寫入系統，寫入新數據和更新已有數據均使用相同的接口。 （2） Delete （key）:刪除操作，從系統中刪除鍵對應的鍵值對。 （3） Get （key）:點查詢操作，讀取鍵對應的值數據。 （4） Scan （start_key， end_key）:范圍查詢操作，按用戶定義的順序關系（一般為字典序）讀取鍵在區間[start_key， end_key]內的所有鍵值對。 可以看出鍵值存儲系統支持的存取操作非常簡單，不同鍵值對間不存在訪問依賴，于是，每個鍵值對都可以獨立地存儲在任意存儲節點上，因此隨著數據規模的增大，系統容易進行橫向擴展。 1.3系統架構及關鍵問題 鍵值存儲系統中常見的數據結構有哈希表和日志結構合并樹（LSM-tree）。其中，基于哈希表的系統支持對鍵值對的快速點查詢，但是難以進行高效范圍查詢，并且內存開銷很高。正是由于這些特性，哈希表主要應用在數據庫索引與緩存系統中。基于日志結構合并樹將隨機寫入轉化為順序寫入，能夠充分利用設備的帶寬，具有高效的寫入性能，因此在大規模持久化鍵值存儲中廣泛應用。本篇介紹的鍵值存儲技術與系統都是基于日志結構合并樹的鍵值存儲系統。 1.3.1 常見數據結構 1.哈希表的結構 圖1.1展示了一個簡單的哈希表，它是一種可以將鍵數據映射到值數據的結構。哈希表在進行映射的過程中，以鍵數據作為輸入，使用哈希函數將其計算為哈希碼，以此作為表中位置的索引。常見的哈希算法有除留余數、隨機數法、平方取中法等。 圖1.1 哈希表的結構 理想情況下，哈希函數會為每個鍵數據生成唯一的哈希碼作為索引，但大多數哈希表設計并不能達到完美哈希的程度，無法避免哈希沖突的發生，即多個鍵數據產生了相同的哈希值。為了應對這些沖突，有以下幾種常見的方法：①開放地址法，當發生地址沖突時，按照某種方法繼續探測哈希表中的其他存儲單元，直到找到空位置；②鏈地址法，產生哈希沖突后在存儲數據后面加一個鏈表，管理發生沖突的數據；③公共溢出區法，建立一個特殊存儲空間，專門存放沖突的數據。若通過這些方法仍然無法解決哈希沖突，則需要對哈希表進行擴容。 基于哈希表的索引具有以下特點：①點查詢速度快，通過鍵數據就能直接計算值數據的存儲地址，查詢效率極高；②存在空間浪費，隨著哈希空間利用率的
書友推薦
- >
自卑與超越
- >
推拿
- >
羅曼·羅蘭讀書隨筆-精裝
- >
隨園食單
- >
小考拉的故事-套裝共3冊
- >
上帝之肋:男人的真實旅程
- >
伯納黛特,你要去哪(2021新版)
- >
李白與唐代文化
本類暢銷
