數據庫系統內幕 Database Internals A Deep Dive Into How Distributed Data Systems Work

Alex Petrov 黃鵬程,傅宇,張晨譯

  • 出版商: 機械工業
  • 出版日期: 2020-06-01
  • 售價: $714
  • 貴賓價: 9.5$678
  • 語言: 簡體中文
  • 頁數: 296
  • 裝訂: 平裝
  • ISBN: 7111655168
  • ISBN-13: 9787111655169
  • 此書翻譯自: Database Internals

立即出貨

買這商品的人也買了...

商品描述

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

目錄大綱

前言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二分搜索
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 lti-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故障場景2
14.5拜占庭共識266
14.5.1 PBFT算法266
14.5.2恢復和檢查點268
14.6本章小結269
第二部分總結272
參考文獻275