文件

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

• Log Files：

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

• sorted tables

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

• Mainifest

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

• Current

CURRENT是一個(gè)簡(jiǎn)單的文本文件包含最新的一個(gè)MANIFEST文件的名字

• Info logs

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

• Others

其他文件用來(lái)生成其他的用處，比如LOCK，*.dbtmp等等

Level 0

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

• Compactions

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

• Timing

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

• Number of files

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

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