LCP IP allocation algorithm - new function lcp2_failback_candidate()

There's a bug in LCP2.  Selecting the node with the highest imbalance
doesn't always work.  Some nodes can have a high imbalance metric
because they have a lot of IPs.  However, these nodes can be part of a
group that is perfectly balanced.  Nodes in another group with less
IPs might actually be imbalanced.

Factor out the code from lcp2_failback() that actually takes a node
and decides which address should be moved to which node.

This is the first step in fixing the above bug.

Signed-off-by: Martin Schwenke <martin@meltin.net>

diff --git a/server/ctdb_takeover.c b/server/ctdb_takeover.c
index 5865a17d3ae03aab3e32b57976d0df6ff05c82ae..20311724834e71988fbfc104576bb89e9b935ce3 100644 (file)
--- a/server/ctdb_takeover.c
+++ b/server/ctdb_takeover.c
@@ -1607,57 +1607,26 @@ void lcp2_allocate_unassigned(struct ctdb_context *ctdb,
        }
 }
 
-/* LCP2 algorithm for rebalancing the cluster.  This finds the source
- * node with the highest LCP2 imbalance, and then determines the best
- * IP/destination node combination to move from the source node.
+/* LCP2 algorithm for rebalancing the cluster.  Given a candidate node
+ * to move IPs from, determines the best IP/destination node
+ * combination to move from the source node.
  *
  * Not static, so we can easily link it into a unit test.
  */
-bool lcp2_failback(struct ctdb_context *ctdb,
-                  struct ctdb_node_map *nodemap,
-                  uint32_t mask,
-                  struct ctdb_public_ip_list *all_ips,
-                  uint32_t *lcp2_imbalances,
-                  bool *newly_healthy)
-{
-       int srcnode, dstnode, mindstnode, i, num_newly_healthy;
-       uint32_t srcimbl, srcdsum, maximbl, dstimbl, dstdsum;
-       uint32_t minsrcimbl, mindstimbl, b;
+bool lcp2_failback_candidate(struct ctdb_context *ctdb,
+                            struct ctdb_node_map *nodemap,
+                            struct ctdb_public_ip_list *all_ips,
+                            int srcnode,
+                            uint32_t candimbl,
+                            uint32_t *lcp2_imbalances,
+                            bool *newly_healthy)
+{
+       int dstnode, mindstnode;
+       uint32_t srcimbl, srcdsum, dstimbl, dstdsum;
+       uint32_t minsrcimbl, mindstimbl;
        struct ctdb_public_ip_list *minip;
        struct ctdb_public_ip_list *tmp_ip;
 
-       /* It is only worth continuing if we have suitable target
-        * nodes to transfer IPs to.  This check is much cheaper than
-        * continuing on...
-        */
-       num_newly_healthy = 0;
-       for (i = 0; i < nodemap->num; i++) {
-               if (newly_healthy[i]) {
-                       num_newly_healthy++;
-               }
-       }
-       if (num_newly_healthy == 0) {
-               return false;
-       }
-
-        /* Get the node with the highest imbalance metric. */
-        srcnode = -1;
-        maximbl = 0;
-       for (i=0; i < nodemap->num; i++) {
-               b = lcp2_imbalances[i];
-               if ((srcnode == -1) || (b > maximbl)) {
-                       srcnode = i;
-                       maximbl = b;
-               }
-       }
-
-        /* This means that all nodes had 0 or 1 addresses, so can't be
-        * imbalanced.
-        */
-        if (maximbl == 0) {
-               return false;
-       }
-
        /* Find an IP and destination node that best reduces imbalance. */
        minip = NULL;
        minsrcimbl = 0;
@@ -1665,7 +1634,7 @@ bool lcp2_failback(struct ctdb_context *ctdb,
        mindstimbl = 0;
 
        DEBUG(DEBUG_DEBUG,(" ----------------------------------------\n"));
-       DEBUG(DEBUG_DEBUG,(" CONSIDERING MOVES FROM %d [%d]\n", srcnode, maximbl));
+       DEBUG(DEBUG_DEBUG,(" CONSIDERING MOVES FROM %d [%d]\n", srcnode, candimbl));
 
        for (tmp_ip=all_ips; tmp_ip; tmp_ip=tmp_ip->next) {
                /* Only consider addresses on srcnode. */
@@ -1675,7 +1644,7 @@ bool lcp2_failback(struct ctdb_context *ctdb,
 
                /* What is this IP address costing the source node? */
                srcdsum = ip_distance_2_sum(&(tmp_ip->addr), all_ips, srcnode);
-               srcimbl = maximbl - srcdsum;
+               srcimbl = candimbl - srcdsum;
 
                /* Consider this IP address would cost each potential
                 * destination node.  Destination nodes are limited to
@@ -1700,7 +1669,7 @@ bool lcp2_failback(struct ctdb_context *ctdb,
                                           ctdb_addr_to_str(&(tmp_ip->addr)),
                                           dstnode, dstimbl - lcp2_imbalances[dstnode]));
 
-                       if ((dstimbl < maximbl) && (dstdsum < srcdsum) && \
+                       if ((dstimbl < candimbl) && (dstdsum < srcdsum) && \
                            ((mindstnode == -1) ||                              \
                             ((srcimbl + dstimbl) < (minsrcimbl + mindstimbl)))) {
 
@@ -1732,6 +1701,63 @@ bool lcp2_failback(struct ctdb_context *ctdb,
        
 }
 
+/* LCP2 algorithm for rebalancing the cluster.  This finds the source
+ * node with the highest LCP2 imbalance, and then determines the best
+ * IP/destination node combination to move from the source node.
+ *
+ * Not static, so we can easily link it into a unit test.
+ */
+bool lcp2_failback(struct ctdb_context *ctdb,
+                  struct ctdb_node_map *nodemap,
+                  uint32_t mask,
+                  struct ctdb_public_ip_list *all_ips,
+                  uint32_t *lcp2_imbalances,
+                  bool *newly_healthy)
+{
+       int srcnode, i, num_newly_healthy;
+       uint32_t maximbl, b;
+
+       /* It is only worth continuing if we have suitable target
+        * nodes to transfer IPs to.  This check is much cheaper than
+        * continuing on...
+        */
+       num_newly_healthy = 0;
+       for (i = 0; i < nodemap->num; i++) {
+               if (newly_healthy[i]) {
+                       num_newly_healthy++;
+               }
+       }
+       if (num_newly_healthy == 0) {
+               return false;
+       }
+
+        /* Get the node with the highest imbalance metric. */
+        srcnode = -1;
+        maximbl = 0;
+       for (i=0; i < nodemap->num; i++) {
+               b = lcp2_imbalances[i];
+               if ((srcnode == -1) || (b > maximbl)) {
+                       srcnode = i;
+                       maximbl = b;
+               }
+       }
+
+        /* This means that all nodes had 0 or 1 addresses, so can't be
+        * imbalanced.
+        */
+        if (maximbl == 0) {
+               return false;
+       }
+
+       return lcp2_failback_candidate(ctdb,
+                                      nodemap,
+                                      all_ips,
+                                      srcnode,
+                                      maximbl,
+                                      lcp2_imbalances,
+                                      newly_healthy);
+}
+
 /* The calculation part of the IP allocation algorithm.
  * Not static, so we can easily link it into a unit test.
  */