背景

BIGO的服务器分布在全球各地，各种服务如分布式追踪等都对全球机器存在时钟对齐的需求。而客观上，受限于服务器本身的时间源设备精度以及内核时钟系统的软件设计实现等多种复杂因素制约，常见的服务器秒级别的设备时钟误差大约在万分之二左右，而累积误差会出现正反向补偿，根据经验观测值，一年存在至少分钟级别的时钟误差。

此类问题最常见的解决手段就是接入网络授时服务如NTP，但是作为一个全球分布几万+服务器的公司，简单接入NTP服务，并不能彻底解决全球时钟对齐的问题。

BIGO的服务器很早期就接入了time.nist.gov的NTP网络时间同步服务，但是观测到公司内部的机器普遍存在百毫秒级别的时钟误差，单机视图存在时间跳变等问题，而且误差分布几乎是随机的，同机房内部都可能出现极大误差。

基于以上现状，结合BIGO的业务需求，我们的全球时钟true time服务开启调研和建设。在业界相关领域，google的spanner论文有提到true time服务的建设，facebook也有公开过chrony时钟对齐服务解决方案。前者核心是依赖全球多机房部署原子钟+GPS构建了一个双层的架构，配合Marzullo变种算法来提供7ms时间区间服务。而后者本质上也是基于原子钟+GPS构建了一个最高可以达到16层的架构来提供true time服务。

业界的现有技术方案，一方面存在硬件设备依赖，另一方面直接作为开箱即用的时间源在BIGO实际场景会制约我们的服务部署情况。于是我们基于外部NTP网络时间源+内部UTC时间源集群+多PTP集群的方案来构建了BIGO自己的全球true time时钟对齐服务，目标是在不依赖内部原子钟的前提下，把BIGO全球机器99.99%场景时钟误差控制在亚毫秒。

该基础能力的建设，可以应用于BIGO内部不少场景：

1) 解决分布式追踪场景的时间误差问题；

2) 可以赋能BIGO的音视频优化直播帧时间戳跳变引起的卡顿问题，以及音视频和文件传输在重传准确率，拥塞控制等方向的提升；

3) 解决时间跳变问题，提升BIGO基础框架等服务的稳定性，避免跳变引起的服务卡顿和挂死。

 

NTP

在了解时钟对齐相关原理时，NTP协议（Network Time Protocal）和相应的ntpd和ntpdate服务是必须要了解的。这里我们简单回顾一下相关原理。

NTP协议的提出是为了解决这样一个问题：已知有一个基准服务器A，A的时间是准确的，怎么通过网络让B本地时钟跟A对齐？

聪明的读者可能已经很快想到答案，B发包询问A，A把本地时间回给B就搞定了。但是问题没有这么简单，B->A的网络包延时d1，A->B的网络包延时d2，甚至A收到请求再回包过程的耗时d3都会导致B拿到的时间存在误差。

针对此问题David L. Mills提出了NTP协议，最早出现在rfc958。

图1是单次NTP授时过程，首先B向A发送一个NTP包，包里包含了离开B的本地时间戳T1。A收到NTP请求包之后，依次记录包到达的本地时间戳T2，回包离开的时间戳T3，然后立即把包返回给B。B收到回包后，记录本地时间戳T4。

其中我们把d1=T2-T1定义为上行延时，d2=T4-T3定义为下行延时。假设A-B的时钟绝对误差为diff，则有如下公式：

d=d1+d2

T2=T1+diff+d1

T4=T3-diff+d2

如上推算，A-B的时钟误差公式求解如下：

 

假设网络的上下行延时对等无波动，即d1=d2，则A-B的时钟误差近似值diff_appro跟diff相等，diff_appro的表达公式如下：

 

在单次的ntp对齐过程中，工程上往往基于diff_appro公式去计算A-B的时钟差，此时并未剔除上下行网络波动的影响，我们把diff称为A,B机对齐前时钟误差（简称前误差），把diff_appro-diff称为A,B机对齐后的时钟误差（简称后误差）。

后误差的公式表达为diff_appro-diff=(d1-d2)/2，当d1或者d2等于d时，后误差最大为±d/2。

NTP算法简单来说，就是基于diff_appro公式计算diff值，并对B机的时钟做出加diff_appro的调整，从而让B机的时钟向A机尽量对齐。对齐过程还会存在后误差（diff_appro-diff），后误差最大可以到±d/2。

看到这里，可能聪明的读者要发出灵魂拷问了，A直接回时间给B,B完全不考虑任何误差直接使用A返回的时间设置为本机时间，这个过程存在的误差也就是d2而已，最大误差可以换算为d。这NTP绕了这么一圈，仅仅是把后误差缩小到到d/2而已，反正是不准，优化一半的精度似乎没什么价值。

其实本质不是这样的，仅仅关注最大误差确实只优化了一半的精度。但是直接使用A返回的时间，A和B的时钟误差是恒等于d2的，而NTP的时钟误差本质上是跟上行延时和下行延时的差值成正比，网络延时是永恒存在的，而上下行延时差值（简述为网络波动）却不一定是永恒存在的，只要配合一些多次采样平滑调整，是可以基于NTP把时钟对齐的精度控制在比较理想的范围的。

ntpd和ntpdate就是2种基于ntp协议封装的时钟对齐服务方式，前者利用了多时钟源以及一些平滑算法来规避对齐过程中的时钟跳变问题。而后者仅仅是对ntp协议过程的定期应用，容易存在误差和跳变。

 

架构权衡与设计

前面提到BIGO一开始全球机器都基于ntpdate接入了time.nist.gov，但是效果显而易见是不好的，普遍存在百毫秒误差，时钟跳变，误差无视机房，每个问题都很致命。

那么简单换成ntpd会不会变好，我们的实践表明ntpd本机房同步误差可以控制在毫秒级别，但是跨大区同步存在10毫秒级别的误差，虽然对比ntpdate会有改善，但是这个效果还不够满足业务需求。或者我们的服务器可以物理距离跟ntp源保持靠近部署，但这不是一个好扩展的服务架构，也不符合我们全球多机房的运维现状。

我们后续还尝试引入facebook的chrony（facebook提供的一种NTP时间源）作为时间源，其对比ntpd有更优秀的同步算法，但是我们验证跨大区同步的误差依然在6毫秒级别，主要原因在于公网跨大区上下行delay差异导致。此外chrony对第三方使用者的调优成本较高，其提供了如mindelay等十几种同步模式，缺乏最佳实践指引。

简单总结一些权衡，如果要开箱即用一些ntp源服务，则BIGO的服务器部署会受到限制，如部署地点，同步频率等。因此我们在这一期放弃了全网直接使用相关ntp服务，而是开始在BIGO内部分层构建true time服务。

架构上，我们要在没有内部原子钟设备的前提下，解决2个问题。

1. BIGO的机器时间要和UTC时间保持较高精度的同步；

2. BIGO各个内部机器之间的时间要尽量保持较高精度同步，且ping延时越小的机器之间精度要求越高。

问题1即时间源的问题，google spanner里的true time的处理方式是依赖硬件设备，引入原子钟+GPS组成分布全球的master群，利用原子钟和GPS故障概率和故障原因存在差异这个特性做双保险保障master可用性。同时master和daemon(即slave)都会通过一些算法识别明显异常的时钟，从而在内部建设了一套全球高可用的高精度时间源。

而BIGO在面对这个问题时，尚没有大规模的原子钟设备，为了低成本的解决时间源问题，最终我们选择了建设一个单机房的时间源，我们称为super master。super master为了保证可用性，应该是集群。Super master的时间并不是来自自身的时钟，而是基于ntpd跟一个物理距离上最接近的NTP源做时钟对齐。

至此，我们在没有原子钟的情况下，得到了一个可用性对比google spanner里的 true time稍差一点的时间源。

问题2，我们希望按机房分层建设架构。最终确定在每个机房建设一些master节点，本机房的其他节点（我们称为slave）只会跟这些master做时钟同步，基于PTP协议来进行。看到这里可能读者会疑惑，PTP是个什么协议，这里不急，后面会有篇幅对该协议做一个回顾，你可以先简单理解PTP是在NTP上做的一种工程优化，其比较适合子网内的高精度时钟同步（在毫秒内精度进一步提升），支持广播，单播等工作模式。

最终，我们得到BIGO true time服务一期架构图如下：

架构里的相关名词解释如下：

NTP源——基于ntpd或者ntpdate形式提供时钟对齐服务的标准机构（例如time.nist.gov是由美国国家标准技术研究所提供），NTP源的时间同步报文里包含的时间是UTC时间（等效于GMT格林威治时间）。

Super Master——角色定位为BIGO内部的可靠UTC时间源，前面说了，super master是没有原子钟的，基于ntpd跟物理最近的NTP源做UTC时钟同步。Super master一期暂时是单机房的，后面为了更高的可用性，会规划多机房的分布式UTC源架构。

Name Service——BIGO内部的分布式名字服务，具体架构不细讲了，可以对标Etcd等架构，这里该模块主要用于给master发现super master做ptp单播时钟同步用。

Master——某个机房内的时钟源，仅仅服务本机房的节点。一个机房内可以有多个master存在。Master会定期基于PTP单播配合我们的平滑算法去super master做时钟同步，同时，也会秒级对子网内做ptp的sync广播达成master和slave的时钟同步。

关于master的选举决策，这里涉及到PTP里的BMC算法，原则上一个机房不需要唯一的master，该算法不同于其他分布式强一致算法如paxos，不需要达成全局唯一共识。关于BMC选举master机制我们后面会展开讲解。

Slave——机房里的普通服务器，会周期秒级收到同机房master的PTP sync同步广播，达成时钟同步，当前由于只会在同机房做时钟同步，该过程暂未做平滑处理。

 

机房内Master选举

提起Master选举，可能很多读者会想到Raft，Paxos等相关技术方案。而在我们这个具体的问题领域，关于在一堆机器里选出合适的主机作为master来成为时钟源，比较经典的是IEEE1588里的BMC（Best Master Clock）算法。

该算法比较适合子网内部Master选举的特点，只负责选出确定的Master群，并动态保障slave一定可以较快找到可用的Master，但是不考虑slave使用的master是否是最优解，BIGO内部为该算法设计了保底策略，用于规避极端情况长期使用较差的master。

BMC算法本身为每台机器设置了几个属性：

1）机器优先级：根据机器属性赋予机器的一个优先级，值越小优先级越高；

2）分组优先级：对机器进行分组，每个组有一个优先级值越小优先级越高；

3）唯一标识：进程的唯一标识，一般使用MAC地址。

BIGO这边由于子网天然是同机房的，所以1和2默认都是不配置的，基于保底策略来动态解决机器网络状况波动问题。

原始的BMC算法选主流程如下：

1） 进程接收子网内的master的广播信息，并加入自身的foreignMaster列表；

2）进程根据foreignMaster列表信息（可能为空）和本进程信息通过BMC算法按机器属性选择出最优的master；

3）如果进程成为master的话，则开始广播信息。

图3是选主过程的状态迁移图，子网内任何一台机器都会周期的check自身的foreignMaster列表，选出当前的自己的master(可以是自己)，然后相应把自身角色设置为master(slave)。

该算法集群多机状态收敛过程还是比较清晰简单的。

1) 初始的时候，不考虑引入任何随机退让算法，子网内所有机器都没有收到任何master的announce请求，则会将自己提升为master，并开始广播自己的信息。此时，子网内全部机器都是master；

2) 子网内的机器开始陆续收到子网内master的信息，在这过程中，不断执行bmc算法，进而将更优的进程设置为master，最后一般在几个广播周期内，整个集群的master，slvae状态达到稳定。

下面的图4简要的展示了BMC算法从初始化到收敛过程：

总结来看，BMC算法优点就是快速，简洁，而由于选主条件是静态的（如MAC地址大小），无法保证选出的master是网络情况最优的，这种算法在子网内比较合适。

为了保证该算法在网络变化后可以剔除掉明显异常的Master点，BIGO尝试引入网络波动保底策略。即在保持BMC算法主流程情况下，引入master->slave的网络波动情况来优化master选择策略。

为什么基于网络波动来做选主决策，而不考虑网络延时大小，根据我们前面描述的NTP原理，读者应该清楚，时钟同步的误差受上下行网络差值影响较大，而延时的绝对大小是没有影响的。

BIGO这边会基于PTP的delay过程（后面一节PTP协议会详细讲解），在本机维护slave跟他foreignMaster列表的机器的历史delay值集合——foreignMaster’s delay_list。然后基于标准方差公式计算每台