|
69
|
1 # Write a function taht maps
|
|
|
2 # Key string to one of N servers
|
|
|
3 from bisect import bisect_left
|
|
|
4 from hashlib import sha256
|
|
|
5
|
|
|
6 class Server:
|
|
|
7
|
|
|
8 def __init__(self):
|
|
|
9 self.id = str(sha256())
|
|
|
10
|
|
|
11 class ConsistentHash:
|
|
|
12 def __init__(self):
|
|
|
13 self.server = []
|
|
|
14 self.hash_key_to_server = {}
|
|
|
15 self.hash_range = 10000
|
|
|
16
|
|
|
17 def get_hash_pos(self, key: str) -> int:
|
|
|
18 x = sha256(bytes(key, "utf-8"))
|
|
|
19 return int.from_bytes(x.digest()[:8]) % self.hash_range
|
|
|
20
|
|
|
21 def add_server(self, server: Server):
|
|
|
22 self.server.append(server)
|
|
|
23 for i in range(len(self.server) + 1):
|
|
|
24 hash_key = self.get_hash_pos(server.id)
|
|
|
25 self.hash_key_to_server[hash_key] = i
|
|
|
26
|
|
|
27 def get_server(self, key):
|
|
|
28 hash_key = self.get_hash_pos(key)
|
|
|
29 return self.server[bisect_left(list(self.hash_key_to_server.keys()), hash_key)]
|
|
|
30
|
|
|
31 def remove_server(self, server):
|
|
|
32 hash_key = self.get_hash_pos(server.id)
|
