[PATCH] Improved hash director behavior

[WaveCDN Development]

This patch improves the behavior of the hash director when some of its 
backends get unhealty. The hash range of each unhealthy backend is 
splitted and mapped to the remaining healthy backends. Thus, not the 
complete hash range is beeing remapped and backends will perform better.
---
  bin/varnishd/cache/cache_dir_random.c |   75 
++++++++++++++++++++++++++++++++-
  1 files changed, 74 insertions(+), 1 deletions(-)

diff --git a/bin/varnishd/cache/cache_dir_random.c 
b/bin/varnishd/cache/cache_dir_random.c
index b323343..a7ae4e0 100644
--- a/bin/varnishd/cache/cache_dir_random.c
+++ b/bin/varnishd/cache/cache_dir_random.c
@@ -125,6 +125,7 @@ vdi_random_init_seed(const struct vdi_random *vs, 
const struct sess *sp)
   /*
   * Find the healthy backend corresponding to the weight r [0...1[
+ * except for the hash director.
   */
  static struct vbc *
  vdi_random_pick_one(struct sess *sp, const struct vdi_random *vs, 
double r)
@@ -158,6 +159,75 @@ vdi_random_pick_one(struct sess *sp, const struct 
vdi_random *vs, double r)
  }
   /*
+ * Find the healthy backend corresponding to the weight r [0...1[
+ * for the hash director. When a backend becomes unhealthy, its hash
+ * range is splitted and mapped to the remaining healthy backends.
+ */
+static struct vbc *
+vdi_random_hash_pick_one(struct sess *sp, const struct vdi_random *vs, 
double r)
+{
+	int nhealthy;
+	int healthy[vs->nhosts];
+	int i, j;
+	double s1;
+
+	assert(r >= 0.0 && r < 1.0);
+
+	/*
+	 * Get the number of healthy hosts, sum up weights,
+	 * initialize array w with host weights and
+	 * build arry with indizes of healthy hosts.
+	 */
+	nhealthy = 0;
+	s1 = 0.0;
+	for (i = 0; i < vs->nhosts; i++) {
+		if (VDI_Healthy(vs->hosts[i].backend, sp))
+		{
+			healthy[i] = 1;
+			nhealthy++;
+		}
+		else
+		{
+			healthy[i] = 0;
+		}
+		s1 += vs->hosts[i].weight;
+	}
+	if (nhealthy == 0)
+		return (NULL);
+
+	/* Pick host */
+	r *= s1;
+	s1 = 0.0;
+	for (i = 0; i < vs->nhosts; i++)  {
+		if (healthy[i] == 1)
+		{
+			s1 += vs->hosts[i].weight;
+			if (r < s1)
+			{
+				return(VDI_GetFd(vs->hosts[i].backend, sp));
+			}
+		}
+		else
+		{
+			/* Host unhealthy, split his weight to healthy hosts */
+			double part = vs->hosts[i].weight / nhealthy;
+			for (j = 0; j < vs->nhosts; j++) {
+				if(healthy[j] == 1)
+				{
+					s1 += part;
+					if (r < s1)
+					{
+						return(VDI_GetFd(vs->hosts[healthy[j]].backend, sp));
+					}
+				}
+			}
+		}
+	}
+	return (NULL);
+}
+
+
+/*
   * Try the specified number of times to get a backend.
   * First one according to policy, after that, deterministically
   * random by rehashing the key.
@@ -177,7 +247,10 @@ vdi_random_getfd(const struct director *d, struct 
sess *sp)
  	r = vdi_random_init_seed(vs, sp);
   	for (k = 0; k < vs->retries; k++) {
-		vbe = vdi_random_pick_one(sp, vs, r);
+		if(vs->criteria == c_hash)
+			vbe = vdi_random_hash_pick_one(sp, vs, r);
+		else
+			vbe = vdi_random_pick_one(sp, vs, r);
  		if (vbe != NULL)
  			return (vbe);
  		r = vdi_random_sha((void *)&r, sizeof(r));
-- 
1.7.2.5