Week 05 作业

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))
    node_list = []
    for node, vnode in vnode_info.items():
        print("{}={}%".format(node, len(vnode) / case_num * 100))
        node_list.append(len(vnode) / case_num * 100)
    print(node_list)
    avg_node = sum(node_list) / len(node_list)
    avg_node_list = [node - avg_node for node in node_list]
    std = sum(map(lambda x: x ** 2, avg_node_list))
    print("std:", std)
if __name__ == '__main__':
    test_consistent_hash(1000000, 200)