复制、容错原子存储
翻译自：Replicated/Fault-tolerant atomic storage
零基础入门分布式系统 7.2 Linearizability-腾讯云开发者社区-腾讯云
云计算设计在这些日子里展示了对复制容灾的喜爱。例如在在数据中心级别进行赋值存储的是GFS，Dynamo，Cassandra。在广域网级别有PNUTS，COPS和Walter。我一直在寻找这个主题的基础分布式算法, 发现了在复制原子存储的很好的论文: Reconfiguring Replicated Atomic Storage: A Tutorial, M. K. Aguilera, I. Keidar, D. Malkhi, J-P Martin, and A. Shraer, 2010.
复制提供了对崩溃故障的屏蔽.然而这是一个有限的容错能力,除非你重新配置存储服务拉埃添加新的副本替换掉崩溃的节点.事实证明,由于设计并发性和容错性问题,复制存储服务的动态重新配置是一个微妙/复杂的问题. MSR@Slicon Valley的这个团队已经研究复制存储中的重新配置问题一段时间了。但是在这篇文章中我不会谈论重配置工作，只会关注，复制、容错原子存储部分。
多数复制算法
这是一个用于复制容错原子存储的优雅算法，我认为每一个分布式系统的学者和开发者都应该知道。他简单强大并且有趣。我承诺你学习这个多数复制算法后大脑中会感觉良好。这个原算法发表在 Sharing memory robustly in message-passing systems, H. Attiya, A. Bar-Noy, and D. Dolev, 1995。在这里，我将根据教程论文中的讨论总结算法。
算法使用了多数复制来提供在同步模型下，崩溃故障下原子读取和写入操作。（当然，FLP结果表明在这种模型下不可能解决共识，但这是一个比解决共识更弱的问题。）这里原子意味着系统提供线性化，强一致性，保证读取返回最新版本的数据。这种单拷贝一致性比Amazon Dynamo的最终一致性更强.在CAP定理中这个算法在CP测；当大部分副本不可达时，可用性在这里被牺牲了。
写操作
每个存储节点保存起客户端存储的最新值的本地副本，一级指示该新鲜度的时间戳。一个vt-pair表示(value,timestamp)的一对，存储节点保存该数据。为了执行write(v)操作，客户端执行俩个阶段，他执行俩个操作：首先执行get阶段，然后执行set阶段。
get 阶段：vt-set=从大多数存储节点读取kv对。选择唯一的t'让t'>max(t在vt-set中)
set阶段：write_request(v,t')在存储节点。如果t'>他存储的t，存储节点存储vt'。存储节点发送ack，当大部分节点回复收到，返回OK
通过将客户端id与时间戳相邻，可确保t'的唯一性，因此，时间戳由一对数字和客户端id组成，按字典顺序排列。
读操作
read()操作非常类似写请求。客户端还背靠执行get和set阶段。唯一的区别是，在设置阶段，客户端写会在它在获取阶段学习到的最大时间的vt对。
get 阶段：vt-set=从大部分存储节点读取vt对
set阶段：write_request(v,t')在存储节点。如果t'>他存储的t，存储节点存储vt'。存储节点发送ack，当大部分节点回复收到，返回 V
read()中的set阶段是必须的，用来防止由于存储节点故障导致的震荡读取，在这种情况下，在写入过程中，连续的读取会在新旧值之间震荡，这违反了原子性原则。set阶段确保后续的read()返回的值至少是当前的read().这里的关键直觉是，任何两个多数存储节点总是至少有一个共同的存储节点。因此，如果某个客户端将值v存储在大多数存储节点上，那么另一个客户端在查询任何多数节点时都可以看到v。
与 Paxos
的关系多数复制算法似乎与 Paxos 共识算法密切相关。vt-pair 中的 t 对应于 Paxos 中的选票编号。Get 和 Set 阶段对应于 Paxos 的 phase1 和 phase2。（当然，由于多数复制不是为了共识，所以没有与 Paxos 的 phase3：commit 对应的东西。最后，读取作对应于 Paxos 中的学习作。现在是差异。在多数复制中，客户端不协调写入作，而在 Paxos 中，领导者被限制重新提议/重写具有最高 t 的值。同样为了避免领导者决斗问题，Paxos 依赖于领导者选举服务，以便系统最终收敛到一个领导者，该领导者可以安全地锚定/最终确定一个值作为决策值。（Paxos 中的领导人选举服务需要一些部分同步才能取得进展，因此只有到那时才能达成共识。总之，多数复制是 Paxos 共识的基石。
结束语
这种优雅算法的好处是它可以容忍/屏蔽少数存储节点和任意数量的客户端节点的崩溃，并且它可以在“异步”系统中工作。该算法的正确性不依赖于同步系统，因此该算法非常适合在分布式系统（尤其是广域网系统）中部署。
基于
共识/Paxos 的算法可以使复制服务的重新配置成为可能。示例包括 RAMBO 算法和 FAB：从商品组件构建分布式企业磁盘阵列，它提供了一个实现这些想法的化。但是，重新配置教程论文解释说，在异步模型下实现复制的重新配置也是可能的（没有共识）！！
其他
ABD算法确保线性一致性的操作被称为blind write盲写：它只是覆盖了一个数据项的值，而不考虑它之前的值。它只是覆盖了一个数据项的值，而不考虑它之前的值。如果多个客户端同时写入同一个项目，它将使用last-writer-wins最后写入者获胜的策略冲突解决。也就是说，其中一个写法将最终成为 "赢家"，其他的值将被默默地丢弃。
在某些应用中，我们希望决策更加谨慎，同时只在一个值没有被另一个节点修改的情况下才覆盖它。这可以通过一个atomic compare-and-swap (CAS)操作来实现。问题是我们如何在一个分布式多副本系统中实现线性一致化的CAS操作？
ABD算法无法实现CAS，因为不同的副本可能会以不同的顺序观察到操作，从而对某一CAS操作是否成功得出不一致的结论。然而，使用全序广播可以实现线性一致化且多副本的CAS操作。我们简单地广播每一个我们想要执行的操作，并在操作被递交时执行。这种算法可以确保一个操作在每个副本上有相同的作用和结果，就像在状态机副本中一样。
版本号
ABD算法需要一个机制来生成单调递增且全局唯一的标识符，以充当数据版本的逻辑时间戳。他必须满足俩个关键属性：
- 单调递增：每次成功的写操作都必须产生一个比之前所有时间戳都更大的时间戳。
- 全局唯一：不同客户端并发产生的写操作，其时间戳也不能相同，必须能够区分先后顺序。
结构：时间戳通常不是一个简单的数字，而是一个二元组 (序列号, 客户端ID)。
比较规则：采用字典序进行比较。即先比较序列号，序列号大的时间戳更大；如果序列号相同，则比较客户端ID，ID大的获胜（只要保证客户端ID唯一，任何比较规则都可以，目的是打破平局）。
- 客户端在执行写操作的 Get阶段，会从多数派节点收集当前已存在的时间戳。
- 客户端找出其中最大的时间戳，记为 max_ts。
- 在 Set阶段，客户端生成的新时间戳其序列号部分必须大于 max_ts的序列号（例如，max_ts.seq + 1），然后附上自己的客户端ID。
通过这种方式，每个新的写操作都“站在巨人的肩膀上”，确保自己的时间戳能超越之前所有已知的版本，从而满足单调递增的要求。客户端ID的引入确保了即使两个客户端并发地基于同一个 max_ts生成新时间戳，它们也会产生不同的时间戳（客户端ID不同），从而避免了冲突，满足了全局唯一性。