Forum: NGINX consistent hashing using split_clients

2974d09ac2541e892966b762aad84943?d=identicon&s=25 rmalayter (Guest)
on 2012-10-31 15:31
(Received via mailing list)
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;}

split_clients "${scheme}://${host}${request_uri}" $uhash {
6.25% hash0;
6.25% hash1;
6.25% hash2;
6.25% hash3;
6.25% hash4;
6.25% hash5;
6.25% hash6;
6.25% hash7;
6.25% hash8;
6.25% hash9;
6.25% hashA;
6.25% hashB;
6.25% hashC;
6.25% hashD;
6.25% hashE;
* hashF;}

location /foo {
 proxy_pass http://$uhash;}

Posted at Nginx Forum:
http://forum.nginx.org/read.php?2,232428,232428#msg-232428
A8108a0961c6087c43cda32c8616dcba?d=identicon&s=25 Maxim Dounin (Guest)
on 2012-10-31 15:51
(Received via mailing list)
Hello!

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 http://nginx.org/r/split_clients for
details.

[...]

--
Maxim Dounin
http://nginx.com/support.html
2974d09ac2541e892966b762aad84943?d=identicon&s=25 rmalayter (Guest)
on 2012-10-31 17:46
(Received via mailing list)
Maxim Dounin Wrote:
> original value, and selects resulting value based on a hash
> function result.  See http://nginx.org/r/split_clients 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:
http://forum.nginx.org/read.php?29,212712,212739#msg-212739

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.

Posted at Nginx Forum:
http://forum.nginx.org/read.php?2,232428,232434#msg-232434
8a92465c849dda1cd172e8727e5c77d2?d=identicon&s=25 Weibin Yao (yaoweibin)
on 2012-11-01 06:44
(Received via mailing list)
You can have a look at Tengine. We are developing the consistent hash
module: https://github.com/taobao/tengine/pull/68

This module is current used in about 200 production servers. If you like
it, we  can give you the pure Nginx consistent hash module.

2012/11/1 rmalayter <nginx-forum@nginx.us>
A8108a0961c6087c43cda32c8616dcba?d=identicon&s=25 Maxim Dounin (Guest)
on 2012-11-01 10:59
(Received via mailing list)
Hello!

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.

You may also try memcached_hash module by Tomash Brechko, as
available at http://openhack.ru/nginx-patched/wiki/MemcachedHash.

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
http://nginx.com/support.html.

--
Maxim Dounin
http://nginx.com/support.html
Please log in before posting. Registration is free and takes only a minute.
Existing account

NEW: Do you have a Google/GoogleMail, Yahoo or Facebook account? No registration required!
Log in with Google account | Log in with Yahoo account | Log in with Facebook account
No account? Register here.