美国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社区编辑的一员。你可以翻译、投稿、采访、提供内容线索等。