文件

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

• Log Files：

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

• sorted tables

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

• Mainifest

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

• Current

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

• Info logs

數(shù)據(jù)信息會打印在LOG和LOG.old文件中

• Others

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

Level 0

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

• Compactions

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

• Timing

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

• Number of files

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

[Leveldb] 實現(xiàn)文檔翻譯