I’m looking for a way to do consistent hashing without any 3rd-party
modules
or perl/lua. I came up with the idea of generating a split_clients and
list
of upstreams via script, so we can add/remove backends without blowing
out
the cache on each upstream when a backend server is added, removed or
otherwise offline.
What I have looks like the config below. The example only includes 16
upstreams for clarity, and is generated by sorting by the SHA1 hash of
server names for each upstream bucket along with the bucket name.
Unfortunately, to get an even distribution of requests to upstream
buckets
with consistent hashing, I am actually going to need at least 4096
upstreams, and the corresponding number of entries in split_clients.
Will 4096 entries in single split_clients block pose a performance
issue?
Will split_clients have a distribution problem with a small percentage
like
“0.0244140625%”? How many “buckets” does the hash table for
split_clients
have (it doesn’t seem to be configurable)?
Thanks for any insights. I haven’t actually built a test environment for
this yet as the setup is quite a bit of work, so I want to find out if I
am
doing something stupid before committing a lot of time and resources.
upstream hash0 {server 192.168.47.104; server 192.168.47.102 backup;}
upstream hash1 {server 192.168.47.104; server 192.168.47.102 backup;}
upstream hash2 {server 192.168.47.105; server 192.168.47.104 backup;}
upstream hash3 {server 192.168.47.101; server 192.168.47.103 backup;}
upstream hash4 {server 192.168.47.102; server 192.168.47.101 backup;}
upstream hash5 {server 192.168.47.101; server 192.168.47.104 backup;}
upstream hash6 {server 192.168.47.103; server 192.168.47.102 backup;}
upstream hash7 {server 192.168.47.101; server 192.168.47.105 backup;}
upstream hash8 {server 192.168.47.102; server 192.168.47.105 backup;}
upstream hash9 {server 192.168.47.105; server 192.168.47.102 backup;}
upstream hashA {server 192.168.47.105; server 192.168.47.103 backup;}
upstream hashB {server 192.168.47.103; server 192.168.47.105 backup;}
upstream hashC {server 192.168.47.103; server 192.168.47.105 backup;}
upstream hashD {server 192.168.47.103; server 192.168.47.104 backup;}
upstream hashE {server 192.168.47.101; server 192.168.47.105 backup;}
upstream hashF {server 192.168.47.104; server 192.168.47.101 backup;}
On Wed, Oct 31, 2012 at 10:31:12AM -0400, rmalayter wrote:
Unfortunately, to get an even distribution of requests to upstream buckets
with consistent hashing, I am actually going to need at least 4096
upstreams, and the corresponding number of entries in split_clients.
Will 4096 entries in single split_clients block pose a performance issue?
Will split_clients have a distribution problem with a small percentage like
“0.0244140625%”?
Percentage values are stored in fixed point with 2 digits after
the point. Configuration parsing will complain if you’ll try to
specify more digits after the point.
How many “buckets” does the hash table for split_clients
have (it doesn’t seem to be configurable)?
The split_clients algorithm doesn’t use buckets, as it’s not a
hash table. Instead, it calculates hash function of the
original value, and selects resulting value based on a hash
function result. See Module ngx_http_split_clients_module for
details.
So clearly I am down the wrong path here, and split_clients just cannot
do
what I need. I will have to rethink things.
The 3rd-party ngx_http_consistent_hash module appears to be
un-maintained,
un-commented. It also uses binary search to find an upstream instead of
a
hash table, making it O(log(n)) for each request. My C skills haven’t
been
used in anger since about 1997, so updating or maintaining it myself
would
probably not be a fruitless exercise.
Perhaps I will have to fall back to using perl to get a hash bucket for
the
time being. I assume 4096 upstreams is not a problem for nginx given
that it
is used widely by CDNs.
A long time ago Igor mentioned he was working on an variable-based
upstream
hashing module using MurmurHash3:
I suppose other work took priority. Maybe Igor has some code stashed
somewhere that just needs testing and polishing.
If not, it seems that the current “ip_hash” scheme used in nginx could
be
easily adapted to fast consistent hashing by simply
-using MurmurHash3 or similar instead of the current simple
multiply+modulo scheme
-allowing arbitrary nginx variables as hash input instead of just the
IP
address during upstream selection
-at initialization utilizing a hash table of 4096 or whatever
configurable
number of buckets
-fill the hash table by sorting the server array on
murmurhash3(bucket_number + server_name + server_weight_counter) and
taking
the first server
Is there a mechanism for sponsoring development along these lines and
getting it into the official nginx distribution? Consistent hashing is
the
one commonly-used proxy server function that nginx seems to be missing.
On Wed, Oct 31, 2012 at 12:46:09PM -0400, rmalayter wrote:
hash table. Instead, it calculates hash function of the
hash table, making it O(log(n)) for each request. My C skills haven’t been
used in anger since about 1997, so updating or maintaining it myself would
probably not be a fruitless exercise.
It features Ketama consistent hashing compatible with
Cache::Memcached::Fast (memcached client module from the same
author). Unfortunately, it’s more or less unmaintained too, but I
think I have patches to bring it up to nginx 0.8.50 at least, and
it should be trivial to merge it with more recent versions.
Perhaps I will have to fall back to using perl to get a hash bucket for the
time being. I assume 4096 upstreams is not a problem for nginx given that it
is used widely by CDNs.
As long as you use split_clients to actually select a hash bucket,
I see no real difference with using embedded perl.
-allowing arbitrary nginx variables as hash input instead of just the IP
address during upstream selection
-at initialization utilizing a hash table of 4096 or whatever configurable
number of buckets
-fill the hash table by sorting the server array on
murmurhash3(bucket_number + server_name + server_weight_counter) and taking
the first server
Is there a mechanism for sponsoring development along these lines and
getting it into the official nginx distribution? Consistent hashing is the
one commonly-used proxy server function that nginx seems to be missing.
Hash module Igor mentioned is still in the TODO, but no ETA as
it’s not something frequently asked about. If you want to sponsor
the development, please write to the email address listed at Technical Support for NGINX and NGINX Plus Software.