Models consistent hash bias

chash.py

#!/usr/bin/python

import argparse
import hashlib
import struct
import sys

p = argparse.ArgumentParser()
p.add_argument('nodes', type=int)
p.add_argument('vnodes', type=int, nargs='?', default=256)
p.add_argument('runs', type=int, nargs='?', default=1)
args = p.parse_args()

def make_hash(val, seed):
    h = hashlib.sha256()
    h.update(seed)
    h.update(val)
    return h.digest()[:8]


node_ids = []
for i in xrange(args.nodes):
    node_ids.append(hashlib.md5(str(i)).hexdigest()[:22])

tot = 0
for run in xrange(args.runs):
    seed = struct.pack('Q', run)

    vnodes = []
    for n in node_ids:
        vnode_value = seed
        for _ in xrange(args.vnodes):
            vnode_value = make_hash(n, vnode_value)
            vnodes.append((n, struct.unpack('Q', vnode_value)[0]))

    vnodes.sort(key=lambda x: x[1])

    spans = {}
    spans[vnodes[0][0]] = (1<<64) - vnodes[-1][1] + vnodes[0][1]
    for i in xrange(1, len(vnodes)):
        n, l = vnodes[i], vnodes[i-1]
        spans[l[0]] = spans.get(l[0], 0) + (n[1] - l[1])
    c = spans.items()
    c.sort(key=lambda x: x[1])
    if args.runs == 1:
        for v in c:
            print "id=%-22s c=%d" % v
    spread = float(c[-1][1]) / float(c[0][1])
    print "spread: %.4f" % (spread)
    tot += spread

if args.runs > 1:
    print "avg: %.4f" % (tot / args.runs)