最近研究了 papaya，这是一个为 Rust 设计的高效且功能完备的并发哈希表。在这篇文章中，我将深入探讨其设计理念、研究过程，以及为什么你可能选择它而不是现有的解决方案。如果你正在寻找 papaya 的概览，建议你查阅相关文档。

设计理念

并发哈希表是一个在学术文献和开源实现中都得到了充分探索的主题。在某些方面，它们是并发数据结构的圣杯。另一方面，并发哈希表通常是一个共享可变数据的笨重集合，往往标志着程序架构不佳。哈希表本身有许多不幸的特性，在并发环境中这些特性会被放大。然而，尽管存在这些缺点，哈希表在读取密集型用例中仍然是一个必要的“恶”，因为其他数据结构在性能上无法与之竞争。

一个优秀的并发哈希表需要关注以下几个重要属性：

• 读取吞吐量/延迟
• 写入吞吐量/延迟
• 内存使用

并发哈希表根据上述属性的优先级不同，可以分为多种类型。papaya 更关注读取者而非写入者。读取操作应具有极低的延迟，并且不会被慢速写入者阻塞。同时，它也非常关注整体的可预测延迟。虽然写入吞吐量可能不是最优的，但读取者和写入者都不应遭受延迟峰值。

通常，关注写入吞吐量的用例可能更适合使用其他数据结构，如哈希尝试（hash tries），这些数据结构值得进一步实验。papaya 旨在服务于读取密集型工作负载。

另一个重要的考虑因素是易于使用的 API。虽然 papaya 内部可能使用锁，但经过精心设计，其 API 是无锁的，并且不可能出现死锁。

基本设计

考虑一个基本的 RwLock<HashMap<K, V>>。这里存在几个明显的问题，最主要的是每个写操作都需要独占访问哈希表。这不仅在同步时非常昂贵，还意味着在面对单个写入者时，读取者无法继续执行。

即使在读取密集型或只读的工作负载中，RwLock 也远非理想。通过读写锁，读取者可以并行执行。然而，锁仍然是单点争用，即使是读取者也是如此。这意味着每个读操作都会尝试获取锁的独占访问权，导致大量的缓存一致性流量，并使可扩展性停滞不前。这使得读写锁对于任何可扩展的数据结构都不切实际。

我们可以通过分片（sharding）来显著提高可扩展性：

Box<[RwLock<HashMap<K, V>>]>

通过将键分散到多个映射中，并根据键的哈希值决定键进入哪个映射，我们可以将争用分散到多个锁上。这是 dashmap 使用的策略。

分片减少了争用，但远非理想。读取者仍然需要修改共享内存。虽然内存共享减少了，但它仍然是共享的，写入共享内存是昂贵的。此外，写操作仍然会阻塞读取者，这意味着即使少数写入者也会极大地影响整体可扩展性。锁通常对读取延迟分布构成重大问题，因为单个慢速写入者可能导致所有读取者的延迟峰值。

那么，我们如何做得更好呢？最简单的无锁哈希表看起来像这样：

struct HashMap<K, V> {
    buckets: AtomicPtr<[AtomicPtr<Node<K, V>>]>
}

struct Node<K, V> {
    key: K,
    value: V,
    next: AtomicPtr<Node<K, V>>,
}

这里有两个重要的层次。整个表被包裹在一个原子指针中，允许在调整大小时原子地交换它。此外，每个键值对都位于一个原子指针后面，碰撞形成一个并发链表。

使用原子指针是重要的。大多数 CPU 只支持原子读取最多 128 位的值，而不会撕裂。为了支持任意大小的键和值，条目需要被分配。这允许我们原子地交换指针。

注意，为每个条目分配是一个重大的基本设计决策。这意味着在重写负载下牺牲写入吞吐量，因为分配器压力。然而，这种权衡是值得的，因为它允许读取者在写入者访问表时并发访问。这是 C# 的 ConcurrentDictionary 采用的设计。然而，它引入了另一个关键问题。

现在每个键值对都被分配了，读取者在遍历链表时必须通过指针访问键，这意味着缓存未命中。在并发环境中，缓存未命中的成本更加严重，因为条目正在被写入者修改，导致争用。我们希望尽可能少地访问共享内存。

缓存局部性也是大多数现代哈希表选择开放寻址（open addressing）而不是封闭链（closed chaining）的原因。通过开放寻址，每个桶包含一个键值对。写入者不是使用链表来解决碰撞，而是探测后续桶，直到找到一个空桶。当读取者在序列中遇到一个空桶时，他们可以停止探测，知道键不在映射中。这允许整个表由一个扁平的 [(K, V)] 表示，使访问非常缓存友好。

乍一看，开放寻址在并发环境中似乎没有提供太多好处，因为条目仍然被分配。

struct HashMap<K, V> {
    buckets: AtomicPtr<[AtomicPtr<(K, V)>]>
}

然而，它为关键优化打开了大门。除了条目数组，我们还可以包含一个称为元数据表的第二个数组。每个键值对都有一个对应的元数据字节，包含其哈希值的子集。

struct HashMap<K, V> {
    table: AtomicPtr<Table<K, V>>
}

struct Table<K, V> {
    metadata: [AtomicU8],
    entries: [AtomicPtr<(K, V)>],
}

元数据表允许读取操作非常缓存高效，因为它们可以探测元数据而不是条目。注意，因为我们只有 8 位元数据，仍然有可能出现假阳性，但这仍然是一个巨大的改进。

元数据表存在于大多数现代哈希表中，包括 std::collections::HashMap 的基础瑞士表（swiss tables）。在并发哈希表中，它们更加关键，因为条目被分配，直接探测条目是不切实际的。

探测策略

开放寻址表的最大决策之一是探测策略。探测策略决定了如果初始桶已满，则按什么顺序探测桶。虽然有许多有趣的策略，如布谷鸟（cuckoo）、罗宾汉（robin-hood）或跳房子（hopscotch）哈希，但这些策略在并发实现中很昂贵，需要额外的同步，尤其是在有元数据表的情况下。

另一方面，元数据表的存在意味着探测变得相对便宜，因此更简单的探测策略更有意义。例如，hashbrown 使用混合线性和二次探测策略。使用 SIMD 例程并行探测 16 个元数据条目，而组内探测是二次的。这允许缓存高效的探测，同时避免线性探测的常见陷阱——主聚类。

不幸的是，并发哈希表中的 SIMD 探测存在一个问题——原子加载必须对齐。这意味着我们不能简单地从探测位置加载接下来的 16 个条目，我们必须加载对齐的组。不幸的是，在我的测试中，当需要这种对齐时，SIMD 探测是不值得的。事实上，瑞士表在切换到未对齐读取时看到了 20% 的性能提升，因为哈希位的熵增加了。出于这个原因，papaya 坚持使用传统的二次探测策略，以及典型的快速模数的二的幂容量。

负载因子

哈希表的另一个重要部分是其负载因子。负载因子决定了哈希表何时太满，应该调整大小。确定是否达到负载因子需要跟踪哈希表中的条目数量。然而，在并发环境中维护计数器非常昂贵，因为它形成了另一个单一的争用点！虽然计数器仅由写入者访问，但它仍然对性能影响很大。

有几种方法可以解决这个问题。最明显的是分片长度计数器。虽然这减少了增加计数器时的争用，但它使访问总长度更加昂贵。papaya 使用分片计数器并公开长度以方便使用，但在每次写入时访问所有计数器分片是不可行的。

一个解决方案是依赖概率计数器进行调整大小，类似于 HyperLogLog。然而，papaya 采用了不同的方法，灵感来自这篇文章。哈希表不是设置负载因子，而是根据表的容量设置最大探测限制。一旦达到限制，表就会调整大小。探测限制基于表容量的 log2，倾向于约 80% 的负载因子。我对探测限制与其与负载因子的关系的正式化很感兴趣，但这个数字在实践中似乎非常一致，并且避免了同步并发计数器的需要。

删除

在开放寻址中，你不能简单地从链表链中取消链接一个值来删除它。相反，你通常放置一个称为墓碑（tombstone）的标记值。有更复杂的删除方案，如后移删除（backshift deletion），但这些在引入额外同步的情况下很难在并发环境中实现。

墓碑有点不幸，因为它们会导致更长的探测序列。然而，如果插入在探测序列中遇到墓碑，则可以为新键重用该条目。这在一定程度上缓解了问题。

然而，并发删除在有元数据表的情况下存在问题。想象以下事件序列：

1. 线程 1 插入键 “a”
2. 线程 2 删除键 “a”
3. 线程 2 在同一槽中插入键 “b”
4. 线程 2 写入元数据 0b01
5. 线程 1 稍后写入元数据 0b10

同步条目及其元数据位于不同的位置，使得在槽被重用时难以同步。一个解决方案是为每个条目存储一个锁，在存储条目及其元数据时获取该锁。这确保了同步，但对写入者是一个显著的减速。

然而，还有另一个选择。我们可以通过不允许条目在删除后被重用来完全消除问题。这意味着只有一个元数据值被写入给定的槽，因此我们不必担心同步。这种方法被 Cliff Click 著名的无锁哈希表采用，尽管它用于同步键和值而不是元数据。然而，这是一个相当大的权衡，因为这意味着插入和删除大量键的工作负载必须更频繁地调整大小以释放条目。我们稍后会更多地讨论调整大小。

内存回收

到目前为止，我们忽略了一个大问题，内存回收。在无锁环境中，并发删除变得更加困难。特别是，没有明显的方法可以确定何时可以安全地释放对象，因为任意读取者可能正在并发访问它。

这个问题的明显解决方案是某种形式的引用计数。不幸的是，引用计数的成本类似于读写锁，因为每次访问都需要修改共享内存。特别是，这对于同步访问表本身是灾难性的，因为它为所有操作创建了一个单一的争用点。

有许多算法可以解决这个问题。一个流行的方案是危险指针（hazard pointers），它强制线程通过线程本地指针列表宣布对给定对象的访问。虽然这可以非常节省内存，但对于读取者来说也非常昂贵。

另一个算法是基于时代的回收（epoch-based reclamation）。线程跟踪它们所处的时代，基于偶尔递增的全局时代计数器。对象在给定的时代中被退役，一旦所有线程都离开了该时代，它们就可以安全地回收。

EBR 非常轻量。然而，它不如其他算法内存高效，因为它按批次跟踪对象。虽然这对于提高性能可能是一个可接受的权衡，但 EBR 有一些其他缺点。

EBR 和相关方案的最大缺点是回收非常不可预测。一批对象只能在所有线程离开时代后回收。这意味着要回收一批对象，你必须检查所有活动线程的状态，这非常昂贵，并且需要访问线程本地的共享内存。这导致在尝试回收的频率和性能之间进行权衡。例如，crossbeam-epoch crate 每 128 次操作检查一次垃圾。重要的是，检查必须由读取者和写入者执行，导致回收不可预测地触发，并导致较差的延迟分布。

因为 papaya 分配每个条目并且不重用墓碑，内存效率是一个非常重要的因素。不幸的是，在我测试中，现有的内存回收算法并不达标。

几年前，我偶然发现了 hyaline，一个解决了很多这些问题的算法，后来在 seize crate 中实现了。在 hyaline 中，昂贵的跨线程检查在一批对象退役时执行。该批次仅一次传播到所有活动线程。在初始退役阶段之后，使用引用计数回收批次。这个回收过程更加可预测，因为线程可以在每次操作之前检查新垃圾，而不会牺牲性能。在实践中，由于工作负载平衡的并行性收益，它往往优于 EBR。

Hyaline 还解决了 EBR 的另一个问题，鲁棒性。在 EBR 中，单个慢速线程可以阻止给定时代中所有对象的回收。Hyaline 通过跟踪对象创建的时代来解决这个问题，在回收新对象时过滤掉慢速线程。这些额外的属性使 hyaline 成为 papaya 的完美选择。

调整大小

一旦哈希表太满，它就需要调整大小，将所有键和值迁移到更大的表中。在并发环境中，这可能非常昂贵。为了减少调整大小的成本，多个线程可以并行帮助迁移和复制条目。

在实现并发调整大小时有许多权衡。理想情况下，读取者不应受到调整大小的影响。这需要所有写入者在继续前进之前完成迁移，为读取者提供单一的事实来源。然而，调整大小可能很慢，为写入者引入延迟峰值。对于大型表，调整大小可能需要数百毫秒甚至几秒钟才能完成。这对于许多应用程序来说是不可接受的延迟。

为了避免延迟峰值，我们可以实现增量调整大小，其中条目逐渐复制到新表中，而不是阻塞。这是单线程哈希表（如 griddle crate）也采用的方法。

管理两个表的并发状态很棘手，但 papaya 实现了一个迁移算法，允许对旧表进行并发更新，并将条目原子地复制到新表中。这意味着在迁移期间，许多操作在搜索条目时必须检查新旧表。然而，这是一个通常可以接受的权衡，因为调整大小操作通常不常见，并且在短时间内稍微增加延迟比极端延迟峰值更好。

增量调整大小还抵消了永久墓碑的影响，因为调整大小的成本被分摊。然而，为了灵活性，papaya 支持两种调整大小模式作为选项。当写入吞吐量或读取延迟是主要关注点时，可以使用阻塞调整大小。

注意，调整大小是 papaya 唯一不是无锁的情况。分配下一个表涉及获取锁以防止过多的分配器压力。此外，如果键正在被复制到新表中，写操作可能会阻塞。papaya 在这种情况下使用混合自旋策略，然后回退到阻塞。然而，注意复制条目不涉及分配，通常非常快。阻塞是一个有意的设计决策，因为真正的无锁调整大小非常昂贵，但已采取措施减轻可能由此产生的任何问题。

额外功能

除了上述性能特性外，papaya 还有一些独特的功能。

由于 papaya 不包含锁，执行复杂操作更具挑战性。相反，papaya 公开了许多原子操作。其中最强大的是 HashMap::compute，它允许使用比较和交换（CAS）函数更新条目：

let map = papaya::HashMap::new();

let compute = |entry| match entry {
    // 如果值是偶数，则删除该值。
    Some((_key, value)) if value % 2 == 0 => {
        Operation::Remove
    }

    // 如果值是奇数，则递增值。
    Some((_key, value)) => {
        Operation::Insert(value + 1)
    }

    // 如果键不存在，则不执行任何操作
    None => Operation::Abort(()),
};

map.pin().compute('A', compute);

这允许在缺乏锁的情况下执行复杂操作。

papaya 的另一个独特功能是异步支持。dashmap 的一个最大缺点是它使用同步锁，因此从 Dashmap 中持有对项目的引用会导致死锁。由于 papaya 具有无锁 API，因此不可能出现死锁。然而，访问映射仍然需要获取内存回收的守卫，即上述示例中的 pin 调用。这个守卫是 !Send，因为它与当前线程的内存回收状态绑定。然而，papaya 还公开了拥有的守卫，它们是 Send 和 Sync，独立于任何给定线程。这些创建起来更昂贵，但在使用工作窃取调度程序时允许跨 .await 点持有：

async fn run(map: Arc<HashMap<i32, String>>) {
    tokio::spawn(async move {
        let map = map.pin_owned(); // <--
        for (key, value) in map.iter() {
            tokio::fs::write("db.txt", format!("{key}: {value}\n")).await;
        }
    });
}

异步支持是我非常兴奋的功能，据我所知，现有的并发哈希表中没有这个功能。

比较

有许多现有的并发哈希表 crate。然而，与 papaya 相比，大多数在读取吞吐量和可预测延迟方面表现不佳。此外，异步支持是一个难以找到的功能。然而，在某些情况下，你可能希望考虑不同的 crate。

• dashmap 具有基于 hashbrown 的非常简单的设计。它还非常接近 std::collections::HashMap 的 API。对于写入密集型工作负载，它可能提供更好的性能。它在内存使用方面也开销更低。
• scc 类似于 dashmap，但更积极地分片桶锁。对于写入密集型工作负载，它应该是你的首选，尽管代码本身似乎相当复杂且难以审计。
• flurry 是一个带有条纹锁但无锁读取的封闭寻址表。然而，由于分配器压力，它在性能和内存使用方面存在问题。papaya 在大多数工作负载中应该优于 flurry。
• evmap 非常适合极端读取密集型用例。然而，它是最终一致的，写入相对昂贵。即使在 99% 读取密集型工作负载下，可扩展性在负载下也会受到影响。
• leapfrog 提供了出色的性能，但仅限于 64 位 Copy 值。这一限制在学术文献中很常见，并且 leapfrog 为任意值类型回退到自旋锁，这对于通用映射来说是不幸的。

有关更多信息，请参阅基准测试，但请记住，始终根据你自己的工作负载进行测量。