當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

LevelDB源码解读

發布時間：2024/2/28 编程问答 26 豆豆

生活随笔收集整理的這篇文章主要介紹了 LevelDB源码解读小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

LevelDB源碼解讀

- 提供的功能
- - read and write
  - - Group commit
    - sequence number
  - delete
  - Atomic Updates
  - 同步寫Synchronous Writes
  - 遍歷 iteration
  - 快照 Snapshots
  - Slice
  - 比較器 Comparators
- concurrency保證
- compaction
- LevelDB的性能優化參數
- - Block size
  - Compression
  - Cache
  - 鍵分布 Key Layout
  - Filters
  - 校驗和 Checksum
  - Approximate Sizes
  - Environment
  - porting
- 參考鏈接

提供的功能

leveldb index

前面打開關閉數據庫的方式略過

read and write

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);

寫流程：

找到合適的memtable(skiplist)并寫入數據，如果memtable寫完并且immutableTable還未完成持久化，或者L0文件太多，則等待。如果memtable滿了，則換一個memtable，并觸發compaction

寫日志，下刷日志

寫memtable

讀流程：

首先查找memtable，再查找immutable memtable

如果沒有，查找下面所有持久化的levelVersion::Get，逐層向下搜索。搜索方法的策略是并不是遍歷每一個sstable，而是先看需要查找的key是否落在sstable的范圍內（每個sstable記錄begin/end key），如果落在，對sstable搜索。

后臺線程也會按需做compaction。通過MaybeScheduleCompaction()函數判斷。

注意，日志只是為了保證內存中的數據不丟失（memtable和immutable），內存數據下刷完成之后，日志就可以刪掉了

Group commit

為了防止寫日志在高并發下成為瓶頸，LevelDB將不同線程同時產生的日志數據聚合在一起寫入文件并進行一次fsync()，而非對每個線程寫的數據進行單獨fsync()。這個做法稱為group commit。

具體的commit見added group commit

具體的實現上，通過在構造writer的時候控制mutex，只有一個線程會順利進行BuildBatchGroup，而其他沒有拿到mutex的線程會在隨后將日志操作寫進隊列。重復這個過程，最終只有排在隊首的線程會真正flush日志，其他的線程都在等待。

sequence number

sequence number 是一個由VersionSet直接持有的全局的編號，每次寫入（注意批量寫入時sequence number是相同的），就會遞增。key的排序以及snapshot都要依賴它。

當我們進行Get操作時，我們只需要找到目標key，同時其sequence number 小于等于sequence number：

普通的讀取，sepcific sequence number =last sequence number
snapshot讀取，sepcific sequenc number =snapshot sequence number

delete

delete仍然是通過write batch的形式向存儲引擎下發的。只不過ValueType是特殊的kTypeDeletion。但是delete在compact的時候需要特殊對待

Atomic Updates

將一系列的操作作為一個batch，提供原子性。這里猜測做法是在WAL中增加一些特殊的LogEntry如Transaction begin/end等。

#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); }

同步寫Synchronous Writes

leveldb::WriteOptions write_options; write_options.sync = true; db->Put(write_options, ...);

異步寫比同步寫塊上千倍，但是默認的異步寫有可能導致丟數據（系統crash的時候異步寫還沒完成）

Note that a crash of just the writing process (i.e., not a reboot) will not cause any loss since even when sync is false, an update is pushed from the process memory into the operating system before it is considered done.

如果系統希望避免丟數據，可以用以下幾種方式實現：

只要上層應用知道當前寫的數據是什么，那么就算crash了也沒關系，重試就行了

另外可以每隔N個async write寫一個sync write作為checkpoint，如果crash了，從上一個checkpoint處開始寫就行了。

另外可以用atomic write提供的batch寫。

遍歷 iteration

scan table

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;

范圍搜索

for (it->Seek(start);it->Valid() && it->key().ToString() < limit;it->Next()) {... }

倒序，注意，這里和正序的時間復雜度不一致。

for (it->SeekToLast(); it->Valid(); it->Prev()) {... }

快照 Snapshots

快照只讀，并且讀時可以不用加鎖，我們使用DB:GetSnapshot()創建快照：

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);

Slice

Slice用來存放levelDB存儲的數據類型，它存放數據的length和指針。使用Slice是一種比std::string更為輕量化的方法。LevelDB不允許返回末尾是null的C-Style字符串，LevelDB允許字符串含有\0。另外slice持有的是指針，而不是對象，所以要注意指針指向的對象的生命周期

class LEVELDB_EXPORT Slice {public:// 各種構造函數，成員函數...private:const char* data_;size_t size_; }; leveldb::Slice s1 = "hello"; // null-termicated C-style string std::string str("world"); // C++ string leveldb::Slice s2 = str;// Slice輸出為std::string std::string str = s1.ToString(); assert(str == std::string("hello"));

比較器 Comparators

levelDB可以針對自定義的Slice數據類型使用自定義的比較器。只要在打開數據的時候指定比較器options.comparator = &cmp;就行了。該比較器的名字會在數據庫初始化的時候持久化進數據庫，如果后面使用不同命的比較器打開數據庫，會失敗。

concurrency保證

每個database（文件系統的一個對應目錄）只能同一時刻被一個進程打開，level啟動的時候會獲取一個文件鎖。在一個進程內，DB對象leveldb::DB可以被多個線程并發訪問。由levelDB負責線程間同步。當然如果要做事務的話（writebatch）可能要外部進行并發控制（加鎖）。

compaction

之前已經談到了memtable、immutable、各個level。除了l0中每個run是可以重疊的（其實l0就是一個個的memtable），其他level都是只有一個run，被分配成很多2M的小文件。

做compaction的時候，只有l0層是將所有文件一起合并，其它層都是以2M為單位進行合并，寫入合并的文件，丟棄之前的文件。

LevelDB Compaction分三種：

minor compaction
- 將immutable memtable dump成sstable
major compaction
- 如果某個level文件過多或過大、seek的次數過多都會引發Major compaction，每一層都有一個target size，通過比較算出一個score，然后對score較高的某個level的sstable進行major compaction
- 通過PickLevelForMemTableOutput判斷產生文件位于哪一層
Manual Compaction
- 通過接口DBImpl::CompactRange(const Slice begin, const Slice end)接口調用
- 可以看到，如果某層一直沒有進行Major compaction，可能會造成compaction在高層的數據一直無法和低層的delete進行merge，導致數據無法被回收。這是可以主動調用Manual Compaction，手動對某個范圍進行compaction，也就是說，通過一次全量的compaction，消除delete特別是range delete帶來的負面影響
- 數據無法被回收只是影響的一方面，在數據庫應用中，delete會導致統計信息不準，影響sql優化器的決策

LevelDB的性能優化參數

Block size

levelDB默認最小存儲單元Block默認是4K（壓縮前），如果上層應用經常做全表掃描的話，可以增大Block size。如果上層應用經常做各種小的隨機讀，可以縮小Block size。實踐表明Block大于幾M或者小于1K是沒有任何益處。有一點要注意的是，Blocksize越大Compression越高效。

Compression

每個block在持久化之前默認都需要被壓縮。當然用戶也可以顯式指定不需要壓縮

leveldb::Options options; options.compression = leveldb::kNoCompression; ... leveldb::DB::Open(options, name, ...) ....

Cache

LevelDB可以指定Cache的大小，Cache中存放的是已經持久化的數據，注意這個cache不是文件系統的buffer cache。buffer cache存儲的是已經被壓縮的數據，levelDB中的cache存儲的是解壓后的數據。

如果上層應用進行一系列的讀例如table scan，我們希望將cache disable掉，以防上面的cache全被刷掉，下面的代碼，就是在當前的遍歷中disable掉cache。

leveldb::ReadOptions options; options.fill_cache = false; leveldb::Iterator* it = db->NewIterator(options); for (it->SeekToFirst(); it->Valid(); it->Next()) {... }

鍵分布 Key Layout

LevelDB中的鍵是順序分布的，所以可以將經常訪問的key放一起，不長訪問的key放一起。

Filters

因為LevelDB使用了LSM tree，因此一個簡單的Get()操作可能會設計多個對磁盤的read，為了優化讀性能，LevelDB使用了布隆過濾器(Bloom Filter)判斷某個鍵是否存在。

leveldb::Options options; options.filter_policy = NewBloomFilterPolicy(10); leveldb::DB* db; leveldb::DB::Open(options, "/tmp/testdb", &db); ... use the database ... delete db; delete options.filter_policy;

實際應用中，我們需要對過濾器的大小和過濾器的精度進行取舍。這部分的代碼放在leveldb/filter_policy.h

校驗和 Checksum

LevelDB使用Checksum校驗持久化數據，ReadOptions::verify_checksums將對每一個read都做校驗。Options::paranoid_checks將在數據庫打開時校驗整個數據庫的Checksum

如果發現數據損壞，可以使用leveldb::RepairDB來修復數據。

Approximate Sizes

使用GetApproximateSizes用來獲取大概占用的空間

leveldb::Range ranges[2]; ranges[0] = leveldb::Range("a", "c"); ranges[1] = leveldb::Range("x", "z"); uint64_t sizes[2]; db->GetApproximateSizes(ranges, 2, sizes);

Environment

LevelDB可以使用用戶自定義的環境參數、接口函數，例如，用戶可以在磁盤IO路徑上加入一些delay

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可以引入不同的系統實現，例如：mutex、condition variable等。從而在不同的系統上實現LevelDB。

參考鏈接

[leveldb] 3.put/delete操作

LevelDB設計與實現 - 基礎篇

總結

以上是生活随笔為你收集整理的LevelDB源码解读的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。