Akamai在内容分发网络中的算法研究(翻译总结)

作者介绍:钱坤,腾讯后台开发工程师,从事领域为流媒体CDN相关,参与腾讯TVideo平台开发维护。

原文是《Algorithmic Nuggets in Content Delivery》。这篇文章是akamai15年的文章,里面介绍了一些akamai在内容分发网络中的算法研究,下面对论文中的这些算法进行简单的总结。水平有限有限,有理解错误的还望指正。

ps:并不是所有的算法都已经投入到了实用阶段。

BLOOM FILTERS

Bloom filters的研究主要用在akamai的CDN中的两个场景:1)索引管理优化;2)内容过滤。

Bloom filters是hash算法的一个变种,有非常优秀的空间效率(使用位数组)和时间效率(插入的时间复杂度稳定为常数),但是会有一定的错误率。直观的说,bloom算法类似一个hash set,用来判断某个元素(key)是否在某个集合中。和一般的hash set不同的是,这个算法无需存储key的值,对于每个key,只需要k个比特位,每个存储一个标志,用来判断key是否在集合中。其基本算法如下:

1)首先需要k个hash函数,每个函数可以把key散列成为1个整数

2) 初始化时,需要一个长度为n比特的数组,每个比特位初始化为0

3) 某个key加入集合时,用k个hash函数计算出k个散列值,并把数组中对应的比特位置为1。

4) 判断某个key是否在集合时,用k个hash函数计算出k个散列值,并查询数组中对应的比特位,如果所有的比特位都是1,认为在集合中。

通过一系列balabala的数学证明,可以得出最优hash函数个数k、位数组的位数m、存储的最元素数n关系如下:

再通过一系列balabala的数学证明,可以得出正向错误率、位数组的位数m、存储的最元素数n关系如下:

根据这两个公式,可以进行参数调整以达到预期目标。Bloom filters的主要场景如下:

1)索引管理优化:有些cache系统的索引查询可能由于访问慢设备导致查询操作较慢,可以在索引查询之前用使用Bloom filters搭建一层索引cache提升索引查询速度,如果Bloom filters中无法查到该文件,则认为该文件不存在,如果Bloom filters中可以查到该文件,则请求索引系统。在这种场景中由于存在元素删除操作,Bloom filters不能使用位数组,每一位需要用一个数字变量来代替,当多个文件共用一位时使用递增。

2)内容过滤:akamai统计了一个server cluster两天中web文件访问次数,如下图,可以发现,在总共4亿左右的文件中,有74%的文件仅被访问过一次,90%文件访问次数少于4次。

仅有单次访问的文件是没有必要落盘的,对于这种文件落盘会占用磁盘io和存储,并且可能会将更热的文件挤掉,进而降低cache命中率导致回源带宽增高。

以此为基础,akamai实现了“Cache-on-second-hit rule.”算法,即文件被第二次访问才落盘,而记录是否有过第一次访问所使用的算法就是Bloom filters。

由于cdn上被访问的文件数趋近于无穷,所以可以使用两个Bloom filters交替来记录文件第一次被访问,当第一个Bloom filters已经到了能记录的上限,就使用第二个Bloom filters,如果第二个也到了上限,则清空第一个Bloom filters重新使用第一个,每次查询文件是否曾经被访问需要查询两个Bloom filters。

Akamai实现了这个组件之后在测试环境进行了测试,从下面的测试结果来看,测试环境缓存命中率从74%上升到了83%,磁盘写数据量下降了44%,磁盘操作时延下降了24%。

稳定分配问题

稳定分配问题的研究主要被用于全局负载均衡。

在cdn中的网络中可以抽象出两个概念。

1)map unit,map unit包含两个元素,第一个元素是用户ip的集合,第二个元素是map unit的类型(比如video、web等)

2)server cluster,akamai的服务器集群最小单位是cluster,一个cluster中包含若干服务器。通过对map unit和server cluster进行稳定分配,可以实现全局负载均衡。

Akamai对Gale-Shapley算法进行研究拓展以用于解决全局负载均衡问题。标准的Gale-Shapley算法是被提出用来解决“稳定婚姻问题”的:为n个男性和n个女性互相找到最合适的配偶。算法的基本思路为,先对所有男士进行落选标记,称其为自由男。且每个男士和每个女士均有一份排序,在排序中标记心仪的异性排名。当存在自由男时,进行以下操作:

(1)每一位自由男在所有尚未拒绝她的女士中选择一位被他排名最优先的女士;

(2)每一位女士将正在追求她的自由男与其当前男友进行比较,选择其中排名优先的男士作为其男友,即若自由男优于当前男友,则抛弃前男友;否则保留其男友,拒绝自由男。

(3)若某男士被其女友抛弃,重新变成自由男。

把这个算法基于以下的点进行拓展用于对map unit和server cluster进行匹配,也就是全局负载均衡。

(1)map unit和server cluster数目并不相等。在正常的cdn场景中,map unit的数目是要多于server cluster的数目。

(2)排序列表可以不完整。没有必要建立一个map unit到所有的server cluster的性能分数排序,只需要选择出该用户组可能被调度到的服务器集群并进行打分排序即可。

(3)每个server cluster拥有不确定的任意的容量。估算server cluster的容量,并让它为多个用户组进行服务。

有了拓展的Gale-Shapley算法作为框架,再对机器的资源进行细化,一个server cluster中一台机器的资源可以具体分为两种:网络资源和非网络资源(如内存、cpu能力等)。网络资源消耗用BPS来表示,非网络资源消耗用FPS来表示。那么可以用如下一个分层的资源树来对一个机器的资源进行表示:

Node A代表机器的可用网络资源为50BPS,node B代表机器可用的非网络资源为30FPS,叶子节点代表不同的请求类型可以使用的FPS上限。

如果这时收到20单位video请求,每单位请求占用0.25FPS和1BPS,那么资源树剩余资源如上图中蓝字所示,node A剩余30BPS,node B剩余25 FPS,node C剩余25 FPS。

假设接下来收到26单位的web请求,每个请求消耗1FPS和0.2BPS,总共需要消耗26FPS和6.2BPS,这时发现当前机器的资源不足以承受全部的web请求,这时会根据Scoring(akamai用来评估客户端和服务器的服务性能的组件)的输出判断该cluster和哪种map unit之间有更好的性能,如果结果是更适合于服务新来的web请求,则按照Gale-Shapley算法会驱逐4单位的旧video请求,并接纳新来的web请求。反复进行这种驱逐操作可以让全局实现最优分配。

感觉这个算法在具体的实现细节上还存在着很多挑战。

一致性hash

一致性hash的研究被用来实现akamai的cdn局部负载均衡。感觉一致性hash应该和akamai有着千丝万缕的联系,比如两者都是来源于MIT,一致性hash的提出人曾经在akamai工作等等。

当用户被分配到一个server cluster之后,需要尽可能通过一致性hash将同样的文件请求尽可能的hash到某台已经在cache中缓存了该文件的机器上。所以可以通过一致性hash提升cache命中率,来达到提升性能和增加资源有效利用率的目的。

关于最基本的一致性hash算法网上有很多讲解,一致性hash解决了当分布式系统中某台cache down掉了或者新加入一台cache可能会导致所有cache内容要重新洗牌的问题。并引入虚拟节点来优化算法结果。这些内容网上有很多,就不在重复了。下面说一些论文提到的akamai对于一致性hash的特性化改造:

1)对于热点文件,为了防止请求压在服务器组内同一台机器上,需要将一个热点文件映射到k台服务器上进行分流,比较方便的方式为将文件映射在原本的hash出来的机器上以及之后的(k-1)台机器上。不同的热点文件集合在做一致性hash的时候,需要变换hash桶的排列,以防止由于hash值接近导致不同文件所映射的k台机器大部分重合,从而导致机器高负载的问题。

2)用户所使用业务也是做一致性hash需要考虑的输入之一。对于一个在akamai上注册的业务,会得到一个或多个统一分配的序列号,akamai可以按照序列号对对象存储,并将对于同样序列号的不同文件请求hash到cluster同一个机器(或集合),以尽可能满足某些客户端复用连接下载多个对象的需求(比如尽可能的把同一个web界面上的小对象存储到一台机器上)。

Leader election与数据一致性

即使两个机器上的运行程序完全相同,由于运行时的分别独立收集输入数据可能导致输出结果不相同的情况,这种情况需要leader election来在服务器组里选择一个leader来向其他的服务器分发运算结果,以统一输出。Leader的选择过程中会遇到数据一致性的问题,这种一致性的问题可以通过paxos或者raft算法来解决。我找到以下的两个地址,感觉对两个算法讲的比较容易理解:

Paxos:paxos和分布式系统

Raft:Understandable Distributed Consensus

leader election有两种:

1)At-Least-One Leader Election:至少要选择一个leader。

2)At-Most-One Leader Election:最多只有一个leader被选择出来。

比如当网络出现问题导致一个集群出现两个子网,如果使用At-Most-One Leader Election类的算法不会允许选择出两个leader,而是选择宁可放弃leader选举的过程,使用比较旧的决策数据。比如akamai用户组划分的过程,如果网络中出现两份用户组划分的结果,会引发全局负载均衡运算出现问题,所以在这种情况下不能选举出两个leader,宁可使用旧一点的用户组划分结果。

原创声明,本文系作者授权云+社区-专栏发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏腾讯技术工程官方号的专栏

TDSQL 全时态数据库系统--核心技术

1803
来自专栏xingoo, 一个梦想做发明家的程序员

批处理作业调度-回溯法

问题描述:   给定n个作业,集合J=(J1,J2,J3)。每一个作业Ji都有两项任务分别在2台机器上完成。每个作业必须先有机器1处理,然后再由机器2处理。作业...

1798
来自专栏进击的程序猿

图数据库奥秘初探

主要参考书籍:graph database 近期工作中要做一些图谱的应用,于是这几天就调研了下图数据库,最后就有了本文。ps:本人第一次做图谱相关的应用,具体...

532
来自专栏Golang语言社区

C++ 实现银行排队服务模拟

教程简介:使用 C++对银行排队服务进行模拟,以事件驱动为核心思想,手动实现模板链式队列、随机数产生器等内容,进而学习概率编程等知识。作为可选进阶,这个模型同时...

34312
来自专栏数据和云

如何编写更好的SQL查询:终极指南(下)

SQL是数据挖掘分析行业不可或缺的一项技能,对于SQL来说,编写查询语句只是第一步,确保查询语句高效并且适合于你的数据库操作工作,才是最重要的。在上一篇文章中,...

2736
来自专栏北京马哥教育

一致性hash原理与实现

一、背景介绍 memcached的分布式 memcached虽然称为“分布式”缓存服务器,但服务器端并没有“分布式”功能。服务器端内存存储功能,其实现非常简单。...

3237
来自专栏跨界架构师

分布式系统关注点——仅需这一篇,吃透「负载均衡」妥妥的

  上一篇《分布式系统关注点——初识「高可用」》我们对「高可用」有了一个初步认识,其中认为「负载均衡」是「高可用」的核心工作。那么,本篇将通过图文并茂的方式,来...

582
来自专栏用户画像

2.4 物理层本章小结

传输媒体并不是物理层。由于传输媒体在物理层的下面,而物理层是体系结构的第一层,因此有时称传输媒体为0层,在传输媒体中传输的是信号,但传输媒体并不知道所传输的信号...

822
来自专栏跨界架构师

分布式系统关注点——仅需这一篇,吃透「负载均衡」妥妥的

  上一篇《分布式系统关注点——初识「高可用」》我们对「高可用」有了一个初步认识,其中认为「负载均衡」是「高可用」的核心工作。那么,本篇将通过图文并茂的方式,来...

802
来自专栏SeanCheney的专栏

《Python分布式计算》第1章 并行和分布式计算介绍 (Distributed Computing with Python)并行计算分布式计算共享式内存vs分布式内存阿姆达尔定律混合范式总结

本书示例代码适用于Python 3.5及以上。 ---- 当代第一台数字计算机诞生于上世纪30年代末40年代初(Konrad Zuse 1936年的Z1存在争议...

2728

扫码关注云+社区