哈希函數(shù)，想必大家都不陌生。通過哈希函數(shù)我們可以將數(shù)據(jù)映射成一個數(shù)字（哈希值），然后可用于將數(shù)據(jù)打亂。例如，在HashMap中則是通過哈希函數(shù)使得每個桶中的數(shù)據(jù)盡量均勻。那一致性哈希又是什么？它是用于解決什么問題？本文將從普通的哈希函數(shù)說起，看看普通哈希函數(shù)存在的問題，然后再看一致性哈希是如何解決，一步步進行分析，并結合代碼實現(xiàn)來講解。
首先，設定這樣一個場景，我們每天有1千萬條業(yè)務數(shù)據(jù)，還有100個節(jié)點可用于存放數(shù)據(jù)。那我們希望能將數(shù)據(jù)盡量均勻地存放在這100個節(jié)點上，這時候哈希函數(shù)就能派上用場了，下面我們按一天的數(shù)據(jù)量來說明。
首先，準備下需要存放的數(shù)據(jù)，以及節(jié)點的地址。為了簡單，這里的數(shù)據(jù)為隨機整型數(shù)字，節(jié)點的地址為從“192.168.1.0”開始遞增。
private static int dataNum = 10000000;
private static int nodeNum = 100;
private static List<Integer> datas = initData(dataNum);
private static List<String> nodes = initNode(nodeNum);
private static List<Integer> initData(int n) {
List<Integer> datas = new ArrayList<>();
Random random = new Random();
for (int i = 0; i < n; i++) {
datas.add(random.nextInt());
}
return datas;
}
private static List<String> initNode(int n) {
List<String> nodes = new ArrayList<>();
for (int i = 0; i < n; i++) {
nodes.add(String.format("192.168.1.%d", i));
}
return nodes;
}
接下來，我們看下通過“哈希+取模”得到數(shù)據(jù)相應的節(jié)點地址。這里的hash方法使用Guava提供的哈希方法來實現(xiàn)，后文也將繼續(xù)使用該hash方法。
public static String normalHash(Integer data, List<String> nodes) {
int hash = hash(data);
int nodeIndex = hash % nodes.size();
return nodes.get(nodeIndex);
}
private static int hash(Object object) {
HashFunction hashFunction = Hashing.murmur3_32();
if (object instanceof Integer) {
return Math.abs(hashFunction.hashInt((Integer) object).asInt());
} else if (object instanceof String) {
return Math.abs(hashFunction.hashUnencodedChars((String) object).asInt());
}
return -1;
}
最后，我們對數(shù)據(jù)的分布情況進行統(tǒng)計，觀察分布是否均勻，這里通過標準差來觀察。
public static void normalHashMain() {
Map<String, Integer> nodeCount = new HashMap<>();
for (Integer data : datas) {
String node = normalHash(data, nodes);
if (nodeCount.containsKey(node)) {
nodeCount.put(node, nodeCount.get(node) + 1);
} else {
nodeCount.put(node, 1);
}
}
analyze(nodeCount, dataNum, nodeNum);
}
public static void analyze(Map<String, Integer> nodeCount, int dataNum, int nodeNum) {
double average = (double) dataNum / nodeNum;
IntSummaryStatistics s1
= nodeCount.values().stream().mapToInt(Integer::intValue).summaryStatistics();
int max = s1.getMax();
int min = s1.getMin();
int range = max - min;
double standardDeviation
= nodeCount.values().stream().mapToDouble(n -> Math.abs(n - average)).summaryStatistics().getAverage();
System.out.println(String.format("平均值：%.2f", average));
System.out.println(String.format("最大值：%d,（%.2f%%）", max, 100.0 * max / average));
System.out.println(String.format("最小值：%d,（%.2f%%）", min, 100.0 * min / average));
System.out.println(String.format("極差：%d,（%.2f%%）", range, 100.0 * range / average));
System.out.println(String.format("標準差：%.2f,（%.2f%%）", standardDeviation, 100.0 * standardDeviation / average));
}
/**
平均值：100000.00
最大值：100818,（100.82%）
最小值：99252,（99.25%）
極差：1566,（1.57%）
標準差：240.08,（0.24%）
**/
其中標準差較小，說明分布較為均勻，那我們的需求達到了。
接著，隨著業(yè)務的發(fā)展，你發(fā)現(xiàn)100個節(jié)點不夠用了，我們希望再增加10個節(jié)點，來提高系統(tǒng)性能。而我們還將繼續(xù)采用之前的方法來分布數(shù)據(jù)。這時候就出現(xiàn)了一個新的問題，我們是通過“哈希+取模”來決定數(shù)據(jù)的相應節(jié)點，原來數(shù)據(jù)的哈希值是不會改變的，可是取模的時候節(jié)點的數(shù)量發(fā)生了變化，這將導致的結果就是原來的數(shù)據(jù)存在A節(jié)點，現(xiàn)在可能需要遷移到B節(jié)點，也就是數(shù)據(jù)遷移問題。下面我們來看下有多少數(shù)據(jù)將發(fā)生遷移。
private static int newNodeNum = 11;
private static List<String> newNodes = initNode(newNodeNum);
public static void normalHashMigrateMain() {
int migrateCount = 0;
for (Integer data : datas) {
String node = normalHash(data, nodes);
String newNode = normalHash(data, newNodes);
if (!node.equals(newNode)) {
migrateCount++;
}
}
System.out.println(String.format("數(shù)據(jù)遷移量：%d（%.2f%%）", migrateCount, migrateCount * 100.0 / datas.size()));
}
/**
數(shù)據(jù)遷移量：9091127（90.91%）
**/
有90%多的數(shù)據(jù)都需要進行遷移，這是幾乎全部的量了。普通哈希的問題暴露出來了，當將節(jié)點由100擴展為110時，會存在大量的遷移工作。在1997年MIT提出了一致性哈希算法，用于解決普通哈希的這一問題。
我們再分析下，假設hash值為10000，nodeNum為100，那按照index = hash % nodeNum得到的結果是0，而將100變?yōu)?10時，取模的結果將改變?yōu)?00。如果我們將取模的除數(shù)增大至大于hash值，那hash值取模的結果將仍是其本身。也就是說，只要除數(shù)保證大于hash值，那取模的結果將不會改變。這里的hash值是int，4個字節(jié)，那我們把除數(shù)固定為2^32-1，index = hash % (2^32-1)。取模的結果也將固定在0到2^32-1中，可將其構成一個環(huán)，如下所示。
取模的結果范圍
現(xiàn)在的除數(shù)是2^32-1，hash值為10000，取模的結果為10000，而我們有100個節(jié)點，該映射到哪個節(jié)點上呢？我們可以先將節(jié)點通過哈希映射到環(huán)上。為了繪圖方便，我們以3個節(jié)點為例，如下圖所示：
一致性哈希環(huán)
10000落到環(huán)上后，如果沒有對應的節(jié)點，則按順時針方向找到下一個節(jié)點，便為hash值對應的節(jié)點。下面我們用JAVA的TreeMap來存節(jié)點的hash值，利用TreeMap的tailMap尋找節(jié)點。
我們使用和之前同樣的方法，測試下當節(jié)點由100變?yōu)?10時，數(shù)據(jù)需要遷移的情況，如下所示：
public static void consistHashMigrateMain() {
int migrateCount = 0;
SortedMap<Integer, String> circle = new TreeMap<>();
for (String node : nodes) {
circle.put(hash(node), node);
}
SortedMap<Integer, String> newCircle = new TreeMap<>();
for (String node : newNodes) {
newCircle.put(hash(node), node);
}
for (Integer data : datas) {
String node = consistHash(data, circle);
String newNode = consistHash(data, newCircle);
if (!node.equals(newNode)) {
migrateCount++;
}
}
System.out.println(String.format("數(shù)據(jù)遷移量：%d（%.2f%%）", migrateCount, migrateCount * 100.0 / datas.size()));
}
public static String consistHash(Integer data, SortedMap<Integer, String> circle) {
int hash = hash(data);
// 從環(huán)中取大于等于hash值的部分
SortedMap<Integer, String> subCircle = circle.tailMap(hash);
int index;
// 如果在大于等于hash值的部分沒有節(jié)點，則取環(huán)開始的第一個節(jié)點
if (subCircle.isEmpty()) {
index = circle.firstKey();
} else {
index = subCircle.firstKey();
}
return circle.get(index);
}
/**
數(shù)據(jù)遷移量：817678（8.18%）
**/
可見需要遷移的數(shù)據(jù)由90%降到了8%，效果十分可觀。那我們再看下數(shù)據(jù)的分布情況，是否仍然均勻：
/**
平均值：100000.00
最大值：589675,（589.68%）
最小值：227,（0.23%）
極差：589448,（589.45%）
標準差：77421.44,（77.42%）
**/
77%的標準差，一個字，崩！這是為啥？我們原本設想的是節(jié)點映射到環(huán)上時，能將環(huán)均勻劃分，所以當數(shù)據(jù)映射到環(huán)上時，也將被均勻分布到節(jié)點上。而實際情況，由于節(jié)點地址相似，映射到環(huán)上的位置也將相近，所以造成分布的不均勻，如下圖所示：
分布不均
由于A、B、C的地址相似，例如：
A: 192.168.1.0
B: 192.168.1.1
C: 192.168.1.2
所以映射的位置相近，那我們可以復制幾份A、B、C，并且通過改變key，讓節(jié)點能更均勻的劃分環(huán)。比如我們在地址后面追加 “-index” 的序號，例如：
A0: 192.168.1.0-0
B0: 192.168.1.1-0
C0: 192.168.1.2-0
A1: 192.168.1.0-1
B1: 192.168.1.1-1
C1: 192.168.1.2-1
雖然A0、B0、C0會相距較近，但是和A1、B1、C1的key具有差別，將能夠成功分開，這也正是虛擬節(jié)點的作用。達到的效果如下：
虛擬節(jié)點
下面我們通過代碼驗證下實際效果：
private static int vNodeNum = 100;
public static void consistHashVirtualNodeMain() {
Map<String, Integer> nodeCount = new HashMap<>();
SortedMap<Integer, String> circle = new TreeMap<>();
for (String node : nodes) {
for (int i = 0; i < vNodeNum; i++) {
circle.put(hash(node + "-" + i), node);
}
}
for (Integer data : datas) {
String node = consistHashVirtualNode(data, circle);
if (nodeCount.containsKey(node)) {
nodeCount.put(node, nodeCount.get(node) + 1);
} else {
nodeCount.put(node, 1);
}
}
analyze(nodeCount, dataNum, nodeNum);
}
/**
平均值：100000.00
最大值：122931,（122.93%）
最小值：74434,（74.43%）
極差：48497,（48.50%）
標準差：7475.08,（7.48%）
**/
可看到標準差已經(jīng)由77%降到7%，效果顯著。再多做幾組實驗，標準差隨著虛擬節(jié)點數(shù)的變化如下：
結果中，隨著虛擬節(jié)點數(shù)的增加，標準差逐步下降。可見虛擬節(jié)點能達到均勻分布數(shù)據(jù)的效果。
一句話總結下：
一致性哈希可用于解決哈希函數(shù)在擴容時的數(shù)據(jù)遷移的問題，而一致性哈希的實現(xiàn)中需要借助虛擬節(jié)點來均勻分布數(shù)據(jù)。
