import hashlibimport randomimport statistics as stats
def _getVirtualNodes(number): samples = random.sample(range(0, 0xffffffff), number) return samples
def _hash(key): hashcode = int(hashlib.md5(key.encode('utf-8')).hexdigest(), 16) & 0xffffffff return hashcode
def _findInRing(item, ring): length = len(ring) middle = length // 2
if item > ring[-1] or item < ring[0]: return ring[0] if item == ring[middle - 1]: return ring[middle - 1] if item == ring[middle]: return ring[middle] if item < ring[middle - 1]: return _findInRing(item, ring[0: middle]) if item > ring[middle]: return _findInRing(item, ring[middle + 1:])
return ring[middle]
class Node: def __init__(self, name, virtualSets): self._name = name self._virtualNodes = virtualSets self._accessCounter = 0
def access(self): self._accessCounter += 1
def getVirtualNodeSet(self): return self._virtualNodes
def getAmount(self): return self._accessCounter
class ConsistencyHash: def __init__(self, virtualNodeNum = 0): self._virtualNodeNum = virtualNodeNum self._nodeList = [] self._nodes = dict() self._virtulaNodeMap = dict() self._totalNodes = set() self._ring = []
def _print(self): print('Node: {}'.format(self._nodeList)) print('vMap: {}'.format(self._virtulaNodeMap)) print('total: {}'.format(self._totalNodes)) print('ring: {}'.format(self._ring)) self._printAccess()
def _printTotalNodes(self): print('Total: {}'.format(len(self._totalNodes))) def _printAccess(self): for item in self._nodeList: node = self._nodes[item] print('{} : {}'.format(node._name, node._accessCounter))
def addNode(self, node): virtualNodes = _getVirtualNodes(self._virtualNodeNum + 1) for item in virtualNodes: self._virtulaNodeMap[item] = node
self._nodes[node] = Node(node, set(virtualNodes)) self._nodeList.append(node) self._totalNodes = self._totalNodes | set(virtualNodes) self._ring = sorted(self._totalNodes)
def removeNode(self, node):
if not node in self._nodeList: return removeSet = self._nodes[node].getVirtualNodeSet()
for key in removeSet: del self._virtulaNodeMap[key]
self._totalNodes = self._totalNodes - removeSet self._ring = sorted(self._totalNodes) del self._nodes[node] self._nodeList.remove(node)
def access(self, key): hashCode = _hash(key) whichNode = _findInRing(hashCode, self._ring) node = self._virtulaNodeMap[whichNode] self._nodes[node].access()
def calculateSTD(self): valueList = [] for item in self._nodeList: valueList.append(self._nodes[item]._accessCounter)
stdev = stats.stdev(valueList) return stdev
if __name__ == '__main__':
random.seed(1000) virtualNodeNum = [0, 50, 100, 150, 200, 250, 300] NodeNumber = 10 testTimes = 1000000
for item in virtualNodeNum:
print("Virtual Node Number: {}".format(item)) chash = ConsistencyHash(item)
for node in range(0, NodeNumber): chash.addNode("Node" + str(node))
chash._printTotalNodes() for times in range(0, testTimes): chash.access("key" + str(times)) chash._printAccess() stdev = chash.calculateSTD() print("std: {}\n".format(stdev))
评论