分布式系统中的哈希算法

分布式系统(如 memcached 服务器集群)的一个最重要的内容是要保证同一个 key 每次都必须命中同一个服务器,本文介绍两种分布方式:

  • 简单hash分布(simple hashing)
  • 一致性hash分布(Consistent hashing)

简单hash分布

这个算法很简单:

server = serverlist[hash(key) % len(serverlist)]

python3-memcached 模块就是利用了这种算法。

一致性hash分布

简单 hash 分布算法有一个致命的缺点,就是扩展性和容错性, 当系统加入或减少服务器后, 因为服务器数量被改变,所有 key 值将会被重新映射, 造成整个系统不能高效运行。

一致性 hash 分布通过建立环形 hash 空间和服务器虚拟节点解决了上面的问题,提高了系统的扩展性和容错性。

环形 hash 空间是一个具有一定大小(比如 2^32 次方个值)的空间,其头尾相连,就像一个闭合的环形,如下图:

hash ring

我们可以通过某种 hash 算法将 key 映射到这个 hash 空间中:

hash ring map

将分布式服务器通过 hash 算法映射到这个 hash 空间中, 此后索引服务器时,根据 key 值绕着这个 hash 空间顺时针方向查询,第一个找到的服务器即为该 key 值对应的服务器:

hash ring map to server

当删除一个服务器节点时,不会影响其它 key:

hash ring delete server

当添加一个服务器节点时,只会重定向一段 key:

hash ring add server

通过 hash 算法并不能保证服务器均匀的分布在 hash 空间上,然后通过为一个服务器建立多个虚拟节点,进而减少这种不均匀性:

hash ring virtual server

python一致性hash分布算法实现

#!/usr/bin/python

import hashlib

class HashRing(object):
    def __init__(self, nodes=None, replicas=3):
        self.replicas = replicas
        self.ring = dict()
        self._sorted_keys = []
        if nodes:
            for node in nodes:
                self.add_node(node)

    def add_node(self, node):
        for i in range(0, self.replicas):
            key = self.gen_key('%s:%s' % (node, i))
            self.ring[key] = node
            self._sorted_keys.append(key)
        self._sorted_keys.sort()

    def remove_node(self, node):
        for i in range(0, self.replicas):
            key = self.gen_key('%s:%s' % (node, i))
            del self.ring[key]
            self._sorted_keys.remove(key)

    def get_node(self, string_key):
        return self.get_node_pos(string_key)[0]

    def get_node_pos(self, string_key):
        if not self.ring:
            return None, None
        key = self.gen_key(string_key)
        nodes = self._sorted_keys
        for i in range(0, len(nodes)):
            node = nodes[i]
            if key <= node:
                return self.ring[node], i
        return self.ring[nodes[0]], 0

    def gen_key(self, key):
        m = hashlib.md5()
        m.update(key.encode())
        return int(m.hexdigest(), 16)

    def get_nodes(self, string_key):
        if not self.ring:
            yield None, None
        node, pos = self.get_node_pos(string_key)
        for key in self._sorted_keys[pos:]:
            yield self.ring[key]
        while True:
            for key in self._sorted_keys:
                yield self.ring[key]


if __name__ == '__main__':

    memcache_servers = ['192.168.0.246:11212',
                        '192.168.0.247:11212',
                        '192.168.0.249:11212']

    ring = HashRing(memcache_servers)
    server = ring.get_node('node_key')
    print(server)

参考: