Deno KV 内幕：为现代网络构建数据库

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 之上构建 Deno KV，FoundationDB 是 Apple 的开源分布式数据库，在 iCloud 和 Snowflake 中使用，因为它非常适合构建可扩展的数据库解决方案：它通过确定性模拟进行了彻底验证，可扩展且高效，并提供事务性键值存储 API。

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

Deno KV 不仅在数据方面是多租户的，而且在配置方面也是多租户的。不同的用户有不同的复制设置、备份策略和吞吐量配额。FoundationDB 没有处理此问题的原生机制。
我们希望 Deno KV 完全是 JavaScript 原生的，并使用 JavaScript 类型。例如，Deno KV 可以存储带符号的 varint（bigint），我们希望支持对它们进行原子求和操作，但 FoundationDB 本身不支持对 varint 进行原子求和。
为了最大限度地减少计算和数据之间潜在的无界延迟，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。如果在执行操作时为假，则整个操作将被丢弃
写入命令：任何对键的 .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 现在处于公开 Beta 阶段。

注册 Deno Deploy 并免费获得对零配置、全球分布式数据库的访问权限。