背景
想要同一时间做N个实验? 想要同一份流量不同实验之间不干扰? 想要每个实验都能得到100%流量? 那么你就需要分层实验。
1.1 什么是分层实验 分层实验概念:每个独立实验为一层,层与层之间流量是正交的。 简单来讲,就是一份流量穿越每层实验时,都会再次随机打散,且随机效果离散。 所有分层实验的奠基石–Goolge论文 《Overlapping Experiment Infrastructure More, Better, Faster Experimentation》 下面将以一个简单例子来解释分层实验核心原理,如果要了解全貌,可以看一下上面论文 首先来看一下MD5的作为hash的特点,本文以最简单得MD5算法来介绍分层实验。(但一定要知道,实际应用场景复杂,需要我们设计更复杂的hash算法) 1.2 MD5 特点 压缩性:任意长度的数据,算出的MD5值长度都是固定的。 容易计算:从原数据计算出MD5值很容易。 抗修改性:对原数据进行任何改动,哪怕只修改1个字节,所得到的MD5值都有很大区别。(重要理论依据!) 弱抗碰撞:已知原数据和其MD5值,想找到一个具有相同MD5值的数据(即伪造数据)是非常困难的。 强抗碰撞:想找到两个不同的数据,使它们具有相同的MD5值,是非常困难的。 正是由于上面的特性,MD5也经常作为文件是否被篡改的校验方式。 所以, 理论上,如果我们采用MD5计算hash值,对每个cookie 加上某固定字符串(离散因子),求余的结果,就会与不加产生很大区别。加上离散因子后,当数据样本够大的时候,基于概率来看,所有cookie的分桶就会被再次随机化。 下面我们将通过实际程序来验证。 实战讲解
2.1 我们的程序介绍 使用java SecureRandom模拟cookie的获取(随机化cookie,模拟真实场景) hash算法选用上文介绍的MD5。实验分两种:对cookie不做任何处理;对cookie采用增加离散因子离散化 一共三层实验(也就是3个实验),我们会观察第一层2号桶流量在第2层的分配,以及第2层2号桶流量在第3层的分配 如果cookie加入离散因子后,一份流量经过三个实验,按照如下图比例每层平均打散,则证明实验流量正交
从上图可以看出,即使第1层的2号桶的实验结果比其他几个桶效果好很多,由于流量被离散化,这些效果被均匀分配到第2层。(第3层及后面层类同),这样虽然实验效果被带到了下一层,但是每个桶都得到了相同的影响,对于层内的桶与桶的对比来说,是没有影响的。而我们分析实验数据,恰恰只会针对同一实验内部的基准桶和实验桶。 =>与原来实验方式区别? 传统方式,我们采用将100%流量分成不同的桶,假设有A,B两个人做实验,为了让他们互不影响,只能约定0-3号桶给A做实验,4-10号桶给B做实验的方式,这样做实验,每个人拿到的只是总流量的一部分。 上面基于MD5分层的例子告诉我们,分层实验可以实现实验与实验之间“互不影响”,这样我们就可以把100%流量给A做实验,同时这100%流量也给B做实验。(这里的A,B举例来说,一个请求,页面做了改版(实验A)、处理逻辑中调用了算法,而算法也做了调整(实验B)),如果采用不采用分层方式,强行将100%流量穿过A,B,那么最终看实验报表时,我们无法区分,是由于改版导致转化率提高,还是算法调整的好,导致转化率提高。 2.2 代码 import java.security.MessageDigest;import java.security.NoSuchAlgorithmException;import java.security.SecureRandom;import java.util.ArrayList;import java.util.List;/** * @author 九德 */public class MultiLayerExperiment { private static String byteArrayToHex(byte[] byteArray) { char[] hexDigits = {‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’, ‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’}; char[] resultCharArray = new char[byteArray.length * 2]; int index = 0; for (byte b : byteArray) { resultCharArray[index++] = hexDigits[b >>> 4 & 0xf]; resultCharArray[index++] = hexDigits[b & 0xf]; } return new String(resultCharArray); } private static long splitBucket(MessageDigest md5,long val,String shuffle){ String key = String.valueOf(val) +((shuffle==null)?”“:shuffle); byte[] ret = md5.digest(key.getBytes()); String s = byteArrayToHex(ret) ; long hash =Long.parseUnsignedLong(s.substring(s.length()-16,s.length()-1),16); if(hash < 0){ hash = hash * (-1); } return hash ; } private static void exp(SecureRandom sr,MessageDigest md5, final int LevelOneBucketNumm,/第一层实验桶数/ final int LevelTwoBucketNumm,/第二层实验桶数/ final int LevelThreeBucketNumm,/第三层实验桶数/ final int AllFlows,/所有流量数/ String shuffleLevel1,/第一层实验离散因子/ String shuffleLevel2,/第二层实验离散因子/ String shuffleLevel3/第三层实验离散因子/ ){ System.out.println("==第1层实验 start!==");
int[] bucketlevel1 = new int[LevelOneBucketNumm];
for (int i=0; i<LevelOneBucketNumm; i++) {
bucketlevel1[i] = 0;
}
List<Integer> level1bucket2 = new ArrayList<Integer>();
for(int i=0; i<AllFlows; i++)
{
int cookie = sr.nextInt();
long hashValue = splitBucket(md5, cookie, shuffleLevel1);
int bucket =(int) (hashValue % LevelOneBucketNumm);
if(bucket == 2){
/*将2号桶的流量记录下来*/
level1bucket2.add(cookie);
}
bucketlevel1[bucket]++;
}
for(int i=0; i<LevelOneBucketNumm; i++){
System.out.println("1层" + i + "桶:" + bucketlevel1[i]);
}
System.out.println("==第1层实验 end!==");
System.out.println("==第1层2号桶流量到达第2层实验 start!==");
int[] bucketlevel2 = new int[LevelTwoBucketNumm];
for (int i=0; i<LevelTwoBucketNumm; ++i) {
bucketlevel2[i] = 0;
}
List<Integer> level2bucket2 = new ArrayList<Integer>();
for(int cookie : level1bucket2) {
long hashValue = splitBucket(md5, cookie, shuffleLevel2);
int bucket =(int) (hashValue % LevelTwoBucketNumm);
if(bucket == 2){
/*将第2层2号桶的流量记录下来*/
level2bucket2.add(cookie);
}
bucketlevel2[bucket]++;
}
for(int i=0; i<LevelTwoBucketNumm; i++){
System.out.println("2层" + i + "桶:" + bucketlevel2[i]);
}
System.out.println("==第1层2号桶流量到达第2层实验 end!==");
System.out.println("==第2层2号桶流量到达第3层实验 start!==");
int[] bucketlevel3 = new int[LevelThreeBucketNumm];
for (int i=0; i<LevelThreeBucketNumm; ++i) {
bucketlevel3[i] = 0;
}
for(int cookie : level2bucket2) {
long hashValue = splitBucket(md5, cookie, shuffleLevel3);
int bucket =(int) (hashValue % LevelThreeBucketNumm);
bucketlevel3[bucket]++;
}
for(int i=0; i<LevelThreeBucketNumm; i++){
System.out.println("3层" + i + "桶:" + bucketlevel3[i]);
}
System.out.println("==第2层2号桶流量到达第3层实验 end!==");
}
public static void main(String[] args) throws NoSuchAlgorithmException {
SecureRandom sr = SecureRandom.getInstance("SHA1PRNG");/*用来生成随机数*/
MessageDigest md5 = MessageDigest.getInstance("MD5");/*用来生成MD5值*/
/*1. 不对cookie做处理,一个cookie在每层实验分到的桶是一致的*/
exp(sr,md5,5,5,5,1000000,null,null,null);
System.out.println("=======================");
/*2. 每层加一个离散因子,这里只是简单的a,b,c,就可以将多层了流量打散*/
exp(sr,md5,5,5,5,1000000,"a","b","c");
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68
} 2.3 结果分析(重点) 2.3.1 不对cookie处理,每层实验的分桶号一样 因为hash%5中的hash保持不变,无论哪层,所以流量一直处于2号桶。 ==第1层实验 start!== 1层0桶:199698 1层1桶:199874 1层2桶:199989 1层3桶:200711 1层4桶:199728 ==第1层实验 end!== ==第1层2号桶流量到达第2层实验 start!== 2层0桶:0 2层1桶:0 2层2桶:199989 2层3桶:0 2层4桶:0 ===第1层2号桶流量到达第2层实验 end!== ===第2层2号桶流量到达第3层实验 start!== 3层0桶:0 3层1桶:0 3层2桶:199989 3层3桶:0 3层4桶:0 ===第2层2号桶流量到达第3层实验 end!== 2.3.2. 对cookie做离散处理后,每层流量均匀分配 如下所示, 流量到达第一层时,流量被均匀分配 第2层实验的2号桶流量到达第3层时,流量均匀分配到第2层的5个桶。 第2层实验的2号桶流量到达第3层时,流量均匀分配到第3层的5个桶。 ==第1层实验 start!== 1层0桶:199951 1层1桶:199536 1层2桶:200127 1层3桶:200938 1层4桶:199448 ==第1层实验 end!== ==第1层2号桶流量到达第2层实验 start!== 2层0桶:40122 2层1桶:40080 2层2桶:39881 2层3桶:40096 2层4桶:39948 ===第1层2号桶流量到达第2层实验 end!== ===第2层2号桶流量到达第3层实验 start!== 3层0桶:8043 3层1桶:7971 3层2桶:7823 3层3桶:7956 3层4桶:8088 ===第2层2号桶流量到达第3层实验 end!== 2.4 结论 我们观测的第2层和第3层流量均来源于第一层的2号桶。 所以得出结论,第一层的流量在第2层、第3层均得到重新的离散分配。 总结 随着个性化和算法不断引入我们的应用,同一时间做多个实验需求越来越多,更多人开始使用分层实验
|