文件

leveldb是根據單機版BigTable來實現的，但是文件的組織方式卻有以下幾點不同。
每一個數據庫是由存儲在文件夾下面的一系列文件集合來實現的，有很多不同類型的文件：

• Log Files：

log文件(*.log) 存儲了一系列最近的更新。每一個更新都會追加到當前的log文件中。當一個log文件到達一個預設閾值(默認是4MB)，它將會轉變成一個有序表，并且為以后的更新操作生成一個新的log文件。

• sorted tables

一個 sorted tables （*.sst） 存儲一系列有序的key。每一個entry是一個key的value或者一個刪除的key。
sorted tables 由多級的方式組成。sorted table 由一個特殊的更新的層級生成（也叫做level-0）。當更新的文件超過某一閾值（通常是4個），所有更新的文件會一起與level-1層的文件進行合并產生一個新的leve-1文件（我們為每2M的數據建立一個level-1層的文件）
更新層的文件可能會包含重復的key，然而在其他層級的文件有著有序不相同的key。加入第L層，L>=1。當在L層文件的大小超過10^L MB 時，一個在L層的文件以及所有在L+1層的文件會形成一個新的文件集合。這些合并操作會逐漸的從level-0到最后一層。

• Mainifest

一個MANIFEST文件列出了所有sorted tables的集合，key的序列，一起他重要的元數據。一個新的MANIFEST文件，會在一個數據庫重新打開時生成。這個MANIFEST文件以一個log文件的格式，服務的一些更新信息會追加到這個log文件中。

• Current

CURRENT是一個簡單的文本文件包含最新的一個MANIFEST文件的名字

• Info logs

數據信息會打印在LOG和LOG.old文件中

• Others

其他文件用來生成其他的用處，比如LOCK，*.dbtmp等等

Level 0

當一個log文件增長到超過閾值時（默認為1MB）：
建立一個新的內存表和log文件用于寫入以后的更新
在后臺：
將之前內存表中的內存寫到一個sstable中
丟掉這個內存表
刪除舊的log文件和舊的內存表
向level-0層中增加新的sstable

• Compactions

當L層的大小超過它的界限，我們在后臺的進程中對它進行壓縮。壓縮操作從L層和所有L+1層之間選擇一個文件。注意如果一個L層的文件只與一個L+1層的文件重疊，全部的L+1層的文件被用來做壓縮的輸出文件并且壓縮后將會被刪除。一方面：因為level-0的特殊性，我們特殊對待從level-0到level-1的壓縮：一個level-0的壓縮可能會選擇超過一個level-0文件因為這些文件會與其他文件有重疊。
一個壓縮會合并選擇的文件的內存來生成一個L+1文件序列。我們會生成一個新的L+1層的文件在當前輸出文件達到文件的大小（2MB）。我們也會生成一個新的輸出文件當這些key超過是個L+2文件。最后的規則保證了后續的L+1層文件的壓縮不會從L+2層選擇過多的數據
老文件會被刪除，新文件會被添加到服務的狀態中。
一個典型的壓縮會通過key空間進行旋轉，更多的細節是，對于沒一個L層我們記住最后一個key。下一個L層的壓縮會從這個key開始選擇第一個文件。
合并會丟棄掉重復的值。我們也會丟棄標記刪除的key，如果編號更高的層數中包含覆蓋當前key的文件。

• Timing

Level-0 壓縮會根據從level0中取的四個1MB的文件，并且最壞情況所有的level-1（10M）。。。我們將會讀14MB寫14MB。
除了level0的特殊壓縮，我們會從L層選擇一個2MB的文件。在最壞情況，這個會與其他L+1中的12個文件重疊。壓縮過程會讀26MB，寫26MB。假設一個磁盤的IO速度為100MB最壞情況的壓縮會花費0.5秒
如果我們限制后臺寫的速度，假如100MB的10%,一個壓縮過程會花費5秒。如果用戶以10MB的速度寫，我們可能會建立很多level-0文件。這樣在每次合并的過程中花費會上升。
Solution 1： 減少這類問題，當level-0的文件數量足夠大時我們可能會增加log文件轉換的閾值。閾值下降的趨勢越大，內存表需要的內存就越大。
Solution 2： 當level0文件數量上升的時候認為降低寫的速率
Solution 3：降低大量合并操作的花費。大部分level-0的文件不進行壓縮，而我們只在合并時考慮O(N)復雜度的算法。

• Number of files

不是只生成2MB的文件，而是對于更大的層級我們可以生成更大的文件以減少文件總數，盡管這樣會增加合并的花費。我們可以在多個文件夾中共享文件集合。

[Leveldb] 實現文檔翻譯