leveldb中數(shù)據(jù)存儲(chǔ)過(guò)程

當(dāng)向leveldb寫入數(shù)據(jù)時(shí)，首先將數(shù)據(jù)寫入log文件，然后在寫入memtable內(nèi)存中。log文件主要是用在當(dāng)斷電時(shí)，內(nèi)存中數(shù)據(jù)會(huì)丟失，數(shù)據(jù)可以從log文件中恢復(fù)。當(dāng)memtable數(shù)據(jù)達(dá)到一定大小，會(huì)變?yōu)?code>immemtable，并自動(dòng)生成新的memtable，然后log文件也生成一個(gè)新的log文件。Immutable Memtable則被新的線程Dump到磁盤中，Dump結(jié)束則該Immutable Memtable就可以釋放了。memtable提供了寫入KV記錄，刪除以及讀取KV記錄的接口，但是事實(shí)上memtable并不執(zhí)行真正的刪除操作,刪除某個(gè)Key的Value在memtable內(nèi)是作為插入一條記錄實(shí)施的，但是會(huì)打上一個(gè)Key的刪除標(biāo)記，真正的刪除操作在后面的 Compaction過(guò)程中(是不是感覺(jué)和前面介紹的skiplist很相似，沒(méi)錯(cuò)，memtable的核心結(jié)構(gòu)就是skiplist)

leveldb 中的 Key

user_key

Slice類，實(shí)質(zhì)上就是一個(gè)string，只不過(guò)稍微封裝了一下

class Slice {
 public:
   //something...和本文關(guān)系不大，不全部貼出來(lái)了
 private:
  const char* data_;
  size_t size_;
};

ParsedInternalKey

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

ParsedInternalKey就是一個(gè)struct，其中SequenceNumber和ValueType定義如下:

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

InternalKey

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) {
    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_;
  }
  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;
};

通過(guò)源碼我們可以看到InternalKey本質(zhì)上也是一個(gè)字符串，這個(gè)字符串是由ParsedInternalKey轉(zhuǎn)換而來(lái)的。下面看看具體的轉(zhuǎn)換函數(shù)

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));
}
static uint64_t PackSequenceAndType(uint64_t seq, ValueType t) {
  assert(seq <= kMaxSequenceNumber);
  assert(t <= kValueTypeForSeek);
  return (seq << 8) | t;
}

實(shí)質(zhì)上就是一個(gè)字符串拼接的過(guò)程。(其中涉及到coding)

根據(jù)這個(gè)我們也能得到InternalKey的組成形式實(shí)際上就是

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

同樣從InternalKey中我們能獲得user_key,操作也十分簡(jiǎn)單

inline Slice ExtractUserKey(const Slice& internal_key) {
  assert(internal_key.size() >= 8);
  return Slice(internal_key.data(), internal_key.size() - 8);
}

從InternalKey中我們能獲得TypeValue:

inline ValueType ExtractValueType(const Slice& internal_key) {
  assert(internal_key.size() >= 8);
  const size_t n = internal_key.size();
  uint64_t num = DecodeFixed64(internal_key.data() + n - 8);
  unsigned char c = num & 0xff;
  return static_cast<ValueType>(c);
}

LookupKey

memtable的查詢接口傳入的就是LookuoKey

bool Get(const LookupKey& key, std::string* value, Status* s);

先看一下LookupKey是怎么定義的

class LookupKey {
 public:
  LookupKey(const Slice& user_key, SequenceNumber sequence);
  ~LookupKey();
  Slice memtable_key() const { return Slice(start_, end_ - start_); }
  Slice internal_key() const { return Slice(kstart_, end_ - kstart_); }
  Slice user_key() const { return Slice(kstart_, end_ - kstart_ - 8); }
 private:
  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&);
};

再看看構(gòu)造函數(shù)

LookupKey::LookupKey(const Slice& user_key, SequenceNumber s) {
  size_t usize = user_key.size();
  size_t needed = usize + 13;  // A conservative estimate
  char* dst;
  if (needed <= sizeof(space_)) {
    dst = space_;
  } else {
    dst = new char[needed];
  }
  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;
}

這樣的話不難分析出，LookupKey的結(jié)構(gòu)如下:

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

這里的size其實(shí)就是user_key的長(zhǎng)度加8.
start_是LookupKey字符串的開(kāi)始，end_是結(jié)束，kstart_是user key字符串的起始地址

======
Key分析完了=。=明天再繼續(xù)分析memtable，啦啦啦啦啦啦啦