[[345832]]

『看看論文』是一系列分析計算機和軟件工程領域論文的文章，我們在這個系列的每一篇文章中都會閱讀一篇來自 OSDI、SOSP 等頂會中的論文，這里不會事無巨細地介紹所有的細節(jié)，而是會篩選論文中的關鍵內(nèi)容，如果你對相關的論文非常感興趣，可以直接點擊鏈接閱讀原文。

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

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

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

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

架構(gòu)

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

圖 1 - Taiji 架構(gòu)

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

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

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

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

{edge:{datacenter:fraction}} 

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

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

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

上述的這些數(shù)據(jù)都是未經(jīng)處理的原始數(shù)據(jù)，我們在整個系統(tǒng)中會引入讀取層抽象，幫助我們對原始數(shù)據(jù)進行讀取、標準化以及聚合，這樣能夠減少運行時其他部分的工作量，可以更好地對問題進行建模：

runtime-architecture

圖 2 - 運行時架構(gòu)

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

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

流量管道

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

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

connection-aware-routing

圖 3 - 關系感知路由

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

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

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

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

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

離線模塊

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

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

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

在線模塊

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

圖 5 - 桶和段

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

邊緣負載均衡

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

初始用戶請求沒有桶的信息，用戶會把它路由到最近的數(shù)據(jù)中心;

最近的數(shù)據(jù)中心會存儲用戶對應的桶，我們會將用戶的桶寫入 Cookie;

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

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

總結(jié)

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

本文轉(zhuǎn)載自微信公眾號「真沒什么邏輯」，可以通過以下二維碼關注。轉(zhuǎn)載本文請聯(lián)系真沒什么邏輯公眾號。