本文共 5798 字,大约阅读时间需要 19 分钟。
发表于: 阿里技术矩阵
每个独立实验为一层,层与层之间流量是正交的。简单来讲,就是一份流量穿越每层实验时,都会再次随机打散,且随机效果离散。所有分层实验的奠基石–Goolge论文《Overlapping Experiment Infrastructure More, Better, Faster Experimentation》
下面将以一个简单例子来解释分层实验核心原理,如果要了解全貌,可以看一下上面论文
首先来看一下MD5的作为hash的特点,本文以最简单得MD5算法来介绍分层实验。(但一定要知道,实际应用场景复杂,需要我们设计更复杂的hash算法)
容易计算:从原数据计算出MD5值很容易。
抗修改性:对原数据进行任何改动,哪怕只修改1个字节,所得到的MD5值都有很大区别。(重要理论依据!)
弱抗碰撞:已知原数据和其MD5值,想找到一个具有相同MD5值的数据(即伪造数据)是非常困难的。
强抗碰撞:想找到两个不同的数据,使它们具有相同的MD5值,是非常困难的。
正是由于上面的特性,MD5也经常作为文件是否被篡改的校验方式。所以,理论上,如果我们采用MD5计算hash值,对每个cookie 加上某固定字符串(离散因子),求余的结果,就会与不加产生很大区别。加上离散因子后,当数据样本够大的时候,基于概率来看,所有cookie的分桶就会被再次随机化。下面我们将通过实际程序来验证。
使用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,那么最终看实验报表时,我们无法区分,是由于改版导致转化率提高,还是算法调整的好,导致转化率提高。
package tau.young.ab;import java.security.MessageDigest;import java.security.NoSuchAlgorithmException;import java.security.SecureRandom;import java.util.ArrayList;import java.util.List;import com.google.common.hash.HashCode;import com.google.common.hash.HashFunction;import com.google.common.hash.Hashing;/** * * 多层实验架构 * */public class MultiLayerExperiment { 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, "1", "2", "3"); } /** * 实验分流 */ private static void exp(SecureRandom sr, MessageDigest md5, final int firtstLevelBucketNumm, // 第一层实验桶数 final int secondLevelBucketNumm, // 第二层实验桶数 final int thirdLevelBucketNumm, // 第三层实验桶数 final int AllFlows, // 所有流量数 String shuffleLevel1, // 第一层实验离散因子 String shuffleLevel2, // 第二层实验离散因子 String shuffleLevel3) // 第三层实验离散因子 { System.out.println("==第1层实验 start!=="); int[] bucketlevel1 = new int[firtstLevelBucketNumm]; for (int i = 0; i < firtstLevelBucketNumm; i++) { bucketlevel1[i] = 0; } Listlevel1bucket2 = new ArrayList (); for (int i = 0; i < AllFlows; i++) { int cookie = sr.nextInt(); long hashValue = splitBucket(md5, cookie, shuffleLevel1); int bucket = (int) (hashValue % firtstLevelBucketNumm); if (bucket == 2) { // *将2号桶的流量记录下来*// level1bucket2.add(cookie); } bucketlevel1[bucket]++; } for (int i = 0; i < firtstLevelBucketNumm; i++) { System.out.println("1层" + i + "桶:" + bucketlevel1[i]+" 个流量"); } System.out.println("==第1层实验 end!=="); System.out.println("==第1层2号桶流量到达第2层实验 start!=="); int[] bucketlevel2 = new int[secondLevelBucketNumm]; for (int i = 0; i < secondLevelBucketNumm; ++i) { bucketlevel2[i] = 0; } List level2bucket2 = new ArrayList (); for (int cookie : level1bucket2) { long hashValue = splitBucket(md5, cookie, shuffleLevel2); int bucket = (int) (hashValue % secondLevelBucketNumm); if (bucket == 2) { // *将第2层2号桶的流量记录下来*// level2bucket2.add(cookie); } bucketlevel2[bucket]++; } for (int i = 0; i < secondLevelBucketNumm; 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[thirdLevelBucketNumm]; for (int i = 0; i < thirdLevelBucketNumm; ++i) { bucketlevel3[i] = 0; } for (int cookie : level2bucket2) { long hashValue = splitBucket(md5, cookie, shuffleLevel3); int bucket = (int) (hashValue % thirdLevelBucketNumm); bucketlevel3[bucket]++; } for (int i = 0; i < thirdLevelBucketNumm; i++) { System.out.println("3层" + i + "桶:" + bucketlevel3[i]+" 个流量"); } System.out.println("==第2层2号桶流量到达第3层实验 end!=="); } 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); } static boolean isMd5 = false ; private static long splitBucket(MessageDigest md5, long val, String shuffle) { shuffle = (shuffle == null) ? "" : shuffle ; String key = String.valueOf(val) + shuffle; long hash = 0 ; if(isMd5) { byte[] ret = md5.digest(key.getBytes()); String s = byteArrayToHex(ret); hash = Long.parseUnsignedLong(s.substring(s.length() - 16, s.length() - 1), 16); }else { /* hash = key.hashCode(); HashFunction murmur3_128 = Hashing.murmur3_128(); HashCode hashBytes = murmur3_128.hashBytes(key.getBytes()); hash = hashBytes.asLong(); */ /**/ hash = Hashing.murmur3_32().newHasher().putLong(val).putBytes(shuffle.getBytes()).hash().asInt(); } if (hash < 0) { hash = hash * (-1); } return hash; }}
我们观测的第2层和第3层流量均来源于第一层的2号桶。所以得出结论,第一层的流量在第2层、第3层均得到重新的离散分配。
实际使用中,业务场景复杂,我们会面临需要设计更复杂的hash算法的情况,MD5是一种相对容易,效果也不错的方式。有兴趣可以关注大质数素数hash算法等更加精密优良的算法。同时,分层实验中,为了防止流量影响,还会有“流量隔离”等更复杂的概念。
转载地址:http://cfdoi.baihongyu.com/