计算机时钟整理

介绍

在计算机的开发中，我们遇到过很多不同类型的时钟。每种时钟都具有自己的定义，根据定义的不同，其在计算机中也具有各种不同的作用。我们需要做的就是在合适的地方使用合适的时钟。因为时钟在计算机中，更多的时候不是自己在使用，而是会将自己产生的时钟传递到别的服务器上存在一定的交互性。然而时钟在很多时候却是不可靠的存在，所以，在很多情况下我们需要考虑如何选择甚至是设计时钟来保证我们的功能正常，并且在不可靠的时钟下可能可靠运行。

物理时钟

UTC Time

utc(Universal Time Coordinated)时间又叫协调世界时，其定义是：0时区从1972年1月1日0时走过的秒数。我们在大部分情况下说的unix时间戳就是这个时间。UTC的时钟定义其值只能精确到秒，但是内核提供的接口也能精确到微秒。

// 精度到秒
time_t t1;
time(&t1);
// 精度到微秒
// 该接口第二个参数为时区信息，默认为0时区
timeval t2;
gettimeofday(&t2, NULL);

Local Time

local time就是当地时间，在计算机中，系统维护的只有utc时间。所有的local time都是根据utc以及系统设置的时区换算得来的。

time_t t1;
time(&t1);
/*
struct tm {
int tm_sec; // seconds after the minute [0-60]
int tm_min; // minutes after the hour [0-59]
int tm_hour; // hours since midnight [0-23]
int tm_mday; // day of the month [1-31]
int tm_mon; // months since January [0-11]
int tm_year; // years since 1900
int tm_wday; // days since Sunday [0-6]
int tm_yday; // days since January 1 [0-365]
int tm_isdst; // Daylight Savings Time flag
long tm_gmtoff; // offset from UTC in seconds
char *tm_zone; // timezone abbreviation
};
*/
struct tm* local_time = localtime(&t1);

这里得到的tm中的tm_min，tm_hour等都是已经换算成当前时区的值。

struct tm* gm_time = gmtime(&t1);

而这里得到的tm则是0时区对应的值。

utc time and local time transfer

时间的结构除了上述的time_t，timeval，tm以外，还有就是我们常见的字符串格式，他们的转换关系如下。

CPU Time

CPU时间就是进程真正跑在cpu上的时间，如果进程进入了中断，挂起，休眠等都不占用CPU时间。CPU时间并不以秒为单位，而是处理器的时钟周期为单位(clock_t)。而CPU时间可以除以宏CLOCKS_PER_SEC来转化为秒，对于不同的系统，clock_t和CLOCKS_PER_SEC的类型可能不是整形，所以最好是转换成double以后进行计算。

// 返回cpu时间
clock_t clock(void);

在使用中，cpu时间并不总是从0开始，所以正确的方式是取两次求差值来计算cpu时间。上述接口不区分系统cpu时间还是用户cpu时间。

/*
struct tms {
clock_t tms_utime; // user time
clock_t tms_stime; // system time
clock_t tms_cutime; // user time of children
clock_t tms_cstime; // system time of children
}
*/
clock_t times(struct tms* buf);

该接口可以区分主进程，子进程的系统cpu时间和用户cpu时间。

Wall Time

wall time就是墙上时钟，直观来讲就是我们体会到的时间。定义为：进程从开始到结束，系统时钟走过的时间。简单来说就是，进程从开始到结束跑了多久。包含了进程的阻塞时间，根据进程的状态来说：墙上时钟 = 阻塞时间 + 就绪时间 + 运行时间。其中运行时间 = 用户cpu时间 + 系统cpu时间

linux kernel中维护的四个时钟

上述我们讲的都是具体的时钟的含义，以及如何获得。但是在linux的内核中，我们可以看到有主要维护了四种时钟类型，这四种时钟和上述的四种是否存在关系。

CLOCK_REALTIME

可以理解为墙上时钟，其实就是实际的时间，我们直观感受的时间。当我们改变系统的时间，或者因为ntp等修正了系统时间，这个时间就会发生跳变。所以这个时间是有可能往前或者往后跳跃的。这个时间其实就是UTC时间，只不过它更加精确，可以精确到纳秒。

CLOCK_MONOTONIC

单调时钟，从某一个时刻开始进行递增，但是系统休眠(suspend)的时候不会递增。这个起点就是引导时间，或者可以单纯认为是启动时间。如字面意思，这个时钟是不会发生跳跃，也不会回滚，只会连续递增。但是可能受到ntp影响，在ntp和授时服务同步中，如果发现震荡频率不同而发生修正，就会改变该时钟的修改频率。

CLOCK_MONOTONIC_RAW

含义和CLOCK_MONOTONIC相同，唯一不同的是他不受ntp服务影响，只受限于本地振荡器。

CLOCK_BOOTTIME

含义和CLOCK_MONOTONIC相同，唯一不同的是，在休眠(suspend)期间也会递增。

获取上述时钟的接口如下。上述四个宏即为clockid_t。

/*
struct timespace {
__darwin_time_t tv_sec;
long tv_nsec;
}
*/
clock_gettime(clockid_t clock_id, struct timespec *tp);

逻辑时钟

在物理时钟的基础上，我们为什么会需要逻辑时钟，其实本质是因为交互。如果一个事情只会在一个服务器上进行，那么我们使用一个只会单调递增的物理时钟就能够确定时间的先后顺序。但是如果是在多个进程或者是服务器上发生的不同事情，同时又需要在不同的服务器上对这两个时间进行排序，如何能够保证结果一致呢？显然只依靠物理时钟会存在很大隐患，在上述我们介绍的各种物理时钟中都可能发生意外，导致两个事件在不同的服务器上定序结果会有所不同。这个时候我们就需要考虑使用逻辑时钟来唯一确定事件的先后顺序。

Lamport逻辑时钟

在介绍该逻辑时钟的算法之前先解释两个数学概念，偏序和全序。简单理解，偏序就是一个集合中，部分数据能够进行大小比较，全序则是集合中的所有元素都能进行大小比较。比如整数集合就是全序，复数集合就是偏序，因为复数集合中的实数和虚数的比较没有意义。

我们做需要逻辑时钟的原因已经在上述中表述，就是为了确定事件的逻辑顺序，因为物理时钟不可靠。我们首先定义，如果a事件发生在b事件之前，那么我们记作a->b。如果a和b无法判断先后关系则记为a||b。我们划分事件为三种：进程内的事件，发送事件，接收事件。下面三种情况都是a->b：

• a和b在同一个进程内，并且a发生在b之前，则a->b

• a和b在不同进程，但是a是发送事件，b是接收该消息的时间，则a->b

• 如果a->b并且b->c，那么a->c

如图有A,B两个进程，我们可以直观得得出

• a->b->e

• f->c->d

• a->b->c->d

• a||f

• b||f

• e||c

• e||d

a->b的关系，除了表示时间顺序以外，更重要的是因果关系，或者是逻辑关系。就像图中的b->c，而没有因果关系的两个事件也就没有办法定序，比如e||d，两者更像平行世界，相互不影响。

这里因为算法来表示每个事件的值：

分布式系统中，每个进程Pi保存了一个逻辑时钟值Ci，Ci(a)的含义是，进程Pi发生事件a时候的逻辑时钟值。Ci的值如下获得

• 进程Pi每发生一次事件，Ci加1；

• 进程Pi给进程Pj发送消息的时候，需要带上自己的本地逻辑时钟Ci；

• 进程Pj在接收消息的时候，更新Pj为max(Ci,Cj)+1；

根据算法上图的逻辑时钟值如下：

从上述算法可以比较明显得下面两个结论：

• 在同一个进程中，如果a->b，则Ci(a) -> Ci(b)

• a是进程i的发送事件，b是进程j的接收事件，那么有Ci(a)

上述结论可以得出，如果有两个事件a->b，那么一定有C(a) b。从图中我们可以得出是不能的，如e和d，Ci(e)是2小于Cj(d)的3，但是两者是并发关系，也就是由于并发的存在，让上述算法得到的时钟是偏序的。

那么我们能否加一些条件让他们的关系确定呢？因为e和d本身是没有逻辑上的联系的所以可以增加限制来让这个序确定下来。我们规定a=>b只需要满足下面的任何一个条件就成立

• Ci(a)

• Ci(a) == Cj(b) 并且 Pi

也就是给进程编号，我们规定，在逻辑时钟相同的情况下，标号小的进程对应的事件更小，则上述的事件可以确定唯一的序：a=>f=>b=>e=>c=>d。注意：e虽然排在c的前面，但是在物理时间上，可能是c先发生(实际哪个先也不一定)，但是因为两者没有逻辑关系，所以排序可能和物理时间不同也没有影响。

向量时钟

在逻辑时钟中我们能通过a->b得到C(a) b。在向量时钟中，这一问题将得到解决。

向量时钟需要维护除自己以为的其他进程的逻辑时钟，分布式系统中每个进程Pi保存一个本地逻辑时钟向量值VCi，向量的长度是分布式系统中进程的总个数。VCi (j) 表示进程Pi知道的进程Pj的本地逻辑时钟值，VCi的更新算法如下：

• 初始化VCi的值全为0：VCi = [0, … , 0]

• 进程Pi每发生一次事件，VCi[i]加1。

• 进程Pi给进程Pj发送消息，需要带上自己的向量时钟VCi。

• 进程Pj接收消息，需要做两步操作。

  • 4.1 对于VCj向量中的每个值VCj[k]，更新为 max (VCi[k], VCj[k])。

  • 4.2 将VCj中自己对应的时钟值加1，即VCj[j]加1。

可以理解为i,j为记录逻辑时钟值的下标，对应的就是对应进程的逻辑时钟值，但是在进程有通信之前，每个进程维护的向量值是存在差异的，因为没有交互的情况下，并不感知别的进程的值变化，只有自身的值在不断向前推进。

向量时钟里面的向量其实是一种偏序关系，并不能够确定每两个向量的大小:

• 如果向量VCi中的每个元素VCi[k]都小于等于VCj中的对应元素VCj[k]，则VCi ≤ VCj。

• 如果VCi中的每个元素VCi[k]都和VCj中的对应元素VCj[k]相等，则VCi = VCj。

• 如果VCi和VCj不能比较大小，则称两个向量是并发的 VCi || VCj。

从以上算法可以很容易地得出下面两个结论：

• 同一个进程内的两个事件a和b，如果 a → b，那么 VCi (a)

• a是Pi进程的消息发送事件，b是Pj进程该消息的接收事件，那么 VCi (a)

由以上两个结论又可以得出，对于任意两个事件a和b，如果 a → b，那么VC(a) 。

但是又如何证明VC(a)

设VCa = [m ,n], VCb = [s, t]。

因为VCa ≤ s，所以必然在不早于a之前和不晚于b之后的时间内，Pa向Pb发送了消息，否则Pb对Pa的计数器得不到及时刷新，s就不会小于m。

实际上，可以分为以下几种情况：

1. 当a = c且d = b，易得a → b。

1. 当a = c且d → b，由传递性，得a → b。

1. 同样对于d = b且a → c的情况。

1. 当a → c且d → b，根据进程内的算法逻辑性和传递性，也很容易得出结论。

综上: VCa

那么向量时钟的作用又是什么呢，因为作为偏序关系，是没有办法给全局定序的，所以向量时钟的其中一个作用就是发现冲突，但是不能解决冲突，冲突的部分就是无法判定因果关系的部分。另一个应用就是对于可以确定的部分，能够确定因果关系，比如聊天场景中，有问答，对于信息的交流部分需要严格定序。

混合逻辑时钟

混合逻辑时钟也就是HLC(Hybrid Logical Clocks)，顾名思义就是混合了多种时钟，其混合的也就是物理时钟和逻辑时钟。其目的也是为了补充逻辑时钟或者向量时钟与实际物理时钟的差距，在能够表示因果关系的基础上，又有物理时钟的直观特点。

HLC的定义如下，给分布式系统中的每个事件分配一个HLC，比如事件e分配了l.e，那么

1. 如果 e 事件发生在 f 事件之前（e happened before f），那么 l.e 一定小于 l.f，也就是满足因果关系。

1. l.e 可以存储在一个整数中，不会随着分布式系统中节点数的增加而增加。（这点和向量时钟不一样，向量时钟会随着节点数的增加而增加）

1. l.e 的值不会无限增长。（这点和Lamport逻辑时钟不一样，Lamport逻辑时钟会无限增长）

1. l.e 的值和 e 事件发生的物理时钟值接近，| l.e - pt.e |的值会小于一定的范围。

其实这里有个探索的过程，如何一步步得到最优现在最终的算法还是有思考的意义的，但是限于篇幅问题就不细述了，这里直接给出最终的算法。

我们把HLC分成两部分 l.j 和 c.j。l.j 表示事件 j 发生时所感知到的最大物理时钟值，c.j 是事件 j 的逻辑时钟部分，当几个事件在同一个物理时钟值内发生时，c 用于记录事件之间的因果关系。pt 依然表示本地NTP协议的物理时钟值。算法如下：

• 初始化:

l.j = 0;
c.j = 0;

• 发送消息事件或者本地事件：

// 如果事件发生时候，本地物理时间小于等于hlc的物理时钟部分，则逻辑部分+1
if pt.j <= l.j
c.j = c.j + 1
// 否则逻辑部分变为0，物理部分变更为本地的物理时间
else
c.j = 0
l.j = pt.j

• 接收m消息事件：

l.max = max(l.j, l.m, pt.j)
/*
如果物理时间都没有追上两个时间的物理部分，则选择逻辑部分大的+1
如果物理时间追上了其中的一个，那么用没被追上的那个的作为物理部分，也用它的逻辑部分+1
如果物理时间同时追上了发送事件和接收事件，那么接收事件的物理部分变成物理时间，逻辑部分变成0
*/
if l.max = l.j && l.max = l.m
c.j = max(c.j, c.m) + 1
else if l.max = l.j
l.j = l.max
c.j = c.j+1
else if l.max = l.m
l.j = l.max
c.j = c.m+1
else
l.j = l.max
c.j = 0

论文中的原文是这样的，感觉看起来比较难理解，上面的是我翻译的：

具体的证明过程和细节可以查看论文。

看一个例子

上图中，如果消息只在节点123之间流动，HLC的物理时钟部分 l.j 会一直保持为10，c.j 部分会不断增长，直到节点123中任何一个的NTP时钟值超过10，这时会将 c.j 重置为0。

工程实现上，HLC可以设置成64比特的整数，高位48比特是以毫秒为单位的物理时间。低位16比特是一个单调增长的整数，最大65535。具体位数分配可以根据实际的场景进行调整。

但是该算法其实也是个偏序算法，对于存在的冲突在我们了解业务场景情况下可能需要添加别的限制条件，比如在HLC中拼上节点的需要，来让两者发生冲突的时候能够定唯一的序。并且，我们也需要防范物理时钟的巨大跳跃，因为这会导致该物理时间向其他节点扩散，当然在定序上可能不会有影响，但是会扰乱HLC的值。