九張圖，帶你了解一致性哈希原理
假設(shè)我們現(xiàn)在做一個(gè)簡單的文件緩存服務(wù)，由于文件數(shù)過多，我們先使用3臺(tái)機(jī)器用來存儲(chǔ)文件。
為了由文件名(假設(shè)文件名稱不重復(fù))能得到存儲(chǔ)的機(jī)器，考慮先對文件名做hash運(yùn)算，接著對3取余，得到的余數(shù)即為所在機(jī)器的編號(hào)。
這套系統(tǒng)運(yùn)行了很久，后來文件數(shù)量慢慢增多，3臺(tái)機(jī)器存不下了，現(xiàn)在我們考慮擴(kuò)充到4臺(tái)。
這個(gè)時(shí)候，我們的算法更新為hash(文件名)%5。
那么使用該算法獲取abc.txt文件所在的緩存機(jī)器時(shí)，在其hash值為10的時(shí)候，將會(huì)映射到0號(hào)機(jī)器上，而之前是存儲(chǔ)在1號(hào)機(jī)器上的，這個(gè)時(shí)候就會(huì)重新將文件存儲(chǔ)到0號(hào)機(jī)器上，或者將1號(hào)機(jī)器上的文件遷移到0號(hào)機(jī)器上。
因此，增加了兩臺(tái)機(jī)器后，導(dǎo)致了緩存失效。
我們使用代碼來大致確定一下緩存失效的比例：
- public static void main(String[] args) {
- //緩存失效計(jì)數(shù)
- int count = 0;
- //假設(shè)一共有10000份文件
- for (int i = 0; i < 10000; i++) {
- //文件名稱
- String fileName = "file#" + i;
- int hashCode = fileName.hashCode();
- //原來的存儲(chǔ)位置
- int oldSite = hashCode % 3;
- //增加兩臺(tái)機(jī)器后，現(xiàn)在的存儲(chǔ)位置
- int newSite = hashCode % 5;
- if (oldSite != newSite) {
- count++;
- }
- }
- System.out.println(count);
- }
運(yùn)行后發(fā)現(xiàn)，超過80%的緩存都會(huì)失效。
也就是說，無論是增加機(jī)器還是減少機(jī)器，都會(huì)使得緩存大面積的失效，這是我們不愿意見到的結(jié)果，那么有沒有一種新的算法呢?
一致性哈希算法，就應(yīng)運(yùn)而生了。該算法可以使得增減機(jī)器時(shí)，大幅度減少失效的緩存數(shù)量。
首先這里有個(gè)圓，你可以看做是從0到2^32-1頭尾相連的環(huán)。
我們先對一臺(tái)機(jī)器的ip做哈希運(yùn)算，再對2^32取模，即hash(ip)%2^32，得到了數(shù)字肯定在環(huán)上。
假設(shè)我們使用的哈希算法得到的哈希值返回值是int類型，則本身相當(dāng)于已經(jīng)取過模。
因此我們標(biāo)記出三臺(tái)機(jī)器在環(huán)上的位置
這個(gè)時(shí)候，需要將文件映射到環(huán)上，使用一樣的哈希函數(shù)，即hash(文件名)。假設(shè)這里有4個(gè)文件，我們在環(huán)上標(biāo)記出文件的位置。
那現(xiàn)在怎么確定文件在哪臺(tái)機(jī)器上存儲(chǔ)呢?
很簡單，從當(dāng)前文件開始，順時(shí)針找到第一個(gè)機(jī)器，即為文件的存儲(chǔ)位置。
假設(shè)這個(gè)時(shí)候機(jī)器2宕機(jī)，我們將機(jī)器2從環(huán)上移除，觀察一下文件3的變化
當(dāng)機(jī)器2宕機(jī)時(shí)，文件3將重新指向機(jī)器3。
也就是說，當(dāng)機(jī)器2宕機(jī)時(shí)，原本映射到機(jī)器1與機(jī)器2之間位置的文件，將會(huì)被重新映射到機(jī)器3。
因此，一致性哈希能夠大幅度降低緩存失敗的范圍，不至于“牽一發(fā)而動(dòng)全身”。
不知道大家有沒有看出來，在上圖中，幾臺(tái)機(jī)器在環(huán)上的分布比較均勻，這是一種非常理想的情況。
然而現(xiàn)實(shí)可能并不是這樣，假設(shè)3臺(tái)機(jī)器經(jīng)過映射后，彼此之間非?？拷?。
當(dāng)機(jī)器數(shù)量特別少的時(shí)候，經(jīng)過映射后，節(jié)點(diǎn)在環(huán)上分布不均勻，導(dǎo)致大部分文件全部落在同一臺(tái)機(jī)器上，也就是存在數(shù)據(jù)傾斜問題。
如圖所示，4個(gè)文件全部存儲(chǔ)在了機(jī)器1上。倘若有一天，機(jī)器1承載不住大量的文件訪問掛了，這些文件將會(huì)立即轉(zhuǎn)移到機(jī)器2上。機(jī)器2同樣也會(huì)承載不住，最后就會(huì)造成整個(gè)系統(tǒng)的連鎖崩潰。
既然問題的根本在于機(jī)器數(shù)量少，那我們可以增加機(jī)器啊!
但機(jī)器是一種實(shí)際存在的物理資源，不可能說增加就增加，老板也不讓啊!
這個(gè)時(shí)候，我們可以復(fù)制現(xiàn)有的物理機(jī)器，形成一些虛擬節(jié)點(diǎn)，通過以物理節(jié)點(diǎn)的ip加上后綴序號(hào)來實(shí)現(xiàn)。
當(dāng)虛擬節(jié)點(diǎn)以同樣的算法映射到環(huán)上之后，文件1最終將會(huì)落到機(jī)器2上。
理論上，虛擬節(jié)點(diǎn)越多，越能做到相對的均勻分布。
下面以代碼的形式，來驗(yàn)證一下。
- public class Main {
- //真實(shí)節(jié)點(diǎn)
- private static final String[] ipArray = new String[]{"192.168.1.1", "192.168.1.2", "192.168.1.3", "192.168.1.4"};
- //哈希環(huán)(哈希值->真實(shí)節(jié)點(diǎn)ip)
- private static final TreeMap<Long, String> circle = new TreeMap<>();
- //指定倍數(shù)初始化哈希環(huán)
- private static void initCircle(int mul) {
- //映射真實(shí)節(jié)點(diǎn)
- for (String ip : ipArray) {
- circle.put(hash(ip), ip);
- //按照倍數(shù)映射虛擬節(jié)點(diǎn)
- for (int i = 1; i <= mul; i++) {
- String virtual = ip + "#" + i;
- circle.put(hash(virtual), ip);
- }
- }
- }
- //獲取指定文件存儲(chǔ)的機(jī)器ip
- private static String getIpByFileName(String fileName) {
- long hash = hash(fileName);
- Long higherKey = circle.higherKey(hash);
- if (higherKey == null) {
- //返回哈希環(huán)中的第一個(gè)ip
- return circle.get(circle.firstKey());
- }
- //返回比文件名稱的哈希值大的最小ip
- return circle.get(higherKey);
- }
- //統(tǒng)計(jì)落在每個(gè)節(jié)點(diǎn)上的文件總數(shù)(ip->文件總數(shù))
- private static Map<String, Long> count(long fileCount) {
- //(ip,文件總數(shù))
- Map<String, Long> map = new HashMap<>();
- for (long i = 1; i <= fileCount; i++) {
- String ip = getIpByFileName("file#" + i);
- Long ipCount = map.get(ip);
- map.put(ip, (ipCount == null ? 0 : ipCount) + 1);
- }
- return map;
- }
- //打印各個(gè)ip存儲(chǔ)的文件數(shù)占總數(shù)的百分比
- private static void print(int fileCount) {
- Map<String, Long> map = count(fileCount);
- for (String ip : ipArray) {
- Long ipCountL = map.get(ip);
- long ipCount = ipCountL == null ? 0 : ipCountL;
- double result = ipCount * 100 / (double) fileCount;
- //保留一位小數(shù)
- String format = String.format("%.1f", result);
- System.out.println(ip + ":" + format + "%");
- }
- }
- // 32位的 Fowler-Noll-Vo 哈希算法
- // https://en.wikipedia.org/wiki/Fowler–Noll–Vo_hash_function
- private static Long hash(String key) {
- final int p = 16777619;
- long hash = 2166136261L;
- for (int idx = 0, num = key.length(); idx < num; ++idx) {
- hash = (hash ^ key.charAt(idx)) * p;
- }
- hash += hash << 13;
- hash ^= hash >> 7;
- hash += hash << 3;
- hash ^= hash >> 17;
- hash += hash << 5;
- if (hash < 0) {
- hash = Math.abs(hash);
- }
- return hash;
- }
- public static void main(String[] args) {
- //初始化哈希環(huán)
- initCircle(1000000);
- //文件總數(shù)10000個(gè)
- print(10000);
- }
- }
當(dāng)倍數(shù)為0時(shí)：
- 192.168.1.1:0.0%
- 192.168.1.2:0.0%
- 192.168.1.3:100.0%
- 192.168.1.4:0.0%
相當(dāng)于沒有虛擬節(jié)點(diǎn)，可以看到極度不均勻，傾斜嚴(yán)重。
當(dāng)倍數(shù)為100時(shí)：
- 192.168.1.1:28.4%
- 192.168.1.2:22.4%
- 192.168.1.3:34.6%
- 192.168.1.4:14.6%
傾斜改善了!但仍然不滿足
當(dāng)倍數(shù)為10000時(shí)：
- 192.168.1.1:24.6%
- 192.168.1.2:25.9%
- 192.168.1.3:23.3%
- 192.168.1.4:26.3%
基本上算是比較均勻了
大膽點(diǎn)，我們把倍數(shù)調(diào)到1百萬，文件數(shù)也調(diào)到1百萬
- 192.168.1.1:25.0%
- 192.168.1.2:24.9%
- 192.168.1.3:25.0%
- 192.168.1.4:25.1%
可見所有ip下存儲(chǔ)的文件總數(shù)非常均勻!
