[MEDIUM] backend: implement consistent hashing variation
Consistent hashing provides some interesting advantages over common
hashing. It avoids full redistribution in case of a server failure,
or when expanding the farm. This has a cost however, the hashing is
far from being perfect, as we associate a server to a request by
searching the server with the closest key in a tree. Since servers
appear multiple times based on their weights, it is recommended to
use weights larger than approximately 10-20 in order to smoothen
the distribution a bit.
In some cases, playing with weights will be the only solution to
make a server appear more often and increase chances of being picked,
so stats are very important with consistent hashing.
In order to indicate the type of hashing, use :
hash-type map-based (default, old one)
hash-type consistent (new one)
Consistent hashing can make sense in a cache farm, in order not
to redistribute everyone when a cache changes state. It could also
probably be used for long sessions such as terminal sessions, though
that has not be attempted yet.
More details on this method of hashing here :
http://www.spiteful.com/2008/03/17/programmers-toolbox-part-3-consistent-hashing/
diff --git a/src/backend.c b/src/backend.c
index ec83205..77c5a92 100644
--- a/src/backend.c
+++ b/src/backend.c
@@ -30,6 +30,7 @@
#include <proto/acl.h>
#include <proto/backend.h>
#include <proto/client.h>
+#include <proto/lb_chash.h>
#include <proto/lb_fwlc.h>
#include <proto/lb_fwrr.h>
#include <proto/lb_map.h>
@@ -117,7 +118,10 @@
l += sizeof (int);
}
hash_done:
- return map_get_server_hash(px, h);
+ if (px->lbprm.algo & BE_LB_LKUP_CHTREE)
+ return chash_get_server_hash(px, h);
+ else
+ return map_get_server_hash(px, h);
}
/*
@@ -161,7 +165,10 @@
hash = c + (hash << 6) + (hash << 16) - hash;
}
hash_done:
- return map_get_server_hash(px, hash);
+ if (px->lbprm.algo & BE_LB_LKUP_CHTREE)
+ return chash_get_server_hash(px, hash);
+ else
+ return map_get_server_hash(px, hash);
}
/*
@@ -209,7 +216,10 @@
uri_len--;
p++;
}
- return map_get_server_hash(px, hash);
+ if (px->lbprm.algo & BE_LB_LKUP_CHTREE)
+ return chash_get_server_hash(px, hash);
+ else
+ return map_get_server_hash(px, hash);
}
}
/* skip to next parameter */
@@ -308,7 +318,10 @@
p++;
/* should we break if vlen exceeds limit? */
}
- return map_get_server_hash(px, hash);
+ if (px->lbprm.algo & BE_LB_LKUP_CHTREE)
+ return chash_get_server_hash(px, hash);
+ else
+ return map_get_server_hash(px, hash);
}
}
/* skip to next parameter */
@@ -395,7 +408,10 @@
}
}
hash_done:
- return map_get_server_hash(px, hash);
+ if (px->lbprm.algo & BE_LB_LKUP_CHTREE)
+ return chash_get_server_hash(px, hash);
+ else
+ return map_get_server_hash(px, hash);
}
struct server *get_server_rch(struct session *s)
@@ -437,7 +453,10 @@
p++;
}
hash_done:
- return map_get_server_hash(px, hash);
+ if (px->lbprm.algo & BE_LB_LKUP_CHTREE)
+ return chash_get_server_hash(px, hash);
+ else
+ return map_get_server_hash(px, hash);
}
/*
@@ -515,9 +534,13 @@
s->srv = fwlc_get_next_server(s->be, s->prev_srv);
break;
+ case BE_LB_LKUP_CHTREE:
case BE_LB_LKUP_MAP:
if ((s->be->lbprm.algo & BE_LB_KIND) == BE_LB_KIND_RR) {
- s->srv = map_get_server_rr(s->be, s->prev_srv);
+ if (s->be->lbprm.algo & BE_LB_LKUP_CHTREE)
+ s->srv = chash_get_next_server(s->be, s->prev_srv);
+ else
+ s->srv = map_get_server_rr(s->be, s->prev_srv);
break;
}
else if ((s->be->lbprm.algo & BE_LB_KIND) != BE_LB_KIND_HI) {
@@ -581,8 +604,12 @@
/* If the hashing parameter was not found, let's fall
* back to round robin on the map.
*/
- if (!s->srv)
- s->srv = map_get_server_rr(s->be, s->prev_srv);
+ if (!s->srv) {
+ if (s->be->lbprm.algo & BE_LB_LKUP_CHTREE)
+ s->srv = chash_get_next_server(s->be, s->prev_srv);
+ else
+ s->srv = map_get_server_rr(s->be, s->prev_srv);
+ }
/* end of map-based LB */
break;