Created
June 20, 2020 07:26
-
-
Save bobby569/46fa88e1a8ae25742c65642e2d5dad82 to your computer and use it in GitHub Desktop.
Simple scalable entry-to-machine assignment policy using consistent hashing.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import bisect | |
| import hashlib | |
| def my_hash(key): | |
| '''Return a hash in the range [0,1).''' | |
| return (int(hashlib.md5(key.encode('utf-8')).hexdigest(), 16) % 1000000) / 1000000 | |
| class ConsistentHashing: | |
| ''' | |
| ConsistentHashing(n, r) creates a consistent hash object for a | |
| cluster of size n, using r replicas. | |
| The class has a single instance method, get_machine(key), which | |
| returns the number of the machine to which key should be mapped. | |
| ''' | |
| def __init__(self, num_machines=1, num_replicas=1): | |
| self.num_machines = num_machines | |
| self.num_replicas = num_replicas | |
| hash_tuples = [(j, k, my_hash(str(j) + "_" + str(k))) | |
| for j in range(self.num_machines) | |
| for k in range(self.num_replicas)] | |
| # Sort the hash tuples based on hash values | |
| hash_tuples.sort(key=lambda x: x[2]) | |
| self.hash_tuples = hash_tuples | |
| def get_machine(self, key): | |
| '''Returns the number of the machine which key gets sent to''' | |
| h = my_hash(key) | |
| # edge case where cycle past hash value of 1 and back to 0 | |
| if h > self.hash_tuples[-1][2]: | |
| return self.hash_tuples[0][0] | |
| hash_values = list(map(lambda x: x[2], self.hash_tuples)) | |
| index = bisect.bisect_left(hash_values, h) | |
| return self.hash_tuples[index][0] | |
| def main(): | |
| ch = ConsistentHashing(7,3) | |
| print("machine, replica, hash-value:") | |
| for j, k, h in ch.hash_tuples: | |
| print("%4d,%8d,%14.6f" % (j, k, h)) | |
| while True: | |
| print("\nPlease enter a key:") | |
| key = input() | |
| print("\nKey \"%s\" maps to hash %.6f, and so to machine %d" \ | |
| % (key, my_hash(key), ch.get_machine(key))) | |
| if __name__ == "__main__": | |
| main() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment