【得物技术】AB实验设计实现与分流算法

背景

在现实的产品设计场景中以及业务决策中，需要对方案进行决策。例如，App或网页端某个页面的某个按钮的颜色是用蓝色还是红色，是放在左边还是右边？传统的解决方案通常是集体表决或由某位Leader拍板，类似的选择还有很多，从概率上很难保证传统的选择策略每次都是有效的，而ABTest显然是一种更加科学的方法。

 

业务价值

研发视角

• 先验性：采用流量分割与小流量测试的方式，先让线上部分小流量用户使用，来验证我们的想法，再根据数据反馈来推广到全流量，减少产品损失。
• 并行性：我们可以同时运行两个或两个以上版本的试验同时去对比，而且保证每个版本所处的环境一致的，这样以前整个季度才能确定要不要发版的情况，现在可能只需要一周的时间，避免流程复杂和周期长的问题，节省验证时间。
• 科学性：统计试验结果的时候，ABTest 要求用统计的指标来判断这个结果是否可行，避免我们依靠经验主义去做决策。

 

PM视角

• 实验流程化，系统化，降低用户使用数据产品的门槛
• 数据分析可视化，将通用指标系统化分析，降低手工分析频率；对实验结果做到智能解读，直接给出用户数据分析结果，降低用户数据理解门槛

 

核心概念

1. 场景
   对应业务场景，场景之间完全独立，比如首页推荐瀑布流、金刚位等。
2. 桶
   从属于场景，一个场景可以有多个桶，一个桶中可以多个实验，不同的桶之间流量是互斥的。
3. 层
   一类（种）实验的集合，从属于场景，一个场景可以有多个层，处于同一层的各实验之间流量互斥，各实验流量之和为总流量，处于不同层的各实验之间流量正交。
4. 实验
   用来验证某个决定请求处理方式的功能或策略的一部分流量，通常用来验证某个功能或策略对系统指标（如PV/UV，CRT，下单转化率等）的影响。
5. 流量
   指所有用户请求。
6. 流量正交
   不同层之间流量分配方式完全独立，不会互相影响MECE。

 

实验建模

   

    这里我们将用户流量分成了三份，分层桶、小流量桶和基准桶。其中：

• 层和桶的数量支持扩展（理论上支持任意多个）
• 层和桶之间没有关联关系
• 实验处于层和桶的交叉部位
• 每一层的hash因子不同（通过加盐实现）
• 每一层和桶的交叉部位有一个基准实验，当没命中实验（流量没有完全利用）时，走基准实验

    分层桶类似于“测试环境”，由算法方较为自由的验证一些想法，因此管控比较松，在分层桶里我们允许多个实验组交叉的去验证不同的策略通路，以此来挑选更优的算法组合模式，如果某种组合模式经过初步验证，产生了更好的指标，就可以进入小流量桶。

    小流量桶类似于“预发环境”，我们将这个组合模式单独灌入新的一批流量，相当于排除干扰，再次double check下，如果确实产生了更好的指标，我们将其晋升为基准桶。

    基准桶类似于“生产环境”，作为一种稳定的算法策略持续使用。

                         

 

分流算法

     进行分流算法的目的是将线上用户按照固定的流量比例分配到不同实验(桶)中，并且保持这种实验(桶)分配关系，以此来对照验证相关的指标是否有所好转，所以为了保持这种用户和实验(桶)的分配关系，我们使用了hash取模的方式将一个用户固定在了一个0到100的区间中，这样只要对应实验(桶)的区间没有变化，这个用户和实验(桶)的分配关系就不会变化。

     所以我们的做法就是将每个实验(桶)的流量占比分配到一个0到100的区间中，根据用户id和每一层不同的hash因子组合进行hash，然后取模，余数落到哪个区间就取包含该区间的实验(桶)。

     

      如上图所示，A实验流量占比30%，B实验30%，C实验40%，将它们分配到0到100的区间中，即A实验占[0,30)，B实验占[30,60)，C实验占[60,100)，计算一个用户模为50则命中B实验。

      如果不需要进行流量调整，这种模式能够很稳定的运行并且保持这种实验(桶)流量分配关系，但是如果进行流量调整，就会存在一些问题，比如此时我们将A实验减少15%，B实验不变，C实验增加15%，则A实验占[0,15)，B实验占[15,45)，C实验占[45,100)，因为每个层的hash因子不变，相同的用户请求产生相同的模数，最后模为50会落入C实验的区间，如下图：

           

    这样的结果在业务上是不可接受的，因为A和C实验流量的调整对B实验的用户进行了污染，导致本应该属于B实验的一部分用户却走到了实验C中，所以在这里我们进行一些调整，每次流量的调整只会调整它的邻边，即尽可能的减少流量调整对实验区间重新分配带来的影响，我们以上图的场景为例，进行改进后的AB算法的拆解。

         

    如上图，算法第一步是优先在自己的区域内进行选择，A实验流量调整为15%，从自己的区域[0,30)中选取[0,15)，B实验保持[30,60)，C实验因为流量调整为55%，先把自己的区域选满，即[60,100)。

    第二步是填补间隙，C实验因为还有15%没有填补，就把间隙[15,30)补上。

    这样调整后，A和C实验的流量调整不会给B实验带来影响，原先B实验的用户调整后依然还是走B实验。然后还能让流量调整后原来A实验中的一半用户继续留存在A实验中，C实验原来的用户依然还是走C实验，尽可能减少了用户集变动给实验(桶)最终效果带来的影响。

    依此类推，如果继续对上述实验集进行流量调整，A实验调整为25%，B实验调整为35%，C实验调整为40%，进行算法的拆解，如下图：

         

    第一步是优先在自己的区域内进行选择，A实验因为流量调整为25%，先把自己的区域选满，即[0,15)，B实验调整为35%，也是优先把自己的区域选满，即[30,60)，C实验调整为40%，从自己的区域中选择[15,30)和[60,85)。

    第二步填补间隙，A实验因为还有10%没有填补，就把间隙[85,95)补上，B实验因为还有5%没有填补，就把间隙[95,100)补上，最终形成上图的区间分布。

    这样经过多次调整后，每个实验都尽可能的减少了自己区间的变动，进行相应的“多退少补”，保证自己用户的留存性，减少对实验指标的影响。

    从上面的例子可以看出，经过多次的流量调整后，各个实验的区间分布会变得比较复杂，但是从使用者的角度看，他只需要关心每个实验所占的流量配比，不需要关心底层实验流量的区间分布情况(这块对他是黑匣子)，因此不会增加使用者操作的难度。

 

系统设计

      AB平台在系统设计上尽可能的减少了外部依赖和IO调用，将处理都尽量放在了本地内存中，如下图：

                         

    仅依赖了配置中心和数据库，然后上游流量的请求进入AB获取实验决策全部都是本地内存操作。其中重载配置过程如上图所示：

• 后台用户编辑实验信息(①)
• 进行相应的增删改操作修改DB(②)
• 触发发布一个静态配置，如果该配置已存在则配置值加一(③)
• 配置中心将该配置推送给所有AB机器(④)
• 触发所有机器重新加载数据库配置进本地缓存(⑤)

这样上游的请求进入任意一台机器都是在本地内存进行处理，并且每台机器都是加载的最新的配置，大大提高了AB平台的处理能力降低了rt。

系统设计没有银弹，之所以这样设计是因为AB平台具有如下的特点:

1.弱一致性

    依赖配置中心推送随着订阅机器的增加一定会有一些延迟，但是用户修改实验配置后对于即时生效并不是特别敏感，延迟几秒都是可以接受的。

2.缓存内容较少

    本身实验的配置信息就比较少，哪怕未来实验数量达到万量级，单机内存中都完全足够存放。

3.读多写少

    用户修改实验配置的次数远远小于上游调用AB平台获取决策的次数，所以对于配置中心的调用压力足够小，是在可预期范围内。

 

这样设计也存在一些缺陷:

1.数据库毛刺

    随着机器数量的增加，用户每次修改实验配置后，所有机器都需要重新加载数据库配置进入本地缓存，每台机器都要触发场景、桶、层、实验、白名单等等的数据库查询，而且是所有机器瞬间一起的查询，在机器数达到百台千台以上的时候会对数据库造成较大的瞬时查询压力，造成查询超时甚至是更严重的问题，不过可以通过一些方式去缓解:

• 随机时间等待，每台机器在收到配置变更后随机等待一个短暂的时间将所有机器加载数据库的时间点错开一些。
• 数据库缓存，每次修改完数据库后都主动的触发一次缓存加载，不过这里缓存要谨慎使用，如果触发缓存加载失败，此时去触发配置中心推送，机器会加载到脏数据导致实验配置修改没有生效，所以修改数据库和主动触发缓存加载一定要在一个事务中。
• sql优化，每次重新加载所有配置信息本身sql不复杂，加索引带来的提升也不是特别提效，因为配置信息达到MB级别的时候，对于网络开销也是较大的，然后机器数量上去后，网络IO吞吐会很大，所以可以修改为查询最近一段时间内发生变化的配置信息，这样可以大大减少查询的压力。当然如果将推送版本号改为推送修改的id然后单独加载id也是可行的，不过要考虑到多个用户并发修改不同的实验配置导致配置中心合并配置带来的推送丢失问题，之所以推送版本号也是考虑到这个问题。

2.推送效率

    随着订阅机器数的增加，推送rt的增加是必然的，当然这个缺陷是在可接受范围内的。

3.僵尸节点

    如果机器因为网络问题失联导致配置项推送失败会造成实验配置修改没有完全生效的问题，会造成一些诡异的现象，不过概率较低，只能依赖运维平台的各种端口检测来提前发现处理。

文｜尉迟繁缕

关注得物技术，携手走向技术的云端