二分法表面上看很簡單，但歷史上出現(xiàn)第一個沒有 bug 的二分法代碼還頗費了一番工夫。雖然我們在日常工作中不用手寫二分法，但它的思想?yún)s很有用，例如用于排查 master 分支上有問題的 commit。

場景

通常來說，master 分支上的代碼需要保證沒有 bug，隨時能夠發(fā)布。但在實際的工作場景中，為每個 commit 做嚴格的 ab 測試、驗證是很麻煩的事情。有時候，只改一行代碼，改動非常小，直接就合入 master 了。

假設(shè)我們每周固定上一次線，master 上已經(jīng)積累了十幾個 commit 了。直接全量上線最新的 commit 可能會引入問題：業(yè)務(wù)指標(biāo)不平、耗時不平、錯誤率不平……

因此要想辦法能將這些 commit 安全地推上線，找到其中有問題的 commit。

原理

假設(shè)線上有 1000 個實例，拿出 50 臺作為 base 組，50 臺作為 abtest 組，也就是拿 10% 流量來做 ab 實驗。前者就是基準(zhǔn)，以這個為標(biāo)準(zhǔn)，如果 abtest 組符合標(biāo)準(zhǔn)，那就認為其沒問題。

master 分支

在上面這張圖中，C0 代表項目的第一個提交，C100 代表當(dāng)前線上正在跑的版本。C101 到 C110 是一周以來所做的變更，我們的目標(biāo)是將 C110 推全到線上。

問題是 C101 -> C110 之間可能存在一些有問題的 commit，任務(wù)就是找到這個 commit。

我們將 C100 部署到 base 組，將 C110 部署到 abtest 組，線上跑一天時間。

ab 實驗

通過收集各種業(yè)務(wù)指標(biāo)、服務(wù)指標(biāo)、工程指標(biāo)等，來比較兩個版本間的差異。

如果我們發(fā)現(xiàn) base 和 abtest 組的指標(biāo)基本一致，說明 C101->C110 中間的版本沒有問題，是安全的。那就可以直接推全 C110;否則，說明中間存在有問題的 commit，接下來就用二分法來定位。

總之，我們需要一個可以做 ab 實驗的系統(tǒng)、一個可以比較各種指標(biāo)的系統(tǒng)。

做法

理解了原理，做法就比較簡單了。但這中間還是有一些稍微有點繞的地方，如果不深入研究一下，很可能會錯過這些細節(jié)。

第一次先做個大跨度的 ab 實驗：當(dāng)前線上的版本(C100) -> master 上最新的版本(C110)，將多個 commit 包括進來，發(fā)現(xiàn)指標(biāo)不平，說明有問題的 commit 就在這個之間。

再在中間選擇一個版本 C105，開一個 ab：C105->C110，發(fā)現(xiàn)有問題;同時，開一個 C100->C105 的 ab，沒有問題。說明到 C105 為止都沒有問題，C105 成為最新的安全版本。

接著又開了一個 ab：C105->C107，如果這時 base 組用的是 C106，其實是不行的。因為前面的實驗只能說明 C105 沒有問題，并不能說明 C106 沒問題。即 到 C100 安全傳遞到了 到 C105 安全。

再繼續(xù)開 C107->C110……

總結(jié)規(guī)律：整個過程就是一個通過二分查找不斷擴大安全版本范圍，縮小問題版本范圍的過程。

首先有一個已知的安全版本(通常是線上正在跑的版本)，這個作為 base，然后另一側(cè)先往外探一大步，通常是最新的提交;這一次 ab 實驗 通常是有問題的，不然也沒有接下來的二分查找。

接著在中間找一個版本，分別開兩個 ab：start->mid，mid->end。運氣好的話，start->mid 可以排除，那么安全范圍會迅速擴大。然后是同樣的思路，遞歸做下去。

總結(jié)

本文描述了一個如何用二分法檢驗 master 分支未上線 commit 的過程。

其中有一個關(guān)鍵的點是當(dāng)確定了 mid 沒問題時，下一次要以 mid 為起點，不能用 mid+1。因為 mid 被證明安全，可以作為 base，不能說明 mid+1 也安全。言外之意是 base 是免檢的，其他 commit 都應(yīng)該作為待檢對象。

進一步抽象一下：給定一個包含 0 和 1 的數(shù)組，1 占多數(shù)，代表沒問題的 commit，0 則代表有問題的 commit，需要找到其中的 0。

最簡單的辦法是一個個地找，線性找的復(fù)雜度是 O(n)，改用二分查找法降為 O(logN)，加快速度。