blob: 84a2ef36e46efb2230bf333e308ee547440b3839 [file] [log] [blame]
Willy Tarreau6b2e11b2009-10-01 07:52:15 +02001/*
2 * Consistent Hash implementation
3 * Please consult this very well detailed article for more information :
4 * http://www.spiteful.com/2008/03/17/programmers-toolbox-part-3-consistent-hashing/
5 *
6 * Our implementation has to support both weighted hashing and weighted round
7 * robin because we'll use it to replace the previous map-based implementation
8 * which offered both algorithms.
9 *
Willy Tarreau4c14eaa2010-11-24 14:01:45 +010010 * Copyright 2000-2010 Willy Tarreau <w@1wt.eu>
Willy Tarreau6b2e11b2009-10-01 07:52:15 +020011 *
12 * This program is free software; you can redistribute it and/or
13 * modify it under the terms of the GNU General Public License
14 * as published by the Free Software Foundation; either version
15 * 2 of the License, or (at your option) any later version.
16 *
17 */
18
19#include <common/compat.h>
20#include <common/config.h>
21#include <common/debug.h>
Willy Tarreau4c14eaa2010-11-24 14:01:45 +010022#include <common/standard.h>
Willy Tarreau45cb4fb2009-10-26 21:10:04 +010023#include <eb32tree.h>
Willy Tarreau6b2e11b2009-10-01 07:52:15 +020024
25#include <types/global.h>
26#include <types/server.h>
27
28#include <proto/backend.h>
29#include <proto/queue.h>
30
Willy Tarreau6b2e11b2009-10-01 07:52:15 +020031/* Return next tree node after <node> which must still be in the tree, or be
32 * NULL. Lookup wraps around the end to the beginning. If the next node is the
33 * same node, return NULL. This is designed to find a valid next node before
34 * deleting one from the tree.
35 */
36static inline struct eb32_node *chash_skip_node(struct eb_root *root, struct eb32_node *node)
37{
38 struct eb32_node *stop = node;
39
40 if (!node)
41 return NULL;
42 node = eb32_next(node);
43 if (!node)
44 node = eb32_first(root);
45 if (node == stop)
46 return NULL;
47 return node;
48}
49
50/* Remove all of a server's entries from its tree. This may be used when
51 * setting a server down.
52 */
53static inline void chash_dequeue_srv(struct server *s)
54{
55 while (s->lb_nodes_now > 0) {
56 if (s->lb_nodes_now >= s->lb_nodes_tot) // should always be false anyway
57 s->lb_nodes_now = s->lb_nodes_tot;
58 s->lb_nodes_now--;
59 if (s->proxy->lbprm.chash.last == &s->lb_nodes[s->lb_nodes_now].node)
60 s->proxy->lbprm.chash.last = chash_skip_node(s->lb_tree, s->proxy->lbprm.chash.last);
61 eb32_delete(&s->lb_nodes[s->lb_nodes_now].node);
62 }
63}
64
65/* Adjust the number of entries of a server in its tree. The server must appear
66 * as many times as its weight indicates it. If it's there too often, we remove
67 * the last occurrences. If it's not there enough, we add more occurrences. To
68 * remove a server from the tree, normally call this with eweight=0.
69 */
70static inline void chash_queue_dequeue_srv(struct server *s)
71{
72 while (s->lb_nodes_now > s->eweight) {
73 if (s->lb_nodes_now >= s->lb_nodes_tot) // should always be false anyway
74 s->lb_nodes_now = s->lb_nodes_tot;
75 s->lb_nodes_now--;
76 if (s->proxy->lbprm.chash.last == &s->lb_nodes[s->lb_nodes_now].node)
77 s->proxy->lbprm.chash.last = chash_skip_node(s->lb_tree, s->proxy->lbprm.chash.last);
78 eb32_delete(&s->lb_nodes[s->lb_nodes_now].node);
79 }
80
81 while (s->lb_nodes_now < s->eweight) {
82 if (s->lb_nodes_now >= s->lb_nodes_tot) // should always be false anyway
83 break;
84 if (s->proxy->lbprm.chash.last == &s->lb_nodes[s->lb_nodes_now].node)
85 s->proxy->lbprm.chash.last = chash_skip_node(s->lb_tree, s->proxy->lbprm.chash.last);
86 eb32_insert(s->lb_tree, &s->lb_nodes[s->lb_nodes_now].node);
87 s->lb_nodes_now++;
88 }
89}
90
91/* This function updates the server trees according to server <srv>'s new
92 * state. It should be called when server <srv>'s status changes to down.
93 * It is not important whether the server was already down or not. It is not
94 * important either that the new state is completely down (the caller may not
95 * know all the variables of a server's state).
96 */
97static void chash_set_server_status_down(struct server *srv)
98{
99 struct proxy *p = srv->proxy;
100
Willy Tarreauc5150da2014-05-13 19:27:31 +0200101 if (!srv_lb_status_changed(srv))
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200102 return;
103
Willy Tarreau87eb1d62014-05-13 18:51:40 +0200104 if (srv_is_usable(srv))
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200105 goto out_update_state;
106
Willy Tarreau87eb1d62014-05-13 18:51:40 +0200107 if (!srv_was_usable(srv))
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200108 /* server was already down */
109 goto out_update_backend;
110
Willy Tarreauc93cd162014-05-13 15:54:22 +0200111 if (srv->flags & SRV_F_BACKUP) {
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200112 p->lbprm.tot_wbck -= srv->prev_eweight;
113 p->srv_bck--;
114
115 if (srv == p->lbprm.fbck) {
116 /* we lost the first backup server in a single-backup
117 * configuration, we must search another one.
118 */
119 struct server *srv2 = p->lbprm.fbck;
120 do {
121 srv2 = srv2->next;
122 } while (srv2 &&
Willy Tarreauc93cd162014-05-13 15:54:22 +0200123 !((srv2->flags & SRV_F_BACKUP) &&
Willy Tarreau87eb1d62014-05-13 18:51:40 +0200124 srv_is_usable(srv2)));
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200125 p->lbprm.fbck = srv2;
126 }
127 } else {
128 p->lbprm.tot_wact -= srv->prev_eweight;
129 p->srv_act--;
130 }
131
132 chash_dequeue_srv(srv);
133
134out_update_backend:
135 /* check/update tot_used, tot_weight */
136 update_backend_weight(p);
137 out_update_state:
Willy Tarreauc5150da2014-05-13 19:27:31 +0200138 srv_lb_commit_status(srv);
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200139}
140
141/* This function updates the server trees according to server <srv>'s new
142 * state. It should be called when server <srv>'s status changes to up.
143 * It is not important whether the server was already down or not. It is not
144 * important either that the new state is completely UP (the caller may not
145 * know all the variables of a server's state). This function will not change
146 * the weight of a server which was already up.
147 */
148static void chash_set_server_status_up(struct server *srv)
149{
150 struct proxy *p = srv->proxy;
151
Willy Tarreauc5150da2014-05-13 19:27:31 +0200152 if (!srv_lb_status_changed(srv))
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200153 return;
154
Willy Tarreau87eb1d62014-05-13 18:51:40 +0200155 if (!srv_is_usable(srv))
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200156 goto out_update_state;
157
Willy Tarreau87eb1d62014-05-13 18:51:40 +0200158 if (srv_was_usable(srv))
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200159 /* server was already up */
160 goto out_update_backend;
161
Willy Tarreauc93cd162014-05-13 15:54:22 +0200162 if (srv->flags & SRV_F_BACKUP) {
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200163 p->lbprm.tot_wbck += srv->eweight;
164 p->srv_bck++;
165
166 if (!(p->options & PR_O_USE_ALL_BK)) {
167 if (!p->lbprm.fbck) {
168 /* there was no backup server anymore */
169 p->lbprm.fbck = srv;
170 } else {
171 /* we may have restored a backup server prior to fbck,
172 * in which case it should replace it.
173 */
174 struct server *srv2 = srv;
175 do {
176 srv2 = srv2->next;
177 } while (srv2 && (srv2 != p->lbprm.fbck));
178 if (srv2)
179 p->lbprm.fbck = srv;
180 }
181 }
182 } else {
183 p->lbprm.tot_wact += srv->eweight;
184 p->srv_act++;
185 }
186
187 /* note that eweight cannot be 0 here */
188 chash_queue_dequeue_srv(srv);
189
190 out_update_backend:
191 /* check/update tot_used, tot_weight */
192 update_backend_weight(p);
193 out_update_state:
Willy Tarreauc5150da2014-05-13 19:27:31 +0200194 srv_lb_commit_status(srv);
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200195}
196
197/* This function must be called after an update to server <srv>'s effective
198 * weight. It may be called after a state change too.
199 */
200static void chash_update_server_weight(struct server *srv)
201{
202 int old_state, new_state;
203 struct proxy *p = srv->proxy;
204
Willy Tarreauc5150da2014-05-13 19:27:31 +0200205 if (!srv_lb_status_changed(srv))
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200206 return;
207
208 /* If changing the server's weight changes its state, we simply apply
209 * the procedures we already have for status change. If the state
210 * remains down, the server is not in any tree, so it's as easy as
211 * updating its values. If the state remains up with different weights,
212 * there are some computations to perform to find a new place and
213 * possibly a new tree for this server.
214 */
215
Willy Tarreau87eb1d62014-05-13 18:51:40 +0200216 old_state = srv_was_usable(srv);
217 new_state = srv_is_usable(srv);
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200218
219 if (!old_state && !new_state) {
Willy Tarreauc5150da2014-05-13 19:27:31 +0200220 srv_lb_commit_status(srv);
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200221 return;
222 }
223 else if (!old_state && new_state) {
224 chash_set_server_status_up(srv);
225 return;
226 }
227 else if (old_state && !new_state) {
228 chash_set_server_status_down(srv);
229 return;
230 }
231
232 /* only adjust the server's presence in the tree */
233 chash_queue_dequeue_srv(srv);
234
Willy Tarreauc93cd162014-05-13 15:54:22 +0200235 if (srv->flags & SRV_F_BACKUP)
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200236 p->lbprm.tot_wbck += srv->eweight - srv->prev_eweight;
237 else
238 p->lbprm.tot_wact += srv->eweight - srv->prev_eweight;
239
240 update_backend_weight(p);
Willy Tarreauc5150da2014-05-13 19:27:31 +0200241 srv_lb_commit_status(srv);
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200242}
243
244/*
Andrew Rodland4f88c632016-10-25 12:50:37 -0400245 * This function implements the "Consistent Hashing with Bounded Loads" algorithm
246 * of Mirrokni, Thorup, and Zadimoghaddam (arxiv:1608.01350), adapted for use with
247 * unequal server weights.
248 */
249int chash_server_is_eligible(struct server *s)
250{
251 /* The total number of slots to allocate is the total number of outstanding requests
252 * (including the one we're about to make) times the load-balance-factor, rounded up.
253 */
254 unsigned tot_slots = ((s->proxy->served + 1) * s->proxy->lbprm.chash.balance_factor + 99) / 100;
255 unsigned slots_per_weight = tot_slots / s->proxy->lbprm.tot_weight;
256 unsigned remainder = tot_slots % s->proxy->lbprm.tot_weight;
257
258 /* Allocate a whole number of slots per weight unit... */
259 unsigned slots = s->eweight * slots_per_weight;
260
261 /* And then distribute the rest among servers proportionally to their weight. */
262 slots += ((s->cumulative_weight + s->eweight) * remainder) / s->proxy->lbprm.tot_weight
263 - (s->cumulative_weight * remainder) / s->proxy->lbprm.tot_weight;
264
265 /* But never leave a server with 0. */
266 if (slots == 0)
267 slots = 1;
268
269 return s->served < slots;
270}
271
272/*
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200273 * This function returns the running server from the CHASH tree, which is at
274 * the closest distance from the value of <hash>. Doing so ensures that even
275 * with a well imbalanced hash, if some servers are close to each other, they
276 * will still both receive traffic. If any server is found, it will be returned.
277 * If no valid server is found, NULL is returned.
278 */
279struct server *chash_get_server_hash(struct proxy *p, unsigned int hash)
280{
281 struct eb32_node *next, *prev;
282 struct server *nsrv, *psrv;
283 struct eb_root *root;
284 unsigned int dn, dp;
Andrew Rodland4f88c632016-10-25 12:50:37 -0400285 int loop;
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200286
287 if (p->srv_act)
288 root = &p->lbprm.chash.act;
289 else if (p->lbprm.fbck)
290 return p->lbprm.fbck;
291 else if (p->srv_bck)
292 root = &p->lbprm.chash.bck;
293 else
294 return NULL;
295
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200296 /* find the node after and the node before */
297 next = eb32_lookup_ge(root, hash);
298 if (!next)
299 next = eb32_first(root);
300 if (!next)
301 return NULL; /* tree is empty */
302
303 prev = eb32_prev(next);
304 if (!prev)
305 prev = eb32_last(root);
306
307 nsrv = eb32_entry(next, struct tree_occ, node)->server;
308 psrv = eb32_entry(prev, struct tree_occ, node)->server;
309 if (nsrv == psrv)
310 return nsrv;
311
312 /* OK we're located between two distinct servers, let's
313 * compare distances between hash and the two servers
314 * and select the closest server.
315 */
316 dp = hash - prev->key;
317 dn = next->key - hash;
318
Andrew Rodland4f88c632016-10-25 12:50:37 -0400319 if (dp <= dn) {
320 next = prev;
321 nsrv = psrv;
322 }
323
324 loop = 0;
325 while (p->lbprm.chash.balance_factor && !chash_server_is_eligible(nsrv)) {
326 next = eb32_next(next);
327 if (!next) {
328 next = eb32_first(root);
329 if (++loop > 1) // protection against accidental loop
330 break;
331 }
332 nsrv = eb32_entry(next, struct tree_occ, node)->server;
333 }
334
335 return nsrv;
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200336}
337
338/* Return next server from the CHASH tree in backend <p>. If the tree is empty,
339 * return NULL. Saturated servers are skipped.
340 */
341struct server *chash_get_next_server(struct proxy *p, struct server *srvtoavoid)
342{
343 struct server *srv, *avoided;
344 struct eb32_node *node, *stop, *avoided_node;
345 struct eb_root *root;
346
347 srv = avoided = NULL;
348 avoided_node = NULL;
349
350 if (p->srv_act)
351 root = &p->lbprm.chash.act;
352 else if (p->lbprm.fbck)
353 return p->lbprm.fbck;
354 else if (p->srv_bck)
355 root = &p->lbprm.chash.bck;
356 else
357 return NULL;
358
359 stop = node = p->lbprm.chash.last;
360 do {
361 struct server *s;
362
363 if (node)
364 node = eb32_next(node);
365 if (!node)
366 node = eb32_first(root);
367
368 p->lbprm.chash.last = node;
369 if (!node)
370 /* no node is available */
371 return NULL;
372
Willy Tarreaud16a1b22013-04-12 14:46:51 +0200373 /* Note: if we came here after a down/up cycle with no last
374 * pointer, and after a redispatch (srvtoavoid is set), we
375 * must set stop to non-null otherwise we can loop forever.
376 */
377 if (!stop)
378 stop = node;
379
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200380 /* OK, we have a server. However, it may be saturated, in which
381 * case we don't want to reconsider it for now, so we'll simply
382 * skip it. Same if it's the server we try to avoid, in which
383 * case we simply remember it for later use if needed.
384 */
385 s = eb32_entry(node, struct tree_occ, node)->server;
386 if (!s->maxconn || (!s->nbpend && s->served < srv_dynamic_maxconn(s))) {
387 if (s != srvtoavoid) {
388 srv = s;
389 break;
390 }
391 avoided = s;
392 avoided_node = node;
393 }
394 } while (node != stop);
395
396 if (!srv) {
397 srv = avoided;
398 p->lbprm.chash.last = avoided_node;
399 }
400
401 return srv;
402}
403
404/* This function is responsible for building the active and backup trees for
405 * constistent hashing. The servers receive an array of initialized nodes
406 * with their assigned keys. It also sets p->lbprm.wdiv to the eweight to
407 * uweight ratio.
408 */
409void chash_init_server_tree(struct proxy *p)
410{
411 struct server *srv;
412 struct eb_root init_head = EB_ROOT;
413 int node;
414
415 p->lbprm.set_server_status_up = chash_set_server_status_up;
416 p->lbprm.set_server_status_down = chash_set_server_status_down;
417 p->lbprm.update_server_eweight = chash_update_server_weight;
418 p->lbprm.server_take_conn = NULL;
419 p->lbprm.server_drop_conn = NULL;
420
421 p->lbprm.wdiv = BE_WEIGHT_SCALE;
422 for (srv = p->srv; srv; srv = srv->next) {
Willy Tarreau004e0452013-11-21 11:22:01 +0100423 srv->eweight = (srv->uweight * p->lbprm.wdiv + p->lbprm.wmult - 1) / p->lbprm.wmult;
Willy Tarreauc5150da2014-05-13 19:27:31 +0200424 srv_lb_commit_status(srv);
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200425 }
426
427 recount_servers(p);
428 update_backend_weight(p);
429
430 p->lbprm.chash.act = init_head;
431 p->lbprm.chash.bck = init_head;
432 p->lbprm.chash.last = NULL;
433
434 /* queue active and backup servers in two distinct groups */
435 for (srv = p->srv; srv; srv = srv->next) {
Willy Tarreauc93cd162014-05-13 15:54:22 +0200436 srv->lb_tree = (srv->flags & SRV_F_BACKUP) ? &p->lbprm.chash.bck : &p->lbprm.chash.act;
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200437 srv->lb_nodes_tot = srv->uweight * BE_WEIGHT_SCALE;
438 srv->lb_nodes_now = 0;
Vincent Bernat3c2f2f22016-04-03 13:48:42 +0200439 srv->lb_nodes = calloc(srv->lb_nodes_tot, sizeof(struct tree_occ));
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200440
441 for (node = 0; node < srv->lb_nodes_tot; node++) {
442 srv->lb_nodes[node].server = srv;
Willy Tarreau4c14eaa2010-11-24 14:01:45 +0100443 srv->lb_nodes[node].node.key = full_hash(srv->puid * SRV_EWGHT_RANGE + node);
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200444 }
445
Willy Tarreau87eb1d62014-05-13 18:51:40 +0200446 if (srv_is_usable(srv))
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200447 chash_queue_dequeue_srv(srv);
448 }
449}