一,需求

在A/B测试系统中,常常将进入系统中的流量按百分比分组。对不同的分组做不同的业务逻辑,一段时间后观测两组达成的业务效果。比如实验组为20%的流量,对比组为80%的流量,由于最终进入系统总的流量数和具体进入系统有哪些流量都是为止了。需要一个分流算法来保证.

  • 进入流量的分配,在宏观上按实验的百分比配置分配,比如20%的流量进入实验组,80%的流量进入对比组
  • 同一份流量多次进入系统时,保证分组的一致性。即不要出现一会分到实验组,一会分到对比组

二,算法实现

算法思想

  1. 通过hash算法,将流量平均分配到100个桶
  2. 按百分比顺序取分分配这一个百个桶

具体实现


算法总共分为三个流程

  1. 使用MurmurHash将流量id,计算出一个hash值
  2. 按hash值,将流量Id分配到一百个桶中
  3. 按实验分组配置的百分比,来分配桶。从而达到分配百分比分流的效果。

为什么使用MurmurHash,而不直接将流量id取模分桶?

因为流量id可能随机性不够,可能导致分桶不够均匀,MurmurHash算法随机性更好。且MurmurHash支持对非数字类型的Key Hash。这使得基于此的分流算法,可以做成普适的通用模块

为什么要为Hash算法加盐?

对同一批人可能做不同的实验,我们不希望,不同的人在不同的实验也被分配到相同的桶里。加盐可以确保不同实验对相同流量的分桶随机性