leveldb是一個由谷歌開源的高效的單機key-value存儲系統，該系統提供了key到value的有序映射，現有的主流的kv存儲系統有很多基于或者借鑒了leveldb的思想。主體代碼大約1w行。基于 LSM(LOG Structured Merge Tree) 實作，将所有的 Key/Value 按照 Key 的詞法序有序地儲存在檔案中，具有很高的随機/順序寫性能，非常适用于寫多讀少的環境。
DBImpl是leveldb資料庫的結構體，一個DBImpl就是一個資料庫，DBImpl的結構體在db_impl.h中。DBImpl和DB是友元類（friend class），DB可以直接通路DBImpl中的私有成員和保護成員，DB類是leveldb的對外接口。DBImpl中主要的成員主要有：
上圖簡單展示了 LevelDB 的整體架構。
MemTable：記憶體資料結構，具體實作是 SkipList。 接受使用者的讀寫請求，新的資料會先在這裡寫入。
Immutable MemTable：當 MemTable 的大小達到設定的門檻值後，會被轉換成 Immutable MemTable，隻接受讀操作，不再接受寫操作，然後由背景線程 flush 到磁盤上 —— 這個過程稱為 minor compaction。
Log：資料寫入 MemTable 之前會先寫日志，用于防止當機導緻 MemTable 的資料丢失。一個日志檔案對應到一個 MemTable。
SSTable：Sorted String Table。分為 level-0 到 level-n 多層，每一層包含多個 SSTable，檔案内資料有序。除了 level-0 之外，每一層内部的 SSTable 的 key 範圍都不相交。
Manifest：Manifest 檔案中記錄 SSTable 在不同 level 的資訊，包括每一層由哪些 SSTable，每個 SSTable 的檔案大小、最大 key、最小 key 等資訊。
Current：重新開機時，LevelDB 會重新生成 Manifest，是以 Manifest 檔案可能同時存在多個，Current 記錄的是目前使用的 Manifest 檔案名。
TableCache：TableCache 用于緩存 SSTable 的檔案描述符、索引和 filter。
BlockCache：SSTable 的資料是被組織成一個個 block。BlockCache 用于緩存這些 block（解壓後）的資料。
首先我們會把資料寫入memtable(位于記憶體中)，當memtable滿了之後。就會變成immutable memtable。也就是所謂的冷卻狀态，這個時候的memtable無法再被寫入資料。在immutable memtable中的資料會準備寫入SST(磁盤)中。
如果不使用任何同步機制（例如mutex或atomic），在多線程中讀寫同一個變量，那麼程式的結果是難以預料的。編譯器和CPU的行為會影響到程式執行的結果：
C++不保證一條沒有任何機制的語句是原子操作，其他線程可能看見指令執行的中間結果
為了優化程式執行性能，CPU可能會調整指令的執行順序（如果兩條指令不互相依賴）
如果CPU沒有亂序執行指令，那麼Thread-2将輸出100，然而，對于Thread-1來說，x=100和y=200兩個語句之間沒有依賴關系，CPU可能調整兩者的執行順序，Thread-2将輸出0或者100。
在CPU cache的影響下，一個CPU執行了某個指令，不會立即被其他CPU看見。
盡管A可能先于B執行，但CPU cache的影響下，Thread-2不能保證立即看到A執行的結果，是以Thread-2可能輸出0或者100。
C++中對共享資料的存取在并法條件下可能引發data race的行為，需要限制并發程式以某種特定的順序執行，有兩種方式，使用mutex保護共享資料，或者原子操作，針對原子類型的操作要麼一步完成，要麼不完成，不會在中途切換cpu，這樣可以防止多線程指令交叉執行帶來的可能錯誤。非原子操作下，某個線程可能看見的是其他線程未操作完成的資料。
atomic頭檔案聲明了兩個C++類，atomic和atomic_flag。
https://www.jianshu.com/p/8c1bb012d5f8
memory order解決的是多線程讀寫中的問題2，是單個線程中的操作造成多線程出現的問題。為了解決2中重排造成的問題，C++中有6種可以應用于原子變量的記憶體次序。（思考：memory fence保證的是執行的順序，但是這并不能解決問題3中cache産生的問題：cache重新整理的順序沒有受到限制）
舉例如下。這種寫法可以讓data=42先于flag=true執行，讓while循環先于assert執行。
Slice類中有兩個成員，data_和size_，前者是資料，後者是大小。
default拷貝構造函數是淺拷貝
需要注意的是兩個slice比較大小的函數。隻比較共同長度的那一部分，如果那一部分相同，那麼誰長誰大。例如，“123”<"23"
SkipList 是平衡樹的一種替代資料結構，但是和紅黑樹不相同的是，SkipList 對于樹的平衡的實作是基于一種随機化的算法的，這樣也就是說 SkipList 的插入和删除的工作是比較簡單的。SkipList 不僅是維護有序資料的一個簡單實作，而且相比較平衡樹來說，在插入資料的時候可以避免頻繁的樹節點調整操作，是以寫入效率是很高的，LevelDB 整體而言是個高寫入系統，SkipList 在其中應該也起到了很重要的作用。Redis 為了加快插入操作，也使用了 SkipList 來作為内部實作資料結構。leveldb中的跳表是線程安全的，寫資料要加鎖，讀資料不需要加鎖，隻要保證跳表不會在讀的過程中被銷毀。
聲明新的node的時候，是一個node加一個next_數組大小，Node類中成員的排列是連續的。next_數組存儲了各層的後繼節點，next_數組的長度取決于生成節點時跳表的高度height，node類中有一個私有成員next_[1]，用Node*數組來代替Node**，實際上就是個指針。
使用了單連結清單的記憶體池。用blocks數組管理已經配置設定出去的記憶體塊。回收記憶體的時候将其逐一回收。（todo:為什麼使用array delete，為什麼沒有對remaining記憶體回收？）
需要注意的是采取了記憶體對齊的措施。
memtable的主要功能是将内部編碼、記憶體配置設定（arena）和SkipList封裝在一起， 提供了将 KV 資料寫入，删除以及讀取 KV 記錄的操作接口，但是事實上 Memtable 并不存在真正的删除操作，删除某個 key 的 value 在 Memtable 内是作為插入一條記錄實施的，但是會打上一個 key 的删除标記（tag的ValueType置為kTypeDeletion），真正的删除操作是 Lazy 的，會在以後的 Compaction 過程中去掉這個 KV。
memtable使用了引用計數，維護了一個refs_變量。每次調用Ref()，引用計數++，調用unref()，引用計數--，若引用計數為0，則delete此對象。
memtable中定義了兩個友元類：memtableIterator和memtableBackWardIterator。定義了自己的記憶體池、比較器和跳表。
memtable中有兩個主要的函數：Add和Get。
memtable中的資料用編碼之後的格式存儲，其中sequence是序列号（快照是根據sequence生成的），type标志着這條entry是否被删除。
//todo：
// todo:
Version儲存目前磁盤以及記憶體中的檔案資訊，一般隻有一個version為”current version”。同時還儲存了一系列的曆史version，這些version的存在是因為有讀操作還在引用（iterator和get，Compaction操作後會産生新的version作為current version
VersionSet就是一系列Version的集合
VersionEdit表示Version之間的變化，表示增加了多少檔案，删除了多少檔案
快照提供了一個目前KV存儲的一個可讀視圖，使得讀取操作不受寫操作影響，可以在讀操作過程中始終看到一緻的資料
一個快照對應目前存儲的最新資料版本号
寫操作
Put操作會将(key,value)轉化成writebatch後，通過write接口來完成
在write之前需要通過MakeRoomForWrite來保證MemTable有空間來接受write請求，這個過程中可能阻塞寫請求，以及進行compaction。
BuildBatchGroup就是盡可能的将多個writebatch合并在一起然後寫下去，能夠提升吞吐量
AddRecord就是在寫入MemTable之前,現在操作寫入到log檔案中
最後WriteBatchInternal::InsertInto會将資料寫入到MemTable中
讀操作
首先判斷options.snapshot是否為空，如果為不為空，快照值就取這個值，否則取最新資料的版本号
然後依次嘗試去MemTable, Immutable MemTable, VersionSet中去查找。VersionSet中的查找流程:
逐層查找，确定key可能所在的檔案
然後根據檔案編号,在TableCache中查找，如果未命中，會将Table資訊Load到cache中
根據Table資訊，确定key可能所在的Block
在BlockCache中查找Block，如果未命中，會将Block load到Cache中。然後在Block内查找key是否命中
更新讀資料的統計資訊，作為一根檔案是否應該進行Compaction的依據，後面講述Compaction時會說明
最後釋放對Memtable，Immutable MemTable，VersionSet的引用
memtabe的寫入過程從WriteBatchInternal::InsertInto()函數開始。模式很奇怪，定義了memTableInserter的handler，用iterate的方式處理？
tips：
用統一的status類作為open、write、get等函數的傳回值，以此檢視執行是否成功。如果是get等需要執行結果資料的函數，用一個位址傳參作為承接。
【參考】
https://developer.aliyun.com/article/618109
https://blog.csdn.net/sjc2870/article/details/112342573