一致性哈希
问题呈现
如下图采用普通hash把数据存储到不同节点上。
问题1：当增加或删除一个节点时，需要重新分配大量的键，导致大量数据迁移和性能下降。
问题2：如果一个节点宕机，普通哈希并不会自动调整数据的分布，也不能平衡负载。
如何改进呢？采用一致性hash可以解决这个问题。
当插入一个新的节点E，只有上屏100和101从节点A迁移到节点E。同理删除一个节点，也只有一个节点的数据会发生迁移。
一致性哈希（Consistent Hashing）是一种特殊的哈希算法，在分布式系统中具有广泛的应用。以下是对一致性哈希的理解及其解决的问题的详细阐述：
一、一致性哈希的定义
一致性哈希算法由麻省理工学院在1997年提出，目的是解决分布式缓存的问题。其核心思想是将整个哈希值空间组织成一个虚拟的环，通常使用MD5或SHA-1等哈希函数将数据项和服务器节点都映射到这个环上，并通过比较哈希值来确定数据应该存储在哪个节点上。这个哈希环的取值范围通常为0到2^32-1，形成一个闭环结构。
二、一致性哈希的工作原理
- 节点映射：使用哈希函数将每个服务器节点映射到哈希环上的某个点，这些点称为节点的哈希值或位置。
- 数据映射：使用相同的哈希函数将数据项映射到哈希环上的某个点。
- 数据分配：数据项在环上的位置确定后，从该位置开始顺时针查找，找到的第一个节点即为其存储节点。
三、一致性哈希解决的问题
- 动态伸缩性问题：在分布式系统中，节点的增加或减少是常见的操作。传统的哈希方法在面对这种动态变化时会导致大量的数据重新分配，因为哈希空间被完全重新映射。而一致性哈希通过在哈希环上顺时针查找来分配数据，当新节点加入或旧节点离开时，仅需重新分配少量数据，从而大大减少了数据迁移的范围和开销，保持了系统的高效性和稳定性。
- 负载均衡问题：一致性哈希通过将数据均匀分布在哈希环上，使得每个节点都能够承担相对均衡的负载。当节点数量增加时，新的节点会分担原有节点的负载，从而实现负载均衡。
- 容错性问题：在分布式系统中，节点故障是不可避免的。一致性哈希通过顺时针查找机制，使得当一个节点失效时，其负责的数据可以迅速重新分配到下一个节点上，从而保证了系统的容错性和可用性。
四、一致性哈希的改进与优化
- 引入虚拟节点：为了解决服务器节点分布不均匀的问题，一致性哈希引入了虚拟节点的概念。每个物理节点对应多个虚拟节点，数据映射到虚拟节点上，从而实现数据的均匀分布。当某个物理节点失效时，其对应的虚拟节点上的数据会均匀分散到其他节点的虚拟节点上，进一步提高了系统的容错性和负载均衡能力。
- 使用更高效的哈希函数：为了提高哈希计算的速度和准确性，一致性哈希可以使用更高效的哈希函数，如FNV-1a等。这些哈希函数具有较低的碰撞率和较高的散列均匀性，能够更好地满足分布式系统的需求。
五、代码实现
实现一致性哈希（Consistent Hashing）在Java中需要一些基础的数据结构和算法。以下是一个简单的Java实现，它包括了基本的节点添加、删除和数据定位功能。请注意，这个实现是简化的，可能并不适合在生产环境中直接使用。
首先，我们需要一个HashRing类来表示哈希环，以及一个HashNode类来表示环上的节点。
import java.nio.charset.StandardCharsets;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
public class ConsistentHashing {
// 虚拟节点的前缀，用于区分不同的物理节点
private static final String VIRTUAL_NODE_PREFIX = "vnode_";
// 虚拟节点的数量，可以根据需要调整
private static final int VIRTUAL_NODE_COUNT = 100;
// 存储节点和它们对应的哈希值
private SortedMap<Integer, HashNode> circle = new TreeMap<>();
// 存储物理节点和它们对应的虚拟节点集合
private Map<String, List<HashNode>> realNodes = new ConcurrentHashMap<>();
// 存储数据项和它们对应的节点
private Map<String, String> dataMapping = new ConcurrentHashMap<>();
// 哈希函数，用于计算哈希值
private MessageDigest md;
public ConsistentHashing() throws NoSuchAlgorithmException {
md = MessageDigest.getInstance("MD5");
}
// 添加物理节点到哈希环
public void addNode(String node) {
List<HashNode> vnodeList = new ArrayList<>();
for (int i = 0; i < VIRTUAL_NODE_COUNT; i++) {
String virtualNodeName = VIRTUAL_NODE_PREFIX + node + "#" + i;
int hash = hash(virtualNodeName);
vnodeList.add(new HashNode(virtualNodeName, hash));
circle.put(hash, new HashNode(virtualNodeName, hash));
}
realNodes.put(node, vnodeList);
}
// 从哈希环中移除物理节点
public void removeNode(String node) {
List<HashNode> vnodeList = realNodes.get(node);
if (vnodeList != null) {
for (HashNode vnode : vnodeList) {
circle.remove(vnode.getHash());
}
realNodes.remove(node);
}
}
// 获取数据项对应的节点
public String getNode(String key) {
if (circle.isEmpty()) {
return null;
}
int hash = hash(key);
SortedMap<Integer, HashNode> tailMap = circle.tailMap(hash);
hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
return circle.get(hash).getVirtualNodeName().split("#")[0].replace(VIRTUAL_NODE_PREFIX, "");
}
// 添加数据项到哈希环
public void put(String key, String value) {
String node = getNode(key);
dataMapping.put(key, node + ":" + value);
}
// 获取数据项的值
public String get(String key) {
return dataMapping.get(key);
}
// 计算哈希值
private int hash(String key) {
md.reset();
md.update(key.getBytes(StandardCharsets.UTF_8));
byte[] digest = md.digest();
// 只取哈希值的前4个字节（32位）作为整数返回
return ((digest[0] & 0xFF) << 24) |
((digest[1] & 0xFF) << 16) |
((digest[2] & 0xFF) << 8) |
(digest[3] & 0xFF);
}
// 辅助类：表示哈希环上的节点
private static class HashNode {
private final String virtualNodeName;
private final int hash;
public HashNode(String virtualNodeName, int hash) {
this.virtualNodeName = virtualNodeName;
this.hash = hash;
}
public String getVirtualNodeName() {
return virtualNodeName;
}
public int getHash() {
return hash;
}
}
public static void main(String[] args) throws NoSuchAlgorithmException {
ConsistentHashing ch = new ConsistentHashing();
ch.addNode("NodeA");
ch.addNode("NodeB");
ch.addNode("NodeC");
ch.put("key1", "value1");
ch.put("key2", "value2");
ch.put("key3", "value3");
System.out.println("key1 is on node: " + ch.get("key1"));
System.out.println("key2 is on node: " + ch.get("key2"));
System.out.println("key3 is on node: " + ch.get("key3"));
// 移除节点并查看数据重新分配情况
ch.removeNode("NodeB");
System.out.println("After removing NodeB:");
System.out.println("key1 is now on node: " + ch.get("key1"));
System.out.println("key2 is now on node: " + ch.get("key2"));
System.out.println("key3 is now on node: " + ch.get("key3"));
}
}在这个实现中：
ConsistentHashing类包含了哈希环、物理节点、数据项映射和哈希函数。addNode方法用于向哈希环中添加物理节点，并为每个物理节点创建多个虚拟节点。removeNode方法用于从哈希环中移除物理节点及其对应的虚拟节点。getNode方法用于根据数据项的哈希值找到其应该存储的物理节点。put和get方法用于在哈希环上存储和检索数据项。hash方法使用MD5哈希函数计算字符串的哈希值，并将其转换为整数。HashNode类是一个辅助类，用于表示哈希环上的节点。
请注意，这个实现中的哈希函数仅使用了MD5的前4个字节（32位）作为整数哈希值，这是为了简化示例。在生产环境中，您可能需要使用更完整的哈希值或更强大的哈希函数。此外，这个实现没有处理并发修改和数据一致性等高级问题。
key1 is on node: NodeA:value1
key2 is on node: NodeA:value2
key3 is on node: NodeB:value3
After removing NodeB:
key1 is now on node: NodeA:value1
key2 is now on node: NodeA:value2
key3 is now on node: NodeB:value3
六、一致性哈希与普通哈希的区别
普通哈希（Hashing）与一致性哈希（Consistent Hashing）在数据分布、扩展性和容错性等方面存在显著区别。以下是对两者的详细比较：
6.1、核心思想与应用场景
-
普通哈希：
- 核心思想：将输入（如键）通过哈希函数映射到固定范围内的一个值（如数组的索引）。
- 应用场景：适用于静态系统或节点数量固定的情况，如哈希表或某些缓存场景。
-
一致性哈希：
- 核心思想：在哈希空间中建立一个虚拟环，以减小节点的变动对整个系统的影响。
- 应用场景：广泛用于分布式系统中，特别是节点数量可能动态变化的情况，如缓存系统（Redis、Memcached）、分布式存储系统、分布式数据库等。
6.2、数据分布与哈希空间
-
普通哈希：
- 通常将输入映射到一个固定的哈希空间，如数组或固定大小的存储单元。
- 设计目标是将输入均匀地分布在哈希空间中，以避免哈希冲突。
-
一致性哈希：
- 将哈希值映射到一个环形结构上，节点和数据都在这个环上，数据映射到离它最近的节点上。
- 使用了虚拟节点的概念，一个物理节点可以映射到多个哈希位置，有助于提高负载均衡性和避免数据倾斜问题。
6.3、扩展性与容错性
-
普通哈希：
- 扩展性差：当增加或删除一个节点时，需要重新分配大量的键，导致大量数据迁移和性能下降。
- 不具备容错性：如果一个节点宕机，普通哈希并不会自动调整数据的分布，也不能平衡负载。
-
一致性哈希：
- 扩展性好：在增加或删除节点时，只需要重新分配少量的数据。新增一个节点后，只会将该节点附近的数据重新分配，而不会影响整个系统。
- 容错性强：如果一个节点宕机，它的数据会自动映射到它周围的其他节点，减少数据丢失的风险。
6.4、具体实现与算法特性
-
普通哈希：
- 实现相对简单，通常使用固定的哈希函数和哈希表。
- 常见的哈希算法包括MD5、SHA-1等。
-
一致性哈希：
- 实现相对复杂，需要设计一个环状结构，并将节点和数据映射到环上。
- 使用了虚拟节点的概念来均衡负载。
- 在增加或移除节点时，只有相关的少量节点参与到拓扑的维护中，具有较好的可扩展性和容错性。
原文地址：https://blog.csdn.net/oopxiajun2011/article/details/143651685
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！