美國36%流量背後 Netflix CDN分發算法優化

文 / Mohit Vora, Andrew Berglund, Videsh Sadafal, David Pfitzner, and Ellen Livengood

譯 / Ant，趙軍 

技術審校 / 扶凱

CDN的原理就是将使用者想要的内容放在距他盡可能近的地方，以最低的成本擷取。當面對海量的内容和使用者時，情況就變得很複雜。同時，任何裝置都可能出現故障而失效，系統能夠面對任何一個裝置失效被替換的情況，同時保證從叢集到伺服器各個硬體單元之間保持負載均衡。根據您2015年的統計，Netflix占據了美國36%的流量。本文将揭示Netflix如何應對如此巨大的流量，通過不斷改進的算法快速配置設定熱門内容，并保證整個CDN網絡平穩運作。

LiveVideoStack對本文進行的翻譯，感謝英特爾資深軟體開發工程師趙軍和雲帆加速聯合創始人&CTO扶凱協助完成翻譯和審校。

之前我們曾經讨論過内容的流行度，通過計算、預測以及使用内容的流行度來最大化的發揮Open Connect（Netflix發起的開放CDN平台）的硬體基礎設施的能力，同時我們也讨論了這一領域的一些其他資料科學的挑戰。我們還在最近的文章讨論了如何提升伺服器的吞吐量(throughput)的問題。本文，我們将深入讨論如何在Open Connect伺服器（有時也稱作 Open Connect Appliances 或者 OCAs）上配置設定内容，包括我們的哈希政策以及如何處理異構伺服器叢集。這個工作是Nexflix的Open Connect團隊與Science & Analytics 團隊一起合作的一個成果。

内容(檔案)放置政策與目标

檔案的放置政策涉及到決定把哪些檔案内容放署在哪些叢集的哪個伺服器上（更多内容可以參考早期文章，它綜述了為什麼這些決定是非常重要的）。一般而言，為了讓叢集的流量最大化，應該把最流行(熱門)的内容放在目前叢集中；并保證叢集中的每台伺服器上是負載均衡。其次，要保證叢集長期的穩定，尤其是在增加或移除伺服器過程中保持穩定(不能讓熱點失效)。最後，這個配置設定檔案内容放置政策與目錄算法必須在有限時間就要計算出來的(時間過久會影響分發效率)。

統一的一緻性哈希（Uniform Consistent Hashing）

我們使用一緻性哈希在多個伺服器中分發内容。想象一個圓環，從0一直到N（見圖1）。伺服器ID從S1到Sn哈希後分布在這個圓環中，每個伺服器ID的哈希值h(Si)之前的空間為他自己所有（在圖2中被塗上了一種顔色）。内容ID從C1到Cm哈希後也在同樣的圓環中。于是，每個内容ID的哈希Ci落在了伺服器ID哈希Si的空間中。

圖1，圖2，圖3

另外，我們把每個伺服器ID（S1到Sn）哈希了1000次以使得内容(content)合理的均勻分布，且當叢集伺服器發生增減時，為了促進公平再次進行哈希。通過使用統一的一緻性哈希，我們為每個伺服器配置設定了一個相同的權重，最終我們發現盡可能多的需要被替換的特定内容。

采用這種技術，對伺服器的擾動做到最小。當增加或删除檔案内容時，伺服器隻需要對這些變動的檔案内容的切片進行下載下傳或删除操作。當叢集增加伺服器時，當有1000個新的切片過來時, 會分布在整個哈希的圓環中，新的伺服器所要處理的切片數量與其他伺服器差不多。類似的，當伺服器從叢集移除時，他自己的1000個切片也會删除，他所管理的内容會在伺服器移除後重新平均哈希到到叢集中的其他伺服器。

異構叢集配置設定

伺服器異構

對于Netflix而言，當引入一組異構伺服器會導緻額外的複雜性，一緻性哈希是次優的方法(對同一叢集非常有效)。我們的伺服器主要分為兩類，即磁盤存儲和SSD存儲。磁盤存儲伺服器大部分由機械磁盤組成，提供最高200TB空間，大約40Gbps的吞吐率。SSD伺服器完全由SSD磁盤組成，提供最大100Gbps的吞吐率，最大支援18TB空間。在一些中小型的ISP服務商，我們隻托管磁盤存儲伺服器。在我們的IX和大型的ISP服務商中，會托管兩種伺服器，SSD伺服器處理大部分流量，磁盤伺服器負責存儲所有的目錄檔案。

我們的硬體團隊，建立了一套新的伺服器以應對日益增長的容量需求。為了最大的彈性，我們需要讓新的伺服器與老伺服器并肩戰鬥，而無需在資源利用上進行妥協。另外，任何一個磁盤都可能壞掉，我們要自動的将損壞的磁盤屏蔽掉，這會導緻即使是相同的伺服器，其磁盤空間也不盡相同。總而言之，這些複雜性意味着，叢集中的伺服器有着不同級别的存儲量和吞吐量。

當伺服器時同構時，一緻性哈希工作非常不錯；但在伺服器異構情況下，整個系統趨于資源的過載或低載。

不同的存儲空間：由于叢集中的伺服器容量不同（比如，4個100TB的伺服器和1個50TB的伺服器組成一個叢集），還使用一緻性哈希會産生1/5的空洞内容（從第250TB的标記到500TB的标記之間）, 因些我們會在存儲的熱門檔案中建立一個間隔（我們稱之為“内容洞”）。在某些情況下，“内容洞”會導緻檔案内容不可用。

不同的吞吐量：在2016年，我們構造的伺服器在18TB容量（SSD）下支援100Gbps的吞吐量；而我們大部分産品化部署的SSD伺服器吞吐量為40Gbps，12TB容量。因為伺服器的流量正比于存儲空間3：2 （18T：12T），但目标流量比例應該接近于 5：2（100Gbps : 40Gbps），此時一緻性哈希不能把這兩種伺服器放到一個叢集中。

如何應對這一狀況呢？我們開發了新的算法稱之為異構叢集配置設定（HCA，Heterogeneous Cluster Allocation）。通過智能的配置設定内容，HCA算法可以更好的發揮基礎設施的性能。

HCA通過調整配置設定協定來解決上述問題。基本的原理很簡單——保留了一緻性哈希，但通過一個模型來調整不同伺服器上的内容權重。權重的調整是通過改變每個伺服器在一緻性哈希圓環上的哈希片段的數量來實作的。

算法

我們有兩個條件需要被滿足：

1. 内容分布正比于每個伺服器的存儲能力，且不引起内容洞
2. 根據每個伺服器的吞吐量分布熱資料和冷資料

一個簡單的權重一緻性雜湊演算法——給每台伺服器配置設定不同的權重，可以滿足上述兩個條件中的之一，但不能同時支援。如果要同時支援兩個條件，我們需要兩個不同配置設定權重的集合---- 一個是為流行的内容，另一個為非流行内容。

HCA算法分兩個階段配置設定内容，每個階段都有自己的權重一緻哈希環。要配置它，我們必須為每個階段的每台伺服器指定權重，以及一個目錄深度D（截點）用于從階段1切換到階段2。給定每個伺服器的存儲和吞吐量規格，區域和候選截點D，我們制定和解決一個優化問題，其解要麼是産生滿足上述兩個條件的配置設定權重集合， 要麼就确定截點D是不可行的（沒有配置滿足限制條件）。 

雖然可能存在沒有HCA配置滿足某些叢集和流行度曲線組合的情況，但是我們發現，在實踐中通常存在大範圍的可行截止D。對于最終的HCA配置，我們選擇導緻跨過截斷點的内容的最小擾動的截止D *。例如，如果截止點在目錄深度D處，并且特定可下載下傳内容的流行度排名在第一晚和下一晚由于受歡迎程度的變化，它會在連續的時間點配置設定在不同的環，并可能搬移到不同的伺服器。我們選擇其搬移機率最小的截斷點。

我們還需要處理群集配置發生變化的情況 - 例如，在群集中添加或删除OCA時，如果HCA的重新配置改變截止D *或令牌數量，這種情況也可能導緻擾動。為了緩解這種影響，我們可以放大或縮小每個區域的令牌數量（隻有它們的比例重要，而非絕對數量）以在重新配置之間産生較小的擾動。

結果

使用HCA算法在OCA的伺服器上分發資料是很有價值的，并伴随着内容洞減小，以及負載均衡能力提升。

LiveVideoStack招募全職技術編輯和社群編輯

LiveVideoStack是專注在音視訊、多媒體開發的技術社群，通過傳播最新技術探索與應用實踐，幫助技術人員成長，解決企業應用場景中的技術難題。如果你有意為音視訊、多媒體開發領域發展做出貢獻，歡迎成為LiveVideoStack社群編輯的一員。你可以翻譯、投稿、采訪、提供内容線索等。

通過[email protected]聯系，或在LiveVideoStack公衆号回複『技術編輯』或『社群編輯』了解詳情。