LevelDB源码分析——5.不同的主键Key类型

五.不同的主键Key类型

本系列的前两篇介绍了LevelDB高性能写操作的核心：日志与内存数据库。

在阅读LevelDB的源码时，往往能看到这样的参数传递：Slice key ,const char* key,Key key等等

他们都有相同的参数名，但有时代表的key却不一定相同。

在skiplist.h中, 能看到

void Insert(const Key& key); 

在memtable.h中，能看到

void Add(SequenceNumber seq,ValueType type, const Slice& key, const Slice& value); 

在block_builder.h中，能看到

void Add(const Slice& key,const Slice& value); 

在table_builder.h中，能看到

void Add(const Slice& key,const Slice& value); 

实际上，LevelDB中一共有五种key的概念，分别是UserKey、InternalKey、ParsedInternalKey、LookupKey、MemtableKey。

其中用户输入的key即为UserKey，在各个函数的传递过程中，经过各种各样的处理，很难弄清楚现在拿到的key是什么。通过梳理sstable的插入和查询过程中，key的变化过程，分析清楚各种key的作用。

UserKey

从最简单的入手，我们先弄清楚UserKey

前面已经提到过用户输入的key即为UserKey，例如，用户输入k/v对，key1:value1 ,则key1即为UserKey ，在leveldb中，是以Slice类型传入

Slice user_key;

InternalKey

InternalKey是将user_key按一定规则编码后得到的字符串

• Seq用于表示记录插入的顺序
• Type用于表示记录的类型，目前取值只有两种kTypeDeletion表示记录被删除，kTypeValue表示记录有效

enum ValueType { kTypeDeletion = 0x0, kTypeValue = 0x1 }; 

Seq占7B，Type占1B通过下面的函数打包

static uint64_t PackSequenceAndType(uint64_t seq, ValueType t) {    
	assert(seq <= kMaxSequenceNumber);    
	assert(t <= kValueTypeForSeek);    
	return (seq << 8) | t; 
	} 

打包后拼接到user_key_bytes后面即构成了InternalKey

ParsedInternalKey

ParsedInternalKey将字符串InternalKey解析为一个结构体

struct ParsedInternalKey {    
	Slice user_key;    
	SequenceNumber sequence{};    
	ValueType type;     
	ParsedInternalKey() = default;  // Intentionally left uninitialized (for speed)    

ParsedInternalKey(const Slice& u, const SequenceNumber& seq, ValueType t)  : user_key(u), sequence(seq), type(t) {} }; 

补上了ParsedInternalKey的概念后，就能看懂InternalKey的所有代码了

void AppendInternalKey(std::string *result, const ParsedInternalKey &key) {    
	result->append(key.user_key.data(), key.user_key.size());    
	PutFixed64(result, PackSequenceAndType(key.sequence, key.type)); 
} 

class InternalKey { 
	private:    
		std::string rep_; 
	public:    
		InternalKey() = default;  // Leave rep_ as empty to indicate it is invalid    
		InternalKey(const Slice& user_key, SequenceNumber s, ValueType t) {        
			AppendInternalKey(&rep_, ParsedInternalKey(user_key, s, t));    
		}     
		bool DecodeFrom(const Slice& s) {        
			rep_.assign(s.data(), s.size());        
			return !rep_.empty();    
		}     
		Slice Encode() const {        
			assert(!rep_.empty());        
			return rep_;    
		}     
		Slice user_key() const { 
			return ExtractUserKey(rep_); 
		}     
		void SetFrom(const ParsedInternalKey& p) {        
			rep_.clear();        
			AppendInternalKey(&rep_, p);    
		}    
		void Clear() { rep_.clear(); } }; 

LookupKey&&MemtableKey

下面是源码中给出的注释

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()]  ...... } 

我们可以看到：在InternalKey的头部拼接上InternalKey的长度，即构成MemtableKey。

LookupKey和MemtableKey格式一致，用于查找。