問題：1-2億數據需要緩存，如何設計？

1 哈希取余分區

2億條記錄就是2億個k,v，假設有3臺機器構成一個集群，用戶每次讀寫操作都是根據公：hash(key) % N個機器臺數，計算出哈希值，并用來決定數據映射到哪一個節點上。取數據的時候只需要個根據公式在相應的機器，用key就可以取到value。

優點：? 簡單粗暴，直接有效，只需要預估好數據規劃好節點，例如3臺、8臺、10臺，就能保證一段時間的數據支撐。使用Hash算法讓固定的一部分請求落到同一臺服務器上，這樣每臺服務器固定處理一部分請求（并維護這些請求的信息），起到負載均衡+分而治之的作用。

缺點：原來規劃好的節點，進行擴容或者縮容就比較麻煩了，不管擴縮，每次數據變動導致節點有變動，映射關系需要重新進行計算，在服務器個數固定不變時沒有問題，如果需要彈性擴容或故障停機的情況下，原來的取模公式就會發生變化：Hash(key)/3會變成Hash(key) /?。此時地址經過取余運算的結果將發生很大變化，根據公式獲取的服務器也會變得不可控。某個redis機器宕機了，由于臺數數量變化，會導致hash取余全部數據重新洗牌。

2 一致性哈希算法分區

提出一致性Hash解決方案，目的是當服務器個數發生變動時，盡量減少影響客戶端到服務器的映射關系。

2.1 一致性哈希環

????????一致性哈希算法必然有個hash函數并按照算法產生hash值，這個算法的所有可能哈希值會構成一個全量集，這個集合可以成為一個hash空間[0,2^32-1]，這個是一個線性空間，但是在算法中，我們通過適當的邏輯控制將它首尾相連(0 = 2^32),這樣讓它邏輯上形成了一個環形空間。

????????它也是按照使用取模的方法，前面筆記介紹的節點取模法是對節點（服務器）的數量進行取模。而一致性Hash算法是對2^32取模，簡單來說， 一致性Hash算法將整個哈希值空間組織成一個虛擬的圓環 ，如假設某哈希函數H的值空間為0-2^32-1（即哈希值是一個32位無符號整形），整個哈希環如下圖：整個空間 按順時針方向組織 ，圓環的正上方的點代表0，0點右側的第一個點代表1，以此類推，2、3、4、……直到2^32-1，也就是說0點左側的第一個點代表2^32-1， 0和2^32-1在零點中方向重合，我們把這個由2^32個點組成的圓環稱為Hash環。

2.2 節點映射

?將集群中各個IP節點映射到環上的某一個位置。

???將各個服務器使用Hash進行一個哈希，具體可以選擇服務器的IP或主機名作為關鍵字進行哈希，這樣每臺機器就能確定其在哈希環上的位置。假如4個節點NodeA、B、C、D，經過IP地址的 哈希函數 計算(hash(ip))，使用IP地址哈希后在環空間的位置如下：

2.3 落鍵規則

????????當我們需要存儲一個kv鍵值對時，首先計算key的hash值，hash(key)，將這個key使用相同的函數Hash計算出哈希值并確定此數據在環上的位置， 從此位置沿環順時針“行走” ，第一臺遇到的服務器就是其應該定位到的服務器，并將該鍵值對存儲在該節點上。

????????如我們有Object A、Object B、Object C、Object D四個數據對象，經過哈希計算后，在環空間上的位置如下：根據一致性Hash算法，數據A會被定為到Node A上，B被定為到Node B上，C被定為到Node C上，D被定為到Node D上。

?2.4 優缺點

優點：容錯性和擴展性

容錯性：

????????假設Node C宕機，可以看到此時對象A、B、D不會受到影響，只有C對象被重定位到Node D。一般的，在一致性Hash算法中，如果一臺服務器不可用，則 受影響的數據僅僅是此服務器到其環空間中前一臺服務器（即沿著逆時針方向行走遇到的第一臺服務器）之間數據 ，其它不會受到影響。簡單說，就是C掛了，受到影響的只是B、C之間的數據，并且這些數據會轉移到D進行存儲。

?缺點：數據傾斜（節點少不宜）

????????一致性Hash算法在服務 節點太少時 ，容易因為節點分布不均勻而造成 數據傾斜 （被緩存的對象大部分集中緩存在某一臺服務器上）問題，

例如系統中只有兩臺服務器：

3 哈希槽計算

為了解決一致性哈希算法的傾斜問題

解決均勻分配的問題， 在數據和節點之間又加入了一層，把這層稱為哈希槽（slot），用于管理數據和節點之間的關系 ，現在就相當于節點上放的是槽，槽里放的是數據。

槽解決的是粒度問題，相當于把粒度變大了，這樣便于數據移動。

哈希解決的是映射問題，使用key的哈希值來計算所在的槽，便于數據分配。

一個集群只能有16384個槽，編號0-16383（0-2^14-1）。這些槽會分配給集群中的所有主節點，分配策略沒有要求。可以指定哪些編號的槽分配給哪個主節點。集群會記錄節點和槽的對應關系。解決了節點和槽的關系后，接下來就需要對key求哈希值，然后對16384取余，余數是幾key就落入對應的槽里。slot = CRC16(key) % 16384。以槽為單位移動數據，因為槽的數目是固定的，處理起來比較容易，這樣數據移動問題就解決了。

????????Redis 集群中內置了 16384 個哈希槽，redis 會根據節點數量大致均等的將哈希槽映射到不同的節點。當需要在 Redis 集群中放置一個 key-value時，redis 先對 key 使用 crc16 算法算出一個結果，然后把結果對 16384 求余數，這樣每個 key 都會對應一個編號在 0-16383 之間的哈希槽，也就是映射到某個節點上。如下代碼，key之A 、B在Node2， key之C落在Node3上

總結