相信大家都知道二分搜索，在一個有序的列表中，使用二分搜索，能夠以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萬的房子。

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

• 500萬的房子被別人買走了。列表變成[200, 250, 300, 400, 530, 600]，因此唯一適合你的是530萬的房子。
• 如果現在250萬的房子被人買走了，列表變成[200, 300, 400, 500, 530, 600]。此時對你沒有任何影響，適合你的房子還是500萬的房子。
• 如果現在增加了一個480萬的房子，列表變成[200, 250, 300, 400, 480, 500, 530, 600]。那么現在適合你的房子變成了480萬。
• 如果現在增加了一個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的完整算法還涉及到虛擬節點和避免數據傾斜的算法。如果大家有興趣的話，我也可以寫一篇文章，完整解釋它的算法實現。