系统与数据库2020assets.amazon.science编辑精选
数百万个微型数据库
Millions of Tiny Databases
进阶 · 约 60 分钟读完前置知识：CAP 定理、分布式一致性基础、键值存储基础
导读
这篇论文介绍 Physalia，亚马逊为大规模云控制平面设计的事务性键值存储。它利用对数据中心拓扑和客户端访问模式的知识，把数据放置在最可能对特定客户端可用的位置，从而在 CAP 限制下同时为百万级客户端提供高可用性和强一致性。
HN 关注点：AWS 罕见地公开了内部控制平面的分布式系统设计细节，涉及 CAP 定理的工程化取舍，对分布式系统从业者很有吸引力。
后来怎么样
Physalia 论文发表于 NSDI 2020，成为云控制平面存储设计的代表性案例，其'爆炸半径'等术语和按客户端可用性放置数据的思路在分布式系统社区被广泛引用。
HN 评论精选
这几条评论里：支持 1 补充 2 亲历 1
亲历论文作者现身，提供了轻量版介绍和会议演讲信息
这是我和 Tao、Fan 合写的论文，很高兴它正式发表，为 Physalia 团队感到自豪。这里有一篇更轻量的介绍，参加 NSDI 的读者可以在周三的“部署经验”分会听我讲 Physalia。
mjb查看英文原文
This is my paper (along with Tao and Fan). It's a great feeling to have this published and available, and I'm super proud of the team behind Physalia. There's a lighter-weight introduction to the work here: https://www.amazon.science/blog/amazon-ebs-addresses-the-challenge-of-the-cap-theorem-at-scale and for those attending NSDI, I'll be talking about Physalia in the "Deployment Experience" session on Wednesday.
支持称赞论文的术语与隐喻，并举例说明廉价启发式放置策略的效果
这篇论文用了大量精彩术语——爆炸半径、菌落、颜色、game day、脑裂——还有僧帽水母的绝妙生物隐喻。即使你不关心容错、CAP 定理或 AWS 规模的分布式均衡，也值得一读。一个体现廉价启发式胜过完整数值计算的例子：全局优化放置不可行（非凸优化且需在线进行），但用一种类似冒泡排序的粗糙启发式随机交换两个 cell 间的节点，就能把可用性丢失概率降低最多 4 倍。
kthejoker2查看英文原文
Thought for sure this'd be a thinkpiece on Excel in the enterprise ... Seriously, though, this whole paper uses an amazing amount of terminology - blast radius, colony, color, game day, split brain - and an awesome biological metaphor of the Portuguese man o'war. Great read even if you don't care about fault tolerance, CAP theorem, or distributed balancing at AWS-scale. One sample quote of the value of cheap heuristics over full-blown number-crunching: > Globally optimizing the placement of Physalia volumes is not feasible for two reasons, one is that it’s a non-convex optimization problem across huge numbers of variables, the other is that it needs to be done online because volumes and cells come and go at a high rate in our production environment. Figure 11 shows the results of using one very rough placement heuristic: a sort of bubble sort which swaps nodes between two cells at random if doing so would improve locality. In this simulation, we considered 20 candidates per cell. Even with this simplistic and cheap approach to placement, Physalia is able to offer significantly (up to 4x) reduced probability of losing availability.
补充摘录摘要核心思想，并建议与 Route53/IAM 对比、期待 S3 论文
Physalia 是为大规模云控制平面优化的事务性 KV 存储，利用事务模式和基础设施设计的知识，为百万级客户端同时提供高可用和强一致性；它不做对所有键对所有客户端都高可用，而是针对每个客户端需要的键做到极高可用。有趣的是可以对比 Route53 或 IAM 这类需要全局复制、有界最终一致读的数据存储。希望 AWS 也开始发表关于 S3 的文章——虽然可以从专利窥探内部实现，但那些（有意？）很难读。
ignoramous查看英文原文
Abstract at: https://www.amazon.science/publications/millions-of-tiny-databases > ...Physalia is a transactional key-value store, optimized for use in large-scale cloud control planes, which takes advantage of knowledge of transaction patterns and infrastructure design to offer both high availability and strong consistency to millions of clients. Physalia uses its knowledge of data center topology to place data where it is most likely to be available. Instead of being highly available for all keys to all clients, Physalia focuses on being extremely available for only the keys it knows each client needs, from the perspective of that client. > ...We believe that the same patterns, and approach to design, are widely applicable to distributed systems problems like control planes,configuration management, and service discovery. It'd be interesting to constrast this approach with Route53's or IAM's datastore which need to be globally-replicated with time-bounded eventually-consistent reads, and transactional but verifiable writes. I hope AWS begins publishing about S3, now. One can look at the patents AWS engineers author to get a feel for some of the internals, but they are (intentionally?) hard to read. For instance, patents filed by two of the many S3 founding-engineers: https://patents.google.com/?inventor=James+Christopher+Sorenson%2c+III,Allan+H.+Vermeulen&oq=inventor:(James+Christopher+Sorenson%2c+III)+or+inventor:(Allan+H.+Vermeulen) Also see: https://aws.amazon.com/builders-library/ https://research.google/pubs/
补充补充 Google BigQuery 的类似数据放置实践
相关的是，BigQuery 也采用类似的基于使用情况的方案来放置和复制数据，使其对用户而言大概率可用。
vimota查看英文原文
Tangentially related, BigQuery uses a similar usage-based approach to place and replicate data in a manner that's likely to be available for users: https://cloud.google.com/blog/products/data-analytics/how-bigquery-zone-assignments-work
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
历次讨论
- 2020Hacker News 讨论帖173 分 · 10 评
同领域还值得读
I/O 比 CPU 更快——让我们划分资源并消除操作系统抽象
I/O Is Faster Than CPU – Let’s Partition Resources and Eliminate OS Abstractions
指出在现代服务器硬件上 I/O 速度已接近甚至超过 CPU，传统操作系统抽象反而成为瓶颈。
系统与数据库2019 · 817 分 · 277 评进阶 · 约 30 分钟编辑精选使用 io_uring 的高效 I/O
Efficient IO with io_uring
由 Linux 内核开发者 Jens Axboe 撰写，介绍 Linux 新的异步 I/O 接口 io_uring。
系统与数据库2019 · 426 分 · 96 评进阶 · 约 45 分钟编辑精选线程对大多数用途而言是个坏主意（1995）
Threads Are a Bad Idea for Most Purposes (1995)
这篇 1995 年的文章由 John Ousterhout 撰写，讨论为什么线程对大多数用途而言是坏主意，并主张事件驱动编程通常更简单、更高效。
系统与数据库2017 · 423 分 · 382 评进阶 · 约 25 分钟编辑精选学习型索引结构之论证
The Case for Learned Index Structures
提出把索引看作一种"模型"：既然 B-tree 等结构本质上是在学习数据的分布，就可以用机器学习模型（如回归模型、神经网络）来近似键到位置的映射，从而替代 B-tree、哈希索引…
系统与数据库2017 · 398 分 · 66 评 · 引用 25进阶 · 约 60 分钟编辑精选FoundationDB：一个分布式、解耦的事务型键值存储
FoundationDB: A distributed, unbundled, transactional key value store
介绍 FoundationDB：一个分布式、解耦设计的事务性键值存储。
系统与数据库2021 · 283 分 · 99 评进阶 · 约 90 分钟编辑精选