基於hash計算的多層實驗流量切分的成功實現

  1. 環境紹介

  站點新功能還是是站內新策略研發完結在這以後,在全流量上線之前要評估新功能還是新策略的優劣,常用的評估辦法是A-B測試,作法是在全量中取樣出兩份小流量,作別走新策略分支和舊策略分支,經過相比較這兩份流量下的各指標的差別,我們可以評估出新策略的優劣,繼續往前表決新策略是否全流量。

  上文中提到的取樣是指依照某種確認的隨機化辦法,對線上流量施行區分清楚。取樣可以指這種區分清楚的辦法,也可以指區分清楚獲得的一個流量子集。取樣是一種特別的小流量,要求對流量的區分清楚務必保障平均性和隨機性,況且可以依據需要過淋掉不合規范的局部,我們把取樣的過程分為流量切分和流量用篩子選兩個步驟,流量切分是指把全流量施行平均的打散,提出取得出那裡面固定的流量比例,流量用篩子選是對流量切分的匡助,用篩子選過程就是從切分好的流量中過淋掉不合規范的局部,本文主要牽涉到的是流量切分的成功實現。

  2. 單層流量切分架構

  做到流量切分的常用的辦法是單層流量切分,流量切分需求以某種形式施行,即流量切分的打散根據,例如,我們可以根據流量中的cookie打散,還是是隨機打散等,打散的形式不一樣,切分的對象全集也就不一樣了,假如我們根據cookie打散,那末我們的切分對象全集就是全部的cookie,若是隨機打散,那末我們的切分對象全集就是該站點的全部的流量。

  

  圖1.1 單層流量切分架構概況圖

  有了上頭的想法,我們怎麼樣成功實現單層流量切分呢?如圖1.1所示,我們依照指定的流量切分形式,將所需求的輸入參變量先通過一次hash計算,萌生最後結果的平均性和隨機性由hash算法來保障,有了hash萌生的最後結果,流量切分的過程還沒有終了,我們還需求將hash最後結果對應到切分對象的全集上頭,成功實現辦法是將切分對象全集看作是一個區間段,而後將hash最後結果對應到區間段上頭,區間的體積是切分的最小粒度表決的,例如,假如需求最小切分粒度為0.01百分之百,則我們選取的區間段為[0,9999],有了區間段的定義,我們可以將hash最後結果對一個數字取模,這個數字等於區間段最大值加1,取模在這以後的最後結果可以惟一的對應到切分對象全集區間上頭,這麼我們就將全部的流量擊倒達流量切分對象全集上頭。

  最終,我們再將區間段依照實驗需要細分,區分清楚成多少子區間,用作於實驗相比較,例如下所述圖所示,將整個兒100百分之百的區間分為多個子區間,每個子區間運用惟一的編號——sid,作為區間的惟一的標識,sid=1的子區間對應的流量為1百seo分之百,那末它的子區間就是[0,99],同理,sid=2的第二個1百分之百的子區間對應的區間值為[100,199],這麼我們就將一個100百分之百的完整區間區分清楚成了多少個子區間,兩個比例相同的子區間就可以用作於實驗策略相比較。

  

  圖1.2 流量子區間的區分清楚

  3. 可復用流量的多層流量切分架構

  這種單層流量切分形式是一種獨佔式的流量切分形式,一個子區間只能提供一個實驗運用,一個煩請只能打中目標一個實驗,長處是實驗之間解藕,不互相影響,欠缺是資源有限,流量分配完結在這以後,後續的需要將處於長時期的等待與需要吃東西狀況,這種獨佔式的流量切分形式,顯然在實驗需要不斷增加的事情狀況下是絕對不可以滿意的,為理解決獨佔的問題,我們可以認為合適而使用多層流量切分形式。

  多層流量切分的思想是將單層結構擴展為多層結構,如下所述圖所示,多層之間務必滿意正交性,這處多層之間的正交性是指某一層的不論什麼一個子區間可以隨機的、平均的對應到其它層上頭,這麼我們就把一個子區間對其它層的影響平均的散布到整個兒層上頭。

  多層流量切分架構可以將實驗流量從100百分之百擴展到100百分之百*n,也就說每層中的流量我們都可以用做於實驗相比較,一次煩請可以同時打中目標多個實驗,實驗流量是復用的,多層流量是滿意不一樣層的實驗之間的影響都是平均、可預估的,開展多層實驗的前提是保障這種實驗間的影響是可接納的,有一點實驗是不准許不論什麼復用,例如,展出類的實驗,假如兩個實驗各自指定了一套展出式樣模型板,而從展出板塊的角度來講一次煩請只能展出一種式樣模型板,因為這個,這處不兼容的實驗只能位於同一層中。

  

  圖1.3 多層流量切分架構概況圖

  多層流量切分的另一個優勢是每一層我們可以運用不一樣的切分形式施行,這麼也莫大的浩博了流量切分的多樣性,那末,還有另一個問題,每一個流量層中只能認為合適而使用一種流量切分形式,假如同一層中有多種切分形式的需要又怎麼樣解決呢?解答是經過層的嵌套來成功實現,層的嵌套是指在一個層中可以裡面含有其它的層,如下所述圖所示,長方形表達層,圓形表達切分出來的實驗流量,那裡面,1號層裡面含有了2、3、4三個層,4號層又裡面含有9、10、11三個層,為了達到同一層內多種流量切分形式的目標,我們需求將該層切分成多個區間,例如,下圖中的2號層就被分成了5、6兩個層,不過這兩個層也務必認為合適而使用相同的切分形式,由於這兩個層相當於把其父層的流量分成了兩局部,故而這兩局部的萌生形式應當是完全一樣的,最終,在5、6層中,我們又可以樹立其它的層,這兩個層就可以認為合適而使用不一樣的流量切分形式了。

  

  圖1.4 流量切分多層嵌套概況圖

  理論上,多層流量切分架構的可切分層數是無限的,可以支持恣意多的流量層,不過,從成功實現的角度來講,層數做到無限是很難成功實現的,由於,為了保障層和層之間的正交性,我們一定要為每一層成功實現一套hash算法,保障每種hash算法的最後結果是正交的,要成功實現層數的無限,則需求成功實現無限多個保障正交的hash算法,hash算法的增多必然會造成正交性的減退,我們可以成功實現有限個正交的hash算法,hash算法的數量是要求可以滿意全部的實驗需要的。下邊我們紹介一種多層流量切分架構的成功實現辦法。

  為了成功實現多層流量切分,我們的思考的線索是先成功實現一種hash算法,這種hash算法的輸入是cookie、隨機值等信息,輸出是單次hash的最後結果,況且保障這種hash算法最後結果足夠的平均和隨機,而後將這種hash施行變換,擴展現多個正交的hash算法。

  為了證驗單個hash算法的隨機性和平均性,我們施行了實驗證驗,如下所述圖所示,每一行表達一個100百分之百的全集,每一列表達從全集中抽抽取10百分之百,測試的全集是100w,從下邊的測試數值來看,每個層中的流量切分最後結果是比較平均和隨機的。

  

  圖1.5 單hash算法平均性、隨機性證驗明驗數值

  有了單層hash算法,我們需求將單層hash擴展變成多層,這處可以認為合適而使用的辦法眾多,本文認為合適而使用的是移位變換的辦法將單層hash擴展變成多層hash,多層實驗流量切分的真實背景測試數值如下所述文所示。

  4. 實際數值測試

  為了證驗其算法的行得通性,我們施行了實際數值測試,測試最後結果如下所述:

  表1.2 平均性證驗數值

  

  

  by yangfangwei&huangjin&yaoshiyu