blob: 82124bc27bddfd933ef0ad7df296690891e1207a [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{
Emeric Brun52a91d32017-08-31 14:41:55 +020072 while (s->lb_nodes_now > s->next_eweight) {
Willy Tarreau6b2e11b2009-10-01 07:52:15 +020073 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
Emeric Brun52a91d32017-08-31 14:41:55 +020081 while (s->lb_nodes_now < s->next_eweight) {
Willy Tarreau6b2e11b2009-10-01 07:52:15 +020082 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
Emeric Brun52a91d32017-08-31 14:41:55 +0200104 if (srv_willbe_usable(srv))
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200105 goto out_update_state;
106
Emeric Brun52a91d32017-08-31 14:41:55 +0200107 if (!srv_currently_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) {
Emeric Brun52a91d32017-08-31 14:41:55 +0200112 p->lbprm.tot_wbck -= srv->cur_eweight;
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200113 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) &&
Emeric Brun52a91d32017-08-31 14:41:55 +0200124 srv_willbe_usable(srv2)));
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200125 p->lbprm.fbck = srv2;
126 }
127 } else {
Emeric Brun52a91d32017-08-31 14:41:55 +0200128 p->lbprm.tot_wact -= srv->cur_eweight;
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200129 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
Emeric Brun52a91d32017-08-31 14:41:55 +0200155 if (!srv_willbe_usable(srv))
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200156 goto out_update_state;
157
Emeric Brun52a91d32017-08-31 14:41:55 +0200158 if (srv_currently_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) {
Emeric Brun52a91d32017-08-31 14:41:55 +0200163 p->lbprm.tot_wbck += srv->next_eweight;
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200164 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 {
Emeric Brun52a91d32017-08-31 14:41:55 +0200183 p->lbprm.tot_wact += srv->next_eweight;
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200184 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
Emeric Brun52a91d32017-08-31 14:41:55 +0200216 old_state = srv_currently_usable(srv);
217 new_state = srv_willbe_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)
Emeric Brun52a91d32017-08-31 14:41:55 +0200236 p->lbprm.tot_wbck += srv->next_eweight - srv->cur_eweight;
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200237 else
Emeric Brun52a91d32017-08-31 14:41:55 +0200238 p->lbprm.tot_wact += srv->next_eweight - srv->cur_eweight;
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200239
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... */
Emeric Brun52a91d32017-08-31 14:41:55 +0200259 unsigned slots = s->cur_eweight * slots_per_weight;
Andrew Rodland4f88c632016-10-25 12:50:37 -0400260
261 /* And then distribute the rest among servers proportionally to their weight. */
Emeric Brun52a91d32017-08-31 14:41:55 +0200262 slots += ((s->cumulative_weight + s->cur_eweight) * remainder) / s->proxy->lbprm.tot_weight
Andrew Rodland4f88c632016-10-25 12:50:37 -0400263 - (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;
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200309
Andrew Rodland18330ab2017-04-26 02:57:03 -0400310 /* OK we're located between two servers, let's
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200311 * compare distances between hash and the two servers
312 * and select the closest server.
313 */
314 dp = hash - prev->key;
315 dn = next->key - hash;
316
Andrew Rodland4f88c632016-10-25 12:50:37 -0400317 if (dp <= dn) {
318 next = prev;
319 nsrv = psrv;
320 }
321
322 loop = 0;
323 while (p->lbprm.chash.balance_factor && !chash_server_is_eligible(nsrv)) {
324 next = eb32_next(next);
325 if (!next) {
326 next = eb32_first(root);
327 if (++loop > 1) // protection against accidental loop
328 break;
329 }
330 nsrv = eb32_entry(next, struct tree_occ, node)->server;
331 }
332
333 return nsrv;
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200334}
335
336/* Return next server from the CHASH tree in backend <p>. If the tree is empty,
337 * return NULL. Saturated servers are skipped.
338 */
339struct server *chash_get_next_server(struct proxy *p, struct server *srvtoavoid)
340{
341 struct server *srv, *avoided;
342 struct eb32_node *node, *stop, *avoided_node;
343 struct eb_root *root;
344
345 srv = avoided = NULL;
346 avoided_node = NULL;
347
348 if (p->srv_act)
349 root = &p->lbprm.chash.act;
350 else if (p->lbprm.fbck)
351 return p->lbprm.fbck;
352 else if (p->srv_bck)
353 root = &p->lbprm.chash.bck;
354 else
355 return NULL;
356
357 stop = node = p->lbprm.chash.last;
358 do {
359 struct server *s;
360
361 if (node)
362 node = eb32_next(node);
363 if (!node)
364 node = eb32_first(root);
365
366 p->lbprm.chash.last = node;
367 if (!node)
368 /* no node is available */
369 return NULL;
370
Willy Tarreaud16a1b22013-04-12 14:46:51 +0200371 /* Note: if we came here after a down/up cycle with no last
372 * pointer, and after a redispatch (srvtoavoid is set), we
373 * must set stop to non-null otherwise we can loop forever.
374 */
375 if (!stop)
376 stop = node;
377
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200378 /* OK, we have a server. However, it may be saturated, in which
379 * case we don't want to reconsider it for now, so we'll simply
380 * skip it. Same if it's the server we try to avoid, in which
381 * case we simply remember it for later use if needed.
382 */
383 s = eb32_entry(node, struct tree_occ, node)->server;
384 if (!s->maxconn || (!s->nbpend && s->served < srv_dynamic_maxconn(s))) {
385 if (s != srvtoavoid) {
386 srv = s;
387 break;
388 }
389 avoided = s;
390 avoided_node = node;
391 }
392 } while (node != stop);
393
394 if (!srv) {
395 srv = avoided;
396 p->lbprm.chash.last = avoided_node;
397 }
398
399 return srv;
400}
401
402/* This function is responsible for building the active and backup trees for
403 * constistent hashing. The servers receive an array of initialized nodes
404 * with their assigned keys. It also sets p->lbprm.wdiv to the eweight to
405 * uweight ratio.
406 */
407void chash_init_server_tree(struct proxy *p)
408{
409 struct server *srv;
410 struct eb_root init_head = EB_ROOT;
411 int node;
412
413 p->lbprm.set_server_status_up = chash_set_server_status_up;
414 p->lbprm.set_server_status_down = chash_set_server_status_down;
415 p->lbprm.update_server_eweight = chash_update_server_weight;
416 p->lbprm.server_take_conn = NULL;
417 p->lbprm.server_drop_conn = NULL;
418
419 p->lbprm.wdiv = BE_WEIGHT_SCALE;
420 for (srv = p->srv; srv; srv = srv->next) {
Emeric Brun52a91d32017-08-31 14:41:55 +0200421 srv->next_eweight = (srv->uweight * p->lbprm.wdiv + p->lbprm.wmult - 1) / p->lbprm.wmult;
Willy Tarreauc5150da2014-05-13 19:27:31 +0200422 srv_lb_commit_status(srv);
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200423 }
424
425 recount_servers(p);
426 update_backend_weight(p);
427
428 p->lbprm.chash.act = init_head;
429 p->lbprm.chash.bck = init_head;
430 p->lbprm.chash.last = NULL;
431
432 /* queue active and backup servers in two distinct groups */
433 for (srv = p->srv; srv; srv = srv->next) {
Willy Tarreauc93cd162014-05-13 15:54:22 +0200434 srv->lb_tree = (srv->flags & SRV_F_BACKUP) ? &p->lbprm.chash.bck : &p->lbprm.chash.act;
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200435 srv->lb_nodes_tot = srv->uweight * BE_WEIGHT_SCALE;
436 srv->lb_nodes_now = 0;
Vincent Bernat3c2f2f22016-04-03 13:48:42 +0200437 srv->lb_nodes = calloc(srv->lb_nodes_tot, sizeof(struct tree_occ));
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200438
439 for (node = 0; node < srv->lb_nodes_tot; node++) {
440 srv->lb_nodes[node].server = srv;
Willy Tarreau4c14eaa2010-11-24 14:01:45 +0100441 srv->lb_nodes[node].node.key = full_hash(srv->puid * SRV_EWGHT_RANGE + node);
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200442 }
443
Emeric Brun52a91d32017-08-31 14:41:55 +0200444 if (srv_currently_usable(srv))
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200445 chash_queue_dequeue_srv(srv);
446 }
447}