ABTest系统分流技术实践、优化和思考

什么是ABTest系统和分流？

在运营和设计的时候，为了验证一个策略，对不同用户的吸引程度，验证哪个策略更具效益，我们会将访问流量划分为不同的策略组，然后进行统计分析这些访问流量的留存情况等，这个过程称之为AB实验，也成为ABTest系统。而ABTest系统最核心的就是分流策略的实现，包含单个实验的分流，多个实验不同层的交叉或互斥分流等。如下图：

分流技术实现方案

先准备三个类，一个是策略类，一个是策略类的VO，最后一个是一致性hash工具类。如下：

@Data
@AllArgsConstructor
@NoArgsConstructor
public class Strategy {

   /**
    * 分组编码
    */
   private String code;

   /**
    * 百分比（30% => 0.30 、 25.5% => 0.255）
    */
   private BigDecimal percent;

   /**
    * 策略值
    */
   private String val;

}

@Data
@Builder
@AllArgsConstructor
@NoArgsConstructor
public class StrategyVO {

   /**
    * 流量区间值 0 ~ Integer.MAX_VALUE
    */
   private Integer flowVal;

   /**
    * 策略值
    */
   private String val;

}

public class MurmurHashUtils {

   private MurmurHashUtils() {}

   /**
    * Generates 32 bit hash from byte array of the given length and
    * seed.
    *
    * @param data byte array to hash
    * @param length length of the array to hash
    * @param seed initial seed value
    * @return 32 bit hash of the given array
    */
   public static int hash32(final byte[] data, int length, int seed) {
      // 'm' and 'r' are mixing constants generated offline.
      // They're not really 'magic', they just happen to work well.
      final int m = 0x5bd1e995;
      final int r = 24;

      // Initialize the hash to a random value
      int h = seed^length;
      int length4 = length/4;

      for (int i=0; i<length4; i++) {
         final int i4 = i*4;
         int k = (data[i4+0]&0xff) +((data[i4+1]&0xff)<<8)
               +((data[i4+2]&0xff)<<16) +((data[i4+3]&0xff)<<24);
         k *= m;
         k ^= k >>> r;
         k *= m;
         h *= m;
         h ^= k;
      }

      // Handle the last few bytes of the input array
      switch (length%4) {
         case 3: h ^= (data[(length&~3) +2]&0xff) << 16;
         case 2: h ^= (data[(length&~3) +1]&0xff) << 8;
         case 1: h ^= (data[length&~3]&0xff);
            h *= m;
      }

      h ^= h >>> 13;
      h *= m;
      h ^= h >>> 15;

      return h;
   }

   /**
    * Generates 32 bit hash from byte array with default seed value.
    *
    * @param data byte array to hash
    * @param length length of the array to hash
    * @return 32 bit hash of the given array
    */
   public static int hash32(final byte[] data, int length) {
      return hash32(data, length, 0x9747b28c);
   }

   /**
    * Generates 32 bit hash from a string.
    *
    * @param text string to hash
    * @return 32 bit hash of the given string
    */
   public static int hash32(final String text) {
      final byte[] bytes = text.getBytes();
      return hash32(bytes, bytes.length);
   }

}

这里使用MurmurHash算法，对于规律性较强的key，其随机分布特征表现良好。同时，在本文中，仅使用Murmur32做演示，在流量超过十万级时，建议使用Murmur64或Murmur128，但是Murmur128的分流效率比不上Murmur64，可根据实际情况使用。 市面上有guava工具包、hutool工具包等实现，也可以从github上找到合适的工具类放入自己的工程中进行使用。

（1）方案一（一致性hash + 升序数组）

public class FlowV1Test {

   public static void main(String[] args) {

      // 模拟从数据库查询出一个实验下的分组列表（当前仅考虑一个实验的情况，不考虑交叉或互斥）
      List<Strategy> list = new ArrayList<>();
      list.add(new Strategy("code01", BigDecimal.valueOf(0.35), "A"));
      list.add(new Strategy("code02", BigDecimal.valueOf(0.25), "B"));
      list.add(new Strategy("code03", BigDecimal.valueOf(0.40), "C"));

      // 方案一（hash + 升序数组）：
      List<StrategyVO> rangeList = FlowV1Test.v1(list);
      // 结果测试
      Map<String, Integer> v1Map = new HashMap<>(8);
      StopWatch st = new StopWatch();
      st.start("v1");
      for (int i = 0; i < 100000; i++) {
         // 产生随机一个字符串
         String data = UUID.randomUUID().toString() + i;
         for (StrategyVO strategyVO : rangeList) {
            // 取hash的绝对值
            int keyHash2 = Math.abs(MurmurHashUtils.hash32(data));
            if (keyHash2 <= strategyVO.getFlowVal()) {
               String val = strategyVO.getVal();
               // 命中的策略值放入map中，方便观察
               v1Map.put(val, v1Map.get(val) == null ? 0 : v1Map.get(val) + 1);
               break;
            }
         }
      }
      st.stop();

      // 打印结果
      for (Map.Entry<String, Integer> entry : v1Map.entrySet()) {
         System.out.println(entry.getKey() + " - " + entry.getValue());
      }
   }

   private static List<StrategyVO> v1(List<Strategy> list) {
      // 策略list按流量比例升序排序
      List<Strategy> sortedList = list.stream().sorted(Comparator.comparing(Strategy::getPercent)).collect(Collectors.toList());
      List<StrategyVO> rangeList = new ArrayList<>();
      BigDecimal sum = BigDecimal.ZERO;
      // 组装一个数组列表 => [123456, 1234567, 12345678, Integer.MAX_VALUE]
      for (Strategy strategy : sortedList) {
         sum = sum.add(strategy.getPercent());
         BigDecimal multiply = BigDecimal.valueOf(Integer.MAX_VALUE).multiply(sum);
         StrategyVO strategyVO = StrategyVO.builder().flowVal(multiply.intValue()).val(strategy.getVal()).build();
         rangeList.add(strategyVO);
      }
      /* rangeList即为顺序列表（将Integer.MAX_VALUE按比例划分为几个区间）*/
      return rangeList;
   }

}

在这个示例中，首先模拟了一个策略分组的list，通常情况下，这个策略列表是从数据库中查询出来的，然后对这个list按照流量比例进行升序排序，这么做是为了更方便地将Integer.MAX_VALUE分隔为一个递增的数组，为了方便处理，我们构建为一个list。如下：

然后我们模拟了10万个数据进行分流，在程序中，使用UUID生成了随机字符串，对其进行MurmurHash32，同时取绝对值，因为负数不方便处理区间（实际方案应该把负数设计进去，减少碰撞，当然不考虑负数影响不是很大），然后在上面构建的递增数组中进行遍历对比，大于比例值就继续对比下一个值，小于比例值时就放入map并加一，然后break，最后打印最终的结果（耗时的打印结果在后文会和下面一个方案一起对比）如下：

（2）方案二（一致性hash + 排序树）

public class FlowV2Test {

   public static void main(String[] args) {
      // 模拟从数据库查询出一个实验下的分组列表（当前仅考虑一个实验的情况，不考虑交叉或互斥）
      List<Strategy> list = new ArrayList<>();
      list.add(new Strategy("code01", BigDecimal.valueOf(0.35), "A"));
      list.add(new Strategy("code02", BigDecimal.valueOf(0.25), "B"));
      list.add(new Strategy("code03", BigDecimal.valueOf(0.40), "C"));

      // 方案二（一致性hash + 排序树）：
      SortedMap<Integer, String> sortedMap = FlowV2Test.v2(list);
      // 结果测试
      Map<String, Integer> v2Map = new HashMap<>(8);

      for (int i = 0; i < 100000; i++) {
         // 产生随机一个字符串
         String data = UUID.randomUUID().toString() + i;
         int keyHash = Math.abs(MurmurHashUtils.hash32(data));
         // 顺时针找一个虚拟节点
         SortedMap<Integer, String> tailMap = sortedMap.tailMap(keyHash);
         keyHash = tailMap.isEmpty() ? sortedMap.firstKey() : tailMap.firstKey();
         // 命中的策略值放入map中，方便观察
         String val = sortedMap.get(keyHash);
         v2Map.put(val, v2Map.get(val) == null ? 0 : v2Map.get(val) + 1);
      }

      // 打印结果
      for (Map.Entry<String, Integer> entry : v2Map.entrySet()) {
         System.out.println(entry.getKey() + " - " + entry.getValue());
      }
   }

   private static SortedMap<Integer, String> v2(List<Strategy> list) {
      // 方案二（排序树）：
      SortedMap<Integer, String> sortedMap = new TreeMap<>();
      for (Strategy strategy : list) {
         // 35/25/40
         int size = BigDecimal.valueOf(100).multiply(strategy.getPercent()).intValue();
         for (int i = 0; i < size; i++) {
            // {code01_0的hash值, strategy对象地址} {code02_210的hash值, strategy对象地址} ……
            sortedMap.put(Math.abs(MurmurHashUtils.hash32(strategy.getCode() + "_" + i)), strategy.getVal());
         }
      }
      /* sortedMap即为排序树（将Integer.MAX_VALUE按虚拟节点数分为多个节点，天然排序）*/
      return sortedMap;
   }

}

在方案二的代码中，我们模拟的策略分组的list保持不变，然后同样适用一致性hash，即MurmurHash32。但是在这个里面，我们不需要再对策略列表按比例升序排序，只需要对其构建足够的虚拟节点来减少hash倾斜。同时构建一个TreeMap，其本质是一个红黑树，也是一颗二叉排序树，其自平衡的成本较低，这也是JDK8的HashMap使用红黑树的原因之一。然后虚拟节点的个数按比例计算，这里模拟100个虚拟节点，为了平衡排序树的查找成本和分布的均衡度，可以适当修改虚拟节点的个数，结构类似下图：

构建完这个TreeMap，将策略code+虚拟节点i拼接和MurmurHash后作为key放入TreeMap中，value为策略值。在构建这颗树的时候，已经完成了排序。然后开始进行测试。和方案一一样，用UUID生成10万个key进行MurmurHash。在这个方案中，我们直接通过tailMap方法找到大于等于keyhash值的最小的节点，取出对应的value策略值，放入map中进行累加计数，最后打印结果，如下：

其数值比例和策略列表的数值比例大致相同。

方案对比分析

我们从耗时、占用空间、可扩展性3个角度来观察这俩个方案

（1）耗时

从图中可以看到方案一和方案二的耗时没有孰优孰劣。尽管排序树的查询时间复杂度是O(log N)，而数组查询时间复杂度是O(N)。但是在上面的俩个方案中，有俩个地方需要注意，首先是策略的个数不多，所以数组查询即使时间复杂度是O(N)，但是很快；而另一个点是由于排序树方案中，构建了100个虚拟节点，但是其平均时间复杂度是O(log N)，当然这会收到虚拟节点个数的影响。但是分流占比误差在可接受范围情况下，无需增加过多的虚拟节点，这是一个trade off的过程。

（2）占用的存储空间

在方案一中，我们仅需要维护一个策略比例值的数组，个数由策略数组的个数决定，而方案二，我们需要维护100个虚拟节点所构建的排序树，这个会相对更加占用空间。但是，这个是占用空间是几乎可以忽略的，因为在全局中也仅需要维护一份。

（3）可扩展性

这里的可扩展性需要考虑的问题是当策略比例调整时，哪个方案更灵活？假如策略比例调整，那么对于方案一，我们需要对维护的数组进行控制以确保原有的流量命中的策略不会改变或者小部分改变，而这需要较多的编码；针对方案二，策略比例调整导致的排序树的变更几乎不需要变动，始终都会按照总的100个虚拟节点和策略流量比例划分对应的虚拟节点个数，会有小部分的影响，但总体可控。所以，相比之下，方案二是更加具备可扩展性的。

另外，方案二在增加节点或者删减节点的时候，都只会影响增加的虚拟节点数和删减的虚拟节点数。例如当25%-35%-40%中的40%变更为12%-28%。这时假如原总虚拟节点数为100，变更后，在原先流量均匀分布的情况下，只会影响原来落在0~28个虚拟节点数的流量。这便是一致性hash算法+虚拟节点的好处之一：原失效的流量范围可接受，不至于像取模那样全量失效。

综上，方案二是可接受的。

分流技术的思考

有些问题是需要思考的：

（1）策略流量比例切分后的统计数据问题？ 例如当按照某个比例运行一段时间后，数据的统计结果是A方案比较好，然后在实验还没结束前，变更比例，导致比例变了，那这时候如果想要统计数据的准确性，应该是需要将数据按变更比例的前后进行分割，之后再进行统计和分析。如果比例变更前实验运行时间短，数据量不高，在比例变更后，流量变得比较大，例如比例变更前的流量：流量变更后的流量 = (<5%)：(>95%)，那么统计分析时可以加上前面的数据，因为这部分数据对最终结果的影响较小。

（2）然后我们再来看策略流量比例的切分问题？ 这里的切分分3种情况：

• 策略比例小范围切分
• 策略比例部分合并
• 策略比例混合更新

策略比例小范围切分指的是原先25%-35%-40%变成了25%-35%-12%-28%，在这种情况下，为了不影响原有流量的策略命中值，需要修改代码对Integer.MAX_VALUE的60%~100%的这部分区间重新映射到12%和28%，而这个会因为排序问题变得复杂，但方案二相对会更加适配。

策略比例部分合并指的是原先25%-35%-40%变成了60%-40%，在这种情况下，方案一同样需要修改区间重新映射，而方案二不需要变化。

策略比例混合更新指的是原先25%-35%-40%变成了20%-30%-50%，与原比例完全不匹配，在这种情况下，要想保证已流入的流量保持或小部分保持原有的策略命中值，会相对困难和复杂。而方案二同样不存在需要修改代码的问题。

（3）多试验情况下，分层的交叉和互斥如何实现？

可以考虑根据使用seed来使MurmurHash的值产生变化，也可以构建不同的排序树来实现。

扩展

分布式缓存的一致性hash问题 当缓存数据分布在不同的缓存集群中时，我们需要考虑当增减集群时，要面临的数据失效问题。当情况发生时，由于集群增减，取模情况下，数据会大面积失效，最终压力会给到数据库，导致数据库压力激增。这种情况下，就需要考虑引入一致性hash算法来解决这个问题，同时需要通过增加虚拟节点来避免数据倾斜的问题。而这就是上面方案二的实现思路。