從最基本層面看，數據庫只需做兩件事：

• 向它插入數據肘，它就保存數據
• 之后查詢時，返回那些數據

本文討論如何存儲輸入的數據，并在收到查詢請求時，如何重新找到數據。

為何關注數據庫內部的存儲和檢索呢？你不可能從頭開始實現存儲引擎，往往需要從眾多現有的存儲引擎中選擇適合業務的存儲引擎。為針對特定工作負載而對數據庫調優時，就得對存儲引擎底層機制有所了解。

針對事務型工作負載、分析型負載的存儲引擎優化存在很大差異。

事務處理與分析處理”和“面向列的存儲”部分，分析型優化的存儲引擎。

先討論存儲引擎，用于大家比較熟悉的兩種數據庫，傳統關系數據庫和NoSQL數據庫。研究兩個存儲引擎家族 ，即日志結構的存儲引擎和面向頁的存儲引擎，比如B-tree。

數據庫核心：數據結構

最簡單的數據庫，由兩個Bash函數實現：

#!/bin/bash

db_set() { 
    echo "$1,$2" >> database
}

db_get() {
    grep "^$1," database | sed -e "s／^$1,//" tail -n 1
}

這兩個函數實現一個K.V存儲。當調用 db_set key value，它將在數據保存你所輸入的key value key value幾乎可以是任何內容。例如值可以是JSON文檔。然后調用db_get key，它會查找與輸入key相關聯的最新值并返回。

例如：

$ db_set 123456 '{"name":"London", "attractions":["Big Ben","London Eye"]}'

$ db_set 42 '{"name":"San Francisco","attractions":["Golden Gate Bridge"]}'

$ db_get 42 {"name":"San Francisco", "attractions":["Golden Gate Bridge"]}

它底層的存儲格式其實非常簡單：一個純文本文件。其中每行包含一個K.V，用逗號分隔（大致像一個csv文件，忽略轉義問題）。每次調用db_set，即追加新內容到文件末尾，因此，若多次更新某K，舊版本值不會被覆蓋，而需查看文件中最后一次出現的K來找到最新V（因此在db_get中使用tail -n 1）。

$ db_set 42 '{"name":"San Francisco", "attractions":["Exploratorium"]}'

$ db_get 42 {"name":"San Francisco", "attractions":["Exploratorium"]}

$ cat database
123456,{"name":"London","attractions":["Big Ben","London Eye"]} 42, {"name":"San Francisco","attractions":["Golden Gate Bridge"]}
42,{"name":"San Francisco","attractions":["Exploratorium"]}

簡單情況，追加到文件尾部方式通常夠高效了，因而db_set函數性能很好。類似db_set，許多數據庫內部都使用日志（log），日志是個僅支持追加式更新的數據文件。雖然真正的數據庫有很多更復雜問題要考慮（如并發控制、回收磁盤空間以控制日志文件大小、處理錯誤和部分完成寫記錄等），但基本原理相同 。

日志這個詞通常指應用程序的運行輸出日志，來記錄發生了什么事情 。日志則是個更通用的含義，表示一個僅能追加的記錄序列集合。它可能是人類不可讀的，可能是二進制格式而只能被其他程序來讀取。

另一方面，若日志文件保存大量記錄，則db_get性能會很差。每次想查找一個K，db_get 必須從頭到尾掃描整個數據庫文件來查找K的出現位置。在算法術語中，查找開銷是O（n） ，即若數據庫記錄條數加倍，則查找需要兩倍時間。這一點并不好。

為高效查找數據庫中特定K的V，需要數據結構：索引。它們背后基本想法都是保留一些額外元數據，這些元數據作為路標，幫助定位想要數據。若希望用幾種不同方式搜索相同數據，在數據的不同部分，可能要定義多種不同的索引。

索引是基于原始數據派生而來的額外數據結構。很多數據庫允許單獨添加、刪除索引，而不影響數據庫內容，它只會影響查詢性能。維護額外結構勢必會引入開銷，特別是在新數據寫入時。對于寫人，它很難超過簡單追加文件方式的性能，因為那已經是最簡單的寫操作。由于每次寫數據時，需更新索引，所以任何類型索引基本都會降低寫速度。

存儲系統中重要的trade off

合適的索引能加速查詢，但每個索引都會降低寫速度。默認情況下，數據庫通常不會對所有內容索引 ，它需要SE或DBA基于對應用程序典型查詢模式的了解，手動決定索引。就是為應用提供最有利加速同時，避免引入過多不必要的開銷。

哈希索引

以KV數據的索引開始。KV類型并非唯一能索引的數據，但隨處可見，而且是其他更復雜索引的基礎。

KV存儲與大多數編程語言所內置的字典結構類似，一般采用hash map或hash table實現。既然已有內存數據結構的hash map ，為何不用它們在磁盤上直接索引數據？

假設數據存儲全部采用追加式文件組成，最簡單的索引策略：保存內存中的hash map，將每個K一一映射到數據文件中特定的字節偏移量，這就能找到每個值的位置：

圖1

每當在文件中追加新的KV對時，還要更新hashma來反映剛寫入的數據的偏移量（包括插入新K與更新已有K）。當查找一個值時，使用hashmap找到文件中的偏移量，即存儲位置，然后讀取其內容。

聽著簡單，但的確可行。Bitcask（Riak默認的存儲引擎）就是這么做的。Bitcask提供高性能讀寫，但所有K必須能放入內存。而V則可以使用比可用內存更多的空間，只需一次磁盤尋址，就能將V從磁盤加載到內存，若那部分數據文件已在文件系統的緩存中，則讀取根本不需要任何磁盤I/O。

Bitcask這種存儲引擎適合每個K的V經常更新場景。如：

• K，視頻的URL
• V，播放次數（每次有人點擊播放按鈕時遞增）

在這種工作負載下，有大量寫操作，但沒有太多不同的K，即每個K都有大量寫操作，但將所有K保存在內存中還是可行的。

至此，只追加寫到一個文件，那如何避免最終用完磁盤空間？可將日志分為特定大小的段，當日志文件達到一定大小時就關閉，并開始寫到一個新的段文件中。然后，就能壓縮這些段：

圖2：壓縮KV 更新日志文件，僅保留每個K的最新值

壓縮意味著在日志中丟棄重復K，只保留每個K的最近更新。

由于壓縮經常會使段更小（假設K在一個段內被平均重寫多次），也能在執行壓縮時將個段合并：

圖3：同時執行段壓縮和多段的合并

由于段在寫入后不會再被修改，所以合并的段會被寫入一個新文件。對這些凍結段的合并和壓縮過程可在后臺線程完成，而在運行時，仍能繼續使用舊的段文件繼續正常的讀寫請求。合并過程完成后，將讀請求切換到新的合并段上，舊的段文件就能安全刪除了。

每個段現在都有自己的內存哈希表，將K映射到文件的偏移量。為找到鍵的值，先檢查最新的段的 hashmap；若K不存在，則檢查第二最新的段，依此類推。因為合并過程可維持較少的段數量，因此查找一般無需檢查太多hashmap。

實現難點

(1) 文件格式

CSV不是日志最佳格式，二進制格式更快，更簡單。首先以字節為單位，記錄字符串的長度，然后跟上原始的字符串（無需轉義）。

(2) 刪除記錄

若要刪除一個K及其V，則必須在數據文件中中追加一個特殊的刪除記錄（有時稱為邏輯刪除）。合并日志段時，一旦發現邏輯刪除標記，就會丟棄這個已刪除鍵的所有值。

(3) 崩潰恢復

若數據庫重啟，則內存的hashmap將丟失。原則上，可通過從頭到尾讀取整個段文件，記錄每個鍵的最新值的偏移量，來恢復每個段的hashmap。但若段文件很大，這可能耗時久，這將使服務器重啟很慢。Bitcask通過存儲加速恢復磁盤上每個段的哈希映射的快照，可以更快地加載到內存中。

(4) 部分寫入記錄

數據庫可能隨時崩潰，包括將記錄追加到日志的過程中。Bitcask文件包含校驗值，這樣就能發現損壞部分并丟棄。

(5) 并發控制

由于寫是以嚴格的先后順序追加到日志，所以常見實現是只有一個寫線程。數據文件段是追加的且不可變，所以它們能被多線程同時讀取。

追加的日志看起來很浪費：為何不更新文件，用新值覆蓋舊值？

追加寫設計的優勢

• 追加和分段合并是順序寫，一般比隨機寫快得多，尤其是在旋轉式磁盤。某種程度上，順序寫在基于閃存的 固態硬盤（SSD） 也很合適
• 若段文件是追加的或不可變的，則并發和崩潰恢復就簡單得多。如不必擔心在重寫值時發生崩潰的情況，導致留下一個包含部分舊值和部分新值混雜的文件
• 合并舊段能避免數據文件隨時間推移，數據文件出現碎片化問題

哈希索引的劣勢

• 散列表必須能放進內存若你有很多鍵，那真是倒霉。原則上，可在磁盤上維護一個hashmap，但磁盤上的hashmap很難表現優秀，需大量隨機訪問I/O，當hash變滿時，繼續增長代價昂貴，并且哈希沖突需要復雜處理邏輯
• 范圍查詢效率不高如無法輕松掃描kitty00000到kitty99999之間的所有K，只能采用逐個查找的方式查詢每個K