從最基本層面看，數(shù)據(jù)庫只需做兩件事：

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

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

為何關(guān)注數(shù)據(jù)庫內(nèi)部的存儲和檢索呢？你不可能從頭開始實現(xiàn)存儲引擎，往往需要從眾多現(xiàn)有的存儲引擎中選擇適合業(yè)務(wù)的存儲引擎。為針對特定工作負載而對數(shù)據(jù)庫調(diào)優(yōu)時，就得對存儲引擎底層機制有所了解。

針對事務(wù)型工作負載、分析型負載的存儲引擎優(yōu)化存在很大差異。

事務(wù)處理與分析處理”和“面向列的存儲”部分，分析型優(yōu)化的存儲引擎。

先討論存儲引擎，用于大家比較熟悉的兩種數(shù)據(jù)庫，傳統(tǒng)關(guān)系數(shù)據(jù)庫和NoSQL數(shù)據(jù)庫。研究兩個存儲引擎家族 ，即日志結(jié)構(gòu)的存儲引擎和面向頁的存儲引擎，比如B-tree。

數(shù)據(jù)庫核心：數(shù)據(jù)結(jié)構(gòu)

最簡單的數(shù)據(jù)庫，由兩個Bash函數(shù)實現(xiàn)：

#!/bin/bash

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

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

這兩個函數(shù)實現(xiàn)一個K.V存儲。當(dāng)調(diào)用 db_set key value，它將在數(shù)據(jù)保存你所輸入的key value key value幾乎可以是任何內(nèi)容。例如值可以是JSON文檔。然后調(diào)用db_get key，它會查找與輸入key相關(guān)聯(lián)的最新值并返回。

例如：

$ 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文件，忽略轉(zhuǎn)義問題）。每次調(diào)用db_set，即追加新內(nèi)容到文件末尾，因此，若多次更新某K，舊版本值不會被覆蓋，而需查看文件中最后一次出現(xiàn)的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函數(shù)性能很好。類似db_set，許多數(shù)據(jù)庫內(nèi)部都使用日志（log），日志是個僅支持追加式更新的數(shù)據(jù)文件。雖然真正的數(shù)據(jù)庫有很多更復(fù)雜問題要考慮（如并發(fā)控制、回收磁盤空間以控制日志文件大小、處理錯誤和部分完成寫記錄等），但基本原理相同 。

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

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

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

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

存儲系統(tǒng)中重要的trade off

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

哈希索引

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

KV存儲與大多數(shù)編程語言所內(nèi)置的字典結(jié)構(gòu)類似，一般采用hash map或hash table實現(xiàn)。既然已有內(nèi)存數(shù)據(jù)結(jié)構(gòu)的hash map ，為何不用它們在磁盤上直接索引數(shù)據(jù)？

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

圖1

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

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

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

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

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

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

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

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

由于壓縮經(jīng)常會使段更?。僭O(shè)K在一個段內(nèi)被平均重寫多次），也能在執(zhí)行壓縮時將個段合并：

圖3：同時執(zhí)行段壓縮和多段的合并

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

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

實現(xiàn)難點

(1) 文件格式

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

(2) 刪除記錄

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

(3) 崩潰恢復(fù)

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

(4) 部分寫入記錄

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

(5) 并發(fā)控制

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

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

追加寫設(shè)計的優(yōu)勢

• 追加和分段合并是順序?qū)?，一般比隨機寫快得多，尤其是在旋轉(zhuǎn)式磁盤。某種程度上，順序?qū)懺诨陂W存的 固態(tài)硬盤（SSD） 也很合適
• 若段文件是追加的或不可變的，則并發(fā)和崩潰恢復(fù)就簡單得多。如不必擔(dān)心在重寫值時發(fā)生崩潰的情況，導(dǎo)致留下一個包含部分舊值和部分新值混雜的文件
• 合并舊段能避免數(shù)據(jù)文件隨時間推移，數(shù)據(jù)文件出現(xiàn)碎片化問題

哈希索引的劣勢

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