[[345832]]

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

本文要介紹的是 2019 年 SOSP 期刊中的論文 —— Taiji: Managing Global User Traffic for Large-Scale Internet Services at the Edge[^1]，該論文介紹的 Taiji 是 Facebook 在大規模互聯網服務中動態管理用戶流量的系統，通過該系統我們可以平衡各個數據中心的資源利用率并降低用戶請求的網絡延遲。

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

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

為了解決上述的問題，Facebook 的工程師設計出了全球用戶流量管理系統，該系統將邊緣節點到數據中心的路由過程看做分配問題(Assignment Problem)，我們會通過約束優化器生成路由表，路由表能夠決定處理用戶請求的數據中心，邊緣節點會遵循路由表轉發用戶請求。

架構

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

圖 1 - Taiji 架構

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

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

如上圖所示，邊緣節點的負載均衡解析所有的用戶請求并將用戶映射到合適的桶中，然后根據路由配置將用戶請求轉發到桶對應的數據中心。

運行時運行時組件會負責生成路由表，該路由表指定了部分用戶流量從邊緣節點轉發到的數據中心，路由表由以下的一組元組構成：

{edge:{datacenter:fraction}} 

為了生成由上述元組組成的路由表，Taiji 的運行時會從監控系統中讀取兩種類型的動態數據：

基礎設施的運維狀態，例如：容量、健康狀態、邊緣節點和數據中心的利用率;

測量數據，例如：邊緣節點的流量以及從邊緣節點到數據中心的訪問延遲;

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

runtime-architecture

圖 2 - 運行時架構

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

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

流量管道

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

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

connection-aware-routing

圖 3 - 關系感知路由

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

圖 4 - 用戶、桶和數據中心

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

• 離線任務 — 用戶、桶分配;
• 在線任務 — 桶、數據中心分配;

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

離線模塊

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

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

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

在線模塊

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

圖 5 - 桶和段

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

邊緣負載均衡

轉發既然邊緣節點需要負責將用戶的請求轉發到特定的數據中心，那么所有的邊緣節點都需要存儲路由表以確定處理當前請求的數據中心，不過直接存儲用戶到數據中心的路由表需要占用非常大的內存，所以邊緣節點只會存儲桶到數據中心的映射，當用戶向邊緣節點發出動態內容請求時會經過以下過程：

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

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

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

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

總結

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

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