大規模存儲系統數據消冗

近年來，雲計算、物聯網、區塊鏈和邊緣計算等多種新型應用產生了海量的、有價值的數據，而且呈現出持續增長的趨勢。如何有效地存儲和管理如此龐大數據是現代工業界和學術界共同關注的重點和難點問題。

本書系統地介紹了數據消冗技術，該技術能夠通過有效地檢測和排除數據中的冗餘部分，達到減輕存儲系統的負擔和降低成本的目標，從而應對海量數據增長帶來的挑戰。本書結合作者近十餘年在與存儲系統領域相關的國際學術會議和期刊上發表的前沿成果，一方面對單個數據消冗技術問題進行深入的理論剖析，另一方面針對多種常見應用場景的數據消冗需求提供豐富的系統級解決方案和技術思路。

第 1 章緒論 1

1．1 數據增長與數據消冗 1

1．2 大規模存儲系統冗餘負載分析 2

1．3 數據消冗技術的應用與挑戰 4

1．4 本章小結 6

參考文獻 6

第 2 章從傳統壓縮到大規模數據消冗 10

2．1 傳統壓縮技術 10

2．2 數據去重技術 13

2．3 差量壓縮技術 16

2．4 本章小結 19

參考文獻 19

第3 章數據消冗前沿技術概述 23

3．1 數據分塊 23

3．2 計算加速 28

3．3 指紋索引 29

3．4 數據恢復 32

3．5 垃圾回收 33

3．6 安全性 36

3．7 可靠性 38

3．8 差量壓縮 39

3．9 開源社區實踐 41

3．10 本章小結 43

參考文獻 43

第4 章極速基於內容分塊算法 53

4．1 技術背景 53

4．1．1 FSC 算法 54

4．1．2 CDC 算法 55

4．2 典型的CDC 算法 56

4．2．1 基於拉賓指紋的CDC 算法 56

4．2．2 非對稱極值CDC 算法 57

4．3 FastCDC 算法的技術框架 59

4．3．1 基於齒輪哈希的CDC 算法 59

4．3．2 分塊判斷優化 61

4．3．3 收斂分塊策略 62

4．3．4 循環展開優化 65

4．4 性能分析 66

4．4．1 實驗設置 66

4．4．2 分塊判斷優化評估 67

4．4．3 收斂分塊策略評估 69

4．4．4 綜合評估 70

4．5 本章小結 73

參考文獻 73

第5 章流水線化和並行化數據去重技術 75

5．1 數據去重技術面臨的計算挑戰 75

5．1．1 數據去重技術的計算瓶頸與研究背景 75

5．1．2 數據去重流程的獨立性與依賴性 78

5．2 流水線化和並行化數據去重技術的設計與實現 79

5．2．1 設計原理 80

5．2．2 主要功能模塊 81

5．2．3 數據去重子任務的流水線化 82

5．2．4 指紋計算的並行化 83

5．2．5 分塊的並行化 84

5．2．6 並行化過程中的同步和異步問題 87

5．3 性能分析 88

5．3．1 實驗設置 88

5．3．2 關鍵參數測試 89

5．3．3 整體性能測試 93

5．3．4 其他CDC 算法的適配性測試 94

5．4 本章小結 95

參考文獻 96

第6 章高效的數據去重指紋索引技術 99

6．1 數據去重指紋索引的規模與挑戰 99

6．2 基於局部性的數據去重指紋索引策略相關研究 100

6．2．1 備份數據流的局部性 100

6．2．2 典型相關係統介紹 100

6．3 基於相似性的數據去重指紋索引策略相關研究 103

6．3．1 備份數據流的相似性 103

6．3．2 典型相關係統介紹 104

6．4 基於局部性和相似性的數據去重指紋索引策略設計與實現 106

6．4．1 小文件與大文件的去重策略問題 106

6．4．2 局部性與相似性的互補設計 108

6．4．3 基於互補設計的指紋索引技術原理與理論剖析 109

6．4．4 基於互補設計的指紋索引技術設計與實現 110

6．5 性能分析 117

6．5．1 測試環境 117

6．5．2 相似性與局部性測試分析 118

6．5．3 與其他數據去重指紋索引算法性能比較 121

6．6 本章小結 125

參考文獻 125

第7 章面向相似去重的快速差量壓縮技術 128

7．1 相似數據差量壓縮的技術背景 128

7．2 快速差量壓縮技術的設計原理 130

7．3 受數據去重啓發的快速差量壓縮技術 131

7．3．1 主要設計思路與模塊介紹 131

7．3．2 Gear-CDC 算法 134

7．3．3 基於重複數據相鄰區域的貪心檢測算法 135

7．3．4 差量編碼與解碼操作 135

7．3．5 差量編碼的總體流程 136

7．4 性能分析 137

7．4．1 測試環境 137

7．4．2 Gear-CDC 算法性能測試 138

7．4．3 應用案例一測試：數據去重後的相似數據差量壓縮 142

7．4．4 應用案例二測試：文件更新後的差量壓縮 146

7．5 本章小結 147

參考文獻 148

第8 章基於數據去重感知的相似數據檢測和差量壓縮技術 150

8．1 相似數據消冗技術概述 150

8．1．1 相似數據消冗技術的原理與發展趨勢 150

8．1．2 基於超級特徵值的相似數據檢測技術分析 152

8．1．3 基於數據去重感知的相似數據檢測技術的提出 153

8．2 基於數據去重感知的相似數據檢測和差量壓縮技術的設計與實現 154

8．2．1 設計原理與結構 154

8．2．2 基於數據去重感知的相似數據檢測 156

8．2．3 基於超級特徵值的相似數據檢測 157

8．2．4 差量壓縮與存儲管理 158

8．2．5 整體流程 159

8．3 性能分析 160

8．3．1 測試環境 160

8．3．2 基於超級特徵值的相似數據檢測的驗證學習 161

8．3．3 基於數據去重感知的相似數據檢測和差量壓縮性能 165

8．3．4 可擴展性測試 167

8．3．5 恢復性能測試 169

8．4 本章小結 170

參考文獻 171

第9 章受數據去重啓發的輕量級差量同步技術 174

9．1 差量同步與數據去重技術 174

9．1．1 差量同步與數據去重技術簡介 174

9．1．2 本章的主要內容 183

9．2 基於內容分塊的差量同步算法 184

9．2．1 CDC 算法回顧與選擇 184

9．2．2 用CDC 算法代替FSC 算法 189

9．2．3 CDC 算法中的弱指紋複用策略 190

9．2．4 改進CDC 算法後的差量同步算法簡述 195

9．3 面向差量同步的協議優化 196

9．3．1 強弱指紋比較過程分離 196

9．3．2 合併連續相同數據塊 198

9．3．3 關於元數據規模 200

9．3．4 最終版本 203

9．4 性能分析 204

9．4．1 測試環境 205

9．4．2 整體性能測試 206

9．4．3 三種代表性差量同步技術對比 208

9．4．4 高帶寬大文件場景下的性能對比 212

9．5 本章小結 212

參考文獻 213

第 10 章面向人工智能模型的差量壓縮技術 217

10．1 人工智能模型壓縮技術現狀 217

10．1．1 基於輕量化設計的模型壓縮 218

10．1．2 基於剪枝技術的模型壓縮 221

10．1．3 基於量化技術的模型壓縮 223

10．2 基於局部敏感性的網絡浮點參數量化壓縮技術 225

10．2．1 網絡浮點參數壓縮的難點 225

10．2．2 神經網絡浮點參數的分佈 226

10．2．3 局部敏感量化方案設計 228

10．2．4 量化壓縮後模型的版本相似性 230

10．3 利用版本間相似性的神經網絡差量壓縮方案 233

10．3．1 現有神經網絡差量壓縮方案的不足與改進思路 233

10．3．2 基於量化的神經網絡差量壓縮方案 234

10．3．3 基於誤差反饋的神經網絡量化訓練更新算法 235

10．3．4 神經網絡的量化及差量壓縮方案 237

10．3．5 壓縮時間複雜度分析 241

10．4 資源受限場景應用分析 241

10．4．1 場景一：減少人工智能模型快照的存儲開銷 242

10．4．2 場景二：減少人工智能模型傳輸的通信開銷 242

10．5 性能分析 245

10．5．1 測試環境、數據集與對比方法 245

10．5．2 網絡浮點參數量化比特數的選擇 245

10．5．3 壓縮後網絡模型精度測試 247

10．5．4 網絡模型壓縮性能測試 249

10．6 本章小結 253

參考文獻 254

第 11 章面向時序數據庫的有損壓縮技術 260

11．1 時序數據特性和有損浮點數壓縮編碼器 260

11．1．1 數據庫浮點數壓縮現狀 260

11．1．2 有損浮點數壓縮算法簡介 261

11．1．3 時序數據庫場景簡介 262

11．1．4 有損浮點數壓縮算法在時序數據庫中的應用 262

11．2 典型的有損浮點數壓縮算法 263

11．3 在線化設計與實現 268

11．3．1 特殊值編碼器在線化方案 268

11．3．2 哈夫曼編碼器在線化方案 270

11．3．3 無損編碼器在線化方案 271

11．3．4 自適應算術編碼方案 272

11．3．5 對比測試 277

11．4 預測器的改進 280

11．4．1 預測器方案介紹 280

11．4．2 對比測試 282

11．5 數據庫中的性能測試 283

11．5．1 測試環境與方案 284

11．5．2 測試結果 285

11．6 本章小結 287

參考文獻 287

第 12 章面向非易失性內存場景的數據消冗技術 290

12．1 NVM 文件系統與數據消冗技術 290

12．1．1 NVM 的發展及其結構與特性 291

12．1．2 NVM 文件系統研究現狀 292

12．1．3 面向NVM 的數據消冗技術研究現狀 295

12．1．4 本章的主要內容 300

12．2 NVM 文件系統在數據消冗方面的性能與一致性挑戰 300

12．2．1 面向NVM 的高吞吐率數據消冗技術難點分析 301

12．2．2 面向NVM 的數據消冗一致性技術難點分析 304

12．3 支持數據消冗的NVM 文件系統設計與實現 306

12．3．1 輕量級的數據消冗框架設計 306

12．3．2 高效的冗餘檢測優化策略 307

12．3．3 NVM 友好的去重元數據管理 309

12．3．4 高性能的NVM 去重索引構建 310

12．3．5 輕量級一致性的設計與恢復 312

12．4 性能分析 316

12．4．1 測試環境 316

12．4．2 整體測試 317

12．4．3 高吞吐率設計的有效性測試 324

12．4．4 一致性設計的有效性測試 327

12．4．5 恢復時間測試 329

12．4．6 交織模式的影響 330

12．5 本章小結 332

參考文獻 333

第 13 章面向圖像存儲的細粒度數據去重技術 336

13．1 圖像去重的研究現狀 336

13．2 圖像去重的特性與挑戰 337

13．2．1 圖像場景的特性 338

13．2．2 圖像去重的挑戰 339

13．3 細粒度圖像去重框架 341

13．4 基於特徵位圖的相似性檢測器 342

13．4．1 相似性檢測器的框架 342

13．4．2 生成二維特徵 343

13．4．3 基於特徵位圖的指紋算法 345

13．4．4 基於特徵位圖的相似性檢測器的優點 348

13．5 與圖像編碼兼容的差量壓縮器 349

13．5．1 差量壓縮器的框架 349

13．5．2 差量壓縮器的細節 350

13．5．3 針對連續重複塊的優化 352

13．5．4 與圖像編碼兼容的差量壓縮器的優點 353

13．6 性能分析 353

13．6．1 系統原型的實現和具體配置 354

13．6．2 測試環境與數據集介紹 354

13．6．3 關鍵性能測試指標 355

13．6．4 針對相似性檢測器的測試 355

13．6．5 針對差量壓縮器的測試 360

13．6．6 與粗粒度圖像去重技術對比 361

13．7 本章小結 362

參考文獻 363

第 14 章總結與展望 365

14．1 面向存儲系統的通用數據消冗技術 365

14．2 針對特定場景的專用數據消冗技術 367

附錄主要術語表 369

夏文

哈爾濱工業大學（深圳）副教授、博士生導師，研究方向為存儲系統、數據消冗等，在FAST、USENIX ATC、IEEE TC 等會議和期刊發表論文70餘篇，30 項專利獲授權。主持國家級、省市級科研項目十餘項；曾獲教育部自然科學獎一等獎等獎項；研究成果被Ceph、Zstd 等多個開源項目採納。

馮丹

華中科技大學計算機科學與技術學院教授、博士生導師、院長，信息存儲系統教育部重點實驗室主任，數據存儲系統與技術教育部工程研究中心主任，國家傑出青年科學基金獲得者。主要從事計算機體系結構、大數據存儲系統等方面的研究。研究成果獲多項國際、國家級和省部級獎項。

華宇

華中科技大學教授，研究方向為高性能存儲系統與體系結構等。部分研究成果發表在OSDI、ASPLOS、MICRO、FAST、HPCA 等國際會議上。擔任ACM APSys 2019、ICDCS 2021等國際會議程序共同主席、副主席。研究成果獲教育部自然科學獎一等獎、湖北省科技進步獎一等獎等。

鄒翔宇

哈爾濱工業大學（深圳）博士研究生，研究領域包括數據消冗、有損壓縮等。在FAST、USENIX ATC、TPDS、TOS 等會議和期刊上發表論文十餘篇。論文曾入選“阿里雲- 中國計算機學會存儲專委會優秀論文”，兩次獲哈爾濱工業大學計算學部學生優秀論文獎，獲博士研究生國家獎學金。 ^[1]