论文导读：Building a Database on S3

TL;DR

这篇论文研究如何把 Amazon S3/SQS 这类早期云服务当作数据库底层存储来使用。它把小对象聚合成 page 存到 S3，用 SQS 保存 redo log 和 pending update，再通过异步 checkpoint 合并更新。实验显示，这种方法可以降低前台事务延迟，但一致性、原子性和数据新鲜度都需要额外成本来换。

为什么值得读？

这篇论文值得读，不是因为今天应该照搬它的 S3/SQS 协议，而是因为它很早就把一个后来云原生数据库反复遇到的问题讲清楚了：对象存储很适合做便宜、可靠、可扩展的持久层，但它天然不提供数据库真正需要的细粒度更新、事务语义和索引一致性。

它对理解计算存储分离、对象存储上的数据库、lakehouse 表格式、serverless database、云原生存储引擎都有启发。尤其适合用来观察：当底层只给你 get/put、弱一致性和较高延迟时，上层数据库协议到底要补哪些东西。

如果只记住一个阅读理由：这篇论文展示了“对象存储便宜可靠”背后隐藏的数据库语义成本。

这篇论文一句话讲什么？

它研究把 S3 当数据库存储层时，性能、成本和一致性之间如何互相牵制。

这篇论文试图解决什么问题？

论文表面上要解决的问题是：S3 当时主要用于图片、视频、备份等大对象和低频更新场景，那么它是否也能支撑通用数据库应用，尤其是小对象、频繁更新、并发客户端、索引和提交协议？

深层矛盾在于：S3 提供高可用、可扩展、持久化和按量付费，但它不是传统磁盘，也不是数据库。传统数据库假设自己可以控制缓冲池、日志、锁、页面写回和恢复协议；S3 则只暴露远程对象读写接口，而且一致性语义较弱。

旧方法不够，是因为如果直接把每个小对象作为 S3 对象读写，延迟和成本都很差；如果把多个记录聚合成 page，又会遇到多个客户端并发更新同一个 page 时互相覆盖的问题。传统共享磁盘数据库可以靠集中协调解决，但这会破坏论文想保留的高可用和可扩展性。

作者因此把问题转化成一个更具体的研究问题：不追求完整 ACID 和 serializability，而是在 S3/SQS 之上设计 read、write、commit、checkpoint、B-tree 和弱一致性协议，尽量保留 durability、atomicity、monotonic reads / writes 等部分数据库属性。

这篇论文的边界很清楚：它不是要证明 S3 可以替代完整数据库，而是研究在弱一致对象存储上补出一部分数据库语义需要什么代价。

有哪些相关研究？

大致可以分成四条路线：

传统数据库并发控制与恢复协议 这类方法通过锁、日志、事务管理、恢复协议来保证一致性、隔离性和崩溃恢复。局限是它们通常假设数据库系统能控制底层存储和并发调度，不适合大量客户端直接围绕 S3 协作。
分布式系统一致性模型 这类研究关注 strict consistency、eventual consistency、monotonic reads、monotonic writes 等不同一致性级别。局限是弱一致性虽然提升可用性和扩展性，但会把复杂性转移给上层协议和应用。
把 S3 作为集中式数据库存储模块 论文提到已有做法是把 S3 放到 MySQL 这类集中式数据库下面，当作存储模块或备份层。局限是这种方式仍然依赖中心化数据库，不能充分讨论大量无状态客户端直接使用 S3/SQS 的协议问题。
utility computing / grid computing / peer-to-peer storage 这些系统关注弹性资源、节点失败、分布式存储和高可用。局限是它们通常不直接处理数据库 page、B-tree、commit protocol 和事务属性。

这篇论文的区别在于：它把 S3/SQS 当作公共底层服务，在上面设计低层数据库协议，而不是只把 S3 当大对象仓库、备份盘或中心化数据库的外部存储。

论文的核心方法是什么？

论文的核心方法是：把记录级更新转换成 redo log，先写入 SQS 队列，再由异步 checkpoint 把日志合并到 S3 page 中。输入是记录读写和索引操作，核心转换是“记录更新 → 日志队列 → 页面合并”，输出是最终写回 S3 的数据页和索引页。

记录读写请求 → redo log / PU Queue / checkpoint → S3 page 与 B-tree page

**Page-based storage：**把小记录聚合进 page，避免频繁读写大量 S3 小对象。
**B-tree on S3：**把 B-tree 节点也作为 S3 page 存储，用于主索引和二级索引。
**SQS redo log：**commit 时先写 pending update queue，再异步合并到 S3。
**事务属性补偿：**用 LOCK Queue、ATOMIC Queue、timestamp 和 counter 补一部分一致性语义。

论文是怎么解决这个问题的？

论文的解决方案可以拆成三层：

第一层：把 S3 抽象成数据库 page store 它解决的是 S3 不适合频繁小对象访问的问题。论文把多个 record 聚合到 page，page manager 负责缓存、读写和刷新，record manager 提供记录级 API。关键假设是：page 粒度比单条记录更适合 S3 的访问模型。
第二层：用 SQS 队列承接更新和提交 它解决的是多个客户端直接写回同一个 page 容易覆盖的问题。客户端提交时不直接写 S3 page，而是把 redo log 写入 pending update queue。之后 checkpoint 再读取 log，合并到对应 page。关键假设是：redo log 是幂等的，即重复应用不会破坏最终状态。
第三层：用额外协议补弱事务属性 Basic Commit Protocol 只能提供 eventual consistency 和 durability，不能保证完整 atomicity。论文进一步引入 ATOMIC Queue 支持事务原子性，用客户端时间戳和计数器支持 monotonic reads / writes。关键假设是：应用可以接受异步可见性和弱一致性，而不是强制要求完整 ACID。

论文做了哪些实验？

论文使用 TPC-W benchmark 的一个子集模拟在线书店 workload。每个复杂客户事务大致包括三步：读取客户记录，搜索 6 个产品，然后对其中 3 个产品下单。实验目标是比较不同一致性协议下的事务运行时间和美元成本。

协议	核心做法	实验意义
Naive	commit 时直接把 dirty pages 写回 S3	简单 baseline，但存在 lost update
Basic	更新先进入 SQS PU Queue，再异步 checkpoint	评估基本日志队列协议
Monotonicity	在 Basic 上加入 monotonic reads / writes	评估弱一致性增强成本
Atomicity	在 Basic 上加入 ATOMIC Queue	评估原子提交语义成本

主要实验有三组：

Experiment 1：事务运行时间 指标是每个事务的平均时间和最大时间。Table 3 显示：Naive 平均约 11.3 秒，Basic 约 4.0 秒，Monotonicity 约 4.0 秒，Atomicity 约 2.8 秒。Atomicity 更快主要是因为它在提交时可以批量发送更少的 SQS 消息，而不是因为“一致性越强越快”。
Experiment 2：每 1000 次事务的美元成本 Table 4 显示：Naive 约 0.15 美元，Basic 约 1.8 美元，Monotonicity 约 2.1 美元，Atomicity 约 2.9 美元。也就是说，延迟可以通过协议设计降低，但更强语义需要更多 SQS/S3 交互，成本明显上升。
Experiment 3：改变 checkpoint interval Figure 3 展示了 Basic 和 Atomicity 在不同 checkpoint interval 下的成本变化。checkpoint interval 越短，更新越快被合并到 S3，但成本越高；interval 增大后，成本下降并逐渐变平。事务运行时间不受该参数直接影响，因为 checkpoint 在事务之外异步执行。

此处建议插入 Table 3 / Table 4：用于展示四种协议在事务运行时间和每 1000 次事务成本上的对比。

实验结果说明了什么？

论文结果支持的是：把更新先写成 redo log，再异步合并到 S3 page，可以降低前台事务等待时间。Naive 方法慢，是因为它在 commit 阶段直接写回所有 dirty pages；Basic、Monotonicity 和 Atomicity 则把部分工作推迟到 checkpoint。

论文结果也支持另一个结论：更强的数据库语义不是免费的。Atomicity、Monotonicity、checkpoint freshness 都需要额外队列、元数据和请求操作，因此美元成本上升明显。尤其在当时的 AWS 计费模型下，SQS 交互本身就会成为重要成本来源。

论文结果没有证明 S3 适合高性能事务处理。作者的结论更克制：utility computing 当时不适合 high-performance transaction processing，更适合部分 Web 2.0 和交互式应用。

这些结论不能直接外推到今天所有对象存储数据库。S3/SQS 的性能、价格和一致性语义已经变化，现代系统也有 DynamoDB、Aurora、Snowflake、Iceberg、Delta Lake 等不同技术路线。但“对象存储提供低成本持久化，上层数据库语义需要额外协议补偿”这个核心判断仍然成立。

这篇论文的主要贡献是什么？

**建模贡献：**把“在 S3 上构建数据库”拆成 page、record manager、page manager、B-tree、redo log、commit 和 checkpoint 等具体问题。
**方法贡献：**提出用 SQS pending update queue 保存 redo log，再通过异步 checkpoint 合并到 S3 page。
**一致性贡献：**展示如何在不追求完整 ACID 的前提下，实现 durability、atomicity、monotonic reads 和 monotonic writes。
**实验贡献：**用 TPC-W 子集量化不同协议在事务延迟、美元成本和 checkpoint interval 上的 trade-off。
**边界贡献：**明确指出 strict consistency 和完整 DB-style transactions 会破坏论文追求的可扩展性和高可用性。

局限与现实校准

时间背景很旧。 论文基于 2007 年左右的 AWS 服务状态，S3/SQS 的性能、价格、一致性语义和现代云数据库生态都已经变化，具体数字不能直接用于今天的工程判断。
workload 较窄。 实验只使用 TPC-W 的一个在线书店事务子集，不能代表复杂 OLTP、高热点写、多表 join、长事务或分析型查询。
Naive baseline 偏弱。 Naive 方法本身存在 lost update，甚至不能达到 Basic Protocol 的 eventual consistency，因此它更像“直观但不正确”的基线。
数据新鲜度依赖 checkpoint。 commit 成功不等于更新立即在 S3 page 上可见，应用必须接受“提交”和“全局可见”之间的时间差。
完整数据库工程问题没有解决。 查询优化、join、bulk load、索引重建、元数据管理、安全授权、队列积压和运维监控都没有系统展开。[推论]

可以进一步探索的问题

如果用今天的 S3/SQS 重新实现这套协议，哪些实验结论会改变，哪些 trade-off 仍然存在？
PU Queue / LOCK Queue / ATOMIC Queue 和现代 WAL、commit log、transaction coordinator 有什么对应关系？
B-tree on S3 在热点 key、range scan、频繁 split 的场景下会出现什么瓶颈？
checkpoint interval 能不能根据 workload 自适应调整，而不是手动固定？
如果把 SQS 换成 Kafka、Pulsar、DynamoDB Streams 或 cloud-native queue，协议会如何变化？
这篇论文和 Aurora、Snowflake、Iceberg、Delta Lake 的关系是思想延续还是问题重构？
如果要复现这篇论文，应该复现原始 S3/SQS 协议，还是抽象出对象存储 + 队列 + checkpoint 模型？
对资源受限环境中的轻量级 KV store 来说，这篇论文的日志合并思想是否有迁移价值？

如果您想深入了解本论文，请点击：深入理解