Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 1 | /* |
| 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 Tarreau | 4c14eaa | 2010-11-24 14:01:45 +0100 | [diff] [blame] | 10 | * Copyright 2000-2010 Willy Tarreau <w@1wt.eu> |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 11 | * |
| 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 | |
Willy Tarreau | 4c7e4b7 | 2020-05-27 12:58:42 +0200 | [diff] [blame] | 19 | #include <haproxy/api.h> |
Willy Tarreau | 48fbcae | 2020-06-03 18:09:46 +0200 | [diff] [blame] | 20 | #include <haproxy/tools.h> |
Willy Tarreau | 8d2b777 | 2020-05-27 10:58:19 +0200 | [diff] [blame] | 21 | #include <import/eb32tree.h> |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 22 | |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 23 | #include <types/server.h> |
| 24 | |
| 25 | #include <proto/backend.h> |
| 26 | #include <proto/queue.h> |
| 27 | |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 28 | /* Return next tree node after <node> which must still be in the tree, or be |
| 29 | * NULL. Lookup wraps around the end to the beginning. If the next node is the |
| 30 | * same node, return NULL. This is designed to find a valid next node before |
| 31 | * deleting one from the tree. |
| 32 | */ |
| 33 | static inline struct eb32_node *chash_skip_node(struct eb_root *root, struct eb32_node *node) |
| 34 | { |
| 35 | struct eb32_node *stop = node; |
| 36 | |
| 37 | if (!node) |
| 38 | return NULL; |
| 39 | node = eb32_next(node); |
| 40 | if (!node) |
| 41 | node = eb32_first(root); |
| 42 | if (node == stop) |
| 43 | return NULL; |
| 44 | return node; |
| 45 | } |
| 46 | |
| 47 | /* Remove all of a server's entries from its tree. This may be used when |
| 48 | * setting a server down. |
| 49 | */ |
| 50 | static inline void chash_dequeue_srv(struct server *s) |
| 51 | { |
| 52 | while (s->lb_nodes_now > 0) { |
| 53 | if (s->lb_nodes_now >= s->lb_nodes_tot) // should always be false anyway |
| 54 | s->lb_nodes_now = s->lb_nodes_tot; |
| 55 | s->lb_nodes_now--; |
| 56 | if (s->proxy->lbprm.chash.last == &s->lb_nodes[s->lb_nodes_now].node) |
| 57 | s->proxy->lbprm.chash.last = chash_skip_node(s->lb_tree, s->proxy->lbprm.chash.last); |
| 58 | eb32_delete(&s->lb_nodes[s->lb_nodes_now].node); |
| 59 | } |
| 60 | } |
| 61 | |
| 62 | /* Adjust the number of entries of a server in its tree. The server must appear |
| 63 | * as many times as its weight indicates it. If it's there too often, we remove |
| 64 | * the last occurrences. If it's not there enough, we add more occurrences. To |
| 65 | * remove a server from the tree, normally call this with eweight=0. |
Willy Tarreau | 1b87748 | 2018-08-21 19:44:53 +0200 | [diff] [blame] | 66 | * |
| 67 | * The server's lock and the lbprm's lock must be held. |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 68 | */ |
| 69 | static inline void chash_queue_dequeue_srv(struct server *s) |
| 70 | { |
Emeric Brun | 52a91d3 | 2017-08-31 14:41:55 +0200 | [diff] [blame] | 71 | while (s->lb_nodes_now > s->next_eweight) { |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 72 | if (s->lb_nodes_now >= s->lb_nodes_tot) // should always be false anyway |
| 73 | s->lb_nodes_now = s->lb_nodes_tot; |
| 74 | s->lb_nodes_now--; |
| 75 | if (s->proxy->lbprm.chash.last == &s->lb_nodes[s->lb_nodes_now].node) |
| 76 | s->proxy->lbprm.chash.last = chash_skip_node(s->lb_tree, s->proxy->lbprm.chash.last); |
| 77 | eb32_delete(&s->lb_nodes[s->lb_nodes_now].node); |
| 78 | } |
| 79 | |
Olivier Houchard | f8eb8d5 | 2017-10-17 15:52:59 +0200 | [diff] [blame] | 80 | /* Attempt to increase the total number of nodes, if the user |
| 81 | * increased the weight beyond the original weight |
| 82 | */ |
| 83 | if (s->lb_nodes_tot < s->next_eweight) { |
Christopher Faulet | 0a52c17 | 2019-08-01 10:09:29 +0200 | [diff] [blame] | 84 | struct tree_occ *new_nodes; |
Olivier Houchard | f8eb8d5 | 2017-10-17 15:52:59 +0200 | [diff] [blame] | 85 | |
Christopher Faulet | 0a52c17 | 2019-08-01 10:09:29 +0200 | [diff] [blame] | 86 | /* First we need to remove all server's entries from its tree |
| 87 | * because the realloc will change all nodes pointers */ |
| 88 | chash_dequeue_srv(s); |
| 89 | |
| 90 | new_nodes = realloc(s->lb_nodes, s->next_eweight * sizeof(*new_nodes)); |
Olivier Houchard | f8eb8d5 | 2017-10-17 15:52:59 +0200 | [diff] [blame] | 91 | if (new_nodes) { |
| 92 | unsigned int j; |
| 93 | |
| 94 | s->lb_nodes = new_nodes; |
| 95 | memset(&s->lb_nodes[s->lb_nodes_tot], 0, |
| 96 | (s->next_eweight - s->lb_nodes_tot) * sizeof(*s->lb_nodes)); |
| 97 | for (j = s->lb_nodes_tot; j < s->next_eweight; j++) { |
| 98 | s->lb_nodes[j].server = s; |
| 99 | s->lb_nodes[j].node.key = full_hash(s->puid * SRV_EWGHT_RANGE + j); |
| 100 | } |
| 101 | s->lb_nodes_tot = s->next_eweight; |
| 102 | } |
| 103 | } |
Emeric Brun | 52a91d3 | 2017-08-31 14:41:55 +0200 | [diff] [blame] | 104 | while (s->lb_nodes_now < s->next_eweight) { |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 105 | if (s->lb_nodes_now >= s->lb_nodes_tot) // should always be false anyway |
| 106 | break; |
| 107 | if (s->proxy->lbprm.chash.last == &s->lb_nodes[s->lb_nodes_now].node) |
| 108 | s->proxy->lbprm.chash.last = chash_skip_node(s->lb_tree, s->proxy->lbprm.chash.last); |
| 109 | eb32_insert(s->lb_tree, &s->lb_nodes[s->lb_nodes_now].node); |
| 110 | s->lb_nodes_now++; |
| 111 | } |
| 112 | } |
| 113 | |
| 114 | /* This function updates the server trees according to server <srv>'s new |
| 115 | * state. It should be called when server <srv>'s status changes to down. |
| 116 | * It is not important whether the server was already down or not. It is not |
| 117 | * important either that the new state is completely down (the caller may not |
| 118 | * know all the variables of a server's state). |
Willy Tarreau | 1b87748 | 2018-08-21 19:44:53 +0200 | [diff] [blame] | 119 | * |
| 120 | * The server's lock must be held. The lbprm lock will be used. |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 121 | */ |
| 122 | static void chash_set_server_status_down(struct server *srv) |
| 123 | { |
| 124 | struct proxy *p = srv->proxy; |
| 125 | |
Willy Tarreau | c5150da | 2014-05-13 19:27:31 +0200 | [diff] [blame] | 126 | if (!srv_lb_status_changed(srv)) |
Christopher Faulet | 5b51755 | 2017-06-09 14:17:53 +0200 | [diff] [blame] | 127 | return; |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 128 | |
Willy Tarreau | 1b87748 | 2018-08-21 19:44:53 +0200 | [diff] [blame] | 129 | HA_SPIN_LOCK(LBPRM_LOCK, &p->lbprm.lock); |
| 130 | |
Emeric Brun | 52a91d3 | 2017-08-31 14:41:55 +0200 | [diff] [blame] | 131 | if (srv_willbe_usable(srv)) |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 132 | goto out_update_state; |
| 133 | |
Emeric Brun | 52a91d3 | 2017-08-31 14:41:55 +0200 | [diff] [blame] | 134 | if (!srv_currently_usable(srv)) |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 135 | /* server was already down */ |
| 136 | goto out_update_backend; |
| 137 | |
Willy Tarreau | c93cd16 | 2014-05-13 15:54:22 +0200 | [diff] [blame] | 138 | if (srv->flags & SRV_F_BACKUP) { |
Emeric Brun | 52a91d3 | 2017-08-31 14:41:55 +0200 | [diff] [blame] | 139 | p->lbprm.tot_wbck -= srv->cur_eweight; |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 140 | p->srv_bck--; |
| 141 | |
| 142 | if (srv == p->lbprm.fbck) { |
| 143 | /* we lost the first backup server in a single-backup |
| 144 | * configuration, we must search another one. |
| 145 | */ |
| 146 | struct server *srv2 = p->lbprm.fbck; |
| 147 | do { |
| 148 | srv2 = srv2->next; |
| 149 | } while (srv2 && |
Willy Tarreau | c93cd16 | 2014-05-13 15:54:22 +0200 | [diff] [blame] | 150 | !((srv2->flags & SRV_F_BACKUP) && |
Emeric Brun | 52a91d3 | 2017-08-31 14:41:55 +0200 | [diff] [blame] | 151 | srv_willbe_usable(srv2))); |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 152 | p->lbprm.fbck = srv2; |
| 153 | } |
| 154 | } else { |
Emeric Brun | 52a91d3 | 2017-08-31 14:41:55 +0200 | [diff] [blame] | 155 | p->lbprm.tot_wact -= srv->cur_eweight; |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 156 | p->srv_act--; |
| 157 | } |
| 158 | |
| 159 | chash_dequeue_srv(srv); |
| 160 | |
| 161 | out_update_backend: |
| 162 | /* check/update tot_used, tot_weight */ |
| 163 | update_backend_weight(p); |
| 164 | out_update_state: |
Willy Tarreau | c5150da | 2014-05-13 19:27:31 +0200 | [diff] [blame] | 165 | srv_lb_commit_status(srv); |
Willy Tarreau | 1b87748 | 2018-08-21 19:44:53 +0200 | [diff] [blame] | 166 | |
| 167 | HA_SPIN_UNLOCK(LBPRM_LOCK, &p->lbprm.lock); |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 168 | } |
| 169 | |
| 170 | /* This function updates the server trees according to server <srv>'s new |
| 171 | * state. It should be called when server <srv>'s status changes to up. |
| 172 | * It is not important whether the server was already down or not. It is not |
| 173 | * important either that the new state is completely UP (the caller may not |
| 174 | * know all the variables of a server's state). This function will not change |
| 175 | * the weight of a server which was already up. |
Willy Tarreau | 1b87748 | 2018-08-21 19:44:53 +0200 | [diff] [blame] | 176 | * |
| 177 | * The server's lock must be held. The lbprm lock will be used. |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 178 | */ |
| 179 | static void chash_set_server_status_up(struct server *srv) |
| 180 | { |
| 181 | struct proxy *p = srv->proxy; |
| 182 | |
Willy Tarreau | c5150da | 2014-05-13 19:27:31 +0200 | [diff] [blame] | 183 | if (!srv_lb_status_changed(srv)) |
Christopher Faulet | 5b51755 | 2017-06-09 14:17:53 +0200 | [diff] [blame] | 184 | return; |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 185 | |
Willy Tarreau | 1b87748 | 2018-08-21 19:44:53 +0200 | [diff] [blame] | 186 | HA_SPIN_LOCK(LBPRM_LOCK, &p->lbprm.lock); |
| 187 | |
Emeric Brun | 52a91d3 | 2017-08-31 14:41:55 +0200 | [diff] [blame] | 188 | if (!srv_willbe_usable(srv)) |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 189 | goto out_update_state; |
| 190 | |
Emeric Brun | 52a91d3 | 2017-08-31 14:41:55 +0200 | [diff] [blame] | 191 | if (srv_currently_usable(srv)) |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 192 | /* server was already up */ |
| 193 | goto out_update_backend; |
| 194 | |
Willy Tarreau | c93cd16 | 2014-05-13 15:54:22 +0200 | [diff] [blame] | 195 | if (srv->flags & SRV_F_BACKUP) { |
Emeric Brun | 52a91d3 | 2017-08-31 14:41:55 +0200 | [diff] [blame] | 196 | p->lbprm.tot_wbck += srv->next_eweight; |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 197 | p->srv_bck++; |
| 198 | |
| 199 | if (!(p->options & PR_O_USE_ALL_BK)) { |
| 200 | if (!p->lbprm.fbck) { |
| 201 | /* there was no backup server anymore */ |
| 202 | p->lbprm.fbck = srv; |
| 203 | } else { |
| 204 | /* we may have restored a backup server prior to fbck, |
| 205 | * in which case it should replace it. |
| 206 | */ |
| 207 | struct server *srv2 = srv; |
| 208 | do { |
| 209 | srv2 = srv2->next; |
| 210 | } while (srv2 && (srv2 != p->lbprm.fbck)); |
| 211 | if (srv2) |
| 212 | p->lbprm.fbck = srv; |
| 213 | } |
| 214 | } |
| 215 | } else { |
Emeric Brun | 52a91d3 | 2017-08-31 14:41:55 +0200 | [diff] [blame] | 216 | p->lbprm.tot_wact += srv->next_eweight; |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 217 | p->srv_act++; |
| 218 | } |
| 219 | |
| 220 | /* note that eweight cannot be 0 here */ |
| 221 | chash_queue_dequeue_srv(srv); |
| 222 | |
| 223 | out_update_backend: |
| 224 | /* check/update tot_used, tot_weight */ |
| 225 | update_backend_weight(p); |
| 226 | out_update_state: |
Willy Tarreau | c5150da | 2014-05-13 19:27:31 +0200 | [diff] [blame] | 227 | srv_lb_commit_status(srv); |
Willy Tarreau | 1b87748 | 2018-08-21 19:44:53 +0200 | [diff] [blame] | 228 | |
| 229 | HA_SPIN_UNLOCK(LBPRM_LOCK, &p->lbprm.lock); |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 230 | } |
| 231 | |
| 232 | /* This function must be called after an update to server <srv>'s effective |
| 233 | * weight. It may be called after a state change too. |
Willy Tarreau | 1b87748 | 2018-08-21 19:44:53 +0200 | [diff] [blame] | 234 | * |
| 235 | * The server's lock must be held. The lbprm lock may be used. |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 236 | */ |
| 237 | static void chash_update_server_weight(struct server *srv) |
| 238 | { |
| 239 | int old_state, new_state; |
| 240 | struct proxy *p = srv->proxy; |
| 241 | |
Willy Tarreau | c5150da | 2014-05-13 19:27:31 +0200 | [diff] [blame] | 242 | if (!srv_lb_status_changed(srv)) |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 243 | return; |
| 244 | |
| 245 | /* If changing the server's weight changes its state, we simply apply |
| 246 | * the procedures we already have for status change. If the state |
| 247 | * remains down, the server is not in any tree, so it's as easy as |
| 248 | * updating its values. If the state remains up with different weights, |
| 249 | * there are some computations to perform to find a new place and |
| 250 | * possibly a new tree for this server. |
| 251 | */ |
| 252 | |
Emeric Brun | 52a91d3 | 2017-08-31 14:41:55 +0200 | [diff] [blame] | 253 | old_state = srv_currently_usable(srv); |
| 254 | new_state = srv_willbe_usable(srv); |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 255 | |
| 256 | if (!old_state && !new_state) { |
Willy Tarreau | c5150da | 2014-05-13 19:27:31 +0200 | [diff] [blame] | 257 | srv_lb_commit_status(srv); |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 258 | return; |
| 259 | } |
| 260 | else if (!old_state && new_state) { |
| 261 | chash_set_server_status_up(srv); |
| 262 | return; |
| 263 | } |
| 264 | else if (old_state && !new_state) { |
| 265 | chash_set_server_status_down(srv); |
| 266 | return; |
| 267 | } |
| 268 | |
Willy Tarreau | 1b87748 | 2018-08-21 19:44:53 +0200 | [diff] [blame] | 269 | HA_SPIN_LOCK(LBPRM_LOCK, &p->lbprm.lock); |
| 270 | |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 271 | /* only adjust the server's presence in the tree */ |
| 272 | chash_queue_dequeue_srv(srv); |
| 273 | |
Willy Tarreau | c93cd16 | 2014-05-13 15:54:22 +0200 | [diff] [blame] | 274 | if (srv->flags & SRV_F_BACKUP) |
Emeric Brun | 52a91d3 | 2017-08-31 14:41:55 +0200 | [diff] [blame] | 275 | p->lbprm.tot_wbck += srv->next_eweight - srv->cur_eweight; |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 276 | else |
Emeric Brun | 52a91d3 | 2017-08-31 14:41:55 +0200 | [diff] [blame] | 277 | p->lbprm.tot_wact += srv->next_eweight - srv->cur_eweight; |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 278 | |
| 279 | update_backend_weight(p); |
Willy Tarreau | c5150da | 2014-05-13 19:27:31 +0200 | [diff] [blame] | 280 | srv_lb_commit_status(srv); |
Willy Tarreau | 1b87748 | 2018-08-21 19:44:53 +0200 | [diff] [blame] | 281 | |
| 282 | HA_SPIN_UNLOCK(LBPRM_LOCK, &p->lbprm.lock); |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 283 | } |
| 284 | |
| 285 | /* |
Andrew Rodland | 4f88c63 | 2016-10-25 12:50:37 -0400 | [diff] [blame] | 286 | * This function implements the "Consistent Hashing with Bounded Loads" algorithm |
| 287 | * of Mirrokni, Thorup, and Zadimoghaddam (arxiv:1608.01350), adapted for use with |
| 288 | * unequal server weights. |
| 289 | */ |
| 290 | int chash_server_is_eligible(struct server *s) |
| 291 | { |
| 292 | /* The total number of slots to allocate is the total number of outstanding requests |
| 293 | * (including the one we're about to make) times the load-balance-factor, rounded up. |
| 294 | */ |
Willy Tarreau | 76e84f5 | 2019-01-14 16:50:58 +0100 | [diff] [blame] | 295 | unsigned tot_slots = ((s->proxy->served + 1) * s->proxy->lbprm.hash_balance_factor + 99) / 100; |
Andrew Rodland | 4f88c63 | 2016-10-25 12:50:37 -0400 | [diff] [blame] | 296 | unsigned slots_per_weight = tot_slots / s->proxy->lbprm.tot_weight; |
| 297 | unsigned remainder = tot_slots % s->proxy->lbprm.tot_weight; |
| 298 | |
| 299 | /* Allocate a whole number of slots per weight unit... */ |
Emeric Brun | 52a91d3 | 2017-08-31 14:41:55 +0200 | [diff] [blame] | 300 | unsigned slots = s->cur_eweight * slots_per_weight; |
Andrew Rodland | 4f88c63 | 2016-10-25 12:50:37 -0400 | [diff] [blame] | 301 | |
| 302 | /* And then distribute the rest among servers proportionally to their weight. */ |
Emeric Brun | 52a91d3 | 2017-08-31 14:41:55 +0200 | [diff] [blame] | 303 | slots += ((s->cumulative_weight + s->cur_eweight) * remainder) / s->proxy->lbprm.tot_weight |
Andrew Rodland | 4f88c63 | 2016-10-25 12:50:37 -0400 | [diff] [blame] | 304 | - (s->cumulative_weight * remainder) / s->proxy->lbprm.tot_weight; |
| 305 | |
| 306 | /* But never leave a server with 0. */ |
| 307 | if (slots == 0) |
| 308 | slots = 1; |
| 309 | |
| 310 | return s->served < slots; |
| 311 | } |
| 312 | |
| 313 | /* |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 314 | * This function returns the running server from the CHASH tree, which is at |
| 315 | * the closest distance from the value of <hash>. Doing so ensures that even |
| 316 | * with a well imbalanced hash, if some servers are close to each other, they |
| 317 | * will still both receive traffic. If any server is found, it will be returned. |
Willy Tarreau | 59884a6 | 2019-01-02 14:48:31 +0100 | [diff] [blame] | 318 | * It will also skip server <avoid> if the hash result ends on this one. |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 319 | * If no valid server is found, NULL is returned. |
| 320 | */ |
Willy Tarreau | 59884a6 | 2019-01-02 14:48:31 +0100 | [diff] [blame] | 321 | struct server *chash_get_server_hash(struct proxy *p, unsigned int hash, const struct server *avoid) |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 322 | { |
| 323 | struct eb32_node *next, *prev; |
| 324 | struct server *nsrv, *psrv; |
| 325 | struct eb_root *root; |
| 326 | unsigned int dn, dp; |
Andrew Rodland | 4f88c63 | 2016-10-25 12:50:37 -0400 | [diff] [blame] | 327 | int loop; |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 328 | |
Willy Tarreau | 1b87748 | 2018-08-21 19:44:53 +0200 | [diff] [blame] | 329 | HA_SPIN_LOCK(LBPRM_LOCK, &p->lbprm.lock); |
| 330 | |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 331 | if (p->srv_act) |
| 332 | root = &p->lbprm.chash.act; |
Willy Tarreau | 1b87748 | 2018-08-21 19:44:53 +0200 | [diff] [blame] | 333 | else if (p->lbprm.fbck) { |
| 334 | nsrv = p->lbprm.fbck; |
| 335 | goto out; |
| 336 | } |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 337 | else if (p->srv_bck) |
| 338 | root = &p->lbprm.chash.bck; |
Willy Tarreau | 1b87748 | 2018-08-21 19:44:53 +0200 | [diff] [blame] | 339 | else { |
| 340 | nsrv = NULL; |
| 341 | goto out; |
| 342 | } |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 343 | |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 344 | /* find the node after and the node before */ |
| 345 | next = eb32_lookup_ge(root, hash); |
| 346 | if (!next) |
| 347 | next = eb32_first(root); |
Willy Tarreau | 1b87748 | 2018-08-21 19:44:53 +0200 | [diff] [blame] | 348 | if (!next) { |
| 349 | nsrv = NULL; /* tree is empty */ |
| 350 | goto out; |
| 351 | } |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 352 | |
| 353 | prev = eb32_prev(next); |
| 354 | if (!prev) |
| 355 | prev = eb32_last(root); |
| 356 | |
| 357 | nsrv = eb32_entry(next, struct tree_occ, node)->server; |
| 358 | psrv = eb32_entry(prev, struct tree_occ, node)->server; |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 359 | |
Andrew Rodland | 18330ab | 2017-04-26 02:57:03 -0400 | [diff] [blame] | 360 | /* OK we're located between two servers, let's |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 361 | * compare distances between hash and the two servers |
| 362 | * and select the closest server. |
| 363 | */ |
| 364 | dp = hash - prev->key; |
| 365 | dn = next->key - hash; |
| 366 | |
Andrew Rodland | 4f88c63 | 2016-10-25 12:50:37 -0400 | [diff] [blame] | 367 | if (dp <= dn) { |
| 368 | next = prev; |
| 369 | nsrv = psrv; |
| 370 | } |
| 371 | |
| 372 | loop = 0; |
Willy Tarreau | 76e84f5 | 2019-01-14 16:50:58 +0100 | [diff] [blame] | 373 | while (nsrv == avoid || (p->lbprm.hash_balance_factor && !chash_server_is_eligible(nsrv))) { |
Andrew Rodland | 4f88c63 | 2016-10-25 12:50:37 -0400 | [diff] [blame] | 374 | next = eb32_next(next); |
| 375 | if (!next) { |
| 376 | next = eb32_first(root); |
| 377 | if (++loop > 1) // protection against accidental loop |
| 378 | break; |
| 379 | } |
| 380 | nsrv = eb32_entry(next, struct tree_occ, node)->server; |
| 381 | } |
| 382 | |
Willy Tarreau | 1b87748 | 2018-08-21 19:44:53 +0200 | [diff] [blame] | 383 | out: |
| 384 | HA_SPIN_UNLOCK(LBPRM_LOCK, &p->lbprm.lock); |
Andrew Rodland | 4f88c63 | 2016-10-25 12:50:37 -0400 | [diff] [blame] | 385 | return nsrv; |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 386 | } |
| 387 | |
| 388 | /* Return next server from the CHASH tree in backend <p>. If the tree is empty, |
| 389 | * return NULL. Saturated servers are skipped. |
| 390 | */ |
| 391 | struct server *chash_get_next_server(struct proxy *p, struct server *srvtoavoid) |
| 392 | { |
| 393 | struct server *srv, *avoided; |
| 394 | struct eb32_node *node, *stop, *avoided_node; |
| 395 | struct eb_root *root; |
| 396 | |
| 397 | srv = avoided = NULL; |
| 398 | avoided_node = NULL; |
| 399 | |
Christopher Faulet | 2a944ee | 2017-11-07 10:42:54 +0100 | [diff] [blame] | 400 | HA_SPIN_LOCK(LBPRM_LOCK, &p->lbprm.lock); |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 401 | if (p->srv_act) |
| 402 | root = &p->lbprm.chash.act; |
Christopher Faulet | 5b51755 | 2017-06-09 14:17:53 +0200 | [diff] [blame] | 403 | else if (p->lbprm.fbck) { |
| 404 | srv = p->lbprm.fbck; |
| 405 | goto out; |
| 406 | } |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 407 | else if (p->srv_bck) |
| 408 | root = &p->lbprm.chash.bck; |
Christopher Faulet | 5b51755 | 2017-06-09 14:17:53 +0200 | [diff] [blame] | 409 | else { |
| 410 | srv = NULL; |
| 411 | goto out; |
| 412 | } |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 413 | |
| 414 | stop = node = p->lbprm.chash.last; |
| 415 | do { |
| 416 | struct server *s; |
| 417 | |
| 418 | if (node) |
| 419 | node = eb32_next(node); |
| 420 | if (!node) |
| 421 | node = eb32_first(root); |
| 422 | |
| 423 | p->lbprm.chash.last = node; |
Willy Tarreau | 1ed90ac | 2017-11-05 10:54:50 +0100 | [diff] [blame] | 424 | if (!node) { |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 425 | /* no node is available */ |
Willy Tarreau | 1ed90ac | 2017-11-05 10:54:50 +0100 | [diff] [blame] | 426 | srv = NULL; |
| 427 | goto out; |
| 428 | } |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 429 | |
Willy Tarreau | d16a1b2 | 2013-04-12 14:46:51 +0200 | [diff] [blame] | 430 | /* Note: if we came here after a down/up cycle with no last |
| 431 | * pointer, and after a redispatch (srvtoavoid is set), we |
| 432 | * must set stop to non-null otherwise we can loop forever. |
| 433 | */ |
| 434 | if (!stop) |
| 435 | stop = node; |
| 436 | |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 437 | /* OK, we have a server. However, it may be saturated, in which |
| 438 | * case we don't want to reconsider it for now, so we'll simply |
| 439 | * skip it. Same if it's the server we try to avoid, in which |
| 440 | * case we simply remember it for later use if needed. |
| 441 | */ |
| 442 | s = eb32_entry(node, struct tree_occ, node)->server; |
| 443 | if (!s->maxconn || (!s->nbpend && s->served < srv_dynamic_maxconn(s))) { |
| 444 | if (s != srvtoavoid) { |
| 445 | srv = s; |
| 446 | break; |
| 447 | } |
| 448 | avoided = s; |
| 449 | avoided_node = node; |
| 450 | } |
| 451 | } while (node != stop); |
| 452 | |
| 453 | if (!srv) { |
| 454 | srv = avoided; |
| 455 | p->lbprm.chash.last = avoided_node; |
| 456 | } |
| 457 | |
Christopher Faulet | 5b51755 | 2017-06-09 14:17:53 +0200 | [diff] [blame] | 458 | out: |
Christopher Faulet | 2a944ee | 2017-11-07 10:42:54 +0100 | [diff] [blame] | 459 | HA_SPIN_UNLOCK(LBPRM_LOCK, &p->lbprm.lock); |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 460 | return srv; |
| 461 | } |
| 462 | |
| 463 | /* This function is responsible for building the active and backup trees for |
| 464 | * constistent hashing. The servers receive an array of initialized nodes |
| 465 | * with their assigned keys. It also sets p->lbprm.wdiv to the eweight to |
| 466 | * uweight ratio. |
| 467 | */ |
| 468 | void chash_init_server_tree(struct proxy *p) |
| 469 | { |
| 470 | struct server *srv; |
| 471 | struct eb_root init_head = EB_ROOT; |
| 472 | int node; |
| 473 | |
| 474 | p->lbprm.set_server_status_up = chash_set_server_status_up; |
| 475 | p->lbprm.set_server_status_down = chash_set_server_status_down; |
| 476 | p->lbprm.update_server_eweight = chash_update_server_weight; |
| 477 | p->lbprm.server_take_conn = NULL; |
| 478 | p->lbprm.server_drop_conn = NULL; |
| 479 | |
| 480 | p->lbprm.wdiv = BE_WEIGHT_SCALE; |
| 481 | for (srv = p->srv; srv; srv = srv->next) { |
Emeric Brun | 52a91d3 | 2017-08-31 14:41:55 +0200 | [diff] [blame] | 482 | srv->next_eweight = (srv->uweight * p->lbprm.wdiv + p->lbprm.wmult - 1) / p->lbprm.wmult; |
Willy Tarreau | c5150da | 2014-05-13 19:27:31 +0200 | [diff] [blame] | 483 | srv_lb_commit_status(srv); |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 484 | } |
| 485 | |
| 486 | recount_servers(p); |
| 487 | update_backend_weight(p); |
| 488 | |
| 489 | p->lbprm.chash.act = init_head; |
| 490 | p->lbprm.chash.bck = init_head; |
| 491 | p->lbprm.chash.last = NULL; |
| 492 | |
| 493 | /* queue active and backup servers in two distinct groups */ |
| 494 | for (srv = p->srv; srv; srv = srv->next) { |
Willy Tarreau | c93cd16 | 2014-05-13 15:54:22 +0200 | [diff] [blame] | 495 | srv->lb_tree = (srv->flags & SRV_F_BACKUP) ? &p->lbprm.chash.bck : &p->lbprm.chash.act; |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 496 | srv->lb_nodes_tot = srv->uweight * BE_WEIGHT_SCALE; |
| 497 | srv->lb_nodes_now = 0; |
Vincent Bernat | 3c2f2f2 | 2016-04-03 13:48:42 +0200 | [diff] [blame] | 498 | srv->lb_nodes = calloc(srv->lb_nodes_tot, sizeof(struct tree_occ)); |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 499 | for (node = 0; node < srv->lb_nodes_tot; node++) { |
| 500 | srv->lb_nodes[node].server = srv; |
Willy Tarreau | 4c14eaa | 2010-11-24 14:01:45 +0100 | [diff] [blame] | 501 | srv->lb_nodes[node].node.key = full_hash(srv->puid * SRV_EWGHT_RANGE + node); |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 502 | } |
| 503 | |
Emeric Brun | 52a91d3 | 2017-08-31 14:41:55 +0200 | [diff] [blame] | 504 | if (srv_currently_usable(srv)) |
Willy Tarreau | 6b2e11b | 2009-10-01 07:52:15 +0200 | [diff] [blame] | 505 | chash_queue_dequeue_srv(srv); |
| 506 | } |
| 507 | } |