Week05 作业

import hashlib
from collections import defaultdict
from bisect import bisect

servers = [
    "10.10.1.1",
    "10.10.1.2",
    "10.10.1.3",
    "10.10.1.4",
    "10.10.1.5",
    "10.10.1.6",
    "10.10.1.7",
    "10.10.1.8",
    "10.10.1.9",
    "10.10.1.10"
]


class HashRing:
    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):
        """
        Adds a `node` to the hash ring (including a number of replicas)
        """
        for i in range(self.replicas):
            virtual_node = f"{node}#{i}"
            key = self.gen_key(virtual_node)
            self.ring[key] = node
            self._sorted_keys.append(key)
            # print(f"{virtual_node} --> {key} --> {node}")

        self._sorted_keys.sort()
        # print([self.ring[key] for key in self._sorted_keys])

    def remove_node(self, node):
        """
        Removes `node` from the hash ring and its replicas
        """
        for i in range(self.replicas):
            key = self.gen_key(f"{node}#{i}")
            del self.ring[key]
            self._sorted_keys.remove(key)

    def get_node(self, string_key):
        """
        Given a string key a corresponding node in the hash ring is returned.

        If the hash ring is empty, `None` is returned.
        """
        return self.get_node_pos(string_key)[0]

    def get_node_pos(self, string_key):
        """
        Given a string key a corresponding node in the hash ring is returned
        along with it's position in the ring.

        If the hash ring is empty, (`None`, `None`) is returned.
        """
        if not self.ring:
            return None, None

        key = self.gen_key(string_key)
        nodes = self._sorted_keys
        pos = bisect(nodes, key) % len(nodes)

        return self.ring[nodes[pos]], pos

    def gen_key(self, string_key):
        """
        Given a string key it returns a long value, this long value represents
        a place on the hash ring
        """
        m = hashlib.md5()
        m.update(string_key.encode('utf-8'))
        return m.hexdigest()


def test_consistent_hash(case_num, replicas):
    hr = HashRing(servers, replicas)
    vnode_info = defaultdict(list)

    for i in range(case_num):
        node = hr.get_node(str(i))
        vnode_info[node].append(i)
        print("{}:{}".format(i, node))

    for node, vnode in vnode_info.items():
        print("{}={}%".format(node, len(vnode) / case_num * 100))

if __name__ == '__main__':
    test_consistent_hash(1000000, 200)