[[345832]]

『看看論文』是一系列分析計(jì)算機(jī)和軟件工程領(lǐng)域論文的文章，我們?cè)谶@個(gè)系列的每一篇文章中都會(huì)閱讀一篇來(lái)自 OSDI、SOSP 等頂會(huì)中的論文，這里不會(huì)事無(wú)巨細(xì)地介紹所有的細(xì)節(jié)，而是會(huì)篩選論文中的關(guān)鍵內(nèi)容，如果你對(duì)相關(guān)的論文非常感興趣，可以直接點(diǎn)擊鏈接閱讀原文。

本文要介紹的是 2019 年 SOSP 期刊中的論文 —— Taiji: Managing Global User Traffic for Large-Scale Internet Services at the Edge[^1]，該論文介紹的 Taiji 是 Facebook 在大規(guī)模互聯(lián)網(wǎng)服務(wù)中動(dòng)態(tài)管理用戶流量的系統(tǒng)，通過(guò)該系統(tǒng)我們可以平衡各個(gè)數(shù)據(jù)中心的資源利用率并降低用戶請(qǐng)求的網(wǎng)絡(luò)延遲。

Taiji 會(huì)利用用戶之間的關(guān)系將一批強(qiáng)相關(guān)的用戶路由到相同的數(shù)據(jù)中心，這種關(guān)系感知路由策略能夠降低 17% 的后端存儲(chǔ)負(fù)載。多數(shù)的服務(wù)都會(huì)使用靜態(tài)映射將用戶請(qǐng)求從邊緣節(jié)點(diǎn)路由到數(shù)據(jù)中心，但是靜態(tài)的映射很難處理大規(guī)模的全球數(shù)據(jù)中心，不同地區(qū)的邊緣節(jié)點(diǎn)的不同負(fù)載和高峰時(shí)段會(huì)帶來(lái)以下的一些挑戰(zhàn)：

• 容量短缺(Capacity crunch)— 如果服務(wù)的容量超過(guò)了采購(gòu)計(jì)劃，我們可能無(wú)法服務(wù)全部的用戶請(qǐng)求，而靜態(tài)的映射調(diào)度可能會(huì)使某些數(shù)據(jù)中心處于資源短缺或者而另外一些處于過(guò)度供應(yīng)的狀態(tài);
• 產(chǎn)品異構(gòu)(Product heterogeneity)— 隨著產(chǎn)品的逐漸迭代，我們可能會(huì)在交互方面提升用戶的體驗(yàn)，當(dāng)請(qǐng)求需要用戶設(shè)備與數(shù)據(jù)中心維持固定的會(huì)話時(shí)，靜態(tài)映射很難管理用戶流量;
• 硬件異構(gòu)(Hardware heterogeneity)— 底層基礎(chǔ)設(shè)施的演變會(huì)影響數(shù)據(jù)中心能夠處理的流量，例如：服務(wù)器的更新、容量的增減、網(wǎng)絡(luò)設(shè)備性能的提升;
• 錯(cuò)誤容忍(Fault tolerance)— 當(dāng)基礎(chǔ)設(shè)施變得越來(lái)越復(fù)雜，邊緣節(jié)點(diǎn)或者數(shù)據(jù)中心會(huì)有更高的幾率出現(xiàn)網(wǎng)絡(luò)錯(cuò)誤、斷電以及軟件錯(cuò)誤等問(wèn)題，靜態(tài)映射難以快速響應(yīng)問(wèn)題并緩解故障;

為了解決上述的問(wèn)題，F(xiàn)acebook 的工程師設(shè)計(jì)出了全球用戶流量管理系統(tǒng)，該系統(tǒng)將邊緣節(jié)點(diǎn)到數(shù)據(jù)中心的路由過(guò)程看做分配問(wèn)題(Assignment Problem)，我們會(huì)通過(guò)約束優(yōu)化器生成路由表，路由表能夠決定處理用戶請(qǐng)求的數(shù)據(jù)中心，邊緣節(jié)點(diǎn)會(huì)遵循路由表轉(zhuǎn)發(fā)用戶請(qǐng)求。

架構(gòu)

在成熟的內(nèi)容分發(fā)網(wǎng)絡(luò)(Content Delivery Network、CDN)中，邊緣節(jié)點(diǎn)可以處理用戶的絕大多數(shù)請(qǐng)求，它能夠低成本地、快速地提供靜態(tài)資源，靜態(tài)資源的分發(fā)和流量調(diào)度已經(jīng)有了一些比較成熟的解決方案，但是動(dòng)態(tài)的內(nèi)容往往需要具有更多計(jì)算和存儲(chǔ)資源的數(shù)據(jù)中心處理，在不同數(shù)據(jù)中心之間快速、穩(wěn)定的平衡負(fù)載是一個(gè)比較復(fù)雜的問(wèn)題，Taiji 會(huì)使用如下所示的架構(gòu)控制從邊緣節(jié)點(diǎn)到數(shù)據(jù)中心的流量來(lái)解決該問(wèn)題：

圖 1 - Taiji 架構(gòu)

Taiji 系統(tǒng)由兩個(gè)主要的組件構(gòu)成，分別是運(yùn)行時(shí)(Runtime)和流量管道(Traffic Pipeline)，這兩者在系統(tǒng)中起到了如下所示的作用：

• 運(yùn)行時(shí)會(huì)根據(jù)流量負(fù)載、數(shù)據(jù)中心利用率、邊緣節(jié)點(diǎn)與數(shù)據(jù)中心的延遲以及服務(wù)級(jí)別策略生成路由表;
• 流量管道會(huì)將路由表翻譯成細(xì)粒度的規(guī)則，利用關(guān)系感知路由為邊緣節(jié)點(diǎn)上的負(fù)載均衡生成路由配置并將用戶的請(qǐng)求到轉(zhuǎn)發(fā)特定的數(shù)據(jù)中心;

如上圖所示，邊緣節(jié)點(diǎn)的負(fù)載均衡解析所有的用戶請(qǐng)求并將用戶映射到合適的桶中，然后根據(jù)路由配置將用戶請(qǐng)求轉(zhuǎn)發(fā)到桶對(duì)應(yīng)的數(shù)據(jù)中心。

運(yùn)行時(shí)運(yùn)行時(shí)組件會(huì)負(fù)責(zé)生成路由表，該路由表指定了部分用戶流量從邊緣節(jié)點(diǎn)轉(zhuǎn)發(fā)到的數(shù)據(jù)中心，路由表由以下的一組元組構(gòu)成：

{edge:{datacenter:fraction}} 

為了生成由上述元組組成的路由表，Taiji 的運(yùn)行時(shí)會(huì)從監(jiān)控系統(tǒng)中讀取兩種類型的動(dòng)態(tài)數(shù)據(jù)：

基礎(chǔ)設(shè)施的運(yùn)維狀態(tài)，例如：容量、健康狀態(tài)、邊緣節(jié)點(diǎn)和數(shù)據(jù)中心的利用率;

測(cè)量數(shù)據(jù)，例如：邊緣節(jié)點(diǎn)的流量以及從邊緣節(jié)點(diǎn)到數(shù)據(jù)中心的訪問(wèn)延遲;

上述的這些數(shù)據(jù)都是未經(jīng)處理的原始數(shù)據(jù)，我們?cè)谡麄€(gè)系統(tǒng)中會(huì)引入讀取層抽象，幫助我們對(duì)原始數(shù)據(jù)進(jìn)行讀取、標(biāo)準(zhǔn)化以及聚合，這樣能夠減少運(yùn)行時(shí)其他部分的工作量，可以更好地對(duì)問(wèn)題進(jìn)行建模：

runtime-architecture

圖 2 - 運(yùn)行時(shí)架構(gòu)

Taiji 的運(yùn)行時(shí)會(huì)使用每秒的請(qǐng)求數(shù)(RPS)衡量無(wú)狀態(tài)服務(wù)的流量，使用用戶會(huì)話數(shù)量衡量有狀態(tài)服務(wù)的流量，該模型可以允許無(wú)狀態(tài)流量路由到任意可用的數(shù)據(jù)中心，并將有狀態(tài)的流量約束到相同的機(jī)器上避免影響建立的會(huì)話。

在每一個(gè)時(shí)間周期(Epoch)中，Taiji 都會(huì)根據(jù)數(shù)據(jù)中心的資源利用率重新評(píng)估全局的流量分配決策，在重新評(píng)估的過(guò)程中，該系統(tǒng)會(huì)使用如下所示的步驟改變數(shù)據(jù)中心的路由以滿足服務(wù)指定的策略：在兩個(gè)數(shù)據(jù)中心之間切換一單位的流量、識(shí)別當(dāng)前最優(yōu)的路由策略、不斷迭代直到不能實(shí)現(xiàn)更好的結(jié)果。除此之外，為了保證整個(gè)系統(tǒng)的穩(wěn)定，運(yùn)行時(shí)還需要控制流量調(diào)度的頻率，避免對(duì)單個(gè)數(shù)據(jù)中心造成較大的抖動(dòng)以影響整個(gè)系統(tǒng)。

流量管道

流量管道會(huì)消費(fèi)運(yùn)行時(shí)模塊輸出的路由表并使用關(guān)系感知路由在配置文件中生成特定的路由規(guī)則，當(dāng)我們生成了新的路由規(guī)則之后，該模塊會(huì)通過(guò)配置管理服務(wù)(Configuration Management Service、CMS)將規(guī)則同步到所有的邊緣負(fù)載均衡上，整個(gè)過(guò)程大概也只需要一分鐘左右的時(shí)間。

關(guān)系感知路由構(gòu)建在請(qǐng)求相同內(nèi)容的用戶流量具有局部性的特點(diǎn)上，這對(duì)數(shù)據(jù)的緩存和其他后端系統(tǒng)有積極的作用，正是因?yàn)榱髁烤哂羞@樣的特點(diǎn)，我們才會(huì)將高度關(guān)聯(lián)的用戶路由到相同的數(shù)據(jù)中心進(jìn)行處理，降低系統(tǒng)的延遲。

connection-aware-routing

圖 3 - 關(guān)系感知路由

如上圖所示，關(guān)系感知路由根據(jù)所屬的社區(qū)將用戶分到了不同的桶中，它會(huì)使用平衡樹(shù)保證每一個(gè)用戶桶中都有數(shù)量差不多的用戶，同時(shí)也最大化桶中用戶的關(guān)聯(lián)程度。然而桶的大小對(duì)系統(tǒng)的性能有著很重要的影響，過(guò)小的桶可能會(huì)使大的社區(qū)被分割，從而降低緩存的有效性;而過(guò)大的桶會(huì)提高緩存的有效性，不過(guò)會(huì)影響路由的精度，Taiji 期望每個(gè)桶的流量占全局流量的 0.01%，這樣才能在緩存有效性和路由精度之間做出平衡。

圖 4 - 用戶、桶和數(shù)據(jù)中心

整個(gè)系統(tǒng)不僅需要將用戶分到不同桶中，還需要把桶中的用戶分配到不同的數(shù)據(jù)中心，這需要消耗非常大的計(jì)算量，為了解決關(guān)系感知路由的問(wèn)題，流量管道模塊會(huì)通過(guò)以下兩個(gè)部分在局部性和穩(wěn)定性之間做出平衡：

• 離線任務(wù) — 用戶、桶分配;
• 在線任務(wù) — 桶、數(shù)據(jù)中心分配;

上述的這種方式可以讓同一個(gè)社區(qū)轉(zhuǎn)發(fā)到相同數(shù)據(jù)中心的流量從 55% 提高至 75%，能夠非常明顯地提高后端服務(wù)的資源利用率，接下來(lái)我們將分別介紹上述兩種不同的任務(wù)以及邊緣節(jié)點(diǎn)負(fù)載均衡處理請(qǐng)求的過(guò)程。

離線模塊

系統(tǒng)中的社區(qū)層級(jí)會(huì)以完全二叉樹(shù)的結(jié)構(gòu)表示，二叉樹(shù)的葉節(jié)點(diǎn)是用戶組成的桶，內(nèi)部的節(jié)點(diǎn)表示子樹(shù)中的所有桶，我們會(huì)使用社交哈希(Social Hash)構(gòu)造整棵樹(shù)。因?yàn)闃?shù)的構(gòu)造是離線的，同時(shí)也需要非常大的計(jì)算量，所以系統(tǒng)會(huì)以周的頻率定期更新二叉樹(shù)。

雖然使用二叉樹(shù)的方式分割用戶比較有效，但是也無(wú)法適用于全部的場(chǎng)景，它在以下兩種情況中并不能很好地工作：

• 用戶訪問(wèn)高度連通的實(shí)體，例如：各種明星以及名人，這種場(chǎng)景更類似于發(fā)布和訂閱消息;
• 一次性的交互，例如：支付等一次性的臨時(shí)操作，類似的交互不會(huì)被系統(tǒng)看做用戶之間存在關(guān)聯(lián);

在線模塊

流量管道的在線模塊會(huì)根據(jù)離線模塊生成的樹(shù)狀結(jié)構(gòu)、每個(gè)桶的流量以及數(shù)據(jù)中心的容量為桶分配合適的數(shù)據(jù)中心，該過(guò)程會(huì)盡量將一組相鄰的桶分配到同一個(gè)數(shù)據(jù)中心以提高數(shù)據(jù)的訪問(wèn)局部性。

圖 5 - 桶和段

我們可以把樹(shù)中桶分成個(gè)段，其中是社區(qū)層級(jí)的高度，在線模塊會(huì)以段為單位將數(shù)據(jù)分配給不同的數(shù)據(jù)中心，如上圖所示，如果 2 號(hào)段被分配到了某個(gè)數(shù)據(jù)中心，那么 1 號(hào)和 2 號(hào)桶都會(huì)被分配到該數(shù)據(jù)中心，的選擇需要考慮到穩(wěn)定性和局部性，該高度越低，數(shù)據(jù)的局部性就越高，但是穩(wěn)定性也越低，數(shù)據(jù)段更可能分到不同的桶中。

邊緣負(fù)載均衡

轉(zhuǎn)發(fā)既然邊緣節(jié)點(diǎn)需要負(fù)責(zé)將用戶的請(qǐng)求轉(zhuǎn)發(fā)到特定的數(shù)據(jù)中心，那么所有的邊緣節(jié)點(diǎn)都需要存儲(chǔ)路由表以確定處理當(dāng)前請(qǐng)求的數(shù)據(jù)中心，不過(guò)直接存儲(chǔ)用戶到數(shù)據(jù)中心的路由表需要占用非常大的內(nèi)存，所以邊緣節(jié)點(diǎn)只會(huì)存儲(chǔ)桶到數(shù)據(jù)中心的映射，當(dāng)用戶向邊緣節(jié)點(diǎn)發(fā)出動(dòng)態(tài)內(nèi)容請(qǐng)求時(shí)會(huì)經(jīng)過(guò)以下過(guò)程：

初始用戶請(qǐng)求沒(méi)有桶的信息，用戶會(huì)把它路由到最近的數(shù)據(jù)中心;

最近的數(shù)據(jù)中心會(huì)存儲(chǔ)用戶對(duì)應(yīng)的桶，我們會(huì)將用戶的桶寫(xiě)入 Cookie;

之后的請(qǐng)求都會(huì)攜帶 Cookie，邊緣負(fù)載均衡會(huì)把請(qǐng)求直接路由到特定的數(shù)據(jù)中心;

關(guān)系感知路由會(huì)在原有的請(qǐng)求處理路徑上帶來(lái)可以忽略不計(jì)的額外開(kāi)銷，桶到數(shù)據(jù)中心的映射文件會(huì)每五分鐘同步一次，大小約為 15KB，這樣的內(nèi)容在網(wǎng)絡(luò)中的傳輸開(kāi)銷幾乎是可以忽略不計(jì)的。

總結(jié)

Facebook 在這篇論文中介紹的 Taiji 系統(tǒng)能夠在數(shù)據(jù)中心的維度對(duì)系統(tǒng)整體的負(fù)載進(jìn)行調(diào)節(jié)，F(xiàn)acebook 作為社交網(wǎng)絡(luò)的巨頭，它的很多業(yè)務(wù)都與社交和用戶關(guān)系相關(guān)，而該系統(tǒng)基于的關(guān)系感知路由也是為它的業(yè)務(wù)量身定做的，正是因?yàn)楦叨汝P(guān)聯(lián)的用戶會(huì)請(qǐng)求類似的內(nèi)容，所以基于關(guān)系的路由才能優(yōu)化系統(tǒng)，將用戶請(qǐng)求路由到最近的、利用率低的集群，也能夠提升系統(tǒng)的訪問(wèn)局部性并減少計(jì)算資源的消耗。

本文轉(zhuǎn)載自微信公眾號(hào)「真沒(méi)什么邏輯」，可以通過(guò)以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系真沒(méi)什么邏輯公眾號(hào)。