同步發表于：http://blog.lanjingdejia.com/articles/2018/08/05/1533440489704.html
Redis有沒有使用一緻性哈希？
很多人包括之前的我在内，一直認為reids叢集的資料存儲用的是一緻性hash算法，後來讀了亞馬遜的《Dynamo: Amazon’s Highly Available Key-value Store》論文，感覺Redis不至于實作的這麼複雜，帶着一些疑問，翻了redis官網和用戶端代碼，發現Redis并沒有使用一緻性hash算法。
Redis叢集使用的是一種哈希槽(hash slot)的方式，将key通過hash後存儲在16384個槽中，然後将這些槽平均配置設定給叢集中的各個節點，舉個例子，比如一個叢集有4個節點，那麼配置設定可以是這樣的：
0~5000 NodeA
5001~10000 NodeB
10001 ~ 15000 NodeC
15001 ~ 16384 NodeD
這樣當叢集中節點的數量發生變化時，隻需要調整槽的配置設定就可以了：
當有節點加入時，每個節點把自己的槽分一些給新節點。
當有節點退出時，将退出節點的槽配置設定給其他節點。
仔細想想，其實這定沒有違背一緻性hash定義中當有一個節點發生變化時，隻影響K/N個key的緩存這個定義。
anyway，不管一緻性hash也好，hash slot也好，不要執着于Redis用沒用一緻性hash，搞清楚每一種解決問題的算法的思想才是最重要的。
一緻性hash的局限和改進：cache or storage
如果你隻是用來做緩存，那自然沒問題，一緻性hash天生就是來做這個的。當hash環中添加或者移除節點時，平均隻有K/N個key受到影響，因為是緩存系統，緩存無法命中時，再從資料源重新加載一遍就是了。
可是，如果我們要做的不僅僅是一個緩存系統呢？如果我們要做的是一個存儲系統呢？K/N個key受到影響時，你本身就是資料源了，你還能從哪裡加載資料呢？那大概直接就是事故了。
為了解決一緻性hash的存儲問題，方法大概有兩種：
1. hash環上的replication
正如Dynamo論文圖中所示，AB區間内的key，不再隻由節點B存儲，而是擴充到三個節點，B、C、D都存儲，這樣當B節點故障時，AB之間的key仍然可以從C、D節點中得到，然後把A~B區間的key再複制到E節點中一份，保證每份資料都有兩個replication，是以說，大多數事情都是殊途同歸的，為了解決節點故障導緻的可用性問題，不管怎樣，RAID也好，ZK也好，GFS也好，Mysql主從複制也好，說到底都是通過資料的備援備份（replication）來做的，一個節點可能故障，那我就多弄幾個候補的，如果遇到極端情況，所有候補節點同時挂了，那算我倒黴，我認了。畢竟再厲害的容災，你能跨機器、跨機架、跨機房、跨城市、跨國家，可是你能誇星球嗎？來個小行星撞地球，啥都沒意義了，所有的東西都有個限度，都需要權衡和考慮成本效益的
整個論文讀完，發現Dynamo這種把replication做到hash環上的方法雖然解決了可用性的問題，考慮到虛拟節點的存在，這種方法其實是大大增加了系統的複雜度的。
2. 另一種replication
這種replication比上面那種要清晰不少，這種也是redis采用的：
如上圖所示，hash環（redis使用的是hash槽）上的節點都當做是master節點，每個master節點配備若幹個slave節點，當master節點故障時，其中一個slave節點會被選舉為新的master節點，選舉的過程是由Redis的sentinel元件（你可以認為跟zookeeper做的事情差不多）實作的。雖然多了一個額外的sentinel元件，但是整個結構上清晰了許多。而且，Redis叢集采用hash槽的概念替換了一緻性hash的虛拟節點，hash槽的配置設定可以保證每個節點的負載是均衡的。
無論哪種實作方式，slave節點都是可以提供讀服務的，也就是讀寫分離。其實，在redis的适用場景中，大部分都是讀多寫少的。
Redis叢集中節點變動的三種情況
1. 向叢集中添加一個節點
當然這個節點還附帶着它的slave節點，這裡暫且略過，向叢集中添加節點時，先把其他節點“管轄”的槽位都拉一部分過來到自己的節點上，使各個節點的負載接近平衡，然後更新叢集上所有節點中記錄的各個節點和slot的映射關系，新的請求進來後，剛才加入的節點就可以正常工作了。
2. 手動從叢集中去除一個節點
當你覺得叢集的使用率比較低，向去除一個節點時，redis會先把要去除的節點管轄的slot平均配置設定到其他節點上，分完之後，更新叢集中各個節點中存儲的節點和slot的映射關系，最後删除這個節點及其slave節點就可以了。
3. 叢集中的一個節點因為故障當機了
對于這種突發情況，是沒有時間讓我們預先将節點的slot轉移到其他節點的，這種情況就靠我們上面提到的master-slave機制應對了，master挂了，slave會頂替它成為新的master，并不影響整個叢集的可用性。當然，如果一個節點的master和它所有的slave同時挂了，那就隻能自認倒黴了。
兩種路由方式
現在思考一下，你用用戶端向叢集發起請求，get/set一個key的時候，整個流程是怎麼樣運轉的呢？你是怎樣找到應該存放這個key的slot的呢？又是怎樣找到“管轄”這個slot的節點的呢？
下面以get為例，描述這個步驟：
1. 将key % 16384找到slot的編号
2. 找到管轄這個slot的節點
這一步有兩種實作方式：
a. 用戶端實作
你的redis cluster client會緩存叢集中各個節點與slot的映射關系，當因為節點變動引起映射關系的變動時，client會在發現後及時擷取新的映射關系。這樣用戶端幫你找到“管轄”這個slot的節點後，直接向這個節點發起get請求，節點将結果傳回，流程就結束了。
b. 服務端實作
你的redis cluster client并不會緩存任何節點和slot的映射關系，而是直接将請求發送到随便一個節點，因為每個節點中都存儲着各個節點和slot的映射關系，那麼接收到請求的節點會查詢該slot的管轄節點是誰，如果不是自己的話，該節點會将請求轉發到正确的節點上，然後該節點将資料傳回給用戶端。
兩種方式各有利弊吧，用戶端實作的方式需要用戶端維護節點和slot的映射關系，服務端實作的方式需要服務端多做一次轉發。redis的java用戶端JedisCluster倒是兩種方式都實作了，都有實作類，預設使用的是“用戶端實作”的方式。
有很多地方沒提到，比如redis主從複制的最終一緻性，sentinel的工作流程等，redis叢集中的事務以及包含多個key的請求時的問題等等，大家有興趣可以去redis的官網看看，文檔很詳細。