資料庫系統內幕

《資料庫系統內幕》從資料庫開發者角度，對現代資料庫技術進行了全景式解讀，由機械工業出版社出版。

基本介紹

• 中文名：資料庫系統內幕
• 作者：亞歷克斯·彼得羅夫（Alex Petrov）
• 譯者：黃鵬程+傅宇+張晨
• 出版社：機械工業出版社
• 出版時間：2020年6月1日
• 頁數：300 頁
• 定價：119 元
• 開本：16 開
• 裝幀：平裝
• ISBN：9787111655169

內容簡介

本書旨在指導開發者理解現代資料庫和存儲引擎背後的內部概念，包含從眾多書籍、論文、部落格和多個開源資料庫原始碼中精心選取的相關材料。本書深入介紹了數據存儲、數據構建塊、分散式系統和數據集群，並且指出了現代資料庫之間最重要的區別在於決定存儲結構和數據分布的子系統。本書分為兩部分：第一部分討論節點本地的進程，並關注資料庫系統的核心組件——存儲引擎，以及最重要的一個特有元素；第二部分探討如何將多個節點組織到一個資料庫集群中。本書主要面向資料庫開發人員，以及使用資料庫系統構建軟體的人員，如軟體開發人員、運維工程師、架構師和工程技術經理。

圖書目錄

前言 1

第一部分 存儲引擎

第1章 簡介與概述 13

1.1 資料庫架構 14

1.2 記憶體資料庫與磁碟資料庫 16

1.3 面向列與面向行的資料庫 17

1.3.1 面向行的數據布局 18

1.3.2 面向列的數據布局 19

1.3.3 區別與最佳化 20

1.3.4 寬列式存儲 20

1.4 數據檔案和索引檔案 21

1.4.1 數據檔案 22

1.4.2 索引檔案 23

1.4.3 間接的主索引 24

1.5 緩衝、不可變性和有序性 25

1.6 本章小結 26

第2章 B樹基礎知識 28

2.1 二分搜尋樹 28

2.1.1 樹的平衡 29

2.1.2 基於磁碟存儲的樹 31

2.2 基於磁碟的結構 32

2.2.1 機械硬碟 32

2.2.2 固態硬碟 32

2.2.3 磁碟存儲結構 34

2.3 無處不在的B樹 35

2.3.1 B樹的層次結構 36

2.3.2 分隔鍵 38

2.3.3 B樹查找複雜度 39

2.3.4 B樹查找算法 39

2.3.5 鍵的數目 40

2.3.6 B樹的節點分裂 40

2.3.7 B樹的節點合併 42

2.4 本章小結 43

第3章 檔案格式 45

3.1 動機 45

3.2 二進制編碼 46

3.2.1 原始類型 46

3.2.2 字元串和變長數據 48

3.2.3 按位打包的數據：布爾值、枚舉值和標誌 48

3.3 通用原理 49

3.4 頁的結構 51

3.5 分槽頁 51

3.6 單元格布局 53

3.7 將單元格放進分槽頁 54

3.8 管理變長數據 55

3.9 版本 56

3.10 校驗和 57

3.11 本章小結 58

第4章 B樹的實現 59

4.1 頁頭 59

4.1.1 魔數 59

4.1.2 同級指針 60

4.1.3 最右指針 60

4.1.4 節點的高鍵 61

4.1.5 溢出頁 62

4.2 二分搜尋 64

4.3 傳播分裂與合併 65

4.4 再平衡 67

4.5 僅在右側追加 68

4.6 壓縮 69

4.7 清掃與維護 70

4.7.1 更新和刪除導致的碎片 70

4.7.2 頁的碎片整理 71

4.8 本章小結 72

第5章 事務處理與恢復 74

5.1 緩衝區管理 75

5.1.1 快取語義 77

5.1.2 快取回收 77

5.1.3 在快取中鎖定頁 78

5.1.4 頁置換 79

5.2 恢復 82

5.2.1 日誌語義 83

5.2.2 操作日誌與數據日誌 84

5.2.3 steal和force策略 84

5.2.4 ARIES 85

5.3 並發控制 86

5.3.1 可串列化 86

5.3.2 事務隔離 87

5.3.3 讀異常和寫異常 88

5.3.4 隔離級別 88

5.3.5 樂觀並發控制 90

5.3.6 多版本並發控制 91

5.3.7 悲觀並發控制 91

5.3.8 基於鎖的並發控制 91

5.4 本章小結 98

第6章 B樹的變體 101

6.1 寫時複製 101

6.2 抽象節點更新 103

6.3 惰性B樹 103

6.3.1 WiredTiger 104

6.3.2 惰性自適應樹 105

6.4 FD樹 106

6.4.1 分段級聯 106

6.4.2 對數級的有序段 108

6.5 Bw樹 108

6.5.1 更新鏈 109

6.5.2 用CAS控制並發 109

6.5.3 結構修改操作 110

6.5.4 合併和垃圾收集 111

6.6 快取無關B樹 112

6.7 本章小結 114

第7章 日誌結構存儲 116

7.1 LSM樹 117

7.1.1 LSM樹的結構 118

7.1.2 更新與刪除 122

7.1.3 LSM樹的查找 123

7.1.4 合併疊代 124

7.1.5 協調 126

7.1.6 LSM樹的維護 126

7.2 讀寫放大與空間放大 129

7.3 實現細節 130

7.3.1 有序字元串表 130

7.3.2 布隆過濾器 132

7.3.3 跳表 133

7.3.4 磁碟訪問 135

7.3.5 壓縮 136

7.4 無序LSM存儲 136

7.4.1 Bitcask 137

7.4.2 WiscKey 138

7.5 LSM樹中的並發 139

7.6 日誌堆疊 140

7.6.1 快閃記憶體轉換層 141

7.6.2 檔案系統日誌記錄 142

7.7 LLAMA與精心堆疊 144

7.8 本章小結 145

第一部分總結 147

第二部分 分散式系統

第8章 簡介與概述 151

8.1 並發執行 151

8.2 分散式計算的誤區 153

8.2.1 處理 154

8.2.2 時鐘和時間 155

8.2.3 狀態一致性 156

8.2.4 本地和遠程執行 157

8.2.5 處理故障的需要 157

8.2.6 網路分區和部分故障 157

8.2.7 級聯故障 158

8.3 分散式系統抽象 160

8.4 兩將軍問題 165

8.5 FLP不可能定理 166

8.6 系統同步性 167

8.7 故障模型 167

8.7.1 崩潰故障 168

8.7.2 遺漏故障 168

8.7.3 任意故障 169

8.7.4 故障處理 169

8.8 本章小結 169

第9章 故障檢測 171

9.1 心跳和ping 172

9.1.1 無逾時的故障檢測器 173

9.1.2 外包心跳 174

9.2 phi增量故障檢測器 175

9.3 Gossip和故障檢測 175

9.4 反向故障檢測 176

9.5 本章小結 177

第10章 領導者選舉 179

10.1 霸道選舉算法 180

10.2 依次故障轉移 181

10.3 候選節點/普通節點最佳化 182

10.4 邀請算法 183

10.5 環算法 184

10.6 本章小結 185

第11章 複製和一致性 187

11.1 實現可用性 188

11.2 臭名昭著的CAP理論 188

11.2.1 小心使用CAP 189

11.2.2 收成與產量 190

11.3 共享記憶體 191

11.4 順序 192

11.5 一致性模型 193

11.5.1 嚴格一致性 194

11.5.2 可線性化 194

11.5.3 順序一致性 198

11.5.4 因果一致性 199

11.6 會話模型 202

11.7 最終一致性 204

11.8 可調一致性 204

11.9 見證者副本 206

11.10 強最終一致性和CRDT 207

11.11 本章小結 209

第12章 反熵和傳播 212

12.1 讀修復 213

12.2 摘要讀 214

12.3 提示移交 215

12.4 Merkle樹 215

12.5 點陣圖版本向量 216

12.6 Gossip傳播 218

12.6.1 Gossip技術細節 219

12.6.2 覆蓋網路 219

12.6.3 混合Gossip 220

12.6.4 局部視圖 221

12.7 本章小結 222

第13章 分散式事務 224

13.1 多個操作的原子性 225

13.2 兩階段提交 226

13.2.1 2PC中的參與者故障 227

13.2.2 2PC中的協調者故障 228

13.3 三階段提交 229

13.4 Calvin分散式事務 231

13.5 Spanner分散式事務 233

13.6 資料庫分區 235

13.7 Percolator分散式事務 236

13.8 協調避免 238

13.9 本章小結 240

第14章 共識 243

14.1 廣播 244

14.2 原子廣播 245

14.2.1 虛同步 245

14.2.2 Zookeeper原子廣播 246

14.3 Paxos 248

14.3.1 Paxos算法 249

14.3.2 Paxos的Quorum 250

14.3.3 故障場景 251

14.3.4 Multi-Paxos 253

14.3.5 快速Paxos 254

14.3.6 平等Paxos 255

14.3.7 柔性Paxos 257

14.3.8 共識的推廣解法 259

14.4 Raft 261

14.4.1 Raft中的領導者角色 263

14.4.2 故障場景 264

14.5 拜占庭共識 266

14.5.1 PBFT算法 266

14.5.2 恢復和檢查點 268

14.6 本章小結 269

第二部分總結 272

參考文獻 275

作者簡介

作者簡介

Alex Petrov是一位數據基礎架構工程師，資料庫和存儲系統的狂熱愛好者，Apache Cassandra 提交者和PMC成員，精通存儲、分散式系統和算法。

譯者簡介

黃鵬程 畢業於北京郵電大學，過去八年一直專注於資料庫和大數據平台研發與架構工作。畢業後就職於中國民生銀行，歷任軟體工程師及大數據基礎架構團隊負責人，目前為阿里雲高級產品專家，負責阿里雲資料庫相關產品的設計與規劃工作。你可以通過搜尋“gnuhpc”在LinkedIn或者微信上找到他。

傅宇 畢業於南京大學計算機系，專注於資料庫技術，現任阿里雲技術專家，擔任 PolarDB-X 分散式關係型資料庫核心研發工作，在分散式事務、查詢最佳化器、執行器等方向略有經驗，對資料庫和大數據領域充滿熱情。個人部落格：https://ericfu.me，知乎賬號 Eric Fu，歡迎與我交流！

張晨 畢業於上海交通大學。大數據、資料庫、分散式系統和函式式編程愛好者。現於Indeed東京擔任軟體工程師一職。你可以通過 我的個人主頁chasezhang.me了解更多信息。