时钟和状态管理
关于时钟
1. 同步物理时钟的算法 （Physical Clock）
2. 逻辑时钟（Logic Clock），包括Vector Clock，用来ordering event，即使不知道事件发生的绝对时间
分布式系统里面，关于时钟的问题，主要是没有一个Global Physical Time （因为每个系统都有自己的physical clock）
这带来的一个问题就是对于状态的管理，无法确切的得知某个process的state（因为无法依靠时间来判断，但是不是应该通过消息来trigger么？）
例子
一组process，跑在各自的processor上面，各个processor之间没有share memory
每个process P都有自己的状态S，随着process的running，状态会自己变化
这里，S是个抽象的概念，包含process里面相关的一组变量值，甚至包括文件
process之间只能通过消息通信
每个process都有自己的action，例如消息的send 、receive，or some operation that changes the state
在实际应用中，这里的action会比较“高大上”，例如client dispatched order message’ or ‘merchant server recorded transaction to log
每当上面提到的某个action发生的时候，我们说有一个Event发生了
event之间是有顺序关系的，并且
关于PC 物理时钟的管理
最底层，叫physical clock，实际是电子装置（芯片？）electronic device，数晶振的震荡次数count oscillations occurring in a crystal at a definite frequency，然后存到couter register里面 H(t)
然后到OS这一层，从寄存器里面取出H(t)，弄个算法，变成process可读的时间C(t) = aH(t) + b
For example, C(t) could be the 64-bit value of the number of nanoseconds that have elapsed at time t since a convenient reference time.
这就是“时间”在OS里面的具体存储形式，例如，通常好像是从1900年到现在的纳秒数值
为什么网络上面的Server不能保持一致的时间
主要就是因为各个server上面晶振的频率不能保持一致，一方面是硬件造成的，另外一方面，即使是同一个晶振，温度不同，频率也会有变化，所以count的时候就不准了。
晶振的工业误差，10的-6次方秒/没秒 => 每产生1s的误差，需要100000S（11.6天）
所以，server需要经常采用外部时钟来同步自己 => 最准的就是原子钟误差是10的13次方分之一，known as International Atomic Time
实践中，通常各种设备是通过UTC来矫正自己的时间，UTC是base在原子钟上面的，并且引入了“闰秒”的概念，来做定期的矫正 => 来keep it in step with
astronomical time（应该是真实的地球自转的真实时间=> 地球自转越来越慢）
UTC，通过radio或者卫星给的GPS送达各个设备
UTC signals are synchronized and broadcast regularly from landbased radio stations and satellites （GPS） covering many parts of the world.
上面扯了一堆时钟的原理，总算进正题说同步了
两种
External Sync：两个process都和外部的一个UTC时钟源同步，并且process之间的误差小于D
Internal Sync：两个process之间相互同步，并且误差小于D（即使可能这两个process和UTC都有较大偏差）
几乎所有号称“同步”的分布式系统，在实际中，都不是同步的，主要是因为消息（包括用来同步时间的消息）传送的延时是不可控的
用来同步时间的几种算法
Cristian 算法
弄一个time server和UTC device相连，向网络上的其他server提供time 服务
简单流程为，Server发一个消息Mr给time server，Time Server回一个消息Mt，里面带上自己的当前之间Tc
然后对于Server来说，当收到Mt之后，判断自己的时间：
1. 最简单的方法：从中取出Tc，加上(round-trip time)/2 即为自己的当前时间 => 这个假设round-trip time平均分配，去的时间 和 回的时间相等
2. 但是大多数case下，round trip来回的时间是不等的，所以改进算法为
=> 通过理论值，算出round trip 的“单程”最小值 min，于是Time Server 发送 Mt的最早时间为t+min，最晚时间为t+roundtrip-min
于是对于自己的Server来说，当收到消息Mt，取出其中的Tc的实际时间的可能范围为[Tc+min, Tc+roundtrip-min] => 这个区间的范围为roundtrip-2xmin，所以可以认为这种算法的精度为 “正负”roundtrip/2-min
实际使用中，可以多测几次roundtrip数值，防止间断性的网络阻塞影响roundtrip短暂性的很大
Cristian算法的一个问题是，如果Time Server坏了，就都完蛋了
于是演进算法Berkeley 算法，大致思想为（Internal Sync）
一组Server，选举一个做为Master，其他为Slave，Master用Cristian算法问Slave要时间
然后Master对取来的时间做个平均值，得出一个“准确的时间”，
同时再把这个“准确的时间”和各个Slave之间的差值送还给Slave，用来修改他们自己的时间
这里一个潜在的问题是，“平均”算法，如果某个“采样值”太不靠谱，会极大影响整个平均值=> 算法会加以控制，如果某个采样的offset太大，则丢弃
然后再演进，就是NTP
分层不用说了
NTP的三种模式，multicast、procedure call、symmetric mode，从左往右，精度越来越高
multicast通常用在高速的LAN之中，假设网络延迟很小，Timerserver广播自己的时间
procedure call就类似Cristian算法，Timesever应答来自client的request，返回自己的时间，精度高于multicast
symmetric mode（对称模式？），貌似是有2个Timerserver，分别从更高层拿时间，同时这两个server之间做消息交互，确保时间一致
A pair of servers operating in symmetric mode exchange messages bearing timing information. Timing data are retained as part of an association between the servers that is maintained in order to improve the accuracy of their synchronization over time.
不管上面哪种模式，消息都是UDP的，那么如何保证准确性呢？
几个概念
1. offset，指的是上面两个server A和B的时钟的actual offset
2. delay，di，指的是上面上面两条m消息的总transmission时间
其中m消息的transmission时间为t，m’的transmission时间为t’
。。。。
没看懂。。。P606
逻辑时钟
简单讲，就是用counter来表示逻辑顺序=》KERN里面好像有类似的机制，回头翻翻
引入背景
1. single sever上面可以用本机物理时间来对事件进行排序 => ordering envents
2. 分布式系统中，很显然，因为各机器物理时钟不可靠（即使有NTP），所以无法用物理时间来对Event排序
于是，引入一个概念：happened-before relation， 经常又被叫做causal（因果关系） ordering or potential causal ordering
定义很简单：发消息的event，总是先于收消息的event
（关于这个relation的一些注意点，例如下图，即使A发先于F收，但是A和F是没有因果关系的）
（再例如，也不是所有的event都能够有这种关系，例如A和E）
再有了上述happened-before relation的定义之后，引入logical clock概念
实现上，就是一个software counter，和physical clock没任何关系
每个process有自己的 locial clock Li
对每个event，如果是发生的process pi上面的，我们用Li(e)来做标识它的“logical timestamp”；用L(e)来标识process无关的“逻辑时间戳”
实际操作过程中，例如发消息之前，把自己的Li+1，同时把这个数值和消息一块发过去
收消息的时候，解出消息里面对方的counter值，和自己的当前值比较，从而得到“逻辑上的时间先后关系”
在logical clock中
如果e->e‘, 那么一定能推出L(e) < L(e‘)
但是反之不能从L(e) < L(e‘) 推出e->e‘ （因为e和e‘）可能没有这种因果关系，例如下图的b和e
为了解决这个问题，推出了vector clock的概念。。
举例如下
在一个有N的process的分布式系统中（例如下图N=3），vector clock是一个有N个整数的数组
每当有event发生的时候，加减关系如下图所示（每个process只增加属于自己的那一位）
当P1发消息给P2的时候
P1把vector clock中属于自己的那一位+1
P2收到的时候，比较自己的vector clock里面“属于P1的那一位”和P1这次发来的消息中的“属于P1的那一位”的大小，留下大的数值
=> 这样得到的效果是，对每个process的vector clock，属于自己的那一位，总是自己发送消息的数目；属于别的process的那一位，总是那个process发出的影响到自己的消息的数目
=> KERN的DB里面一定有类似的算法，好像是用来做同步的，翻一下
回到引入Vector Clock的初衷=> logical clock中不能从L(e) < L(e‘) 推出e->e‘
只要给出vector clock比较大小的算法，这个问题就很容易解决了
=> 例如上图中的c和e点，从V的比较上来说，只能落入上面的第三行 => 这说明，他们是并行发生的。
全局状态管理（Global State）
先说问题
这块最典型的问题例如“垃圾回收”
如下图，为了决定是否要回收某个对象，除了判断本机的状态，还要判断其他server的状态（例如P2引用了P1上面的对象），甚至消息，例如message里面引用了P2里面的对象 => 如果是在一个server上面，最简单的方法是，确定一个时间，大家都上报自己的状态，这样就比较好判断了
但是分布式系统，各个server时间无法保证Perfect Sync，所以“限定一个时间，各自上报状态”的方法无效。
（其他的例子，例如死锁，以及无法终止“涉及多个Process的算法”=> 各方都处于passive状态 => P611)
解决这个问题=> 可以通过“local state" 来构造出global state
we might ask whether we can assemble a meaningful global state from local states recorded at different real times. The answer is a qualified
‘yes’
需要先加入几个新概念
1. 单个Process的“历史事件”
2. 单个process的状态定义：Si
3. 对整个系统来说，整个系统的history => global history
4. 对整个系统，针对History，给一个Cut的定义
A cut of the system’s execution is a subset of its global history that is a union of prefixes of process histories
下面是两种典型的Cut，一致性的cut和非一致性的cut
区别在于，上面inconsistent的Cut的例子里面，P1 还没有发送消息，但是cut里面却包含了“P2收到那个P1还没有发送的消息”
正规一点的定义就是：对于consistent的cut，这个cut里面的每个event，他们的happend-before event一定也包含在这个cut里面
5. 再进一步“一致性的全局状态”（Consistent Global State）对应的就是一系列Consistent Cut
于是整个系统的运转就被抽象成了一组Consistent Global State之间的迁移
S0 -> S1 -> S2 ->...
上面的每个转换之间可能发生的事情就例如收发消息，或者自己的internal event
如何用这个模型解决最开始的问题，垃圾回收，死锁等等
分布式系统概念与设计-第十四章笔记,布布扣,bubuko.com
分布式系统概念与设计-第十四章笔记
原文：http://usdaydayup.blog.51cto.com/8723085/1388589
