CHRing - A Skiplist based Consistent Hash Ring
 
 

CHRing - A Skiplist based Consistent Hash Ring

May 26, 2025
development
algorithms, Consistent Hashing, C, bngx, IXDP

The Ingredients #

The CHRing API # 

#define CHRingNOSERVER UINT32_MAX

CHRingNOSERVER is returned by CHRingLookup() and CHRingLookupCCW() when the ring is empty, and by CHRingLookupExact() when there is no match for the exact hash (or key).

CHRing* CHRingCreate();
void CHRingDestroy(CHRing * chring);

void CHRingInfo(CHRing * chring);
uint32_t CHRingNodes(CHRing * chring);
uint32_t CHRingCollisions(CHRing * chring);
uint32_t CHRingServerWeight(CHRing * chring, uint32_t server_id);

void CHRingInsert(CHRing * chring, uint32_t server_id, uint32_t server_weight);
void CHRingDelete(CHRing * chring, uint32_t server_id);

uint32_t CHRingLookup(CHRing * chring, uint64_t hash);
uint32_t CHRingLookupExact(CHRing * chring, uint64_t hash);
uint32_t CHRingLookupCCW(CHRing * chring, uint64_t hash);

void CHRingDistributionTest(CHRing * chring, uint32_t nservers, uint32_t lookups);
void CHRingDistributionTestCCW(CHRing * chring, uint32_t nservers, uint32_t lookups);

Related RPCL Words # 

ok chring. .i 
chring.collisions                return CHRing collisions ( - n )
chring.delete                    delete server from CHRing ( server_id - )
chring.dtest                     perform distribution test ( nservers lookups - )
chring.dtest-ccw                 perform distribution test counterclockwise ( nservers lookups - )
chring.dtest-random              perform random distribution test ( nservers lookups - )
chring.info                      show CHRing info ( - )
chring.insert                    insert server with weight ( server_id weight - )
chring.lookup                    lookup CHRing ( hash - server_id )
chring.lookup-ccw                lookup CHRing counterclockwise ( hash - server_id )
chring.lookup-exact              lookup CHRing exactly ( hash - server_id )
chring.multi-insert              insert n servers with same weight, start = 0 ( n weight - )
chring.nodes                     return number of CHRing nodes ( - n )
chring.print                     print CHRing contents ( - )
chring.print-reversed            print CHRing contents reversed ( - )
chring.rndhash                   generate random 8 byte hash ( - data )
chring.server-weight             return server weight ( server_id - weight )
ok ▂

Detailed examples can be found here: rpcl.inlab.net/built-in-words/#chringcollisions

Distribution Testing #

A distribution test with 20 servers weight 10000 and 1000000 lookups with random hashes looks like this:

ok 20 10000 chring.multi-insert
ok timer-start 20 1000000 chring.dtest timer-show 
       id    weight      hits
--------- --------- ---------
        0     10000     49812   4.9812%
        1     10000     51238   5.1238%
        2     10000     50272   5.0272%
        3     10000     49636   4.9636%
        4     10000     50704   5.0704%
        5     10000     50779   5.0779%
        6     10000     49949   4.9949%
        7     10000     48549   4.8549%
        8     10000     49435   4.9435%
        9     10000     50775   5.0775%
       10     10000     49597   4.9597%
       11     10000     49840   4.9840%
       12     10000     50878   5.0878%
       13     10000     49586   4.9586%
       14     10000     49370   4.9370%
       15     10000     50032   5.0032%
       16     10000     50868   5.0868%
       17     10000     48809   4.8809%
       18     10000     49967   4.9967%
       19     10000     49904   4.9904%
expected    50000.0000
chi_squared 192.3040
1318316 microseconds elapsed
ok ▂

Here’s another test result with 2 servers, 100000 weight each and 1000000 lookups:

ok 2 100000 chring.multi-insert
ok timer-start 2 1000000 chring.dtest timer-show 
       id    weight      hits
--------- --------- ---------
        0    100000    498978  49.8978%
        1    100000    501022  50.1022%
expected    500000.0000
chi_squared 4.1779
1325003 microseconds elapsed
ok ▂

The same with 2 servers, weight 1000 each looks like this:

ok 2 1000 chring.multi-insert
ok timer-start 2 1000000 chring.dtest timer-show 
       id    weight      hits
--------- --------- ---------
        0      1000    506596  50.6596%
        1      1000    493404  49.3404%
expected    500000.0000
chi_squared 174.0289
777111 microseconds elapsed
ok ▂

First Conclusions #

  • Both, f448() and MurmurHash3 populate the 2^64 hash ring without collisions (verified with 10000000 instances).
  • The resulting distribution gets better when the number of instances (the weight) is increased.
  • Counterclockwise operation works the same as expected.
  • Weighting is also working as expected.
  • The lookup speed depends on the total number of server instances (a skiplist property).
  • Perfect chi squared results require (very) high numbers of instances per server.
  • There seem no other public references which examine the uniform distribution of a specific consistent hash implementation this way.
  • f448() is slightly faster as MurmurHash3 and also distributes better.