LevelDB源碼分析之八:memtable
閱讀本文可參考:
LevelDB源碼分析之一:coding
LevelDB源碼分析之二:comparator
LevelDB源碼分析之三:arena
LevelDB源碼分析之四:AtomicPointer
LevelDb源碼分析之五:skiplist(1)
LevelDb源碼分析之六:skiplist(2)
LevelDB源碼分析之七:Random
? ? ? ? 在LevelDB中所有KV數(shù)據(jù)都是存儲在Memtable,Immutable Memtable和SSTable中的,Immutable Memtable從結(jié)構(gòu)上講和Memtable是完全一樣的,區(qū)別僅僅在于其是只讀的,不允許寫入操作,而Memtable則是允許寫入和讀取的。當(dāng)Memtable寫入的數(shù)據(jù)占用內(nèi)存到達(dá)指定數(shù)量,則自動轉(zhuǎn)換為Immutable Memtable,等待Dump到磁盤中,系統(tǒng)會自動生成新的Memtable供寫操作寫入新數(shù)據(jù),理解了Memtable,那么Immutable Memtable自然不在話下。
? ? ? ? LevelDB的MemTable提供了將KV數(shù)據(jù)寫入,刪除以及讀取KV記錄的操作接口,但是事實(shí)上Memtable并不存在真正的刪除操作,刪除某個Key的Value在Memtable內(nèi)是作為插入一條記錄實(shí)施的,但是會打上一個Key的刪除標(biāo)記,真正的刪除操作是延后的,會在以后的Compaction過程中去掉這個KV。 需要注意的是,LevelDB的Memtable中KV對是根據(jù)Key大小有序存儲的,在系統(tǒng)插入新的KV時(shí),LevelDB要把這個KV插到合適的位置上以保持這種Key有序性。其實(shí),LevelDb的Memtable類只是一個接口類,真正的操作是通過背后的SkipList來做的,包括插入操作和讀取操作等,所以Memtable的核心數(shù)據(jù)結(jié)構(gòu)是一個SkipList。
? ? ? ? Memtable主要作用是對skiplist、arena、comparator進(jìn)行組合和管理,接口函數(shù)屏蔽了底層操作,對使用者更加優(yōu)雅。
一.構(gòu)造函數(shù)
MemTable::MemTable(const?InternalKeyComparator&?cmp) ????:?comparator_(cmp), ??????refs_(0), ??????table_(comparator_,?&arena_)?{ }
構(gòu)造函數(shù)對私有成員變量進(jìn)行了初始化,table_是SkipList類型,將&aerna_當(dāng)做key傳入,arena_是Arena類型。
二.內(nèi)存估算函數(shù)
size_t?MemTable::ApproximateMemoryUsage()?{?return?arena_.MemoryUsage();?}
這里直接調(diào)用的是Arena類的MemoryUsage方法,該方法返回整個內(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三個字段組成,user_key ??//?也就是這里的key,sequence和type會打包成一個uint64_t類型的數(shù)據(jù), ??//?所以這里的長度為key_size+8 ??size_t?internal_key_size?=?key_size?+?8; ??//?參考LevelDB源碼分析之一:coding,為了節(jié)約空間,數(shù)字都是編碼存儲的, ??//?VarintLength方法求出的是編碼后的長度。關(guān)于encoded_len的組成詳見下圖。 ??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)行了簡單的拷貝(考慮的大端或小端)。 ??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); ??//?判斷存儲完后所占內(nèi)存的大小,是否與初始計(jì)算的大小相等 ??assert((p?+?val_size)?-?buf?==?encoded_len); ??//?插入到SkipList中 ??table_.Insert(buf); }
一個完整的buf內(nèi)容如下圖所示。
四.獲取函數(shù)
//?如果能找到key對應(yīng)的value,?將該value存儲到*value參數(shù)中,返回值為true。 //?如果這個key中的有刪除標(biāo)識,存放一個NotFound()錯誤到*status參數(shù)中,返回值為true。 //?否則返回值為false bool?MemTable::Get(const?LookupKey&?key,?std::string*?value,?Status*?s)?{ ??//?得到memkey,memkey中實(shí)際上包含了klength|userkey|tag,也就是說它包含了internal_key_size ??//?和internal_key ??Slice?memkey?=?key.memtable_key(); ??Table::Iterator?iter(&table_); ??//?找到SkipList中大于等于memkey的結(jié)點(diǎn) ??iter.Seek(memkey.data()); ??//?如果找到了這個結(jié)點(diǎn) ??if?(iter.Valid())?{ //?一個結(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是否相等,如果相等,說明找到了這個結(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ù)的第一個參數(shù)是LookupKey類型,LookupKey是一個幫助類,通過它可以更方便的對Memtable進(jìn)行操作。由于LookupKey的官方注釋特別詳細(xì),這里就不分析了。
? ? ?