leveldb 源碼分析 —— SkipList跳表
leveldb 存取數(shù)據(jù)疚漆，都在用 MemTable 這個(gè)結(jié)構(gòu)體木柬，而 MemTable 核心在于 level::MemTable::Table郑藏，也就是 typedef SkipList<const char*, KeyComparator> level::MemTable::Table渗柿。 SkipList 看名字就知道堵第，跳表兆旬，是一種數(shù)據(jù)結(jié)構(gòu)假抄，允許快速查詢一個(gè)有序連續(xù)元素的數(shù)據(jù)鏈表。這是一種 "以空間換取時(shí)間" 的一種做法丽猬，值得注意的是宿饱，這些鏈表都是有序的。
關(guān)于這個(gè)跳表脚祟，我查了一下作者(William Pugh)給出的解析:
Skip lists are a data structure that can be used in place of balanced trees. Skip lists use probabilistic balancing rather than strictly enforced balancing and as a result the algorithms for insertion and deletion in skip lists are much simpler and significantly faster than equivalent algorithms for balanced trees.
跳表是平衡樹的一種替代的數(shù)據(jù)結(jié)構(gòu)谬以，但是和紅黑樹不相同的是，跳表對(duì)于樹的平衡的實(shí)現(xiàn)是基于一種隨機(jī)化的算法的由桌，這樣也就是說跳表的 插入和刪除的工作是比較簡單的为黎。
也就是說核心在于隨機(jī)算法，一個(gè)靠譜的隨機(jī)算法對(duì)跳表是非常重要的行您。
現(xiàn)在我們來一邊用代碼加圖解來分析一下跳表魅力铭乾！
跳表數(shù)據(jù)存儲(chǔ)模型
跳表數(shù)據(jù)結(jié)構(gòu)如下：
template <typename Key, typename Value>
class SkipList {
private:
struct Node; // 聲明節(jié)點(diǎn)結(jié)構(gòu)體
public:
explicit SkipList();
private:
int level_; // 跳表層數(shù)
Node* head_; // 跳表頭部節(jié)點(diǎn)列表
unit32_t rnd_; // 隨機(jī)數(shù)因子
// 生成節(jié)點(diǎn)方法
Node* NewNode(int level, const Key& key, const Value& value);
Node* FindGreaterOrEqual(const Key& key, Node** prev) const;
};
節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)：
template <typename Key, typename Value>
struct SkipList<Key, Value>::Node {
explicit Node(const Key& k, const Value& v) : key(k), value(v) {}
Key key;
Value value;
void SetNext(int i, Node* x);
Node* Next(int i)；
private:
struct Node* forward_[1]; // 節(jié)點(diǎn)數(shù)組列表娃循，這個(gè)比較重要炕檩，后面會(huì)詳細(xì)介紹，如果不理解這個(gè)變量捌斧，就很難理解跳表了
}
通過圖來看一下總體結(jié)構(gòu)
[圖片上傳失敗...(image-c31a3f-1523849207450)]
ps:圖中虛線鏈接表述數(shù)組關(guān)系笛质，實(shí)現(xiàn)標(biāo)識(shí)指針鏈表關(guān)系
上圖假設(shè) level 為 4 等級(jí)的一個(gè)跳表圖，捞蚂，forward_ 變量是一個(gè)指針數(shù)組经瓷，一邊指向下一個(gè)節(jié)點(diǎn)(黑色填充箭頭)的鏈表，一邊又是這些鏈表的數(shù)組(透明填充箭頭)這樣的一個(gè)數(shù)據(jù)結(jié)構(gòu)形成了我們需要的一個(gè)鏈表洞难。
后面我們會(huì)稱為圖中豎向(dowm)節(jié)點(diǎn)為節(jié)點(diǎn)數(shù)組，橫向(left)的節(jié)點(diǎn)為節(jié)點(diǎn)鏈表
初始化跳表
首先為了實(shí)現(xiàn)這個(gè)結(jié)構(gòu)揭朝，我們來初始化跳表
enum {kMaxLevel = 12}; // 這里初始化默認(rèn)跳表最大層數(shù)高度為12
template <typename Key, typename Value>
SkipList<Key, Value>::SkipList() : head_(NewNode( kMaxLevel, 0, 0)), rnd_(0xdeadbeef)
{
// 將 head 節(jié)點(diǎn)數(shù)組全部初始化
for (int i = 0; i < kMaxLevel; ++i) {
head_->SetNext(i, nullptr); // 設(shè)置第 i 層節(jié)點(diǎn)
}
}
現(xiàn)在我們的結(jié)構(gòu)就實(shí)現(xiàn)了下圖的樣子了
[圖片上傳失敗...(image-dee636-1523849207450)]
當(dāng)然队贱，這些節(jié)點(diǎn)都是空的就是了。NewNode 方法查看
插入操作
插入操作分為兩步：
- 查找每層鏈表潭袱，知道找到該插入的位置（因?yàn)橐３钟行虻模?/li>
- 更新節(jié)點(diǎn)指針和跳表高度
第一步：
template <typename Key, typename Value>
typename SkipList<Key, Value>::Node*
SkipList<Key, Value>::FindGreaterOrEqual(const Key& key, Node** prev) const
{
Node* x = head_, *next = nullptr;
int level = level_ - 1;
// 從最高層往下查找需要插入的位置
// 填充 prev柱嫌，prev 為用來記錄每 層（level）跳點(diǎn)的位置
for (int i = level; i >= 0 ; --i) {
while ( (next = x->Next(i)) && next->key < key) {
x = next;
}
if (NULL != prev) {prev[i] = x;}
}
return next; // 返回第 level0 層最合適插入的節(jié)點(diǎn)位置
};
第一步操作如圖3.1 所示， 往這一跳表中插入 key=17 的操作屯换， 可以看出跳表不斷尋找跳點(diǎn)编丘，記錄跳點(diǎn) (紅色框框住的點(diǎn)与学，我們以下稱為跳點(diǎn))，尋找該插入的位置嘉抓，例如 圖3.1中運(yùn)行上面代碼后索守，返回了 next 為 key=12 的節(jié)點(diǎn)，因?yàn)?key=17 大于 12 抑片，小于 19卵佛。
圖 3.1
[圖片上傳失敗...(image-b179bb-1523849207450)]
第二步：
template <typename Key, typename Value>
bool SkipList<Key, Value>::Insert(const Key& key, const Value& value) {
/** 第一步實(shí)現(xiàn)*/
// prev 為用來記錄每 層（level）跳點(diǎn)的位置
Node* prev[kMaxLevel];
// 查找每層鏈表，知道找到該插入的位置（因?yàn)橐３钟行虻模? Node* next = FindGreaterOrEqual(key, prev);
int level;
// 不能插入相同的key
if ( next && next->key == key ) {
return false;
}
/** 第二部實(shí)現(xiàn)敞斋， 第二步實(shí)現(xiàn)后的代碼如圖 3.2*/
// 產(chǎn)生一個(gè)隨機(jī)層數(shù) k
level = randomLevel();
if (level > level_) {
for (int i = level_; i < level; ++i) {
prev[i] = head_; // 新增的層數(shù)初始化
}
level_ = level;
}
// 新建一個(gè)待插入節(jié)點(diǎn) next截汪，
next = NewNode(level, key, value);
// 逐層更新節(jié)點(diǎn)的指針, 一層一層插入
for (int j = 0; j < level; ++j) {
next->SetNext(j, prev[j]->Next(j)); // 該節(jié)點(diǎn)第 levelJ 層的節(jié)點(diǎn)指向 prev （跳點(diǎn)位置）的 levelJ 層鏈表指向的節(jié)點(diǎn)
prev[j]->SetNext(j, next); // 將 pre 跳點(diǎn)第 levelJ 層鏈表指向了 Next 第 levelJ 層的鏈表節(jié)點(diǎn)
}
return true;
}
上述代碼中 randomLevel() 生成的層數(shù)，就作為了跳表的總層數(shù)植捎，同時(shí)衙解，也代表了這個(gè)新增節(jié)點(diǎn)的層數(shù)，例如 圖3.2 中焰枢，節(jié)點(diǎn) key=3蚓峦，高度為1，key=6医咨，高度為4枫匾。
圖 3.2
[圖片上傳失敗...(image-907dc9-1523849207450)]
randomLevel 隨機(jī)層數(shù)生成
setNext 設(shè)置節(jié)點(diǎn)鏈表
查找操作
插入操作中的第一步就是我們的查找操作了，就不做解析了拟淮，直接封裝一層代碼
template <typename Key, typename Value>
Value
SkipList<Key, Value>::Find(const Key &key) {
Node* node = FindGreaterOrEqual(key, NULL);
if (node) {
return node->value;
}
return NULL;
}
刪除操作
在 leveldeb 中干茉，跳表 SkipList 是沒有刪除操作的，leveldb 的跳表只是用來增加節(jié)點(diǎn)個(gè)查詢節(jié)點(diǎn)很泊，如果要?jiǎng)h除某個(gè)節(jié)點(diǎn)角虫，只是將某個(gè)節(jié)點(diǎn)標(biāo)記為刪除，因?yàn)閯h除操作又得重新計(jì)算 level 層數(shù)委造，更新每層的節(jié)點(diǎn)鏈表戳鹅，這樣太耗費(fèi)性能了。
但是我們?cè)谶@里還是實(shí)現(xiàn)一下跳表的刪除操作昏兆，同樣的枫虏，跳表刪除和插入操作相同
- 首先查找到需要?jiǎng)h除的節(jié)點(diǎn)
- 如果找到該節(jié)點(diǎn)，更新指針域爬虱，需要更新 level 的話隶债，逐層更新每個(gè)鏈表
template <typename Key, typename Value>
bool
SkipList<Key, Value>::Delete(const Key&key)
{
Node* prev[kMaxLevel];
Node* next = FindGreaterOrEqual(key, prev);
int level = level_;
if (next && next->key == key) {
// 將每層跳點(diǎn)鏈表設(shè)置到 next 節(jié)點(diǎn)所指向的每層的鏈表
for (int i = 0; i < level; ++i) {
if (prev[i]->Next(i) && prev[i]->Next(i)->key == next->key) {
prev[i]->SetNext(i, next->Next(i));
}
}
// 釋放該節(jié)點(diǎn)數(shù)組的所有內(nèi)存
free(next);
//如果刪除的是最大層的節(jié)點(diǎn)，那么需要重新維護(hù)跳表的
for (int j = level_-1; j >= 0 ; --j) {
if (head_->Next(j) == NULL) {
level_--;
}
}
return true;
}
return false;
};
圖4.1
[圖片上傳失敗...(image-590362-1523849207450)]
如 圖4.1所示跑筝，刪除節(jié)點(diǎn) key=17 時(shí)候的操作死讹，先查找并返回 next 節(jié)點(diǎn)，檢查 next 節(jié)點(diǎn)是否 key=17曲梗，如果是的是赞警，則將逐層的跳點(diǎn)全部更新過來妓忍，并更新層數(shù)。
附屬實(shí)現(xiàn)代碼
生成節(jié)點(diǎn)方法
template <typename Key, typename Value>
typename SkipList<Key, Value>::Node*
SkipList<Key, Value>::NewNode(int level, const Key& key, const Value& value)
{
size_t men = sizeof(Node) + level * sizeof(Node*);
Node* node = (Node*)malloc(men);
node->key = key;
node->value = value;
return node;
}
代碼中 sizeof(Node) 為本身結(jié)構(gòu)體所需要的內(nèi)存分配愧旦，level * sizeof(Node*) 是為 forward_ 數(shù)組分配內(nèi)存世剖，因?yàn)橐?level 個(gè)節(jié)點(diǎn)鏈表。 在 leveldb 中使用了字節(jié)對(duì)齊的方式來分配這塊內(nèi)存忘瓦，我這邊并沒有寫出來搁廓，有興趣的可以瀏覽一下源碼。
我們假設(shè) level = 4
圖 6.1
[圖片上傳失敗...(image-53155-1523849207450)]
代碼生成了圖6.1的結(jié)構(gòu)耕皮，level0 節(jié)點(diǎn)的 forward_ 數(shù)組大小為4境蜕，leve1 ~ level3 都為空節(jié)點(diǎn)，但是分配了 8 個(gè)字節(jié)的指針內(nèi)存 (64位操作系統(tǒng))凌停。圖中虛線為數(shù)組引用表達(dá)粱年，并不是指針指向。
隨機(jī)層數(shù)生成數(shù)方法實(shí)現(xiàn)
取自google開源項(xiàng)目leveldb的實(shí)現(xiàn)
template <typename Key, typename Value>
int SkipList<Key, Value>::randomLevel() {
static const unsigned int kBranching = 4;
int height = 1;
while (height < kMaxLevel && ((::Next(rnd_) % kBranching) == 0)) {
height++;
}
assert(height > 0);
assert(height <= kMaxLevel);
return height;
}
uint32_t Next( uint32_t& seed) {
seed = seed & 0x7fffffffu; // 防止負(fù)數(shù)
if (seed == 0 || seed == 2147483647L) {
seed = 1;
}
static const uint32_t M = 2147483647L; // 2^31-1
static const uint64_t A = 16807; // bits 14, 8, 7, 5, 2, 1, 0
// We are computing
// seed_ = (seed_ * A) % M, where M = 2^31-1
//
// seed_ must not be zero or M, or else all subsequent computed values
// will be zero or M respectively. For all other values, seed_ will end
// up cycling through every number in [1,M-1]
uint64_t product = seed * A;
// Compute (product % M) using the fact that ((x << 31) % M) == x.
seed = static_cast<uint32_t>((product >> 31) + (product & M));
// The first reduction may overflow by 1 bit, so we may need to
// repeat. mod == M is not possible; using > allows the faster
// sign-bit-based test.
if (seed > M) {
seed -= M;
}
return seed;
}
總體來說這個(gè) level 層數(shù)的生成方法也不是隨機(jī)的罚拟，根據(jù) seed 不斷被修改的次數(shù)來決定層數(shù)台诗，換而言之就是 level0 節(jié)點(diǎn)數(shù)量來決定層數(shù)。
有關(guān)節(jié)點(diǎn)結(jié)構(gòu)體的方法實(shí)現(xiàn)
template <typename Key, typename Value>
void
SkipList<Key, Value>::SetNext(int i, Node* x) {
assert(i >= 0);
forward_[i] = x; // 設(shè)置數(shù)組節(jié)點(diǎn)
}
template <typename Key, typename Value>
void
SkipList<Key, Value>::Node* Next(int i) {
assert(i >= 0);
return forward_[i];
}
SetNext(int i, Node* x) 方法是設(shè)置 forward_ 節(jié)點(diǎn)數(shù)組第 i 層(level)的鏈表引用赐俗。
例如圖6.1 中拉队，key=10 調(diào)用了 SetNext(4, Node where key = 20 and level = 4) 和 key=20 調(diào)用了 SetNext(4, Node where key = 40 and level = 4) 的表述。
圖 6.2
[圖片上傳失敗...(image-50d9c4-1523849207450)]
Next(int i) 為取出某層節(jié)點(diǎn)鏈表的方法阻逮，這個(gè)應(yīng)該不應(yīng)解析了吧粱快。
輸出跳表結(jié)構(gòu)
template <typename Key, typename Value>
void
SkipList<Key, Value>::Print()
{
Node* next, *x = head_;
printf("--------\n");
for (int i = level_ - 1; i >= 0; --i) {
x = head_;
while ((next = x->Next(i))) {
x = next;
std::cout << "key: " << next->key << " -> ";
}
printf("\n");
}
printf("--------\n");
}
Print 方法來輸出查看當(dāng)前跳表有哪些節(jié)點(diǎn)結(jié)構(gòu)
