likes
comments
collection
share

什么是一致性哈希？

作者站长头像
站长
· 阅读数 7

一致性哈希（Consistent Hashing）是一种特殊的哈希算法，主要用于分布式系统中，以提高系统的可扩展性和稳定性。一致性哈希最初是为了解决网络服务中的分布式缓存失效问题而提出的，但它现在被广泛应用于各种分布式系统中，比如分布式存储、负载均衡等。

简单介绍

原理：

  1. 环形哈希空间：一致性哈希将哈希值空间组织成一个虚拟的环状结构。假设哈希函数的结果是一个 m 位的整数，那么哈希值的范围就是 0 到 2^m - 1，这些值在一致性哈希中形成一个环。

  2. 节点的映射：在这个环上，每个服务器（或缓存节点）都通过哈希函数计算得到一个或多个哈希值，这些哈希值确定了这些服务器在环上的位置。

  3. 数据的定位：当需要查找一个键（key）时，系统会将这个键也通过相同的哈希函数映射到环上的一个位置，然后从这个位置顺时针找到的第一个服务器节点就是该键所属的节点。

特点：

  • 可扩展性：当系统中增加或删除一个服务器节点时，只影响其相邻节点的数据分配，大部分数据仍然能够在原有的节点上找到，这极大地减少了节点变更时的数据迁移量，提高了系统的可扩展性。

  • 负载均衡：一致性哈希算法能够在多个服务器节点之间较为均匀地分配数据，从而达到负载均衡的效果。通过引入“虚拟节点”概念，可以进一步优化数据的分布，使得节点的增减变动对整个系统的影响更小。

  • 高可用性：在面对节点故障时，一致性哈希能够通过重新映射受影响的数据项到其他节点，以此来保证系统的高可用性。

简单案例

在Spring Boot项目中使用一致性哈希。以下是一个使用一致性哈希来决定数据应该存储在哪个缓存节点的示例，引入了虚拟节点以提高分布均匀性。

首先，我们定义一个一致性哈希的工具类，这个类负责实现一致性哈希逻辑：

import java.util.Collection;
import java.util.SortedMap;
import java.util.TreeMap;
public class ConsistentHash<T> {
    private final HashFunction hashFunction; // 一个实现了HashFunction接口的哈希函数，用于计算节点和数据的哈希值。
    private final int numberOfReplicas; // 虚拟节点的数量，增加虚拟节点可以使数据更均匀地分布在各个节点上。
    private final SortedMap<Integer, T> circle = new TreeMap<>(); // 一个有序映射，用来存储虚拟节点和实际节点的映射关系。键是哈希值，值是对应的节点。
    
    // 接受一个哈希函数，虚拟节点数量，和一组初始节点。构造器将每个节点添加到哈希环中。
    public ConsistentHash(HashFunction hashFunction, int numberOfReplicas, Collection<T> nodes) {
        this.hashFunction = hashFunction;
        this.numberOfReplicas = numberOfReplicas;

        for (T node : nodes) {
            add(node);
        }
    }

    // 通过对节点toString()结果加上不同的索引i并计算哈希值，为同一个节点创建多个虚拟节点，这些虚拟节点分布在环上的不同位置。
    public void add(T node) {
        for (int i = 0; i < numberOfReplicas; i++) {
            circle.put(hashFunction.hash(node.toString() + i), node);
        }
    }

    public void remove(T node) {
        for (int i = 0; i < numberOfReplicas; i++) {
            circle.remove(hashFunction.hash(node.toString() + i));
        }
    }

    // 用于确定给定键（比如一个数据的键值）应由哪个节点负责。首先计算键的哈希值，然后在环上找到最近的一个大于等于该哈希值的虚拟节点，其对应的实际节点就是目标节点。如果没有找到，就使用环上的第一个节点（实现环形结构）
    public T get(Object key) {
        if (circle.isEmpty()) {
            return null;
        }
        int hash = hashFunction.hash(key);
        if (!circle.containsKey(hash)) {
            SortedMap<Integer, T> tailMap = circle.tailMap(hash);
            hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
        }
        return circle.get(hash);
    }

    public interface HashFunction {
        int hash(Object key);
    }
}

然后，你可以在你的Spring Boot服务中使用这个ConsistentHash类来决定某个键应该被存储在哪个节点上。比如，在一个分布式缓存的场景中，根据缓存的键来确定数据应该存储到哪个缓存服务器：

import java.util.List;

public class CacheService {
    private ConsistentHash<String> consistentHash;

    public CacheService(List<String> nodeAddresses) {
        // 初始化一致性哈希环，这里简单地使用String的hashCode作为哈希函数，实际应用中可能需要更复杂的哈希函数
        consistentHash = new ConsistentHash<>(String::hashCode, 3, nodeAddresses);
    }

    public String getCacheNode(String key) {
        return consistentHash.get(key);
    }

    public void addCacheNode(String node) {
        consistentHash.add(node);
    }

    public void removeCacheNode(String node) {
        consistentHash.remove(node);
    }
}

这个CacheService类可以被注入到需要进行缓存操作的Spring Boot服务中，以决定数据应该被存储或检索自哪个节点。

总结

一致性哈希主要应用于分布式系统中，以解决节点的动态增减导致的数据重新分配问题。这种算法通过有效地分布数据和负载，提高了系统的可扩展性和稳定性。以下是一些典型的应用场景：

  1. 分布式缓存：在分布式缓存系统中，如Redis集群、Memcached等，一致性哈希能够帮助系统均匀地分布缓存数据到不同的节点上。当缓存集群扩展或缩小时，一致性哈希确保只有少量的数据需要迁移，大大减少了因节点变更导致的缓存失效。

  2. 分布式存储系统：在分布式数据库或文件系统中，一致性哈希帮助确定数据片段的存储位置。这样可以在增加或减少存储节点时最小化数据迁移，例如在Amazon的DynamoDB或Google的Bigtable中的应用。

  3. 负载均衡：在分布式网络服务中，一致性哈希可以帮助将用户请求均匀分配到多个服务器节点上。这不仅确保了服务的高可用性，也提高了资源的利用效率。

  4. 分布式会话或状态管理：在需要跨多个服务器节点共享会话或状态的应用中，一致性哈希可以确定用户的会话或状态存储在哪个节点，以保持会话的持久性和一致性。

  5. P2P网络：在P2P网络和分布式哈希表（DHT）中，如BitTorrent的Tracker系统或Kademlia网络，一致性哈希用于确定资源或节点的位置，以实现高效的资源定位和分布。

  6. 数据分片和复制：在需要将数据分片并在多个节点之间进行复制的系统中，一致性哈希有助于均衡每个节点的数据量和工作负载，同时在节点故障时简化数据的恢复过程。

转载自:https://juejin.cn/post/7346519210723835938
评论
请登录