ctdb/server/ipalloc_lcp2.c

   1 /*
   2    ctdb ip takeover code
   3
   4    Copyright (C) Ronnie Sahlberg  2007
   5    Copyright (C) Andrew Tridgell  2007
   6    Copyright (C) Martin Schwenke  2011
   7
   8    This program is free software; you can redistribute it and/or modify
   9    it under the terms of the GNU General Public License as published by
  10    the Free Software Foundation; either version 3 of the License, or
  11    (at your option) any later version.
  12
  13    This program is distributed in the hope that it will be useful,
  14    but WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16    GNU General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with this program; if not, see <http://www.gnu.org/licenses/>.
  20 */
  21
  22 #include "replace.h"
  23 #include "system/network.h"
  24
  25 #include "lib/util/debug.h"
  26 #include "common/logging.h"
  27
  28 #include "protocol/protocol_api.h"
  29
  30 #include "server/ipalloc_private.h"
  31
  32 /*
  33  * This is the length of the longtest common prefix between the IPs.
  34  * It is calculated by XOR-ing the 2 IPs together and counting the
  35  * number of leading zeroes.  The implementation means that all
  36  * addresses end up being 128 bits long.
  37  *
  38  * FIXME? Should we consider IPv4 and IPv6 separately given that the
  39  * 12 bytes of 0 prefix padding will hurt the algorithm if there are
  40  * lots of nodes and IP addresses?
  41  */
  42 static uint32_t ip_distance(ctdb_sock_addr *ip1, ctdb_sock_addr *ip2)
  43 {
  44         uint32_t ip1_k[IP_KEYLEN];
  45         uint32_t *t;
  46         int i;
  47         uint32_t x;
  48
  49         uint32_t distance = 0;
  50
  51         memcpy(ip1_k, ip_key(ip1), sizeof(ip1_k));
  52         t = ip_key(ip2);
  53         for (i=0; i<IP_KEYLEN; i++) {
  54                 x = ip1_k[i] ^ t[i];
  55                 if (x == 0) {
  56                         distance += 32;
  57                 } else {
  58                         /* Count number of leading zeroes.
  59                          * FIXME? This could be optimised...
  60                          */
  61                         while ((x & (1 << 31)) == 0) {
  62                                 x <<= 1;
  63                                 distance += 1;
  64                         }
  65                 }
  66         }
  67
  68         return distance;
  69 }
  70
  71 /* Calculate the IP distance for the given IP relative to IPs on the
  72    given node.  The ips argument is generally the all_ips variable
  73    used in the main part of the algorithm.
  74  */
  75 static uint32_t ip_distance_2_sum(ctdb_sock_addr *ip,
  76                                   struct public_ip_list *ips,
  77                                   int pnn)
  78 {
  79         struct public_ip_list *t;
  80         uint32_t d;
  81
  82         uint32_t sum = 0;
  83
  84         for (t = ips; t != NULL; t = t->next) {
  85                 if (t->pnn != pnn) {
  86                         continue;
  87                 }
  88
  89                 /* Optimisation: We never calculate the distance
  90                  * between an address and itself.  This allows us to
  91                  * calculate the effect of removing an address from a
  92                  * node by simply calculating the distance between
  93                  * that address and all of the exitsing addresses.
  94                  * Moreover, we assume that we're only ever dealing
  95                  * with addresses from all_ips so we can identify an
  96                  * address via a pointer rather than doing a more
  97                  * expensive address comparison. */
  98                 if (&(t->addr) == ip) {
  99                         continue;
 100                 }
 101
 102                 d = ip_distance(ip, &(t->addr));
 103                 sum += d * d;  /* Cheaper than pulling in math.h :-) */
 104         }
 105
 106         return sum;
 107 }
 108
 109 /* Return the LCP2 imbalance metric for addresses currently assigned
 110    to the given node.
 111  */
 112 static uint32_t lcp2_imbalance(struct public_ip_list * all_ips, int pnn)
 113 {
 114         struct public_ip_list *t;
 115
 116         uint32_t imbalance = 0;
 117
 118         for (t = all_ips; t != NULL; t = t->next) {
 119                 if (t->pnn != pnn) {
 120                         continue;
 121                 }
 122                 /* Pass the rest of the IPs rather than the whole
 123                    all_ips input list.
 124                 */
 125                 imbalance += ip_distance_2_sum(&(t->addr), t->next, pnn);
 126         }
 127
 128         return imbalance;
 129 }
 130
 131 static bool lcp2_init(struct ipalloc_state *ipalloc_state,
 132                       uint32_t **lcp2_imbalances,
 133                       bool **rebalance_candidates)
 134 {
 135         int i, numnodes;
 136         struct public_ip_list *t;
 137
 138         numnodes = ipalloc_state->num;
 139
 140         *rebalance_candidates = talloc_array(ipalloc_state, bool, numnodes);
 141         if (*rebalance_candidates == NULL) {
 142                 DEBUG(DEBUG_ERR, (__location__ " out of memory\n"));
 143                 return false;
 144         }
 145         *lcp2_imbalances = talloc_array(ipalloc_state, uint32_t, numnodes);
 146         if (*lcp2_imbalances == NULL) {
 147                 DEBUG(DEBUG_ERR, (__location__ " out of memory\n"));
 148                 return false;
 149         }
 150
 151         for (i=0; i<numnodes; i++) {
 152                 (*lcp2_imbalances)[i] =
 153                         lcp2_imbalance(ipalloc_state->all_ips, i);
 154                 /* First step: assume all nodes are candidates */
 155                 (*rebalance_candidates)[i] = true;
 156         }
 157
 158         /* 2nd step: if a node has IPs assigned then it must have been
 159          * healthy before, so we remove it from consideration.  This
 160          * is overkill but is all we have because we don't maintain
 161          * state between takeover runs.  An alternative would be to
 162          * keep state and invalidate it every time the recovery master
 163          * changes.
 164          */
 165         for (t = ipalloc_state->all_ips; t != NULL; t = t->next) {
 166                 if (t->pnn != -1) {
 167                         (*rebalance_candidates)[t->pnn] = false;
 168                 }
 169         }
 170
 171         /* 3rd step: if a node is forced to re-balance then
 172            we allow failback onto the node */
 173         if (ipalloc_state->force_rebalance_nodes == NULL) {
 174                 return true;
 175         }
 176         for (i = 0;
 177              i < talloc_array_length(ipalloc_state->force_rebalance_nodes);
 178              i++) {
 179                 uint32_t pnn = ipalloc_state->force_rebalance_nodes[i];
 180                 if (pnn >= numnodes) {
 181                         DEBUG(DEBUG_ERR,
 182                               (__location__ "unknown node %u\n", pnn));
 183                         continue;
 184                 }
 185
 186                 DEBUG(DEBUG_NOTICE,
 187                       ("Forcing rebalancing of IPs to node %u\n", pnn));
 188                 (*rebalance_candidates)[pnn] = true;
 189         }
 190
 191         return true;
 192 }
 193
 194 /* Allocate any unassigned addresses using the LCP2 algorithm to find
 195  * the IP/node combination that will cost the least.
 196  */
 197 static void lcp2_allocate_unassigned(struct ipalloc_state *ipalloc_state,
 198                                      uint32_t *lcp2_imbalances)
 199 {
 200         struct public_ip_list *t;
 201         int dstnode, numnodes;
 202
 203         int minnode;
 204         uint32_t mindsum, dstdsum, dstimbl, minimbl;
 205         struct public_ip_list *minip;
 206
 207         bool should_loop = true;
 208         bool have_unassigned = true;
 209
 210         numnodes = ipalloc_state->num;
 211
 212         while (have_unassigned && should_loop) {
 213                 should_loop = false;
 214
 215                 DEBUG(DEBUG_DEBUG,(" ----------------------------------------\n"));
 216                 DEBUG(DEBUG_DEBUG,(" CONSIDERING MOVES (UNASSIGNED)\n"));
 217
 218                 minnode = -1;
 219                 mindsum = 0;
 220                 minip = NULL;
 221
 222                 /* loop over each unassigned ip. */
 223                 for (t = ipalloc_state->all_ips; t != NULL ; t = t->next) {
 224                         if (t->pnn != -1) {
 225                                 continue;
 226                         }
 227
 228                         for (dstnode = 0; dstnode < numnodes; dstnode++) {
 229                                 /* only check nodes that can actually takeover this ip */
 230                                 if (!can_node_takeover_ip(ipalloc_state,
 231                                                           dstnode,
 232                                                           t)) {
 233                                         /* no it couldnt   so skip to the next node */
 234                                         continue;
 235                                 }
 236
 237                                 dstdsum = ip_distance_2_sum(&(t->addr),
 238                                                             ipalloc_state->all_ips,
 239                                                             dstnode);
 240                                 dstimbl = lcp2_imbalances[dstnode] + dstdsum;
 241                                 DEBUG(DEBUG_DEBUG,
 242                                       (" %s -> %d [+%d]\n",
 243                                        ctdb_sock_addr_to_string(ipalloc_state,
 244                                                                 &(t->addr)),
 245                                        dstnode,
 246                                        dstimbl - lcp2_imbalances[dstnode]));
 247
 248
 249                                 if ((minnode == -1) || (dstdsum < mindsum)) {
 250                                         minnode = dstnode;
 251                                         minimbl = dstimbl;
 252                                         mindsum = dstdsum;
 253                                         minip = t;
 254                                         should_loop = true;
 255                                 }
 256                         }
 257                 }
 258
 259                 DEBUG(DEBUG_DEBUG,(" ----------------------------------------\n"));
 260
 261                 /* If we found one then assign it to the given node. */
 262                 if (minnode != -1) {
 263                         minip->pnn = minnode;
 264                         lcp2_imbalances[minnode] = minimbl;
 265                         DEBUG(DEBUG_INFO,(" %s -> %d [+%d]\n",
 266                                           ctdb_sock_addr_to_string(
 267                                                   ipalloc_state,
 268                                                   &(minip->addr)),
 269                                           minnode,
 270                                           mindsum));
 271                 }
 272
 273                 /* There might be a better way but at least this is clear. */
 274                 have_unassigned = false;
 275                 for (t = ipalloc_state->all_ips; t != NULL; t = t->next) {
 276                         if (t->pnn == -1) {
 277                                 have_unassigned = true;
 278                         }
 279                 }
 280         }
 281
 282         /* We know if we have an unassigned addresses so we might as
 283          * well optimise.
 284          */
 285         if (have_unassigned) {
 286                 for (t = ipalloc_state->all_ips; t != NULL; t = t->next) {
 287                         if (t->pnn == -1) {
 288                                 DEBUG(DEBUG_WARNING,
 289                                       ("Failed to find node to cover ip %s\n",
 290                                        ctdb_sock_addr_to_string(ipalloc_state,
 291                                                                 &t->addr)));
 292                         }
 293                 }
 294         }
 295 }
 296
 297 /* LCP2 algorithm for rebalancing the cluster.  Given a candidate node
 298  * to move IPs from, determines the best IP/destination node
 299  * combination to move from the source node.
 300  */
 301 static bool lcp2_failback_candidate(struct ipalloc_state *ipalloc_state,
 302                                     int srcnode,
 303                                     uint32_t *lcp2_imbalances,
 304                                     bool *rebalance_candidates)
 305 {
 306         int dstnode, mindstnode, numnodes;
 307         uint32_t srcimbl, srcdsum, dstimbl, dstdsum;
 308         uint32_t minsrcimbl, mindstimbl;
 309         struct public_ip_list *minip;
 310         struct public_ip_list *t;
 311
 312         /* Find an IP and destination node that best reduces imbalance. */
 313         srcimbl = 0;
 314         minip = NULL;
 315         minsrcimbl = 0;
 316         mindstnode = -1;
 317         mindstimbl = 0;
 318
 319         numnodes = ipalloc_state->num;
 320
 321         DEBUG(DEBUG_DEBUG,(" ----------------------------------------\n"));
 322         DEBUG(DEBUG_DEBUG,(" CONSIDERING MOVES FROM %d [%d]\n",
 323                            srcnode, lcp2_imbalances[srcnode]));
 324
 325         for (t = ipalloc_state->all_ips; t != NULL; t = t->next) {
 326                 /* Only consider addresses on srcnode. */
 327                 if (t->pnn != srcnode) {
 328                         continue;
 329                 }
 330
 331                 /* What is this IP address costing the source node? */
 332                 srcdsum = ip_distance_2_sum(&(t->addr),
 333                                             ipalloc_state->all_ips,
 334                                             srcnode);
 335                 srcimbl = lcp2_imbalances[srcnode] - srcdsum;
 336
 337                 /* Consider this IP address would cost each potential
 338                  * destination node.  Destination nodes are limited to
 339                  * those that are newly healthy, since we don't want
 340                  * to do gratuitous failover of IPs just to make minor
 341                  * balance improvements.
 342                  */
 343                 for (dstnode = 0; dstnode < numnodes; dstnode++) {
 344                         if (!rebalance_candidates[dstnode]) {
 345                                 continue;
 346                         }
 347
 348                         /* only check nodes that can actually takeover this ip */
 349                         if (!can_node_takeover_ip(ipalloc_state, dstnode,
 350                                                   t)) {
 351                                 /* no it couldnt   so skip to the next node */
 352                                 continue;
 353                         }
 354
 355                         dstdsum = ip_distance_2_sum(&(t->addr),
 356                                                     ipalloc_state->all_ips,
 357                                                     dstnode);
 358                         dstimbl = lcp2_imbalances[dstnode] + dstdsum;
 359                         DEBUG(DEBUG_DEBUG,(" %d [%d] -> %s -> %d [+%d]\n",
 360                                            srcnode, -srcdsum,
 361                                            ctdb_sock_addr_to_string(
 362                                                    ipalloc_state, &(t->addr)),
 363                                            dstnode, dstdsum));
 364
 365                         if ((dstimbl < lcp2_imbalances[srcnode]) &&
 366                             (dstdsum < srcdsum) &&                      \
 367                             ((mindstnode == -1) ||                              \
 368                              ((srcimbl + dstimbl) < (minsrcimbl + mindstimbl)))) {
 369
 370                                 minip = t;
 371                                 minsrcimbl = srcimbl;
 372                                 mindstnode = dstnode;
 373                                 mindstimbl = dstimbl;
 374                         }
 375                 }
 376         }
 377         DEBUG(DEBUG_DEBUG,(" ----------------------------------------\n"));
 378
 379         if (mindstnode != -1) {
 380                 /* We found a move that makes things better... */
 381                 DEBUG(DEBUG_INFO,
 382                       ("%d [%d] -> %s -> %d [+%d]\n",
 383                        srcnode, minsrcimbl - lcp2_imbalances[srcnode],
 384                        ctdb_sock_addr_to_string(ipalloc_state, &(minip->addr)),
 385                        mindstnode, mindstimbl - lcp2_imbalances[mindstnode]));
 386
 387
 388                 lcp2_imbalances[srcnode] = minsrcimbl;
 389                 lcp2_imbalances[mindstnode] = mindstimbl;
 390                 minip->pnn = mindstnode;
 391
 392                 return true;
 393         }
 394
 395         return false;
 396 }
 397
 398 struct lcp2_imbalance_pnn {
 399         uint32_t imbalance;
 400         int pnn;
 401 };
 402
 403 static int lcp2_cmp_imbalance_pnn(const void * a, const void * b)
 404 {
 405         const struct lcp2_imbalance_pnn * lipa = (const struct lcp2_imbalance_pnn *) a;
 406         const struct lcp2_imbalance_pnn * lipb = (const struct lcp2_imbalance_pnn *) b;
 407
 408         if (lipa->imbalance > lipb->imbalance) {
 409                 return -1;
 410         } else if (lipa->imbalance == lipb->imbalance) {
 411                 return 0;
 412         } else {
 413                 return 1;
 414         }
 415 }
 416
 417 /* LCP2 algorithm for rebalancing the cluster.  This finds the source
 418  * node with the highest LCP2 imbalance, and then determines the best
 419  * IP/destination node combination to move from the source node.
 420  */
 421 static void lcp2_failback(struct ipalloc_state *ipalloc_state,
 422                           uint32_t *lcp2_imbalances,
 423                           bool *rebalance_candidates)
 424 {
 425         int i, numnodes;
 426         struct lcp2_imbalance_pnn * lips;
 427         bool again;
 428
 429         numnodes = ipalloc_state->num;
 430
 431 try_again:
 432         /* Put the imbalances and nodes into an array, sort them and
 433          * iterate through candidates.  Usually the 1st one will be
 434          * used, so this doesn't cost much...
 435          */
 436         DEBUG(DEBUG_DEBUG,("+++++++++++++++++++++++++++++++++++++++++\n"));
 437         DEBUG(DEBUG_DEBUG,("Selecting most imbalanced node from:\n"));
 438         lips = talloc_array(ipalloc_state, struct lcp2_imbalance_pnn, numnodes);
 439         for (i = 0; i < numnodes; i++) {
 440                 lips[i].imbalance = lcp2_imbalances[i];
 441                 lips[i].pnn = i;
 442                 DEBUG(DEBUG_DEBUG,(" %d [%d]\n", i, lcp2_imbalances[i]));
 443         }
 444         qsort(lips, numnodes, sizeof(struct lcp2_imbalance_pnn),
 445               lcp2_cmp_imbalance_pnn);
 446
 447         again = false;
 448         for (i = 0; i < numnodes; i++) {
 449                 /* This means that all nodes had 0 or 1 addresses, so
 450                  * can't be imbalanced.
 451                  */
 452                 if (lips[i].imbalance == 0) {
 453                         break;
 454                 }
 455
 456                 if (lcp2_failback_candidate(ipalloc_state,
 457                                             lips[i].pnn,
 458                                             lcp2_imbalances,
 459                                             rebalance_candidates)) {
 460                         again = true;
 461                         break;
 462                 }
 463         }
 464
 465         talloc_free(lips);
 466         if (again) {
 467                 goto try_again;
 468         }
 469 }
 470
 471 bool ipalloc_lcp2(struct ipalloc_state *ipalloc_state)
 472 {
 473         uint32_t *lcp2_imbalances;
 474         bool *rebalance_candidates;
 475         int numnodes, num_rebalance_candidates, i;
 476         bool ret = true;
 477
 478         unassign_unsuitable_ips(ipalloc_state);
 479
 480         if (!lcp2_init(ipalloc_state,
 481                        &lcp2_imbalances, &rebalance_candidates)) {
 482                 ret = false;
 483                 goto finished;
 484         }
 485
 486         lcp2_allocate_unassigned(ipalloc_state, lcp2_imbalances);
 487
 488         /* If we don't want IPs to fail back then don't rebalance IPs. */
 489         if (1 == ipalloc_state->no_ip_failback) {
 490                 goto finished;
 491         }
 492
 493         /* It is only worth continuing if we have suitable target
 494          * nodes to transfer IPs to.  This check is much cheaper than
 495          * continuing on...
 496          */
 497         numnodes = ipalloc_state->num;
 498         num_rebalance_candidates = 0;
 499         for (i=0; i<numnodes; i++) {
 500                 if (rebalance_candidates[i]) {
 501                         num_rebalance_candidates++;
 502                 }
 503         }
 504         if (num_rebalance_candidates == 0) {
 505                 goto finished;
 506         }
 507
 508         /* Now, try to make sure the ip adresses are evenly distributed
 509            across the nodes.
 510         */
 511         lcp2_failback(ipalloc_state, lcp2_imbalances, rebalance_candidates);
 512
 513 finished:
 514         return ret;
 515 }