Ignore:
Timestamp:
2011-08-15 20:45:58 (3 years ago)
Author:
Poul-Henning Kamp <phk@…>
Branches:
master, 4.0, experimental-ims
Children:
b38682
Parents:
0caee0
git-author:
Poul-Henning Kamp <phk@…> (2011-08-15 20:45:58)
git-committer:
Poul-Henning Kamp <phk@…> (2011-08-15 20:45:58)
Message:

Implement a consistent retry policy in the random/client/hash director:

If the first (policy-chosen) backend fails to get us a connection,
retry a random backend (still according to their weight) until
retries are exhausted.

Kristian sent a proof of concept patch, I just cleaned it up and made
it compile.

Thanks to: Kristian

Fixes #977

File:
1 edited

Legend:

Unmodified
Added
Removed
  • bin/varnishd/cache_dir_random.c

    rc11726 r149c4d  
    11/*- 
    22 * Copyright (c) 2006 Verdens Gang AS 
    3  * Copyright (c) 2006-2010 Varnish Software AS 
     3 * Copyright (c) 2006-2011 Varnish Software AS 
    44 * All rights reserved. 
    55 * 
     
    2727 * SUCH DAMAGE. 
    2828 * 
    29  * This code is shared between the random and hash directors, because they 
    30  * share the same properties and most of the same selection logic. 
    31  * 
    32  * The random director picks a backend on random, according to weight, 
    33  * from the healty subset of backends. 
    34  * 
    35  * The hash director first tries to locate the "canonical" backend from 
    36  * the full set, according to weight, and if it is healthy selects it. 
    37  * If the canonical backend is not healthy, we pick a backend according 
    38  * to weight from the healthy subset. That way only traffic to unhealthy 
    39  * backends gets redistributed. 
     29 * This code is shared between the random, client and hash directors, because 
     30 * they share the same properties and most of the same selection logic. 
     31 * 
     32 * The random director picks a backend on random. 
     33 * 
     34 * The hash director picks based on the hash from vcl_hash{} 
     35 * 
     36 * The client director picks based on client identity or IP-address 
     37 * 
     38 * In all cases, the choice is by weight of the healthy subset of 
     39 * configured backends. 
     40 * 
     41 * Failures to get a connection are retried, here all three policies 
     42 * fall back to a deterministically random choice, by weight in the 
     43 * healthy subset. 
     44 * 
    4045 */ 
    4146 
     
    4752#include <stdio.h> 
    4853#include <errno.h> 
     54#include <math.h> 
    4955#include <stdlib.h> 
    5056#include <string.h> 
     
    7884}; 
    7985 
     86/* 
     87 * Applies sha256 using the given context and input/length, and returns 
     88 * a double in the range [0...1[ based on the hash. 
     89 */ 
     90static double 
     91vdi_random_sha(const char *input, ssize_t len) 
     92{ 
     93        struct SHA256Context ctx; 
     94        uint8_t sign[SHA256_LEN]; 
     95 
     96        AN(input); 
     97        SHA256_Init(&ctx); 
     98        SHA256_Update(&ctx, input, len); 
     99        SHA256_Final(sign, &ctx); 
     100        return (vle32dec(sign) / exp2(32)); 
     101} 
     102 
     103/* 
     104 * Sets up the initial seed for picking a backend according to policy. 
     105 */ 
     106static double 
     107vdi_random_init_seed(const struct vdi_random *vs, const struct sess *sp) 
     108{ 
     109        const char *p; 
     110        double retval; 
     111 
     112        switch (vs->criteria) { 
     113        case c_client: 
     114                if (sp->client_identity != NULL) 
     115                        p = sp->client_identity; 
     116                else 
     117                        p = sp->addr; 
     118                retval = vdi_random_sha(p, strlen(p)); 
     119                break; 
     120        case c_hash: 
     121                AN(sp->digest); 
     122                retval = vle32dec(sp->digest) / exp2(32); 
     123                break; 
     124        case c_random: 
     125        default: 
     126                retval = random() / exp2(31); 
     127                break; 
     128        } 
     129        return (retval); 
     130} 
     131 
     132/* 
     133 * Find the healthy backend corresponding to the weight r [0...1[ 
     134 */ 
     135static struct vbc * 
     136vdi_random_pick_one(struct sess *sp, const struct vdi_random *vs, double r) 
     137{ 
     138        double w[vs->nhosts]; 
     139        int i; 
     140        double s1; 
     141 
     142        assert(r >= 0.0 && r < 1.0); 
     143 
     144        memset(w, 0, sizeof w); 
     145        /* Sum up the weights of healty backends */ 
     146        s1 = 0.0; 
     147        for (i = 0; i < vs->nhosts; i++) { 
     148                if (VDI_Healthy(vs->hosts[i].backend, sp)) 
     149                        w[i] = vs->hosts[i].weight; 
     150                s1 += w[i]; 
     151        } 
     152 
     153        if (s1 == 0.0) 
     154                return (NULL); 
     155 
     156        r *= s1; 
     157        s1 = 0.0; 
     158        for (i = 0; i < vs->nhosts; i++)  { 
     159                s1 += w[i]; 
     160                if (r < s1) 
     161                        return(VDI_GetFd(vs->hosts[i].backend, sp)); 
     162        } 
     163        return (NULL); 
     164} 
     165 
     166/* 
     167 * Try the specified number of times to get a backend. 
     168 * First one according to policy, after that, deterministically 
     169 * random by rehashing the key. 
     170 */ 
    80171static struct vbc * 
    81172vdi_random_getfd(const struct director *d, struct sess *sp) 
    82173{ 
    83         int i, k; 
    84         struct vdi_random *vs; 
    85         double r, s1; 
    86         unsigned u = 0; 
     174        int k; 
     175        struct vdi_random *vs; 
     176        double r; 
    87177        struct vbc *vbe; 
    88         struct director *d2; 
    89         struct SHA256Context ctx; 
    90         uint8_t sign[SHA256_LEN], *hp = NULL; 
    91178 
    92179        CHECK_OBJ_NOTNULL(sp, SESS_MAGIC); 
     
    94181        CAST_OBJ_NOTNULL(vs, d->priv, VDI_RANDOM_MAGIC); 
    95182 
    96         if (vs->criteria == c_client) { 
    97                 /* 
    98                  * Hash the client IP# ascii representation, rather than 
    99                  * rely on the raw IP# being a good hash distributor, since 
    100                  * experience shows this not to be the case. 
    101                  * We do not hash the port number, to make everybody behind 
    102                  * a given NAT gateway fetch from the same backend. 
    103                  */ 
    104                 SHA256_Init(&ctx); 
    105                 AN(sp->addr); 
    106                 if (sp->client_identity != NULL) 
    107                         SHA256_Update(&ctx, sp->client_identity, 
    108                             strlen(sp->client_identity)); 
    109                 else 
    110                         SHA256_Update(&ctx, sp->addr, strlen(sp->addr)); 
    111                 SHA256_Final(sign, &ctx); 
    112                 hp = sign; 
    113         } 
    114         if (vs->criteria == c_hash) { 
    115                 /* 
    116                  * Reuse the hash-string, the objective here is to fetch the 
    117                  * same object on the same backend all the time 
    118                  */ 
    119                 hp = sp->digest; 
    120         } 
    121  
    122         /* 
    123          * If we are hashing, first try to hit our "canonical backend" 
    124          * If that fails, we fall through, and select a weighted backend 
    125          * amongst the healthy set. 
    126          */ 
    127         if (vs->criteria != c_random) { 
    128                 AN(hp); 
    129                 u = vle32dec(hp); 
    130                 r = u / 4294967296.0; 
    131                 assert(r >= 0.0 && r < 1.0); 
    132                 r *= vs->tot_weight; 
    133                 s1 = 0.0; 
    134                 for (i = 0; i < vs->nhosts; i++)  { 
    135                         s1 += vs->hosts[i].weight; 
    136                         if (r >= s1) 
    137                                 continue; 
    138                         d2 = vs->hosts[i].backend; 
    139                         if (!VDI_Healthy(d2, sp)) 
    140                                 break; 
    141                         vbe = VDI_GetFd(d2, sp); 
    142                         if (vbe != NULL) 
    143                                 return (vbe); 
    144                         break; 
    145                 } 
    146         } 
    147  
    148         for (k = 0; k < vs->retries; ) { 
    149                 /* Sum up the weights of healty backends */ 
    150                 s1 = 0.0; 
    151                 for (i = 0; i < vs->nhosts; i++) { 
    152                         d2 = vs->hosts[i].backend; 
    153                         /* XXX: cache result of healty to avoid double work */ 
    154                         if (VDI_Healthy(d2, sp)) 
    155                                 s1 += vs->hosts[i].weight; 
    156                 } 
    157  
    158                 if (s1 == 0.0) 
    159                         return (NULL); 
    160  
    161                 if (vs->criteria != c_random) { 
    162                         r = u / 4294967296.0; 
    163                 } else { 
    164                         /* Pick a random threshold in that interval */ 
    165                         r = random() / 2147483648.0;    /* 2^31 */ 
    166                 } 
    167                 assert(r >= 0.0 && r < 1.0); 
    168                 r *= s1; 
    169  
    170                 s1 = 0.0; 
    171                 for (i = 0; i < vs->nhosts; i++)  { 
    172                         d2 = vs->hosts[i].backend; 
    173                         if (!VDI_Healthy(d2, sp)) 
    174                                 continue; 
    175                         s1 += vs->hosts[i].weight; 
    176                         if (r >= s1) 
    177                                 continue; 
    178                         vbe = VDI_GetFd(d2, sp); 
    179                         if (vbe != NULL) 
    180                                 return (vbe); 
    181                         break; 
    182                 } 
    183                 k++; 
     183        r = vdi_random_init_seed(vs, sp); 
     184 
     185        for (k = 0; k < vs->retries; k++) { 
     186                vbe = vdi_random_pick_one(sp, vs, r); 
     187                if (vbe != NULL) 
     188                        return (vbe); 
     189                r = vdi_random_sha((void *)&r, sizeof(r)); 
    184190        } 
    185191        return (NULL); 
    186192} 
    187193 
     194/* 
     195 * Healthy if just a single backend is... 
     196 */ 
    188197static unsigned 
    189198vdi_random_healthy(const struct director *d, const struct sess *sp) 
Note: See TracChangeset for help on using the changeset viewer.