LevelDB源碼分析之八：memtable

閱讀本文可參考：

LevelDB源碼分析之一：coding

LevelDB源碼分析之二：comparator

LevelDB源碼分析之三：arena

LevelDB源碼分析之四：AtomicPointer

LevelDb源碼分析之五：skiplist（1）

LevelDb源碼分析之六：skiplist（2）

LevelDB源碼分析之七：Random

? ? ? ? 在LevelDB中所有KV數(shù)據(jù)都是存儲(chǔ)在Memtable，Immutable Memtable和SSTable中的，Immutable Memtable從結(jié)構(gòu)上講和Memtable是完全一樣的，區(qū)別僅僅在于其是只讀的，不允許寫(xiě)入操作，而Memtable則是允許寫(xiě)入和讀取的。當(dāng)Memtable寫(xiě)入的數(shù)據(jù)占用內(nèi)存到達(dá)指定數(shù)量，則自動(dòng)轉(zhuǎn)換為Immutable Memtable，等待Dump到磁盤(pán)中，系統(tǒng)會(huì)自動(dòng)生成新的Memtable供寫(xiě)操作寫(xiě)入新數(shù)據(jù)，理解了Memtable，那么Immutable Memtable自然不在話下。

? ? ? ? LevelDB的MemTable提供了將KV數(shù)據(jù)寫(xiě)入，刪除以及讀取KV記錄的操作接口，但是事實(shí)上Memtable并不存在真正的刪除操作，刪除某個(gè)Key的Value在Memtable內(nèi)是作為插入一條記錄實(shí)施的，但是會(huì)打上一個(gè)Key的刪除標(biāo)記，真正的刪除操作是延后的，會(huì)在以后的Compaction過(guò)程中去掉這個(gè)KV。 需要注意的是，LevelDB的Memtable中KV對(duì)是根據(jù)Key大小有序存儲(chǔ)的，在系統(tǒng)插入新的KV時(shí)，LevelDB要把這個(gè)KV插到合適的位置上以保持這種Key有序性。其實(shí)，LevelDb的Memtable類只是一個(gè)接口類，真正的操作是通過(guò)背后的SkipList來(lái)做的，包括插入操作和讀取操作等，所以Memtable的核心數(shù)據(jù)結(jié)構(gòu)是一個(gè)SkipList。

? ? ? ? Memtable主要作用是對(duì)skiplist、arena、comparator進(jìn)行組合和管理，接口函數(shù)屏蔽了底層操作，對(duì)使用者更加優(yōu)雅。

一.構(gòu)造函數(shù)

MemTable::MemTable(const?InternalKeyComparator&?cmp)
????:?comparator_(cmp),
??????refs_(0),
??????table_(comparator_,?&arena_)?{
}

構(gòu)造函數(shù)對(duì)私有成員變量進(jìn)行了初始化，table_是SkipList類型，將&aerna_當(dāng)做key傳入，arena_是Arena類型。

二.內(nèi)存估算函數(shù)

size_t?MemTable::ApproximateMemoryUsage()?{?return?arena_.MemoryUsage();?}

這里直接調(diào)用的是Arena類的MemoryUsage方法，該方法返回整個(gè)內(nèi)存池使用內(nèi)存的總大?。ú痪_）。

三.添加函數(shù)

void?MemTable::Add(SequenceNumber?s,?ValueType?type,
???????????????????const?Slice&?key,
???????????????????const?Slice&?value)?{
??//?Format?of?an?entry?is?concatenation?of:
??//??key_size?????:?varint32?of?internal_key.size()
??//??key?bytes????:?char[internal_key.size()]
??//??value_size???:?varint32?of?value.size()
??//??value?bytes??:?char[value.size()]
??size_t?key_size?=?key.size();
??size_t?val_size?=?value.size();
??//?參考LevelDB源碼分析之二：comparator中關(guān)于Internal?Key的介紹，
??//?因?yàn)镮nternal?Key由user_key、sequence和type三個(gè)字段組成，user_key
??//?也就是這里的key，sequence和type會(huì)打包成一個(gè)uint64_t類型的數(shù)據(jù)，
??//?所以這里的長(zhǎng)度為key_size+8
??size_t?internal_key_size?=?key_size?+?8;
??//?參考LevelDB源碼分析之一：coding，為了節(jié)約空間，數(shù)字都是編碼存儲(chǔ)的，
??//?VarintLength方法求出的是編碼后的長(zhǎng)度。關(guān)于encoded_len的組成詳見(jiàn)下圖。
??const?size_t?encoded_len?=
??????VarintLength(internal_key_size)?+?internal_key_size?+
??????VarintLength(val_size)?+?val_size;
??//?分配內(nèi)存
??char*?buf?=?arena_.Allocate(encoded_len);
??//?編碼internal_key_size，編碼后存放到buf中，p指向internal_key_size的結(jié)尾
??char*?p?=?EncodeVarint32(buf,?internal_key_size);
??//?將key拷貝到buf中，占用key_size大小
??memcpy(p,?key.data(),?key_size);
??p?+=?key_size;
??//?將sequence和type打包后存放到buf中，大小為8字節(jié)，EncodeFixed64只是進(jìn)行了簡(jiǎn)單的拷貝（考慮的大端或小端）。
??EncodeFixed64(p,?(s?<<?8)?|?type);
??p?+=?8;
??//?編碼val_size，編碼后存放到buf中，p指向val_size的結(jié)尾
??p?=?EncodeVarint32(p,?val_size);
??//?將value拷貝到buf中，占用val_size大小
??memcpy(p,?value.data(),?val_size);
??//?判斷存儲(chǔ)完后所占內(nèi)存的大小，是否與初始計(jì)算的大小相等
??assert((p?+?val_size)?-?buf?==?encoded_len);
??//?插入到SkipList中
??table_.Insert(buf);
}

一個(gè)完整的buf內(nèi)容如下圖所示。

四.獲取函數(shù)

//?如果能找到key對(duì)應(yīng)的value,?將該value存儲(chǔ)到*value參數(shù)中，返回值為true。
//?如果這個(gè)key中的有刪除標(biāo)識(shí),存放一個(gè)NotFound()錯(cuò)誤到*status參數(shù)中，返回值為true。
//?否則返回值為false
bool?MemTable::Get(const?LookupKey&?key,?std::string*?value,?Status*?s)?{
??//?得到memkey，memkey中實(shí)際上包含了klength|userkey|tag，也就是說(shuō)它包含了internal_key_size
??//?和internal_key
??Slice?memkey?=?key.memtable_key();
??Table::Iterator?iter(&table_);
??//?找到SkipList中大于等于memkey的結(jié)點(diǎn)
??iter.Seek(memkey.data());
??//?如果找到了這個(gè)結(jié)點(diǎn)
??if?(iter.Valid())?{
	//?一個(gè)結(jié)點(diǎn)的結(jié)構(gòu)如下所示
????//?entry?format?is:
????//????klength??varint32
????//????userkey??char[klength]
????//????tag??????uint64
????//????vlength??varint32
????//????value????char[vlength]
????//?Check?that?it?belongs?to?same?user?key.??We?do?not?check?the
????//?sequence?number?since?the?Seek()?call?above?should?have?skipped
????//?all?entries?with?overly?large?sequence?numbers.
????const?char*?entry?=?iter.key();
????uint32_t?key_length;
	//?取出klength，并將key_ptr指到klength之后
	//?為什么加5？參考LevelDB源碼分析之一：coding
????const?char*?key_ptr?=?GetVarint32Ptr(entry,?entry+5,?&key_length);
	//?比較結(jié)點(diǎn)中的userkey和LookupKey中的userkey是否相等，如果相等，說(shuō)明找到了這個(gè)結(jié)點(diǎn)。
????if?(comparator_.comparator.user_comparator()->Compare(
????????????Slice(key_ptr,?key_length?-?8),
????????????key.user_key())?==?0)?{
??????//?獲取tag，tag等于(sequence<<8)|type
??????const?uint64_t?tag?=?DecodeFixed64(key_ptr?+?key_length?-?8);
	??//?取出type并判斷
??????switch?(static_cast(tag?&?0xff))?{
????????case?kTypeValue:?{
		??//?取出value的大小和內(nèi)容
??????????Slice?v?=?GetLengthPrefixedSlice(key_ptr?+?key_length);
??????????value->assign(v.data(),?v.size());
??????????return?true;
????????}
????????case?kTypeDeletion:
??????????*s?=?Status::NotFound(Slice());
??????????return?true;
??????}
????}
??}
??return?false;
}

}

獲取函數(shù)的第一個(gè)參數(shù)是LookupKey類型，LookupKey是一個(gè)幫助類，通過(guò)它可以更方便的對(duì)Memtable進(jìn)行操作。由于LookupKey的官方注釋特別詳細(xì)，這里就不分析了。

? ? ?