5.1 基本原理
SkipList稱之為跳表鄙煤，可實(shí)現(xiàn)Log(n)級別的插入、刪除啦桌。跳表是平衡樹的一種替代方案，和平衡樹不同的是歼培，跳表并不保證嚴(yán)格的“平衡性”震蒋，而是采用更為隨性的方法：隨機(jī)平衡算法。
關(guān)于SkipList的完整介紹請參見跳表(SkipList)躲庄，這里借用幾幅圖做簡要說明：
- 圖1.1中紅色部分為初始化狀態(tài)查剖，即head各個(gè)level中next節(jié)點(diǎn)均為NULL。
- 跳表是分層的噪窘，由下往上分別為1笋庄、2、3...倔监，因此需要分層算法直砂。
- 跳表中每一層的數(shù)據(jù)都是按順序存儲的浩习，因此需要Compactor静暂。
- 查找動(dòng)作由最上層開始依序查找，直到找到數(shù)據(jù)或查找失敗谱秽。
- 插入動(dòng)作僅影響插入位置前后節(jié)點(diǎn)洽蛀，對其他節(jié)點(diǎn)無影響。
- 刪除動(dòng)作僅影響插入位置前后節(jié)點(diǎn)郊供，對其他節(jié)點(diǎn)無影響。
5.2 分層算法
分層算法決定了數(shù)據(jù)插入的Level近哟，SkipList的平衡性如何全權(quán)由分層算法決定驮审。極端情況下，假設(shè)SkipList只有Level-0層吉执，SkipList將弱化成自排序List疯淫。此時(shí)查找、插入戳玫、刪除的時(shí)間復(fù)雜度均為O(n)峡竣，而非O(Log(n))。
LevelDB中的分層算法實(shí)現(xiàn)如下(leveldb::skiplist::RandomHeight())
// enum { kMaxHeight = 12 };
template<typename Key, class Comparator>
int SkipList<Key, Comparator>::RandomHeight()
{
// Increase height with probability 1 in kBranching
static const unsigned int kBranching = 4;
int height = 1;
while (height < kMaxHeight && ((rnd_.Next() % kBranching) == 0)) {
height++;
}
assert(height > 0);
assert(height <= kMaxHeight);
return height;
}
kMaxHeight 代表Skiplist的最大高度量九，即最多允許存在多少層，為關(guān)鍵參數(shù)，與性能直接相關(guān)荠列。修改kMaxHeight 类浪，在數(shù)值變小時(shí)，性能上有明顯下降肌似，但當(dāng)數(shù)值增大時(shí)费就，甚至增大到10000時(shí)，和默認(rèn)的kMaxHeight =12相比仍舊無明顯差異川队，內(nèi)存使用上也是如此力细。
為何如此？關(guān)鍵在于while循環(huán)中的判定條件：height < kMaxHeight && ((rnd_.Next() % kBranching) == 0)固额。除了kMaxHeight 判定外眠蚂，(rnd_.Next() % kBranching) == 0)判定使得上層節(jié)點(diǎn)的數(shù)量約為下層的1/4。那么斗躏，當(dāng)設(shè)定MaxHeight=12時(shí)逝慧，根節(jié)點(diǎn)為1時(shí)，約可均勻容納Key的數(shù)量為4^11=4194304(約為400W)啄糙。因此笛臣，當(dāng)單獨(dú)增大MaxHeight時(shí)，并不會使得SkipList的層級提升隧饼。MaxHeight=12為經(jīng)驗(yàn)值沈堡，在百萬數(shù)據(jù)規(guī)模時(shí)，尤為適用燕雁。
5.3 比較器(Compactor)
如同二叉樹诞丽，Skiplist也是有序的，鍵值比較需由比較器(Compactor)完成贵白。SkipList對Compactor的要求只有一點(diǎn)：()操作符重載率拒，格式如下：
//a<b返回值小于0，a>b返回值大于0禁荒，a==b返回值為0
int operator()(const Key& a, const Key& b) const;
SkipList定義中猬膨，Key與Compactor均為模板參數(shù)，因而Compactor亦由使用者實(shí)現(xiàn)呛伴。
template <typename Key, class Comparator>
class SkipList
{
....
}
LevelDB中存在一個(gè)Compactor抽象類勃痴，但該抽象類并沒有重載()操作符，至于Compacotr如何使用及Compactor抽象類和此處的Compactor的關(guān)系如何請參見MemTable一節(jié)热康。
5.4 查找沛申、插入、刪除
LevelDB中實(shí)現(xiàn)的SkipList并無刪除行為姐军，這由其業(yè)務(wù)特性決定铁材，故此處不提尖淘。
查找、插入亦即讀著觉、寫行為村生。由圖1.2可知，插入首先需完成一次查找動(dòng)作饼丘，隨后在指定位置上完成一次插入行為趁桃。
5.4.1 查找
LevelDB中的查找、插入行為幾乎做到了“無鎖”并發(fā)肄鸽，這一點(diǎn)是非澄啦。可取的。關(guān)于這一點(diǎn)典徘，是本次備忘的重點(diǎn)蟀苛。先來看查找：
template<typename Key, class Comparator>
typename SkipList<Key, Comparator>::Node*
SkipList<Key, Comparator>::FindGreaterOrEqual(const Key& key, Node** prev) const
{
Node* x = head_;
int level = GetMaxHeight() - 1;
while (true) {
Node* next = x->Next(level);
if (KeyIsAfterNode(key, next)) {
// Keep searching in this list
x = next;
}
else {
if (prev != NULL) prev[level] = x;
if (level == 0) {
return next;
}
else {
// Switch to next list
level--;
}
}
}
}
實(shí)現(xiàn)并無特別之處：由最上層開始查找，一直查找到Level-0烂斋。找到大于等于指定Key值的數(shù)據(jù)屹逛，如不存在返回NULL。來看SkipList的Node結(jié)構(gòu)：
template<typename Key, class Comparator>
struct SkipList<Key, Comparator>::Node {
explicit Node(const Key& k) : key(k) { }
Key const key;
// Accessors/mutators for links. Wrapped in methods so we can
// add the appropriate barriers as necessary.
Node* Next(int n) {
assert(n >= 0);
// Use an 'acquire load' so that we observe a fully initialized
// version of the returned Node.
return reinterpret_cast<Node*>(next_[n].Acquire_Load());
}
void SetNext(int n, Node* x) {
assert(n >= 0);
// Use a 'release store' so that anybody who reads through this
// pointer observes a fully initialized version of the inserted node.
next_[n].Release_Store(x);
}
// No-barrier variants that can be safely used in a few locations.
Node* NoBarrier_Next(int n) {
assert(n >= 0);
return reinterpret_cast<Node*>(next_[n].NoBarrier_Load());
}
void NoBarrier_SetNext(int n, Node* x) {
assert(n >= 0);
next_[n].NoBarrier_Store(x);
}
private:
// Array of length equal to the node height. next_[0] is lowest level link.
port::AtomicPointer next_[1]; //看NewNode代碼汛骂，實(shí)際大小為node height
};
Node有兩個(gè)成員變量罕模，Key及next_數(shù)組。Key當(dāng)然是節(jié)點(diǎn)數(shù)據(jù)帘瞭，next_數(shù)組(注意其類型為AtomicPointer )則指向了其所在層及之下各個(gè)層中的下一個(gè)節(jié)點(diǎn)(參見圖1.1)淑掌。Next_數(shù)組的實(shí)際大小和該節(jié)點(diǎn)的height一致，來看Node的工廠方法NewNode:
template<typename Key, class Comparator>
typename SkipList<Key, Comparator>::Node*
SkipList<Key, Comparator>::NewNode(const Key& key, int height)
{
//此處分別的為對象體蝶念，需要邊界對齊
char* mem = arena_->AllocateAligned( sizeof(Node) +
sizeof(port::AtomicPointer) * (height - 1));
//c++ placement顯示調(diào)用構(gòu)造函數(shù)抛腕，并不常見。
return new (mem) Node(key);
}
Node的兩組方法：SetNext/Next媒殉、NoBarrier_SetNext/NoBarrier_Next担敌，用于讀寫指定層的下一節(jié)點(diǎn)指針，前者并發(fā)安全廷蓉、后者非并發(fā)安全全封。
5.4.2 插入
template<typename Key, class Comparator>
void SkipList<Key, Comparator>::Insert(const Key& key)
{
// TODO(opt): We can use a barrier-free variant of FindGreaterOrEqual()
// here since Insert() is externally synchronized.
Node* prev[kMaxHeight];
Node* x = FindGreaterOrEqual(key, prev);
// Our data structure does not allow duplicate insertion
assert(x == NULL || !Equal(key, x->key));
int height = RandomHeight();
if (height > GetMaxHeight())
{
for (int i = GetMaxHeight(); i < height; i++) {
prev[i] = head_;
}
//fprintf(stderr, "Change height from %d to %d\n", max_height_, height);
// It is ok to mutate max_height_ without any synchronization
// with concurrent readers. A concurrent reader that observes
// the new value of max_height_ will see either the old value of
// new level pointers from head_ (NULL), or a new value set in
// the loop below. In the former case the reader will
// immediately drop to the next level since NULL sorts after all
// keys. In the latter case the reader will use the new node.
max_height_.NoBarrier_Store(reinterpret_cast<void*>(height));
}
x = NewNode(key, height);
for (int i = 0; i < height; i++) {
// NoBarrier_SetNext() suffices since we will add a barrier when
// we publish a pointer to "x" in prev[i].
x->NoBarrier_SetNext(i, prev[i]->NoBarrier_Next(i));
prev[i]->SetNext(i, x);
}
}
插入行為主要修改兩類數(shù)據(jù)：max_height_及所有l(wèi)evel中前一節(jié)點(diǎn)的next指針。
max_height_沒有任何并發(fā)保護(hù)桃犬，關(guān)于此處作者注釋講的很清楚：
讀線程在讀到新的max_height_同時(shí)刹悴，對應(yīng)的層級指針(new level pointer from head_)可能是原有的NULL，也有可能是部分更新的層級指針攒暇。如果是前者將直接跳到下一level繼續(xù)查找土匀，如果是后者，新插入的節(jié)點(diǎn)將被啟用形用。
隨后節(jié)點(diǎn)插入方是將無鎖并發(fā)變?yōu)楝F(xiàn)實(shí)：
- 首先更新插入節(jié)點(diǎn)的next指針就轧，此處無并發(fā)問題证杭。
- 修改插入位置前一節(jié)點(diǎn)的next指針，此處采用SetNext處理并發(fā)钓丰。
- 由最下層向上插入可以保證當(dāng)前層一旦插入后躯砰，其下層已更新完畢并可用。
當(dāng)然携丁，多個(gè)寫之間的并發(fā)SkipList時(shí)非線程安全的，在LevelDB的MemTable中采用了另外的技巧來處理寫并發(fā)問題兰怠。
5.5 總結(jié)
SkipList的功能定位和B-Tree類似梦鉴，但實(shí)現(xiàn)更簡單。LevelDB選用SkipList一來和SkipList的高效揭保、簡潔相關(guān)肥橙，二來SkipList也僅存在MemTable一種簡單應(yīng)用場景。下一節(jié)侣滩，讓我們聊聊MemTable逸贾。
轉(zhuǎn)載請注明：【隨安居士】http://www.reibang.com/p/6624befde844
