Node.js module for performing fast rendezvous (HRW) hashing with skeleton - Can efficiently handle a large number of machines/sites.
This approach is slower than consistent hashing but provides much more even distribution of keys across sites - Particularly when there are a large number of sites and keys; the distribution gets progressively better as you add more keys. It can be configured to prioritize different features (e.g. distribution, performance, remapping %).
Last test results:
API
When adding a site twice during instantiation
✓ should not contain duplicate sites
When adding a site a second time after instantiation
✓ should not contain duplicate sites
When adding a site as a string argument instead of an array
✓ should add the site
When trying to find a site when the sites list is empty
✓ should not throw an error
✓ result should be null
When trying to remove a site which is not in the list
✓ should not throw an error
✓ should have removed the sites that were in the sites list
When trying to remove a single site as a string instead of an array
✓ should not throw an error
✓ should have removed the site
When passing null as the argument to findSite
✓ should not throw an error
Calling setSites with an array of sites should replace all existing sites
✓ should map keys across latest sites list
Calling setSites with a single site string should replace all existing sites
✓ should not throw error
✓ should map keys across latest sites list
Distribution
SRH distributes 1000 keys between 3 sites
✓ should return 1000 valid targets
Key distribution difference between min and max sites: 1.1596091205211727
✓ should distribute keys evenly between sites
Duration: 2 ms
✓ should take less than 50 ms to complete on a decent machine
SRH distributes 1000 keys between 4 sites after one new site is added
Key distribution difference between min and max sites: 1.150214592274678
✓ should distribute keys evenly between sites after adding the new site
Moved 240 keys out of 1000
✓ less than 28% of keys should have changed site after adding the new site
SRH distributes 1000 keys between 3 sites after the host3 site is removed
Key distribution difference between min and max sites: 1.1596091205211727
✓ should distribute keys evenly between sites after removing the site
Moved 261 keys out of 1000
✓ less than 28% of keys should have changed site after removing the site
SRH distributes 10000 keys between 20 sites
✓ should return 10000 valid targets
Key distribution difference between min and max sites: 1.1695278969957081
✓ should distribute keys evenly between sites
Duration: 114 ms
✓ should take less than 500 ms to complete on a decent machine
SRH distributes 20000 keys between 21 sites after one new site is added
Key distribution difference between min and max sites: 1.118232044198895
✓ should distribute keys evenly between sites after adding the new site
Moved 972 keys out of 20000
✓ less than 5% of keys should have changed site after adding the new site
SRH distributes 40000 keys between 100 sites after one new site is added
Key distribution difference between min and max sites: 1.2706552706552707
✓ should distribute keys evenly between sites after adding the new site
Moved 784 keys out of 40000
✓ less than 2.5% of keys should have changed site after adding the new site
SRH distributes 10000 keys between 20 sites after the host9 site is removed
Key distribution difference between min and max sites: 1.1404255319148937
✓ should distribute keys evenly between sites after removing the site
Moved 452 keys out of 10000
✓ less than 5.5% of keys should have changed site after removing the site
SRH distributes 40000 keys between 96 sites after the host11 site is removed
Key distribution difference between min and max sites: 1.2338709677419355
✓ should distribute keys evenly between sites after removing the site
Moved 775 keys out of 40000
✓ less than 2.5% of keys should have changed site after removing the site
SRH distributes 40000 keys between 1000 sites after the host4 site is removed
Moved 150 keys out of 40000
✓ less than 0.5% of keys should have changed site after removing the site
SRH distributes 10000 keys between 20 sites after the host9, host10 and host22 sites are removed
Key distribution difference between min and max sites: 1.1373390557939915
✓ should distribute keys evenly between sites after removing the sites
Moved 1251 keys out of 10000
✓ less than 15% of keys should have changed site after removing the sites
SRH distributes 10000 keys between 33 sites after the single cluster splits in two
✓ should split the single cluster in two
Keys owned by more than one site: 0 before the split, 0 after
✓ should not have any key owned by more than one site before or after the split
Moved 4633 keys out of 10000
✓ less than 50% of keys should have changed site after the split
SRH distributes 10000 keys between 55 sites after one of the two clusters splits
✓ should split one of the two clusters in two
Moved 3010 keys out of 10000
✓ less than 35% of keys should have changed site after the split
SRH distributes 10000 keys between 70 sites after one of the three clusters splits
✓ should split one of the three clusters in two
Moved 2401 keys out of 10000
✓ less than 28% of keys should have changed site after the split
SRH adds one site at a time to site lists which do not split a cluster
✓ should leave the cluster layout unchanged at every step
33 sites: moved 3.94% against a minimum of 2.94% (1.34x)
40 sites: moved 3.05% against a minimum of 2.44% (1.25x)
47 sites: moved 2.71% against a minimum of 2.08% (1.30x)
53 sites: moved 2.49% against a minimum of 1.85% (1.34x)
✓ should move less than 1.5 times the minimum number of keys at every step
Fanout
SRH distributes 20000 keys between 40 sites with a fanout of 9
✓ should hash each branch separately rather than slicing a single digest
✓ should return 20000 valid targets
Key distribution difference between min and max sites: 1.206208425720621
✓ should distribute keys evenly between sites
SRH distributes 20000 keys between 300 sites with a fanout of 9
✓ should walk more than one level of the skeleton
Sites without keys: 0 out of 300
✓ should give every site a share of the keys
Time complexity
SRH distributes 10000 keys in O(log n) time with respect to the number of sites
Duration with 100 sites: 146 ms
Duration with 1000 sites: 171 ms
✓ should be able to handle 10 times the number of sites while using less than 50% extra time
49 passing (17s)