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，宁可使用旧一点的用户组划分结果。

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