Deno KV 内部机制：为现代 Web 构建数据库

Deno 旨在通过内置的现代工具、直接访问 Web 平台 API 和通过 npm 导入模块的能力简化 Web 和云开发。Web 应用程序通常需要一些持久应用程序状态。设置数据库涉及许多配置步骤以及随后集成 ORM 或其他系统。

如果您无需任何预先设置即可访问这样的数据库，会怎么样？这就是 Deno KV 所允许您做的。

const kv = await Deno.openKv();
const userId = crypto.randomUUID();
await kv.set(["users", userId], { userId, name: "Alice" });

为什么要构建 Deno KV？

Deno 运行时不仅以 deno 可执行文件的形式在您的本地机器上运行，而且还在我们的 Deno Deploy 云平台上运行，该平台允许您将 Deno 应用程序部署到世界各地的许多区域。这种全局部署最大程度地减少了用户与应用程序计算之间的延迟，这可以极大地提高应用程序的性能。

我们知道我们想要为 Deno 构建一个数据库，因为我们从许多客户那里听到了一个非常简单的问题：除非您的应用程序数据也是全局分布的，否则您将无法利用通过分布式计算获得的性能优势。

此外，由于 Deno 运行时旨在在本地单实例场景或全局多实例场景中运行，因此我们为其中一个场景引入的任何 API 也应该在另一个场景中运行良好。这使得您能够轻松地在本地开发和测试您的应用程序，然后将其全局部署，而无需更改代码或添加任何配置。

这导致我们制定了 Deno KV 的几个设计目标

可扩展性：一个分布式数据库，可以处理大量数据，具有高吞吐量
高性能：计算和数据库之间最少的延迟往返，以最大程度地减少网络延迟的影响
JavaScript 原生：一个旨在从 JavaScript 和 TypeScript 使用的数据库，其 API 本地使用 JavaScript 类型
原子事务：一个提供原子操作以确保数据完整性和实现复杂应用程序逻辑的数据库
在本地和全局无缝工作：一个在单实例和多实例场景中都能完美工作的数据库

因此，我们着手构建了两个版本的 Deno KV 系统，它们具有相同的面向用户 API。一个用于本地开发和测试的 Deno KV 版本，它建立在 SQLite 之上；另一个用于生产环境的分布式系统版本（尤其是在 Deno Deploy 上）。这篇文章介绍了 Deno KV 生产版、分布式系统版本是如何实现的。如果您对 Deno KV 的 SQLite 实现感兴趣，您可以查看源代码，因为它是开源的。

FoundationDB：可扩展、分布式、灵活且生产就绪

我们选择在 FoundationDB（Apple 的开源分布式数据库，用于 iCloud 和 Snowflake）之上构建 Deno KV，因为它非常适合构建可扩展的数据库解决方案：它经过彻底验证，具有确定性模拟，可扩展且高效，并提供事务性键值存储 API。

虽然 FoundationDB 提供了健壮分布式数据库的必要机制，但在将其转换为我们 Deno Deploy 平台中可用的无缝 JavaScript 原生体验时，仍然存在一些挑战。

Deno KV 不仅在数据中，而且在配置中也是多租户的。不同的用户拥有不同的复制设置、备份策略和吞吐量配额。FoundationDB 没有原生机制来处理这种情况。
我们希望 Deno KV 能够完全使用 JavaScript 原生，并使用 JavaScript 类型。例如，Deno KV 可以存储带符号的变体（bigint），我们希望支持对这些变体进行原子求和操作，但 FoundationDB 本身不支持对变体进行原子求和操作。
为了最大程度地减少计算和数据之间可能存在的无限制延迟，Deno KV API 是围绕非交互式事务（即原子操作）设计的，而 FoundationDB 提供了乐观交互式事务。即使可能，在 FoundationDB 之上实现 Deno KV API 也会产生不必要的开销。

这些限制导致我们设计了一个基于 FoundationDB 的新系统，我们称之为“事务层”。它以分布式方式执行事务处理和跨区域数据复制，同时仍然将分布式数据库的困难方面委托给 FoundationDB：分片、集群内的同步复制、确保事务的序列化和线性化处理，以及持久存储数据。

Deno Deploy Transaction Layer that interfaces between Deno Deploy isolates and FoundationDB — 来自 Deno Deploy 的每个 Deno KV 命令都将在我们的事务层中进行处理和优化，然后提交到 FoundationDB。

让我们深入了解我们如何为原子性、最小延迟和高并发性设计我们的事务层。

原子操作，最少的网络请求

原子操作，通常是交互式事务，也就是说它们需要多次向数据库请求才能保证原子性。

但是，对于全局分布式数据库，交互式事务的成本很高。如果写操作需要在计算服务器和数据库区域之间进行多次往返，那么执行多个写操作的 Web 应用程序可能会遇到很高的网络延迟。

Non-interactive atomic operation in global Deno KV

为了最大程度地减少延迟，我们设计了全局 Deno KV 为非交互式——所有事务都应该在一到两次网络往返内完成。我们通过将所有原子写入封装到“包”中来实现这一点，其中包含条件、写入命令和无冲突变体

条件：为了保证原子性，我们会检查密钥的 versionstamp。如果在执行操作时它为 false，则整个操作将被丢弃
写入命令：对密钥的任何 .set() 或 .delete() 操作
无冲突变体：任何接受密钥的旧值并返回新值的函数。例如，变体类型 .sum() 会将提供的操作数添加到旧值中

为了创建此“包”，Deno KV 要求所有原子操作按照 .atomic() 进行链式连接

const kv = await Deno.openKv();
const change = 10;

const bob = await kv.get(["balance", "bob"]);
const liz = await kv.get(["balance", "liz"]);
if (bob.value < change) {
  throw "not enough balance";
}

const success = await kv.atomic()
  .check(bob, liz) // balances did not change
  .set(["balance", "bob"], bob.value - change)
  .set(["balance", "liz"], liz.value + change)
  .commit();

这种原子操作的 API 设计确保了计算和数据库之间最少的往返，以实现最佳性能。

构建在 FoundationDB 的无锁系统之上

“锁” 在数据库中是确保数据完整性的机制。这些机制只允许一个事务修改或访问数据。相反，无锁系统允许并发进程访问和修改数据，从而在不牺牲数据完整性的情况下提供并行性和可扩展性。

尽管 FoundationDB 使用的是无锁设计，但简单地将冲突检查机制委托给 FoundationDB 会导致延迟问题，尤其是在原子操作执行无法下推到底层数据库原语的无冲突变体时。

await kv.atomic().sum(["visitor_count"], 1n).commit();

此原子操作无法下推，因为 FoundationDB 本身不理解可变大小的整数类型（如 JS bigint），因此没有为此类型实现任何无冲突变体操作。

为了最大程度地提高原子操作的性能和并发性，我们构建了 Deno KV 事务层，该层管理原子操作的全局顺序。对于由该事务层接收的每个事务，

事务将由排序器分配一个事务序列号（“TSN”，一个单调递增的整数，其顺序等效于原子操作的线性化顺序）。
事务将与其他事务一起批处理，评估器从这些事务中构建一个图形，该图形描述了所有条件、写入命令和无冲突变体之间的关系。然后，评估器以最大并发性处理图形，直到每个图形节点的值都已知。
最后，事务将由写入器提交到 FoundationDB。

排序器、评估器和写入器是独立的组件，它们协同工作以处理大量操作。但是我们如何才能从这条流水线中榨取更多的性能呢？

利用推测执行加速操作

推测执行是一种最大化指令处理吞吐量的技术，其中会完成一些可能不需要的工作。

Deno KV 的事务层 使用这种技术，事务以集中方式分配全局顺序，但在其他地方进行乱序处理。然后，事务的输出在事务持久化到磁盘之前，就会被推测性地用于未来的事务中。事务的影响只有在提交到 FoundationDB 后才会在外部可见。

该机制的核心数据结构是“事务重排序缓冲区”，它管理事务的处理流程。

Transaction Reorder Buffer — 上面的数字表示事务序列号，每个数字下面的列表示事务层收到的单个操作。

排序器负责发出在某个时期内连续的单调整数。虽然它是每个 KV 数据库的单例，但排序是一种非常便宜的操作，因为它只是对内存中的原子计数器进行增量操作。排序器只需要等待上一个排序器提交（绿色）。

评估器批处理处理事务。在每个批处理中，评估器都会构建一个“数据流子图”，描述所有条件、写入命令和无冲突变异之间的关系。这是一个确定事务是否成功或失败以及操作最终值的操作图。然后，评估器以最大并发性处理子图，直到每个图节点的值都已知。

为了更好地说明这种数据流子图（它在一个无锁系统中实现了高并发），让我们看一个例子。

// Client 1 is updating the login of user UID1 from “alice” to “bob”
await kv
  .atomic()
  .check({ key: ["users", UID1], versionstamp: V1 })
  .check({ key: ["user_by_login", "bob"], versionstamp: null })
  .set(["users", UID1], user1)
  .set(["user_by_login", "bob"], UID1)
  .delete(["user_by_login", "alice"])
  .commit();

// Client 2 is creating a new user with login "bob"
await kv
  .atomic()
  .check({ key: ["user_by_login", "bob"], versionstamp: null })
  .set(["users", UID2], user2)
  .set(["user_by_login", "bob"], UID2)
  .commit();

上面的两个操作相互冲突，因此只有一个可以成功。假设第二个操作分配的 TSN 比第一个操作大，那么这就是从包含这两个操作的评估器批处理构建的数据流子图。

Data flow subgraph example — 数据流子图的示例，这是一个确定事务是否成功或失败以及操作最终值的、操作图。

这个图看起来有点复杂 - 让我们逐步分析一下。

最上面的行（包含两个 GetMetadata 框）表示来自客户端 1 的两个 .check() 命令（.check({ key: ["users", UID1], versionstamp: V1 }) 和 .check({ key: ["user_by_login", "bob"], versionstamp: null })）。它们流入水平的 AND 线，因为两个检查都需要成功。

第二行（水平 AND 线下面）显示三个 MUX（又称多路复用器逻辑门）操作，它们表示客户端 1 的 .set() 和 .delete() 命令。每个 MUX 门上面显示每个命令的输入。

.set(["users", UID1], user1) -> user1 和 [pass]
.set(["users_by_login", "bob"], UID1) -> UID1 和 [pass]
.delete(["user_by_login", "alice"]) -> [delete] 和 [pass]

请注意，[pass] 只是意味着保留旧值，因为当 MUX 门可以接受两个输入时，这些命令只有一个输入。

虽然第一个和第三个 MUX 门的输出是绿色的（最终结果），但中间的一个是蓝色的（中间结果）。请记住，最终结果不是一个值；它是一个写入函数，其输入（在图中由 ? 表示）将在创建该图后进行评估。

那么为什么会出现中间结果呢？这是因为客户端 2 的 .check() 需要在共享键 ["user_by_login", "bob"] 上断言 versionstamp。为了解决这个中间结果并得到最终结果，我们使用另一个 MUX 门，它接受中间结果和 ["user_by_login", "bob"] 的 GetMetadata。

这将我们带到了最下面一行，这里有两个 MUX 门代表客户端 2 的 .set() 命令（.set(["users", UID2], user2) 和 .set(["user_by_login", "bob"], UID2)）。从这些门，我们可以得到最终结果。

评估器从一批操作中创建此数据流子图后，它会计算结果，并将结果缓冲在内存中。这些内存中的结果可以在接下来的评估器批处理中使用，以便进行更多推测性执行，因为这些结果可能尚未在 FoundationDB 中可见。当已知提交版本 提升时，或者当我们确定可以从 FoundationDB 中读取数据时，这些内存中的结果将被丢弃。

最后，启动写入器以持久化变异。写入器也批处理处理事务。在每个批处理中，写入器将事务的结果写入底层数据库，并执行各种其他任务，例如写入复制日志和将密钥排队以供过期。

使用推测执行以及排序器-评估器-写入器管道可以帮助最大化并发性和性能，同时维护原子操作的数据完整性。

结论

Deno KV 的开发是基于现代 Web 开发的需求和 FoundationDB 提供的可能性。我们一直强调功能、可扩展性和 JavaScript 的无缝集成。通过利用 FoundationDB 的无锁系统，并引入事务层和推测执行等功能，我们的目标是同时解决性能和用户体验问题。

但是，技术和需求都在不断发展。虽然我们相信 Deno KV 背后的基础和原则，但我们也意识到了技术领域的持续进步。我们与 Deno KV 的旅程仍在继续，它由我们的愿景以及来自用户社区的宝贵反馈塑造。

展望未来，我们致力于完善 Deno KV，满足新出现的需求，并确保其在快速发展的 Web 和云环境中的适应性。我们欢迎所有开发人员尝试 Deno KV，更重要的是，分享见解和反馈，以便指导其未来的发展方向。

Deno KV 现在已进入公开测试阶段。

注册 Deno Deploy 并免费获取零配置、全球分布式数据库。