Google LevelDB 原始碼解說 (三) LevelDB中不同Key的種類

在瀏覽LevelDB的資料時，會看到許多對key結構上的描述，應該有許多人會像我剛開始看時一樣，覺得LevelDB有那麼多種Key?其實這都是層層相關的，從下圖便可以看出其中結構。

User Key

我們先從最底層開始看起，User key就是用戶所傳入的鍵值數據

Slice user_key

ParsedInternalKey&InternalKey

InternalKey是有幾個部分組合成的一個key，ParsedInternalKey就是對InternalKey分拆後的結果，也就是說InternalKey是由User key + SequenceNumber + ValueType組合而成的
InternalKey的格式為： | User key (string) | sequence number (7 bytes) | value type (1 byte) |

// ValueType代表這個數據是要插入還是刪除，0就刪除，1就保留
enum ValueType {
  kTypeDeletion = 0x0,
  kTypeValue = 0x1
};
// kValueTypeForSeek defines the ValueType that should be passed when
// constructing a ParsedInternalKey object for seeking to a particular
// sequence number (since we sort sequence numbers in decreasing order
// and the value type is embedded as the low 8 bits in the sequence
// number in internal keys, we need to use the highest-numbered
// ValueType, not the lowest).
static const ValueType kValueTypeForSeek = kTypeValue;

typedef uint64_t SequenceNumber;

// We leave eight bits empty at the bottom so a type and sequence#
// can be packed together into 64-bits.
// 這裡定義SequenceNum可以取值的範圍[0,2^56-1)
static const SequenceNumber kMaxSequenceNumber =
    ((0x1ull << 56) - 1);
//  ParsedInternalKey則是將InternalKey分拆的結果，由user_key,sequenceNum,type組成
struct ParsedInternalKey {
  Slice user_key;
  SequenceNumber sequence;
  ValueType type;

  ParsedInternalKey() { }  // Intentionally left uninitialized (for speed)
  ParsedInternalKey(const Slice& u, const SequenceNumber& seq, ValueType t)
      : user_key(u), sequence(seq), type(t) { }
  std::string DebugString() const;
};

// Return the length of the encoding of "key".
// 因為InternalKey是user＿Key,sequenceNum,type組成，因為sequenceNum和type共64bit，
// 也就是8bytes，所以長度就是user_key+8
inline size_t InternalKeyEncodingLength(const ParsedInternalKey& key) {
  return key.user_key.size() + 8;
}

LookupKey & Memtable Key

Memtable的查詢接口傳入的是LookupKey，它也是由User Key和Sequence Number組合而成的，從其函數：LookupKey(const Slice& user_key, SequenceNumber s)中分析出LookupKey的格式為

| Size (varint32)| User key (string) | sequence number (7 bytes) | value type (1 byte) |

• start_為字串的開始地址
• end_為字串的結束地址
• kstart_紀錄user_key的起始地址
  *LookupKey的size是變長存儲的，因此它使用kstart_記錄了user key string的起始地址，否則將不能正確的獲取size和user key；

class LookupKey {
 public:
  // Initialize *this for looking up user_key at a snapshot with
  // the specified sequence number.
  LookupKey(const Slice& user_key, SequenceNumber sequence);

  ~LookupKey();

  // Return a key suitable for lookup in a MemTable.
  // 從下方得知LookupKey為 Memtable Key 的 Slice 形式
  Slice memtable_key() const { return Slice(start_, end_ - start_); }

  // Return an internal key (suitable for passing to an internal iterator)
  // 因為internalkey為user_key+sequenceNum+type，所以是 Slice(kstart_, end_-kstart_)
  Slice internal_key() const { return Slice(kstart_, end_ - kstart_); }

  // Return the user key
  // user_key就是再扣掉sequenceNum跟type所以是8
  Slice user_key() const { return Slice(kstart_, end_ - kstart_ - 8); }

 private:
  // We construct a char array of the form:
  //    klength  varint32               <-- start_
  //    userkey  char[klength]          <-- kstart_
  //    tag      uint64
  //                                    <-- end_
  // The array is a suitable MemTable key.
  // The suffix starting with "userkey" can be used as an InternalKey.
  const char* start_;
  const char* kstart_;
  const char* end_;

下方為LookupKey的實作

LookupKey::LookupKey(const Slice& user_key, SequenceNumber s) {
  size_t usize = user_key.size();// user_key長度
  size_t needed = usize + 13;  // A conservative estimate
                               // +13是 sequenceNum+type=8 和 varint32最大為5bytes

  char* dst;
  if (needed <= sizeof(space_)) {
    dst = space_;
  } else {
    dst = new char[needed];//若超過預留得space_就要重新分配
  }
  //下方為計算start_,kstart_,end_的實作
  start_ = dst;
  dst = EncodeVarint32(dst, usize + 8);
  kstart_ = dst;
  memcpy(dst, user_key.data(), usize);
  dst += usize;
  EncodeFixed64(dst, PackSequenceAndType(s, kValueTypeForSeek));
  dst += 8;
  end_ = dst;
}