LevelDB源碼閱讀-key

levelDB中的key

前言

在

levelDB

中有五種不同的

key

，在正式分析

memtable

之前我們先介紹一下這5中不同的

key

• user_key
• ParsedInternalKey
• InternalKey
• LookupKey
• MemtableKey

user_key（使用者key）

user_key

是

Slice

結構體來表示的，其内部就是簡單封裝了字元串和它的

size

。

顧名思義，這個

key

就是用來儲存使用者輸入的真實

key

值。

class LEVELDB_EXPORT Slice {
//...
 private:
  const char* data_;
  size_t size_;
};
           

ParsedInternalKey

ParseInternalKey

和

InternalKey

是有所關聯的，

ParsedInternalKey

是解析後的

InternalKey

。

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;
};
           

解析

internal_key

的函數，實作

internal_key

到

ParseInternalKey

的轉換

inline bool ParseInternalKey(const Slice& internal_key,
                             ParsedInternalKey* result) {
  const size_t n = internal_key.size();
  if (n < 8) return false;
  uint64_t num = DecodeFixed64(internal_key.data() + n - 8);
  unsigned char c = num & 0xff;
  //分别得到sequence type 和user_key
  result->sequence = num >> 8;
  result->type = static_cast<ValueType>(c);
  result->user_key = Slice(internal_key.data(), n - 8);
  return (c <= static_cast<unsigned char>(kTypeValue));
}
           

InternalKey（内部key）

class InternalKey {
 private:
   //私有成員,就是一個簡單的字元串
  std::string rep_;
 public:
  //構造函數
  InternalKey() { }   // Leave rep_ as empty to indicate it is invalid
  InternalKey(const Slice& user_key, SequenceNumber s, ValueType t) {
    //構造一個内部key
    AppendInternalKey(&rep_, ParsedInternalKey(user_key, s, t));
  }

  void DecodeFrom(const Slice& s) { rep_.assign(s.data(), s.size()); }
  Slice Encode() const {
    assert(!rep_.empty());
    return rep_;
  }
  //傳回user_key
  Slice user_key() const { return ExtractUserKey(rep_); }

  void SetFrom(const ParsedInternalKey& p) {
    rep_.clear();
    AppendInternalKey(&rep_, p);
  }

  void Clear() { rep_.clear(); }

  std::string DebugString() const;
};
           

從源碼可以看出，

InternalKey

的内部組成（rep_）格式為

（當插入資料時,

SequenceNumber

會依次增長）

|user_key|SequenceNumber|ValueType|
           

LookupKey / MemtableKey

LookupKey

的内部組成為

| Size (int32變長)| User key (string) | sequence number (7 bytes) | value type (1 byte) |
           

維護了3個指針，如圖：

内部成員函數

可以調用以下幾個成員函數，傳回不同類型的

key

，之前已經介紹過了

internal_key

和

user_key

，以下代碼的邏輯很簡單。

// Return a key suitable for lookup in a MemTable.
  //傳回适合在MemTable中進行查找的key。
  Slice memtable_key() const { return Slice(start_, end_ - start_); }

  // Return an internal key (suitable for passing to an internal iterator)
  Slice internal_key() const { return Slice(kstart_, end_ - kstart_); }

  // Return the user key
  Slice user_key() const { return Slice(kstart_, end_ - kstart_ - 8); }
           

LookupKey

的結構源碼

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();
  //...

 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.
  //内部維護了3個指針
  const char* start_;
  const char* kstart_;
  const char* end_;
  char space_[200];      // Avoid allocation for short keys

  // No copying allowed
  LookupKey(const LookupKey&);
  void operator=(const LookupKey&);
};
           

構造函數

LookupKey::LookupKey(const Slice& user_key, SequenceNumber s) {
  size_t usize = user_key.size();
  size_t needed = usize + 13;  // A conservative estimate
  char* dst;
  //如果需求量小于space的大小，則直接指向space
  if (needed <= sizeof(space_)) {
    dst = space_;
  } else {
  //否則新開辟一段空間來滿足需求
    dst = new char[needed];
  }
  //start_指向起始位置
  start_ = dst;
  dst = EncodeVarint32(dst, usize + 8);
  //kstart指向user_key開始的位置
  kstart_ = dst;
  memcpy(dst, user_key.data(), usize);
  dst += usize;
  EncodeFixed64(dst, PackSequenceAndType(s, kValueTypeForSeek));
  dst += 8;
  //end_指向結束的位置
  end_ = dst;
}
           

總結

以上介紹了在

levelDB

中出現的所有

key

，在不同的地方由他們不同的用處，我們可以看到

lookup_key

是比較通用的一種，可以調用其内部的成員函數傳回其他類型的

key

。接下來我們正式分析

memtable