Let’s take a look at how Memtable organizes and stores data.

1. Key structure

Memtable is a KV storage structure, so this key is a key, we need to carefully analyze the use of Memtable on key. LevelDB has 5 keys in LevelDB, so it’s very confusing.

1.1) InternalKey & ParsedInternalKey & User Key

InternalKey is a compound concept, a key that has several parts combined. ParsedInternalKey is the result of splitting InternalKey. Let’s look at the definition of ParsedInternalKey, which is a struct:

struct ParsedInternalKey {
  Slice user_key;
  SequenceNumber sequence;
  ValueType type;
};
Copy the code

That is, InternalKey is a combination of User key, SequenceNumber, and ValueType. InternalKey and User Key. InternalKey and User Key. InternalKey and User Key

ParsedInternalKey(const Slice& u, const SequenceNumber& seq, ValueType t)
      : user_key(u), sequence(seq), type(t) {}


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));
}
Copy the code

Function implementation is very simple, is the string concatenation and the string by byte split. According to the implementation, it is easy to obtain InternalKey in the format:

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

The sequence number is 7 bytes. The sequence number is all the key data based on the operation log system. It uniquely specifies the time sequence of different operations.

The User Key is the original input Key. The reason for putting the User Key in front is that operations on the same User Key can be consecutively stored in sequence number order. Different User keys are irrelevant to each other, so it is meaningless to put them together. In addition, users can customize the comparison function for the User Key, which is alphabetical by default.

The following two functions separate the User Key and Value Type from InternalKey:

Code:

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


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);
}
Copy the code

In SkipList, each Node stored in the Memtabl SkipList is a key-value in the following format:

internal_key_size|internal_key|val_size|value
Copy the code

And key is an internal_key. 1.2 ) LookupKey & Memtable Key

The Memtable query interface passes LookupKey, which is also a combination of User Key and Sequence Number. The data structure is as follows:

class 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. const char* start_; const char* kstart_; const char* end_; char space_[200]; // Avoid allocation for short keys };Copy the code

The constructor LookupKey(const Slice& user_key, SequenceNumber s) is in the following format:

Explain three things:

1) Here klength is the user key length +8, that is, the entire LoopupKey string length.

2) Value type is kValueTypeForSeek, which is equal to kTypeValue.

static const ValueType kValueTypeForSeek = kTypeValue;
Copy the code

3) Since LookupKey size is stored with variable length, it uses kstart_ to record the start address of the user key string. Otherwise, size and user keys will not be retrieved correctly.

LookupKey exports three functions to get Internal Key, Memtable Key, and User Key from LookupKey, as follows:

  // Return a key suitable for lookup in a MemTable.
  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); }
Copy the code

Start_ is the start of the LookupKey string, end_ is the end, and kstart_ is start_+4, which is the start address of the user key string.

Memtable_key () indicates that MemtableKey is a LookupKey, that is, MemtableKey == LookupKey, not internalKey, klength+internalKey.

InternalKey is: | user key (string) | sequence number value type (7 bytes) | | (1 byte)

2, Memtable:

MemTable is an in-memory data structure that can be used to organize and maintain data in LevelDB. It is essentially a SkipList table, and most of the time is O(log n), which meets LevelDB’s requirements for fast Key lookup. In MemTable, all data is sorted according to user-defined sorting method and then stored in order. Its data structure is as follows:

class MemTable {
  typedef SkipList<const char*, KeyComparator> Table;
  KeyComparator comparator_;
  int refs_;
  Arena arena_;
  Table table_;
};
Copy the code

Table is the SkipList object, and Arena is the Memtable memory allocator, which allocates and frees memory by inserting and deleting elements into the SkipList.