leveldb中数据存储过程

当向leveldb写入数据时，首先将数据写入log文件，然后在写入memtable内存中。log文件主要是用在当断电时，内存中数据会丢失，数据可以从log文件中恢复。当memtable数据达到一定大小，会变为immemtable，并自动生成新的memtable，然后log文件也生成一个新的log文件。Immutable Memtable则被新的线程Dump到磁盘中，Dump结束则该Immutable Memtable就可以释放了。memtable提供了写入KV记录，删除以及读取KV记录的接口，但是事实上memtable并不执行真正的删除操作,删除某个Key的Value在memtable内是作为插入一条记录实施的，但是会打上一个Key的删除标记，真正的删除操作在后面的 Compaction过程中(是不是感觉和前面介绍的skiplist很相似，没错，memtable的核心结构就是skiplist)

leveldb 中的 Key

user_key

Slice类，实质上就是一个string，只不过稍微封装了一下

class Slice {
 public:
   //something...和本文关系不大，不全部贴出来了
 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就是一个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;
};

通过源码我们可以看到InternalKey本质上也是一个字符串，这个字符串是由ParsedInternalKey转换而来的。下面看看具体的转换函数

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

实质上就是一个字符串拼接的过程。(其中涉及到coding)

根据这个我们也能得到InternalKey的组成形式实际上就是

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

同样从InternalKey中我们能获得user_key,操作也十分简单

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

再看看构造函数

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的结构如下:

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

这里的size其实就是user_key的长度加8.
start_是LookupKey字符串的开始，end_是结束，kstart_是user key字符串的起始地址

======
Key分析完了=。=明天再继续分析memtable，啦啦啦啦啦啦啦