架构师训练营第五周作业 1

import bisect
import hashlib
class ConsistentHashRing():
    def __init__(self, replicates = 100):
        """ Create a new Consisten Hashing ring
        :param replicates: :number of virtual nodes per node
        """
        self.replicates = replicates
        self.keys = []
        self.nodes = {}
    def hash(self, key):
        """Given a string key, return a hash value"""
        m = hashlib.sha256()
        m.update(bytes(key,'utf-8'))
        return int(m.hexdigest(), 16)
    def virtual_iterator(self, nodename):
        """Given a node name, return an iterable of replica hashes"""
        return (self.hash("%s:%s" %(nodename, i)) for i in range(self.replicates))
    def __setitem__(self, nodename, node):
        """Add a node, giveing its name"""
        for hash in self.virtual_iterator(nodename):
            if hash in self.nodes:
                raise ValueError("Node name %s is already present" %nodename)
            self.nodes[hash] = node
            bisect.insort(self.keys, hash)
    def __delitem__(self, nodename):
        """Remove a node, given its name"""
        for hash in self.virtual_iterator(nodename):
            del self.nodes[hash]
            index = bisect.bisect_left(self.keys, hash)
            del self.keys[index]
    def __getitem__(self, item):
        """return a node, given a key"""
        hash = self.hash(item)
        start = bisect.bisect(self.keys, hash)
        if start == len(self.keys):
            start = 0
        return self.nodes[self.keys[start]]