HotRing：热点感知的无锁内存 KV 索引

为什么需要 HotRing？

在大规模分布式系统中，内存 KV 存储（如 Memcached、Redis）承担着缓存热点数据的关键角色。然而，一个被长期忽视的矛盾正在变得越来越尖锐：

传统哈希索引对所有数据"一视同仁"——无论一个 key 被访问 1 次还是 100 万次，查找它的代价完全相同，取决于它在冲突链中的位置。

现实中的访问分布极度不均匀。阿里巴巴 Tair 的生产数据显示，热点比例通常在 10%-20%（即 10%-20% 的 key 承担了绝大部分请求），且这一趋势在持续加剧。论文引用的数据表明，Amazon 每 100ms 的额外延迟会损失 1% 的销售额，Google 搜索每增加 0.5s 加载时间就会导致 20% 的流量下降。

核心矛盾：访问频率极不均匀，但索引结构完全不感知这种不均匀。

HotRing 正是为解决这一矛盾而提出的。它是阿里巴巴在 FAST 2020（USENIX 文件与存储技术顶会）上发表的工作，由陈吉强等人完成，目前已落地为阿里巴巴 Tair 产品的核心组件。

理论基础：热点感知的收益有多大？

在动手设计之前，论文先做了一个优雅的理论分析。

假设哈希表有 $B$ 个桶，存储 $N$ 个 item，平均冲突链长度 $L = N/B$ 。在传统哈希索引中，查找一个 item 的期望内存访问次数为：

$E_{\text{chain}} = 1 + \frac{L}{2} = 1 + \frac{N}{2B}$

所有 item 的访问代价是均匀的——热点和冷数据没有任何区别。

而在理想的热点感知索引中，如果我们能按访问频率排序（最热的排在最前面），期望访问次数为：

$E_{\text{ideal}} = 1 + \sum_{k=1}^{L} F(k) \cdot k$

其中 $F(k)$ 是链上第 $k$ 个 item 的累积访问频率。

论文用 Zipf 分布建模热点（ $f(x) = \frac{1}{x^q} / \sum \frac{1}{n^q}$ ，其中 $q$ 是偏斜因子），计算两种方案的差异：

冲突链长度	传统哈希 $E_{\text{chain}}$	热点感知 $E_{\text{ideal}}$	加速比
5	3.5	~1.5	2.3x
10	6.0	~1.8	3.3x
15	8.5	~2.0	4.3x

冲突链越长，热点感知的收益越大。 这一分析为后续设计提供了坚实的理论支撑。

核心设计

1. 有序环哈希索引（Ordered-Ring）

HotRing 最大的结构创新是把冲突链变成环。

传统哈希索引的冲突链：

Head → A → B → C → D → NULL

HotRing 的有序环：

Head → B → D → A → C → (回到 B)
         ↑                    |
         └────────────────────┘

为什么用环？ 这是一个精巧的设计权衡。在链表中，head 指针必须指向第一个节点——如果想把"最热的 item"放到最前面，就需要重新排列整个链表。但在环中，head 指针可以指向任意 item，而不丢失任何数据。这意味着我们可以通过移动 head 指针（而非重排数据）来优化热点访问。

有序环的关键： 环中的 item 按 (tag, key) 字典序排列。tag 是 key 哈希值的高 16 位，用于快速比较。这带来两个好处：

查找可提前终止：不需要遍历整个环。如果连续遇到两个 item A 和 B，且 A < target < B（在代码块外用纯文本表示），就可以判定目标不存在（因为它应该在 A 和 B 之间，但中间没有其他节点）。
平均只需遍历 n/2 + 1 个 item：传统链表最坏情况需要遍历全部。

2. 两种热点识别策略

head 指针应该指向哪个 item？热点会随时间变化，如何检测？

策略一：随机移动（HotRing-r）

最简单直接的方案。每 R 次访问（默认 R=5），检查当前访问是否命中 head item：

如果命中 → 当前热点仍然有效，不做任何事
如果未命中 → 把 head 指针移到这次访问的 item

优点是反应极快（2 秒内达到稳定），缺点是精度低且无法处理多热点。

策略二：统计采样（HotRing-s）

更精确的方案，利用了指针中未使用的位来存统计信息：

Head 指针：48 位地址 + 1 bit Active 标志 + 15 bit 总访问计数器
Item 的 next 指针：48 位地址 + 14 bit 访问计数器 + Rehash/Occupied 标志

现代机器的物理地址只占 48 位，剩余 16 位正好可以存元数据，零额外空间开销。

采样流程：

每 R 次请求检查一次，如果当前访问不是 head item，启动采样
采样期间记录每个 item 的访问次数
采样完成后（收集了 k 个样本（k = 环大小）），计算最优 head 位置

最优位置的计算使用论文公式 (6)：

$W_t = \sum_{i=1}^{k} \frac{n_i}{N} \cdot ((i - t) \bmod k)$

其中 $n_i$ 是第 $i$ 个 item 的访问次数， $N$ 是总访问次数， $t$ 是候选 head 位置。选择 $W_t$ 最小的位置作为新的 head——这不一定是最热的 item，而是使整体期望访问次数最小的位置。

这个设计还能处理多热点场景：如果两个 item 热度相近，最优 head 可能在它们之间的某个位置。

3. RCU 写热点的特殊处理

对于大于 8 字节的 value，更新需要用 RCU（Read-Copy-Update）：创建新副本 → 修改前驱指针 → 释放旧版本。

问题： 如果热点 item 是 head，RCU 更新需要找到它的前驱 → 必须遍历整个环 → 代价极高。

解决方案： 对于 RCU 更新操作，统计采样时不仅计数当前 item，还会计数它的前驱 item。这样 head 指针会指向热点的前驱，RCU 更新只需 1 次内存访问。

4. 热点继承

当 head item 被删除或 RCU 更新时，head 指针移到哪？

RCU 更新：head 移到新版本（利用时间局部性——刚被更新的 item 很可能马上又被访问）
删除：head 移到下一个 item

这避免了随机移动导致频繁触发热点识别。

无锁 CAS 实现

论文全面采用 CAS（Compare-And-Swap）实现无锁操作。这是 HotRing 在高并发场景下性能出色的关键原因。

核心操作

查找（Find）

无锁遍历有序环，利用字典序提前终止。如果遇到正在被删除的 item（mark bit 被设置），从 head 重试。

Item *ring_find(HotRing *hr, int bucket_idx, const char *key, int *accesses) {
    Item *head = atomic_load(&hp->item);
    Item *curr = head;
    Item *prev = NULL;

    while (1) {
        Item *next_raw = atomic_load(&curr->next);
        if (is_marked(next_raw)) {
            // 遇到被删除的 item，从 head 重试
            curr = atomic_load(&hp->item);
            continue;
        }

        (*accesses)++;
        if (curr->tag == target_tag && strcmp(curr->key, key) == 0)
            return curr;  // 命中

        // 提前终止：检查"谷值"条件
        if (prev && is_valley(prev, target, curr))
            return NULL;  // 未命中，无需遍历全部

        prev = curr;
        curr = next_raw;
        if (curr == head) return NULL;  // 遍历完整个环
    }
}

插入（Insert）

在有序环中找到正确位置，CAS 修改前驱的 next 指针：

bool ring_insert(HotRing *hr, int bucket_idx, Item *new_item) {
retry:
    Item *curr = head;
    while (1) {
        Item *next = unmark(atomic_load(&curr->next));
        // 找到正确的插入位置（curr <= new_item < next）
        if (should_insert_between(curr, new_item, next)) {
            atomic_store(&new_item->next, next);
            Item *expected = next;
            if (atomic_compare_exchange_strong(&curr->next, &expected, new_item))
                return true;  // CAS 成功
            goto retry;  // CAS 失败，有其他线程修改了 curr->next
        }
        curr = next;
    }
}

删除（Delete）—— Harris 标记法

这是无锁链表的经典技巧，分两步：

逻辑删除：CAS 将目标 item 的 next 指针加上 mark bit
物理删除：CAS 将前驱的 next 指针指向目标的下一个 item（跳过被标记的）

bool ring_delete(HotRing *hr, int bucket_idx, const char *key) {
    // 找到目标 item 和它的前驱 pred
    // Step 1: 逻辑删除 — 标记 target->next
    Item *curr_next = atomic_load(&target->next);
    atomic_compare_exchange_strong(&target->next, &curr_next, mark(curr_next));

    // Step 2: 物理删除 — CAS pred->next 跳过 target
    Item *expected = target;
    if (atomic_compare_exchange_strong(&pred->next, &expected, unmark(curr_next))) {
        // 热点继承：如果删除的是 head，移到下一个
        atomic_compare_exchange_strong(&hp->item, &target, unmark(curr_next));
        return true;
    }
    goto retry;
}

Head 指针移动

void hotspot_random(HotRing *hr, int bucket_idx, Item *accessed, bool is_hot) {
    if (is_hot) return;
    Item *expected = atomic_load(&hp->item);
    // CAS 移动 head 到被访问的 item
    atomic_compare_exchange_strong(&hp->item, &expected, accessed);
}

并发安全的关键设计

操作	并发挑战	解决方案
查找	遍历过程中 item 被删除	mark bit 检测 + 重试
插入	两个线程同时在同一位置插入	CAS 失败后重试
删除	前驱被并发删除	mark bit 两步删除
Head 移动	多线程同时移动 head	CAS 保证原子性
采样	多线程同时触发采样	Active bit + CAS 保证只触发一次

实验结果

测试环境

双路 Intel Xeon E5-2682 v4（32 核 64 线程）
256GB DDR4 RAM
YCSB 基准测试，250M 个 key
Zipf 分布模拟真实热点（q=0.99 日常场景，q=1.22 极端场景）

核心数据

HotRing 的多线程无锁 CAS 实现的 benchmark 结果：

Zipf q	Threads	Chaining Hash 平均访问次数	HotRing-s 平均访问次数	加速比
0.99	1	32.30	9.88	3.27x
0.99	32	32.33	9.93	3.26x
1.22	1	22.05	4.47	4.94x
1.22	32	22.10	4.50	4.91x

几个关键观察：

热点越集中，优势越大：q 从 0.99 到 1.22，加速比从 3.3x 提升到 5x
并发扩展性好：线程从 1 增加到 32，HotRing 的加速比基本保持不变，说明无锁设计有效
尾延迟可控：99 分位 ~2-3μs，有少量长尾 ~9μs（可通过后台线程缓解）

代码实现

完整的代码实现包含两个版本：

Python 版本（教学版）

适合理解核心算法逻辑。实现了完整的有序环、两种热点识别策略、以及与传统哈希的对比 benchmark。

核心数据结构：

@dataclass
class Item:
    tag: int                    # 哈希 tag（用于排序）
    key: str                    # 实际 key
    value: str                  # 存储的 value
    next: Optional['Item']      # 环中的下一个 item
    access_count: int = 0       # 统计采样用的访问计数

@dataclass
class HeadPointer:
    item: Optional[Item] = None # head 指向的 item
    active: bool = False        # 采样是否激活
    total_counter: int = 0      # 采样期间的总访问计数

有序环插入（维护排序）：

def _ring_insert(self, bucket_idx, new_item):
    current = head_ptr.item
    while True:
        nxt = current.next
        # 找到正确位置：current <= new < nxt
        if current.order <= new_item.order < nxt.order:
            current.next = new_item
            new_item.next = nxt
            return
        current = nxt
        if current == head_ptr.item: break

统计采样热点识别：

def _adjust_head_sampling(self, bucket_idx):
    items = self._ring_items(bucket_idx)
    N = head_ptr.total_counter
    k = len(items)

    # 计算每个候选位置的期望访问代价 Wt
    best_item, best_cost = items[0], float('inf')
    for t_idx in range(k):
        cost = sum(
            (items[i].access_count / N) * ((i - t_idx) % k)
            for i in range(k)
        )
        if cost < best_cost:
            best_cost = cost
            best_item = items[t_idx]

    head_ptr.item = best_item  # 移动 head 到最优位置

C 无锁 CAS 版本（生产级）

使用 C11 atomic 操作实现真正的无锁并发。关键技巧：

Harris mark bit：在指针最低位标记逻辑删除
CAS 重试循环：失败时从头重试，保证线程安全
Active bit：保证采样只被一个线程触发