相信大家都知道二分搜索，在一個有序的列表中，使用二分搜索，能夠以O(shè)(logN)的時間復(fù)雜度快速確定目標(biāo)是不是在列表中。

二分搜索的代碼非常簡單，使用遞歸只需要幾行代碼就能搞定：

def binary_search(sorted_list, target):
    """
    sorted_list是單調(diào)遞增的列表
    """
    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，它也能實現(xiàn)二分搜索，但是它的執(zhí)行結(jié)果跟我們上面代碼的效果有點不同：

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()?返回一個索引。如果要搜索的數(shù)已經(jīng)在列表里面了，那么它返回的是這個數(shù)在列表中，最右邊?的這個目標(biāo)數(shù)的索引+1. 以列表[41, 46, 67, 74, 75, 76, 80, 86, 92, 100]?為例，要搜索75?。由于75?在原來列表中的索引是4?。因此返回索引+1?也就是5. 如果原來列表中，75?出現(xiàn)了多次，比如[41, 46, 67, 74, 75, 75, 76, 80, 86, 92, 100]?那么返回的是最右邊?那個75?對應(yīng)的索引+1?，也就是6。

如果要找的數(shù)字不在原來列表中，那么bisect.bisect()?會返回一個索引，當(dāng)我們把目標(biāo)數(shù)字插入到這個列表中對應(yīng)索引的位置時，列表依然有序。例如[41, 46, 67, 74, 75, 76, 80, 86, 92, 100]?中，我們找82?。它返回的是7?。原來列表里面索引為7的位置是數(shù)字86，我們把82插入到這個位置，原有的數(shù)據(jù)依次后移一位，此時列表依然有序。

bisect?這個模塊還有一個函數(shù)，叫做bisect.bisect_left()。如果目標(biāo)數(shù)字在原來的列表中，那么返回的是最左邊那個數(shù)字對應(yīng)的索引.如果不在列表中，那么返回的索引插入目標(biāo)數(shù)字以后依然有序，如下圖所示：

這個函數(shù)看起來非常簡單，但你可能不知道，它在分布式系統(tǒng)中也有重要的用途。

假設(shè)現(xiàn)在你有10個Redis的單節(jié)點用來做分布式緩存。因為某種原因，你不能做集群。當(dāng)你要搜索一個數(shù)據(jù)的時候，你要先確定這個數(shù)據(jù)在不在Redis中。如果在，就直接從Redis中讀取數(shù)據(jù)；如果不在，就先去數(shù)據(jù)庫里面讀取，然后緩存到Redis中。

因為數(shù)據(jù)量很大，你不能把同一份數(shù)據(jù)同時存在10個Redis節(jié)點里面，因此你需要設(shè)計一個算法，不同的數(shù)據(jù)存放在不同的Redis節(jié)點中。

當(dāng)你要查詢數(shù)據(jù)的時候，你能根據(jù)這個算法查詢到數(shù)據(jù)（如果在緩存中）應(yīng)該存放在哪個Redis中。

稍微有一點分布式系統(tǒng)設(shè)計經(jīng)驗的同學(xué)肯定會想到，這個簡單啊，10個Redis節(jié)點編號0-9.對key計算Hash值，這個哈希值是32位的十六進制數(shù)，可以轉(zhuǎn)換成十進制以后對10求余數(shù)，余數(shù)是多少，就放到對應(yīng)的節(jié)點里面。

這樣一來，只要來了一個新的數(shù)據(jù)，你只需要去余數(shù)對應(yīng)的Redis中判斷它有沒有緩存就可以了。

但問題來了，如果你開始使用這個方法，Redis中已經(jīng)有數(shù)據(jù)了，那么你的Redis節(jié)點數(shù)就不能變了。一旦你增加或者減少1個節(jié)點，所有余數(shù)全部變了，新來的數(shù)據(jù)找到的Redis節(jié)點肯定是錯的。例如key的Hash值原來除以10，余數(shù)是2，現(xiàn)在除以9，余數(shù)是1.那本來你應(yīng)該去2號Redis找緩存，現(xiàn)在卻跑到1號Redis找緩存，那一定找不到。

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

假設(shè)現(xiàn)在你的期望是250萬，而正好有個房子賣250萬，因此你可以買它。

假設(shè)現(xiàn)在你的期望是470萬，那么你唯一的選擇是500萬的房子。

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

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

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

當(dāng)備選項發(fā)生改變的時候，只有你目標(biāo)選項附近的房子受到了影響。而小于你候選項的房子和貴的多的房子的變動，對你沒有任何影響。

你注意到了嗎，這個場景跟我們分布式緩存增減Redis節(jié)點的場景非常像。我們原來有10臺Redis，現(xiàn)在新增了一臺，變成11臺了。那么只有一臺Redis的部分緩存會遷移到這個新增的Redis中。而其它9臺Redis的緩存不需要做任何改變。

同理，當(dāng)我們刪除一臺Redis節(jié)點時，這個被刪除的節(jié)點里面的數(shù)據(jù)，只需要同步到它旁邊的另一臺Redis節(jié)點中就可以了。另外8個Redis節(jié)點不需要做任何修改?。ㄒ部梢圆煌剑挥幸恍〔糠謐ey會因為刪除這個節(jié)點導(dǎo)致找不到數(shù)據(jù)，而重新讀數(shù)據(jù)庫。80%的緩存不會受到任何影響。）

這就是一致性Hash的算法。

我來簡單描述一下這個算法的實現(xiàn)過程。首先，我們使用redis.Redis(不同redis的連接參數(shù))創(chuàng)建10個連接對象。然后把每個連接對象和一個Hash值創(chuàng)建映射，如下圖所示：

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

現(xiàn)在，來了一條新的緩存查詢需求，我們計算key對應(yīng)的Hash值，然后使用bisect.bisect_left()到列表中去尋找它對應(yīng)的Redis節(jié)點的Hash值的索引。如果返回的索引等于列表的長度，那么讓索引等于0. 找到索引以后，拿到對應(yīng)的Redis節(jié)點的Hash，最后再用這個Hash去找到對應(yīng)的Redis節(jié)點，簡化代碼如下：

`

如果新增或者刪除了Redis節(jié)點，那么只需要更新node_map和cycle?就可以了。只會發(fā)生很小的數(shù)據(jù)遷移，對絕大部分的緩存都不會造成任何影響。例如我現(xiàn)在把第1個Redis鏈接對象?對應(yīng)的Hash：fbef6b15be1abe9edc8f6aaac6a86357從node_map和cycle中刪除。再進行查詢，會發(fā)現(xiàn)依然找到的是編號為6的Redis節(jié)點。

一致性Hash在分布式系統(tǒng)中有廣泛的應(yīng)用。但你可能想不到，它的核心原理就是二分搜索里面的bisect_left。

當(dāng)然，上面只是簡化算法。一致性Hash的完整算法還涉及到虛擬節(jié)點和避免數(shù)據(jù)傾斜的算法。如果大家有興趣的話，我也可以寫一篇文章，完整解釋它的算法實現(xiàn)。