回答这个问题之前,我们先来看下分布式编程的定义。

the art of solving the same problem that you can solve on a single computer using multiple computers.

在单机系统中,传统的模式是: a single program, one process, one memory space running on one CPU。我们做了很多努力来给编程者提供一种简单的编程模型,一种顺序执行的模型,让程序实际执行的顺序就是代码的顺序。

但是我们一旦来到分布式环境中,我们却发现再也没有这种简单的编程模型了,程序实际执行的顺序你忽然间就无法预测了,因为每个节点时钟不是严格同步的,当然你可以去用复杂的技术来实现所有节点的时钟同步,然后给予每个操作一个时间戳,从而得到一个全局的 total order ;另一个思路是通过一个communication system,给每个操作都编号,从而得到一个顺序,但是就像我们之前说的一样,在分布式系统中,通信是不可靠的,您不可能确定的知道另外一个节点的状态,我们可以看到以上两种方法都很难。

Total and partial order

在分布式环境中一种常见的状态是:partial order,即部分有,在集合中不是任意两个元素都是可比较的。

Total 和 partial order 都满足 自反性和传递性。

If a ≤ b and b ≤ a then a = b

(antisymmetry);

If a ≤ b and b ≤ c then a ≤ c

(transitivity);

total order还满足:

a ≤ b or b ≤ a (totality) for all a, b in X

即所有集合中的元素都是有序的,而partial order则:

a ≤ a (reflexivity) for all a in X

即集合中的元素不是都有序,只满足自反性。

在单机系统中,所有的指令和消息的执行都是可预测的,是有一个total order的,因此程序的行为是可预测的,但是在分布式系统中想要实现total order,代价是巨大的,因为

communication is expensive, and time synchronization is difficult and fragile

What is time?

Time is a source of order - it allows us to define the order of operations- which coincidentally also has an interpretation that people can understand (a second, a minute, a day and so on).

什么是时间?时间有时候就像一个计数器,只不过时间这个计数器比较重要,我们用这个计数器产生的数值来定义整个人类的最重要的概念:时间。

Timestamps really are a shorthand value for representing the state of the world from the start of the universe to the current moment - if something occurred at a particular timestamp, then it was potentially influenced by everything that happened before it.

什么是时间戳(Timestamps),Timestamps定义了世界从初始到现在的状态,如果某件事发生在一个特定的时间点上,是之前影响产生的结果。

此处有个大前提,所有的时间都以相同的速率前行着,time and timestamps在程序中应用的时候,有3个常用的解释:

  • Order
  • Duration
  • Interpretation
  • 当我说:time is a source of order,我指的是:

  • we can attach timestamps to unordered events to order them【通过给事件安排一个时间戳,从而给事件排序】
  • we can use timestamps to enforce a specific ordering of operations or the delivery of messages (for example, by delaying an operation if it arrives out of order)【我们可以通过时间戳给操作重新排序】
  • we can use the value of a timestamp to determine whether something happened chronologically before something else【通过时间戳知道哪个事件发生在前】
  • Interpretation - time as a universally comparable value.

    时间戳的绝对值解释为日期(date),对人们非常有用的概念

    Duration - durations measured in time have some relation to the real world.

    像算法一般只关心Duration,通过Duration来判断延迟,一个好的算法都希望能有低延迟。

    Does time progress at the same rate everywhere?

    对于问题:时间以同样的速率进行吗?有3个常见的回答:

  • "Global clock": yes
  • "Local clock": no, but
  • "No clock": no!
  • 以上回答的的意思是:

  • the synchronous system model has a global clock,
  • the partially synchronous model has a local clock, and
  • in the asynchronous system model one cannot use clocks at all
  • 下面分别来看下

    Time with a "global-clock" assumption

    全局时钟(global-clock)假设是我们有个非常精确的时钟,我们任何人在任何地方都能看到他。这也是平时生活中我们最习以为常的时钟,对于不同时钟间微小的差别我们并不关注。

    在实际系统中,如果我们假设有个global-clock,即每个节点的时钟都是同步的,那么我们可以通过timestamps都就可以得到一个total order,但是在系统间维持时钟同步是非常难的,我们只能做到一定的范围内的同步。

    目前忽略时钟之间的不同步问题做出来的系统有:

  • Facebook's Cassandra:通过时间戳来解决冲突
  • Google's Spanner:时间戳+偏差范围来定义顺序
  • Time with a "Local-clock" assumption

    它假设了一个偏序关系

    events on each system are ordered but events cannot be ordered across systems by only using a clock.

    同一个机器上我们可以通过时间戳来排序,但是不同机器上的时间戳不能比较

    Time with a "No-clock" assumption

    不在使用时间戳,而是使用counter,通过传递消息来交换counter,从而定义不同机器之间的事件的前后顺序,比较有名的论文就是: time, clocks and the ordering of events 。

    How is time used in a distributed system?

    时间的好处是:

  • Time can define order across a system (without communication)
  • Time can define boundary conditions for algorithms
  • 在分布式系统中,定义事件的顺序非常重要,因为:

  • where correctness depends on (agreement on) correct event ordering, for example serializability in a distributed database【正确性依赖于事件的顺序】
  • order can be used as a tie breaker when resource contention occurs, for example if there are two orders for a widget, fulfill the first and cancel the second one【当发生资源争用的时候可以用来做裁决】
  • 当我们有全局时钟的时候,我们不需要通信就能够确定顺序,不幸的是,我们一般都没有全局时钟,因此只能通过通信来确定时序。

    时间除了用来确定时序外,还能定义算法的边界,特别是可以区分 high latency 和 server or network link is down,而用来探测它俩区别的算法就是:failure detectors。

    Failure detectors (time for cutoff)

    在分布式环境中,我们怎么知道一个节点是否宕机了呢?我们可以通过等待一定时间后认为节点失败了。

    那问题是这个一定时间是多久呢?