設(shè)計(jì)思路
LSM-Tree(Log Structure Merge Tree)盗忱，將磁盤(pán)的隨機(jī)寫(xiě)轉(zhuǎn)化為順序?qū)懥杌＃涌炝藢?xiě)速度缠劝。LSM-Tree的思路是將索引樹(shù)拆成一大一小兩棵樹(shù)，較小的常駐內(nèi)存平挑，較大的持久化到磁盤(pán)游添，他們共同維護(hù)一個(gè)有序的key空間。寫(xiě)操作會(huì)首先操作內(nèi)存中的樹(shù)通熄，隨著內(nèi)存不斷變大唆涝，會(huì)觸發(fā)磁盤(pán)中樹(shù)的歸并操作(將內(nèi)存中的數(shù)據(jù)與磁盤(pán)中的數(shù)據(jù)進(jìn)行歸并)，而歸并操作本身僅有順序?qū)憽?隨著數(shù)據(jù)不斷寫(xiě)入唇辨，磁盤(pán)中的樹(shù)會(huì)不斷膨脹廊酣，為了避免每次參與歸并操作的數(shù)據(jù)量過(guò)大，以及優(yōu)化讀操作做考慮赏枚，LevelDB將磁盤(pán)中的數(shù)據(jù)又拆分成多層亡驰，每一層的數(shù)據(jù)達(dá)到一定容量后會(huì)觸發(fā)向下一層的歸并操作
Memtable 內(nèi)存數(shù)據(jù)結(jié)構(gòu)，跳表實(shí)現(xiàn)饿幅，新的數(shù)據(jù)會(huì)首先寫(xiě)入這里
Log 文件凡辱，寫(xiě)Memtable前會(huì)先寫(xiě)Log文件，Log通過(guò)append的方式順序?qū)懭肜醵鳌og使機(jī)器宕機(jī)導(dǎo)致的內(nèi)存數(shù)據(jù)丟失得以恢復(fù)
Immutable Memtable 達(dá)到Memtable上限后煞茫，Memtable會(huì)變成Immutable，為SST文件的歸并做準(zhǔn)備
SST文件 磁盤(pán)數(shù)據(jù)存儲(chǔ)文件摄凡，分為L(zhǎng)evel0 到 LevelN多層，單層SST文件總量隨著層次增加成倍增長(zhǎng)蚓曼，文件內(nèi)數(shù)據(jù)有序亲澡。其中Level0的SST文件由Immutable 直接dump產(chǎn)生。其他Level的SST由其上一層的文件和本層文件歸并產(chǎn)生纫版； SST文件在歸并中順序?qū)懘残鳎珊髢H可能在歸并中被刪除，而不會(huì)有任何的修改操作
Manifest 記錄SST文件在不同的Level的分布，單個(gè)SST文件的最大最小值
Current Manifest可能有多個(gè)癞己，記錄當(dāng)前Manifest的文件名
Slice
為什么不用引用而用Slice結(jié)構(gòu)
Slice允許value中包含\0結(jié)尾
Option
the speed of kSnappyCompression 200~500MB/s compression, 400~800MB/s decompression
異步寫(xiě)： 寫(xiě)操作從用戶進(jìn)程傳遞到操作系統(tǒng)就返回了膀斋，而操作系統(tǒng)從內(nèi)存到持久化存儲(chǔ)是異步的”匝牛可以通過(guò)fsync使寫(xiě)數(shù)據(jù)同步到存儲(chǔ)后再返回仰担， 異步寫(xiě)入比同步寫(xiě)入快很多 。使用異步寫(xiě)入绩社，如果只是寫(xiě)入進(jìn)程掛了摔蓝，不會(huì)丟失任何數(shù)據(jù)，但是機(jī)器crash就會(huì)丟失誰(shuí)
WriteOptions.sync 設(shè)置為true愉耙，相當(dāng)于調(diào)用write后再使用fsync
Option包含ReadOption和WriteOpion贮尉，以及普通的Option
Env
函數(shù)返回值，使用Status代替 true/false
File分為 SequentialFile朴沿， RandomFile猜谚，AppendFIle等，讀入的數(shù)據(jù)赌渣，放入scratch中魏铅，根據(jù)scratch生成slice對(duì)象
Read(size_t n, Slice* result, char* scratch)
Status
錯(cuò)誤信息采字符串，前三位表示長(zhǎng)度锡垄，第四位表示類型沦零，第五位之后表示信息
write
fwrite/fread/fflush是c語(yǔ)言規(guī)定的io流操作
用戶程序（fwrite）用戶緩存區(qū)(write/fflush)內(nèi)核緩沖區(qū)(fsync)物理設(shè)備
util/coding
通過(guò)左移右移和 位與運(yùn)算，取特定位值货岭，例：(value >> 8) & 0xff 取第二個(gè)字節(jié)
通過(guò)或運(yùn)算路操，設(shè)置某個(gè)特定的位
Varint 通過(guò)變長(zhǎng)字節(jié)編碼，可以節(jié)省空間千贯。但壞處是大數(shù)需要用5個(gè)字節(jié)表示了屯仗。 每個(gè)字節(jié)第一位為1的話，表示連續(xù)上一個(gè)數(shù)字搔谴，因此一個(gè)字節(jié)可以表示小于127的數(shù)字
SequenceNumber
一共64位魁袜，其中sequenceNum只占56bit，valueType占8bit
SkipList
使用arena管理內(nèi)存敦第，arena相當(dāng)于內(nèi)存池
實(shí)現(xiàn)簡(jiǎn)單峰弹，相比B樹(shù)系列，更加輕量芜果，SequenceNumber保證了不會(huì)有相同的node鞠呈，也就保證了node不會(huì)更新的情況
迭代器類實(shí)現(xiàn)在類的定義中
memory order：
1、memory_order_seq_cst 順序一致性模型
2右钾、memory_order_release/acquire/consume 提供release蚁吝，acquire或者consume旱爆，release語(yǔ)義一致性保障
3、relexed consisency model 松散一致性模型
