分析hash_ring源码(一致性哈希算法)细节

hash_ring是python的一个模块，实现了一致性哈希算法

本文对一致性哈希算法本身算法的描述不多，如果不熟英文好的可以看看Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web和wiki Consistent_hashing两篇文档。当然也可以看看一致性哈希算法（Consistent Hashing）的讲解，这篇文章的理论讲的很详细。

一致性哈希算法

一致性哈希算法是在哈希算法基础上，能够以较小的代价处理服务node动态增减的算法。在分布式系统设计中很重要。

特性

一致性哈希算法的特性：

  • 冗余少
  • 负载均衡
  • 过渡平滑
  • 存储均衡
  • 关键词单调

一致性哈希算法的应用

  • 亚马逊的云存储系统Dynamo的数据划分功能模块
  • memcache客户端使用了一致性哈希算法进行数据存储节点的选择

具体实现

Python模块hash_ring

代码来自Python2.7.18的模块hash_ring

网上有一些同学分享了实现一致性哈希算法的Python版本代码，算法本身实现没问题，但是我注意到有一些细节还需要打磨，当然别人可能只是分享了示范性代码，并没有考虑过多细节。

我就以模块hash_ring的代码来一波分析。

初始化
  • 使用md5计算哈希值；
  • ring是kv为node哈希值和node的dict，_sorted_keys是node哈希值的有序列表。_sorted_keys和ring共同构成了哈希环。通过stringkey的哈希值在_sorted_keys中查找node的哈希值，然后在ring中查找node哈希值对应的node。

初始化参数的nodes是服务名字列表，每个元素是string类型；weights每个服务的权重，key是node，values是权重。
在_generate_circle函数中生成哈希环。

通过以下两点来保障虚拟结点会按照权重来随机分布：

  • factor是由node的权重来生成，用来计算虚拟结点个数。为什么选40呢？应该是个经验数值，结果就是所有node的factor平均值是40。factor * 3就是node的虚拟结点总个数。这种方式可以让虚拟结点数量变的比较多，避免了一个结点挂了后，请求一股脑全跑另一个结点上。
  • 使用md5来生成哈希值，且得到的是int类型，有些人选择使用long类型，Python的int的比较速度要比long的速度快。
get_node

根据string_key的哈希值在_sorted_keys中查找node的哈希值。我看有些同学使用for循环遍历来查找，这种效率是O(n)。这里使用的是bisect来查找，这是个二分查找，效率是O(logn)。

iterate_nodes

hash_ring没有提供增删结点，但是提供了iterate_nodes，这返回的是一个迭代器，如果找到的第一个node请求失败就开始尝试下一个，直到成功为止。
memcache_ring._get_server就是对iterate_nodes的应用。这就是memcache客户端的Python版本实现。

hash_ring.py完整代码

# -*- coding: utf-8 -*-

import math
import sys
from bisect import bisect

if sys.version_info >= (2, 5):
    import hashlib
    md5_constructor = hashlib.md5
else:
    import md5
    md5_constructor = md5.new

class HashRing(object):

    def __init__(self, nodes=None, weights=None):
        self.ring = dict()
        self._sorted_keys = []

        self.nodes = nodes

        if not weights:
            weights = {}
        self.weights = weights

        self._generate_circle()

    def _generate_circle(self):
        """Generates the circle.
        """
        total_weight = 0
        for node in self.nodes:
            total_weight += self.weights.get(node, 1)

        for node in self.nodes:
            weight = 1

            if node in self.weights:
                weight = self.weights.get(node)

            factor = math.floor((40*len(self.nodes)*weight) / total_weight);

            for j in xrange(0, int(factor)):
                b_key = self._hash_digest( '%s-%s' % (node, j) )

                for i in xrange(0, 3):
                    key = self._hash_val(b_key, lambda x: x+i*4)
                    self.ring[key] = node
                    self._sorted_keys.append(key)

        self._sorted_keys.sort()

    def get_node(self, string_key):
        pos = self.get_node_pos(string_key)
        if pos is None:
            return None
        return self.ring[ self._sorted_keys[pos] ]

    def get_node_pos(self, string_key):
        if not self.ring:
            return None

        key = self.gen_key(string_key)

        nodes = self._sorted_keys
        pos = bisect(nodes, key)

        if pos == len(nodes):
            return 0
        else:
            return pos

    def iterate_nodes(self, string_key, distinct=True):
        if not self.ring:
            yield None, None

        returned_values = set()
        def distinct_filter(value):
            if str(value) not in returned_values:
                returned_values.add(str(value))
                return value

        pos = self.get_node_pos(string_key)
        for key in self._sorted_keys[pos:]:
            val = distinct_filter(self.ring[key])
            if val:
                yield val

        for i, key in enumerate(self._sorted_keys):
            if i < pos:
                val = distinct_filter(self.ring[key])
                if val:
                    yield val

    def gen_key(self, key):
        b_key = self._hash_digest(key)
        return self._hash_val(b_key, lambda x: x)

    def _hash_val(self, b_key, entry_fn):
        return (( b_key[entry_fn(3)] << 24)
                |(b_key[entry_fn(2)] << 16)
                |(b_key[entry_fn(1)] << 8)
                | b_key[entry_fn(0)] )

    def _hash_digest(self, key):
        m = md5_constructor()
        m.update(key)
        return map(ord, m.digest())

memcache_ring.py

import memcache
import types

from hash_ring import HashRing

class MemcacheRing(memcache.Client):
    """Extends python-memcache so it uses consistent hashing to
    distribute the keys.
    """

    def __init__(self, servers, *k, **kw):
        self.hash_ring = HashRing(servers)

        memcache.Client.__init__(self, servers, *k, **kw)

        self.server_mapping = {}
        for server_uri, server_obj in zip(servers, self.servers):
            self.server_mapping[server_uri] = server_obj

    def _get_server(self, key):
        if type(key) == types.TupleType:
            return memcache.Client._get_server(key)

        for i in range(self._SERVER_RETRIES):
            iterator = self.hash_ring.iterate_nodes(key)
            for server_uri in iterator:
                server_obj = self.server_mapping[server_uri]
                if server_obj.connect():
                    return server_obj, key

        return None, None

C++实现

代码来自Consistent-Hash-Ring C++

  • 使用std::map来实现哈希环，std::map的底层是红黑树，红黑树的增删以及lower_bound的时间复杂度都是O(logn)
  • replicas_代表虚拟结点个数

时间复杂度（不考虑增减结点导致的数据迁移）：
AddNode：O(replicas_*logn)
RemoveNode：O(replicas_*logn)
GetNode：O(logn)


template <class Node, class Data, class Hash = HASH_NAMESPACE::hash<const char*> >
class HashRing
{
public:
    typedef std::map<size_t, Node> NodeMap;
 
    HashRing(unsigned int replicas)
        : replicas_(replicas), hash_(HASH_NAMESPACE::hash<const char*>())
    {
    }
 
    HashRing(unsigned int replicas, const Hash& hash)
        : replicas_(replicas), hash_(hash)
    {
    }
 
    size_t AddNode(const Node& node);
    void RemoveNode(const Node& node);
    const Node& GetNode(const Data& data) const;
 
private:
    NodeMap ring_;
    const unsigned int replicas_;
    Hash hash_;
};
 
template <class Node, class Data, class Hash>
size_t HashRing<Node, Data, Hash>::AddNode(const Node& node)
{
    size_t hash;
    std::string nodestr = Stringify(node);
    for (unsigned int r = 0; r < replicas_; r++) {
        hash = hash_((nodestr + Stringify(r)).c_str());
        ring_[hash] = node;
    }
    return hash;
}
 
template <class Node, class Data, class Hash>
void HashRing<Node, Data, Hash>::RemoveNode(const Node& node)
{
    std::string nodestr = Stringify(node);
    for (unsigned int r = 0; r < replicas_; r++) {
        size_t hash = hash_((nodestr + Stringify(r)).c_str());
        ring_.erase(hash);
    }
}
 
template <class Node, class Data, class Hash>
const Node& HashRing<Node, Data, Hash>::GetNode(const Data& data) const
{
    if (ring_.empty()) {
        throw EmptyRingException();
    }
    size_t hash = hash_(Stringify(data).c_str());
    typename NodeMap::const_iterator it;
    // Look for the first node >= hash
    it = ring_.lower_bound(hash);
    if (it == ring_.end()) {
        // Wrapped around; get the first node
        it = ring_.begin();
    }
    return it->second;
}

对比

对比Python版和C++版的实现，对node的增删查效率都是O(logn)。Python使用了一个list和一个dict，dict的底层实现是哈希表（具体实现可以参考CPython—dict源码详解），消耗的内存比较多。C++使用std::map，底层是红黑树，相对而言内存消耗更少点。
抛开语言层面的差异，用红黑树来作为一致性哈希算法的数据结构是比较好的。

引用

Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web
wiki Consistent_hashing
Consistent-Hash-Ring C++
Python模块—bisect

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容