什麼是ABTest系統和分流？

在營運和設計的時候，為了驗證一個政策，對不同使用者的吸引程度，驗證哪個政策更具效益，我們會将通路流量劃分為不同的政策組，然後進行統計分析這些通路流量的留存情況等，這個過程稱之為AB實驗，也成為ABTest系統。而ABTest系統最核心的就是分流政策的實作，包含單個實驗的分流，多個實驗不同層的交叉或互斥分流等。如下圖：

分流技術實作方案

先準備三個類，一個是政策類，一個是政策類的VO，最後一個是一緻性hash工具類。如下：

less複制代碼@Data
@AllArgsConstructor
@NoArgsConstructor
public class Strategy {

   /**
    * 分組編碼
    */
   private String code;

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

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

}

less複制代碼@Data
@Builder
@AllArgsConstructor
@NoArgsConstructor
public class StrategyVO {

   /**
    * 流量區間值 0 ~ Integer.MAX_VALUE
    */
   private Integer flowVal;

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

}

java複制代碼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 + 升序數組）

ini複制代碼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 + 排序樹）

arduino複制代碼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個虛拟節點和政策流量比例劃分對應的虛拟節點個數。是以，相比之下，方案二是更加具備可擴充性的。

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

分流技術的思考

有個問題是需要思考的：政策流量比例的切分問題？這裡的切分分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%，與原比例完全不比對，在這種情況下，要想保證已流入的流量保持或小部分保持原有的政策命中值，會相對困難和複雜。而方案二同樣不存在需要修改代碼的問題。

另一個問題就是多試驗情況下，分層的交叉和互斥的實作。

可以考慮根據使用seed來使MurmurHash的值産生變化，也可以建構不同的排序樹來實作。

擴充

分布式緩存的一緻性hash問題當緩存資料分布在不同的緩存叢集中時，我們需要考慮當增減叢集時，要面臨的資料失效問題。當情況發生時，由于叢集增減，取模情況下，資料會大面積失效，最終壓力會給到資料庫，導緻資料庫壓力激增。這種情況下，就需要考慮引入一緻性hash算法來解決這個問題，同時需要通過增加虛拟節點來避免資料傾斜的問題。而這就是上面方案二的實作思路。

ABTest系統分流技術實踐、優化和思考

什麼是ABTest系統和分流？

分流技術實作方案

（1）方案一（一緻性hash + 升序數組）

（2）方案二（一緻性hash + 排序樹）

方案對比分析

分流技術的思考

擴充

繼續閱讀

突破 MySQL 三大技術瓶頸，分布式資料庫的技術實踐

iOS 螢幕旋轉的實踐解析一、快速實作旋轉二、旋轉後的 UI 布局更新三、相關問題四、相關枚舉值五、結語

AB實驗流量正交的了解

OneCode 領域驅動設計（DDD）技術實踐（二）視圖工廠簡介

存儲成本降低80%！US3在海量資料歸檔存儲下的成本優化技術實踐

廣告業務系統之輔助決策 —— “ AB 實驗平台”

GitLab CI 接入代碼安全掃描技術實踐

學生資訊技術實踐活動(程式設計比賽)

峰值使用率提升20%，攜程離線上資源混部技術實踐

fuchsia學習_下載下傳編譯遇到問題和demo運作

【ABTest】一款簡單易用的ABTest開源庫ABTest

WinForm實作簡單HTTP請求伺服器（待編輯）

AB Test 壓力測試工具使用整理

商湯自研深度學習部署工具包 PPL及其技術實踐

ab-test機率論ab-test顯著性檢驗

springcloud gateway網關內建abtest（灰階釋出、多版本釋出）