hash簡(jiǎn)介
說(shuō)到底，他是一種hash算法一睁，那什么是hash算法钻弄？
hash算法是一種散列算法，常用的比如MD5者吁。抽象來(lái)說(shuō)窘俺，他是將任意長(zhǎng)度的輸入X，經(jīng)過(guò)hash算法后复凳，變成固定長(zhǎng)度的輸出Y（輸出Y稱為散列值）瘤泪，多個(gè)X可能對(duì)應(yīng)同一個(gè)Y（hash碰撞，概率極小極小極小育八，MD5的碰撞概率為2/2的64次方）对途，且從Y不能反推出X，對(duì)X的任意修改髓棋，都將導(dǎo)致輸出的Y完全不一樣实檀。
基于以上的這些特性，hash算法可以有以下這些應(yīng)用場(chǎng)景：
用hash算法對(duì)網(wǎng)站的登陸密碼使用散列值保存（利用的是不可反推這一特性仲锄，這樣即便淘寶的數(shù)據(jù)庫(kù)被盜了劲妙，誰(shuí)也不會(huì)知道你到底在淘寶買了些什么...東西）
對(duì)比兩個(gè)文件是否完全一樣，假如要對(duì)比的txt文件中有上萬(wàn)的字符儒喊，如何一個(gè)一個(gè)去作對(duì)比镣奋，效率很差，直接對(duì)比文件的散列值是否一致即可知道文件是否一致（利用的是輸出的散列值是固定長(zhǎng)度）
-
負(fù)載均衡算法
作為負(fù)載均衡算法時(shí)怀愧，輸入X是客戶端請(qǐng)求的某個(gè)唯一ID或者key侨颈，hash之后的輸出Y是一個(gè)一定范圍內(nèi)的Long類型數(shù)字余赢，然后我們對(duì)這個(gè)Long類型的數(shù)字進(jìn)行取模，取模得到的余數(shù)就是需要訪問(wèn)的節(jié)點(diǎn)唯一編號(hào)哈垢，利用取模的特性（假如集群中服務(wù)器數(shù)量為3臺(tái)妻柒，那么模數(shù)是3，可以將大量的數(shù)字耘分，映射到[0-3)這個(gè)區(qū)間段）將key均勻的映射到集群中的機(jī)器上举塔，這樣就達(dá)到了負(fù)載均衡的目的，算法公式：hash(key) % n求泰，如下圖：
image.png
最終key1 - keyn會(huì)被均勻的分布在圖中的三個(gè)節(jié)點(diǎn)上央渣，看似已經(jīng)達(dá)到了我們想要的負(fù)載均衡的效果了，但是渴频，當(dāng)客戶端請(qǐng)求在某一時(shí)段激增的時(shí)候（比如雙十一）芽丹，我們常常需要增加服務(wù)器，雙十一過(guò)后卜朗，這些增加的服務(wù)器又需要下線拔第，那么上圖中的算法，就不足以支撐這種情況场钉，假如這時(shí)候node3需要被下線蚊俺，那么客戶端請(qǐng)求對(duì)應(yīng)的負(fù)載均衡算法就變成了hash(key) % 2，這時(shí)候客戶端所有請(qǐng)求和節(jié)點(diǎn)之間的映射關(guān)系就全變了惹悄，許多請(qǐng)求會(huì)被負(fù)載均衡到"錯(cuò)誤的"節(jié)點(diǎn)上去從而拿不到想要的數(shù)據(jù)（如果是緩存春叫，那么絕大部分的獲取緩存的請(qǐng)求都會(huì)失效，大量請(qǐng)求會(huì)打到DB）泣港，人為的去轉(zhuǎn)移數(shù)據(jù)暂殖，那只能996.ICU網(wǎng)站見(jiàn)了。為了解決這個(gè)問(wèn)題当纱，所以呛每，我們需要一致性hash算法
一致性hash算法原理
假設(shè)我們采用的hash算法的值空間為0-P，將0-P構(gòu)建成一個(gè)hash環(huán)坡氯，如下圖：
在普通的hash算法中晨横，我們僅僅對(duì)請(qǐng)求唯一標(biāo)識(shí)做了hash，并且它是一個(gè)線性的hash空間箫柳，而在一致性hash算法中手形，還會(huì)使用同樣的hash算法對(duì)服務(wù)器標(biāo)識(shí)做一次hash運(yùn)算（一般對(duì)服務(wù)器IP或者主機(jī)名做hash運(yùn)算），然后將兩種hash值映射在這個(gè)hash環(huán)（java中可以用TreeMap實(shí)現(xiàn)）上面悯恍，如下圖：
一致性hash算法具備以下特性：
- 客戶端請(qǐng)求最終會(huì)落到他所在hash環(huán)的順時(shí)針?lè)较虻牡谝粋€(gè)節(jié)點(diǎn)上库糠，在上圖中，key3涮毫，key14瞬欧，key1024請(qǐng)求最終會(huì)落到node1上面贷屎，而key5，key76982艘虎，key18會(huì)落到node3上面唉侄。
- 當(dāng)集群中刪除節(jié)點(diǎn)nodex時(shí)，原本應(yīng)該落在nodex上面的請(qǐng)求野建，會(huì)被轉(zhuǎn)移到nodex順時(shí)針的下一個(gè)節(jié)點(diǎn)属划，新增節(jié)點(diǎn)同理，可以看到贬墩，無(wú)論新增還是刪除一個(gè)節(jié)點(diǎn)榴嗅，受影響的都只有一個(gè)節(jié)點(diǎn)的數(shù)據(jù)，如下圖：
image.png
image.png
以上的一致性hash算法相比較普通的hash算法有了很大的改進(jìn)陶舞，但是依然存在問(wèn)題，以刪除節(jié)點(diǎn)為例绪励，刪除一個(gè)節(jié)點(diǎn)后肿孵，集群中大部分的請(qǐng)求key都會(huì)落到node2這個(gè)節(jié)點(diǎn)上，已經(jīng)并不是"負(fù)載均衡"了疏魏。一般的hash環(huán)空間會(huì)很大停做，而如果當(dāng)集群中節(jié)點(diǎn)數(shù)量不是很多的時(shí)候，節(jié)點(diǎn)在環(huán)上面的位置可能會(huì)擠在很小的一部分區(qū)域大莫，這樣就導(dǎo)致一大部分請(qǐng)求會(huì)落到某個(gè)節(jié)點(diǎn)上（數(shù)據(jù)傾斜）蛉腌，為了解決這個(gè)問(wèn)題，一致性hash算法引入虛擬節(jié)點(diǎn)只厘。
虛擬節(jié)點(diǎn)
對(duì)每一個(gè)服務(wù)器節(jié)點(diǎn)進(jìn)行多次hash烙丛，將生成的hash值也分布在hash環(huán)上，這些新生成的節(jié)點(diǎn)稱為虛擬節(jié)點(diǎn)羔味。假設(shè)我們用服務(wù)器IP地址來(lái)做hash河咽，那么可以在IP地址后面增加編號(hào)來(lái)做hash運(yùn)算生成虛擬節(jié)點(diǎn)，增加虛擬節(jié)點(diǎn)后赋元，hash環(huán)如下圖：
從圖中看到忘蟹，沒(méi)有增加虛擬節(jié)點(diǎn)的時(shí)候，大部分的請(qǐng)求會(huì)落到node2這個(gè)節(jié)點(diǎn)上面搁凸，導(dǎo)致node2節(jié)點(diǎn)請(qǐng)求壓力過(guò)大媚值，當(dāng)我們?cè)黾犹摂M節(jié)點(diǎn)后，node1护糖，node2褥芒，node3都能均勻的接收到客戶端的請(qǐng)求。而刪除某個(gè)節(jié)點(diǎn)nodex的時(shí)候椅文，原本應(yīng)該落在nodex上面的請(qǐng)求喂很，也會(huì)被均勻的分配給其他節(jié)點(diǎn)惜颇。
java實(shí)現(xiàn)一致性hash算法
首先我們得需要一個(gè)hash算法，hash算法有很多種少辣，這里提供兩種實(shí)現(xiàn)凌摄，一種基于MD5，一種基于FNV1_32_HASH（這種其實(shí)是我抄來(lái)的漓帅，哈哈哈哈~~~~）
基于MD5：
/**
* hash 運(yùn)算
* @param value
* @return
*/
public Long hash(String value){
MessageDigest md5;
try {
md5 = MessageDigest.getInstance("MD5");
} catch (NoSuchAlgorithmException e) {
throw new RuntimeException("MD5 not supported", e);
}
md5.reset();
byte[] keyBytes = null;
try {
keyBytes = value.getBytes("UTF-8");
} catch (UnsupportedEncodingException e) {
throw new RuntimeException("Unknown string :" + value, e);
}
md5.update(keyBytes);
byte[] digest = md5.digest();
// hash code, Truncate to 32-bits
long hashCode = ((long) (digest[3] & 0xFF) << 24)
| ((long) (digest[2] & 0xFF) << 16)
| ((long) (digest[1] & 0xFF) << 8)
| (digest[0] & 0xFF);
long truncateHashCode = hashCode & 0xffffffffL;
return truncateHashCode;
}
基于FNV1_32_HASH：
public class HashUtil {
/**
* 計(jì)算Hash值, 使用FNV1_32_HASH算法
* @param str
* @return
*/
public static int getHash(String str) {
final int p = 16777619;
int hash = (int)2166136261L;
for (int i = 0; i < str.length(); i++) {
hash =( hash ^ str.charAt(i) ) * 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;
}
}
接下來(lái)我們實(shí)現(xiàn)hash環(huán)锨亏，負(fù)載均衡一般是讀多寫少（新增或者刪除節(jié)點(diǎn)畢竟少數(shù)），在讀多寫少的情況下忙干，我們?nèi)菀紫氲接枚鏄?shù)來(lái)實(shí)現(xiàn)器予，在java中一般直接可以用TreeMap來(lái)實(shí)現(xiàn)，TreeMap是由紅黑樹(shù)實(shí)現(xiàn)的捐迫，很適合作為hash環(huán)的存儲(chǔ)結(jié)構(gòu)乾翔，先實(shí)現(xiàn)一個(gè)沒(méi)有虛擬節(jié)點(diǎn)的hash環(huán)：
public class ConsistentHashingWithoutVirtualNode {
/**
* 集群地址列表
*/
private static String[] groups = {
"192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111",
"192.168.0.3:111", "192.168.0.4:111"
};
/**
* 用于保存Hash環(huán)上的節(jié)點(diǎn)
*/
private static SortedMap<Integer, String> sortedMap = new TreeMap<>();
/**
* 初始化，將所有的服務(wù)器加入Hash環(huán)中
*/
static {
// 使用紅黑樹(shù)實(shí)現(xiàn)施戴，插入效率比較差反浓，但是查找效率極高
for (String group : groups) {
int hash = HashUtil.getHash(group);
System.out.println("[" + group + "] launched @ " + hash);
sortedMap.put(hash, group);
}
}
/**
* 計(jì)算對(duì)應(yīng)的請(qǐng)求應(yīng)該落到哪一個(gè)節(jié)點(diǎn)上
*
* @param key
* @return
*/
private static String getServer(String key) {
int hash = HashUtil.getHash(key);
// 只取出所有大于該hash值的部分而不必遍歷整個(gè)Tree
SortedMap<Integer, String> subMap = sortedMap.tailMap(hash);
if (subMap == null || subMap.isEmpty()) {
// hash值在最尾部，應(yīng)該映射到第一個(gè)group上
return sortedMap.get(sortedMap.firstKey());
}
return subMap.get(subMap.firstKey());
}
public static void main(String[] args) {
// 生成隨機(jī)數(shù)進(jìn)行測(cè)試
Map<String, Integer> resMap = new HashMap<>();
for (int i = 0; i < 100000; i++) {
Integer widgetId = (int)(Math.random() * 10000);
String server = getServer(widgetId.toString());
if (resMap.containsKey(server)) {
resMap.put(server, resMap.get(server) + 1);
} else {
resMap.put(server, 1);
}
}
resMap.forEach(
(k, v) -> {
System.out.println("group " + k + ": " + v + "(" + v/1000.0D +"%)");
}
);
}
}
生成10000個(gè)隨機(jī)數(shù)字進(jìn)行測(cè)試赞哗，最終得到的壓力分布情況如下：
[192.168.0.1:111] launched @ 8518713
[192.168.0.2:111] launched @ 1361847097
[192.168.0.3:111] launched @ 1171828661
[192.168.0.4:111] launched @ 1764547046
group 192.168.0.2:111: 8572(8.572%)
group 192.168.0.1:111: 18693(18.693%)
group 192.168.0.4:111: 17764(17.764%)
group 192.168.0.3:111: 27870(27.87%)
group 192.168.0.0:111: 27101(27.101%)
可以看到雷则，請(qǐng)求分布負(fù)載不均衡，接下來(lái)我們引入虛擬節(jié)點(diǎn)：
public class ConsistentHashingWithVirtualNode {
/**
* 集群地址列表
*/
private static String[] groups = {
"192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111",
"192.168.0.3:111", "192.168.0.4:111"
};
/**
* 真實(shí)集群列表
*/
private static List<String> realGroups = new LinkedList<>();
/**
* 虛擬節(jié)點(diǎn)映射關(guān)系
*/
private static SortedMap<Integer, String> virtualNodes = new TreeMap<>();
private static final int VIRTUAL_NODE_NUM = 1000;
static {
// 先添加真實(shí)節(jié)點(diǎn)列表
realGroups.addAll(Arrays.asList(groups));
// 將虛擬節(jié)點(diǎn)映射到Hash環(huán)上
for (String realGroup: realGroups) {
for (int i = 0; i < VIRTUAL_NODE_NUM; i++) {
String virtualNodeName = getVirtualNodeName(realGroup, i);
int hash = HashUtil.getHash(virtualNodeName);
System.out.println("[" + virtualNodeName + "] launched @ " + hash);
virtualNodes.put(hash, virtualNodeName);
}
}
}
private static String getVirtualNodeName(String realName, int num) {
return realName + "&&VN" + String.valueOf(num);
}
private static String getRealNodeName(String virtualName) {
return virtualName.split("&&")[0];
}
private static String getServer(String key) {
int hash = HashUtil.getHash(key);
// 只取出所有大于該hash值的部分而不必遍歷整個(gè)Tree
SortedMap<Integer, String> subMap = virtualNodes.tailMap(hash);
String virtualNodeName;
if (subMap == null || subMap.isEmpty()) {
// hash值在最尾部肪笋，應(yīng)該映射到第一個(gè)group上
virtualNodeName = virtualNodes.get(virtualNodes.firstKey());
}else {
virtualNodeName = subMap.get(subMap.firstKey());
}
return getRealNodeName(virtualNodeName);
}
public static void main(String[] args) {
// 生成隨機(jī)數(shù)進(jìn)行測(cè)試
Map<String, Integer> resMap = new HashMap<>();
for (int i = 0; i < 100000; i++) {
Integer widgetId = i;
String group = getServer(widgetId.toString());
if (resMap.containsKey(group)) {
resMap.put(group, resMap.get(group) + 1);
} else {
resMap.put(group, 1);
}
}
resMap.forEach(
(k, v) -> {
System.out.println("group " + k + ": " + v + "(" + v/100000.0D +"%)");
}
);
}
}
在上面的代碼中月劈，我給每個(gè)節(jié)點(diǎn)增加了1000個(gè)虛擬節(jié)點(diǎn)，測(cè)試結(jié)果如下：
group 192.168.0.2:111: 18354(18.354%)
group 192.168.0.1:111: 20062(20.062%)
group 192.168.0.4:111: 20749(20.749%)
group 192.168.0.3:111: 20116(20.116%)
group 192.168.0.0:111: 20719(20.719%)
可以看到負(fù)載已經(jīng)基本均衡了藤乙。我們?cè)囈幌聞h除和新增節(jié)點(diǎn)的情況：
private static void refreshHashCircle() {
// 當(dāng)集群變動(dòng)時(shí)猜揪，刷新hash環(huán)，其余的集群在hash環(huán)上的位置不會(huì)發(fā)生變動(dòng)
virtualNodes.clear();
for (String realGroup: realGroups) {
for (int i = 0; i < VIRTUAL_NODE_NUM; i++) {
String virtualNodeName = getVirtualNodeName(realGroup, i);
int hash = HashUtil.getHash(virtualNodeName);
System.out.println("[" + virtualNodeName + "] launched @ " + hash);
virtualNodes.put(hash, virtualNodeName);
}
}
}
private static void addGroup(String identifier) {
realGroups.add(identifier);
refreshHashCircle();
}
private static void removeGroup(String identifier) {
int i = 0;
for (String group:realGroups) {
if (group.equals(identifier)) {
realGroups.remove(i);
}
i++;
}
refreshHashCircle();
}
測(cè)試結(jié)果如下：
running the normal test.
group 192.168.0.2:111: 19144(19.144%)
group 192.168.0.1:111: 20244(20.244%)
group 192.168.0.4:111: 20923(20.923%)
group 192.168.0.3:111: 19811(19.811%)
group 192.168.0.0:111: 19878(19.878%)
removed a group, run test again.
group 192.168.0.2:111: 23409(23.409%)
group 192.168.0.1:111: 25628(25.628%)
group 192.168.0.4:111: 25583(25.583%)
group 192.168.0.0:111: 25380(25.38%)
add a group, run test again.
group 192.168.0.2:111: 15524(15.524%)
group 192.168.0.7:111: 16928(16.928%)
group 192.168.0.1:111: 16888(16.888%)
group 192.168.0.4:111: 16965(16.965%)
group 192.168.0.3:111: 16768(16.768%)
group 192.168.0.0:111: 16927(16.927%)
我們可以看到刪除和新增節(jié)點(diǎn)湾盒，一致性hash算法依然能保持良好的負(fù)載均衡湿右。
redis中的一致性hash算法
未完，待續(xù)罚勾。毅人。。尖殃。丈莺。睡覺(jué)！
