实现一致性 hash 算法
发布于: 2020 年 07 月 08 日
要求
用熟悉的语言实现一致性 Hash 算法。编写测试用例，测试 100 万 KV 数据，10 个服务器节点的情况下，计算这些 KV 数据在服务器上分布数量的标准差，以评估算法的存储负载不均衡性。
分析
Hash 作用是定位资源在服务器上的位置，公式：hash(res) % 服务器数量=位置，这样不用遍历整个服务器集群就可以定位资源了。
问题是当服务器数量发生变化时（服务器故障时和新增服务器时），资源在服务器上的位置就会发生变化，而且无法避免。
一致性 Hash 算法是对 2^32 次方取模形成 Hash 环，增加容错性和可扩展性，将影响降下可控范围内。
为了进一步解决数据倾斜问题，在物理节点上增加虚拟节点。
关键点
一致性 Hash 定义、环、物理节点、虚拟节点。
代码
/* * This Java source file was generated by the Gradle 'init' task. */package hash;
import java.util.Collection;import java.util.SortedMap;import java.util.TreeMap;import com.google.common.hash.HashFunction;import java.nio.charset.Charset;
public class ConsistentHash<T> {
private final HashFunction hashFunction; private final int numberOfReplicas; private final SortedMap<Long, T> circle = new TreeMap<Long, T>();
public ConsistentHash(HashFunction hashFunction , int numberOfReplicas, Collection<T> nodes) { this.hashFunction = hashFunction; this.numberOfReplicas = numberOfReplicas; for (T node : nodes) add(node); }
public void add(T node) { for (int i = 0; i < numberOfReplicas; i++) { final String nodeName = String.format("%s#%d", node.toString(), i); final long hash = hashFunction.hashString(nodeName , Charset.defaultCharset()).asLong(); circle.put(hash, node); } }
public void remove(T node) { for (int i = 0; i < numberOfReplicas; i++) { final String nodeName = String.format("%s#%d", node.toString(), i); final long hash = hashFunction.hashString(nodeName , Charset.defaultCharset()).asLong(); circle.remove(hash); } }
public T get(Object key) { if (circle.isEmpty()) { return null; } long hash = hashFunction.hashString(key.toString() , Charset.defaultCharset()).asLong(); if (!circle.containsKey(hash)) { SortedMap<Long, T> tailMap = circle.tailMap(hash); hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey(); } return circle.get(hash); }
}
复制代码
测试类
/* * This Java source file was generated by the Gradle 'init' task. */package hash;
import org.junit.Test;import static org.junit.Assert.*;import java.util.Collection;import java.util.HashMap;import java.util.Map;import com.google.common.hash.HashFunction;import com.google.common.hash.Hashing;import java.util.ArrayList;
public class ConsistentHashTest {
@Test public void test_murmur3_128(){ System.out.println(String.format("hash算法:%s", "murmur3_128")); testWithHf(Hashing.murmur3_128()); }
@Test public void test_sipHash24(){ System.out.println(String.format("hash算法:%s", "sipHash24")); testWithHf(Hashing.sipHash24()); }
@Test public void test_md5(){ System.out.println(String.format("hash算法:%s", "md5")); testWithHf(Hashing.md5()); }
@Test public void test_sha1(){ System.out.println(String.format("hash算法:%s", "sha1")); testWithHf(Hashing.sha1()); }
@Test public void test_sha256(){ System.out.println(String.format("hash算法:%s", "sha256")); testWithHf(Hashing.sha256()); }
@Test public void test_sha384(){ System.out.println(String.format("hash算法:%s", "sha384")); testWithHf(Hashing.sha384()); }
@Test public void test_sha512(){ System.out.println(String.format("hash算法:%s", "sha512")); testWithHf(Hashing.sha512()); }
@Test public void test_farmHashFingerprint64(){ System.out.println(String.format("hash算法:%s", "farmHashFingerprint64")); testWithHf(Hashing.farmHashFingerprint64()); }
private void testWithHf(HashFunction hashFunction){ // 十台主机 ArrayList<String> nodes = new ArrayList<String>(); nodes.add("Node-A"); nodes.add("Node-B"); nodes.add("Node-C"); nodes.add("Node-D"); nodes.add("Node-E"); nodes.add("Node-F"); nodes.add("Node-G"); nodes.add("Node-H"); nodes.add("Node-I"); nodes.add("Node-J"); ConsistentHash<String> consistentHashing = new ConsistentHash(hashFunction, 150, nodes); // 100W数据 Map<String, Integer> stats = new HashMap<>(); for (String node: nodes){ stats.put(node, 0); } for (int i = 0; i < 1000000; i++) { String key = "KEY:" + i; String node = consistentHashing.get(key); stats.put(node, stats.get(node)+1); } //输出值 for(Map.Entry<String, Integer> entry : stats.entrySet()){ String mapKey = entry.getKey(); Integer mapValue = entry.getValue(); System.out.println(mapKey+":"+mapValue); } //标准差 Collection<Integer> collection = stats.values(); Integer[] arr = new Integer[collection.size()]; arr = collection.toArray(arr);
System.out.println(String.format("标准差是:%f", std(arr))); }
private double std(Integer[] arr){ int len = arr.length; double sum = 0; for (int i = 0; i < len; i++) { sum += arr[i]; } double avg = sum / len; double std = 0; for (int i = 0; i < len; i++) { std += (arr[i] - avg) * (arr[i] - avg); } return Math.sqrt(std / len); }}
复制代码
结果
hash算法:sha1Node-B:92823Node-A:108256Node-H:97373Node-G:101293Node-J:102935Node-I:101806Node-D:92264Node-C:107575Node-F:94500Node-E:101175标准差是:5375.654844hash算法:md5Node-B:89324Node-A:102482Node-H:110750Node-G:93059Node-J:112777Node-I:95467Node-D:101781Node-C:94636Node-F:101562Node-E:98162标准差是:7109.427853hash算法:sipHash24Node-B:91167Node-A:88697Node-H:101894Node-G:92392Node-J:100053Node-I:99201Node-D:112520Node-C:116950Node-F:95419Node-E:101707标准差是:8578.124026hash算法:sha256Node-B:110619Node-A:102707Node-H:97519Node-G:100612Node-J:102623Node-I:85726Node-D:99586Node-C:92435Node-F:104434Node-E:103739标准差是:6544.380933hash算法:sha384Node-B:89953Node-A:107664Node-H:98905Node-G:110669Node-J:104997Node-I:96231Node-D:103288Node-C:101887Node-F:89127Node-E:97279标准差是:6737.052352hash算法:sha512Node-B:110213Node-A:100911Node-H:93621Node-G:88849Node-J:99329Node-I:93547Node-D:99120Node-C:108141Node-F:103556Node-E:102713标准差是:6319.168996hash算法:murmur3_128Node-B:93231Node-A:92172Node-H:94394Node-G:103487Node-J:112682Node-I:102916Node-D:105730Node-C:99059Node-F:94142Node-E:102187标准差是:6267.671370hash算法:farmHashFingerprint64Node-B:107604Node-A:86907Node-H:111923Node-G:86216Node-J:94556Node-I:94852Node-D:97597Node-C:101734Node-F:119901Node-E:98710标准差是:10119.477042复制代码
划线
评论
复制
发布于: 2020 年 07 月 08 日阅读数: 100
版权声明: 本文为 InfoQ 作者【LEAF】的原创文章。
原文链接:【http://xie.infoq.cn/article/ec4f620f3fd4390f7ba8a9afc】。未经作者许可，禁止转载。
LEAF
关注
还未添加个人签名 2018.10.08 加入
还未添加个人简介
评论