RHPool implements a Rendezvous Hash Pool, which holds multiple possible destinations (or servers) at a given time. For DSR load balancing (the intended purpose), a MAC address is mapped to the first 6 bytes in memory order, the remaining 2 bytes allow to insert the same MAC address multiple times. A combination of Linux/POSIX rwlocks and atomic uint64_t access allows a maximum of concurrency during regular operation.
CHRing is an experimental consistent hash ring implementation based on a skiplist and f448(), a tabulation hashing function for this purpose. This post provides an overview of the CHRing testing API and the related RPCL control words.
f2568() is a variable length tabulation hashing function which returns a 64 bit hash result of input data up to a size of 256 bytes. It’s fast (requiring as many XOR operations as the data length in bytes), easy to understand and very strong at the same time. f2568() is publicly available under the BSD-3-Clause License.
f448() is another tabulation hashing function which maps two uint32_t to an uniform hash result of type uint64_t. This is useful to implement a skiplist based consistent hash ring with 2^64 possible ring slots (or positions).
f82() is hash function which hashes a unt64_t 8 byte unsigned integer key to a uint16_t 2 byte hash value. It belongs to the class of tabulation hashing functions and is perfect for implementing lock-less hash tables and other data structures that require an uniform and perfect distribution.
Skip lists are a probabilistic data structure that seem likely to supplant balanced trees as the implementation method of choice for many applications. Skip list algorithms have the same asymptotic expected time bounds as balanced trees and are simpler, faster and use less space.
When uniform random numbers are needed in C, just applying modulo is not enough. With using random() for portability and a few calculations this can be easily fixed.