文章內(nèi)容

基于hash計(jì)算的多層實(shí)驗(yàn)流量切分的實(shí)現(xiàn)

發(fā)布時(shí)間: 2012/8/27 9:30:53

1. 背景介紹

　　站點(diǎn)新功能或者是站內(nèi)新策略開發(fā)完畢之后，在全流量上線之前要評(píng)估新功能或者新策略的優(yōu)劣，常用的評(píng)估方法是A-B測(cè)試，做法是在全量中抽樣出兩份小流量，分別走新策略分支和舊策略分支，通過(guò)對(duì)比這兩份流量下的各指標(biāo)的差異，我們可以評(píng)估出新策略的優(yōu)劣，進(jìn)而決定新策略是否全流量。

　　上文中提到的抽樣是指按照某種確定的隨機(jī)化方法，對(duì)線上流量進(jìn)行劃分。抽樣可以指這種劃分的方法，也可以指劃分得到的一個(gè)流量子集。抽樣是一種特殊的小流量，要求對(duì)流量的劃分必須保證均勻性和隨機(jī)性，并且可以根據(jù)需求過(guò)濾掉不符合規(guī)范的部分，我們把抽樣的過(guò)程分為流量切分和流量篩選兩個(gè)步驟，流量切分是指把全流量進(jìn)行均勻的打散，提取出其中固定的流量比例，流量篩選是對(duì)流量切分的輔助，篩選過(guò)程就是從切分好的流量中過(guò)濾掉不符合規(guī)范的部分，本文主要涉及的是流量切分的實(shí)現(xiàn)。

　　2. 單層流量切分架構(gòu)

　　做到流量切分的常用的方法是單層流量切分，流量切分需要以某種方式進(jìn)行，即流量切分的打散依據(jù)，例如，我們可以依據(jù)流量中的cookie打散，或者是隨機(jī)打散等，打散的方式不同，切分的對(duì)象全集也就不同了，如果我們依據(jù)cookie打散，那么我們的切分對(duì)象全集就是所有的cookie，如果是隨機(jī)打散，那么我們的切分對(duì)象全集就是該站點(diǎn)的所有的流量。

　　圖1.1 單層流量切分架構(gòu)示意圖

　　有了上面的想法，我們?nèi)绾螌?shí)現(xiàn)單層流量切分呢?如圖1.1所示，我們按照指定的流量切分方式，將所需要的輸入?yún)?shù)先經(jīng)過(guò)一次hash計(jì)算，產(chǎn)生結(jié)果的均勻性和隨機(jī)性由hash算法來(lái)保證，有了hash產(chǎn)生的結(jié)果，流量切分的過(guò)程還沒(méi)有結(jié)束，我們還需要將hash結(jié)果對(duì)應(yīng)到切分對(duì)象的全集上面，實(shí)現(xiàn)方法是將切分對(duì)象全集看作是一個(gè)區(qū)間段，然后將hash結(jié)果對(duì)應(yīng)到區(qū)間段上面，區(qū)間的大小是切分的最小粒度決定的，例如，如果需要最小切分粒度為0.01%，則我們選取的區(qū)間段為[0,9999]，有了區(qū)間段的定義，我們可以將hash結(jié)果對(duì)一個(gè)數(shù)值取模，這個(gè)數(shù)值等于區(qū)間段最大值加1，取模之后的結(jié)果可以唯一的對(duì)應(yīng)到切分對(duì)象全集區(qū)間上面，這樣我們就將所有的流量打到了流量切分對(duì)象全集上面。

　　最后，我們?cè)賹^(qū)間段按照實(shí)驗(yàn)需求細(xì)分，劃分成若干子區(qū)間，用作于實(shí)驗(yàn)對(duì)比，例如下圖所示，將整個(gè)100%的區(qū)間分為多個(gè)子區(qū)間，每個(gè)子區(qū)間使用唯一的編號(hào)——sid，作為區(qū)間的唯一的標(biāo)識(shí)，sid=1的子區(qū)間對(duì)應(yīng)的流量為1%，那么它的子區(qū)間就是[0,99]，同理，sid=2的第二個(gè)1%的子區(qū)間對(duì)應(yīng)的區(qū)間值為[100,199]，這樣我們就將一個(gè)100%的完整區(qū)間劃分成了若干個(gè)子區(qū)間，兩個(gè)比例相同的子區(qū)間就可以用作于實(shí)驗(yàn)策略對(duì)比。

　　圖1.2 流量子區(qū)間的劃分

　　3. 可復(fù)用流量的多層流量切分架構(gòu)

　　這種單層流量切分方式是一種獨(dú)占式的流量切分方式，一個(gè)子區(qū)間只能供給一個(gè)實(shí)驗(yàn)使用，一個(gè)請(qǐng)求只能命中一個(gè)實(shí)驗(yàn)，優(yōu)點(diǎn)是實(shí)驗(yàn)之間解藕，不相互影響，缺點(diǎn)是資源有限，流量分配完畢之后，后續(xù)的需求將處于長(zhǎng)期的等待與饑餓狀態(tài)，這種獨(dú)占式的流量切分方式，顯然在實(shí)驗(yàn)需求不斷增加的情況下是完全不能滿足的，為了解決獨(dú)占的問(wèn)題，我們可以采用多層流量切分方式。

　　多層流量切分的思想是將單層結(jié)構(gòu)擴(kuò)展為多層結(jié)構(gòu)，如下圖所示，多層之間必須滿足正交性，這里多層之間的正交性是指某一層的任何一個(gè)子區(qū)間可以隨機(jī)的、均勻的對(duì)應(yīng)到其他層上面，這樣我們就把一個(gè)子區(qū)間對(duì)其他層的影響均勻的分散到整個(gè)層上面。

　　多層流量切分架構(gòu)可以將實(shí)驗(yàn)流量從100%擴(kuò)展到100%*n，也就說(shuō)每層中的流量我們都可以用做于實(shí)驗(yàn)對(duì)比，一次請(qǐng)求可以同時(shí)命中多個(gè)實(shí)驗(yàn)，實(shí)驗(yàn)流量是復(fù)用的，多層流量是滿足不同層的實(shí)驗(yàn)之間的影響都是均勻、可預(yù)估的，開展多層實(shí)驗(yàn)的前提是保證這種實(shí)驗(yàn)間的影響是可接受的，有一些實(shí)驗(yàn)是不允許任何復(fù)用，例如，展現(xiàn)類的實(shí)驗(yàn)，如果兩個(gè)實(shí)驗(yàn)各自指定了一套展現(xiàn)樣式模板，而從展現(xiàn)模塊的角度來(lái)講一次請(qǐng)求只能展現(xiàn)一種樣式模板，因此，這里不兼容的實(shí)驗(yàn)只能位于同一層中。

　　圖1.3 多層流量切分架構(gòu)示意圖

　　多層流量切分的另一個(gè)優(yōu)勢(shì)是每一層我們可以使用不同的切分方式進(jìn)行，這樣也極大的豐富了流量切分的多樣性，那么，還有另一個(gè)問(wèn)題，每一個(gè)流量層中只能采用一種流量切分方式，如果同一層中有多種切分方式的需求又如何解決呢?答案是通過(guò)層的嵌套來(lái)實(shí)現(xiàn)，層的嵌套是指在一個(gè)層中可以包含其他的層，如下圖所示，矩形表示層，圓形表示切分出來(lái)的實(shí)驗(yàn)流量，其中，1號(hào)層包含了2、3、4三個(gè)層，4號(hào)層又包含9、10、11三個(gè)層，為了達(dá)到同一層內(nèi)多種流量切分方式的目的，我們需要將該層切分成多個(gè)區(qū)間，例如，下圖中的2號(hào)層就被分成了5、6兩個(gè)層，但是這兩個(gè)層也必須采用相同的切分方式，因?yàn)檫@兩個(gè)層相當(dāng)于把其父層的流量分成了兩部分，因而這兩部分的產(chǎn)生方式應(yīng)該是一致的，最后，在5、6層中，我們又可以建立其他的層，這兩個(gè)層就可以采用不同的流量切分方式了。

　　圖1.4 流量切分多層嵌套示意圖

　　理論上，多層流量切分架構(gòu)的可切分層數(shù)是無(wú)限的，可以支持任意多的流量層，但是，從實(shí)現(xiàn)的角度來(lái)講，層數(shù)做到無(wú)限是很難實(shí)現(xiàn)的，因?yàn)椋瑸榱吮ＷC層和層之間的正交性，我們必須要為每一層實(shí)現(xiàn)一套hash算法，保證每種hash算法的結(jié)果是正交的，要實(shí)現(xiàn)層數(shù)的無(wú)限，則需要實(shí)現(xiàn)無(wú)限多個(gè)保證正交的hash算法，hash算法的增多勢(shì)必會(huì)導(dǎo)致正交性的下降，我們可以實(shí)現(xiàn)有限個(gè)正交的hash算法，hash算法的數(shù)目是要求可以滿足所有的實(shí)驗(yàn)需求的。下面我們介紹一種多層流量切分架構(gòu)的實(shí)現(xiàn)方法。

　　為了實(shí)現(xiàn)多層流量切分，我們的思路是先實(shí)現(xiàn)一種hash算法，這種hash算法的輸入是cookie、隨機(jī)值等信息，輸出是單次hash的結(jié)果，并且保證這種hash算法結(jié)果足夠的均勻和隨機(jī)，然后將這種hash進(jìn)行變換，擴(kuò)展出多個(gè)正交的hash算法。

　　為了驗(yàn)證單個(gè)hash算法的隨機(jī)性和均勻性，我們進(jìn)行了實(shí)驗(yàn)驗(yàn)證，如下圖所示，每一行表示一個(gè)100%的全集，每一列表示從全集中抽取出10%，測(cè)試的全集是100w，從下面的測(cè)試數(shù)據(jù)來(lái)看，每個(gè)層中的流量切分結(jié)果是比較均勻和隨機(jī)的。