Hunger's Blog

在《浅谈分布式协调》一文中，共识算法被称为现代 CP 架构的核心，而 Paxos 算法是共识算法中的重量级，本文把它展开。 分布式协调要解决的三个问题——顺序性、存活检测、互斥性，最终都收敛到一件事：让多个节点对“某个事实”达成一致。Leader 与多数派是达成一致的手段，但 Leader 换人时，“谁是新的 Leader”本身又需要一次一致——用一致来保证一致，这就是共识问题。 共识问题共识（Consensus）：一组进程各自提出一个值，最终所有进程对同一个值达成一致，并且该值必须是某个进程提出过的。 一个可用的共识算法需要满足三个性质： 有效性（Validity）：最终达成的值必须是某个进程提议过的值，不能凭空产生； 一致性（Agreement）：所有进程达成的必须是同一个值，不允许两个进程各自认为自己的值被采纳； 终止性（Termination）：算法最终会得出结果，不会无限拖延。 严格来说，三者无法在异步网络中兼得。FLP 不可能性定理（Fischer-Lynch-Paterson，1985）指出：在异步网络中，只要存在一个节点可能发生故障，就不存在同时保证一致性与终...

单机系统里，互斥、顺序、失效这些问题可以依靠本地内存、数据库事务或进程锁解决。到了分布式系统里，这些办法不再够用。 分布式系统多了一层网络，不确定性也随之而来。每个节点只能看到自己的本地状态，以及已经收到的消息。某个节点没有响应，可能是真的宕机，也可能是网络抖动、GC 暂停、磁盘 I/O 卡住、线程池打满。调用方看到的超时，只能说明自己在指定时间内没有收到结果，不能证明对方一定没有执行。 协调（Coordination），就是多个节点在无法确知彼此状态的前提下，通过交换信息达成一致、共同完成任务的过程。 无论什么业务，分布式系统都需要保证三个性质： 顺序性：确保多个事件发生的先后次序与客观事实一致； 存活检测：确保一个节点卡住了，其他节点能接替它工作； 互斥性：一个任务有且仅有一个实例负责；一个数据有且仅有一个实例写入。 由 CAP 定理（详见《浅谈CAP定理》）可知，系统必须在 CP 与 AP 之间抉择：选 CP（一致性优先），意味着在无法确定数据是否正确时宁可拒绝服务；选 AP（可用性优先），意味着无论数据是否正确都先响应请求。这个抉择决定了两条实现路径各自的手...

CAP定理是分布式系统的基石，其严格的定义为：在一个异步网络（Asynchronous Network）中，如果发生网络分区（P），系统必须在强一致性（C）和完全可用性（A）之间做出取舍。 此处强调“异步网络”，并不是预设有“异步网络”和“同步网络”两个场景，而是为了驳斥经典谬误“C、A、P同时只能成立两个”。因为在同步网络下，C和A是可以同时成立的，而现实世界中并没有完美的同步网络。 异步网络（为什么没有同步网络）分布式系统中，异步网络指数据传输时长没有绝对上限的网络。 此处“没有绝对上限”强调无法确定数据仍在缓慢地传输还是传输已经中断。 由于数据传输时间不可知，故无法确定上限。 这包含了两层含义：既无法知道过去的网络传输耗时，也无法预测将来的网络传输耗时。当然，关键在于将来的传输耗时，因为系统节点都是在实时中决策的。 过去耗时不可知要计算一次数据传输的时间，理论上只需要通过接收时刻-发送时刻即可，而发送方只知道发送时刻、接收方只知道接收时刻，又由于时钟偏移，两方时刻永远无法统一，也就无法算出真实耗时。 此处时钟指节点本地的单调递增计数器（硬件晶振驱动的计时器）。不同...

临近大三开学，才感到焦虑。最近面了某大厂的两面。一面问八股，靠着零散印象勉强过关。二面则更像一面镜子——只抛概念，让我自述理解，说到哪里算哪里。说不透的，就是不会。临了，面试官说，广度可以，深度不够。我又何尝不知道呢，毕竟“八股”么，背不到的自然就不会了。后来看到一个观点，说“八股”最初也是从经典的论文里总结提炼出来的。我深以为然，遂想起以前学习时也总是要摸清脉络、搞懂原理，最后才是记背，怎么现在反而倒过来了呢。时间确是不等人的，但是想来还是不能急功近利，故决定从“四书五经”始，随阅读做些笔记。 想起那句诗：问渠那得清如许？为有源头活水来。 这清水还得从源头来。

这是我新博客的第一篇文章。现在想来旧博客的结局是注定的。终归是违背自己“一月一篇”规矩的代价。既然如此，又有什么可惜的呢，大不了，从头越。