---

theme: juejin

貨拉拉A/B實驗分流演算法實踐

業務背景

  貨拉拉成立於 2013 年，成長於粵港澳大灣區，是一家從事同城、跨城貨運、企業版物流服務、搬家、汽車銷售及車後市場服務的網際網路物流公司。截至 2022 年 4 月，貨拉拉的業務範圍已經覆蓋了國內 352 座城市，月活司機達到 66 萬，月活使用者達到 840 萬。

  這些業務線裡面產生了非常多的業務場景，而大部分業務場景又有A/B實驗的訴求，來支撐他們完成對產品、演算法、策略的優化方向的選取。目前貨拉拉A/B實驗平臺總計已經有200+業務場景、完成10000+以上的實驗，當前月活實驗達到1000+。

A/B 實驗介紹

  A/B實驗的基本思想其實非常簡單——通過控制變數法，隨機抽取一些樣本進行實驗組和對照組的對比實驗，回收實驗資料，通過統計學相關知識判斷兩組的優劣。而目前網際網路行業的A/B實驗設計基本上都是參考Google公司的經典論文：《Overlapping Experiment Infrastructure:More, Better, Faster Experimentation》。通過“層”，“域”的設計，從寶貴的線上流量中選擇一部分，驗證產品的某個新特性，回收資料，以此選擇產品迭代方向。大膽假設，小心求證，用科學的方式讓產品的每一次迭代都走在正確的道路上。

貨拉拉A/B實驗平臺架構設計

上圖是貨拉拉A/B實驗平臺架構圖。按照實驗步驟可分為實驗前、實驗中、實驗後三個步驟。 - 實驗前，使用者在實驗配置平臺上完成實驗的設計，包括實驗生命週期、目標受眾、分組配置、流量管理等等。 - 實驗中，在實驗SDK中完成實驗的分流、實時埋點資料、監控資料的上報，在實驗配置平臺通過實時/離線的資料鏈路進行回收展示。 - 實驗後，將回收的資料通過顯著性分析，OLAP引擎計算等進行顯著性報告、指標詳情報告等的展示。 按照模組劃分實驗配置平臺、分流上報的SDK、資料回收鏈路。

實驗配置平臺

  實驗配置平臺是使用者操作的介面。在上面使用者完成實驗的所有設計工作，包括實驗流量的劃分、分流方式的選擇、配置關注的指標、圈定實驗的受眾人群等等。實驗配置平臺還可以實時觀察實驗中的狀態，實時的進組流量、分流異常監控告警、命中診斷等等。實驗結束之後，使用者也需回到實驗配置平臺，檢視實驗資料的各項報告，置信度報告、指標詳情報告等，完成實驗的最終效果評估。對於產品、分析師等同學而言，從始至終可以都在A/B實驗配置平臺上完成整個實驗的閉環。

分流上報SDK

  分流上報的SDK則是業務研發同學需要接入的，首先業務申請流量的分層ID，業務研發根據分層ID結合他們產品同學設計的A/B的實驗，構造請求引數，分別呼叫SDK的命中分流介面和埋點上報介面，根據命中分流介面的返回結果編寫業務程式碼，進行業務邏輯控制。埋點上報介面則是為了進行最終的實驗效果評估使用。

資料回收鏈路

  資料回收鏈路依賴於貨拉拉大資料團隊搭建的底層鏈路。最初的回收鏈路是將SDK上報到kafka的埋點資料通過飛流平臺（大資料實時計算平臺）的資料採集服務，寫入原始資料表，再由大資料鏈路進行T+1日的指標計算任務，計算結果寫入mysql，最後由實驗平臺進行展示。另外少量簡單的實時指標則直接通過flink走實時鏈路計算，寫入到mysql中。隨著大資料OLAP引擎的完善，能支援10 億資料秒級關聯，所以目前A/B實驗已陸續將所有指標都遷移到OLAP引擎實時計算。

五種分流演算法

  對於A/B實驗而言，最重要的就是保證實驗結果科學性。A/B實驗的目的就是用科學的方式去幫助產品決策，如果實驗結果不科學的話，則會誤導產品決策，從而造成諸如使用者流失等嚴重後果。而保證實驗結果科學性的關鍵點在於，總樣本的選擇和對總樣本的劃分。比如要做一個某款香水的香味濃郁和清香哪個銷量會更好的實驗，如果該香水針對女性使用者，那麼總樣本應該選擇女性使用者。在女性使用者中，實驗組和對照組中的女性應該儘可能保證“同質性”，所謂“同質性”就是保證對可能影響實驗指標的因素，實驗組和對照組應該是一致的。在該實驗中，可能就是女性使用者的年齡、收入等等可能影響購買該香水的所有因素。

  為了保證不同的組的樣本的“同質性”，最簡單的辦法就是隨機，將總樣本完全隨機分成不同組，基本上能保證不同組樣本的同質。這也是業內目前最常見的A/B實驗分流演算法——隨機分流。 而貨拉拉A/B實驗平臺根據自身的業務場景需求，為了加快實驗收斂速度和保障實驗結果科學性，又設計了其他4種分流演算法，分別為：時間片分流、時間片輪播分流、指定順序時間片輪播分流、時空分流。

下面將對5種分流演算法進行一一介紹。

隨機分流/增強隨機演算法

  隨機分流演算法是業內最常見的A/B實驗分流演算法，能夠滿足大部分A/B實驗場景，比如廣告投放、UI樣式、營銷派券等場景對A/B實驗的訴求。隨機分流演算法的設計也較為簡單，通過將分流ID（使用者ID/司機ID等）隨機分到不同組的任意一組即可，但需要特別注意的是，A/B實驗一般都需要滿足：進組的使用者不再出組，即：同一個分流id，在不調整分組流量佔比的情況下，無論多少次進入A/B實驗，都應該在同一個分組。

  如何實現這個“隨機”演算法？貨拉拉A/B實驗第一版隨機分流如下圖左側所示，根據實驗的分組資訊和分流配置，為每一個分組初始化一個分桶，桶中有100個坑位，按照該分組比例，將其中的部分的坑位賦值。將分流ID通過murmurs3 hash演算法hash的整數mod100，得到0～99之內的整數，遍歷不同組的分桶中，該整數所對應下標的坑位是否被賦過值，若有，則判定該id命中改組。由於hash和mod的過程不變，所以能滿足進組使用者不在出組，而經過調研，murmur3的hash演算法能保證結果在32位整形數上面的隨機分佈。

  上述隨機演算法要做到“隨機”需滿足：murmur3的hash值在mod100之後，在100的區間內能均勻雜湊。然而由murmur3的hash演算法，保證的是32位整形數上面的均勻雜湊，mod100之後，不一定能做到均勻。實際生產中也遇到在部分場景下，分流key出現雜湊不均勻的情況。若直接儲存一個32位的桶，佔用的記憶體又較大。於是參考一致性hash演算法，虛擬一個32位的hash環來表示全樣本範圍，每個分組根據其所佔用的流量佔比在環上記錄其區間邊界位置，判定命中的過程第一步和上述普通隨機一致，經過murmur3演算法hash得到一個32位的整形數，順時針在環上找到的第一個節點所屬的組，即落在了某個分組的區間內，完成判定。

時間片分流

  時間片分流也作為業內比較常見的一種分流演算法，其原理和隨機分流一致，唯一差別在於：隨機分流的分流物件是使用者唯一ID（司機唯一ID），而時間片分流的分流物件是一段段的時間片。這種分流演算法的應用在某些業務場景並不關注單個使用者的選擇，更關注在一個時間片內所有使用者的選擇。假定時間片大小為1s，那麼在這1s內所有的使用者都會進入同一個組。同時將城市id加入隨機因子中，就可以觀察不同城市在一個時間片內使用者分流情況的對比，計算業務評估指標。

時間片輪播分流

  時間片輪播分流是基於貨拉拉運力排程場景催生的、由貨拉拉A/B實驗團隊獨立實現一種分流演算法。貨拉拉許多業務場景的分流物件是訂單ID，訂單涉及司機、使用者，會有明顯高低峰期，並且在某個時間段訂單的積壓會影響下個時間段的訂單指標。比如一個研究不同調度演算法對訂單響應率的影響的實驗，如果採用隨機分流，對訂單進行隨機採用某個排程演算法，就無法觀察到該排程演算法在高峰期和低峰期的對比表現，也無法消除，高峰期訂單積壓後導致後續時間段響應率變動對實驗結果產生的影響。又或許有人提出可以採用時間片分流，並將其時間片大小設定得大一點能夠覆蓋住一個高峰期和低峰期。但這樣又帶來的問題是，如果將時間片長度設定太大，樣本流量就會不足，A/B實驗就無法快速收斂。實驗的週期就會被拉長。線上流量是很寶貴的，功能迭代的驗證階段也一般要求快速驗證，顯然單純時間片分流是無法滿足要求的。

  所謂時間片輪播，首先需要劃分一個週期，比如一天（24*3600s），再指定時間片大小3600s，同時設定不同組佔用的時間片的個數，那麼分流SDK就會按照該所設定不同分組佔用時間片的個數進行分流，保證一個時間片內所有訂單進入相同組，並且在一個週期內，不同組佔用時間片的比例符合預先的設定。

  時間片輪播的實現關鍵在於如何保證分散式場景下的分流結果一致。根據流量請求SDK的時間（也可以設定為訂單的建立時間）計算出來該樣本所處的某個週期內的時間片下標，在每個週期第一個時間片的請求到達的時候，生成本輪週期內時間片對應分組的分佈，並採用實驗特定標識作為hash因子，對時間片總個數取模的方式交換週期內時間片分佈，起到打散時間片的作用。由於每個實驗特定標識都是一樣的，就能保證在任意節點，相同的週期內打散的結果是一致的，實現了分散式場景下的分流結果一致。

  時間片輪播自推出後廣受排程場景、分單場景歡迎，根據該分流演算法的實現方式撰寫的專利也成為貨拉拉公司首份授權專利。

指定順序的時間片輪播分流

  指定順序的時間片輪播分流其實和時間片輪播分流的區別就在於，時間片輪播分流會對週期內的時間片分佈進行打散，是一個“隨機化”的過程。而指定順序輪播的時間片序列，完全由使用者自行指定，並且可以指定多個序列，相當於給週期外層再套一個輪轉週期，第一個週期按照序列一進行輪轉，第二個週期按照序列二進行輪轉，以此反覆，週而復始。

也許有讀者會好奇有了時間片輪播，為何還需要指定順序的時間片輪播？適用於什麼場景呢？

其實答案在分析時間片分流的時候已經指出了： - 線上的流量是非常寶貴的 - A/B實驗需要快速驗證

  用時間片作為分流ID帶來的副作用就是很多獨立流量被聚合成一個樣本，比如用3600s作為一個時間片，那麼一天相當於只有24個樣本。樣本量減少的情況，又要保證實驗結果的科學性，那麼就得延長實驗時間，而這與上述第二點又是相悖的。時間片輪播分流相比時間片分流優化了純時間片分流的隨機性導致部分分組樣本不足的情況，而制定順序的時間片輪播則更為徹底的解決，完全由使用者去制定週期內不同分組所佔用的時間片順序和比例，並且可以新增多個序列，不同時間週期採用不同序列，是A/B實驗更快的達到收斂，滿足結果科學性所需的樣本。

  指定順序的時間片輪播的實驗相比於時間片輪播而言更簡單，只需要計算出來流量所處在哪一個週期，以及週期裡面時間片的序號，然後找到該序號和分組對應的結果即可。

時空分流

  催生時空分流的業務是智慧附加費場景，該場景關注不同起終點在不同時間段的附加費指標。該場景也推廣到任何同時關注空間（起終點、距離、座標等）和時間（高低峰、時間段）的業務上。還是以附加費場景介紹，對一筆訂單附加多少費用，需要綜合考慮該筆訂單的起終點和當前時間段的訂單情況（高低峰），通過A/B實驗的時空分流就可以驗證不同附加費策略在空間和時間上的分佈的優劣表現。

  要觀察不同空間上的表現，對空間物件（起終點OD對、距離、座標、城市等）等等進行隨機分流就可以實現，不過此時隨機分流的分流物件不再是使用者ID/司機ID/訂單ID，而是空間物件。不同時間段（高低峰）上的表現情況則可以通過上述已經介紹過的任何一種時間片分流演算法來實現觀測。

  時空分流的實現比較特別，從嚴格意義上來說，並不是一種新的分流演算法，而是通過組合兩種分流演算法去實現。可以理解為兩層實驗，流量在經過第一層的時候（空間隨機分流），會被分成不同群（空間分群1、空間分群2等等），然後每一個群裡面的流量會經過第二層（時間片分流/時間片輪播/指定順序的時間片輪播），最終對映到某一個具體的組上，實施具體的策略。所以時空分流實際是通過一個雙層實驗，或者也稱之為父子實驗的方式來實現的。

結語

  自此貨拉拉A/B實驗平臺的基本架構設計和分流演算法基本原理介紹完畢。基本架構設計和分流演算法是貨拉拉A/B實驗平臺的核心，但是對於貨拉拉A/B實驗平臺，還有非常多的關鍵點，實驗中的實時監控模組、實驗的診斷告警模組、實驗的指標體系、實驗的分析報告模組、實驗配置的下發模組等等，每一個模組單獨拎出來可能都需要較多的篇幅去介紹。這些關鍵模組在整體架構下和分流演算法一起組成了目前的貨拉拉A/B實驗平臺，為貨拉拉全業務場景提供A/B實驗的能力，目前已完成了貨拉拉業務線5000+以上的實驗、15000+以上的實驗版本。賦能業務，助力貨拉拉業務更好更快的向前發展。

  當然，貨拉拉A/B實驗平臺目前也存在著一些不足，對比於火山引擎等業內一流的A/B產品，在實驗設計的便捷性和實驗結果指標的豐富度上面仍有差距。由於是內部使用平臺而非商用平臺，目前對使用者而言有一定的使用門檻，使用者體驗不是非常友好。在分流演算法上，我們也缺少分流過程實時調優（多臂老虎機）等AI能力。我們會在未來繼續迭代，會重點關注實驗結果科學性、穩定性、使用者體驗等方面，打造業內一流的A/B實驗平臺。

作者：貨拉拉大資料技術團隊 高階大資料工程師-林濤