分布式系统概念和设计

时间和全局状态

全局物理时间的缺乏使我们很难查明分布式程序的执行时状态。

我们经常需要知道当进程B处在某种状态依赖进程是什么状态，但不能通过依靠物理时钟理解一个同一个时刻到底是什么情况。

• 维护分布数据一致性算法
• 检查发送给服务器的请求的真实性算法
• 消除重复更新的算法

时间同步算法

基于时间戳的算法主要包括NTP（网络时间协议）和PTP（精密时间协议）。这些算法通过在网络中传输时间戳来同步时钟。NTP采用树状结构来同步时钟，每个节点都有一个本地时钟和一个父时钟，通过不断地比较和调整本地时钟和父时钟的差值来实现同步。PTP则采用主从模式，每个从时钟向主时钟发送请求以获取当前时间并进行同步。

基于频率的算法主要包括RBS（参考广播同步）、TICTOC和FTSP（灵活的时间同步协议）。这些算法通过测量时钟的频率来同步时钟。RBS使用GPS信号作为参考广播，所有的时钟都以此作为参考进行同步。TICTOC和FTSP则分别使用了对称双向延迟测量和多跳同步的机制，通过测量时钟之间的延迟来计算出时钟频率并进行同步。

时钟，事件和进程状态

时钟

操作系统读取结点的硬件时钟值H（t），按一定比例放大，再加上一个偏移量从而产生软件时钟，用于近似度量进程p1的实际物理时间t

• 只要时钟分辨率（时钟值修改的周期）比连续事件之间的时间间隔小，连续的事件就能相对于不同的时间戳。事件发生的速率依赖于处理器指令周期长度的因素。

时钟偏移和时钟漂移

• 两个时钟的读数之间的瞬间不同称为时钟偏移。
  • 在计算机中使用的基于晶体的时钟和其他时钟一样有时钟漂移问题，以不同的频率给事件计数，会产生差异。
  • 时钟的震荡器在物理上会有不同，结果是振荡器的频率会有不同。

通用协调时间

计算机时钟能与外部的高精度时间源同步。

最准确的物理时钟使用原子振荡器，漂移是10负13次方

这些原子时钟的输出被用作实际时间的标准——国际原子时间

秒，年和其他使用的时间单位是来源于天文时间。原来按地球的自转和公转定义。

通用协调时间（coordinated universal time UTC）,国际时间标准。

基于原子时间，但不时要增加闰秒或者删除闰秒。基于UTC信号进行时间同步。

同步物理时钟

同步系统中的同步

最简单的情况：在一个分布式系统中，两个进程之间的内部同步。

在同步系统中，已知时钟漂移率的范围，最大的消息传输延迟和进程每一步执行时间

一个进程在消息M中将本地时钟的时间t发送到另一个进程。

原则上，接收进程能将它的时钟设置为t+T,T是传输m所花费的时间，两个时钟应该一致。

两个时钟应该一致（因为目标是内部时钟同步，不管发送进程的时钟是否准确）

但T是常常变化不定。

通常其他进程与要同步的进程在各自的节点上竞争资源，其他消息与M竞争网络。

如果没有其他进程执行，没有其他网络通信，总有一个最小传输时间min可以获得，min可以被度量或适当的估计。

大多数分布式系统是异步的：导致消息延迟的因素很多，消息传输延迟没有上界max,在因特网尤其如此。

对于一个异步系统，我们只能说Ts = min + x 其中x >= 0。x的值是不知道的，因为无法衡量极端的网络情况。特定内部可控的局域网络中或许可以通过分布进行度量。

同步时钟的Cristian方法

Cristian建议使用一个时间服务器，链接到一个接收UTC信号的设备上，用于实现外部同步。

在接收请求后，服务器根据进程S的时钟提供时间。

Cristian观察到虽然在异步系统中消息传输延迟没有上界，但在一对进程之间进行消息交换的往返时间通常相当短，1s的一小部分时间啊。

把算法描述成有条件的：只有在客户和服务器之间的往返时间与所要求的精确性相比足够短，该方法才能做到同步的效果。

Cristian算法是一种用于在分布式异步系统中实现时间同步的算法。它解决了在没有全局时钟的情况下，如何使分布式系统中的各个节点保持相对一致的时间戳的问题。具体来说，该算法允许客户端向服务器请求其当前时间，并使用服务器返回的时间戳对本地时间进行调整，以实现不同节点之间的时间同步。

用时间服务器的同步图

关于Cristian算法的讨论

时间由一组服务器提供，避免单点导致暂时不能同步。

一个客户能将请求组播到群组然后得到第一个应答。

使用假的时间会引起计算机系统中的灾难。

容错能力通过更好的算法，恶意干扰通过认证技术处理

Berkeley算法

Berkeley算法是一种用于在分布式系统中实现时间同步的算法。它通过测量不同节点之间的时间偏差来调整它们的时钟，从而使它们保持相对一致的时间。

具体来说，该算法使用一个主服务器来收集所有参与者节点的本地时间，并计算它们之间的平均时间偏差。然后，主服务器将根据这个平均值向每个参与者节点发送一个时间调整值，以使它们的本地时钟与主服务器的时钟尽可能接近。

内部同步算法,用于运行unix的计算机群。

选择一台协调者计算机用作主机。

这个计算机周期性的调查其他时钟要被同步的计算机（从属机）

从属机将它们的时钟值返回给主机

主机通过观察往返时间，估计它们的本地时钟时间，并计算所获得值的平均值。

概率上的均衡指这个平均值能抵偿单个时钟跑快或慢的趋势。

协议的精确性依赖于在主机和从属机之间名义上最大的往返时间。

主机排除了任何偶尔的比这个最大值更大的时间读数。

主机不是发送更新的当前时间给其他计算机——这种方式会因为消息传递时间而引入更多的不确定性

而是发送每个从属机的时钟所需的调整量。

算法排除了有错误的时钟读数。

如果用一个普通平均值的话，这种有错的时钟会产生重大的负面影响。

主机采用容错平均值。在时钟中选择差值不多于一个指定量的子集，平均值仅根据这些时钟的读数计算

网络时间协议

定义了时间服务的体系结构和在因特网上发布时间信息的协议

NTP主要设计目标和特色

• 提供一个服务，使得跨因特网的用户能精确地同UTC同步
• 提供一个能在长久的链接损耗中生存的可靠服务，提供冗余的服务器以及服务器之间冗余的路径，如果其中一个不可达，服务器重新配置以便继续提供服务
• 使得客户能经常有效地重新同步以抵消在大多数计算机中存在的偏移率，服务被设计成能扩展到大量客户和服务器的情况
• 提供保护，防止对时间服务的干扰，无论是恶意还是偶然，时间服务使用认证技术，用于检查来自声称是可信源的时序数据。也验证发送给它的消息的返回地址。

NTP服务器按三种模式中的一种相互同步：组播，过程调用，对称模式。

• 组播模式用于高速LAN，一个或多个服务器周期性地将时间组播到由LAN链接的其他计算机的服务器，并设置它们呢的时钟。这个模式仅能获得相对较低精确，但对许多目的而言，足够了
• 过程调用模式：一个服务器从其他计算机接收请求，并用时间戳（当前的时钟读数）应答。这个模式适合精确性要求比组播更高的地方，或者不能用硬件支持组播的地方。
• 对称模式用于在LAN中提供时间信息的服务器和同步子网的较高层，即获得最高精确性的地方。

所有模式中，消息传递用标准UDP传输协议，具有不可靠性。

逻辑时间和逻辑时钟

从任何单个进程的角度，事件可唯一地按照本地时钟显示的时间进行排序。

由于在分布式系统中不能完美的同步时钟问题，因此通常不能使用物理时间找出在分布式系统中发生的任何一对事件的顺序。

通常使用类似于物理的因果关系的模式，但把它应用到分布式系统是为了给发生在不同进程的事件排序。

排序基于的观点：

• 如果两个事件发生在同一个进程中，那么发生的顺序是我们观察到的顺序
• 每次消息在不同进程中发送，发送消息的事件在接收消息的事件之前发生。
• 发生在先的因果关系
  • 如果发生在先关系的两个事件之间成立，那么第一个事件可能或不可能实际地引起了第二个事件。例如，服务器接收到一个请求，发送一个消息，但是这个消息和这个请求没有关系。

逻辑时钟

Lamport逻辑时钟解决了分布式系统中事件的全序问题，即如何对不同时刻发生的事件进行排序。它通过给每个事件分配一个唯一的时间戳并保证时间戳之间的偏序关系来解决这个问题

Larmport逻辑时钟是一个单调增长的软件计数器，计数器的值和任何物理时钟没有关系。

每个进程p维护自己的逻辑时钟l,进程用它给事件加上所谓的Lamport时间戳。

用L(e)表示时间戳。

全局逻辑时钟

一些有不同进程生成的不同的事件对Larmport时间戳在数字值上可能相同

然后可以创建全局时间的全局顺序。

所有事件都能排序，通过考虑发生事件的进程的标识

全局状态

• 分布式无用单元收集

  • 如果分布式系统中一个对象不再有任何对它的引用，那么它被认为是无用的。
  • 一旦一个对象被定义为无用，便可以进行回收操作。
  • 如果检查一个对象是否被引用，必须验证系统中没有地方被引用，程序计数器的设计思路
  • 

• 分布式死锁检测

  • 当一组进程中的每个都在等待另一个进程给它发送消息。
  • 并且等待关系中存在循环就会发生分布式死锁。
  • 

• 分布式终止检测

  • 看起来仅仅是测试是否某个进程都已经停止，看似简单
  • 不能推断算法已经终止，当测试被动性，一个消息在路上，发出该消息马上变成被动，马上发现该进程变成被动又主动，因此算法还没有终止。
  • 

• 分布式调试

  • 非常仔细的确定分布式系统中程序到底发生了什么
  • 变量随程序执行而改变，但又被要求相互在一个值范围内
  • 这里的问题是在变量值变化的同时还要计算某种关系

全局状态和一致割集

缺乏全局时间导致的问题是：

• 原理上观察单个进程的连续状态是可能的，但如何查明系统的全局状态问题——进程集合的状态——hard
• 如果所有的进程都有同步的时间，同一时间让每个进程记录自身的状态的时间——结果将是系统实际的全局时间。
• 我们能够获取单个进程状态的任意集合来形成全局历史。
• 但是哪个全局状态是有价值的——哪些进程状态能在同一个时间发生

全局状态谓词，稳定性，安全性和活性

全局谓词

全局状态谓词（Global State Predicate）是指一个分布式系统中的谓词（Predicate），它用于描述整个系统的全局状态。在分布式系统中，每个节点只能观察到自己的局部状态，因此需要通过收集所有节点的局部状态并将其组合成全局状态来判断系统是否处于某种特定状态。全局状态谓词通常由多个局部谓词组成，并且必须满足一定的一致性条件，以确保在任何给定时间点，系统的全局状态都是唯一确定的。全局状态谓词在分布式系统中广泛应用于一致性协议、故障检测和容错等领域。

稳定性

系统从一个全局状态映射到一个（Ture,False）函数

与对象称为无用单元，系统死锁系统终止状态相关的一个谓词特征是稳定的

一旦系统进入谓词为稳定Ture状态，它将在所有可从该状态可达的状态中一直保持True

安全性和活性

假设有一个不希望有的性质a,该性质是一个系统全局状态的谓词

例如，a是成为死锁的性质

设S0是系统的原始状态。关于a的安全性是一个断言，即对所有可从S0到达所有状态S,a的值是false。a一直都是不稳定的谓词全局状态。

设B是系统全局状态希望有的特质，例如，到达终止的性质。

关于B的活性是对一个状态从S0开始的线性化走向L,对可从S0到达的状态，B的值是Ture,稳定态。

Chandy和Lamport快照算法

Chandy和Lamport快照算法是一种分布式系统中用于记录全局状态的算法，可以在不中断系统运行的情况下捕获系统的快照，并允许对这些快照进行分析。

算法的核心思想是通过消息传递方式构建全局快照。具体来说，每个进程都会记录自己的本地状态，并定期向其他进程发送特殊的Marker消息。当一个进程收到来自其他进程的Marker消息时，它将记录当前的本地状态，并将Marker消息继续向其他进程传递。这样就形成了一张快照图，在该图中，进程的本地状态被记录在节点上，Marker消息被记录在边上。

快照算法的一个重要问题是如何保证正确性。为了达到这个目的，算法引入了两个假设：

1. FIFO消息传递：如果一个进程在时间戳t1之前发送了一条消息，另一个进程在时间戳t2之后接收到消息，则t1 < t2。
2. 对于任意两个进程Pi和Pj，如果Pi在记录快照时记录了Pi->Pj的消息，则在快照中，Pj的状态要么已经被记录，要么在之后的消息中被记录。

以下是一个Python实现的简单示例：

from collections import defaultdictclass Snapshot:def __init__(self, marker_id, local_states, channel_states):self.marker_id = marker_idself.local_states = local_statesself.channel

算法的主要目的是记录进程集的进程状态和通道状态集（“快照”）

即使所记录的状态组合可能从来没有在同一时间发生，所记录的全局状态还是一致的。

• 为什么能很方便的求解稳定的全局谓词的值——系统稳定性

Chandy-Lamport快照算法通过将系统中的进程划分为两种类型：忙碌进程和空闲进程，来实现对全局谓词的稳定求解。

在算法执行过程中，所有的忙碌进程都会记录下它们的本地状态，并向其他进程发送探测消息。当一个忙碌进程接收到来自其他进程发来的探测消息时，它会立即记录下当前的本地状态作为快照，并将该快照发送给发送者，以表示当前的全局状态。同时，该忙碌进程也会将快照存储在本地。

空闲进程则不需要记录本地状态，只需接收来自忙碌进程的探测消息并将其转发给其他进程即可。

由于快照是基于全局探测消息进行记录的，因此能够保证算法的正确性和稳定性。最终，所有的进程都会记录下相同的全局快照，并且可以使用这个全局快照来确定是否满足所求的全局谓词。