算法系列:CDN背后的数学

以上所有内容将我们带回到一致哈希以及它如何使用模数学是一个更大的算法的一部分旨在首先避开“热点”或重载在原始服务器上，也更有效地在“多个”中分发内容请求的百家乐软件”.S. 专利没有. 8458259为基数.

哈希已经以各种方式用于流媒体，而不仅仅是用于CDN存储解决方案. 开源哈希工具xxHash, 例如, 正在被Netflix用于文件传输, 已经集成到微软 Azure平台，也在数据库中使用，例如MySQL，其中通常存储清单文件和用户帐户信息.

越简单的内容和关键结构，可能性电位越高可能会发生冲突，因此许多散列解决方案都变成了长字母数字字符串. 有些还包括加密，其中初始值用已知的加密密钥进行加密.

哈希的另一个问题是它不是随机的，这意味着它不是万无一失的 in 避免碰撞. 但即使是服务器上内容放置的真正随机化也存在这种问题碰撞的可能性, 因为随机数生成可能导致两个或多个内容片段被分配为相同的整体数量. 话虽如此，还是有办法使用的哈希作为真正随机的一个不错的替代品在一个或多个服务器上放置内容同时还能避免碰撞.

当缓存服务器存储从原始服务器复制的内容副本时，它也只有有限的存储空间. 因此，长尾或不太受欢迎的内容(如由布隆过滤算法决定)可能从离最终用户最近的缓存服务器中删除. 的请求缓存服务器导致缓存丢失, 缓存服务器必须与原始服务器联系以满足最终用户的请求.

我们会时不时地回到缓存比率概念，但让我们停在这里，注意专利中的另一点:

如果更多的客户机共享相同的缓存服务器，则需要权衡更大的性能优势反对增加的可能性缓存服务器本身将变得过载. 解决这一困境的一个方法是是使用一组服务器一起作为缓存吗.

专利申请接着指出, 虽然, 仅仅以线性方式投入更多的服务器并不能解决问题. 我们将马上讨论建议的方法, 但是现在, 让我们考虑一下如何在给定位置跨缓存服务器集群搜索内容.

而不是要求终端用户请求遍历集群中的所有服务器, 散列和模的组合可以帮助限制搜索的服务器数量, 哪一种方法减少了整体搜索的复杂性和时间.

在本文前面，我提到了模余数有助于确定哪个服务器给定的数据可能最接近. 有一个很好的解释卡内基梅隆大学网站, 我们用社保号的例子来说明取模的意义, 哈希, 以及缓存服务器存储的映射.

对于本例，我们将假设有19台服务器. 我们用19，因为它是质数. 作为模数的素数, 它不太可能返回余数为零, 这意味着大多数内容将映射到服务器1-9.

让我们以约翰·菲茨杰拉德·肯尼迪为例, 总统图书馆网站上的社保号码是026-22-3747. 如果我们去掉破折号，我们得到的哈希值是026223747. 确定哈希26223747的内容驻留在三个服务器中的哪一个, 我们将使用以下公式:

26223747 mod 19 = 4

约翰·菲茨杰拉德·肯尼迪就是这样在这个特定服务器集群的缓存服务器4上找到吗. 如果内容不在那里, 向源服务器发出的请求不仅将内容返回给最终用户，而且还将内容返回给缓存服务器4，以供后续用户请求使用. 内容在给定服务器上不可用的一个原因, 即使是几天前的事, 是否使用业务规则，如Bloom过滤, 它主动地从缓存服务器中删除不太流行的内容，以便在集群的存储中为更流行的内容腾出空间.

模缓存方法非常简单，但是非常有效，因此在Java等编程语言中也有使用, 哪个使用mod 31进行计算. 除了31是质数又是奇数这个事实, 它也是2减1的幂(32等于2的五次方). 考虑到计算在2的幂下(包括32位和64位)效果最好, 这意味着31在计算上也更省力.

好了，我们知道内容应该驻留在哪个缓存服务器上. 但是，如果缓存集群中的服务器数量发生变化会发生什么呢, 要么是服务器故障，要么是添加了服务器? 如果我们从19个服务器减少到18个服务器, 我们的哈希示例的公式如下:

26223747 mod 18 = 15

因此，对服务器4的任何内容请求都可能是错误的. 更糟糕的是, 虽然, 在传统的服务器集群中, 映射到所有缓存服务器的所有散列键都需要重新计算. 对于一个服务器故障来说，这是大量的工作.

最后, 同样值得注意的是，哈希表不是必需的, 但它们加快了单个服务器上的搜索速度，并充当了多服务器集群中哪台服务器包含所需信息的路线图.

循环缓存集群

一致性哈希的思想是以逻辑“循环”或“轮循”模式(这就是一致性哈希有时也被称为“环哈希”的原因)使用服务器的物理集群(可以在存在点中找到)。.

想想高中代数中关于圆的所有方程. 圆被分成360度. 现在不讲学位了, 把这个圆分成成千上万的条或碎片, 就像你把一个南瓜派分成12片，如果12个感恩节晚餐的客人都想要一片. 12个人中的每一个人分到的馅饼都比你只需要分给8个客人的馅饼要小, 但每位客人至少都能分到一块馅饼.

同样的概念也适用于环中的服务器(n):添加一个额外的服务器, 服务器负载可能会减少额外服务器的一定百分比(n +1). 如果你有13台服务器，每台承载1/13(或7.占服务器集群总负载的692%), 然后再增加一个服务器(1/13+1或1/14), 那么每台服务器只需要承担7个.占服务器集群总负载的142%.

但是如何在可用的服务器上均匀地解析负载? 这就是一致性散列发挥作用的地方, 正如1997年的论文所描述的，以及文章开头提到的麻省理工学院的专利.

一致性哈希是一个强大的工具，不仅适用于初始缓存，也适用于服务器集群中服务器数量经常变化的场景. 它也被用于解决方案，如亚马逊的DynamoDB和大数据数据库集群模型，如Cassandra和Riak.

环散列的最基本形式是将服务器放在一个假想的圆上，彼此距离相等. 如果有三台服务器, 例如, 它们可以手动间隔120°(想象一下服务器被放置在12点钟方向的时钟), 4点钟, 8点). 作为进一步自动化添加或删除服务器的一种方式, 也可以使用某种形式的唯一数字，然后将其绑定到环上的特定点.

算法系列CDN环散列

说明文档和服务器的环散列的图表，改编自美国.S. 专利没有. 8458259，在多个百家乐软件之间分配请求的方法和设备(go2sm.com/cdnpatent)

例如，服务器的静态IP地址为192.168.1.101，我们可以使用1921681101的散列将该服务器放置在环上的特定点上. 如果需要更换服务器, 然而, 新服务器必须使用相同的静态IP地址.

更好的是，虚环允许一致性散列抽象服务器的数量. 而不是将服务器映射到环，并将内容散列映射到服务器(服务器的数量可以更改), 一种更有效的方法是将内容哈希和缓存服务器哈希都映射到环本身.

回到高中基础数学, 我们知道一个圆从0°到360°, 我们可以用公式2求出最大值π 弧度. 然后，我们在0°和360°之间的某个度或部分度将哈希值分配给公式的输出.

算法系列CDN环散列

说明在环上插入新服务器或文档的图表(又称一致哈希), 改编自U.S. 专利没有. 8458259
(go2sm.com/cdnpatent)

通过将哈希表中的所有哈希值分布到圆上的某个位置, 当服务器数量上升或下降时，需要执行的唯一计算是，给定的服务器是否突然更接近散列在圆上的指定位置. 自从服务器的哈希值不是基于手动间隔，整体索引为每一个不需要计算集群中的单个缓存服务器.

那么碰撞呢?? 虽然它不可能产生和非-一样多的碰撞基于环的哈希——当然需要更少的重新计算哈希表-如果内容放置是任意的，手动实现的环哈希方法仍然有可能产生冲突.

为了解决这个问题, 麻省理工学院专利的一致散列方法使用顺时针方法来映射或重新映射内容和服务器的散列. 如果服务器和内容的位置不共享完全相同的散列(i.e., 环上的相同位置), 然后缓存解决方案按顺时针方向查找下一个最近的服务器，并将内容散列位置与附近的服务器散列位置关联起来.

中的任何位置都可以添加新服务器，并且对哈希表的唯一更新将发生在新服务器和在新服务器之前(或逆时针)最近的现有服务器. 从新服务器顺时针方向开始的内容散列将继续与已经分配给它们的服务器关联. 如果我们使用一个将单个服务器添加到现有七个服务器集群的示例, 新的总数是八服务器，内容服务器的百分比需要更新的哈希组合是个位数.

虽然有一种方法可以计算出需要更新哪些内容服务器散列组合的概率, 我们可以这样近似:100%的组合除以7个服务器等于最大潜力14.所有内容服务器哈希值的28% 需要更新的组合——相去甚远不需要在前面提供的其他示例中100%重新映射. 很有可能是平均是14个中的一半.28%(或大约7%)的内容服务器散列组合会这样做需要更新，这需要最少的百家乐软件时间并降低缓存丢失错误.

有些服务器比其他服务器更平等

如果所有服务器的CPU、内存、网卡相同卡和存储容量，这种方法是可行的好吧. 但是如果添加的新服务器是比现有的旧缓存功能强大两倍服务器? 在这种情况下, 使用加权, 其中，一个两倍强大的服务器被赋予两倍于旧服务器的权重.

假设我们有19个现有的服务器，并添加一个功能两倍的服务器. 而服务器的总数为20, 使用加权, 实际上我们同时考虑概率和环21台服务器的哈希位置(20台物理服务器，一个虚拟). 所以理想负荷是4.在21个物理和虚拟服务器中，任何给定服务器的所有内容存储和请求的76%, 而不是20台物理服务器的5%. 这增加了更健壮的服务器存储两倍的内容片段的可能性，并获得两倍的内容请求.

这种通过加权实现的虚拟化发挥了重要作用更重要的因素是将缓存服务器放在环上. 这些虚拟服务器可以用来减少缓存服务器之间的度数.

使用散列将服务器放置在环上的好处在于，虚拟服务器不需要沿着环与物理服务器相邻放置. 这意味着a 单个物理服务器可以分布在多个服务器上该环作为多个虚拟服务器，无论是否使用加权.