蚂蚁技术 + 关注
手机版

10分钟搞懂分层实验原理

  1. 云栖社区>
  2. 蚂蚁技术>
  3. 博客>
  4. 正文

10分钟搞懂分层实验原理

华蒙 2016-02-18 14:14:07 浏览11725 评论2

摘要: 想要同一时间做N个实验?想要同一份流量不同实验之间不干扰?想要每个实验都能得到100%流量? 那么你就需要分层实验。

文/九德


1. 背景


  • 想要同一时间做N个实验?

  • 想要同一份流量不同实验之间不干扰?

  • 想要每个实验都能得到100%流量?

9463fcb0f86b583f022c5bf7d0aebdd46d0ace6c
那么你就需要分层实验。


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. 实战讲解


2.1 我们的程序介绍

  • 使用java SecureRandom模拟cookie的获取(随机化cookie,模拟真实场景

  • hash算法选用上文介绍的MD5。实验分两种:对cookie不做任何处理;对cookie采用增加离散因子离散化

  • 一共三层实验(也就是3个实验),我们会观察第一层2号桶流量在第2层的分配,以及第2层2号桶流量在第3层的分配

  • 如果cookie加入离散因子后,一份流量经过三个实验,按照如下图比例每层平均打散,则证明实验流量正交

8ce20ad919001edfbb43a1ca2e30441c9c84ef95
从上图可以看出,即使第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"); } }

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层均得到重新的离散分配

3. 总结

  • 随着个性化和算法不断引入我们的应用,同一时间做多个实验需求越来越多,更多人开始使用分层实验。

  • 实际使用中,业务场景复杂,我们会面临需要设计更复杂的hash算法的情况,MD5是一种相对容易,效果也不错的方式。有兴趣可以关注大质数素数hash算法等更加精密优良的算法。同时,分层实验中,为了防止流量影响,还会有“流量隔离”等更复杂的概念。


扫码关注阿里技术保障公众号,有更多技术干货分享,更有机会赢取精美礼品。

ea14ec7fb062eab8a29333c7a100d227a258a14a
【云栖快讯】阿里巴巴小程序繁星计划,20亿补贴第一弹云应用立即开通购买,限量从速!  详情请点击

网友评论