調研比較三個解決方案
- Twemproxy Twitter 是C
- Redis ClusterRedis官方是C
- Codis 豌豆莢 否Go+C
Redis常見叢集技術
長期以來，Redis本身僅支援單執行個體，記憶體一般最多8~20GB。這無法支撐大型線上業務系統的需求。而且也造成資源的使用率過低——畢竟現在伺服器記憶體動辄100~200GB。
為解決單機承載能力不足的問題，各大網際網路企業紛紛出手，“自助式”地實作了叢集機制。在這些非官方叢集解決方案中，實體上把資料“分片”(sharding)存儲在多個Redis執行個體，一般情況下，每一“片”是一個Redis執行個體。
包括官方近期推出的Redis Cluster，Redis叢集有三種實作機制，分别介紹如下，希望對大家選型有所幫助。
1.1 用戶端分片
這種方案将分片工作放在業務程式端，程式代碼根據預先設定的路由規則，直接對多個Redis執行個體進行分布式通路。這樣的好處是，不依賴于第三方分布式中間件，實作方法和代碼都自己掌控，可随時調整，不用擔心踩到坑。
這實際上是一種靜态分片技術。Redis執行個體的增減，都得手工調整分片程式。基于此分片機制的開源産品，現在仍不多見。
這種分片機制的性能比代理式更好(少了一個中間分發環節)。但缺點是更新麻煩，對研發人員的個人依賴性強——需要有較強的程式開發能力做後盾。如果主力程式員離職，可能新的負責人，會選擇重寫一遍。
是以，這種方式下，可運維性較差。出現故障，定位和解決都得研發和運維配合着解決，故障時間變長。
這種方案，難以進行标準化運維，不太适合中小公司(除非有足夠的DevOPS)。
1.2 代理分片
這種方案，将分片工作交給專門的代理程式來做。代理程式接收到來自業務程式的資料請求，根據路由規則，将這些請求分發給正确的Redis 執行個體并傳回給業務程式。
這種機制下，一般會選用第三方代理程式(而不是自己研發)，因為後端有多個Redis執行個體，是以這類程式又稱為分布式中間件。
這樣的好處是，業務程式不用關心後端Redis執行個體，運維起來也友善。雖然會是以帶來些性能損耗，但對于Redis這種記憶體讀寫型應用，相對而言是能容忍的。
這是我們推薦的叢集實作方案。像基于該機制的開源産品Twemproxy，便是其中代表之一，應用非常廣泛。
基本架構
Twemproxy
增加Proxy層，由Proxy實作一緻性雜湊演算法(支援：KETAMA/取模/随機)
資料分片算法：
采用一緻性雜湊演算法，以KET 為例：
Redis Cluster 官方實作
關鍵點
各節點維護Key->Server的映射關系
Client可以向任意節點發起請求，節點不會轉發請求，隻是重定向Client
如果在Client第一次請求和重定向請求之間，Cluster拓撲發生改變，則第二次重定向請求将被再次重定向，直到找到正确的Server為止
資料分片算法：
Key空間被劃分為16384個區間,每個Master節點負責一部分區間。
Codis
用戶端可以連接配接到任意的codis-proxy,就和連接配接原生的Redis Server
由Zookeeper維護資料路由表和 codis-proxy 節點的元資訊
資料分片算法：
Key空間被劃分為1024個區間, 對于每個key來說, 通過以下公式确定所屬的 Slot Id : SlotId = crc32(key) % 1024
每一個 slot 都會有一個特定的 server group id 來表示這個 slot 的資料由哪個 server group 來提供
水準擴容
Twemproxy:
不支援運作時水準擴容，需要重新開機。
根據一緻性雜湊演算法進行資料重新分片。
Redis Cluster:
支援通過運作時增加Master節點來水準擴容，提升存儲容量，盡力降低命中率波動
存在節點A，需要遷出其中的部分Key區間。新增節點B，接收由節點A遷出的Key區間。
相應Key區間的請求首先還是會發送給A節點：如果請求為建立Key則直接重定向到B節點；如果請求不是建立Key且A節點存儲有對應的Key則直接作出響應，否則重定向到B節點
同時Cluster會調用實用工具redis-trib向A節點發送MIGRATE指令，把遷移區間内的所有Key原子的遷移到B節點：同時鎖住A、B節點=》在A節點删除Key=》在B節點建立Key=》解鎖
運作時動态遷移大尺寸鍵值可能造成響應時延
Codis:
支援運作時水準擴容
底層基于Codis Server特殊實作原子的資料遷移指令
主從備份
主從備份是否必須
Twemproxy:
沒有資料複制不影響可用節點頂替故障節點
故障發生時，沒有資料複制的故障節點的Key會全部丢失
Redis Cluster:
沒有主從備份的節點一旦故障，将導緻整個叢集失敗：無法寫入/讀取任何Key；無法進行資料重新分片。
Codis:
若出現故障，需要手動配置節點，進行故障轉移。
如果沒有進行故障轉移，隻故障節點負責的slots 會失敗
3.2 主從備份方案
Twemproxy本身不支援出從備份，和Redis Cluster一樣，需要引入Redis本身的主備複制功能。
可以設定1主1備或者1主多備
當Slave節點接入Cluster時，就會向配置的Master節點發送SYNC指令。斷開重連時，也會再次發送SYNC指令
此後Master将啟動背景存盤程序，同時收集所有接收到的用于修改資料集的指令，在背景程序執行完畢後，Master将傳送整個資料庫檔案到Slave，以完成一次完全同步。而Slave伺服器在接收到資料庫檔案資料之後将其存盤并加載到記憶體中。此後，Master繼續将所有已經收集到的修改指令，和新的修改指令依次傳送給Slaves，Slave将在本次執行這些資料修改指令，進而達到最終的資料同步。
Redis的資料複制是異步的，無論在Master端還是Slave端都不會阻塞。
Slave會周期性确認收到的備份資料
Twemproxy引入主備複制後的架構更新為：
開啟主備複制後的Redis Cluster的架構更新為下圖，Client可以向任意節點發起請求，無論是Master節點還是Slave節點。
故障檢測與轉移
Twemproxy
故障檢測
Twemproxy本身通過三個配置項實作：
auto_eject_hosts: truetimeout: 400server_failure_limit: 3
如果Server Pool開啟了auto_eject_hosts，則當連續server_failure_limit次通路某Server，都逾時timeout無響應，則标記該節點為故障。
故障轉移
故障節點将從Hash環上直接取下，之前儲存在該Server上的Key将丢失。
故障轉移耗時評估
假設配置：timeout=400ms, server_failure_limit=2， 則故障轉移需要耗時800ms。
Twemproxy借助其他工具
使用Twemproxy時可以引入Redis Sentinel來進行故障檢測。引入Redis Sentinel後Twemproxy的架構更新為：
每個Sentinel節點可以監控一個或多個Master節點，及其所有Slave節點
啟動Redis Sentinel
redis-sentinel /path/to/sentinel.conf，其中的配置檔案是必須的，配置檔案将會被用來存儲運作時狀态資訊。在配置檔案中隻需要指明要監視的Master節點清單。
無須為運作的每個 Sentinel 分别設監聽同一Master的其他 Sentinel 的位址， 因為 Sentinel 可以通過釋出與訂閱功能來自動發現正在監視相同主伺服器的其他 Sentinel
不必手動列出主伺服器屬下的所有從伺服器， 因為 Sentinel 可以通過詢問主伺服器來獲得所有從伺服器的資訊。
故障檢測
每個 Sentinel 以每秒鐘一次的頻率向它所知的主伺服器、從伺服器以及其他 Sentinel 執行個體發送一個 PING 指令。
如果一個執行個體(instance)距離最後一次有效回複 PING 指令的時間超過 down-after-milliseconds 選項所指定的值， 那麼這個執行個體會被 Sentinel 标記為主觀下線。
如果一個Master被标記為主觀下線， 那麼正在監視這個Master的所有 Sentinel 要以每秒一次的頻率确認主伺服器的确進入了主觀下線狀态。
如果一個主伺服器被标記為主觀下線， 并且有足夠數量的 Sentinel (至少要達到配置檔案指定的數量)在指定的時間範圍内同意這一判斷， 那麼這個主伺服器被标記為客觀下線。
當沒有足夠數量的 Sentinel 同意主伺服器已經下線， 主伺服器的客觀下線狀态就會被移除。 當主伺服器重新向 Sentinel 的 PING 指令傳回有效回複時， 主伺服器的主觀下線狀态就會被移除。
故障轉移
Redis Sentinel進行故障轉移的過程：
某Sentinel節點發現主伺服器已經進入客觀下線狀态。
該Sentinel發起選舉，試圖當選故障轉移主持節點
如果當選失敗， 那麼在設定的故障遷移逾時時間的兩倍之後， 重新嘗試當選。 如果當選成功， 那麼執行以下步驟。
選出一個Slave節點，并将它更新為Master節點
向被選中的從伺服器發送 SLAVEOF NO ONE 指令，讓它轉變為Master節點
通過釋出與訂閱功能， 将更新後的配置傳播給所有其他 Sentinel ， 其他 Sentinel 對它們自己的配置進行更新。
向已下線主伺服器的Slave節點發送 SLAVEOF 指令， 讓它們去複制新的Master節點
Redis Sentinel選擇新的Master節點進行故障轉移之後，Twemproxy無法找到新的Master節點，此時需要引入第四方工具redis-twemproxy-agent(node.js)，更新Twemproxy配置，并重新開機。
故障轉移耗時評估
每個 Sentinel 以每秒鐘發送一次PING，配置down-after-milliseconds=2s，則主觀下線耗時3s
由主觀下線升：數量的 Sentinel (至少要達到配置檔案指定的數量)在指定的時間範圍内同意這一判斷1s
Sentinel當選故障轉移主持節點：1s
選出一個Slave節點，并将它更新為Master節點,向被選中的從伺服器發送 SLAVEOF NO ONE 指令，讓它轉變為Master節點:0.5s
通過釋出與訂閱功能， 将更新後的配置傳播給所有其他 Sentinel ， 其他 Sentinel 對它們自己的配置進行更新:1s
總計耗時：6.5s
Redis Cluster
4.3.1 故障檢測
節點狀态的維護：
節點的拓撲結構是一張完全圖：對于N個節點的Cluster，每個節點都持有N-1個輸入TCP連接配接和N-1個輸出TCP連接配接。
節點資訊的維護：每秒随機選擇節點發送PING包(無論Cluster規模，PING包規模是常量)；每個節點保證在NODE_TIMEOUT/2 時間内，對于每個節點都至少發送一個PING包或者收到一個PONG包.
在節點間互相交換的PING/PONG包中有兩個字段用來發現故障節點：PFAIL(Possible Fail)和FAIL。
PFAIL狀态：
當一個節點發現某一節點在長達NODE_TIMEOUT的時間内都無法通路時，将其标記為PFAIL狀态。
任意節點都可以将其他節點标記為PFAIL狀态，無論它是Master節點還是Slave節點。
FAIL狀态：
當一個節點發現另一節點被自己标記為PFAIL狀态，并且在(NODE_TIMEOUT * FAIL_REPORT_VALIDITY_MULT)的時間範圍内，與其他節點交換的PING/PONG包中，大部分Master節點都把該節點标記為PFAIL或者FAIL狀态，則把該節點标記為FAIL狀态，并且進行廣播。
4.3.2 故障轉移
4.3.2.1 Slave選舉的時機
當某一Slave節點發現它的Master節點處于FAIL狀态時，可以發起一次Slave選舉，試圖将自己晉升為Master。一個Master節點的所有Slave節點都可以發起選舉，但最終隻有一個Slave節點會赢得選舉。Slave發起選舉的條件：
Slave的Master處于FAIL狀态
該MASTER節點存儲的Key數量>0
Slave與Master節點失去連接配接的時間小于閥值，以保證參與選舉的Slave節點的資料的新鮮度
Cluster邏輯時鐘
Config epoch：
每個Master節點啟動時都會為自己建立并維護configEpoch字段，設定初始值為0。Master會在自己的PING/PONG包中廣播自己的configEpoch字段。Redis Cluster盡力保持各個Master節點的configEpoch字段取值都不同。算法：
每當一個Master節點發現有别的Master節點的configEpoch字段與自己相同時
并且自己的Node ID比對方小(字母順序)
則把自己的currentEpoch+1
Slave的PING/PONG包中也包含configEpoch字段，Slave的configEpoch字段取值是它的Master的configEpoch字段取值，由最後一次與Master交換PING/PONG包時取得。
Cluster epoch：
每一個節點啟動的時候都會建立currentEpoch字段，無論是Master節點還是Slave節點，并設定初始值為0。每當一個節點收到來自其他節點的PING/PONG包時，若其他節點的currentEpoch字段大于目前節點的currentEpoch字段，則目前節點把自己的currentEpoch字段設定為該新觀察到的currentEpoch值。
4.3.2.3 Slave選舉的過程
Slave節點遞增自己的currentEpoch字段
發送FAILOVER_AUTH_REQUEST資料包給每一個MASTER節點
若MASTER節點投票晉升該SLAVE節點，則回複FAILOVER_AUTH_ACK。某個MASTER節點投過票之後，在NODE_TIMEOUT * 2時間内不能再給同一MASTER的SLAVE選舉投票。
若Slave在MAX((2*NODE_TIMEOUT),2)的時間内獲得大多數MASTER節點的投票，則赢得選舉
其間，所有currentEpoch小于選舉發起時取值的MASTER投票都會被丢棄
若沒有任何Slave赢得選舉，選舉可以在MAX(NODE_TIMEOUT * 4,4)的時間後重新舉行
Master節點投票邏輯
請求選舉的Slave的Master必須處于FAIL狀态
Master節點維護lastVoteEpoch字段，每當MASTER給某個選舉請求投票時，更新lastVoteEpoch字段為請求的currentEpoch值
currentEpoch
currentEpoch
選舉優先權
當Slave節點發現Master節點處于FAIL狀态時，不會立刻試圖進行選舉，而是會延遲一段時間，延遲時常用以下公式進行計算：
DELAY = 500 milliseconds + random delay between 0 and 500 milliseconds + SLAVE_RANK * 1000 milliseconds
其中，SLAVE_RANK由Slave收到Master資料複制的更新程度來衡量。在發起選舉之前，Slave之間交換各自獲得Master資料複制的更新排名，最新更新的SLAVE_RANK = 0， 其次更新的SLAVE_RANK = 1，以此類推...
故障轉移耗時評估
假設配置NODE_TIMEOUT=2s，FAIL_REPORT_VALIDITY_MULT=3s
标記Master為PFAIL狀态耗時NODE_TIMEOUT=2s
更新PFAIL狀态為FAIL狀态，耗時：NODE_TIMEOUT * FAIL_REPORT_VALIDITY_MULT = 6s
選舉前随機延時期望：1s
收集足夠多Master投票：MAX((2*NODE_TIMEOUT),2)=4s
總計耗時約：13s
4.3.3 主備平衡功能
Redis Cluster能夠自動的遷移Slave節點，從Slave節點有備援的Master節點到完全沒有Slave節點的Master節點。
具體算法：
首先定義Good Slave：對于某一節點來說，如果另一個Slave節點沒有處于FAIL狀态，則認為該Slave節點為Good Slave節點。
當有Slave節點發現有Master節點沒有Good Slave時開始觸發主備平衡遷移。
所有發現有主備平衡需求之後，擁有最多Good Slave節點的Master節點的所有Slave中，Node ID最小的Slave節點真正開始遷移。成為沒有沒有Good Slave Master新Master。
可以配置cluster-migration-barrier參數，控制主備平衡遷移的時候，遷出Master最少需要擁有的Good Slave數
4.4 Codis
支援故障檢測并報警
codis-redis-group中的Slave節點無法自動提升為Master節點
由管理者通過Web界面/指令行來手動操作
5.功能限制
Twemproxy:
不支援多key操作
不支援MULTI/EXEC
不支援EVAL
Redis Cluster:
當Client連接配接到叢集的主體部分時可能有少量的寫丢失，當Client連接配接到叢集的小部分時可能有顯著的寫丢失
複雜的多Key操作(Set求并/求交)不能跨節點操作,可以通過使用Hash Tag使相關Key強制哈希到同一Server，但是在資料重新分片期間，還是可能有時間不可用
不支援MULTI/EXEC
Redis 3.0 正式版時間：2015年2月上旬
Codis:
不支援指令：KEYS, MOVE, OBJECT, RENAME, RENAMENX, SORT, SCAN, BITOP,MSETNX, BLPOP, BRPOP, BRPOPLPUSH, PSUBSCRIBE，PUBLISH, PUNSUBSCRIBE, SUBSCRIBE, UNSUBSCRIBE, DISCARD, EXEC, MULTI, UNWATCH, WATCH, SCRIPT EXISTS, SCRIPT FLUSH, SCRIPT KILL, SCRIPT LOAD, AUTH, ECHO, SELECT, BGREWRITEAOF, BGSAVE, CLIENT KILL, CLIENT LIST, CONFIG GET, CONFIG SET, CONFIG RESETSTAT, DBSIZE, DEBUG OBJECT, DEBUG SEGFAULT, FLUSHALL, FLUSHDB, INFO, LASTSAVE, MONITOR, SAVE, SHUTDOWN, SLAVEOF, SLOWLOG, SYNC, TIME
性能
Twemproxy
通常操作Proxy與直接操作Redis執行個體性能一樣
最壞情況下有20%的性能下降
Redis Cluster
1000個節點内擁有線性的伸縮性：通常情況下與直接操作Redis執行個體性能相同。
不支援多核心，但是可以多程序
Codis
相對于單Redis執行個體40%性能損失
支援多核