并发数据结构设计演练

QuestDB是一个时间序列数据库，提供快速的摄取速度、InfluxDB 线路协议和 PGWire 支持以及 SQL 查询语法。QuestDB 主要是用 Java 编写的，我们学到了很多困难而有趣的教训。我们很高兴与您分享。

研究数据结构

并发数据结构设计很难。该博客提供了有关构建非常有利于读者的专用并发地图的指导。本文不仅会介绍另一种现成的数据结构。相反，我将引导您完成设计过程，同时解决实际问题。我什至会介绍我一路上遇到的死胡同。对于对并发编程感兴趣的程序员来说，这是一个侦探故事。

在本文结束时，我们将拥有一个用于在本机内存中存储数据 blob 的并发映射。该映射在读取路径上是无锁的，并且在内存分配方面也非常保守。让我们开始吧！

本文假设您具备 Java 或类 Java 编程语言的基础知识。

问题

我需要一个并发映射，其中键是字符串，值是固定大小的 blob（公共加密密钥）。这听起来像是JDK 中普通的旧式 ConcurentHashMap 的工作，但有一点不同：blob 必须在 Java 堆之外可用。

为什么？这样调用者就可以获取指向 blob 的指针并通过 JNI 将其传递给 Rust 代码。然后 Rust 代码使用公钥来验证数字签名。

这是该界面的简化版本：

interface ConcurrentString2KeyMap {
  void set(String username, long keyPtr);
  long get(String username);
  void remove(String username);
}

该set()方法接收用户名和指向密钥的指针。映射的寿命比它接收到的指针的寿命长，因此它必须将接收到的指针下的内存复制到自己的缓冲区中。换句话说：该get()方法必须返回一个指向该内部缓冲区的指针，而不是用于 的原始指针set()。

我可以假设该get()方法将在热路径上频繁使用，而突变方法将很少被调用，并且永远不会在热路径上被调用。

读者大致将如何使用它：

boolean verifySignature(CharSequence username, long challengePtr, int
challengeLen, long signaturePtr, int signatureLen) {
  long keyPtr = map.get(username);
  return AuthCrypto.verifySignature(keyPtr, PUBLIC_KEY_SIZE_BYTES, challengePtr, challengeLen, signaturePtr, signatureLen);
}

如果没有突变，我可以只实现一个预先填充的不可变查找目录，然后就到此为止了。然而，共享可变状态带来了两类挑战：

1. 指针生命周期管理
2. 地图内部的一致性

第一个问题归结为确保当 amap.get()返回指针时，该指针必须保持有效，并且其后面的内存在需要的时间内不得更改。在我们的例子中，这意味着直到AuthCrypto.verifySignature()返回。

第二个问题是关于并发数据结构设计的，我们稍后将更详细地讨论这一点。我们
先探讨第一个问题。

指针生命周期管理

如果我们的映射值只是 JVM 管理的常规对象，那么事情可能会很简单：map.get()返回对对象的引用，然后它可能会忘记get()曾经发生过这个调用。和方法只会删除映射对值对象的引用，并且永远不会更改已返回的对象remove()。set()简单的。但这不是我们的情况，我们正在使用堆外内存，并且必须自己管理它。

从根本上来说，有两种方法可以解决：

1. 更改get()合约，使其不返回指针。相反，它从外部接收一个指针并将值复制到那里。
2. get()仍然返回一个指针，但映射保证其背后的内存保持不变，直到调用者通知映射它已完成并且不再使用该指针。

选项 1：调用者拥有目标内存

第一个选项看起来很有趣。新合同可能如下所示：

interface ConcurrentString2KeyMap {
  void set(String username, long srcKeyPtr);
  void get(String username, long dstKeyPtr);
  void remove(String username);
}

调用者将拥有该dstKeyPtr指针，并且映射会将密钥从其内部复制到该指针，并忘记get()曾经发生过此调用。

起初这听起来相当不错，直到我们意识到它只是把罐头踢了下去：它强制每个调用线程维护自己的缓冲区以传递给get(). 如果调用者都是单线程的，这仍然很容易：每个调用对象都拥有一个要传递给 的缓冲区get()。

但如果调用函数本身是并发的，那就会变得更加复杂。我们必须确保每个调用线程使用不同的缓冲区。

理想情况下，缓冲区应该在堆栈上分配，但这是 Java，所以这是不可能的。我们当然不希望
为每次调用在进程堆中分配/取消分配新的缓冲区。

那么还剩下什么呢？汇集？那很乱。

线程局部？更混乱且更难限制缓冲区的数量。

也许选项 1 并不像乍看起来那样有趣。

选项 2：生命周期通知

让我们探讨第二个选项。合同与原始提案中概述的相同：long get(String username)。我们必须确保指针后面的内存保持不变，直到完成为止。

最简单的事情就是使用读写锁。

每个映射都会有一个关联的读写锁，然后读者在调用之前获取读锁get()，并仅在从 返回后释放它AuthCrypto.verifySignature()：

boolean verifySignature(CharSequence username, long challengePtr, int
challengeLen, long signaturePtr, int signatureLen) {
  map.acquireReadLock();
  try {
    long keyPtr = map.get(username);
    return AuthCrypto.verifySignature(keyPtr, PUBLIC_KEY_SIZE_BYTES, challengePtr, challengeLen, signaturePtr, signatureLen);
  } finally {
    map.releaseReadLock();
  }
}

变异器只需在调用set()or之前获取写锁remove()。这种设计不仅推理简单，而且实现起来也很简单。

假设只set()改变remove()内部状态，我们可以采用单线程映射实现，它就会做到这一点。但有一个问题...它违反了我们最初的要求！

读者经常处于热路径上，我们希望他们保持无锁状态。所提出的设计会在地图更新时阻止读者，因此这是不行的。

我们可以做什么？我们可以将锁定模式更改为更细粒度 - 我们可以锁定特定条目，而不是锁定整个映射。虽然这会改善实际行为，但也会使地图设计复杂化，并且当更新相同的密钥时，读者仍然可能被阻止。

还有什么？我们可以使用乐观锁定模式，但这
会带来其自身的复杂性。

越来越明显的是，指针生命周期管理必须与内部映射实现协同工作。那么这次的演习就完全没有结果了吗？不完全的。

我们仍然可以重用一种设计思想：地图用户必须
明确通知他们不再使用指针。

让我们探索如何
设计地图内部！

为无锁读者设计地图

我认为自己是一位经验丰富的多面手。我对并发编程、分布式系统和各种其他领域有所了解，但我并不真正专注于任何特定主题。

是万事通却一事无成？大概。因此，当我在考虑合适的数据结构时，我做了每个通才在 2023 年都会做的事情：问 ChatGPT！

我很惊讶 GPT 意识到我的意思是写“单一作者”而不是“单一读者”，我认为这是 GPT 知道它在说什么的证据！