基于hash计算的多层实验流量切分的实现

1. 背景介绍

站点新功能或者是站内新策略开发完毕之后，在全流量上线之前要评估新功能或者新策略的优劣，常用的评估方法是A-B测试，做法是在全量中抽样出两份小流量，分别走新策略分支和旧策略分支，通过对比这两份流量下的各指标的差异，我们可以评估出新策略的优劣，进而决定新策略是否全流量。

上文中提到的抽样是指按照某种确定的随机化方法，对线上流量进行划分。抽样可以指这种划分的方法，也可以指划分得到的一个流量子集。抽样是一种特殊的小流量，要求对流量的划分必须保证均匀性和随机性，并且可以根据需求过滤掉不符合规范的部分，我们把抽样的过程分为流量切分和流量筛选两个步骤，流量切分是指把全流量进行均匀的打散，提取出其中固定的流量比例，流量筛选是对流量切分的辅助，筛选过程就是从切分好的流量中过滤掉不符合规范的部分，本文主要涉及的是流量切分的实现。

2. 单层流量切分架构

做到流量切分的常用的方法是单层流量切分，流量切分需要以某种方式进行，即流量切分的打散依据，例如，我们可以依据流量中的cookie打散，或者是随机打散等，打散的方式不同，切分的对象全集也就不同了，如果我们依据cookie打散，那么我们的切分对象全集就是所有的cookie，如果是随机打散，那么我们的切分对象全集就是该站点的所有的流量。

图1.1 单层流量切分架构示意图

有了上面的想法，我们如何实现单层流量切分呢？如图1.1所示，我们按照指定的流量切分方式，将所需要的输入参数先经过一次hash计算，产生结果的均匀性和随机性由hash算法来保证，有了hash产生的结果，流量切分的过程还没有结束，我们还需要将hash结果对应到切分对象的全集上面，实现方法是将切分对象全集看作是一个区间段，然后将hash结果对应到区间段上面，区间的大小是切分的最小粒度决定的，例如，如果需要最小切分粒度为0.01%，则我们选取的区间段为［0，9999］，有了区间段的定义，我们可以将hash结果对一个数值取模，这个数值等于区间段最大值加1，取模之后的结果可以唯一的对应到切分对象全集区间上面，这样我们就将所有的流量打到了流量切分对象全集上面。

最后，我们再将区间段按照实验需求细分，划分成若干子区间，用作于实验对比，例如下图所示，将整个100%的区间分为多个子区间，每个子区间使用唯一的编号——sid，作为区间的唯一的标识，sid=1的子区间对应的流量为1%，那么它的子区间就是［0，99］，同理，sid=2的第二个1%的子区间对应的区间值为［100，199］，这样我们就将一个100%的完整区间划分成了若干个子区间，两个比例相同的子区间就可以用作于实验策略对比。

图1.2 流量子区间的划分

3. 可复用流量的多层流量切分架构

这种单层流量切分方式是一种独占式的流量切分方式，一个子区间只能供给一个实验使用，一个请求只能命中一个实验，优点是实验之间解藕，不相互影响，缺点是资源有限，流量分配完毕之后，后续的需求将处于长期的等待与饥饿状态，这种独占式的流量切分方式，显然在实验需求不断增加的情况下是完全不能满足的，为了解决独占的问题，我们可以采用多层流量切分方式。

多层流量切分的思想是将单层结构扩展为多层结构，如下图所示，多层之间必须满足正交性，这里多层之间的正交性是指某一层的任何一个子区间可以随机的、均匀的对应到其他层上面，这样我们就把一个子区间对其他层的影响均匀的分散到整个层上面。

多层流量切分架构可以将实验流量从100%扩展到100%*n，也就说每层中的流量我们都可以用做于实验对比，一次请求可以同时命中多个实验，实验流量是复用的，多层流量是满足不同层的实验之间的影响都是均匀、可预估的，开展多层实验的前提是保证这种实验间的影响是可接受的，有一些实验是不允许任何复用，例如，展现类的实验，如果两个实验各自指定了一套展现样式模板，而从展现模块的角度来讲一次请求只能展现一种样式模板，因此，这里不兼容的实验只能位于同一层中。

图1.3 多层流量切分架构示意图

多层流量切分的另一个优势是每一层我们可以使用不同的切分方式进行，这样也极大的丰富了流量切分的多样性，那么，还有另一个问题，每一个流量层中只能采用一种流量切分方式，如果同一层中有多种切分方式的需求又如何解决呢？答案是通过层的嵌套来实现，层的嵌套是指在一个层中可以包含其他的层，如下图所示，矩形表示层，圆形表示切分出来的实验流量，其中，1号层包含了2、3、4三个层，4号层又包含9、10、11三个层，为了达到同一层内多种流量切分方式的目的，我们需要将该层切分成多个区间，例如，下图中的2号层就被分成了5、6两个层，但是这两个层也必须采用相同的切分方式，因为这两个层相当于把其父层的流量分成了两部分，因而这两部分的产生方式应该是一致的，最后，在5、6层中，我们又可以建立其他的层，这两个层就可以采用不同的流量切分方式了。

图1.4 流量切分多层嵌套示意图

理论上，多层流量切分架构的可切分层数是无限的，可以支持任意多的流量层，但是，从实现的角度来讲，层数做到无限是很难实现的，因为，为了保证层和层之间的正交性，我们必须要为每一层实现一套hash算法，保证每种hash算法的结果是正交的，要实现层数的无限，则需要实现无限多个保证正交的hash算法，hash算法的增多势必会导致正交性的下降，我们可以实现有限个正交的hash算法，hash算法的数目是要求可以满足所有的实验需求的。下面我们介绍一种多层流量切分架构的实现方法。

为了实现多层流量切分，我们的思路是先实现一种hash算法，这种hash算法的输入是cookie、随机值等信息，输出是单次hash的结果，并且保证这种hash算法结果足够的均匀和随机，然后将这种hash进行变换，扩展出多个正交的hash算法。

为了验证单个hash算法的随机性和均匀性，我们进行了实验验证，如下图所示，每一行表示一个100%的全集，每一列表示从全集中抽取出10%，测试的全集是100w，从下面的测试数据来看，每个层中的流量切分结果是比较均匀和随机的。

图1.5 单hash算法均匀性、随机性验证实验数据

有了单层hash算法，我们需要将单层hash扩展成为多层，这里可以采用的方法很多，本文采用的是移位变换的方法将单层hash扩展成为多层hash，多层实验流量切分的真实环境测试数据如下文所示。

4. 实际数据测试

为了验证其算法的可行性，我们进行了实际数据测试，测试结果如下：

表1.2 均匀性验证数据

文章来源：百度搜索研发部官方博客

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有