ABTest分流算法设计与实现

需求

有这么一个需求,我们需要建立一个实验,实验有一个实验名称.实验下面有多个分组,每个分组也有个分组名称.当我们创建一个实验的时候,需要同时建立一个或多个分组,并且每个分组都有一个百分比的属性,代表当我们进入一个实验的时候,选择某个分组的可能性有多大,所有的分组的百分比之和为100%.

目的

通过实现实验和分组,我们可以把它应用在分流策略中,比如ABTest.考虑这样一个场景,我们要对比三个推荐算法带来的效益,此时我们会给这三个推荐算法分配一定的比例,然后让每次推荐都按这个比例来执行不同的算法,最终再根据一定的换算来统计算法带来的效益.

实现思路

我们可以将分组的百分比看成是几条线段,假如总共有100米长,每条线段有一定的长度,我们根据标识(比如hashCode)来对100取模,最终这个数字一定会落在某一条线段上,也就是某个分组上.在我的实现中,将以1000作为模.在这里,我将使用Java语言实现一个简单的分流算法.

完整代码地址为:https://github.com/CodeShowZz/abtest,所有的接口都进行了初步的测试.

步骤一:定义模型

public class Lab {

    private String key;

    private String name;

    private List<Group> groupList;

}

public class Group {

    private String key;

    private String name;
    
    /**
    *  百分比
    **/
    private BigDecimal ratio;

    /**
     * 分组的开始位置
     */
    private int start;

    /**
     * 分组的结束位置
     */
    private int end;

}

步骤二:实现分流工具类

这里要实现一个工具类,能够将百分比转换成区间.

public static void assignRangeByRatio(Lab lab) {
       List<Group> groupList = lab.getGroupList();
       int current = 0;
       for (Group group : groupList) {
           BigDecimal ratio = group.getRatio();
           int count = ratio.multiply(range).setScale(0, RoundingMode.HALF_UP).intValue();
           int start = current;
           int end = current + count - 1;
           group.setStart(start);
           group.setEnd(end);
           current = end + 1;
       }
   }

步骤三:获取标识取Hash,将其分配到某个分组中.

在我的实现中,如果两次传入的标识key是一样的,那么计算出来的分组位置也是一样的.所以使用这个Hash算法时,可能要根据具体的应用场景来取一个具体的key,比如对于一个用户来说,取值如果要和上次相同,那么可以使用用户id来作为key,如果取值要随机,那么可以取时间戳或者其它属性作为key.

这里我的Hash算法借鉴(可以说是照抄)了HashMap中的Hash算法.

public static final int hashCode(String key, String value) {
       return Math.abs(Objects.hashCode(key) ^ Objects.hashCode(value));
   }

接着,使用上面的模型并且结合Hash算法来实现分组.分区函数的返回结果就是某一个分组.

public static Group partition(String key, Lab lab) {
    int hashCode = hashCode(key, lab.getName());
    int position = hashCode % range.intValue();
    List<Group> groupList = lab.getGroupList();
    for (Group group : groupList) {
        if (group.getStart() <= position && group.getEnd() >= position) {
            return group;
        }
    }
    return null;
}

步骤四:测试

通过上面的三个步骤,一个简单的分流算法实现完成.现在我们来假设这样一个场景:据统计,50%的人喜欢数学,30%的人喜欢语文,20%的人喜欢英语,那么现在我们随便找一个人,来猜测它喜欢哪个科目,那么我们就可以使用上面的程序,测试程序如下.

public static void main(String[] args) {
        Lab subject = new Lab();
        Group math = new Group();
        math.setRatio(new BigDecimal(0.5));
        math.setKey("math");
        math.setName("数学");

        Group chinese = new Group();
        chinese.setRatio(new BigDecimal(0.3));
        chinese.setKey("chinese");
        chinese.setName("语文");

        Group english = new Group();
        english.setRatio(new BigDecimal(0.2));
        english.setKey("english");
        english.setName("英语");

        List<Group> groupList = Arrays.asList(math, chinese, english);
        subject.setGroupList(groupList);
        subject.setKey("subject");
        subject.setName("学科");

        SplitFlowUtil.splitFlow(subject);

        Group res = partition("the boy maybe like math", subject);
        System.out.println(res);

        res = partition("i am a programmer", subject);
        System.out.println(res);
    }

继续思考

很明显,上面的这个程序其实算是一个通用程序,如果设计的算法更加的快捷,API接口更加易用,它完全可以作为一个公司内部的服务来提供给别人调用.所以现在我们要思考如何将它改进成一个公司内部可以使用的程序.

改进一:建立微服务

提供添加、更新、删除、查询、分流五个接口来对实验进行操作,在这里使用Restful接口来提供这项服务.

改进二:将模型数据存储到Mysql

上面的测试程序只是在本地构造程序,我们可以将模型数据映射成表,然后存储到数据库中,然后通过UI界面来进行CRUD,这一点很容易就可以做到,不再赘述.

改进三:引入Zookeeper

很明显,既然要在公司内部使用,那么要保证每个实验都是隶属于某个项目的,首先要保证实验的唯一性,而这又能看出有很明显的层级结构,所以可以引入Zookeeper来存储这些模型数据,而上面的Mysql则用于冗余模型数据.

开始第一次改进

先列一下实现上述改进所要引入的一些技术,其中改进二不在本次实现考虑范围.另外在下文中可能不会提供所有的代码,完整的代码将在最后给出Github仓库地址.

• 序列化框架:Kryo,用于序列化模型数据并将其存储到Zookeeper上
• 微服务框架:Spring Boot,用于实现一个微服务并提供Restful接口
• 分布式协调框架:Zookeeper及其API,用于实现模型数据的保存,并形成目录结构.

Zookeeper

在工程中实现对zookeeper api的调用,主要考虑的操作有4种

• 节点增加
• 节点更新
• 节点删除
• 节点数据查询

出于更新的复杂性,调用方可能修改实验名称、分组名称以及分组的属性,所以在真正实现中,将使用节点删除加上节点增加来实现节点更新.在这里将不会讨论Zookeeper API的细节,假设读者已经对此有一定的了解和经验.

Spring Boot

构建一个Spring Boot服务是非常简单的,和上述的Zookeeper类似,我们将对外提供几个api供外部接口调用.

• 实验创建
• 实验更新
• 实验删除
• 实验查询
• 根据实验名称进行分流

API如下所示

/**
   * 创建实验
   * @param lab
   * @return
   */
  @RequestMapping(value = "/create", method = RequestMethod.POST)
  public boolean create(@RequestBody Lab lab) {
      return labService.create(lab);
  }

  /**
   * 根据projectKey和labKey删除实验
   * @param lab
   * @return
   */
  @RequestMapping(value = "/delete", method = RequestMethod.POST)
  public boolean delete(@RequestBody Lab lab) {
      return labService.delete(lab);
  }

  /**
   * 根据projectKey和labKey查询实验下的分组
   * @param projectKey
   * @param labKey
   * @return
   */
  @RequestMapping(value = "/query", method = RequestMethod.GET)
  public List<Group> query(@RequestParam String projectKey, @RequestParam String labKey) {
      return labService.query(projectKey,labKey);
  }

  /**
   * 根据projectKey和labKey还有identify来进行分流 得到某个分组
   * @param projectKey
   * @param labKey
   * @param identify
   * @return
   */
  @RequestMapping(value = "/partition", method = RequestMethod.GET)
  public Group partition(@RequestParam String projectKey, @RequestParam String labKey,@RequestParam String identify) {
      return labService.partition(projectKey,labKey,identify);
  }

  /**
   * 更新实验
   * @param lab
   * @return
   */
  @RequestMapping(value = "update",method = RequestMethod.POST)
  public boolean update(@RequestBody Lab lab) {
      return labService.update(lab);
  }

我在模型数据中又引入了几个参数:

/**
   * 分流需要的参数,由调用方传入,调用方决定分流所使用的标识
   */
  private String identify;

  /**
   * 某个项目的标识,在ZK中是第一级目录,以来区分各个项目的实验
   */
  private String projectKey;

  /**
   * 在进行更新时,需要传入变更前的实验分组key,以便于删除原来的实验
   */
  private String oldKey;

这几个参数的作用已经通过注释来表达,这样可以使得服务更加通用和简单.

测试

实现完上述的两个改进之后,我们就可以打开PostMan或者其它Http请求工具来对我们提供的接口进行测试了,这里对如何测试不进行展开.

总结

在这篇文章中,介绍了一个简单的分流算法的设计以及实现,当然程序还存在很多不足之处,比如异常处理,参数校验,又或者是无法实现多层的分流,这都是值得改进的地方,希望以后有机会再进行改进(程序员经常说的一句话就是下次一定😄).