relayd: improving sessions distribution across hosts in hash mode

[Sebastian Benoit]

Hi,

relayd (when running relays) will distribute client sessions over hosts
using various algorithms. Some of them generate a hash from different data
and calculate modulo rlt->rlt_nhosts to find the host the session should go
to. If this host is down, the current algorithm simply selects the next host
that is up.

This puts heavier load on this next host, it would be nicer if the
connections would be distributed to more destinations.

The following diff changes this algorithm: if the chosen host is not
available, the hash value p is shifted to the right and the calculation is
retried until a host that is usable is found or a maximum of retires is
reached (in that case the old method is used).

ok?

diff --git usr.sbin/relayd/relay.c usr.sbin/relayd/relay.c
index f14d7c9..9bb69ba 100644
--- usr.sbin/relayd/relay.c
+++ usr.sbin/relayd/relay.c
@@ -1220,6 +1220,8 @@ relay_from_table(struct rsession *con)
        struct relay_table      *rlt = NULL;
        struct table            *table = NULL;
        int                      idx = -1;
+       int                      cnt = 0;
+       int                      maxtries;
        u_int64_t                p = 0;
 
        /* the table is already selected */
@@ -1275,18 +1277,38 @@ relay_from_table(struct rsession *con)
                /* NOTREACHED */
        }
        if (idx == -1) {
+               /* handle all hashing algorithms */
                p = SipHash24_End(&con->se_siphashctx);
 
                /* Reset hash context */
                SipHash24_Init(&con->se_siphashctx,
                    &rlay->rl_conf.hashkey.siphashkey);
 
-               if ((idx = p % rlt->rlt_nhosts) >= RELAY_MAXHOSTS)
-                       return (-1);
+               maxtries = (rlt->rlt_nhosts < RELAY_MAX_HASH_RETRIES ?
+                   rlt->rlt_nhosts : RELAY_MAX_HASH_RETRIES);
+               while (cnt < maxtries) {
+                       if ((idx = p % rlt->rlt_nhosts) >= RELAY_MAXHOSTS)
+                               return (-1);
+                       
+                       host = rlt->rlt_host[idx];
+
+                       DPRINTF("%s: session %d: table %s host %s, "
+                           "p 0x%016llx, idx %d, cnt %d, max %d",
+                           __func__, con->se_id, table->conf.name,
+                           host->conf.name, p, idx, cnt, maxtries);
+
+                       if (!table->conf.check || host->up == HOST_UP)
+                               goto found;
+                       p = p >> 1;
+                       cnt++;
+               }
+       } else {
+               /* handle all non-hashing algorithms */
+               host = rlt->rlt_host[idx];
+               DPRINTF("%s: session %d: table %s host %s, p 0x%016llx, idx %d",
+                   __func__, con->se_id, table->conf.name, host->conf.name, p, 
idx);
        }
-       host = rlt->rlt_host[idx];
-       DPRINTF("%s: session %d: table %s host %s, p 0x%016llx, idx %d",
-           __func__, con->se_id, table->conf.name, host->conf.name, p, idx);
+
        while (host != NULL) {
                DPRINTF("%s: session %d: host %s", __func__,
                    con->se_id, host->conf.name);
diff --git usr.sbin/relayd/relayd.h usr.sbin/relayd/relayd.h
index 3c7dc89..2e0fd58 100644
--- usr.sbin/relayd/relayd.h
+++ usr.sbin/relayd/relayd.h
@@ -76,6 +76,7 @@
 #define RELAY_BACKLOG          10
 #define RELAY_MAXLOOKUPLEVELS  5
 #define RELAY_OUTOF_FD_RETRIES 5
+#define RELAY_MAX_HASH_RETRIES 5
 
 #define CONFIG_RELOAD          0x00
 #define CONFIG_TABLES          0x01