levelDBソース分析-Memtable
このセクションでは、メモリ中のLevelDBのデータ構造Memtableについて述べ、Memtableが全体のシステムの中で重要な地位を占めていることは言うまでもない.全体として、すべてのKVデータはMemtable、Immutable MemtableとSSTableに格納されています.Immutable Memtableは構造的にはMemtableと全く同じです.違いは読み取り専用のもので、書き込み操作が禁止されています.Memtableは書き込みと読み取りが許可されています.Memtableに書き込まれたデータが指定数に達すると自動的にImmutable Memtableに変換され、Dumpがディスクに入るのを待つと、システムが自動的に新しいMemtableを作成して書き込み操作を行い、Memtableを理解すると、Immutable Memtableは自然に話をしません. LevelDbのMemTableはKVデータを書き込み、削除及びKV記録を読み取るための操作インターフェースを提供していますが、実際にはMemtableには本当の削除操作は存在しません.あるKeyを削除するValueはMemtable内に挿入として実施していますが、Keyの削除マークを付けます.本当に削除操作はLazyです.今後のコミケでこのKVを外します. LevelDbのMemtableのKVペアはKeyサイズに基づいて規則的に保存されています.システムが新しいKVを挿入する時、LevelDbはこのKVを適切な位置に挿入してこのKey秩序を維持します.実は、LevelDbのMemtable類は一つのインターフェース類にすぎません.本当の操作は後ろのSkipListによって作られます.挿入操作と読み取り操作などを含めて、Memtableのコアデータ構造はSkipListです. SkipListはWilliam Pughによって発明された.彼はCommunications of the ACM June 1990、33(6)668-676にSkip listsを発表しました.a probabilistic alternative to balanced treesはこの論文でスキプリストのデータ構造と挿入削除操作を詳しく説明しました. SkipListは、平衡ツリーの代替データ構造であるが、赤と黒の木とは違って、SkipListはツリーのバランスの実現に臨機化アルゴリズムに基づいており、このようにSkipListの挿入と削除の作業は比較的簡単である. スキップリストの詳細については、「levelDBソース分析-スキplist」または「Skiplist」を参照してください.http://www.cnblogs.com/xuqiang/archive/2011/05/22/2053516.htmlはっきりと述べましたが、LevelDbのSkipListは基本的に具体的な実現であり、特別なところはありません.SkipListは、秩序あるデータを維持するための単純な実現だけでなく、バランスツリーと比較して、データを挿入する際に頻繁なツリーノード調整操作を回避できるので、書き込み効率が高く、LevelDb全体としては高い書き込みシステムであり、SkipListもその中で重要な役割を果たしているはずです.Redisは挿入動作を加速させるために、SkipListを使って内部としてデータ構造を実現しています. MemTableの定義と紹介を紹介します.
MemTableは参照カウントに基づいており、使うたびにまずRef()を呼び出し、使用が終わるとUref()を呼び出す.
SkiplistのNodeのデータは、InternalKey+Value-size+Value-dataです.
MemTableは参照カウントに基づいており、使うたびにまずRef()を呼び出し、使用が終わるとUref()を呼び出す.
class MemTable {
public:
// MemTables are reference counted. The initial reference count
// is zero and the caller must call Ref() at least once.
explicit MemTable(const InternalKeyComparator& comparator); // ， comparator（ ）
// Increase reference count.
void Ref() { ++refs_; } //
// Drop reference count. Delete if no more references exist.
void Unref() { //
--refs_;
assert(refs_ >= 0);
if (refs_ <= 0) {
delete this;
}
}
// Returns an estimate of the number of bytes of data in use by this
// data structure.
//
// REQUIRES: external synchronization to prevent simultaneous
// operations on the same MemTable.
size_t ApproximateMemoryUsage(); //
// Return an iterator that yields the contents of the memtable.
//
// The caller must ensure that the underlying MemTable remains live
// while the returned iterator is live. The keys returned by this
// iterator are internal keys encoded by AppendInternalKey in the
// db/format.{h,cc} module.
Iterator* NewIterator(); //
// Add an entry into memtable that maps key to value at the
// specified sequence number and with the specified type.
// Typically value will be empty if type==kTypeDeletion.
void Add(SequenceNumber seq, ValueType type, // key/value MemTable
const Slice& key, // type=kTypeDeletion ，value
const Slice& value);
// If memtable contains a value for key, store it in *value and return true.
// If memtable contains a deletion for key, store a NotFound() error
// in *status and return true.
// Else, return false.
bool Get(const LookupKey& key, std::string* value, Status* s); //
private:
~MemTable(); // Private since only Unref() should be used to delete it // ， private，
struct KeyComparator {
const InternalKeyComparator comparator;
explicit KeyComparator(const InternalKeyComparator& c) : comparator(c) { }
int operator()(const char* a, const char* b) const;
};
friend class MemTableIterator;
friend class MemTableBackwardIterator;
typedef SkipList<const char*, KeyComparator> Table;
Table table_; // Skiplist
KeyComparator comparator_; // comparator_
Arena arena_; //
int refs_; //
// No copying allowed
MemTable(const MemTable&); //
void operator=(const MemTable&);
};
// Modules in this directory should keep internal keys wrapped inside
// the following class instead of plain strings so that we do not
// incorrectly use string comparisons instead of an InternalKeyComparator.
class InternalKey { // Key
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()); } // string
Slice Encode() const { // string
assert(!rep_.empty());
return rep_;
}
Slice user_key() const { return ExtractUserKey(rep_); } // User Key
void SetFrom(const ParsedInternalKey& p) {
rep_.clear();
AppendInternalKey(&rep_, p);
}
void Clear() { rep_.clear(); }
std::string DebugString() const;
};
struct ParsedInternalKey { // InternalKey :
Slice user_key; //+ user key
SequenceNumber sequence; //+ sequence
ValueType type; //+ type: kTypeDeletion or kTypeValue
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;
};
// Returns the user key portion of an internal key.
inline Slice ExtractUserKey(const Slice& internal_key) { // User Key
assert(internal_key.size() >= 8);
return Slice(internal_key.data(), internal_key.size() - 8);
}
inline ValueType ExtractValueType(const Slice& internal_key) { // Type
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);
}
void AppendInternalKey(std::string* result, const ParsedInternalKey& key) { // InternalKey string
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) { // sequence | type
assert(seq <= kMaxSequenceNumber);
assert(t <= kValueTypeForSeek);
return (seq << 8) | t;
}
// A comparator for internal keys that uses a specified comparator for
// the user key portion and breaks ties by decreasing sequence number.
class InternalKeyComparator : public Comparator {
private:
const Comparator* user_comparator_;
public:
explicit InternalKeyComparator(const Comparator* c) : user_comparator_(c) { }
virtual const char* Name() const;
virtual int Compare(const Slice& a, const Slice& b) const;
virtual void FindShortestSeparator(std::string* start,
const Slice& limit) const;
virtual void FindShortSuccessor(std::string* key) const;
const Comparator* user_comparator() const { return user_comparator_; }
int Compare(const InternalKey& a, const InternalKey& b) const;
};
inline int InternalKeyComparator::Compare(const InternalKey& a, const InternalKey& b) const {
return Compare(a.Encode(), b.Encode()); // Encode string， string
}
int InternalKeyComparator::Compare(const Slice& akey, const Slice& bkey) const {
// Order by:
// increasing user key (according to user-supplied comparator)
// decreasing sequence number
// decreasing type (though sequence# should be enough to disambiguate)
int r = user_comparator_->Compare(ExtractUserKey(akey), ExtractUserKey(bkey));
if (r == 0) {
const uint64_t anum = DecodeFixed64(akey.data() + akey.size() - 8);
const uint64_t bnum = DecodeFixed64(bkey.data() + bkey.size() - 8);
if (anum > bnum) {
r = -1;
} else if (anum < bnum) {
r = +1;
}
}
return r;
}
inline bool ParseInternalKey(const Slice& internal_key, // InternalKey
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; // type：1 byte
result->sequence = num >> 8; // 8 ， 1 type， sequence
result->type = static_cast<ValueType>(c);
result->user_key = Slice(internal_key.data(), n - 8); // User Key
return (c <= static_cast<unsigned char>(kTypeValue)); // ：type
}
// A helper class useful for DBImpl::Get()
class LookupKey { // 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();
// 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); }
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
// No copying allowed
LookupKey(const LookupKey&);
void operator=(const LookupKey&);
};
inline LookupKey::~LookupKey() {
if (start_ != space_) delete[] start_;
}
：
class MemTableInserter : public WriteBatch::Handler { // MemTableInserter Memtable
public:
SequenceNumber sequence_;
MemTable* mem_;
virtual void Put(const Slice& key, const Slice& value) { //
mem_->Add(sequence_, kTypeValue, key, value);
sequence_++;
}
virtual void Delete(const Slice& key) { //
mem_->Add(sequence_, kTypeDeletion, key, Slice());
sequence_++;
}
};
Status WriteBatchInternal::InsertInto(const WriteBatch* b, MemTable* memtable) { //
MemTableInserter inserter;
inserter.sequence_ = WriteBatchInternal::Sequence(b);
inserter.mem_ = memtable;
return b->Iterate(&inserter);
}
SkiplistのNodeのデータは、InternalKey+Value-size+Value-dataです.