Borg 是一个集群管理系统，类似闭源的k8s。 通过准入控制、高效的任务装箱、超售、机器共享、以及进程级别的性能隔离，实现了高利用率。 为高可用应用提

好久没学习了，学点想学的。本次内容是分布式事务Percolator, 不翻译论文，没有算法细节，只记录自己的理解。 Percolator 和 2PC 2PC 两阶段提交协议中包含

一篇AWS的老文章，Dynamo到现在已经售卖了很久了，架构应该也早已不像论文中描述的这样。但文章入选了某年的sigmod best paper，依旧是有很多值得学习的地方。

设计

Dynamo是一种NoSQL产品，对外提供KV存储语义。在产品定义上强调Highly Available而非Consistency，所以在架构设计以及技术选型上和其他的产品还是有很多不同之处。

技术

在技术上，Dynamo其实有很多有问题的地方，比如NWR算法本身的一些。但考虑到Dynamo已经经过了很长时间的验证，也许这些问题已经被很好的解决了，只不过论文中语焉不详。所以暂且放下这些，挑一些来说一说。其中我认为值得拿出来说的主要有这几块：

数据的分区

一致性hash算法。传统的一致性hash算法使用hash ring来解决增减节点rehash范围大的问题，但比如数据倾斜，以及异构机器导致的性能倾斜这类问题是无法避免的。 Dynamo实践上，在原有hash ring上引入了虚拟节点，比较优雅的解决了这两个问题。

数据写入问题

一般存储系统会在写的同时保证一定的数据一致性，换取较低的读操作复杂度，代价上写性能降低（延迟等）。但Dynamo选择了另一条路线。 Dynamo的设计目标是提供一个高可用的KV Store，保证always writable，同时只保证最终的一致性。这样的目标使得Dynamo把解决数据冲突之类的操作放到了读操作中，以保证写永远不会被拒绝。 总的来说，问题有两个。一个是数据更新冲突问题，显然多client并发的读写同一个Key很容易遇到这样的问题，因为Dynamo只能提供最终一致性，Dynamo Ring 上多个节点的数据不一定一致。二是节点数据空洞的问题。因为Dynamo使用的是NMR这类的gossip算法，这类理论上会出现所有节点上都不包含完整数据集的情况，需要同步副本之间的数据。 前者使用版本时钟来标记数据版本，后续在读操作的时候进行读修复合并数据版本；后者有熵逆过程来处理，使用MerkleTree来快速检测副本之间的不一致性，以及最小化转移的数据量。 论文中的这个表格可以清楚的看出Dynamo设计开发需要考虑的方面以及在技术上的选择。剩下这些论文中感觉语焉不详，可以参考原文。

参考

Dynamo 的实现技术和去中心化

Dynamo一个缺陷的架构设计(译) – 后端技术 by Tim Yang

Dynamo: A flawed architecture | Hacker News

这篇文章介绍了AWS的数据库产品Aurora的设计考虑，包括存算分离、一写多读、基于Quorum的NRW一致性协议等。同时，文章也提到了PolarDB参考Aurora进行设计，但在网络瓶颈和系统调用方面有所不同。

---

Aurora是AWS提供的一种数据库产品，主要面向OLTP的业务场景。

设计上，我觉得有这些值得参考的地方：

• Aurora设计的前提是，在数据库上云之后，得益于云基础设施的发展，数据库最大的瓶颈从计算和存储变成了网络， 这是AWS在设计Aurora的时候一个很重要的前提。基于此前提，Aurora重提Log is Database的论调，只将RedoLog下推至存储层。
• 存算分离。数据库存储层对接分布式存储底座，通过存储底座提供良好的可靠性和安全性保证。计算和存储层可以独立拓展。同时，存储底座对上层提供的单一数据视图，使得一些核心功能和运维操作效率得到很好的提升（比如备份，数据恢复，HA等）
• 一些有意思的可靠性保证。比如基于Quorum的NRW一致性协议，存储节点读写都需要多数派的投票。保证双AZ级别的容错；用分片存储减少故障处理时间，以此提升SLA。多数读只发生在数据库恢复的时候，此时数据库需要恢复当前的状态。
• 一写多读。不同于ShareNothing架构的NewSQL产品，Aurora只提供了单个写节点。数据一致性保证也因此变得简单，因为单写节点可以通过RedoLog LSN作为逻辑时钟，以此维护数据更新操作的偏序关系，只需要把RedoLog下推至所有节点，并基于此顺序对这些操作Apply就可以保证数据的一致性。
• 事务的实现。由于存储底座对上层提供的单一文件视图，所以对与Aurora来说，其事务的实现几乎与单机事务算法相同，并能提供相同的事务语义。NewSQL的事务一般是基于2PC的分布式事务实现。
• 后台加速前台处理。类似LevelDB的思路，尽可能将存储节点的一些操作异步化（比如日志Apply），提升前台用户感知性能。这些异步的操作通过维护各种xxLSN来记录当前节点的后台处理进度，比如VLSN，commit-LSN等等

有趣的是，PolarDB虽然是参考Aurora进行的设计，但它的架构设计认为网络并非瓶颈，而是经过OS的各种系统调用拖慢了整体速度。在彼时阿里云存储底座并不稳定的条件下，所以才有了它架构中的PolarStore，用各种硬件以及FUSE等存储技术越过或者优化系统调用，而如今盘古在稳定性和性能上都做的很不错的情况下，弱化PolarStore这个组件也成为了正常的选择。我认为说的不无道理。

另外，为什么他们选择用NWR而不是用Raft之类的一致性协议？目前看上去，NWR在网络上，一次请求的网络比Raft少一轮，可能是这个原因

参考

https://zhuanlan.zhihu.com/p/319806107

http://nil.csail.mit.edu/6.824/2020/notes/l-aurora.txt

论文阅读-Amazon Aurora: Design Considerations for High Throughput Cloud-Native Relational Database - keys961 | keys961 Blog

只是简单写写，有一些具体一点的设计建议去读一下原文。 简介 简单来讲，CR论文介绍了一种用于存储服务的满足线性一致性的复制状态机算法。它通过链式