当前位置：首页 > ds >正文

RocksDB跳表MemTable优化揭秘

ds 2025/7/28 5:32:03

`SkipListRep`

它是 RocksDB 中默认也是最基础的 MemTable 实现。虽然它看起来只是对跳表（SkipList）的一个包装，但其设计和实现中蕴含了许多值得学习的、针对高性能存储场景的优化技巧。

首先，最独特的一点是它使用的不是一个普通的跳表，而是一个 InlineSkipList。

skiplistrep.cc

// ...
class SkipListRep : public MemTableRep {InlineSkipList<const MemTableRep::KeyComparator&> skip_list_;// ...
};
// ...

InlineSkipList 的独特之处和值得学习的点：

内存布局优化 (Cache-Friendly): "Inline" 这个词是关键。传统的跳表节点通常包含一个指向数据的指针（Key*）和一组指向下一层节点的指针数组。而 InlineSkipList 为了提升 CPU 缓存命中率，采用了将 key 数据和节点元数据（主要是后向指针数组）连续存放在同一块内存中的策略。
- 当分配一个新节点时，它会申请一块 sizeof(Node) + key_length 大小的连续内存。
- Node 结构体本身只包含层高信息和指针数组，key 的数据紧跟在 Node 结构体之后。
- 优点: 当 CPU 访问一个跳表节点时，由于 key 和节点指针都在同一缓存行（Cache Line）内的概率大大增加，可以有效减少因指针跳转（pointer chasing）导致的缓存未命中（Cache Miss），从而显著提升遍历和查找性能。这是针对现代 CPU 架构非常重要的性能优化。
自定义内存分配器 (Allocator): InlineSkipList 在构造时接收一个 Allocator*。所有节点的内存都通过这个分配器来申请。
- 优点: 在 MemTable 的场景下，这个 Allocator 通常是 Arena。Arena 是一种内存池技术，它通过预先申请大块内存，然后以极低的开销（通常只是移动一个指针）进行小块内存的分配。这避免了频繁调用 new 或 malloc 带来的系统调用开销和内存碎片问题。当整个 MemTable 被销毁时，Arena 可以一次性释放所有内存，效率极高。

`LookaheadIterator`：针对顺序访问的优化

SkipListRep 提供了两种迭代器，其中 LookaheadIterator 是一个非常精巧的设计。

skiplistrep.cc

// ...// Iterator over the contents of a skip list which also keeps track of the// previously visited node. In Seek(), it examines a few nodes after it// first, falling back to O(log n) search from the head of the list only if// the target key hasn't been found.class LookaheadIterator : public MemTableRep::Iterator {private:const SkipListRep& rep_;InlineSkipList<const MemTableRep::KeyComparator&>::Iterator iter_;InlineSkipList<const MemTableRep::KeyComparator&>::Iterator prev_;// ...};
// ...

LookaheadIterator 的独特之处和值得学习的点：

利用访问局部性原理: 许多数据库操作（如范围扫描 Scan）具有很强的访问局部性，即下一个要查找的 key 很可能就在当前 key 的附近。
优化 Seek 操作:
1. LookaheadIterator 内部维护了两个迭代器：iter_ (当前位置) 和 prev_ (之前的位置)。
2. 当调用 Seek(key) 时，它不会立即从跳表的头节点开始进行 O(logN) 的全局搜索。
3. 相反，它会先判断 key 是否大于 prev_ 指向的 key。如果是，它会从 prev_ 的位置开始，向后进行一个短距离的线性扫描（步数由 lookahead_ 参数控制）。
4. 只有当在线性扫描中没有找到目标 key 时，它才会“退回”到标准的、从头开始的 O(logN) 搜索。
优点: 对于连续的 Seek 操作，这种“向前看”的策略可以将昂贵的 O(logN) 操作降级为廉价的 O(1) 或 O(lookahead) 操作，极大地提升了范围扫描的性能。这是一个典型的用空间（多一个 prev_ 指针）和少量计算换取巨大性能提升的案例。

丰富的并发插入接口

SkipListRep 将 InlineSkipList 提供的多种插入方法暴露了出来，以适应不同的并发场景。

// ...void Insert(KeyHandle handle) override;void InsertWithHint(KeyHandle handle, void** hint) override;void InsertConcurrently(KeyHandle handle) override;void InsertKeyWithHintConcurrently(KeyHandle handle, void** hint) override;
// ...

独特之处和值得学习的点：

区分并发与非并发: 提供了 Insert 和 InsertConcurrently 两个版本。InsertConcurrently 内部会使用更安全的并发控制（如原子操作），而 Insert 则可能使用无锁但非线程安全的优化。这让调用者可以根据上下文选择最高效的插入方式。
WithHint 优化: InsertWithHint 是一种针对有序插入的优化。hint 参数可以保存上次插入操作的路径信息。当下次插入的 key 与上次的 key 很接近时，跳表可以利用这个 hint 从上次结束的位置附近开始搜索，而不是每次都从头开始，从而将插入的复杂度从 O(logN) 降低到接近 O(1)。这在批量加载有序数据时非常有效。

`UniqueRandomSample`：高效的随机采样

细节分析见：RocksDB 高效采样算法：水塘抽样和随机寻址-CSDN博客

这个函数用于从 MemTable 中随机抽取样本，通常用于统计信息收集和生成压缩任务的边界。

独特之处和值得学习的点：

自适应采样策略: 它没有采用单一的采样算法，而是根据采样密度（target_sample_size 与 num_entries 的关系）动态选择最优策略：
1. 当采样密度较高时 (m > sqrt(N)): 它采用水塘抽样的变种。线性遍历所有元素，并以动态调整的概率决定是否将当前元素加入样本集。这种方法只需要遍历一次数据。
2. 当采样密度较低时 (m < sqrt(N)): 它采用随机寻址的方式。直接在跳表中进行 RandomSeek 来随机挑选元素，并用 std::unordered_set 来去重。因为密度低，随机碰撞的概率小，这种方法比完整遍历更高效。
优点: 这种根据数据特征选择不同算法的思路，是实现高性能系统的常用技巧。它避免了单一算法在某些极端情况下的性能退化问题。

总结

SkipListRep 虽然是 RocksDB 的基础 MemTable 实现，但它绝不是一个简单的跳表包装。我们可以从中学习到：

硬件感知的数据结构设计: InlineSkipList 通过优化内存布局来提升缓存命中率，是软件匹配硬件发展的典范。
利用访问模式进行优化: LookaheadIterator 和 InsertWithHint 都是基于“访问局部性”这一常见模式进行的针对性优化。
提供多粒度的接口: 区分并发/非并发、带/不带提示的接口，将优化的选择权交给调用者，使其能根据具体场景压榨性能。
算法的自适应选择: UniqueRandomSample 中根据输入数据的特征选择不同实现路径，是构建健壮、高效系统的关键。

这些设计思想和优化技巧，都非常值得在自己的项目中学习和借鉴。

`InlineSkipList`

极致的内存布局 (The "Inline" in `InlineSkipList`)

之前的分析提到 InlineSkipList 将节点和 Key 连续存储以优化缓存。源代码实现更为精巧。

关键代码 - Node 结构体和内存分配:

// ... existing code ...
// The Node data type is more of a pointer into custom-managed memory than
// a traditional C++ struct.  The key is stored in the bytes immediately
// after the struct, and the next_ pointers for nodes with height > 1 are
// stored immediately _before_ the struct.
template <class Comparator>
struct InlineSkipList<Comparator>::Node {
// ... existing code ...const char* Key() const { return reinterpret_cast<const char*>(&next_[1]); }// Accessors/mutators for links.  Wrapped in methods so we can add// the appropriate barriers as necessary, and perform the necessary// addressing trickery for storing links below the Node in memory.Node* Next(int n) {assert(n >= 0);// Use an 'acquire load' so that we observe a fully initialized// version of the returned Node.return ((&next_[0] - n)->load(std::memory_order_acquire));}
// ... existing code ...private:// next_[0] is the lowest level link (level 0).  Higher levels are// stored _earlier_, so level 1 is at next_[-1].std::atomic<Node*> next_[1];
};// ... existing code ...
template <class Comparator>
Node* InlineSkipList<Comparator>::AllocateNode(size_t key_size, int height) {// The allocated memory space is composed of three parts:// 1. The pointers for levels higher than 0, starting from `height` - 1.// 2. The Node object, which contains the pointer for level 0.// 3. The key payload.char* const ptr = allocator_->AllocateAligned(sizeof(std::atomic<Node*>) * (height - 1) + sizeof(Node) + key_size);Node* const node =new (ptr + sizeof(std::atomic<Node*>) * (height - 1)) Node();return node;
}

三合一内存块: AllocateNode 一次性分配了一整块连续内存，用于存储三样东西：
- 高层级的 next 指针数组 (height - 1 个)。
- Node 结构体本身 (只包含 next_[0])。
- 变长的 Key 数据。
负索引指针技巧: Node 结构体只定义了 next_[0]，但通过 (&next_[0] - n) 这样的指针算术，它可以访问到存储在 Node 结构体之前的、更高层级的 next 指针。
极致的缓存友好性: 这种布局意味着当访问一个 Node 时，它的所有层级的 next 指针以及 Key 数据都紧密地排列在内存中。这大大增加了它们位于同一个 CPU Cache Line 的概率，将访存开销降到最低。这验证并深化了之前的说法，其实现技巧非常高超。

除了之前讨论过的 Allocator、并发控制和 InsertWithHint，InlineSkipList 还有更多优化。

`Splice` 对象：插入操作的“导航仪”

InsertWithHint 的 hint 参数实际上是一个 Splice*。Splice 是一个用于加速查找和插入的内部结构。

关键代码 - Splice 结构体:

inlineskiplist.h

// ... existing code ...
template <class Comparator>
struct InlineSkipList<Comparator>::Splice {// The invariant of a Splice is that prev_[i+1].key <= prev_[i].key <// next_[i].key <= next_[i+1].key for all i.  That means that if a// key is bracketed by prev_[i] and next_[i] then it is bracketed by// all higher levels.  It is _not_ required that prev_[i]->Next(i) ==// next_[i] (it probably did at some point in the past, but intervening// or concurrent operations might have inserted nodes in between).int height_ = 0;Node** prev_;Node** next_;
};

值得学习的点:

缓存搜索路径: Splice 存储了某次查找操作在每一层的前驱节点 (prev_) 和后继节点 (next_)。它就像一张“导航图”。
加速有序插入: 对于非并发的顺序插入，InlineSkipList 内部维护了一个 seq_splice_。当插入下一个 key 时，它可以从 seq_splice_ 记录的位置附近开始搜索，而不是每次都从跳表头（head_）开始。这使得顺序插入的复杂度从 O(logN) 降级为接近 O(1)。
InsertWithHint 的本质: InsertWithHint 允许调用者为不同的 key 分组（例如，不同的写入线程）维护各自的 Splice 对象，将这种优化扩展到更复杂的场景。

舍弃 `prev` 指针：空间与时间的权衡

Node 结构中只有 next 指针，没有 prev 指针。那么 Iterator::Prev() 是如何实现的呢？

关键代码 - Iterator::Prev():

// ... existing code ...
template <class Comparator>
inline void InlineSkipList<Comparator>::Iterator::Prev() {// Instead of using explicit "prev" links, we just search for the// last node that falls before key.assert(Valid());node_ = list_->FindLessThan(node_->Key(), nullptr);if (node_ == list_->head_) {node_ = nullptr;}
}

值得学习的点:

空间优化: 不存储 prev 指针，为每个节点节省了 height 个指针的存储空间。考虑到 MemTable 中可能有数百万个节点，这是一个巨大的内存节省。
性能权衡: 作为代价，Prev() 操作不再是 O(1) 的指针跳转，而变成了一次 O(logN) 的 FindLessThan 搜索。
明智的决策: 对于数据库工作负载，前向迭代 (Next) 和查找 (Seek) 的频率远高于后向迭代 (Prev)。因此，用不常用的 Prev 操作的性能换取显著的内存节省，是一个非常明智和典型的工程决策。

精准的并发控制：`acquire-release` vs `relaxed`

InlineSkipList 对 C++ 内存模型的运用堪称典范。

在 Node::SetNext() 中，它使用 std::memory_order_release。
在 Node::Next() 中，它使用 std::memory_order_acquire。
- 这构成了一对 acquire-release 同步，确保当一个线程通过 Next() 读到一个新节点时，它能看到这个节点被完整初始化的所有内容。这是保证并发正确性的关键。
然而，在 GetMaxHeight() 中，它却使用了最轻量的 std::memory_order_relaxed。
- 这是因为它允许读到稍微过时（stale）的 max_height_ 值。读到旧值不会导致程序错误，最多只是让查找路径稍微不是最优，但性能影响可以忽略不计。

值得学习的点: 根据不同数据访问的特性，选择最恰当、开销最低的内存序。这体现了开发者对并发编程的深刻理解，避免了“一刀切”地使用重量级锁或强内存序，将性能压榨到极致。

`StashHeight`：无伤大雅的“黑魔法”

关键代码 - Node::StashHeight:

// ... existing code ...
template <class Comparator>
struct InlineSkipList<Comparator>::Node {// Stores the height of the node in the memory location normally used for// next_[0].  This is used for passing data from AllocateKey to Insert.void StashHeight(const int height) {assert(sizeof(int) <= sizeof(next_[0]));memcpy(static_cast<void*>(&next_[0]), &height, sizeof(int));}// Retrieves the value passed to StashHeight.  Undefined after a call// to SetNext or NoBarrier_SetNext.int UnstashHeight() const {int rv;memcpy(&rv, &next_[0], sizeof(int));return rv;}
// ... existing code ...

值得学习的点: 这是一个非常有趣的微优化。在 AllocateNode 时，节点的随机高度已经确定。为了将这个高度值传递给 Insert 函数，代码没有修改函数签名增加一个参数，而是巧妙地将 height (一个整数) 临时存入了 next_[0] 指针的内存空间里。因为此时节点尚未链接到跳表中，这个指针字段是空闲的。Insert 函数在执行时会先 UnstashHeight 取出高度，然后再将 next_[0] 设置为真正的指针。

这是一个在不破坏接口优雅性的前提下传递内部状态的 clever hack。

总结

InlineSkipList 远非一个简单的跳表实现。它是一个集硬件感知内存布局、精巧的算法优化、精准的并发控制和务实的工程权衡于一体的杰作。每一处设计都体现了对高性能存储系统底层原理的深刻洞察。

`Splice`

Splice 就像是一次插入操作的“GPS导航记录”。当跳表需要找到一个 key 的插入位置时，它会从最高层逐层向下搜索，这个搜索路径上的“拐点”（即每层最后一个小于目标 key 的节点）被记录下来，就形成了 Splice。后续的插入操作就可以尝试重用这个“导航记录”来走捷径。

我们通过一个完整的插入流程来理解它的使用：

第一幕：准备“导航记录” (`Splice`)

一个 Splice 结构体包含两个主要的指针数组：prev_ 和 next_。

// ... existing code ...
template <class Comparator>
struct InlineSkipList<Comparator>::Splice {// ...int height_ = 0;Node** prev_; // prev_[i] 是在 i 层找到的、key 小于目标 key 的最后一个节点Node** next_; // next_[i] 是在 i 层找到的、key 大于或等于目标 key 的第一个节点
};
// ... existing code ...

当执行一次插入时，系统首先需要一个 Splice 对象。来源有三种：

Insert(): 使用类内部的 seq_splice_。这专门用于优化单线程连续写入的场景。
InsertWithHint(): 使用调用者传入的 hint。如果 hint 是空的，就新分配一个并存入 hint，供调用者下次使用。这用于优化“分组连续写入”的场景。
InsertConcurrently(): 在函数栈上临时创建一个 Splice，用完即弃。

第二幕：使用“导航记录”走捷径

这是 Splice 发挥作用的核心。当 Insert 函数拿到一个 key 和一个 Splice 时，这个 Splice 记录的是上一次插入的路径，不一定适用于当前的 key。于是，代码需要判断这个“导航记录”还有多大用处。

请看 Insert 函数的核心逻辑：

// ... existing code ...template <bool UseCAS>bool Insert(const char* key, Splice* splice, bool allow_partial_splice_fix);
// ... existing code ...
template <bool UseCAS>
bool InlineSkipList<Comparator>::Insert(const char* key, Splice* splice,bool allow_partial_splice_fix) {// ... (获取新节点高度等准备工作) ...// 关键逻辑：检查 Splice 是否可用// recompute_height 记录了需要从哪一层开始重新计算路径int recompute_height = 0;if (splice->height_ < max_height) {// 如果 Splice 的高度比当前跳表还低，说明它太旧了，必须从头计算// ...recompute_height = max_height;} else {// Splice 高度足够，但它记录的路径对不对？// 我们从高层向低层检查，看 Splice 记录的 prev_ 和 next_ 是否能“包住”当前的 keywhile (recompute_height < max_height) {// 检查 prev_[level] 和 next_[level] 是否包围了 keyif (splice->prev_[recompute_height] != head_ &&!KeyIsAfterNode(key_decoded, splice->prev_[recompute_height])) {// key 在 splice 记录的 prev 节点之前，路径不对// ... 需要重新计算 ...break; } else if (KeyIsAfterNode(key_decoded, splice->next_[recompute_height])) {// key 在 splice 记录的 next 节点之后，路径不对// ... 需要重新计算 ...break;}// 如果这一层能包住 key，说明从这一层往上的路径都是对的，不需要重新计算// 我们继续检查下一层recompute_height++;}}// 如果 recompute_height > 0，说明部分或全部路径需要重新计算if (recompute_height > 0) {// 调用 FindSpliceForLevel 等函数，只为需要重新计算的层级（0 到 recompute_height-1）// 重新查找正确的 prev 和 next 节点，更新 SpliceRecomputeSpliceLevels(key_decoded, splice, recompute_height);}// ... (执行插入) ...
}

场景举例:

完美命中 (顺序插入): 假设上次插入了 "key10"，splice->prev_[0] 指向 "key09"。现在要插入 "key10.5"。代码检查发现 "key10.5" 确实在 "key09" 之后，且在 splice->next_[0] 之前。所有层的检查都通过，recompute_height 最终为 0。查找过程被完全跳过，直接进入插入环节，复杂度是 O(1)。
部分命中 (局部插入): 假设上次插入 "key10"，现在插入 "key50"。检查时发现，在最高几层，prev_ 可能是 head_ 节点，next_ 是 nullptr，路径依然能“包住” "key50"。但在较低的层级，路径就失效了。recompute_height 会停在那个失效的层级，系统只需要从那一层开始重新搜索路径，而不是从头开始。
完全失效 (随机插入): 插入一个和上次位置完全无关的 key，Splice 在最高层就失效了，recompute_height 会等于 max_height，相当于进行了一次没有优化的、完整的 O(logN) 查找。

第三幕：执行插入

当第二幕结束后，Splice 对象中的 prev_ 和 next_ 数组已经被完全更新，准确地记录了当前 key 在每一层的前驱和后继节点。

接下来的插入操作就变得非常简单：

// ... 在 Insert 函数的末尾 ...
// 循环新节点的实际高度
for (int i = 0; i < height; ++i) {// 直接使用 Splice 中记录好的前驱节点 prev_[i] 来插入新节点x->InsertAfter(splice->prev_[i], i);
}

总结

Splice 的本质是一个带有状态的查找缓存。它将一次 O(logN) 查找的结果保存下来，使得下一次查找有可能以远低于 O(logN) 的代价完成，在顺序或局部性较好的写入负载下，可以把插入效率提升到接近 O(1)。InsertWithHint 更是将这种优化能力开放给了上层调用者，使其可以为不同的写入流维护各自的“导航记录”，是一个非常精妙的设计。

为什么把高层级的指针数组放在 `Node` 结构体的前面

这其实是一个非常聪明的技巧，目的是在节点高度可变的情况下，依然能让 Node 结构体本身保持固定大小，从而实现极致的内存布局和效率。

我们来分解一下这个设计：

跳表节点的本质: 跳表中的每个节点高度是随机的、可变的。一个高度为 5 的节点需要 5 个 next 指针，而一个高度为 1 的节点只需要 1 个。
C++ 结构体的限制: 在 C++ 中，一个 struct 或 class 的大小在编译时就需要确定。你无法直接定义一个成员是“可变长数组”的结构体（C99 的 flexible array member 是个例外，但 C++ 标准不支持）。
常规解决方案及其弊端:
- 方案A (指针): struct Node { Key* key; Node** next_pointers; };。这需要在分配 Node 的同时，再单独分配一个指针数组，并让 next_pointers 指向它。这会造成两次内存分配和一次额外的指针解引用，破坏了数据局部性，与 InlineSkipList 追求缓存友好的初衷背道而驰。
- 方案B (最大高度数组): struct Node { Key* key; Node* next_pointers[kMaxHeight]; };。这会导致所有节点，无论实际高度是多少，都占用 kMaxHeight 个指针的空间，造成巨大的内存浪费。

`InlineSkipList` 的解决方案：负索引指针

InlineSkipList 的设计完美地规避了上述所有问题。

我们来看 AllocateNode 函数，它揭示了底层的内存布局。

// ... existing code ...
template <class Comparator>
typename InlineSkipList<Comparator>::Node*
InlineSkipList<Comparator>::AllocateNode(size_t key_size, int height) {// 计算 Node 结构体之前需要为 height-1 个高层级指针预留的空间auto prefix = sizeof(std::atomic<Node*>) * (height - 1);// ...// 一次性分配一块连续内存，包含三部分：// 1. 前缀空间 (prefix)，用于存放高层级指针// 2. Node 结构体本身的空间 (sizeof(Node))// 3. Key 的空间 (key_size)char* raw = allocator_->AllocateAligned(prefix + sizeof(Node) + key_size);// 使用 placement new，在 "raw + prefix" 的位置构造 Node 对象// 这意味着 Node 对象的起始地址，正好位于高层级指针空间的后面Node* x = reinterpret_cast<Node*>(raw + prefix);// ...return x;
}

内存布局图示 (对于一个高度为 h 的节点):

| <-- (h-1) * sizeof(ptr) --> | <-- sizeof(Node) --> | <-- key_size --> |
+-----------------------------+----------------------+------------------+
| next_[-(h-1)] ... next_[-1]  | Node { next_[0] }    |   Key's data     |
+-----------------------------+----------------------+------------------+
^                             ^
|                             |
raw                           x (Node* 指针指向这里)

这个特性的使用体现在 Node 的指针访问方法中，这正是整个设计的精髓所在。

// ... existing code ...
template <class Comparator>
struct InlineSkipList<Comparator>::Node {
// ... existing code ...// Accessors/mutators for links.  Wrapped in methods so we can add// the appropriate barriers as necessary, and perform the necessary// addressing trickery for storing links below the Node in memory.Node* Next(int n) {assert(n >= 0);// Use an 'acquire load' so that we observe a fully initialized// version of the returned Node.// 这就是魔法发生的地方！return ((&next_[0] - n)->load(std::memory_order_acquire));}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_[0] - n)->store(x, std::memory_order_release);}
// ... existing code ...private:// next_[0] is the lowest level link (level 0).  Higher levels are// stored _earlier_, so level 1 is at next_[-1].std::atomic<Node*> next_[1];
};

Node 结构体本身只定义了 next_[1]，所以 sizeof(Node) 是一个固定的、已知的值。
当调用 Next(n) 时，&next_[0] 获取 next_ 数组（也就是 Node 结构体内部的 next_ 成员）的地址。
(&next_[0] - n) 是一个指针运算。它将指针从 next_[0] 的位置向前移动 n 个 std::atomic<Node*> 的大小。
- Next(0): (&next_[0] - 0) -> 访问 next_[0]
- Next(1): (&next_[0] - 1) -> 访问 Node 结构体紧邻的前一个指针位置
- Next(2): (&next_[0] - 2) -> 访问再往前一个指针位置
这样，通过一个简单的指针减法，就实现了对可变高度节点所有层级指针的访问。

总结

将高层级指针放在 Node 结构体前面，并非没有意义，而是一个极其精巧的 C++ 实现技巧，其核心优势在于：

实现了真正的 "Inline": 将节点元数据（所有指针）和业务数据（Key）紧密地存放在一块连续的内存中，最大化了 CPU 缓存效率。
避免了内存浪费: 每个节点只分配其随机高度所必需的内存，不像“最大高度数组”方案那样浪费空间。
避免了二次分配和额外指针跳转: 相比于“指针的指针”方案，它减少了内存分配次数和运行时的指针解引用，性能更高。
保持了 Node 结构的固定大小: 这使得内存分配和 placement new 的计算变得简单直接。

这个特性在所有对跳表节点进行遍历和修改的地方都被用到，是 InlineSkipList 高性能的根本保障之一。

理论最大高度和实际高度

InlineSkipList 中存在两种“最大高度”：

kMaxHeight_: 这是一个静态的、理论上的最大值。它在 InlineSkipList 对象被构造时确定。它的主要作用是为控制结构分配足够的空间，而不是为每个数据节点。
max_height_: 这是一个动态的、实际的当前最大值。它是一个原子变量，记录了当前跳表中所有节点里最高的那个节点的高度。

kMaxHeight_ 的成本只在少数地方支付一次。

head_ 哨兵节点: head_ 节点是所有查找的起点。它必须拥有到达理论最大高度的所有层级的指针，这样无论新节点多高，都能从 head_ 开始连接。

// ... existing code ...
template <class Comparator>
InlineSkipList<Comparator>::InlineSkipList(const Comparator cmp,Allocator* allocator,int32_t max_height,int32_t branching_factor): kMaxHeight_(static_cast<uint16_t>(max_height)),kBranching_(static_cast<uint16_t>(branching_factor)),kScaledInverseBranching_((Random::kMaxNext + 1) / kBranching_),allocator_(allocator),compare_(cmp),// 看这里：head_ 节点在构造时，传入了 max_height (即 kMaxHeight_)// 它被分配了足够容纳所有层级指针的空间head_(AllocateNode(0, max_height)),max_height_(1),seq_splice_(AllocateSplice()) {// ...for (int i = 0; i < kMaxHeight_; ++i) {head_->SetNext(i, nullptr);}
}

Splice 辅助结构: Splice 用于缓存查找路径，它的 prev_ 和 next_ 数组也必须能容纳 kMaxHeight_ 个指针。

对于每一个要插入的数据节点，流程如下：

生成随机高度: AllocateKey 函数首先调用 RandomHeight() 为这个新节点生成一个随机的、实际的高度 height。这个 height 在 1 和 kMaxHeight_ 之间。

// ... existing code ...
template <class Comparator>
int InlineSkipList<Comparator>::RandomHeight() {// ...int height = 1;// 以 1/kBranching_ 的概率增加高度，但绝不会超过 kMaxHeight_while (height < kMaxHeight_ && height < kMaxPossibleHeight &&rnd->Next() < kScaledInverseBranching_) {height++;}// ...return height;
}

按需分配内存: 接着，AllocateNode 函数被调用，但传入的是刚刚生成的随机高度 height，而不是 kMaxHeight_。因此，内存只会为这个节点实际需要的 height 个指针分配空间。

// ... existing code ...
template <class Comparator>
char* InlineSkipList<Comparator>::AllocateKey(size_t key_size) {// 1. 先决定这个新节点的实际高度int height = RandomHeight();// 2. 然后只为这个实际高度分配节点内存Node* node = AllocateNode(key_size, height);// 3. 将高度信息临时存入节点，以便 Insert 函数使用node->StashHeight(height);return const_cast<char*>(node->Key());
}template <class Comparator>
typename InlineSkipList<Comparator>::Node*
InlineSkipList<Comparator>::AllocateNode(size_t key_size, int height) {// 分配的内存大小是基于传入的 height，而不是 kMaxHeight_auto prefix = sizeof(std::atomic<Node*>) * (height - 1);// ...char* raw = allocator_->AllocateAligned(prefix + sizeof(Node) + key_size);Node* x = reinterpret_cast<Node*>(raw + prefix);// ...return x;
}

当 Insert 函数执行时：

它从节点中取出之前存好的实际高度 height。
它会检查这个 height 是否大于当前跳表的实际最大高度 max_height_。

如果 height > max_height_，它会以原子方式尝试更新 max_height_ 的值为 height。

// ... existing code ...
template <bool UseCAS>
bool InlineSkipList<Comparator>::Insert(const char* key, Splice* splice,bool allow_partial_splice_fix) {Node* x = reinterpret_cast<Node*>(const_cast<char*>(key)) - 1;// ...int height = x->UnstashHeight(); // 取出节点的实际高度// ...int max_height = max_height_.load(std::memory_order_relaxed);// 如果新节点的实际高度 > 当前列表的最高高度while (height > max_height) {// 尝试用原子操作更新列表的当前最高高度if (max_height_.compare_exchange_weak(max_height, height)) {// 更新成功max_height = height;break;}// 如果失败，说明有其他线程也在更新，重试}// ...// 后续的插入操作，只会循环 height 次，在 0 到 height-1 层上链接指针for (int i = 0; i < height; ++i) {// ... 链接指针 ...}// ...
}

总结

这个设计是空间效率和时间效率的完美结合：

空间上: 除了 head_ 节点，其他所有数据节点都只占用它们实际高度所需的内存，极大地节省了空间。
时间上:
- 查找时，从 GetMaxHeight() - 1（即当前实际最高层）开始，保证了 O(logN) 的效率。
- 插入时，通过动态更新 max_height_，确保了整个跳表结构的正确性和未来的查找效率。

所以，“跳表需要最大高度” 这个说法是对的，但 InlineSkipList 通过区分理论最大高度（用于控制结构）和节点实际高度（用于数据节点），并动态维护列表的当前最大高度，实现了这个需求，同时做到了极致的内存优化。

查看全文

http://www.xdnf.cn/news/16531.html