不同于應(yīng)用服務(wù)器的伸縮性設(shè)計(jì)撮奏，分布式緩存集群的伸縮性不能使用簡單的負(fù)載均衡手段來實(shí)現(xiàn)。
和所有服務(wù)器都部署相同應(yīng)用的應(yīng)用服務(wù)器集群不同弯菊，分布式緩存服務(wù)器集群中不同服務(wù)器中緩存的數(shù)據(jù)各不相同纵势，緩存訪問請(qǐng)求不可以在緩存服務(wù)器集群中的任意一臺(tái)處理踱阿，必須先找到緩存有需要數(shù)據(jù)的服務(wù)器，然后才能訪問钦铁。這個(gè)特點(diǎn)會(huì)嚴(yán)重制約分布式緩存集群的伸縮性設(shè)計(jì)软舌，因?yàn)樾律暇€的緩存服務(wù)器沒有緩存任何數(shù)據(jù)，而已下線的緩存服務(wù)器還緩存這網(wǎng)站的許多熱點(diǎn)數(shù)據(jù)牛曹。
必須讓新上線的緩存服務(wù)器對(duì)整個(gè)分布式緩存集群影響最小佛点，也就是說新加入緩存服務(wù)器后應(yīng)使整個(gè)緩存服務(wù)器集群中已經(jīng)緩存的數(shù)據(jù)盡可能還被訪問到。
Memcached 分布式緩存訪問模型
應(yīng)用程序通過 Memcached 客戶端訪問 Memcached 的服務(wù)器集群黎比。Memcached 客戶端主要由 API超营、路由算法、服務(wù)器集群列表和通信模塊組成阅虫。
路由算法會(huì)根據(jù)緩存數(shù)據(jù)的 KEY演闭，計(jì)算出應(yīng)該把數(shù)據(jù)寫入到哪一臺(tái)服務(wù)器（寫入緩存）或從哪一臺(tái)服務(wù)器讀取數(shù)據(jù)（讀取緩存）。
一個(gè)典型的緩存寫操作颓帝，如圖所示米碰。應(yīng)用程序輸入需要寫緩存的數(shù)據(jù) <'BEIJING',DATA> ，API 將 KEY（'BEIJING'）輸入到路由算法模塊购城。然后路由算法會(huì)根據(jù) KEY 和 Memcached 集群服務(wù)器列表計(jì)算得到一臺(tái)服務(wù)器編號(hào)（Node 1）吕座，這樣就可以得到這臺(tái)服務(wù)器的 IP 地址與端口。然后 Memcached API 調(diào)用通信模塊與編號(hào)為 Node 1 的服務(wù)器通信瘪板，把數(shù)據(jù) <'BEIJING',DATA> 寫入這臺(tái)服務(wù)器吴趴。這樣就完成了一次分布式緩存寫操作。
讀緩存的過程與寫類似篷帅，因?yàn)槎际褂猛瑯拥穆酚伤惴ê头?wù)器列表史侣，所以只要應(yīng)用程序提供相同的 KEY，那么 Memcached 客戶端就總是會(huì)訪問相同的服務(wù)器來讀取數(shù)據(jù)魏身。因此只要服務(wù)器還緩存著數(shù)據(jù)惊橱，就能保證緩存被命中。
分布式緩存集群的伸縮性挑戰(zhàn)
對(duì)于服務(wù)器集群的管理箭昵，路由算法和負(fù)載均衡算法一樣税朴，決定訪問集群中的哪臺(tái)服務(wù)器。
簡單的路由算法可使用余數(shù) Hash：用服務(wù)器數(shù)除緩存數(shù)據(jù) KEY 的 Hash 值家制，求得的余數(shù)即為服務(wù)器列表的下標(biāo)正林。因?yàn)?Hash 值的隨機(jī)性，所以余數(shù) Hash 可以保證緩存數(shù)據(jù)在整個(gè) Memcached 服務(wù)器集群中比較均衡地分布颤殴。對(duì)余數(shù) Hash 路由算法稍加改進(jìn)觅廓，就可以實(shí)現(xiàn)和負(fù)載均衡算法中加權(quán)負(fù)載均衡一樣的加權(quán)路由。事實(shí)上涵但，如果不需要考慮緩存服務(wù)器集群伸縮性杈绸，余數(shù) Hash 幾乎可以滿足絕大多數(shù)的緩存路由需求帖蔓。
但是，當(dāng)分布式緩存服務(wù)器集群需要擴(kuò)容時(shí)瞳脓，事情就棘手咯塑娇。假設(shè)把目前已有的 3 臺(tái)緩存服務(wù)器擴(kuò)容為 4 臺(tái)。更改服務(wù)器列表后劫侧，仍然使用余數(shù) Hash 算法埋酬，會(huì)導(dǎo)致緩存不命中，大約有 75%（3/4）被緩存的數(shù)據(jù)不命中烧栋。隨著服務(wù)器集群規(guī)模的增大写妥，這個(gè)比例呈線性上升。當(dāng)在 N 臺(tái)服務(wù)器集群中加入一臺(tái)新服務(wù)器時(shí)审姓，不能命中的概率為 N/(N+1)耳标。如在 100 臺(tái)中加入一臺(tái)，不能命中的概率為 99%邑跪。
這個(gè)結(jié)果顯然不能接受。網(wǎng)站的大部分業(yè)務(wù)的讀操作請(qǐng)求呼猪，實(shí)際上都是通過緩存獲取的画畅，只有少量的讀操作請(qǐng)求會(huì)訪問數(shù)據(jù)庫，因此數(shù)據(jù)庫的負(fù)載能力是以有緩存的前提而設(shè)計(jì)的宋距。當(dāng)大部分緩存的數(shù)據(jù)因?yàn)榉?wù)器擴(kuò)容而不能正確讀取時(shí)轴踱，這些訪問數(shù)據(jù)的壓力就都落在了數(shù)據(jù)庫身上，這將大大超出數(shù)據(jù)庫的負(fù)載能力谚赎，甚至?xí)?dǎo)致數(shù)據(jù)庫宕機(jī)淫僻。
一種方法是：在網(wǎng)站訪問量最少的時(shí)候再擴(kuò)容，這時(shí)候?qū)?shù)據(jù)庫的負(fù)載壓力最小壶唤。然后通過模擬請(qǐng)求來逐步預(yù)熱緩存雳灵，使得緩存服務(wù)器中的數(shù)據(jù)可以重新分布。但這種方案對(duì)業(yè)務(wù)場景有要求闸盔，而且還需要技術(shù)團(tuán)隊(duì)通宵加班（網(wǎng)站訪問低谷通常是在半夜）悯辙。看來好像不是個(gè)好主意迎吵！
一致性 Hash 算法
一致性 Hash 算法通過一個(gè)叫一致性 Hash 環(huán)的數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn) KEY 到緩存服務(wù)器的 Hash 映射：
先構(gòu)造一個(gè)長度為 0 ~ 2 的 32 次方的整數(shù)環(huán)（一致性 Hash 環(huán)）躲撰，根據(jù)節(jié)點(diǎn)名稱的 Hash 值（范圍在 0 ~ 2 的 32 次方），把緩存服務(wù)器節(jié)點(diǎn)放置在這個(gè) Hash 環(huán)上击费。然后根據(jù)需要緩存數(shù)據(jù)的 KEY 值計(jì)算出 Hash 值（范圍在 0 ~ 2 的 32 次方）拢蛋，最后再在 Hash 環(huán)上順時(shí)針查找距離這個(gè) KEY 的 Hash 值最近的緩存服務(wù)器節(jié)點(diǎn)，完成 KEY 到服務(wù)器的 Hash 映射查找蔫巩。
當(dāng)緩存服務(wù)器需要擴(kuò)容時(shí)谆棱，只需要將新加入的節(jié)點(diǎn)名稱（比如 Node 3）的 Hash 值放入環(huán)中快压，因?yàn)?KEY 是順時(shí)針查找距離最近的節(jié)點(diǎn)，所以新加入的節(jié)點(diǎn)只會(huì)影響整個(gè)環(huán)中的一小段础锐。
加入新節(jié)點(diǎn) Node 3 后嗓节，原來的大部分的 KEY 還能繼續(xù)使用原來的節(jié)點(diǎn)，這樣就能保證大部分被緩存的數(shù)據(jù)還能被命中皆警。3 臺(tái)服務(wù)器擴(kuò)容至 4 臺(tái)服務(wù)器拦宣，可以繼續(xù)命中原有緩存數(shù)據(jù)的概率為 75%，而且隨著集群規(guī)模越大信姓，繼續(xù)命中原有緩存數(shù)據(jù)的概率也逐漸增大鸵隧，100 臺(tái)服務(wù)器集群增加一臺(tái)服務(wù)器，繼續(xù)命中原有緩存數(shù)據(jù)的概率為 99%意推。雖然仍有小部分?jǐn)?shù)據(jù)不能被讀到豆瘫，但是這個(gè)比例足夠小，通過訪問數(shù)據(jù)庫獲取也不會(huì)造成致命的負(fù)載壓力菊值。
一致性 Hash 環(huán)通常使用二叉查找樹實(shí)現(xiàn)外驱，樹最右邊的葉子節(jié)點(diǎn)和最左邊的葉子節(jié)點(diǎn)是相連接，構(gòu)成環(huán)腻窒。Hash 查找的過程是在樹中查找不小于查找數(shù)的最小數(shù)值昵宇。
一致性 Hash 環(huán)有一個(gè)缺陷：比如上例，新加入的節(jié)點(diǎn) NODE 3 只影響了原來的節(jié)點(diǎn) NODE 1儿子。這意味著 NODE 0 和 NODE 2 緩存的數(shù)據(jù)量和負(fù)載量是 NODE 1 和 NODE 3 的兩倍瓦哎。如果這 4 臺(tái)服務(wù)器性能相同，那么我們自然希望這些服務(wù)器緩存的數(shù)據(jù)量和負(fù)載量分布是均衡的柔逼。
計(jì)算機(jī)的任何問題都可以通過增加一個(gè)虛擬層來解決
將每一臺(tái)物理緩存服務(wù)器虛擬為一組虛擬緩存服務(wù)器蒋譬，這樣就可以將虛擬服務(wù)器的 Hash 值放置在 Hash 環(huán)上。KEY 會(huì)先在環(huán)上找出虛擬服務(wù)器節(jié)點(diǎn)愉适，然后再得到物理服務(wù)器的信息犯助。
這樣新加入的物理服務(wù)器節(jié)點(diǎn)時(shí)，是將一組虛擬節(jié)點(diǎn)加入環(huán)中维咸，如果虛擬節(jié)點(diǎn)數(shù)目足夠多也切，這組虛擬節(jié)點(diǎn)將會(huì)影響同樣多數(shù)目的已經(jīng)在環(huán)上存在的虛擬節(jié)點(diǎn)，這些已經(jīng)存在的虛擬節(jié)點(diǎn)又對(duì)應(yīng)不同的物理節(jié)點(diǎn)腰湾。最終結(jié)果是：新加入一臺(tái)緩存服務(wù)器雷恃，將會(huì)較為均勻地影響原來集群中已經(jīng)存在的所有服務(wù)器，也就是說分?jǐn)傇芯彺娣?wù)器集群中所有服務(wù)器的一小部分負(fù)載费坊。
在圖中倒槐，新加入節(jié)點(diǎn) NODE 3 對(duì)應(yīng)的一組虛擬節(jié)點(diǎn)為 V30，V31附井，V32讨越，加入到一致性 Hash 環(huán)上后两残，影響 V01，V12把跨，V22 三個(gè)虛擬節(jié)點(diǎn)人弓，而這三個(gè)虛擬節(jié)點(diǎn)分別對(duì)應(yīng) NODE 0，NODE 1着逐，NODE 2 三個(gè)物理節(jié)點(diǎn)崔赌。最終 Memcached 集群中加入一個(gè)節(jié)點(diǎn)，但是同時(shí)影響到集群中已存在的三個(gè)物理節(jié)點(diǎn)耸别，理想情況下健芭，每個(gè)物理節(jié)點(diǎn)受影響的數(shù)據(jù)量（還在緩存中，但是不能被訪問到的數(shù)據(jù)）為其節(jié)點(diǎn)緩存數(shù)據(jù)量的 1/4（X/(N+X)秀姐，N 為原有物理節(jié)點(diǎn)數(shù)慈迈，X 為新加入物理節(jié)點(diǎn)數(shù)），也就是集群中已經(jīng)被緩存的數(shù)據(jù)有 75% 可以被繼續(xù)命中省有，和未使用虛擬節(jié)點(diǎn)的一致性 Hash 算法結(jié)果相同痒留。
顯然，每個(gè)物理節(jié)點(diǎn)對(duì)應(yīng)的虛擬節(jié)點(diǎn)越多蠢沿，那么各個(gè)物理節(jié)點(diǎn)之間的負(fù)載就會(huì)越均衡狭瞎，新加入的物理服務(wù)器對(duì)原有的物理服務(wù)器的影響越保持一致（這就是一致性 Hash 這個(gè)名稱的由來）。虛擬節(jié)點(diǎn)數(shù)太多會(huì)影響性能搏予，太少會(huì)導(dǎo)致負(fù)載不均衡，一般說來弧轧，經(jīng)驗(yàn)值是 150雪侥，根據(jù)集群規(guī)模和負(fù)載均衡的精度需求，具體情況具體分析精绎。
