資料存儲與檢索(資料密集型應用系統設計)
如果你把東西整理得井井有條, 下次就不用查找了
--- 德國諺語
從最基本的層面看, 資料庫隻需要做兩件事情
- 向它插入資料時, 它就儲存資料
- 查詢資料時, 它應該傳回需要的資料
資料庫核心: 資料結構
世界上最簡單的資料庫
#!/bin/bash
db_set() {
echo "$1,$2" >> database
}
db_get() {
grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}
這兩個函數實作了一個 key-value 存儲
$ db_set 123456 '{"name":"Jack"}'
$ db_set 78 '{"name":"Amy"}'
$ db_get 42
{"name":"Amy"}
它的實作非常簡單, 使用
database
這個純文字檔案存儲資料, 每次調用
db_set
就會追加新内容到檔案末尾, 如果多次更新某個
key
, 舊版本值不會被覆寫, 而是需要檢視檔案中最後一次出現的
key
來找到最新的值(
tail -n 1
)
思考
由于是追加方式寫入, 所有 db_set 函數性能很好, 裡面借用了很多資料庫都使用的日志
log
思想(這裡的 log 并非程式運作日志), 另一方面 日志 儲存了大量的記錄, 那麼 db_get 函數性能非常差, 需要從頭掃描到尾部來查找 key 出現的最後位置(On 複雜度)
解決
為了高效的查找資料庫中特定的鍵值對, 需要新的資料結構: 索引, 基本思想是保留一些額外的中繼資料, 幫助定位想要的資料. 同時, 維護索引勢必會引入開銷, 主要在資料寫入時, 每次寫入資料時, 需要更新索引, 是以任何類型的索引通常都會降低寫的速度
這裡涉及到存儲系統中重要的權衡設計: 适當的索引可以加速讀取, 但每個索引都會減慢寫速度, 是以資料庫通常不會對所有内容添加索引, 需要開發和資料庫管理者手動選擇索引, 避免不必要的開銷
哈希索引
大多數程式設計語言内置的字典結構(hash map)非常适合存儲 key-value, 例如
$ db_set 張三 [email protected]
這樣會将張三的郵箱儲存到
database
檔案中, 同時在記憶體中建立一個哈希表 emails, db_set 寫入時, 記錄檔案的偏移量 emails["張三"] = 0, 當多次調用
db_set 張三 [email protected]
是, 更新 哈希表中的偏移量即可 emails["張三"] = 645, 那麼對于每次調用 db_get 來說, 性能是相同的, 每次先到哈希表中查找到偏移量, 從偏移量開始地方讀取, 遇到結束符号(本例子中是 逗号)結束即可傳回結果.
事實上, Bitcask (Riak 的預設存儲引擎) 就是采用的這種做法
思考
如上所述, 隻追加到一個檔案, 如何避免用盡磁盤空間
- 日志分段: 檔案到達一定大小, 資料寫入新的檔案
- 壓縮: 在日志中丢棄重複的鍵, 隻保留最新的 key-value
- 往往兩者結合使用
以前的段在寫入後不會再進行修改, 是以合并壓縮可以在背景程序進行, 合并後的段會寫入一個新的檔案, 而且程式運作時, 舊的段依然可以正常讀取, 合并完成後, 讀取請求會切換到新的段上, 舊的段檔案可以安全删除
細節
- 檔案格式
- 文本形式存儲不是最佳格式, 二進制格式更快更簡單, 以位元組記錄長度, 之後跟上原始字元串(都不需要轉義)
- 删除記錄
- 删除不是立即删除, 而是做一個删除标記(墓碑), 當背景線程合并日志段時, 發現墓碑标記則丢棄這個鍵的所有值
- 崩潰恢複
- 如果資料庫重新開機, 記憶體中的 hashmap 會丢失, 可以從頭到尾周遊所有段檔案, 重建 hashmap, 但是可能會重建很長時間, Bitcask 通過将每個段的 hashmap 快照存儲在磁盤上, 可以更快的恢複
- 部分寫入
- 追加到日志的過程中如果發生崩潰, 可以設定檔案校驗值來發現損壞部分并丢棄
- 并發控制
- 由于日志寫入需要有嚴格的先後順序, 通常隻會有一個寫線程, 讀取可以有多個線程
- 為什麼采用追加寫 . 而不是覆寫寫
- 順序寫比随機寫快很多
- 并發控制和崩潰恢複實作起來簡單, 防止覆寫寫時候發生崩潰資料丢失
- 長時間運作不會出現碎片化問題
- 缺點
- 不支援區間查詢
- 資料大時, 哈希表占用大量記憶體空間, 也會更容易發生哈希沖突
SSLTables 和 LSM-Tree
假設檔案儲存的 key-value 按 key 排序, 稱這種格式為 排序字元串表 SSTable, 它要求每個鍵在每個合并的段檔案中隻能出現一次(合并段線程已經確定了)
SSTable 對比 哈希索引
優點:
- 合并段更加簡單高效: 并發讀取多個輸入段檔案, 比較每個檔案的第一個鍵, 把最小的鍵拷貝到輸出檔案, 重複這個過程, 會産生一個新的按鍵排序的合并段檔案. 如果相同的鍵出現在多個輸入段檔案中, 保留最新段的值
- 在檔案中查找特定的鍵時, 不再需要記憶體中的hashmap, 假設查找 abc 的 value, 且不知道hashmap 沒有記錄 abc 具體的偏移量, 隻記錄了偏移量 aba = 100 位元組 和 abd = 150 位元組 , 那麼可以直接跳到檔案 100 位元組開始掃描, 在150 位元組掃描終止, 雖然仍然需要 hashmap 記錄某些鍵的便宜, 但它是可以稀疏的, 并不需要每個鍵都記錄, 這樣可以很快在記憶體存放很多 key 的偏移量, 将 key 的快照儲存在磁盤中, 也節省了空間和 io 次數
以上描述的算法本質上是 LevelDB 和 RocksDB 所使用的, 以合并日志樹LSM-Tree 命名
在海量資料中 , LSM-Tree 查找某個不存在的 key 時候可能很慢(先檢查記憶體表, 然後加載磁盤上的段檔案, 在區間内尋找). 為了優化這種通路, 通常會使用布隆過濾器
LSM 的方式可以有效的執行區間查詢, 并且磁盤是順序寫入的, 可以支援非常高的寫入吞吐量
B-trees
雖然上面讨論的日志結構索引正在逐漸接受認可, 但使用最廣泛的是 B-tree
像 SSTable 一樣, B-tree 保留按鍵排序的特征, 這樣可以實作高效的 key-value 查詢和區間查詢, B-tree 将資料庫分解成固定大小的塊或者頁, 一般為 4KB, 頁是資料庫内部讀寫的最小單元, 這種設計更接近底層硬體, 因為磁盤也是按固定大小的排列
每個頁可以使用位址進行辨別, 這樣可以讓一個頁引用另一個頁. 類似指針, 不過指向的是磁盤位址.
例如:
某一頁為 B-tree 的根, 每當查找 key 時, 總是從根開始, 頁面包含若幹個 key 和子頁的位址, 每個子頁都負責一個連續範圍内的 key
假設查找 251, 是以從根上可以知道沿着 200 ~ 300 頁之間的子頁上查找, 找到第三層 250 ~ 270 之間, 然後來到第四層, 從開頭周遊到 251, 擷取到對應的 val
如果遇到更新操作, 首先搜尋包含該 key 子頁, 然後更改對應 key 的 val, 并将這一頁寫回到磁盤, 因為其他頁式引用的位址而不是拷貝, 是以寫會磁盤後, 對其他引用到這個頁的子頁也是生效的
如果遇到新增操作, 需要找到包含新的 key 的子頁, 并将其添加到該頁, 如果這個頁沒有空間容納新鍵, 則将其分裂為兩個半滿的頁, 并且父頁也需要更新
具有 n 個鍵的 B-tree 總是具有 O(logn) 的深度, 大多數資料庫适合 3~4 層的 B-tree, 是以不需要周遊非常深即可找到所需的頁, 每層為 500 的 4KB 頁的四級樹可以存儲 256TB
思考
如果插入時候發生頁分裂, 那麼需要寫入磁盤兩個分裂的頁, 假如資料庫完成部分頁的寫入之後發生崩潰, 會導緻索引被破壞(存在一個孤兒頁, 沒有任何其他頁指向它), 為了能在崩潰中恢複, 會采用預寫日志(write-ahead log, WAL), 也叫重做日志, 這是一個僅支援追加修改的檔案, 每個 B-tree 必須先更新 WAL 然後再修改樹本身的頁, 當資料庫崩潰需要恢複時, 改日志用于将 B-tree 恢複到最近一緻狀态
索引中存的是什麼
- 可以實際行, 也可以是對其他地方存儲的行的引用,如果是行的引用, 那麼行具體所在的位置為堆檔案. 堆檔案方法比較常見, 當存在多個二級索引時, 可以避免複制資料, 每個索引隻引用堆檔案的位置, 實際堆檔案儲存在另一個位置, 當更新值而不是添加新鍵時, 這個方法非常高效
- 某些情況下, 從索引查找到堆檔案對應的行, 然後跳轉過去讀取意味着太多的性能損失, 希望将這一行資料直接儲存在索引中, 稱為聚集索引, 例如 Mysql InnoDB, 表的主鍵始終是聚集索引, 二級索引引用主鍵而不是堆檔案