設計思路
LSM-Tree(Log Structure Merge Tree)，將磁盤的隨機寫轉(zhuǎn)化為順序?qū)?，加快了寫速度。LSM-Tree的思路是將索引樹拆成一大一小兩棵樹，較小的常駐內(nèi)存，較大的持久化到磁盤，他們共同維護一個有序的key空間。寫操作會首先操作內(nèi)存中的樹，隨著內(nèi)存不斷變大，會觸發(fā)磁盤中樹的歸并操作(將內(nèi)存中的數(shù)據(jù)與磁盤中的數(shù)據(jù)進行歸并)，而歸并操作本身僅有順序?qū)憽?隨著數(shù)據(jù)不斷寫入，磁盤中的樹會不斷膨脹，為了避免每次參與歸并操作的數(shù)據(jù)量過大，以及優(yōu)化讀操作做考慮，LevelDB將磁盤中的數(shù)據(jù)又拆分成多層，每一層的數(shù)據(jù)達到一定容量后會觸發(fā)向下一層的歸并操作
Memtable 內(nèi)存數(shù)據(jù)結(jié)構，跳表實現(xiàn)，新的數(shù)據(jù)會首先寫入這里
Log 文件，寫Memtable前會先寫Log文件，Log通過append的方式順序?qū)懭?。Log使機器宕機導致的內(nèi)存數(shù)據(jù)丟失得以恢復
Immutable Memtable 達到Memtable上限后，Memtable會變成Immutable，為SST文件的歸并做準備
SST文件 磁盤數(shù)據(jù)存儲文件，分為Level0 到 LevelN多層，單層SST文件總量隨著層次增加成倍增長，文件內(nèi)數(shù)據(jù)有序。其中Level0的SST文件由Immutable 直接dump產(chǎn)生。其他Level的SST由其上一層的文件和本層文件歸并產(chǎn)生； SST文件在歸并中順序?qū)?，生成后僅可能在歸并中被刪除，而不會有任何的修改操作
Manifest 記錄SST文件在不同的Level的分布，單個SST文件的最大最小值
Current Manifest可能有多個，記錄當前Manifest的文件名
Slice
為什么不用引用而用Slice結(jié)構
Slice允許value中包含\0結(jié)尾
Option
the speed of kSnappyCompression 200~500MB/s compression, 400~800MB/s decompression
異步寫： 寫操作從用戶進程傳遞到操作系統(tǒng)就返回了，而操作系統(tǒng)從內(nèi)存到持久化存儲是異步的?？梢酝ㄟ^fsync使寫數(shù)據(jù)同步到存儲后再返回， 異步寫入比同步寫入快很多 。使用異步寫入，如果只是寫入進程掛了，不會丟失任何數(shù)據(jù)，但是機器crash就會丟失誰
WriteOptions.sync 設置為true，相當于調(diào)用write后再使用fsync
Option包含ReadOption和WriteOpion，以及普通的Option
Env
函數(shù)返回值，使用Status代替 true/false
File分為 SequentialFile， RandomFile，AppendFIle等，讀入的數(shù)據(jù)，放入scratch中，根據(jù)scratch生成slice對象
Read(size_t n, Slice* result, char* scratch)
Status
錯誤信息采字符串，前三位表示長度，第四位表示類型，第五位之后表示信息
write
fwrite/fread/fflush是c語言規(guī)定的io流操作
用戶程序（fwrite）用戶緩存區(qū)(write/fflush)內(nèi)核緩沖區(qū)(fsync)物理設備
util/coding
通過左移右移和 位與運算，取特定位值，例：(value >> 8) & 0xff 取第二個字節(jié)
通過或運算，設置某個特定的位
Varint 通過變長字節(jié)編碼，可以節(jié)省空間。但壞處是大數(shù)需要用5個字節(jié)表示了。 每個字節(jié)第一位為1的話，表示連續(xù)上一個數(shù)字，因此一個字節(jié)可以表示小于127的數(shù)字
SequenceNumber
一共64位，其中sequenceNum只占56bit，valueType占8bit
SkipList
使用arena管理內(nèi)存，arena相當于內(nèi)存池
實現(xiàn)簡單，相比B樹系列，更加輕量，SequenceNumber保證了不會有相同的node，也就保證了node不會更新的情況
迭代器類實現(xiàn)在類的定義中
memory order：
1、memory_order_seq_cst 順序一致性模型
2、memory_order_release/acquire/consume 提供release，acquire或者consume，release語義一致性保障
3、relexed consisency model 松散一致性模型
