blob: d65de7458c35eb0c25db07934e581109319e7709 [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
101 if (srv->state == srv->prev_state &&
102 srv->eweight == srv->prev_eweight)
103 return;
104
105 if (srv_is_usable(srv->state, srv->eweight))
106 goto out_update_state;
107
108 if (!srv_is_usable(srv->prev_state, srv->prev_eweight))
109 /* server was already down */
110 goto out_update_backend;
111
112 if (srv->state & SRV_BACKUP) {
113 p->lbprm.tot_wbck -= srv->prev_eweight;
114 p->srv_bck--;
115
116 if (srv == p->lbprm.fbck) {
117 /* we lost the first backup server in a single-backup
118 * configuration, we must search another one.
119 */
120 struct server *srv2 = p->lbprm.fbck;
121 do {
122 srv2 = srv2->next;
123 } while (srv2 &&
124 !((srv2->state & SRV_BACKUP) &&
125 srv_is_usable(srv2->state, srv2->eweight)));
126 p->lbprm.fbck = srv2;
127 }
128 } else {
129 p->lbprm.tot_wact -= srv->prev_eweight;
130 p->srv_act--;
131 }
132
133 chash_dequeue_srv(srv);
134
135out_update_backend:
136 /* check/update tot_used, tot_weight */
137 update_backend_weight(p);
138 out_update_state:
139 srv->prev_state = srv->state;
140 srv->prev_eweight = srv->eweight;
141}
142
143/* This function updates the server trees according to server <srv>'s new
144 * state. It should be called when server <srv>'s status changes to up.
145 * It is not important whether the server was already down or not. It is not
146 * important either that the new state is completely UP (the caller may not
147 * know all the variables of a server's state). This function will not change
148 * the weight of a server which was already up.
149 */
150static void chash_set_server_status_up(struct server *srv)
151{
152 struct proxy *p = srv->proxy;
153
154 if (srv->state == srv->prev_state &&
155 srv->eweight == srv->prev_eweight)
156 return;
157
158 if (!srv_is_usable(srv->state, srv->eweight))
159 goto out_update_state;
160
161 if (srv_is_usable(srv->prev_state, srv->prev_eweight))
162 /* server was already up */
163 goto out_update_backend;
164
165 if (srv->state & SRV_BACKUP) {
166 p->lbprm.tot_wbck += srv->eweight;
167 p->srv_bck++;
168
169 if (!(p->options & PR_O_USE_ALL_BK)) {
170 if (!p->lbprm.fbck) {
171 /* there was no backup server anymore */
172 p->lbprm.fbck = srv;
173 } else {
174 /* we may have restored a backup server prior to fbck,
175 * in which case it should replace it.
176 */
177 struct server *srv2 = srv;
178 do {
179 srv2 = srv2->next;
180 } while (srv2 && (srv2 != p->lbprm.fbck));
181 if (srv2)
182 p->lbprm.fbck = srv;
183 }
184 }
185 } else {
186 p->lbprm.tot_wact += srv->eweight;
187 p->srv_act++;
188 }
189
190 /* note that eweight cannot be 0 here */
191 chash_queue_dequeue_srv(srv);
192
193 out_update_backend:
194 /* check/update tot_used, tot_weight */
195 update_backend_weight(p);
196 out_update_state:
197 srv->prev_state = srv->state;
198 srv->prev_eweight = srv->eweight;
199}
200
201/* This function must be called after an update to server <srv>'s effective
202 * weight. It may be called after a state change too.
203 */
204static void chash_update_server_weight(struct server *srv)
205{
206 int old_state, new_state;
207 struct proxy *p = srv->proxy;
208
209 if (srv->state == srv->prev_state &&
210 srv->eweight == srv->prev_eweight)
211 return;
212
213 /* If changing the server's weight changes its state, we simply apply
214 * the procedures we already have for status change. If the state
215 * remains down, the server is not in any tree, so it's as easy as
216 * updating its values. If the state remains up with different weights,
217 * there are some computations to perform to find a new place and
218 * possibly a new tree for this server.
219 */
220
221 old_state = srv_is_usable(srv->prev_state, srv->prev_eweight);
222 new_state = srv_is_usable(srv->state, srv->eweight);
223
224 if (!old_state && !new_state) {
225 srv->prev_state = srv->state;
226 srv->prev_eweight = srv->eweight;
227 return;
228 }
229 else if (!old_state && new_state) {
230 chash_set_server_status_up(srv);
231 return;
232 }
233 else if (old_state && !new_state) {
234 chash_set_server_status_down(srv);
235 return;
236 }
237
238 /* only adjust the server's presence in the tree */
239 chash_queue_dequeue_srv(srv);
240
241 if (srv->state & SRV_BACKUP)
242 p->lbprm.tot_wbck += srv->eweight - srv->prev_eweight;
243 else
244 p->lbprm.tot_wact += srv->eweight - srv->prev_eweight;
245
246 update_backend_weight(p);
247 srv->prev_state = srv->state;
248 srv->prev_eweight = srv->eweight;
249}
250
251/*
252 * This function returns the running server from the CHASH tree, which is at
253 * the closest distance from the value of <hash>. Doing so ensures that even
254 * with a well imbalanced hash, if some servers are close to each other, they
255 * will still both receive traffic. If any server is found, it will be returned.
256 * If no valid server is found, NULL is returned.
257 */
258struct server *chash_get_server_hash(struct proxy *p, unsigned int hash)
259{
260 struct eb32_node *next, *prev;
261 struct server *nsrv, *psrv;
262 struct eb_root *root;
263 unsigned int dn, dp;
264
265 if (p->srv_act)
266 root = &p->lbprm.chash.act;
267 else if (p->lbprm.fbck)
268 return p->lbprm.fbck;
269 else if (p->srv_bck)
270 root = &p->lbprm.chash.bck;
271 else
272 return NULL;
273
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200274 /* find the node after and the node before */
275 next = eb32_lookup_ge(root, hash);
276 if (!next)
277 next = eb32_first(root);
278 if (!next)
279 return NULL; /* tree is empty */
280
281 prev = eb32_prev(next);
282 if (!prev)
283 prev = eb32_last(root);
284
285 nsrv = eb32_entry(next, struct tree_occ, node)->server;
286 psrv = eb32_entry(prev, struct tree_occ, node)->server;
287 if (nsrv == psrv)
288 return nsrv;
289
290 /* OK we're located between two distinct servers, let's
291 * compare distances between hash and the two servers
292 * and select the closest server.
293 */
294 dp = hash - prev->key;
295 dn = next->key - hash;
296
297 return (dp <= dn) ? psrv : nsrv;
298}
299
300/* Return next server from the CHASH tree in backend <p>. If the tree is empty,
301 * return NULL. Saturated servers are skipped.
302 */
303struct server *chash_get_next_server(struct proxy *p, struct server *srvtoavoid)
304{
305 struct server *srv, *avoided;
306 struct eb32_node *node, *stop, *avoided_node;
307 struct eb_root *root;
308
309 srv = avoided = NULL;
310 avoided_node = NULL;
311
312 if (p->srv_act)
313 root = &p->lbprm.chash.act;
314 else if (p->lbprm.fbck)
315 return p->lbprm.fbck;
316 else if (p->srv_bck)
317 root = &p->lbprm.chash.bck;
318 else
319 return NULL;
320
321 stop = node = p->lbprm.chash.last;
322 do {
323 struct server *s;
324
325 if (node)
326 node = eb32_next(node);
327 if (!node)
328 node = eb32_first(root);
329
330 p->lbprm.chash.last = node;
331 if (!node)
332 /* no node is available */
333 return NULL;
334
Willy Tarreaud16a1b22013-04-12 14:46:51 +0200335 /* Note: if we came here after a down/up cycle with no last
336 * pointer, and after a redispatch (srvtoavoid is set), we
337 * must set stop to non-null otherwise we can loop forever.
338 */
339 if (!stop)
340 stop = node;
341
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200342 /* OK, we have a server. However, it may be saturated, in which
343 * case we don't want to reconsider it for now, so we'll simply
344 * skip it. Same if it's the server we try to avoid, in which
345 * case we simply remember it for later use if needed.
346 */
347 s = eb32_entry(node, struct tree_occ, node)->server;
348 if (!s->maxconn || (!s->nbpend && s->served < srv_dynamic_maxconn(s))) {
349 if (s != srvtoavoid) {
350 srv = s;
351 break;
352 }
353 avoided = s;
354 avoided_node = node;
355 }
356 } while (node != stop);
357
358 if (!srv) {
359 srv = avoided;
360 p->lbprm.chash.last = avoided_node;
361 }
362
363 return srv;
364}
365
366/* This function is responsible for building the active and backup trees for
367 * constistent hashing. The servers receive an array of initialized nodes
368 * with their assigned keys. It also sets p->lbprm.wdiv to the eweight to
369 * uweight ratio.
370 */
371void chash_init_server_tree(struct proxy *p)
372{
373 struct server *srv;
374 struct eb_root init_head = EB_ROOT;
375 int node;
376
377 p->lbprm.set_server_status_up = chash_set_server_status_up;
378 p->lbprm.set_server_status_down = chash_set_server_status_down;
379 p->lbprm.update_server_eweight = chash_update_server_weight;
380 p->lbprm.server_take_conn = NULL;
381 p->lbprm.server_drop_conn = NULL;
382
383 p->lbprm.wdiv = BE_WEIGHT_SCALE;
384 for (srv = p->srv; srv; srv = srv->next) {
385 srv->prev_eweight = srv->eweight = srv->uweight * BE_WEIGHT_SCALE;
386 srv->prev_state = srv->state;
387 }
388
389 recount_servers(p);
390 update_backend_weight(p);
391
392 p->lbprm.chash.act = init_head;
393 p->lbprm.chash.bck = init_head;
394 p->lbprm.chash.last = NULL;
395
396 /* queue active and backup servers in two distinct groups */
397 for (srv = p->srv; srv; srv = srv->next) {
398 srv->lb_tree = (srv->state & SRV_BACKUP) ? &p->lbprm.chash.bck : &p->lbprm.chash.act;
399 srv->lb_nodes_tot = srv->uweight * BE_WEIGHT_SCALE;
400 srv->lb_nodes_now = 0;
401 srv->lb_nodes = (struct tree_occ *)calloc(srv->lb_nodes_tot, sizeof(struct tree_occ));
402
403 for (node = 0; node < srv->lb_nodes_tot; node++) {
404 srv->lb_nodes[node].server = srv;
Willy Tarreau4c14eaa2010-11-24 14:01:45 +0100405 srv->lb_nodes[node].node.key = full_hash(srv->puid * SRV_EWGHT_RANGE + node);
Willy Tarreau6b2e11b2009-10-01 07:52:15 +0200406 }
407
408 if (srv_is_usable(srv->state, srv->eweight))
409 chash_queue_dequeue_srv(srv);
410 }
411}