一日一技：二分偏左，二分搜尋在分散式系統裡面也有用？

攝影：產品經理

自制帶太陽蛋的雜醬麵

相信大家都知道二分搜尋，在一個有序的列表中，使用二分搜尋，能夠以O(logN)的時間複雜度快速確定目標是不是在列表中。

二分搜尋的程式碼非常簡單，使用遞迴只需要幾行程式碼就能搞定：

def binary_search(sorted_list, target):
    """
    sorted_list是單調遞增的列表
    """
    if not sorted_list:
        return False
    mid = len(sorted_list) // 2
    if target > sorted_list[mid]:
        return binary_search(sorted_list[mid + 1:], target)
    elif target < sorted_list[mid]:
        return binary_search(sorted_list[:mid], target)
    else:
        return True

執行效果如下圖所示：

Python自帶了一個二分搜尋的模組，叫做 bisect ，它也能實現二分搜尋，但是它的執行結果跟我們上面程式碼的效果有點不同：

import bisect

a = [41, 46, 67, 74, 75, 76, 80, 86, 92, 100]
index = bisect.bisect(a, 75)
print(index)

index = bisect.bisect(a, 82)
print(index)

執行效果如下圖所示：

可以看到， bisect.bisect() 返回一個索引。如果要搜尋的數已經在列表裡面了，那麼它返回的是這個數在列表中， 最右邊 的這個目標數的索引+1. 以列表 [41, 46, 67, 74, 75, 76, 80, 86, 92, 100] 為例，要搜尋 75 。由於 75 在原來列表中的索引是 4 。因此返回 索引+1 也就是5. 如果原來列表中， 75 出現了多次，比如 [41, 46, 67, 74, 75, 75, 76, 80, 86, 92, 100] 那麼返回的是 最右邊 那個 75 對應的索引 +1 ，也就是 6 。

如果要找的數字不在原來列表中，那麼 bisect.bisect() 會返回一個索引，當我們把目標數字插入到這個列表中對應索引的位置時，列表依然有序。例如 [41, 46, 67, 74, 75, 76, 80, 86, 92, 100] 中，我們找 82 。它返回的是 7 。原來列表裡面索引為7的位置是數字 86 ，我們把82插入到這個位置，原有的資料依次後移一位，此時列表依然有序。

bisect 這個模組還有一個函式，叫做 bisect.bisect_left() 。如果目標數字在原來的列表中，那麼返回的是最左邊那個數字對應的索引.如果不在列表中，那麼返回的索引插入目標數字以後依然有序，如下圖所示：

這個函式看起來非常簡單，但你可能不知道，它在分散式系統中也有重要的用途。

假設現在你有10個Redis的單節點用來做分散式快取。因為某種原因，你不能做叢集。當你要搜尋一個數據的時候，你要先確定這個資料在不在Redis中。如果在，就直接從Redis中讀取資料；如果不在，就先去資料庫裡面讀取，然後快取到Redis中。

因為資料量很大，你不能把同一份資料同時存在10個Redis節點裡面，因此你需要設計一個演算法，不同的資料存放在不同的Redis節點中。

當你要查詢資料的時候，你能根據這個演算法查詢到資料（如果在快取中）應該存放在哪個Redis中。

稍微有一點分散式系統設計經驗的同學肯定會想到，這個簡單啊，10個Redis節點編號0-9.對 key 計算Hash值，這個雜湊值是32位的十六進位制數，可以轉換成十進位制以後對10求餘數，餘數是多少，就放到對應的節點裡面。

這樣一來，只要來了一個新的資料，你只需要去餘數對應的Redis中判斷它有沒有快取就可以了。

但問題來了，如果你開始使用這個方法，Redis中已經有資料了，那麼你的Redis節點數就不能變了。一旦你增加或者減少1個節點，所有餘數全部變了，新來的資料找到的Redis節點肯定是錯的。例如key的Hash值原來除以10，餘數是2，現在除以9，餘數是1.那本來你應該去2號Redis找快取，現在卻跑到1號Redis找快取，那一定找不到。

這個問題要怎麼解決呢？我們用一個簡單的例子來做演示。假設我現在有一個列表： [200, 250, 300, 400, 500, 530, 600] 。每個數字代表這個價位的房子。單位是萬。你想買一個房子，但便宜的房子太破，好的房子又太貴。因此你只找價格等於你的期望，或者雖然比你的期望略高但差距最小的房子。

假設現在你的期望是250萬，而正好有個房子賣250萬，因此你可以買它。

假設現在你的期望是470萬，那麼你唯一的選擇是500萬的房子。

到目前為止應該非常好理解，那麼我們來增加或者減少候選項：

1. 500萬的房子被別人買走了。列表變成 [200, 250, 300, 400, 530, 600] ，因此唯一適合你的是530萬的房子。
2. 如果現在250萬的房子被人買走了，列表變成 [200, 300, 400, 500, 530, 600] 。此時對你 沒有任何影響 ，適合你的房子還是500萬的房子。
3. 如果現在增加了一個480萬的房子，列表變成 [200, 250, 300, 400, 480, 500, 530, 600] 。那麼現在適合你的房子變成了480萬。
4. 如果現在增加了一個240萬的房子，列表變成 [200, 240, 250, 300, 400, 500, 530, 600] 。此時對你 沒有任何影響 ，適合你的還是500萬的房子。

這個場景，我們正好可以使用 bisect.bisect_left() ！效果如下圖所示：

當備選項發生改變的時候，只有你目標選項附近的房子受到了影響。而小於你候選項的房子和貴的多的房子的變動，對你沒有任何影響。

你注意到了嗎，這個場景跟我們分散式快取增減Redis節點的場景非常像。我們原來有10臺Redis，現在新增了一臺，變成11臺了。那麼 只有一臺 Redis的 部分快取 會遷移到這個新增的Redis中。而其它9臺Redis的快取不需要做任何改變。

同理，當我們刪除一臺Redis節點時，這個被刪除的節點裡面的資料，只需要同步到它旁邊的另一臺Redis節點中就可以了。另外8個Redis節點不需要做任何修改！（也可以不同步，只有一小部分key會因為刪除這個節點導致找不到資料，而重新讀資料庫。80%的快取不會受到任何影響。）

這就是 一致性Hash 的演算法。

我來簡單描述一下這個演算法的實現過程。首先，我們使用 redis.Redis(不同redis的連線引數) 建立10個連線物件。然後把每個連線物件和一個Hash值建立對映，如下圖所示：

然後，我們把這10個Hash值排序以後放到一個列表中。如下圖所示：

現在，來了一條新的快取查詢需求，我們計算key對應的Hash值，然後使用 bisect.bisect_left() 到列表中去尋找它對應的Redis節點的Hash值的索引。如果返回的索引等於列表的長度，那麼讓索引等於0. 找到索引以後，拿到對應的Redis節點的Hash，最後再用這個Hash去找到對應的Redis節點，簡化程式碼如下：

`

如果新增或者刪除了Redis節點，那麼只需要更新 node_map 和 cycle 就可以了。只會發生很小的資料遷移，對絕大部分的快取都不會造成任何影響。例如我現在把 第1個Redis連結物件 對應的Hash： fbef6b15be1abe9edc8f6aaac6a86357 從 node_map 和 cycle 中刪除。再進行查詢，會發現依然找到的是編號為6的Redis節點。

一致性Hash在分散式系統中有廣泛的應用。但你可能想不到，它的核心原理就是二分搜尋裡面的 bisect_left 。

當然，上面只是簡化演算法。一致性Hash的完整演算法還涉及到虛擬節點和避免資料傾斜的演算法。如果大家有興趣的話，我也可以寫一篇文章，完整解釋它的演算法實現。

END

我的爬蟲架構課開課啦！

爬蟲架構進階就在這裡

送未聞Code知識星球一年訂閱！

一二線大廠在職員工

十多年碼齡的程式設計老鳥

國內外高校在讀學生

中小學剛剛入門的新人

在 “未聞 Code技術交流群” 等你來！

入群方式：新增微信“mekingname”，備註“粉絲群”（謝絕廣告黨，非誠勿擾！)