逻辑时钟

什么是逻辑时钟

1978 年，Lamport 在 Time, Clocks, and the Ordering of Events in a Distributed System 中提出了逻辑时钟的概念，来解决分布式系统中区分事件发生的时序问题。

逻辑时钟指的是分布式系统中用于区分事件的发生顺序的时间机制。

ZAB 协议

ZooKeeper 并没有直接采用 Paxos 算法，而是采用了名为 ZAB 的一致性协议。ZAB 协议不是 Paxos 算法，只是比较类似，二者在操作上并不相同。Multi-Paxos 实现的是一系列值的共识，不关心最终达成共识的值是什么，不关心各值的顺序。而 ZooKeeper 需要确保操作的顺序性。

ZAB 协议是 Zookeeper 专门设计的一种支持故障恢复的原子广播协议。

ZAB 协议是 ZooKeeper 的数据一致性和高可用解决方案。

分布式综合

📖 内容

• 分布式简介
• 逻辑时钟 - 关键词：物理时钟、逻辑时钟、向量时钟、全序、偏序
• CAP 和 BASE - 关键词：ACID、CAP、BASE、一致性
• 拜占庭将军问题 - 关键词：共识
• 分布式算法 Paxos - 关键词：共识、Paxos
• 分布式算法 Raft - 关键词：共识、Raft
• 分布式算法 Gossip - 关键词：Gossip
• ZAB 协议 - 关键词：共识、ZAB、ZooKeeper
• 分布式综合面试 💯

CAP 和 BASE

一致性

一致性（Consistency）指的是多个数据副本是否能保持一致的特性。

在一致性的条件下，分布式系统在执行写操作成功后，如果所有用户都能够读取到最新的值，该系统就被认为具有强一致性。

数据一致性又可以分为以下几点：

• 强一致性 - 数据更新操作结果和操作响应总是一致的，即操作响应通知更新失败，那么数据一定没有被更新，而不是处于不确定状态。
• 弱一致性 - 系统在写入数据成功后，不承诺立即能读到最新的值，也不承诺什么时候能读到，但是过一段时间之后用户可以看到更新后的值。那么用户读不到最新数据的这段时间被称为“不一致窗口时间”。
• 最终一致性 - 最终一致性作为弱一致性中的特例，强调的是所有数据副本，在经过一段时间的同步后，最终能够到达一致的状态，不需要实时保证系统数据的强一致性。

分布式简介

分布式系统的发展历程

罗马不是一天建成的，同理，现代分布式系统架构也不是一蹴而就的，而是逐步发展的演化过程。随着业务的不断发展，用户体量的增加，系统的复杂度势必不断攀升，最终迫使系统架构进化，以应对挑战。

了解分布式系统架构的演化过程，有利于我们了解架构进化的发展规律和业界一些成熟的应对方案。帮助我们在实际工作中，如何去思考架构，如何去凝练解决方案。

单机架构

• 场景：网站运营初期，访问用户少，一台服务器绰绰有余。
• 特征：应用程序、数据库、文件等所有的资源都在一台服务器上。
• 描述：通常服务器操作系统使用 linux，应用程序使用 PHP 开发，然后部署在 Apache 上，数据库使用 Mysql，通俗称为 LAMP。汇集各种免费开源软件以及一台廉价服务器就可以开始系统的发展之路了。

分布式综合面试

逻辑时钟

扩展：

• Time, Clocks, and the Ordering of Events in a Distributed System，译文，解读 - Lamport 介绍 happened before、偏序关系（partial ordering）、逻辑时钟（Logical Clocks）概念，提出解决分布式系统中区分事件发生的时序问题的方法。
• Virtual Time and Global States of Distributed Systems，解读 - 逻辑时钟无法描述事件的因果关系。本文提出了向量时钟，这种算法利用了向量这种数据结构将全局各个进程的逻辑时间戳广播给各个进程，通过向量时间戳就能够比较任意两个事件的因果关系。
• 逻辑时钟 - 如何刻画分布式中的事件顺序

拜占庭将军问题

拜占庭将军问题是由莱斯利·兰波特在其同名论文中提出的分布式对等网络通信容错问题。其实是借拜占庭将军的例子，抛出了分布式共识性问题，并探讨和论证了解决的方法。

在分布式计算中，不同的节点通过通讯交换信息达成共识而按照同一套协作策略行动。但有时候，系统中的节点可能出错而发送错误的信息，用于传递信息的通讯网络也可能导致信息损坏，使得网络中不同的成员关于全体协作的策略得出不同结论，从而破坏系统一致性。拜占庭将军问题被认为是容错性问题中最难的问题类型之一。

《数据密集型应用系统设计》笔记一——数据系统基础

第一章：可靠、可扩展与可维护的应用系统

认识数据系统

单一工具难以满足复杂应用系统的需求，因此整体工作被拆解为一系列能被单个工具高效完成的任务，并通过应用代码将它们缝合起来。比如一个缓存、索引、数据库协作的例子： 一个应用被称为数据密集型的，如果数据是其主要挑战（数据量，数据复杂度、数据变化速度）——与之相对的是计算密集型，即处理器速度是其瓶颈。 软件系统中很重要的三个问题：

《数据密集型应用系统设计》笔记二

第五章：数据复制

复制主要指通过网络在多台机器上保存相同数据的副本。通过复制，可以达到以下目的：

• 使数据在地理位置上更接近用户，从而降低访问延迟。如：CDN
• 当部分组件出现故障，系统依然可以继续工作，从而提高可用性。
• 扩展至多台机器以同事提供数据访问服务，从而提高读吞吐量。

主流的复制模式：主从复制、多主复制、无主复制。

复制需要考虑的细节：同步复制还是异步复制？如何处理失败的副本（故障转移）？处理策略通常采用可配置项来调整。

分布式算法 Gossip

Gossip 也叫 Epidemic Protocol （流行病协议），这个协议基于最终一致性以及去中心化设计思想。主要用于分布式节点之间进行信息交换和数据同步，这种场景的一个最大特点就是组成的网络的节点都是对等节点，是非结构化网络（去中心化）。

Gossip 协议最早是在 1987 年发表在 ACM 上的论文 《Epidemic Algorithms for Replicated Database Maintenance》中被提出，其理论基础来源于流行病学的数学模型，这种场景的一个最大特点就是组成的网络的节点都是去中心化的对等节点，在信息同步过程中不能保证某个时刻所有节点都收到消息，但是理论上最终所有节点都会收到消息，实现最终一致性协议。