leveldb_memtable.md

LevelDB memtable

• Put operation is wrapped with WriteBatch(code)

Status DB::Put(const WriteOptions& opt, const Slice& key, const Slice& value) {
  WriteBatch batch;
  batch.Put(key, value);
  return Write(opt, &batch);
}

• Here is the definition of WriteBatch

// WriteBatch::rep_ :=
//    sequence: fixed64
//    count: fixed32        [Perry] WriteBatch could contains multiple records
//    data: record[count]
// record :=
//    kTypeValue varstring varstring         |
//    kTypeDeletion varstring    [Perry] No value size and value for delete
// varstring :=
//    len: varint32
//    data: uint8[len]

Let's say we want to write <key= TestKey, Value=TestValue>, here is the sample of WriteBatch:

It will be wrapped as a Writer and then insert into a deque

  Writer w(&mutex_);
  w.batch = updates;
  w.sync = options.sync;
  w.done = false;

Writer need to write two part of information, one is WAL on disk, in case of failure

      status = log_->AddRecord(WriteBatchInternal::Contents(write_batch));

Another part is add <key,value> pair into memory table(code)

-> WriteBatchInternal::InsertInto(write_batch, mem_);

WriteBatchInternal::InsertInto

Status WriteBatchInternal::InsertInto(const WriteBatch* b, MemTable* memtable) {
  MemTableInserter inserter;
  inserter.sequence_ = WriteBatchInternal::Sequence(b);
  inserter.mem_ = memtable;
  return b->Iterate(&inserter);
}

// Perry: Inside Iterate, it will call inserter's put to put key value
Status WriteBatch::Iterate(Handler* handler) const {
}

// Calling memtable's add 
class MemTableInserter : public WriteBatch::Handler {
  void Put(const Slice& key, const Slice& value) override {
    mem_->Add(sequence_, kTypeValue, key, value);
    sequence_++;
  }
}

Finally, come to call memtable's Add() and then insert <key, value> into skiplist

void MemTable::Add(SequenceNumber s, ValueType type, const Slice& key,
{
    // typedef SkipList<const char*, KeyComparator> Table;
    table_.Insert(buf);

}

For more information about skiplist, please go to here, a great example about how to test current reading for skiplist can be found here