| /* |
| * Consistent Hash implementation |
| * Please consult this very well detailed article for more information : |
| * http://www.spiteful.com/2008/03/17/programmers-toolbox-part-3-consistent-hashing/ |
| * |
| * Our implementation has to support both weighted hashing and weighted round |
| * robin because we'll use it to replace the previous map-based implementation |
| * which offered both algorithms. |
| * |
| * Copyright 2000-2009 Willy Tarreau <w@1wt.eu> |
| * |
| * This program is free software; you can redistribute it and/or |
| * modify it under the terms of the GNU General Public License |
| * as published by the Free Software Foundation; either version |
| * 2 of the License, or (at your option) any later version. |
| * |
| */ |
| |
| #include <common/compat.h> |
| #include <common/config.h> |
| #include <common/debug.h> |
| #include <common/eb32tree.h> |
| |
| #include <types/global.h> |
| #include <types/server.h> |
| |
| #include <proto/backend.h> |
| #include <proto/queue.h> |
| |
| static inline unsigned int chash_hash(unsigned int a) |
| { |
| /* This function is one of Bob Jenkins' full avalanche hashing |
| * functions, which when provides quite a good distribution for little |
| * input variations. The result is quite suited to fit over a 32-bit |
| * space with enough variations so that a randomly picked number falls |
| * equally before any server position. |
| * Check http://burtleburtle.net/bob/hash/integer.html for more info. |
| */ |
| a = (a+0x7ed55d16) + (a<<12); |
| a = (a^0xc761c23c) ^ (a>>19); |
| a = (a+0x165667b1) + (a<<5); |
| a = (a+0xd3a2646c) ^ (a<<9); |
| a = (a+0xfd7046c5) + (a<<3); |
| a = (a^0xb55a4f09) ^ (a>>16); |
| |
| /* ensure values are better spread all around the tree by multiplying |
| * by a large prime close to 3/4 of the tree. |
| */ |
| return a * 3221225473U; |
| } |
| |
| /* Return next tree node after <node> which must still be in the tree, or be |
| * NULL. Lookup wraps around the end to the beginning. If the next node is the |
| * same node, return NULL. This is designed to find a valid next node before |
| * deleting one from the tree. |
| */ |
| static inline struct eb32_node *chash_skip_node(struct eb_root *root, struct eb32_node *node) |
| { |
| struct eb32_node *stop = node; |
| |
| if (!node) |
| return NULL; |
| node = eb32_next(node); |
| if (!node) |
| node = eb32_first(root); |
| if (node == stop) |
| return NULL; |
| return node; |
| } |
| |
| /* Remove all of a server's entries from its tree. This may be used when |
| * setting a server down. |
| */ |
| static inline void chash_dequeue_srv(struct server *s) |
| { |
| while (s->lb_nodes_now > 0) { |
| if (s->lb_nodes_now >= s->lb_nodes_tot) // should always be false anyway |
| s->lb_nodes_now = s->lb_nodes_tot; |
| s->lb_nodes_now--; |
| if (s->proxy->lbprm.chash.last == &s->lb_nodes[s->lb_nodes_now].node) |
| s->proxy->lbprm.chash.last = chash_skip_node(s->lb_tree, s->proxy->lbprm.chash.last); |
| eb32_delete(&s->lb_nodes[s->lb_nodes_now].node); |
| } |
| } |
| |
| /* Adjust the number of entries of a server in its tree. The server must appear |
| * as many times as its weight indicates it. If it's there too often, we remove |
| * the last occurrences. If it's not there enough, we add more occurrences. To |
| * remove a server from the tree, normally call this with eweight=0. |
| */ |
| static inline void chash_queue_dequeue_srv(struct server *s) |
| { |
| while (s->lb_nodes_now > s->eweight) { |
| if (s->lb_nodes_now >= s->lb_nodes_tot) // should always be false anyway |
| s->lb_nodes_now = s->lb_nodes_tot; |
| s->lb_nodes_now--; |
| if (s->proxy->lbprm.chash.last == &s->lb_nodes[s->lb_nodes_now].node) |
| s->proxy->lbprm.chash.last = chash_skip_node(s->lb_tree, s->proxy->lbprm.chash.last); |
| eb32_delete(&s->lb_nodes[s->lb_nodes_now].node); |
| } |
| |
| while (s->lb_nodes_now < s->eweight) { |
| if (s->lb_nodes_now >= s->lb_nodes_tot) // should always be false anyway |
| break; |
| if (s->proxy->lbprm.chash.last == &s->lb_nodes[s->lb_nodes_now].node) |
| s->proxy->lbprm.chash.last = chash_skip_node(s->lb_tree, s->proxy->lbprm.chash.last); |
| eb32_insert(s->lb_tree, &s->lb_nodes[s->lb_nodes_now].node); |
| s->lb_nodes_now++; |
| } |
| } |
| |
| /* This function updates the server trees according to server <srv>'s new |
| * state. It should be called when server <srv>'s status changes to down. |
| * It is not important whether the server was already down or not. It is not |
| * important either that the new state is completely down (the caller may not |
| * know all the variables of a server's state). |
| */ |
| static void chash_set_server_status_down(struct server *srv) |
| { |
| struct proxy *p = srv->proxy; |
| |
| if (srv->state == srv->prev_state && |
| srv->eweight == srv->prev_eweight) |
| return; |
| |
| if (srv_is_usable(srv->state, srv->eweight)) |
| goto out_update_state; |
| |
| if (!srv_is_usable(srv->prev_state, srv->prev_eweight)) |
| /* server was already down */ |
| goto out_update_backend; |
| |
| if (srv->state & SRV_BACKUP) { |
| p->lbprm.tot_wbck -= srv->prev_eweight; |
| p->srv_bck--; |
| |
| if (srv == p->lbprm.fbck) { |
| /* we lost the first backup server in a single-backup |
| * configuration, we must search another one. |
| */ |
| struct server *srv2 = p->lbprm.fbck; |
| do { |
| srv2 = srv2->next; |
| } while (srv2 && |
| !((srv2->state & SRV_BACKUP) && |
| srv_is_usable(srv2->state, srv2->eweight))); |
| p->lbprm.fbck = srv2; |
| } |
| } else { |
| p->lbprm.tot_wact -= srv->prev_eweight; |
| p->srv_act--; |
| } |
| |
| chash_dequeue_srv(srv); |
| |
| out_update_backend: |
| /* check/update tot_used, tot_weight */ |
| update_backend_weight(p); |
| out_update_state: |
| srv->prev_state = srv->state; |
| srv->prev_eweight = srv->eweight; |
| } |
| |
| /* This function updates the server trees according to server <srv>'s new |
| * state. It should be called when server <srv>'s status changes to up. |
| * It is not important whether the server was already down or not. It is not |
| * important either that the new state is completely UP (the caller may not |
| * know all the variables of a server's state). This function will not change |
| * the weight of a server which was already up. |
| */ |
| static void chash_set_server_status_up(struct server *srv) |
| { |
| struct proxy *p = srv->proxy; |
| |
| if (srv->state == srv->prev_state && |
| srv->eweight == srv->prev_eweight) |
| return; |
| |
| if (!srv_is_usable(srv->state, srv->eweight)) |
| goto out_update_state; |
| |
| if (srv_is_usable(srv->prev_state, srv->prev_eweight)) |
| /* server was already up */ |
| goto out_update_backend; |
| |
| if (srv->state & SRV_BACKUP) { |
| p->lbprm.tot_wbck += srv->eweight; |
| p->srv_bck++; |
| |
| if (!(p->options & PR_O_USE_ALL_BK)) { |
| if (!p->lbprm.fbck) { |
| /* there was no backup server anymore */ |
| p->lbprm.fbck = srv; |
| } else { |
| /* we may have restored a backup server prior to fbck, |
| * in which case it should replace it. |
| */ |
| struct server *srv2 = srv; |
| do { |
| srv2 = srv2->next; |
| } while (srv2 && (srv2 != p->lbprm.fbck)); |
| if (srv2) |
| p->lbprm.fbck = srv; |
| } |
| } |
| } else { |
| p->lbprm.tot_wact += srv->eweight; |
| p->srv_act++; |
| } |
| |
| /* note that eweight cannot be 0 here */ |
| chash_queue_dequeue_srv(srv); |
| |
| out_update_backend: |
| /* check/update tot_used, tot_weight */ |
| update_backend_weight(p); |
| out_update_state: |
| srv->prev_state = srv->state; |
| srv->prev_eweight = srv->eweight; |
| } |
| |
| /* This function must be called after an update to server <srv>'s effective |
| * weight. It may be called after a state change too. |
| */ |
| static void chash_update_server_weight(struct server *srv) |
| { |
| int old_state, new_state; |
| struct proxy *p = srv->proxy; |
| |
| if (srv->state == srv->prev_state && |
| srv->eweight == srv->prev_eweight) |
| return; |
| |
| /* If changing the server's weight changes its state, we simply apply |
| * the procedures we already have for status change. If the state |
| * remains down, the server is not in any tree, so it's as easy as |
| * updating its values. If the state remains up with different weights, |
| * there are some computations to perform to find a new place and |
| * possibly a new tree for this server. |
| */ |
| |
| old_state = srv_is_usable(srv->prev_state, srv->prev_eweight); |
| new_state = srv_is_usable(srv->state, srv->eweight); |
| |
| if (!old_state && !new_state) { |
| srv->prev_state = srv->state; |
| srv->prev_eweight = srv->eweight; |
| return; |
| } |
| else if (!old_state && new_state) { |
| chash_set_server_status_up(srv); |
| return; |
| } |
| else if (old_state && !new_state) { |
| chash_set_server_status_down(srv); |
| return; |
| } |
| |
| /* only adjust the server's presence in the tree */ |
| chash_queue_dequeue_srv(srv); |
| |
| if (srv->state & SRV_BACKUP) |
| p->lbprm.tot_wbck += srv->eweight - srv->prev_eweight; |
| else |
| p->lbprm.tot_wact += srv->eweight - srv->prev_eweight; |
| |
| update_backend_weight(p); |
| srv->prev_state = srv->state; |
| srv->prev_eweight = srv->eweight; |
| } |
| |
| /* |
| * This function returns the running server from the CHASH tree, which is at |
| * the closest distance from the value of <hash>. Doing so ensures that even |
| * with a well imbalanced hash, if some servers are close to each other, they |
| * will still both receive traffic. If any server is found, it will be returned. |
| * If no valid server is found, NULL is returned. |
| */ |
| struct server *chash_get_server_hash(struct proxy *p, unsigned int hash) |
| { |
| struct eb32_node *next, *prev; |
| struct server *nsrv, *psrv; |
| struct eb_root *root; |
| unsigned int dn, dp; |
| |
| if (p->srv_act) |
| root = &p->lbprm.chash.act; |
| else if (p->lbprm.fbck) |
| return p->lbprm.fbck; |
| else if (p->srv_bck) |
| root = &p->lbprm.chash.bck; |
| else |
| return NULL; |
| |
| hash = chash_hash(hash); |
| |
| /* find the node after and the node before */ |
| next = eb32_lookup_ge(root, hash); |
| if (!next) |
| next = eb32_first(root); |
| if (!next) |
| return NULL; /* tree is empty */ |
| |
| prev = eb32_prev(next); |
| if (!prev) |
| prev = eb32_last(root); |
| |
| nsrv = eb32_entry(next, struct tree_occ, node)->server; |
| psrv = eb32_entry(prev, struct tree_occ, node)->server; |
| if (nsrv == psrv) |
| return nsrv; |
| |
| /* OK we're located between two distinct servers, let's |
| * compare distances between hash and the two servers |
| * and select the closest server. |
| */ |
| dp = hash - prev->key; |
| dn = next->key - hash; |
| |
| return (dp <= dn) ? psrv : nsrv; |
| } |
| |
| /* Return next server from the CHASH tree in backend <p>. If the tree is empty, |
| * return NULL. Saturated servers are skipped. |
| */ |
| struct server *chash_get_next_server(struct proxy *p, struct server *srvtoavoid) |
| { |
| struct server *srv, *avoided; |
| struct eb32_node *node, *stop, *avoided_node; |
| struct eb_root *root; |
| |
| srv = avoided = NULL; |
| avoided_node = NULL; |
| |
| if (p->srv_act) |
| root = &p->lbprm.chash.act; |
| else if (p->lbprm.fbck) |
| return p->lbprm.fbck; |
| else if (p->srv_bck) |
| root = &p->lbprm.chash.bck; |
| else |
| return NULL; |
| |
| stop = node = p->lbprm.chash.last; |
| do { |
| struct server *s; |
| |
| if (node) |
| node = eb32_next(node); |
| if (!node) |
| node = eb32_first(root); |
| |
| p->lbprm.chash.last = node; |
| if (!node) |
| /* no node is available */ |
| return NULL; |
| |
| /* OK, we have a server. However, it may be saturated, in which |
| * case we don't want to reconsider it for now, so we'll simply |
| * skip it. Same if it's the server we try to avoid, in which |
| * case we simply remember it for later use if needed. |
| */ |
| s = eb32_entry(node, struct tree_occ, node)->server; |
| if (!s->maxconn || (!s->nbpend && s->served < srv_dynamic_maxconn(s))) { |
| if (s != srvtoavoid) { |
| srv = s; |
| break; |
| } |
| avoided = s; |
| avoided_node = node; |
| } |
| } while (node != stop); |
| |
| if (!srv) { |
| srv = avoided; |
| p->lbprm.chash.last = avoided_node; |
| } |
| |
| return srv; |
| } |
| |
| /* This function is responsible for building the active and backup trees for |
| * constistent hashing. The servers receive an array of initialized nodes |
| * with their assigned keys. It also sets p->lbprm.wdiv to the eweight to |
| * uweight ratio. |
| */ |
| void chash_init_server_tree(struct proxy *p) |
| { |
| struct server *srv; |
| struct eb_root init_head = EB_ROOT; |
| int node; |
| |
| p->lbprm.set_server_status_up = chash_set_server_status_up; |
| p->lbprm.set_server_status_down = chash_set_server_status_down; |
| p->lbprm.update_server_eweight = chash_update_server_weight; |
| p->lbprm.server_take_conn = NULL; |
| p->lbprm.server_drop_conn = NULL; |
| |
| p->lbprm.wdiv = BE_WEIGHT_SCALE; |
| for (srv = p->srv; srv; srv = srv->next) { |
| srv->prev_eweight = srv->eweight = srv->uweight * BE_WEIGHT_SCALE; |
| srv->prev_state = srv->state; |
| } |
| |
| recount_servers(p); |
| update_backend_weight(p); |
| |
| p->lbprm.chash.act = init_head; |
| p->lbprm.chash.bck = init_head; |
| p->lbprm.chash.last = NULL; |
| |
| /* queue active and backup servers in two distinct groups */ |
| for (srv = p->srv; srv; srv = srv->next) { |
| srv->lb_tree = (srv->state & SRV_BACKUP) ? &p->lbprm.chash.bck : &p->lbprm.chash.act; |
| srv->lb_nodes_tot = srv->uweight * BE_WEIGHT_SCALE; |
| srv->lb_nodes_now = 0; |
| srv->lb_nodes = (struct tree_occ *)calloc(srv->lb_nodes_tot, sizeof(struct tree_occ)); |
| |
| for (node = 0; node < srv->lb_nodes_tot; node++) { |
| srv->lb_nodes[node].server = srv; |
| srv->lb_nodes[node].node.key = chash_hash(srv->puid * SRV_EWGHT_RANGE + node); |
| } |
| |
| if (srv_is_usable(srv->state, srv->eweight)) |
| chash_queue_dequeue_srv(srv); |
| } |
| } |