极致的读取性能：Append-only SkipList 设计模式

在并发数据结构的设计中，我们常常陷入一种思维定势：试图构建一个全能的、支持完整的增删改查（CRUD）且线程安全的容器。这种全能往往伴随着沉重的代价——复杂的锁机制、昂贵的原子操作（CAS loop），以及令人头秃的内存回收问题（Hazard Pointers 或 Epoch-based Reclamation）。

但在实际的工业级系统中，场景往往更加具体。如果我们面对的是一个只增不减（Append-only）的场景，比如日志存储、时序数据库的 MemTable 或者不可变数据的索引，我们是否可以丢掉那些沉重的包袱？

答案是肯定的。通过牺牲“删除”这一操作，我们可以获得极致的读取性能：Wait-free 的读取，且没有任何锁竞争。

核心设计哲学

Append-only SkipList（只增跳表）的核心设计哲学非常简单：一旦一个节点被链入表中，它就永远存在，且其内容不可变。

这个简单的约束带来了巨大的收益：

无需内存回收机制：读者永远不用担心读到一半节点被释放了。
无需复杂的锁：因为节点位置一旦确定就不会变动（没有节点会被移除或移动），我们只需要保证“新节点的插入”对读者是原子的即可。

结构拆解

在标准的跳表（SkipList）中，节点包含多层索引指针。在 Append-only 的设计中，我们依然保持这个结构，但对指针的操作有了新的定义：

节点（Node）：包含 Key、Value 以及一个原子指针数组（Atomic Pointers）。Key 和 Value 在初始化后不可变。
指针（Next Pointers）：使用原子变量存储。写入时使用 Release 语义，读取时使用 Acquire 语义。

并发模型：单写多读

为了简化实现并保证正确性，通常采用单写多读（Single-Writer Multi-Reader）模型，或者在写入侧加一把互斥锁。你可能会问：“写入加锁会不会太慢？”

在实际的高吞吐场景中，写入往往可以批量化（Batching），或者通过 WAL（Write Ahead Log）顺序写入来缓冲。而读取操作往往是海量的、随机的。只要读取足够快，写入侧的一点点等待通常是可以接受的。

写入流程（Writer）

写入者的工作流程如下：

创建新节点：分配内存，初始化 Key 和 Value，计算随机高度。
寻找插入点：从高层向低层遍历，找到每一层的前驱节点（Predecessor）。
原子链接：从最底层（Level 0）开始，向上逐层将新节点链入链表。

关键点：为什么是从下向上？虽然对于 Append-only 来说，顺序不是绝对致命的（因为没有删除），但从下向上链接通常更符合直觉：一旦 Level 0 链接完成，该节点在逻辑上就已经存在于链表中了（虽然高层索引还没建好，但不影响正确性，只影响查找速度）。而在 Rust 的内存模型中，最重要的是 Store Release 操作。

读取流程（Reader）

读者的工作简直太轻松了：

不需要锁。
不需要 Epoch Guard 保护。
只需要使用 Load Acquire 读取指针。

由于节点不会消失，读者手中的指针永远指向有效的内存（直到整个结构被销毁）。

深度演示：Rust 实现

为了演示这个概念，我们使用 Rust 构建一个精简的模型。我们将使用 AtomicPtr 来管理节点间的连接，并利用 Rust 的类型系统来保证内存安全（尽量）。

注：为了保持代码由简入深，以下代码使用 unsafe 块来处理裸指针，这在构建底层并发原语时是常态。

use std::sync::atomic::{AtomicPtr, Ordering};
use std::ptr;
use rand::Rng;

// 最大层高，通常根据预估数据量设定
const MAX_HEIGHT: usize = 12;

struct Node<K, V> {
    key: K,
    value: V,
    // 原子指针数组，用于并发读取
    next: [AtomicPtr<Node<K, V>>; MAX_HEIGHT],
}

impl<K, V> Node<K, V> {
    fn new(key: K, value: V) -> *mut Self {
        let node = Box::new(Node {
            key,
            value,
            next: Default::default(), // 初始化为空指针
        });
        Box::into_raw(node)
    }
}

pub struct AppendOnlySkipList<K, V> {
    head: *mut Node<K, V>,
}

impl<K, V> AppendOnlySkipList<K, V>
where
    K: Ord,
{
    pub fn new() -> Self {
        // 哨兵节点，由于是 demo，这里简化处理 Key/Value
        // 实际工程中通常使用 Option<K> 或专门的哨兵值
        unsafe {
            let head = Node::new(std::mem::zeroed(), std::mem::zeroed()); 
            AppendOnlySkipList { head }
        }
    }

    // 写入操作：需要 &mut self，意味着同一时间只能有一个写入者
    // 或者由外部 Mutex 保护
    pub fn insert(&mut self, key: K, value: V) {
        let mut prevs = [self.head; MAX_HEIGHT];
        let mut curr = self.head;

        // 1. 定位插入点
        for i in (0..MAX_HEIGHT).rev() {
            loop {
                // Reader 使用 Acquire，这里 Writer 使用 Relaxed 加载即可，
                // 因为我们拥有 &mut self，不存在并发写入竞争
                let next = unsafe { (*curr).next[i].load(Ordering::Relaxed) };
                
                // 找到第一个大于等于 key 的节点的前驱
                if next.is_null() || unsafe { &(*next).key >= &key } {
                    prevs[i] = curr;
                    break;
                }
                curr = next;
            }
        }

        // 2. 创建新节点
        let height = self.random_height();
        let new_node = Node::new(key, value);

        // 3. 链接节点
        for i in 0..height {
            let prev = prevs[i];
            let next = unsafe { (*prev).next[i].load(Ordering::Relaxed) };
            
            unsafe {
                // 设置新节点的 next 指针
                (*new_node).next[i].store(next, Ordering::Relaxed);
                
                // 关键一步：将 prev 的 next 指针指向新节点
                // 使用 Release 语义，确保 reader 看到指针时，
                // new_node 的内容（key, value, next）已经完全初始化完毕
                (*prev).next[i].store(new_node, Ordering::Release);
            }
        }
    }

    // 读取操作：&self，支持并发调用
    pub fn get(&self, key: &K) -> Option<&V> {
        let mut curr = self.head;
        for i in (0..MAX_HEIGHT).rev() {
            loop {
                // 关键一步：使用 Acquire 语义读取
                // 确保如果看到了非空的 next，那么 next 指向的节点内容不仅可见，且是最新的
                let next = unsafe { (*curr).next[i].load(Ordering::Acquire) };
                
                if next.is_null() {
                    break;
                }
                
                let next_ref = unsafe { &*next };
                if &next_ref.key > key {
                    break;
                }
                if &next_ref.key == key {
                    return Some(&next_ref.value);
                }
                curr = next;
            }
        }
        None
    }

    fn random_height(&self) -> usize {
        let mut h = 1;
        let mut rng = rand::thread_rng();
        while h < MAX_HEIGHT && rng.gen_bool(0.25) {
            h += 1;
        }
        h
    }
}

内存序的魔法

代码中最值得玩味的是 Ordering::Release 和 Ordering::Acquire 的配对：

Writer (Release): 当写入者执行 (*prev).next[i].store(new_node, Release) 时，它保证了在此之前的所有内存写入（即 new_node 的 Key、Value 和它自己的 next 指针初始化）对所有观察到这个 store 的线程都是可见的。
Reader (Acquire): 当读取者执行 load(Acquire) 并读到了 new_node 的地址时，它保证能看到与该地址相关联的、在 Release 之前发生的所有写入。

这就建立了一个 Happens-Before 关系。没有这个同步，读者可能会读到一个非空的指针，但顺着指针摸过去，却发现 Key 还是乱码，或者 Value 还没初始化。

这种设计的局限性

任何技术选型都是权衡（Trade-off）。Append-only SkipList 的代价显而易见：

内存膨胀：由于不能删除，所有的历史数据都驻留在内存中。这限制了它的使用场景——它不适合作为通用的缓存，而更适合作为 LSM Tree 的 MemTable（定期刷盘清空）或短期的流式索引。
特定的写入模式：它假设了写入是追加式的，或者允许 Key 重复（如果不做额外检查）。如果需要更新 Value，通常也是通过插入一个更新版本（MVCC）来实现，而不是原地修改。

总结

Append-only SkipList 是“做减法”设计的典范。通过移除“删除”功能，它消除了并发编程中最棘手的内存回收问题，将复杂的无锁算法简化为几次原子指针操作。在构建高性能的日志系统、消息队列或数据库引擎时，这种特化的数据结构往往比通用的 ConcurrentHashMap 能带来更低的时延和更高的吞吐。

有时候，为了跑得更快，你只需要扔掉一些不必要的行李。