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

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

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

運(yùn)行效果如下圖所示：

Python自帶了一個(gè)二分搜索的模塊，叫做bisect，它也能實(shí)現(xiàn)二分搜索，但是它的執(zhí)行結(jié)果跟我們上面代碼的效果有點(diǎn)不同：

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)

運(yùn)行效果如下圖所示：

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

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

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

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

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

因?yàn)閿?shù)據(jù)量很大，你不能把同一份數(shù)據(jù)同時(shí)存在10個(gè)Redis節(jié)點(diǎn)里面，因此你需要設(shè)計(jì)一個(gè)算法，不同的數(shù)據(jù)存放在不同的Redis節(jié)點(diǎn)中。

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

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

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

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

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

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

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

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

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

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

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

你注意到了嗎，這個(gè)場(chǎng)景跟我們分布式緩存增減Redis節(jié)點(diǎn)的場(chǎng)景非常像。我們?cè)瓉?lái)有10臺(tái)Redis，現(xiàn)在新增了一臺(tái)，變成11臺(tái)了。那么只有一臺(tái)Redis的部分緩存會(huì)遷移到這個(gè)新增的Redis中。而其它9臺(tái)Redis的緩存不需要做任何改變。

同理，當(dāng)我們刪除一臺(tái)Redis節(jié)點(diǎn)時(shí)，這個(gè)被刪除的節(jié)點(diǎn)里面的數(shù)據(jù)，只需要同步到它旁邊的另一臺(tái)Redis節(jié)點(diǎn)中就可以了。另外8個(gè)Redis節(jié)點(diǎn)不需要做任何修改?。ㄒ部梢圆煌?，只有一小部分key會(huì)因?yàn)閯h除這個(gè)節(jié)點(diǎn)導(dǎo)致找不到數(shù)據(jù)，而重新讀數(shù)據(jù)庫(kù)。80%的緩存不會(huì)受到任何影響。）

這就是一致性Hash的算法。

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

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

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

`

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

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

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