一致性hash
一般來說，基于hash算法的分片中进每，算法內(nèi)部是把記錄分片到一種叫做“bucket”（hash桶）的內(nèi)部算法結(jié)構(gòu)中的汹粤，然后hash桶與實(shí)際的分片節(jié)點(diǎn)一一對(duì)應(yīng)，從此實(shí)現(xiàn)了分片田晚、路由的功能嘱兼。
在這種一般結(jié)構(gòu)中，在需要增加分片數(shù)量來橫向擴(kuò)容時(shí)贤徒，由于分片節(jié)點(diǎn)和hash桶之間的一一對(duì)應(yīng)芹壕，導(dǎo)致算法根據(jù)原先的hash桶個(gè)數(shù)的進(jìn)行的路由失效，需要根據(jù)新的hash桶數(shù)目做數(shù)據(jù)的再平衡才能再次服務(wù)接奈。
一般hash算法中踢涌，這個(gè)數(shù)據(jù)再平衡本質(zhì)就是更新hash算法的參數(shù)（hash桶數(shù)目）之后，再拿所有現(xiàn)存記錄重新過一遍調(diào)整后hash算法序宦，從而確定新的分片睁壁。
因此，由于數(shù)據(jù)再平衡工作量巨大互捌，而且再平衡期間基本阻塞了所有的訪問與操作潘明，一般hash算法的直接分片很難做橫向擴(kuò)容。
為了實(shí)現(xiàn)橫向擴(kuò)容秕噪，有一種解決思路就是“過度分片”钳降。該規(guī)則在算法層面解除了hash桶與分片節(jié)點(diǎn)的一一對(duì)應(yīng)關(guān)系，從而實(shí)現(xiàn)了這種思路腌巾。這個(gè)規(guī)則獨(dú)有一個(gè)虛擬桶倍數(shù)的概念——指的是一個(gè)分片上有且僅有多少個(gè)hash桶遂填。在平常工作中，該規(guī)則與一般的hash算法分片的表現(xiàn)沒有什么差異壤躲。
在橫向擴(kuò)容的時(shí)候城菊，該規(guī)則就體現(xiàn)其優(yōu)點(diǎn)了备燃。分片節(jié)點(diǎn)的增加不會(huì)影響到算法核心的“分桶”工作碉克，因此就不需要做代價(jià)高昂的數(shù)據(jù)再平衡，而簡化為以hash桶為單位的數(shù)據(jù)遷移并齐。數(shù)據(jù)遷移也不會(huì)波及所有的既存數(shù)據(jù)漏麦，因此從阻塞數(shù)據(jù)范圍和阻塞時(shí)間長度上都得到了極大的改善。
與其他“過度分片”的做法相似更耻，該規(guī)則的橫向擴(kuò)展是存在一個(gè)設(shè)計(jì)極限的秧均。這個(gè)極限是分片節(jié)點(diǎn)數(shù)的上限，值等于“虛擬桶倍數(shù)×分片節(jié)點(diǎn)數(shù)”誉己。此外巨双，由于虛擬桶倍數(shù)與分片節(jié)點(diǎn)數(shù)都必須是正整數(shù)，而且要服從“虛擬桶倍數(shù)×分片節(jié)點(diǎn)數(shù)=設(shè)計(jì)極限”疼阔，因此在橫向擴(kuò)容的過程中，增加分片節(jié)點(diǎn)并不是一臺(tái)一臺(tái)地加上去的淘邻，而是以一種因式分解的方式增加——因此有浪費(fèi)物理計(jì)算力的可能性筹我。
