相關(guān)歷史文章（閱讀本文之前，您可能需要先看下之前的系列 ）

色談Java序列化：女孩子慎入 - 第280篇

煩不煩，別再問(wèn)我時(shí)間復(fù)雜度了：這次不色，女孩子進(jìn)來(lái)吧 - 第281篇

雙向鏈表，比西天還遠(yuǎn)？- 第282篇

面試不再怕，讓LRU無(wú)處可逃 - 第283篇

愛(ài)我，就要懂我 – Memcached- 第284篇

內(nèi)存管理，難于上青天？- memcached - 第285篇

你懂她，可惜你不懂我「LRU 」- Memcached- 第286篇

悟纖：師傅，這個(gè)不是在之前就說(shuō)過(guò)了，這個(gè)我懂。

師傅：恩赫，你懂？那我問(wèn)你下memcached分布式使用的是什么算法？

悟纖：？？？難道不是hash一下就可以了嘛。

師傅：要是這么簡(jiǎn)單就能理解了，我還會(huì)在嘮叨一遍嘛。

悟纖：那徒兒洗耳恭聽(tīng)。

一、Memcached分布式是如何實(shí)現(xiàn)的

memcached本身是一個(gè)非常輕量級(jí)的服務(wù)，不支持主輔同步，也沒(méi)有集群的概念。但為了可擴(kuò)展性，memcached服務(wù)器端和 memcached 客戶端結(jié)合起來(lái)可以構(gòu)成一個(gè)分布式系統(tǒng)。

在memcached分布式系統(tǒng)中，各個(gè) memcached 節(jié)點(diǎn)之間無(wú)須通信，所以擴(kuò)展性非常好。

->Memcached的分布式特點(diǎn)：

?1>: 服務(wù)器端不關(guān)心分布式：服務(wù)端的各個(gè)Memcached都是獨(dú)立部署，之間不相互通信，這樣服務(wù)端部署多個(gè)Memcached就很簡(jiǎn)單。

?2>: 依靠客戶端來(lái)實(shí)現(xiàn)分布式：最簡(jiǎn)單的方式就是客戶端擁有服務(wù)端所有連接地址，客戶端通過(guò)key的hash值獲取到對(duì)應(yīng)的Memcached。

二、分布式算法

當(dāng)向memcached集群存入/取出key/value時(shí)，memcached客戶端程序根據(jù)一定的算法計(jì)算存入哪臺(tái)服務(wù)器，然后再把key/value值存到此服務(wù)器中。也就是說(shuō)，存取數(shù)據(jù)分二步走，第一步，選擇服務(wù)器，第二步存取數(shù)據(jù)。

常用的算法有兩種: 余數(shù)計(jì)算分散法 和 一致性Hash算法。

2.1 余數(shù)計(jì)算分散法

標(biāo)準(zhǔn)的memcached分布式算法

CRC($key)%N

BTW：CRC是一循環(huán)冗余算法，N：memcached服務(wù)器個(gè)數(shù)。

客戶端首先根據(jù)key來(lái)計(jì)算CRC , 然后結(jié)果對(duì)服務(wù)器取模得到memcached服務(wù)器節(jié)點(diǎn)。

這種算法取余計(jì)算簡(jiǎn)單，分散效果好，但是缺點(diǎn)是如果某一臺(tái)機(jī)器宕機(jī)，那么應(yīng)該落在該機(jī)器的請(qǐng)求就無(wú)法得到正確的處理，這時(shí)需要將當(dāng)?shù)舻姆?wù)器從算法從去除，此時(shí)候會(huì)有 (N-1) 的服務(wù)器的緩存數(shù)據(jù)需要重新進(jìn)行計(jì)算；如果新增一臺(tái)機(jī)器，會(huì)有 (N+1)的服務(wù)器的緩存數(shù)據(jù)需要進(jìn)行重新計(jì)算。對(duì)于系統(tǒng)而言，這通常是不可接受的顛簸（因?yàn)檫@意味著大量緩存的失效或者數(shù)據(jù)需要轉(zhuǎn)移）。

2.2 一致性hash算法

將server的hash值分配至0~2^32的圓環(huán)上, 用同樣的方法求出存儲(chǔ)數(shù)值鍵的hash值并映射到圓上. 然后從數(shù)據(jù)映射到的位置開(kāi)始順時(shí)針查找, 將數(shù)據(jù)存放至找到的第一臺(tái)服務(wù)器上。如果超過(guò)0~2^32還找不到, 則將數(shù)據(jù)存放至第一臺(tái)服務(wù)器。

2.2.1 算法過(guò)程

（1）先構(gòu)造一個(gè)長(zhǎng)度為0~2^32（2的32次冪）個(gè)的整數(shù)環(huán)（又稱：一致性Hash環(huán)），根據(jù)節(jié)點(diǎn)名稱的Hash值將緩存服務(wù)器節(jié)點(diǎn)放置在這個(gè)Hash環(huán)中，如上圖中的node1，node2等；

（2）根據(jù)需要緩存的數(shù)據(jù)的KEY值計(jì)算得到其Hash值，如上圖中右半部分的“鍵”，計(jì)算其Hash值后順時(shí)針離node2近；

（3）在Hash環(huán)上順時(shí)針查找距離這個(gè)KEY的Hash值最近的緩存服務(wù)器節(jié)點(diǎn)，完成KEY到服務(wù)器的Hash映射查找，如上圖中離右邊這個(gè)鍵的Hash值最近的順時(shí)針?lè)较虻姆?wù)器節(jié)點(diǎn)是node2，因此這個(gè)KEY會(huì)到node2中讀取數(shù)據(jù)；

2.2.2 添加節(jié)點(diǎn)

當(dāng)緩存服務(wù)器集群需要擴(kuò)容的時(shí)候，只需要將新加入的節(jié)點(diǎn)名稱（如node5）的Hash值放入一致性Hash環(huán)中，由于KEY總是順時(shí)針查找距離其最近的節(jié)點(diǎn)，因此新加入的節(jié)點(diǎn)只影響整個(gè)環(huán)中的一部分。如下圖中所示，添加node5后，只影響右邊逆時(shí)針?lè)较虻娜齻€(gè)Key/Value對(duì)數(shù)據(jù)，只占整個(gè)Hash環(huán)中的一小部分。

BTW：刪節(jié)節(jié)點(diǎn)或者服務(wù)器down機(jī)，影響的也只是順時(shí)針的下一個(gè)節(jié)點(diǎn)。

2.2.3 算法優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：動(dòng)態(tài)的增刪節(jié)點(diǎn)，服務(wù)器down機(jī)，影響的只是順時(shí)針的下一個(gè)節(jié)點(diǎn)

缺點(diǎn)：當(dāng)服務(wù)器進(jìn)行hash后值較為接近會(huì)導(dǎo)致在圓環(huán)上分布不均勻，進(jìn)而導(dǎo)致key的分布、服務(wù)器的壓力不均勻。若中間某一權(quán)重較大的serverdown機(jī)，命中率下降明顯；

2.2.4 算法對(duì)比

我們可以與之前的普通余數(shù)Hash作對(duì)比：采用一致性Hash算法時(shí)，當(dāng)3臺(tái)服務(wù)器擴(kuò)容到4臺(tái)時(shí)，可以繼續(xù)命中原有緩存數(shù)據(jù)的概率為75%，遠(yuǎn)高于普通余數(shù)Hash的25%，而且隨著集群規(guī)模越大，繼續(xù)命中原有緩存數(shù)據(jù)的概率也會(huì)隨之增大。當(dāng)100臺(tái)服務(wù)器增加1臺(tái)時(shí)，繼續(xù)命中的概率是99%。雖然，仍有小部分?jǐn)?shù)據(jù)緩存在服務(wù)器中無(wú)法被讀取到，但是這個(gè)比例足夠小，通過(guò)訪問(wèn)數(shù)據(jù)庫(kù)也不會(huì)對(duì)數(shù)據(jù)庫(kù)造成致命的負(fù)載壓力。

2.3 優(yōu)化一致性hash算法（虛擬節(jié)點(diǎn)）

服務(wù)器的映射地點(diǎn)的分布非常的不均勻, 導(dǎo)致數(shù)據(jù)訪問(wèn)傾斜, 大量的key被映射到同一臺(tái)服務(wù)器上，這時(shí)候需要在一致性哈希算法的基礎(chǔ)上引入虛擬節(jié)點(diǎn)：

引入虛擬節(jié)點(diǎn)的思想，解決一致性hash算法分布不均導(dǎo)致負(fù)載不均的問(wèn)題。一個(gè)真實(shí)節(jié)點(diǎn)對(duì)應(yīng)若干個(gè)虛擬節(jié)點(diǎn)，當(dāng)key被映射到虛擬節(jié)點(diǎn)上時(shí)，則被認(rèn)為映射到虛擬節(jié)點(diǎn)所對(duì)應(yīng)的真實(shí)節(jié)點(diǎn)上。

BTW：引入虛擬節(jié)點(diǎn)的思想，每個(gè)物理節(jié)點(diǎn)對(duì)應(yīng)圓環(huán)上若干個(gè)虛擬節(jié)點(diǎn)（比如200~300個(gè)），當(dāng)key hash到虛擬節(jié)點(diǎn)，就會(huì)存儲(chǔ)到實(shí)際的物理節(jié)點(diǎn)上，有效的實(shí)現(xiàn)了負(fù)載均衡。

三、悟纖小結(jié)

師傅：徒兒，聽(tīng)明白沒(méi)有，來(lái)，你給大家來(lái)個(gè)總結(jié)吧。
悟纖：好的，師傅，您休息下，喝點(diǎn)水。

總結(jié)：

（1）Memcached的分布式實(shí)現(xiàn)原理：服務(wù)端之間互不通信，分布式的實(shí)現(xiàn)是通過(guò)客戶端使用一致性Hash算法進(jìn)行實(shí)現(xiàn)的。
（2）分布式算法：余數(shù)計(jì)算分散法和一致性hash算法。
（3）余數(shù)分散法存在的問(wèn)題：當(dāng)節(jié)點(diǎn)變動(dòng)的時(shí)候，緩存數(shù)據(jù)需要重新計(jì)算，命中率就會(huì)受到很大影響。
（4）一致性hash算法存在問(wèn)題：數(shù)據(jù)分布不均勻，負(fù)載不均衡。
（5）優(yōu)化的一致hash算法原理：加入虛擬節(jié)點(diǎn)，物理節(jié)點(diǎn)映射到若干個(gè)虛擬節(jié)點(diǎn)上，從而使得數(shù)據(jù)分布均衡分布在虛擬節(jié)點(diǎn)上，以此來(lái)實(shí)現(xiàn)負(fù)載均衡。

我就是我，是顏色不一樣的煙火。 我就是我，是與眾不同的小蘋(píng)果。學(xué)院中有Spring Boot相關(guān)的課程：
à悟空學(xué)院：https://t.cn/Rg3fKJD
SpringBoot視頻：http://t.cn/A6ZagYTi
Spring Cloud視頻：http://t.cn/A6ZagxSR
SpringBoot Shiro視頻：http://t.cn/A6Zag7IV
SpringBoot交流平臺(tái)：https://t.cn/R3QDhU0
SpringData和JPA視頻：http://t.cn/A6Zad1OH
SpringSecurity5.0視頻：http://t.cn/A6ZadMBe
Sharding-JDBC分庫(kù)分表實(shí)戰(zhàn)：http://t.cn/A6ZarrqS
分布式事務(wù)解決方案「手寫(xiě)代碼」：http://t.cn/A6ZaBnIr

總結(jié)

以上是生活随笔為你收集整理的memcached客户端_分布式算法真是吊炸天 – memcached - 第287篇的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。