架构师训练营 W5 作业

# Python3
from bisect import insort_left, bisect
from hashlib import md5
from collections import defaultdict
class ConsistentHashing:
    def __init__(self, nodes, vnodes_num=200):
        self.nodes = set()  # store physical nodes
        self.vnodes_num = vnodes_num  # num of each physical node's virtuals nodes
        self.vnode_to_node = {}  # mapping vnode to node
        self.ring = {}  # mapping hashcode to vnode
        self._sorted_hashcode = []  # sorted hashcode of all vnodes
        for node in nodes:
            self.add_node(node)
    def add_node(self, node_name):
        self.nodes.add(node_name)
        self._generate_vnode(node_name)
    # generate virtual nodes and hash them to the ring
    def _generate_vnode(self, node):
        for i in range(self.vnodes_num):
            vnode = node + '_' + str(i)
            self.vnode_to_node[vnode] = node
            vnode_hashcode = self._hash(vnode)
            self.ring[vnode_hashcode] = vnode
            insort_left(self._sorted_hashcode, vnode_hashcode)
    # remove virtual nodes and remove the hashcodes in the ring
    def _remove_vnode(self, node):
        for vnode in self.vnode_to_node:
            if vnode.startswith(node):
                del self.vnode_to_node[vnode]
                vnode_hashcode = self._hash(vnode)
                del self.ring[vnode_hashcode]
                self._sorted_hashcode.remove(vnode_hashcode)
    def delete_node(self, node_name):
        self.nodes.remove(node_name)
        self._remove_vnode(node_name)
    def get_node_by_key(self, key):
        key_hashcode = self._hash(key)
        pos = bisect(self._sorted_hashcode, key_hashcode)
        # handle the last pos, should be the first since it's a ring
        if pos == len(self._sorted_hashcode):
            pos = 0
        return self.vnode_to_node[self.ring[self._sorted_hashcode[pos]]]
    def _hash(self, s):
        return int(md5(s.encode("utf-8")).hexdigest(), 16)
def std(nums):
    var = 0
    avg = sum(nums) / len(nums)
    for n in nums:
        var += (n - avg) ** 2
    return (var / len(nums)) ** 0.5
def cal(nodes_num, vnodes_num):
    print("testing {} nodes, each nodes with {} virtual nodes".format(
        nodes_num, vnodes_num))
    NUMS_SAMPLE = 1000000
    nodes = ['node-' + str(i + 1) for i in range(nodes_num)]
    ch = ConsistentHashing(nodes, vnodes_num)
    keys = [str(i) for i in range(NUMS_SAMPLE)]
    vnodes_counter = defaultdict(list)
    for k in keys:
        node = ch.get_node_by_key(k)
        vnodes_counter[node].append(node)
    nums = []
    for node, vnodes in sorted(vnodes_counter.items(), key=lambda x: (x[0], x[1])):
        print(node, len(vnodes), '{}%'.format(len(vnodes) * 100 / NUMS_SAMPLE))
        nums.append(len(vnodes))
    print("the standard deviation is: {}".format(str(std(nums))))
    print("----------------------------------------------------")
if __name__ == "__main__":
    cal(10, 50)
    cal(10, 100)
    cal(10, 150)
    cal(10, 200)
    cal(10, 500)
    cal(10, 1000)