Time and order

  1. 单机上，程序都是按照一定的顺序一个一个执行。而分布式系统希望能像单机一样执行程序，因此，顺序对于分布式系统而言是很重要的。 同时顺序这么重要是因为它能很容易的预测系统执行的正确性：
  2. 执行相同的操作
  3. 即使这里有多台计算机，也按相同的顺序执行

但是因为操作是在多个不同节点上进行，因此不同节点间需要准确的时间或者其他形式的通信来确保顺序的正确。

全序和偏序

分布式系统自然状态下是偏序的
分布式系统全序：

  1. 若使用通信，代价昂贵
  2. 时间同步困难且难以维持

时间

通常可以通过时间来定义操作的顺序

程序中，时间和时间戳的三种使用场景：

  1. order
  2. duration
  3. interpretation

时间的速率相同吗？

对于人而言，更容易想象推理一件事接着一件事发生的情景，如果说按事情发生的时间排序，人可能更容易推理全序关系，不擅长推理偏序关系。 但是，分布式系统设计需要尽量避免对时间和顺序的强假设，因为这个假设越强，这个系统能容纳的错误越少，对时钟要求就越高，所付出的代价就越高。但是如果降低对时间和顺序的假设，就可以更好利用资源做分布式计算。

有三种答案：

  1. global clock Yes
  2. local clock no,but
  3. no clock no

synchronous system model has a global clock parially synchronous model has a local clock asynchronous system model doesn’t have clock

Time with a “global-clock” assumption

系统拥有一个全局时钟，即每个节点的时间都是相同。 这个假设很好，但是实际本身实现还是有误差，例如NTP同步也会有难以避免的延迟。 除此之外，还会有外界其他因素的影响：

  1. 时钟漂移
  2. 用户意外改变机器上的本地时间
  3. 新加入的机器时间不一致

但这个假设本身是很好的，可以自由使用时间戳来确定全局顺序。使用了这个假设的如：Cassandra， Spanner。前者使用时间戳来解决写入冲突，用较新的时间戳覆盖旧的。后者会同步时间，但也会考虑最坏的时钟漂移。

Time with a “local-clock” assumption

假设每台机器都有本地时钟，但没有全局时钟，这个更符合现实。但可能出现的情况是本机器上的事件是有序的，但整个系统的事件顺序，仅通过时间来看，可能有冲突。 除此之外，本地时钟也可能因为用户的误操作而更改，导致任务超时。

Time with “no-clock” assumption

时钟是为了产生时间戳，给事件排序，但排序功能还可以通过计数器和节点通信来实现。不使用时钟情况下对事件进行排序的方法–矢量时钟

  • 优点：
    • 避免全局时钟和本地时钟遇到的问题
  • 缺点：
    • 无法计算timeout
    • 对事件排序受通信延迟影响

how is time used in distributed system?

使用时间的好处：

  1. 在不需要通信的情况下可以确定这个系统的事件顺序
  • 通过正确的时间给事件排序，可以得到正确的结果
  • 当事件执行发生冲突时，可以讲时间戳作为裁决依据
  1. 时间可以定义算法的边界情况或者说超时情况

向量时钟（vector clock)

lamport clock

lamport时钟和向量时钟是物理时钟的替代品，依靠计数器和通信来确定分布式系统中事件的顺序 这个时钟给每个节点都提供了一个可以比较的计数器 lamport clock,每个进程都维持一个计数器，遵循以下规则：

  1. 任何时候进程完成一个任务，计数器要增加计数
  2. 任何时候进程发送了一条消息，消息要包含计数器计数
  3. 当消息收到后，将counter设置到max(local_counter, received_counter) + 1 lamport时钟定义了一个偏序if timestamp(a) < timestamp(b)`:
  • a事件也许在b事件之前发生
  • a事件不能和b事件比较

这个称为时钟一致性 对于独立系统中的所有事件，若有上述条件成立，a事件在b事件事件不能和b事件比较

这个称为时钟一致性 对于每个独立系统中的所有事件，若有上述条件成立，a事件在b事件之前发生；但对于来自不同独立系统中的事件，这个就无法确定了，因为彼此之间不相关。或者说因为这两个系统没有通信。

vector clock

向量时钟是Lamport时钟的扩展，它保持N个逻辑时钟的数组[t1，t2，…] 每个节点一个。 每个节点不是递增公共计数器，而是在每个内部事件上将其自身的逻辑时钟递增1。 因此更新规则是：

  • 任何时候进程完成了一个任务，增加这个节点的向量时钟计数器计数
  • 任何时候进程发送了一条消息，要包含这个向量计数器的值
  • 当消息收到后
    • 更新每个节点的计数器值max(local, received)
    • 向量计数器中当前节点的值加1

向量时钟的主要问题在于每个节点都要维持一个向量列表，可能会变得很大，目前可通过周期性垃圾回收或者通过降低大小来降低精度

失灵检测

如何判断远程节点出现故障？ 使用物理时间时，是使用timeout,经过设定的时间无响应，则判断远程节点失败。 现在是通过心跳消息和定时器即本地时钟，来实现故障检测。进程间交换心跳消息，如果超时发生前未收到响应，则判断另一个进程失败了。
但这个超时应该设置多久呢?过长和过短都不太好。这个取决于本地节点和远程节点之间的延迟。同时故障检测器也是replication问题的基础。
故障检测器（failure detector）属性

  • completeness
  • accuracy

failure detector

  • 可以区分节点是正在经历延迟还是失败
  • 在最终弱精度 + 弱完全性下可以解决共识问题

failure detector实现： 希望其超时阈值可以根据网络条件不断变化而不是硬编码。或者如Cassandra是输出一个怀疑级别（0-1之间的数)，而不是二进制选项。

Time, order and performance

  1. 系统的自然情况是偏序
  2. 时钟仅仅是网络延迟（逻辑时间）或物理限制的近似值
  3. 时间本身不重要，它所代表的抽象属性很重要：
  4. 任意事件的排序(the causal ordering of events)
  5. 故障探测器(failure detection)
  6. 一致快照(consistent snapshots)
  7. 如果关心每个操作改变的系统状态，time/order/synchronicity是必要的。但如果只在意系统最后的结果，time/order/synchronicity是没必要关心的