???? 作者： Jeff?Dean,?Sanjay?Ghemawat

原文： http://leveldb.googlecode.com/svn/trunk/doc/index.html

譯者： phylips@bmy?2011-8-16

譯文： http://duanple.blog.163.com/blog/static/70971767201171705113636/

LevelDB 庫提供了一種永久性的 key?value 存儲。 Key 和 value 都是任意的字節(jié)序列。在這個 key?value 存儲系統(tǒng)中， key 按照用戶聲明的比較函數(shù)有序排列。

打開一個數(shù)據(jù)庫

一個 LevelDB 數(shù)據(jù)庫有一個文件系統(tǒng)目錄名稱與之關聯(lián)。該數(shù)據(jù)庫的所有內(nèi)容都存儲在該目錄下。下面的例子展示了如何打開一個數(shù)據(jù)庫，或者如何在必要的時候創(chuàng)建一個：

#include?<assert>

#include?"leveldb/db.h"

leveldb::DB*?db;

leveldb::Options?options;

options.create_if_missing?=?true;

leveldb::Status?status?=?leveldb::DB::Open(options,?"/tmp/testdb",?&db);

assert(status.ok());

...

如果你想在數(shù)據(jù)庫已經(jīng)存在的情況下，讓上面的代碼產(chǎn)生一個錯誤，需要再 Open 調(diào)用之前加入如下一行：

options.error_if_exists?=?true;

狀態(tài) (status)

你可能注意到了上面的 leveldb::Status 數(shù)據(jù)類型。在 LevelDB 中絕大多數(shù)可能出錯的函數(shù)調(diào)用都會返回這種類型的值。也可以在出錯的情況下，打印出一些錯誤提示信息

???leveldb::Status?s?=?...;

???if?(!s.ok())?cerr?<<?s.ToString()?<<?endl;

關閉數(shù)據(jù)庫

在完成一個數(shù)據(jù)庫的處理之后，直接刪除該數(shù)據(jù)庫對象即可。

...?open?the?db?as?described?above?...

??...?do?something?with?db?...

??delete?db;

讀操作與寫操作

數(shù)據(jù)庫提供了 Put,?Delete,? 和? Get 方法來對數(shù)據(jù)庫進行修改 / 查詢。比如下面的代碼會將存儲在 key1 下面的值存到 key2 下面。

??std::string?value;

??leveldb::Status?s?=?db->Get(leveldb::ReadOptions(),?key1,?&value);

??if?(s.ok())?s?=?db->Put(leveldb::WriteOptions(),?key2,?value);

??if?(s.ok())?s?=?db->Delete(leveldb::WriteOptions(),?key1);

原子性更新

需要注意的是。在上面的操作中，如果在 Put?key2 之后， delete?key1 之前，進程死掉了，那么相同的 value 值就可能會存儲在多個 key 值下面。可以通過使用 WriteBatch 類原子性的執(zhí)行一組更新操作，來避免這樣的問題：

??#include?"leveldb/write_batch.h"

??...

??std::string?value;

??leveldb::Status?s?=?db->Get(leveldb::ReadOptions(),?key1,?&value);

??if?(s.ok())?{

????leveldb::WriteBatch?batch;

????batch.Delete(key1);

????batch.Put(key2,?value);

????s?=?db->Write(leveldb::WriteOptions(),?&batch);

??}

WriteBatch

會持有對數(shù)據(jù)庫的一系列更改操作，這些操作會按照它們加入順序被執(zhí)行。除了提供這種原子性的保證外， WriteBatch 還可以通過將多個更新放到同一個 batch 里，在存在大量更新操作時，加速它們的執(zhí)行。

同步性的寫操作

默認情況下，對于 leveldb 的寫操作是異步的：在將寫操作從進程交給操作系統(tǒng)之后它就會返回。從操作系統(tǒng)內(nèi)存空間到底層永久性存儲設備之間的傳輸是異步進行的。可以通過打開 sync?flag 來，使得一個寫操作要等到數(shù)據(jù)真正的寫入到永久性存儲后才返回。 ( 在 Posix 系統(tǒng)中，這是通過在寫操作返回之前調(diào)用 fsync(...)? 或者? fdatasync(...)? 或者是? msync(...,?MS_SYNC)) 來實現(xiàn)的 )

??leveldb::WriteOptions?write_options;

??write_options.sync?=?true;

??db->Put(write_options,?...);

異步性的寫操作通常要比同步性的快 1000 倍。它的缺點是，當機器 crash 掉的時候，可能會丟失最后的一些更新。需要注意的是，如果僅僅是寫操作進程的 crash( 比如，不是 reboot) 并不會引起任何的丟失，因為即使 sync=false ，一個更新操作在完成之前必須要把數(shù)據(jù)從應用程序空間傳到系統(tǒng)空間。

異步性的寫操作通常都可以安全的使用。比如，在將大量數(shù)據(jù)加載到數(shù)據(jù)庫中時，你可以通過在 crash 之后重新加載一遍來處理那些丟失的更新。也可以采用一種混合模式，比如每隔 N 個寫操作，進行一次同步，這樣在 crash 發(fā)生時，只需要從最后一次同步的地方開始重新執(zhí)行即可 ( 只需要讓同步性的寫操作更新一個重啟時從何處開始的標記即可 ) 。

WriteBatch 也可以為異步性的寫操作的提供一個改進。多個更新操作可以放到同一個 WriteBatch ，然后使用一個同步性的寫操作 ( 比如令 write_options.sync=true) 。這樣額外的同步開銷就可以分攤到多個寫操作中。

并發(fā)

同一時刻只能有一個進程打開數(shù)據(jù)庫。為了防止誤用， LevelDB 實現(xiàn)會從操作系統(tǒng)申請一把鎖。在一個進程內(nèi)部，同一個 leveldb::DB 對象可以安全地被多個并發(fā)線程共享。比如，多個線程可以在同一個數(shù)據(jù)庫中寫數(shù)據(jù)，獲取迭代器，執(zhí)行 Get 調(diào)用而不需要額外的同步 (LevelDB 實現(xiàn)會自動的完成所需的同步 ) 。然而其他對象 ( 比如迭代器和 WriteBatch) 可能需要額外的同步。如果兩個線程共享相同的此類對象，它們必須使用自己的鎖機制來保護對此類對象的訪問。

迭代

下面的例子用來說明如何打印出數(shù)據(jù)庫中的所有 key?value 對。

??leveldb::Iterator*?it?=?db->NewIterator(leveldb::ReadOptions());

??for?(it->SeekToFirst();?it->Valid();?it->Next())?{

????cout?<<?it->key().ToString()?<<?":?"??<<?it->value().ToString()?<<?endl;

??}

??assert(it->status().ok());?

//?Check?for?any?errors?found?during?the?scan

??delete?it;

下面的例子說明如何只處理那些給定 key 值邊界 [start,limit) 內(nèi)的數(shù)據(jù) :

??for?(it->Seek(start);

???????it->Valid()?&&?it->key().ToString()?<?limit;

???????it->Next())?{

????...

??}

也可以以逆序方式進行處理? ( 可能比順序處理慢些 )

??for?(it->SeekToLast();?it->Valid();?it->Prev())?{

????...

??}

Snapshots

Snapshots 提供了關于整個 key-value 存儲狀態(tài)的一致性的只讀視圖。可以通過設置 ReadOptions::snapshot 為非空值，來指定從數(shù)據(jù)庫的某個特殊的版本中讀取。如果它的值為空，則默認讀取當前狀態(tài)。 Snapshots 通常通過 DB::GetSnapshot() 方法創(chuàng)建：

??leveldb::ReadOptions?options;

??options.snapshot?=?db->GetSnapshot();

??...?apply?some?updates?to?db?...

??leveldb::Iterator*?iter?=?db->NewIterator(options);

??...?read?using?iter?to?view?the?state?when?the?snapshot?was?created?...

??delete?iter;

??db->ReleaseSnapshot(options.snapshot);

需要注意，在一個 snapshot 不再需要的時候，必須通過 DB::ReleaseSnapshot 接口來顯示的進行釋放 。這樣就可以讓底層實現(xiàn)丟棄掉那些為支持對該 snapshot 的讀取操作所維護的一些狀態(tài)數(shù)據(jù)。一個寫操作也可以返回一個應用了一系列特殊的更新操作集合后的數(shù)據(jù)庫狀態(tài)的 snapshot:

??leveldb::Snapshot*?snapshot;

??leveldb::WriteOptions?write_options;

??write_options.post_write_snapshot?=?&snapshot;

??leveldb::Status?status?=?db->Write(write_options,?...);

??...?perform?other?mutations?to?db?...

??leveldb::ReadOptions?read_options;

??read_options.snapshot?=?snapshot;

??leveldb::Iterator*?iter?=?db->NewIterator(read_options);

??...?read?as?of?the?state?just?after?the?Write?call?returned?...

??delete?iter;

??db->ReleaseSnapshot(snapshot);

Slice

上面 it->key() 和? it->value() 調(diào)用的返回值都是 leveldb::Slice 類型。 Slice 是一個包含了長度及指向外部字節(jié)數(shù)組的指針的簡單結(jié)構。返回 Slice 比返回一個 std::string 類型開銷要低，因為這種我們就不必對那些大的 key 和 value 值進行拷貝。另外， LevelDB 方法也不能返回以 null 結(jié)尾的 C 風格字符串，因為它的 key 和 value 都允許包含 '\0' 。

C++?string 和以 null 結(jié)尾的 C 風格字符串可以簡單的轉(zhuǎn)化為一個 Slice 類型：

???leveldb::Slice?s1?=?"hello";

???std::string?str("world");

???leveldb::Slice?s2?=?str;

一個 Slice 類型也可以簡單的轉(zhuǎn)化為一個 C++?string 類型：

???std::string?str?=?s1.ToString();

???assert(str?==?std::string("hello"));

在使用 Slices 需要格外小心，因為它依賴于調(diào)用者去保證 Slice 所指向的外部字節(jié)數(shù)組的有效性 。比如下面代碼的就是有問題的：

???leveldb::Slice?slice;

???if?(...)?{

?????std::string?str?=?...;

?????slice?=?str;

???}

???Use(slice);

因為 if 語句的作用域已經(jīng)結(jié)束， str 將會被析構，這樣 slice 指向的空間就不存在了。

比較器

前面的那些例子為 key 使用了默認的排序函數(shù)，會按字典序進行排序。你可以在打開數(shù)據(jù)庫的時候提供一個自定義的比較器。比如假設數(shù)據(jù)庫的 key 是由兩個數(shù)組成，我們首先按照第一個數(shù)進行排序，如果相等再比較第二個。首先需要定義一個滿足如下規(guī)則的 leveldb::Comparator 的子類：

??class?TwoPartComparator?:?public?leveldb::Comparator?{

???public:

????//?Three-way?comparison?function:

????//???if?a?<?b:?negative?result

????//???if?a?>?b:?positive?result

????//???else:?zero?result

????int?Compare(const?leveldb::Slice&?a,?const?leveldb::Slice&?b)?const?{

??????int?a1,?a2,?b1,?b2;

??????ParseKey(a,?&a1,?&a2);

??????ParseKey(b,?&b1,?&b2);

??????if?(a1?<?b1)?return?-1;

??????if?(a1?>?b1)?return?+1;

??????if?(a2?<?b2)?return?-1;

??????if?(a2?>?b2)?return?+1;

??????return?0;

????}

????//?Ignore?the?following?methods?for?now:

????const?char*?Name()?const?{?return?"TwoPartComparator";?}

????void?FindShortestSeparator(std::string*,?const?leveldb::Slice&)?const?{?}

????void?FindShortSuccessor(std::string*)?const?{?}

??};

現(xiàn)在使用定制的比較器，創(chuàng)建一個數(shù)據(jù)庫 :

??TwoPartComparator?cmp;

??leveldb::DB*?db;

??leveldb::Options?options;

??options.create_if_missing?=?true;

??options.comparator?=?&cmp;

??leveldb::Status?status?=?leveldb::DB::Open(options,?"/tmp/testdb",?&db);

向后兼容 (Backwards?compatibility)

比較器的 Name 方法的返回結(jié)果會在數(shù)據(jù)庫創(chuàng)建時與之綁定，同時在后面每次打開數(shù)據(jù)庫時都會進行檢查。如果返回名稱發(fā)生了變化，那么 leveldb::DB::Open 調(diào)用會失敗。因此，當且僅當新的 key 格式及比較函數(shù)與現(xiàn)有數(shù)據(jù)庫不兼容的時候才需要去改變它，同時此時丟棄掉所有現(xiàn)存數(shù)據(jù)庫的內(nèi)容也應是可以接受的。

你也可以有計劃的逐步改變 key 的格式。比如，可以在每個 key 的后面存儲一個版本號 ( 對于大多數(shù)的情況一個字節(jié)就足夠了 ) 。當切換到一種新的 key 格式 ( 比如，為 TwoPartComparator 處理的 key 增加一個可選的第三塊內(nèi)容 ) ， (a) 保持相同的比較器名稱 (b) 新的 key 增加版本號 (c) 改變比較器函數(shù)，使得它可以通過 key 里面的版本號來決定如何解釋它們。

性能

可以通過改變 include/leveldb/options.h 里的默認值來對性能進行調(diào)整優(yōu)化。

塊大小

LevelDB 會將相鄰的 key 值組合在一塊放到同一個 block 中，這樣的一個 block 是與永久性存儲設備進行傳輸?shù)幕締卧ＤJ的塊大小大概是 4096 個未壓縮字節(jié)。那些經(jīng)常需要掃描整個數(shù)據(jù)庫內(nèi)容的應用可能希望增大這個值。那些讀取大量小的 value 值的應用，如果可以得到性能上的改進，可能傾向于將這個值設得更小。如果這個值過大或過小，也不會有太多好處，比如小于 1KB 或者大于數(shù) MB 的情況下。需要指出的是，對于那些大的 block 大小，壓縮可能會更有效。

壓縮

每個塊被寫入永久性存儲設備之前會被單獨壓縮。由于默認的壓縮方法速度很快，同時對于那些很難壓縮的數(shù)據(jù)它會自動的關閉，因此默認情況下壓縮就是開啟的。只有在很特殊的情況下，應用才會去關閉壓縮，但是只有當通過 benchmarks 能看到性能提升時才應該這樣做。

??leveldb::Options?options;

??options.compression?=?leveldb::kNoCompression;

??...?leveldb::DB::Open(options,?name,?...)?....

緩存

數(shù)據(jù)庫內(nèi)容被存儲在文件系統(tǒng)的一系列文件中，每個文件保存了一系列的壓縮的 blocks 。如果 options.cache 值是非 NULL 的，這時那些已經(jīng)用過的未壓縮的塊內(nèi)容會被緩存。

??#include?"leveldb/cache.h"

??leveldb::Options?options;

??options.cache?=?leveldb::NewLRUCache(100?*?1048576);??//?100MB?cache

??leveldb::DB*?db;

??leveldb::DB::Open(options,?name,?&db);

??...?use?the?db?...

??delete?db

??delete?options.cache;

需要說明的是，緩存里存放的是未壓縮數(shù)據(jù)，因此它的大小是應用級別的數(shù)據(jù)大小，而不是壓縮后的 。 ( 對于已壓縮的 blocks 的緩存交給操作系統(tǒng) buffer 去緩存，或者是由客戶端提供自己的 Env 實現(xiàn)來完成 ) 。 在執(zhí)行大的讀操作的時候，應用程序可能希望不使用緩存，這樣就可以避免這些大數(shù)據(jù)的讀操作消耗掉大量的緩存 。一個針對迭代器的 option 參數(shù)可以實現(xiàn)這個目的：

??leveldb::ReadOptions?options;

??options.fill_cache?=?false;

??leveldb::Iterator*?it?=?db->NewIterator(options);

??for?(it->SeekToFirst();?it->Valid();?it->Next())?{

????...

??}

Key 的 layout

需要注意的是磁盤傳輸和緩存的單位是 block 。相鄰的 key( 根據(jù)數(shù)據(jù)庫排序結(jié)果 ) 通常會被放到同一個 block 里。因此應用程序可以通過將那些相鄰近的 key 值放到一塊進行訪問，將那些很少被使用的 key 值放到一個獨立的 key 值空間內(nèi)。

比如，假設在 LevelDB 之上實現(xiàn)一個簡單的文件系統(tǒng)。通常需要存儲的記錄數(shù)據(jù)如下：

???filename?->?permission-bits,?length,?list?of?file_block_ids

???file_block_id?->?data

我們可以為 filename 添加個前綴 ( 比如 '/') ，為 file_block_id 加上另一個 ( 比如 '0') ，這樣對于文件元數(shù)據(jù)的掃描就不不需要去獲取及緩存大量的文件內(nèi)容數(shù)據(jù)。

Checksums

LevelDB 會為它存儲在文件系統(tǒng)中的所有數(shù)據(jù)生成相應的 checksums 。通常有兩種方式來控制對 checksums 進行何種程度的驗證： ReadOptions::verify_checksums? 設為 true ，會強制對從文件系統(tǒng)中讀出的所有數(shù)據(jù)都進行 checksum 驗證。默認情況下，不進行驗證。 Options::paranoid_checks? 可以在打開數(shù)據(jù)庫之前將其設為 true ，這會使得?數(shù)據(jù)庫底層實現(xiàn)只要檢測到內(nèi)部數(shù)據(jù)錯誤時就會產(chǎn)生一個 error 。 Error 產(chǎn)生的時機取決于數(shù)據(jù)庫的哪個部分出了問題，比如可能在數(shù)據(jù)庫打開時或者是在后面執(zhí)行某個數(shù)據(jù)庫操作時。默認情況下， paranoid?checking 是關閉的，這樣即使數(shù)據(jù)庫的某些永久性存儲出了問題，它仍然也是可以使用的。?如果數(shù)據(jù)庫被破壞了 ( 可能是因為打開了 paranoid?checking 而導致它無法打開 ) ， leveldb::RepairDB 函數(shù)可以用來盡量地對數(shù)據(jù)進行恢復。

Approximate?Sizes

GetApproximateSizes 方法可以被用來得到一個或多個 key?range 所占用的文件系統(tǒng)空間的近似大小。

???leveldb::Range?ranges[2];

???ranges[0]?=?leveldb::Range("a",?"c");

???ranges[1]?=?leveldb::Range("x",?"z");

???uint64_t?sizes[2];

???leveldb::Status?s?=?db->GetApproximateSizes(ranges,?2,?sizes);

上面的調(diào)用，會設置 sizes[0] 的值為 range?[a..c) 所占用的文件系統(tǒng)空間的近似大小， sizes[1]? 的值為 range?[x..z) 所占用的文件系統(tǒng)空間的近似大小。

Environment

所有由 LevelDB 實現(xiàn)產(chǎn)生的文件操作 ( 及其他的操作系統(tǒng)調(diào)用 ) 都是通過 leveldb::Env 對象統(tǒng)一管理。為了進行更好的控制，某些客戶端可能希望提供自己的 Env 實現(xiàn)。比如應用程序可能希望在文件 IO 中引入自定義的延時來限制 LevelDB 對系統(tǒng)其他動作產(chǎn)生的影響。

??class?SlowEnv?:?public?leveldb::Env?{

????..?implementation?of?the?Env?interface?...

??};

??SlowEnv?env;

??leveldb::Options?options;

??options.env?=?&env;

??Status?s?=?leveldb::DB::Open(options,?...);

移植性 (Porting)

通過提供一個 leveldb/port/port.h 中的 types/methods/functions 的平臺描述實現(xiàn)，就可以將 LevelDB 移植到一個新平臺上。具體細節(jié)可以參考： leveldb/port/port_example.h

性能 (Performance)

下面是運行 db_bench 程序得到的性能測試報告。結(jié)果有些雜亂，但是足以說明問題。

測試環(huán)境

使用一個具有百萬條記錄的數(shù)據(jù)庫，每條記錄有一個 16 字節(jié)的 key 及 100 字節(jié)的 value 。對于 values 值壓縮后可能大概只有原始大小的一半。

LevelDB:?version?1.1

Date:?Sun?May?1?12:11:26?2011

CPU:?4?x?Intel(R)?Core(TM)2?Quad?CPU?Q6600?@?2.40GHz

CPUCache:?4096?KB

Keys:?16?bytes?each

Values:?100?bytes?each?(50?bytes?after?compression)

Entries:?1000000

Raw?Size:?110.6?MB?(estimated)

File?Size:?62.9?MB?(estimated)

寫性能

"fill"?benchmarks 會以順序地或者隨機的方式創(chuàng)建一個全新的數(shù)據(jù)庫。 "fillsync"?benchmark? 的每次操作都會將數(shù)據(jù)從操作系統(tǒng) flush 到磁盤；其他的寫操作會允許數(shù)據(jù)在操作系統(tǒng) buffer 中停留一段時間。 "overwrite"?benchmark? 會進行隨機的寫入以更新數(shù)據(jù)庫中現(xiàn)有的 key 值。

fillseq?:?1.765?micros/op;?62.7?MB/s

fillsync?:?268.409?micros/op;?0.4?MB/s?(10000?ops)

fillrandom?:?2.460?micros/op;?45.0?MB/s

overwrite?:?2.380?micros/op;?46.5?MB/s

上面的一次” op ”意味著對于單個 key/value 對的一次寫人。比如隨機寫 benchmark 每秒大概可以近似達到 400,000 寫操作。

每個 "fillsync" 操作花費 (0.3ms) 遠小于一次磁盤 seek 操作 ( 通常需要 10ms) 。我們懷疑這是因為硬盤本身會將這些更新緩存到它的 memory 里，在數(shù)據(jù)真正寫入到扇區(qū)之前就做出了響應。這種情況下的安全性取決于硬盤在電力供應出問題時是否有足夠的電力去保存它的 memory 中的數(shù)據(jù)。

讀性能

我們列出了正向及反向順序讀的性能，以及隨機查找的性能。需要注意的是，由 benchmark 創(chuàng)建的數(shù)據(jù)庫是很小的。因此這個報告只是刻畫了工作集可以載入到內(nèi)存時的 LevelDB 的性能。對于那些未命中操作系統(tǒng)緩存的單片數(shù)據(jù)讀取操作來說，開銷主要是由為從磁盤獲取數(shù)據(jù)所需進行的一次或兩次磁盤 seek 操作造成的。而寫操作性能幾乎不受工作集能否載入到內(nèi)存的影響。

?readrandom?:?16.677?micros/op;?( 每秒大概 60,000?reads)

readseq?:?0.476?micros/op;?232.3?MB/s

readreverse?:?0.724?micros/op;?152.9?MB/s

LevelDB 為提高讀性能會在后臺壓縮它的底層存儲數(shù)據(jù)。上面的測試是在進行過大量的隨機寫操作之后立即進行的。在進行過 compactions( 通常是自動觸發(fā)的 ) 再進行測試結(jié)果會更好些。

readrandom?:?11.602?micros/op;?( 每秒大概 85,000?reads)

readseq?:?0.423?micros/op;?261.8?MB/s

readreverse?:?0.663?micros/op;?166.9?MB/s

某些讀操作的高花費是由于從硬盤讀取出的 blocks 的重復解壓導致的。如果我們可以為 LevelDB 提供足夠的緩存使得它可以將所有的未壓縮塊放入內(nèi)存，那么讀性能會有更大地改善：

readrandom?:?9.775?micros/op;?( 每秒大概? 100,000?reads?before?compaction)

readrandom?:?5.215?micros/op;?( 每秒大概 190,000?reads?after?compaction)

其他信息

實現(xiàn)相關

Immutable?table 文件格式

Log 文件格式

譯考文獻

http://leveldb.googlecode.com/svn/trunk/doc/index.html

http://code.google.com/p/leveldb/

http://www.infoq.com/news/2011/07/LevelDB

LevelDB：一個快速輕量級的key-value存儲庫