Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Consistent Distribution of users across servers
""" Consistent load-balancing.
We have a few servers and we want a load-balancer to
distribute incoming requests across them in a deterministic
and consistent way - without keeping any counter to make the
decision.
Removing a backend server should not impact users on other
servers.
Adding a backend will generate the redistribution of
users across other servers.
The goal is to come up with the best algorithm
for 1M users across 5 servers. Speed is a bonus.
Two known techniques:
- RendezVous : https://en.wikipedia.org/wiki/Rendezvous_hashing#Comparison_With_Consistent_Hashing
- Consistent Hashing: https://en.wikipedia.org/wiki/Consistent_hashing
Consistent Hashing implementation inspired by:
http://techspot.zzzeek.org/2012/07/07/the-absolutely-simplest-consistent-hashing-example
Also, good read on hashes:
http://programmers.stackexchange.com/questions/49550/which-hashing-algorithm-is-best-for-uniqueness-and-speed/145633#145633
"""
import hashlib
import bisect
from collections import defaultdict
import binascii
import time
from functools import wraps
class CollisionError(Exception):
pass
_collisions = {}
def catch_collision(func):
@wraps(func)
def _catch(key):
res = func(key)
if res in _collisions and key != _collisions[res]:
raise CollisionError('%s and %s with %s' % (key, _collisions[res],
func))
_collisions[res] = key
return res
return _catch
@catch_collision
def fnv32a(key):
hval = 0x811c9dc5
fnv_32_prime = 0x01000193
uint32_max = 2 ** 32
for s in key:
hval = hval ^ ord(s)
hval = (hval * fnv_32_prime) % uint32_max
return hval
@catch_collision
def sha512(key):
return long(hashlib.sha512(key).hexdigest(), 16)
@catch_collision
def sha256(key):
return long(hashlib.sha256(key).hexdigest(), 16)
@catch_collision
def md5(key):
return long(hashlib.md5(key).hexdigest(), 16)
class RendezVous(object):
def __init__(self, ips=None, hash=md5):
if ips is None:
ips = []
self.ips = ips
self._hash = hash
def __str__(self):
return '<RendezVous with %s hash>' % self._hash
def add(self, ip):
self.ips.append(ip)
def remove(self, ip):
self.ips.remove(ip)
def select(self, key):
high_score = -1
winner = None
for ip in self.ips:
score = self._hash("%s-%s" % (str(ip), str(key)))
if score > high_score:
high_score, winner = score, ip
elif score == high_score:
high_score, winner = score, max(str(ip), str(winner))
return winner
def _repl(name, index):
return '%s:%d' % (name, index)
class ConsistentHashing(object):
def __init__(self, ips=[], replicas=200, hash=md5):
self._ips = {}
self._hashed_ips = []
self.replicas = replicas
self._hash = hash
for ip in ips:
self.add(ip)
def __str__(self):
return '<ConsistentHashing with %s hash>' % self._hash
def add(self, ip):
for i in range(self.replicas):
sip = _repl(ip, i)
hashed = self._hash(sip)
self._ips[hashed] = sip
bisect.insort(self._hashed_ips, hashed)
def remove(self, ip):
for i in range(self.replicas):
sip = _repl(ip, i)
hashed = self._hash(sip)
del self._ips[hashed]
index = bisect.bisect_left(self._hashed_ips, hashed)
del self._hashed_ips[index]
def select(self, username):
hashed = self._hash(username)
start = bisect.bisect(self._hashed_ips, hashed,
hi=len(self._hashed_ips)-1)
return self._ips[self._hashed_ips[start]].split(':')[0]
NUM_USERS = 1000000
def run_test(servers, users):
selection = defaultdict(list)
for user in users:
user_db = servers.select(user)
selection[user_db].append(user)
print '===='
print('Distribution')
smallest = NUM_USERS + 1
biggest = 0
for db in selection:
size = len(selection[db])
if size < smallest:
smallest = size
if size > biggest:
biggest = size
print('%d users in %s' % (size, db))
print('span: %d' % (biggest - smallest))
# removing server 2 and 4
servers.remove('postgres2')
print '===='
selection = defaultdict(list)
for user in users:
user_db = servers.select(user)
selection[user_db].append(user)
smallest = NUM_USERS + 1
biggest = 0
for i, db in enumerate(selection):
size = len(selection[db])
if size < smallest:
smallest = size
if size > biggest:
biggest = size
print('%d users in %s' % (size, db))
print('span: %d' % (biggest - smallest))
if __name__ == '__main__':
users = ['%06d' % i for i in range(NUM_USERS)]
servers = ['postgres5', 'postgres2', 'postgres3', 'postgres4',
'postgres1']
for klass in (ConsistentHashing, RendezVous):
for hash in (md5, sha256, binascii.crc32, fnv32a, sha512):
try:
cluster = klass(list(servers), hash=hash)
except CollisionError:
print('Collision error with hash %s' % hash)
continue
print(cluster)
start = time.time()
try:
run_test(cluster, users)
except CollisionError:
print('Collision error..')
print('Took %d seconds' % (time.time() - start))
print
print
Owner

tarekziade commented May 14, 2016 edited

<ConsistentHashing with <function md5 at 0x1011b3140> hash>
====
Distribution
218247 users in postgres4
197079 users in postgres5
196812 users in postgres2
192469 users in postgres3
195393 users in postgres1
span: 25778
====
259155 users in postgres4
247254 users in postgres5
248181 users in postgres3
245410 users in postgres1
span: 13745
Took 8 seconds


<ConsistentHashing with <function sha256 at 0x1011aeed8> hash>
====
Distribution
217384 users in postgres4
192092 users in postgres5
190393 users in postgres2
191161 users in postgres3
208970 users in postgres1
span: 26991
====
247301 users in postgres4
238765 users in postgres5
259807 users in postgres3
254127 users in postgres1
span: 21042
Took 8 seconds


<ConsistentHashing with <built-in function crc32> hash>
====
Distribution
171316 users in postgres4
231019 users in postgres5
230567 users in postgres2
162721 users in postgres3
204377 users in postgres1
span: 68298
====
223819 users in postgres4
317162 users in postgres5
210481 users in postgres3
248538 users in postgres1
span: 106681
Took 4 seconds


<ConsistentHashing with <function fnv32a at 0x1011aef50> hash>
====
Distribution
123996 users in postgres4
235235 users in postgres5
324004 users in postgres2
191223 users in postgres3
125542 users in postgres1
span: 200008
====
124818 users in postgres4
360886 users in postgres5
351909 users in postgres3
162387 users in postgres1
span: 236068
Took 6 seconds


<ConsistentHashing with <function sha512 at 0x1011aee60> hash>
====
Distribution
218262 users in postgres4
224372 users in postgres5
187891 users in postgres2
180580 users in postgres3
188895 users in postgres1
span: 43792
====
268997 users in postgres4
278203 users in postgres5
222944 users in postgres3
229856 users in postgres1
span: 55259
Took 10 seconds


<RendezVous with <function md5 at 0x1011b3140> hash>
====
Distribution
199971 users in postgres4
199994 users in postgres5
199315 users in postgres2
201333 users in postgres3
199387 users in postgres1
span: 2018
====
249819 users in postgres4
249765 users in postgres5
251381 users in postgres3
249035 users in postgres1
span: 2346
Took 21 seconds


<RendezVous with <function sha256 at 0x1011aeed8> hash>
====
Distribution
199955 users in postgres4
200206 users in postgres5
200333 users in postgres2
199431 users in postgres3
200075 users in postgres1
span: 902
====
249874 users in postgres4
250312 users in postgres5
249492 users in postgres3
250322 users in postgres1
span: 830
Took 26 seconds


<RendezVous with <built-in function crc32> hash>
====
Distribution
125000 users in postgres4
250000 users in postgres5
250000 users in postgres2
125000 users in postgres3
250000 users in postgres1
span: 125000
====
125000 users in postgres4
500000 users in postgres5
125000 users in postgres3
250000 users in postgres1
span: 375000
Took 8 seconds


<RendezVous with <function fnv32a at 0x1011aef50> hash>
====
Distribution
199691 users in postgres4
200721 users in postgres5
201455 users in postgres2
199780 users in postgres3
198353 users in postgres1
span: 3102
====
249691 users in postgres4
252724 users in postgres5
249953 users in postgres3
247632 users in postgres1
span: 5092
Took 32 seconds


<RendezVous with <function sha512 at 0x1011aee60> hash>
====
Distribution
200326 users in postgres4
200590 users in postgres5
200024 users in postgres2
199341 users in postgres3
199719 users in postgres1
span: 1249
====
250431 users in postgres4
250731 users in postgres5
249384 users in postgres3
249454 users in postgres1
span: 1347
Took 32 seconds
Owner

tarekziade commented May 18, 2016

And the winner is... RendezVous + sha256

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment