背景

BIGO的服務(wù)器分布在全球各地,各種服務(wù)如分布式追蹤等都對(duì)全球機(jī)器存在時(shí)鐘對(duì)齊的需求。而客觀上,受限于服務(wù)器本身的時(shí)間源設(shè)備精度以及內(nèi)核時(shí)鐘系統(tǒng)的軟件設(shè)計(jì)實(shí)現(xiàn)等多種復(fù)雜因素制約,常見(jiàn)的服務(wù)器秒級(jí)別的設(shè)備時(shí)鐘誤差大約在萬(wàn)分之二左右,而累積誤差會(huì)出現(xiàn)正反向補(bǔ)償,根據(jù)經(jīng)驗(yàn)觀測(cè)值,一年存在至少分鐘級(jí)別的時(shí)鐘誤差。

此類問(wèn)題最常見(jiàn)的解決手段就是接入網(wǎng)絡(luò)授時(shí)服務(wù)如NTP,但是作為一個(gè)全球分布幾萬(wàn)+服務(wù)器的公司,簡(jiǎn)單接入NTP服務(wù),并不能徹底解決全球時(shí)鐘對(duì)齊的問(wèn)題。

BIGO的服務(wù)器很早期就接入了time.nist.gov的NTP網(wǎng)絡(luò)時(shí)間同步服務(wù),但是觀測(cè)到公司內(nèi)部的機(jī)器普遍存在百毫秒級(jí)別的時(shí)鐘誤差,單機(jī)視圖存在時(shí)間跳變等問(wèn)題,而且誤差分布幾乎是隨機(jī)的,同機(jī)房?jī)?nèi)部都可能出現(xiàn)極大誤差。

基于以上現(xiàn)狀,結(jié)合BIGO的業(yè)務(wù)需求,我們的全球時(shí)鐘true time服務(wù)開(kāi)啟調(diào)研和建設(shè)。在業(yè)界相關(guān)領(lǐng)域,google的spanner論文有提到true time服務(wù)的建設(shè),facebook也有公開(kāi)過(guò)chrony時(shí)鐘對(duì)齊服務(wù)解決方案。前者核心是依賴全球多機(jī)房部署原子鐘+GPS構(gòu)建了一個(gè)雙層的架構(gòu),配合Marzullo變種算法來(lái)提供7ms時(shí)間區(qū)間服務(wù)。而后者本質(zhì)上也是基于原子鐘+GPS構(gòu)建了一個(gè)最高可以達(dá)到16層的架構(gòu)來(lái)提供true time服務(wù)。

業(yè)界的現(xiàn)有技術(shù)方案,一方面存在硬件設(shè)備依賴,另一方面直接作為開(kāi)箱即用的時(shí)間源在BIGO實(shí)際場(chǎng)景會(huì)制約我們的服務(wù)部署情況。于是我們基于外部NTP網(wǎng)絡(luò)時(shí)間源+內(nèi)部UTC時(shí)間源集群+多PTP集群的方案來(lái)構(gòu)建了BIGO自己的全球true time時(shí)鐘對(duì)齊服務(wù),目標(biāo)是在不依賴內(nèi)部原子鐘的前提下,把BIGO全球機(jī)器99.99%場(chǎng)景時(shí)鐘誤差控制在亞毫秒。

該基礎(chǔ)能力的建設(shè),可以應(yīng)用于BIGO內(nèi)部不少場(chǎng)景:

1) 解決分布式追蹤場(chǎng)景的時(shí)間誤差問(wèn)題;

2) 可以賦能BIGO的音視頻優(yōu)化直播幀時(shí)間戳跳變引起的卡頓問(wèn)題,以及音視頻和文件傳輸在重傳準(zhǔn)確率,擁塞控制等方向的提升;

3) 解決時(shí)間跳變問(wèn)題,提升BIGO基礎(chǔ)框架等服務(wù)的穩(wěn)定性,避免跳變引起的服務(wù)卡頓和掛死。

NTP

在了解時(shí)鐘對(duì)齊相關(guān)原理時(shí),NTP協(xié)議(Network Time Protocal)和相應(yīng)的ntpd和ntpdate服務(wù)是必須要了解的。這里我們簡(jiǎn)單回顧一下相關(guān)原理。

NTP協(xié)議的提出是為了解決這樣一個(gè)問(wèn)題:已知有一個(gè)基準(zhǔn)服務(wù)器A,A的時(shí)間是準(zhǔn)確的,怎么通過(guò)網(wǎng)絡(luò)讓B本地時(shí)鐘跟A對(duì)齊?

聰明的讀者可能已經(jīng)很快想到答案,B發(fā)包詢問(wèn)A,A把本地時(shí)間回給B就搞定了。但是問(wèn)題沒(méi)有這么簡(jiǎn)單,B->A的網(wǎng)絡(luò)包延時(shí)d1,A->B的網(wǎng)絡(luò)包延時(shí)d2,甚至A收到請(qǐng)求再回包過(guò)程的耗時(shí)d3都會(huì)導(dǎo)致B拿到的時(shí)間存在誤差。

針對(duì)此問(wèn)題David L. Mills提出了NTP協(xié)議,最早出現(xiàn)在rfc958。

圖1是單次NTP授時(shí)過(guò)程,首先B向A發(fā)送一個(gè)NTP包,包里包含了離開(kāi)B的本地時(shí)間戳T1。A收到NTP請(qǐng)求包之后,依次記錄包到達(dá)的本地時(shí)間戳T2,回包離開(kāi)的時(shí)間戳T3,然后立即把包返回給B。B收到回包后,記錄本地時(shí)間戳T4。

其中我們把d1=T2-T1定義為上行延時(shí),d2=T4-T3定義為下行延時(shí)。假設(shè)A-B的時(shí)鐘絕對(duì)誤差為diff,則有如下公式:

d=d1+d2

T2=T1+diff+d1

T4=T3-diff+d2

如上推算,A-B的時(shí)鐘誤差公式求解如下:

假設(shè)網(wǎng)絡(luò)的上下行延時(shí)對(duì)等無(wú)波動(dòng),即d1=d2,則A-B的時(shí)鐘誤差近似值diff_appro跟diff相等,diff_appro的表達(dá)公式如下:

在單次的ntp對(duì)齊過(guò)程中,工程上往往基于diff_appro公式去計(jì)算A-B的時(shí)鐘差,此時(shí)并未剔除上下行網(wǎng)絡(luò)波動(dòng)的影響,我們把diff稱為A,B機(jī)對(duì)齊前時(shí)鐘誤差(簡(jiǎn)稱前誤差),把diff_appro-diff稱為A,B機(jī)對(duì)齊后的時(shí)鐘誤差(簡(jiǎn)稱后誤差)。

后誤差的公式表達(dá)為diff_appro-diff=(d1-d2)/2,當(dāng)d1或者d2等于d時(shí),后誤差最大為±d/2。

NTP算法簡(jiǎn)單來(lái)說(shuō),就是基于diff_appro公式計(jì)算diff值,并對(duì)B機(jī)的時(shí)鐘做出加diff_appro的調(diào)整,從而讓B機(jī)的時(shí)鐘向A機(jī)盡量對(duì)齊。對(duì)齊過(guò)程還會(huì)存在后誤差(diff_appro-diff),后誤差最大可以到±d/2。

看到這里,可能聰明的讀者要發(fā)出靈魂拷問(wèn)了,A直接回時(shí)間給B,B完全不考慮任何誤差直接使用A返回的時(shí)間設(shè)置為本機(jī)時(shí)間,這個(gè)過(guò)程存在的誤差也就是d2而已,最大誤差可以換算為d。這NTP繞了這么一圈,僅僅是把后誤差縮小到到d/2而已,反正是不準(zhǔn),優(yōu)化一半的精度似乎沒(méi)什么價(jià)值。

其實(shí)本質(zhì)不是這樣的,僅僅關(guān)注最大誤差確實(shí)只優(yōu)化了一半的精度。但是直接使用A返回的時(shí)間,A和B的時(shí)鐘誤差是恒等于d2的,而NTP的時(shí)鐘誤差本質(zhì)上是跟上行延時(shí)和下行延時(shí)的差值成正比,網(wǎng)絡(luò)延時(shí)是永恒存在的,而上下行延時(shí)差值(簡(jiǎn)述為網(wǎng)絡(luò)波動(dòng))卻不一定是永恒存在的,只要配合一些多次采樣平滑調(diào)整,是可以基于NTP把時(shí)鐘對(duì)齊的精度控制在比較理想的范圍的。

ntpd和ntpdate就是2種基于ntp協(xié)議封裝的時(shí)鐘對(duì)齊服務(wù)方式,前者利用了多時(shí)鐘源以及一些平滑算法來(lái)規(guī)避對(duì)齊過(guò)程中的時(shí)鐘跳變問(wèn)題。而后者僅僅是對(duì)ntp協(xié)議過(guò)程的定期應(yīng)用,容易存在誤差和跳變。

架構(gòu)權(quán)衡與設(shè)計(jì)

前面提到BIGO一開(kāi)始全球機(jī)器都基于ntpdate接入了time.nist.gov,但是效果顯而易見(jiàn)是不好的,普遍存在百毫秒誤差,時(shí)鐘跳變,誤差無(wú)視機(jī)房,每個(gè)問(wèn)題都很致命。

那么簡(jiǎn)單換成ntpd會(huì)不會(huì)變好,我們的實(shí)踐表明ntpd本機(jī)房同步誤差可以控制在毫秒級(jí)別,但是跨大區(qū)同步存在10毫秒級(jí)別的誤差,雖然對(duì)比ntpdate會(huì)有改善,但是這個(gè)效果還不夠滿足業(yè)務(wù)需求。或者我們的服務(wù)器可以物理距離跟ntp源保持靠近部署,但這不是一個(gè)好擴(kuò)展的服務(wù)架構(gòu),也不符合我們?nèi)蚨鄼C(jī)房的運(yùn)維現(xiàn)狀。

我們后續(xù)還嘗試引入facebook的chrony(facebook提供的一種NTP時(shí)間源)作為時(shí)間源,其對(duì)比ntpd有更優(yōu)秀的同步算法,但是我們驗(yàn)證跨大區(qū)同步的誤差依然在6毫秒級(jí)別,主要原因在于公網(wǎng)跨大區(qū)上下行delay差異導(dǎo)致。此外chrony對(duì)第三方使用者的調(diào)優(yōu)成本較高,其提供了如mindelay等十幾種同步模式,缺乏最佳實(shí)踐指引。

簡(jiǎn)單總結(jié)一些權(quán)衡,如果要開(kāi)箱即用一些ntp源服務(wù),則BIGO的服務(wù)器部署會(huì)受到限制,如部署地點(diǎn),同步頻率等。因此我們?cè)谶@一期放棄了全網(wǎng)直接使用相關(guān)ntp服務(wù),而是開(kāi)始在BIGO內(nèi)部分層構(gòu)建true time服務(wù)。

架構(gòu)上,我們要在沒(méi)有內(nèi)部原子鐘設(shè)備的前提下,解決2個(gè)問(wèn)題。

1. BIGO的機(jī)器時(shí)間要和UTC時(shí)間保持較高精度的同步;

2. BIGO各個(gè)內(nèi)部機(jī)器之間的時(shí)間要盡量保持較高精度同步,且ping延時(shí)越小的機(jī)器之間精度要求越高。

問(wèn)題1即時(shí)間源的問(wèn)題,google spanner里的true time的處理方式是依賴硬件設(shè)備,引入原子鐘+GPS組成分布全球的master群,利用原子鐘和GPS故障概率和故障原因存在差異這個(gè)特性做雙保險(xiǎn)保障master可用性。同時(shí)master和daemon(即slave)都會(huì)通過(guò)一些算法識(shí)別明顯異常的時(shí)鐘,從而在內(nèi)部建設(shè)了一套全球高可用的高精度時(shí)間源。

而B(niǎo)IGO在面對(duì)這個(gè)問(wèn)題時(shí),尚沒(méi)有大規(guī)模的原子鐘設(shè)備,為了低成本的解決時(shí)間源問(wèn)題,最終我們選擇了建設(shè)一個(gè)單機(jī)房的時(shí)間源,我們稱為super master。super master為了保證可用性,應(yīng)該是集群。Super master的時(shí)間并不是來(lái)自自身的時(shí)鐘,而是基于ntpd跟一個(gè)物理距離上最接近的NTP源做時(shí)鐘對(duì)齊。

至此,我們?cè)跊](méi)有原子鐘的情況下,得到了一個(gè)可用性對(duì)比google spanner里的 true time稍差一點(diǎn)的時(shí)間源。

問(wèn)題2,我們希望按機(jī)房分層建設(shè)架構(gòu)。最終確定在每個(gè)機(jī)房建設(shè)一些master節(jié)點(diǎn),本機(jī)房的其他節(jié)點(diǎn)(我們稱為slave)只會(huì)跟這些master做時(shí)鐘同步,基于PTP協(xié)議來(lái)進(jìn)行。看到這里可能讀者會(huì)疑惑,PTP是個(gè)什么協(xié)議,這里不急,后面會(huì)有篇幅對(duì)該協(xié)議做一個(gè)回顧,你可以先簡(jiǎn)單理解PTP是在NTP上做的一種工程優(yōu)化,其比較適合子網(wǎng)內(nèi)的高精度時(shí)鐘同步(在毫秒內(nèi)精度進(jìn)一步提升),支持廣播,單播等工作模式。

最終,我們得到BIGO true time服務(wù)一期架構(gòu)圖如下:

架構(gòu)里的相關(guān)名詞解釋如下:

NTP源——基于ntpd或者ntpdate形式提供時(shí)鐘對(duì)齊服務(wù)的標(biāo)準(zhǔn)機(jī)構(gòu)(例如time.nist.gov是由美國(guó)國(guó)家標(biāo)準(zhǔn)技術(shù)研究所提供),NTP源的時(shí)間同步報(bào)文里包含的時(shí)間是UTC時(shí)間(等效于GMT格林威治時(shí)間)。

Super Master——角色定位為BIGO內(nèi)部的可靠UTC時(shí)間源,前面說(shuō)了,super master是沒(méi)有原子鐘的,基于ntpd跟物理最近的NTP源做UTC時(shí)鐘同步。Super master一期暫時(shí)是單機(jī)房的,后面為了更高的可用性,會(huì)規(guī)劃多機(jī)房的分布式UTC源架構(gòu)。

Name Service——BIGO內(nèi)部的分布式名字服務(wù),具體架構(gòu)不細(xì)講了,可以對(duì)標(biāo)Etcd等架構(gòu),這里該模塊主要用于給master發(fā)現(xiàn)super master做ptp單播時(shí)鐘同步用。

Master——某個(gè)機(jī)房?jī)?nèi)的時(shí)鐘源,僅僅服務(wù)本機(jī)房的節(jié)點(diǎn)。一個(gè)機(jī)房?jī)?nèi)可以有多個(gè)master存在。Master會(huì)定期基于PTP單播配合我們的平滑算法去super master做時(shí)鐘同步,同時(shí),也會(huì)秒級(jí)對(duì)子網(wǎng)內(nèi)做ptp的sync廣播達(dá)成master和slave的時(shí)鐘同步。

關(guān)于master的選舉決策,這里涉及到PTP里的BMC算法,原則上一個(gè)機(jī)房不需要唯一的master,該算法不同于其他分布式強(qiáng)一致算法如paxos,不需要達(dá)成全局唯一共識(shí)。關(guān)于BMC選舉master機(jī)制我們后面會(huì)展開(kāi)講解。

Slave——機(jī)房里的普通服務(wù)器,會(huì)周期秒級(jí)收到同機(jī)房master的PTP sync同步廣播,達(dá)成時(shí)鐘同步,當(dāng)前由于只會(huì)在同機(jī)房做時(shí)鐘同步,該過(guò)程暫未做平滑處理。

機(jī)房?jī)?nèi)Master選舉

提起Master選舉,可能很多讀者會(huì)想到Raft,Paxos等相關(guān)技術(shù)方案。而在我們這個(gè)具體的問(wèn)題領(lǐng)域,關(guān)于在一堆機(jī)器里選出合適的主機(jī)作為master來(lái)成為時(shí)鐘源,比較經(jīng)典的是IEEE1588里的BMC(Best Master Clock)算法。

該算法比較適合子網(wǎng)內(nèi)部Master選舉的特點(diǎn),只負(fù)責(zé)選出確定的Master群,并動(dòng)態(tài)保障slave一定可以較快找到可用的Master,但是不考慮slave使用的master是否是最優(yōu)解,BIGO內(nèi)部為該算法設(shè)計(jì)了保底策略,用于規(guī)避極端情況長(zhǎng)期使用較差的master。

BMC算法本身為每臺(tái)機(jī)器設(shè)置了幾個(gè)屬性:

1)機(jī)器優(yōu)先級(jí):根據(jù)機(jī)器屬性賦予機(jī)器的一個(gè)優(yōu)先級(jí),值越小優(yōu)先級(jí)越高;

2)分組優(yōu)先級(jí):對(duì)機(jī)器進(jìn)行分組,每個(gè)組有一個(gè)優(yōu)先級(jí)值越小優(yōu)先級(jí)越高;

3)唯一標(biāo)識(shí):進(jìn)程的唯一標(biāo)識(shí),一般使用MAC地址。

BIGO這邊由于子網(wǎng)天然是同機(jī)房的,所以1和2默認(rèn)都是不配置的,基于保底策略來(lái)動(dòng)態(tài)解決機(jī)器網(wǎng)絡(luò)狀況波動(dòng)問(wèn)題。

原始的BMC算法選主流程如下:

1) 進(jìn)程接收子網(wǎng)內(nèi)的master的廣播信息,并加入自身的foreignMaster列表;

2)進(jìn)程根據(jù)foreignMaster列表信息(可能為空)和本進(jìn)程信息通過(guò)BMC算法按機(jī)器屬性選擇出最優(yōu)的master;

3)如果進(jìn)程成為master的話,則開(kāi)始廣播信息。

圖3是選主過(guò)程的狀態(tài)遷移圖,子網(wǎng)內(nèi)任何一臺(tái)機(jī)器都會(huì)周期的check自身的foreignMaster列表,選出當(dāng)前的自己的master(可以是自己),然后相應(yīng)把自身角色設(shè)置為master(slave)。

該算法集群多機(jī)狀態(tài)收斂過(guò)程還是比較清晰簡(jiǎn)單的。

1) 初始的時(shí)候,不考慮引入任何隨機(jī)退讓算法,子網(wǎng)內(nèi)所有機(jī)器都沒(méi)有收到任何master的announce請(qǐng)求,則會(huì)將自己提升為master,并開(kāi)始廣播自己的信息。此時(shí),子網(wǎng)內(nèi)全部機(jī)器都是master;

2) 子網(wǎng)內(nèi)的機(jī)器開(kāi)始陸續(xù)收到子網(wǎng)內(nèi)master的信息,在這過(guò)程中,不斷執(zhí)行bmc算法,進(jìn)而將更優(yōu)的進(jìn)程設(shè)置為master,最后一般在幾個(gè)廣播周期內(nèi),整個(gè)集群的master,slvae狀態(tài)達(dá)到穩(wěn)定。

下面的圖4簡(jiǎn)要的展示了BMC算法從初始化到收斂過(guò)程:

總結(jié)來(lái)看,BMC算法優(yōu)點(diǎn)就是快速,簡(jiǎn)潔,而由于選主條件是靜態(tài)的(如MAC地址大小),無(wú)法保證選出的master是網(wǎng)絡(luò)情況最優(yōu)的,這種算法在子網(wǎng)內(nèi)比較合適。

為了保證該算法在網(wǎng)絡(luò)變化后可以剔除掉明顯異常的Master點(diǎn),BIGO嘗試引入網(wǎng)絡(luò)波動(dòng)保底策略。即在保持BMC算法主流程情況下,引入master->slave的網(wǎng)絡(luò)波動(dòng)情況來(lái)優(yōu)化master選擇策略。

為什么基于網(wǎng)絡(luò)波動(dòng)來(lái)做選主決策,而不考慮網(wǎng)絡(luò)延時(shí)大小,根據(jù)我們前面描述的NTP原理,讀者應(yīng)該清楚,時(shí)鐘同步的誤差受上下行網(wǎng)絡(luò)差值影響較大,而延時(shí)的絕對(duì)大小是沒(méi)有影響的。

BIGO這邊會(huì)基于PTP的delay過(guò)程(后面一節(jié)PTP協(xié)議會(huì)詳細(xì)講解),在本機(jī)維護(hù)slave跟他foreignMaster列表的機(jī)器的歷史delay值集合——foreignMaster’s delay_list。然后基于標(biāo)準(zhǔn)方差公式計(jì)算每臺(tái)master的delay方差S(關(guān)于方差的概念,本文不再贅述)。我們認(rèn)為方差S可以較好的表達(dá)foreignMaster的網(wǎng)絡(luò)波動(dòng)。

在原BMC選主過(guò)程,BIGO會(huì)額外判斷目標(biāo)master的方差S是否超出了閾值,如果是則會(huì)把該Master機(jī)器從slave的foreignMaster列表里暫時(shí)踢掉,當(dāng)S恢復(fù)小于閾值后,會(huì)再加回foreignMaster列表,全過(guò)程對(duì)BMC選主機(jī)制沒(méi)有任何收斂性相關(guān)的破壞。

最后說(shuō)一下,為什么BIGO不嘗試改變BMC選主順序條件,比如按照master的S大小來(lái)優(yōu)先選主。主要基于2點(diǎn)考慮:

1. 子網(wǎng)內(nèi)機(jī)器間的網(wǎng)絡(luò)狀況一般都是平等,我們沒(méi)有強(qiáng)烈的需求需要選出最優(yōu)的master,我們需要做的是規(guī)避毛刺和異常節(jié)點(diǎn);

2. 改變BMC選主順序,引入動(dòng)態(tài)變量S來(lái)調(diào)整Master優(yōu)先級(jí),意味著每臺(tái)slave機(jī)的Master優(yōu)先級(jí)視圖可以不一樣,BMC簡(jiǎn)潔的Master收斂過(guò)程被破壞,我們需要很小心的去review整個(gè)算法的全過(guò)程,避免出現(xiàn)極端的Bug,而如1所述,這項(xiàng)工作的收益并不大。

PTP

單機(jī)房?jī)?nèi)部,master和slave之間通過(guò)PTP協(xié)議來(lái)完成時(shí)鐘同步。這里簡(jiǎn)單回顧一下PTP協(xié)議,以及BIGO內(nèi)部使用情況。

首先,NTP的原理讀者應(yīng)該已經(jīng)清楚了,那么我們可以認(rèn)為PTP是嘗試對(duì)NTP做工程落地的一種優(yōu)化實(shí)現(xiàn)方式。PTP全稱為Precision Timing Protocol,也是在IEEE1588里提出的。PTP主要解決了2個(gè)工程上的問(wèn)題:

1.解決NTP里面精準(zhǔn)獲取d1,d2的問(wèn)題;

2.怎么高效的在一個(gè)子網(wǎng)內(nèi)對(duì)多個(gè)slave同步時(shí)鐘的問(wèn)題。

先講下問(wèn)題1,精準(zhǔn)獲取d1,d2是什么意思呢?

首先,PTP是基于UDP協(xié)議來(lái)通信的,我們把d1,d2定義為網(wǎng)絡(luò)延時(shí),但是在工程實(shí)現(xiàn)上,假如B給A發(fā)包,A給B回包,A發(fā)回包前獲取本機(jī)時(shí)間T3‘的話,那么T3’=T3-UC。其中T3是網(wǎng)絡(luò)包從內(nèi)核發(fā)出去的時(shí)間,UC是A獲取本機(jī)時(shí)間到回包從內(nèi)核發(fā)出去的時(shí)間差,為什么會(huì)有UC存在,因?yàn)閘inux并不是一個(gè)實(shí)時(shí)操作系統(tǒng)。UC的耗時(shí)組成會(huì)很復(fù)雜,cpu調(diào)度的繁忙程度,緩沖到發(fā)送的耗時(shí)都會(huì)影響UC,且會(huì)動(dòng)態(tài)變化。而真正的延時(shí)d2=T4-T3,如果僅僅把T3’打到包里回給B,那么B在計(jì)算d2的時(shí)候就會(huì)存在誤差。

關(guān)于問(wèn)題2,PTP這邊利用廣播機(jī)制來(lái)主動(dòng)對(duì)多個(gè)slave進(jìn)行時(shí)鐘同步,工程上具備容易配置,快速收斂(參考前面的機(jī)房?jī)?nèi)master選舉算法過(guò)程),以及網(wǎng)絡(luò)帶寬和資源占用少等優(yōu)點(diǎn)

PTP具體同步過(guò)程分為delay機(jī)制和sync機(jī)制:

圖5為PTP時(shí)鐘delay機(jī)制的同步過(guò)程,該過(guò)程重點(diǎn)解決一個(gè)問(wèn)題:工程上精準(zhǔn)算A到B的網(wǎng)絡(luò)時(shí)延delay值。

為什么要算這個(gè)值呢?基于PTP子網(wǎng)同步的場(chǎng)景特點(diǎn),PTP假設(shè)短時(shí)間內(nèi),一個(gè)子網(wǎng)的網(wǎng)絡(luò)波動(dòng)較小,即D1=D2,且D1值短時(shí)間內(nèi)不會(huì)變化。基于這個(gè)假設(shè),PTP后面可以以較低開(kāi)銷完成sync機(jī)制的時(shí)間同步。

簡(jiǎn)單來(lái)說(shuō),PTP在一個(gè)子網(wǎng)內(nèi),slave會(huì)長(zhǎng)周期的進(jìn)行delay廣播機(jī)制,該過(guò)程開(kāi)銷偏大。而master側(cè)會(huì)短周期的進(jìn)行sync機(jī)制,來(lái)達(dá)成對(duì)子網(wǎng)內(nèi)全部slave的時(shí)鐘同步,該過(guò)程開(kāi)銷相對(duì)小。

回到delay機(jī)制過(guò)程本身,是怎么做到精準(zhǔn)測(cè)算A到B的delay值呢。圖中T1’,T2’,T3’,T4’都是PTP程序用戶態(tài)可以拿到的時(shí)間,這些時(shí)間都含有誤差。要精準(zhǔn)測(cè)算delay,B就需要獲取T1,T2,T3,T4,即req和resp從網(wǎng)卡發(fā)出,以及達(dá)到收包方內(nèi)核協(xié)議棧的時(shí)間。

先說(shuō)T2和T4值,這2個(gè)值在udp包達(dá)到內(nèi)核協(xié)議棧之后會(huì)記錄下來(lái),用戶態(tài)可以拿到該時(shí)間。從B的視角,T4本身就可以拿到,T2可以讓A的程序在回包的包體里帶上。

再來(lái)說(shuō)T3,這個(gè)值的獲取原理,是ptp delay機(jī)制需要廣播發(fā)起的主要原因。PDelayResp包回包是廣播到子網(wǎng),由于是廣播包,A自己也可以收到PDelayResp,基于回環(huán)廣播特性此時(shí)A收到的PDelayResp包的到達(dá)時(shí)間就是該包的網(wǎng)卡發(fā)出時(shí)間,即T3。此時(shí)A只需要再發(fā)一個(gè)PDelayRespFollowUp包,包體里帶上T3時(shí)間,則B就可以正確獲取T3時(shí)間了。

最后說(shuō)T1,只要明白T3的獲取原理,則類似T3,B本身獲取T1也是基于PDelayReq包的回環(huán)達(dá)到時(shí)間判定。

至此,基于公式delay = (T2-T1+T4-T3)/2即可在工程上完成精準(zhǔn)測(cè)算A到B的網(wǎng)絡(luò)時(shí)延delay值。

圖6為PTP時(shí)鐘同步的sync過(guò)程,該過(guò)程運(yùn)行時(shí),B已經(jīng)成功獲取到A到B的網(wǎng)絡(luò)時(shí)延dealy。此時(shí)A作為master主動(dòng)廣播sync請(qǐng)求幫助B精準(zhǔn)測(cè)算出A,B本地時(shí)鐘差值offset。

本次過(guò)程依然A,B只能拿到T1’,T2’,但是基于前面delay過(guò)程的描述,讀者應(yīng)該可以比較直接的知道如何獲取到T1和T2。過(guò)程不再贅述,B可以直接拿到T2,而followup包會(huì)把T1帶給B。

于是我們知道T1+offset+dealy=T2,故A,B機(jī)器時(shí)鐘誤差滿足offset=T2-T1-delay。B得到offset之后,修改本地時(shí)鐘即完成了一次PTP的子網(wǎng)時(shí)鐘對(duì)齊的過(guò)程。

最后提一下,PTP本身的工程源碼也存在一些亂序和時(shí)鐘同步錯(cuò)誤的bug,BIGO內(nèi)部基于一個(gè)版本做了一些改造優(yōu)化。

跨機(jī)房同步

Master機(jī)器周期跨機(jī)房與super master做時(shí)鐘同步,是本架構(gòu)里主要誤差來(lái)源。BIGO內(nèi)部跨機(jī)房,跨大洲以走公網(wǎng)為主,網(wǎng)絡(luò)延時(shí)大,網(wǎng)絡(luò)波動(dòng)比較明顯。即使內(nèi)部建設(shè)很好的光纖內(nèi)網(wǎng),雙向鏈路的延時(shí)對(duì)稱性也不一定可以保證,在實(shí)際運(yùn)行中受很多因素影響。

在這一層實(shí)現(xiàn)上,BIGO基于ptp單播協(xié)議(這個(gè)不細(xì)講了,就是ntp協(xié)議的工程實(shí)現(xiàn))來(lái)做同步,但是該協(xié)議顯而易見(jiàn)在網(wǎng)絡(luò)波動(dòng)下存在誤差和跳變。

針對(duì)這個(gè)問(wèn)題,BIGO參考了Ntpd的平滑實(shí)現(xiàn)并加入自研的異常波動(dòng)剔除算法,來(lái)優(yōu)化ptp單播跨機(jī)房同步過(guò)程存在的誤差和跳變,主要有2個(gè)策略:

1. 當(dāng)計(jì)算出offset(即ntp里的diff)在128ms以內(nèi)時(shí),對(duì)master本地時(shí)鐘往super master時(shí)鐘方向調(diào)整最多0.5ms。當(dāng)計(jì)算出offset(即ntp里的diff)大于128ms時(shí),默認(rèn)忽略該offset,除非該offset持續(xù)了一個(gè)較大閾值周期(300s),才會(huì)基于此offset調(diào)整master時(shí)鐘;

2. 基于波動(dòng)閾值x剔除無(wú)效同步。當(dāng)本次ptp單播的delay比最近30次delay值誤差大于閾值x,則本次ptp單播的結(jié)果不被應(yīng)用,同時(shí)x相應(yīng)增加。只有當(dāng)前ptp結(jié)果被采納,且offset值小于2ms,才會(huì)把x重置為初始值。

策略1可以保證時(shí)鐘對(duì)齊過(guò)程的平滑,同時(shí)時(shí)鐘對(duì)齊導(dǎo)致的時(shí)鐘回退問(wèn)題也解決了。這里的0.5ms/s不是人為設(shè)置一個(gè)絕對(duì)值,而是調(diào)用linux內(nèi)核封裝的Phase-locked loop機(jī)制來(lái)對(duì)本機(jī)時(shí)鐘進(jìn)行調(diào)整。從而保證時(shí)間調(diào)整不會(huì)在應(yīng)用上層體現(xiàn)為時(shí)間回退。該機(jī)制原理,本文不做展開(kāi)。

策略2可以剔除網(wǎng)絡(luò)波動(dòng)對(duì)同步結(jié)果的影響,有點(diǎn)類似chrony的mindelay機(jī)制。

BIGO在上線該策略后,對(duì)比之前無(wú)平滑策略的ntpdate效果明顯,在跨機(jī)房同步場(chǎng)景,比nptd和facebook的chrony效果也要更好,相關(guān)效果檢驗(yàn)下面會(huì)完整闡述。

效果評(píng)測(cè)與仿真

關(guān)于精度和效果評(píng)測(cè)這個(gè)話題,業(yè)界如facebook的chrony內(nèi)部聲稱做到0.1ms以內(nèi)的的誤差精度,而google的spanner里的true time是100%確信在7ms的區(qū)間內(nèi)。BIGO在開(kāi)展此項(xiàng)工作的一期目標(biāo)是在沒(méi)有內(nèi)部原子鐘的前提下,把99.99%場(chǎng)景誤差精度控制在亞毫秒。

關(guān)于精度的測(cè)算,本身就是一個(gè)跟全球時(shí)鐘對(duì)齊同等難度的命題。

為什么這么說(shuō)呢,因?yàn)槿绻覀兛梢栽谏系垡暯峭昝?誤差識(shí)別任意2臺(tái)機(jī)器的時(shí)間誤差,那么也就代表著我們可以把任意2臺(tái)機(jī)器的時(shí)間誤差調(diào)整為0。

已知比較好的評(píng)測(cè)手段,有facebook提到的基于1PPS(每秒脈沖數(shù))來(lái)檢測(cè)任意2臺(tái)機(jī)器的時(shí)鐘誤差,該評(píng)測(cè)可以做到納秒級(jí)的誤差,但是對(duì)硬件有很多依賴,如需要在機(jī)器間鋪設(shè)專用同軸電纜,需要定制的網(wǎng)卡硬件。

這個(gè)話題,我們主要從2個(gè)方向來(lái)展開(kāi):評(píng)價(jià)指標(biāo)和評(píng)價(jià)手段。

首先關(guān)于用什么指標(biāo)來(lái)評(píng)價(jià)集群內(nèi)機(jī)器之間的時(shí)鐘誤差情況,比較直觀的就是機(jī)器間誤差的時(shí)間軸坐標(biāo)圖,基于坐標(biāo)圖我們抽象了2個(gè)主要指標(biāo):

1)可用性——基于我們對(duì)誤差精度的要求是是亞毫秒,則每秒進(jìn)行一次機(jī)器間時(shí)鐘誤差判斷,大于1ms則認(rèn)為這1秒時(shí)鐘服務(wù)不可用,最后可用時(shí)間占比即為可用性;

2)最大誤差值——機(jī)器間誤差值波動(dòng)過(guò)大,我們認(rèn)為需要重點(diǎn)關(guān)注。

評(píng)價(jià)手段這塊,我們沒(méi)有相關(guān)硬件來(lái)支撐我們做1PPS的效果評(píng)測(cè),所以我們這里基于仿真的思路來(lái)做評(píng)測(cè)。

我們僅僅觀察同機(jī)房的2臺(tái)機(jī)器A和B的時(shí)間誤差,由于同機(jī)房機(jī)器ping 延時(shí)可以穩(wěn)定在0.1ms以下,此時(shí)我們近似具備了較高精度觀測(cè)誤差的能力。然后我們僅僅先評(píng)測(cè)以下3個(gè)場(chǎng)景:

1)A和B各自基于某種同步算法,跟本機(jī)房(或者同城)的時(shí)間源做時(shí)間同步,觀測(cè)A和B的誤差時(shí)間軸坐標(biāo)圖;

2)A和B各自基于某種同步算法,跟遠(yuǎn)端跨大區(qū)的時(shí)間源做時(shí)間同步,觀測(cè)A和B的誤差時(shí)間軸坐標(biāo)圖;

3)A基于某種同步算法,跟遠(yuǎn)端跨大區(qū)的時(shí)間源做時(shí)間同步,B基于相同同步算法,跟本機(jī)房(或者同城)的時(shí)間源做時(shí)間同步,觀測(cè)A和B的誤差時(shí)間軸坐標(biāo)圖。

圖7簡(jiǎn)單描述了前面所說(shuō)的3種評(píng)測(cè)場(chǎng)景。需要注意一點(diǎn),待評(píng)測(cè)的UTC時(shí)間源可能是跟我們的機(jī)器在一個(gè)機(jī)房,也可能僅僅是同城,取決于待評(píng)測(cè)服務(wù)本身實(shí)際部署情況。

我們?cè)賮?lái)關(guān)注怎么評(píng)測(cè)一個(gè)時(shí)鐘同步算法在跨大區(qū)機(jī)器間的誤差,比如圖中A1和B2之間的時(shí)鐘誤差?

軟件層面這個(gè)問(wèn)題看起來(lái)是無(wú)法評(píng)測(cè)的,但是我們先假設(shè)UTC時(shí)間源(外部原子鐘設(shè)備)之間是沒(méi)有毫秒級(jí)誤差,那么A3和B3的時(shí)鐘誤差我們暫時(shí)可以基于0.1ms的精度進(jìn)行評(píng)測(cè),我們定義A3和B3的時(shí)鐘誤差為diff(A3,B3),則diff(A1,B2)近似等于 diff(A3,B3)。

一句話總結(jié),我們可用觀測(cè)diff(A3,B3)的結(jié)果認(rèn)為其實(shí)仿真表達(dá)了diff(A1,B2),等價(jià)于我們成功評(píng)測(cè)了一個(gè)時(shí)鐘同步算法在跨大區(qū)機(jī)器間的誤差(本質(zhì)上還是有2套本機(jī)房外部原子鐘UTC源加持,但是僅僅是做評(píng)測(cè)時(shí)依賴而已,我們的系統(tǒng)的機(jī)器部署實(shí)質(zhì)不依賴外部UTC時(shí)間源的具體部署情況)。

至此,我們已經(jīng)具備不依賴內(nèi)部硬件設(shè)備,在BIGO全球機(jī)房仿真評(píng)測(cè)同機(jī)房,跨大區(qū)機(jī)器的毫秒級(jí)時(shí)鐘誤差的能力。

圖8到圖13分別為跨大洲和同機(jī)房情況下BIGO,NTP和facebook的chrony時(shí)鐘同步誤差測(cè)量表。

圖8～圖13為我們觀測(cè)BIGO同機(jī)房機(jī)器,基于不同算法和不同區(qū)域源時(shí)鐘同步之后,取得的誤差表。全部場(chǎng)景都觀測(cè)了3個(gè)小時(shí),每秒觀測(cè)一次,每張圖都是1萬(wàn)個(gè)橫軸坐標(biāo)點(diǎn)。需要注意的是,ntpdate本身明顯過(guò)于粗糙,我們認(rèn)為不值得浪費(fèi)時(shí)間進(jìn)行對(duì)比,所以這里只對(duì)比了ntpd和facebook的chrony。

此外,這里的對(duì)比結(jié)果不一定就代表facebook的chrony內(nèi)部精度情況,僅僅表達(dá)了BIGO作為一個(gè)第三方,去依賴這些服務(wù),我們能獲得的精度能力。而且chrony本身提供了數(shù)十種參數(shù)來(lái)調(diào)優(yōu)精度和波動(dòng),因?yàn)榫τ邢?我們對(duì)比時(shí)使用默認(rèn)配置。

圖14為我們對(duì)6張?jiān)u測(cè)效果做的總結(jié)。

前面3行是跨大洲場(chǎng)景的表現(xiàn),以前面定義的可用性而言,ntpd和chrony直接使用都無(wú)法滿足我們的可用性需求,而最大誤差這塊,BIGO自研架構(gòu)下的機(jī)器時(shí)鐘誤差控制在0.5ms內(nèi),而直接接入ntpd有近10ms最大誤差,接入chrony的誤差接近6ms。

后3行是同機(jī)房或者同大區(qū)的表現(xiàn),此時(shí)BIGO自研架構(gòu)下的機(jī)器時(shí)鐘誤差的可用性和最大誤差依然是好過(guò)直接接入ntpd或者chrony的。其表達(dá)的含義為,即使BIGO選擇限制自身的機(jī)房部署情況,做架構(gòu)設(shè)計(jì)去適配ntpd和chrony源來(lái)復(fù)用他們提供的時(shí)鐘對(duì)齊服務(wù),效果依然不如當(dāng)前版本的BIGO自研架構(gòu)。

總結(jié)

總結(jié)一下BIGO在全球時(shí)鐘同步服務(wù)的工作,在沒(méi)有內(nèi)部原子鐘的前提下,基于雙層架構(gòu)設(shè)計(jì),建設(shè)了穩(wěn)定的內(nèi)部UTC時(shí)間源。同時(shí)基于ptp單播配合平滑+異常剔除算法保證了第一層跨機(jī)房時(shí)鐘同步精度控制在亞毫秒。然后在第二層機(jī)房子網(wǎng)內(nèi),基于ptp算法實(shí)現(xiàn),優(yōu)化了網(wǎng)卡發(fā)包到用戶代碼層的時(shí)間誤差問(wèn)題,進(jìn)而把機(jī)房?jī)?nèi)的時(shí)鐘精度在毫秒內(nèi)進(jìn)一步提升。

最終我們收獲了一個(gè)99.99%場(chǎng)景下,集群時(shí)鐘誤差都在亞毫秒精度的時(shí)鐘服務(wù),且隨著ping值減少,同機(jī)房的精度有進(jìn)一步的提升。該服務(wù)架構(gòu)具備良好的內(nèi)部可擴(kuò)展性,不依賴外部NTP時(shí)鐘源的部署和服務(wù)能力。同時(shí)我們提供了有效的評(píng)測(cè)手段來(lái)驗(yàn)證我們的毫秒級(jí)誤差情況。

該系統(tǒng)在內(nèi)部UTC時(shí)間源的精度以及集群可用性,還有對(duì)抗上下行延時(shí)差值,高精度時(shí)鐘評(píng)測(cè)等方向還有諸多工作待進(jìn)一步展開(kāi)優(yōu)化,這些將規(guī)劃到我們的后期工作中。

該系統(tǒng)當(dāng)前作為基礎(chǔ)設(shè)施,為BIGO的全鏈路trace系統(tǒng)等多項(xiàng)服務(wù)提供時(shí)鐘對(duì)齊保證,成功解決了負(fù)調(diào)用耗時(shí)等業(yè)務(wù)問(wèn)題。