source: bin/varnishd/cache_dir_random.c @ c11726

Revision c11726, 7.1 KB checked in by Poul-Henning Kamp <phk@…>, 3 years ago (diff)

Update copyright notices to reflect development and copyright assignment
from Redpill Linpro AS to Varnish Software AS

  • Property mode set to 100644
Line 
1/*-
2 * Copyright (c) 2006 Verdens Gang AS
3 * Copyright (c) 2006-2010 Varnish Software AS
4 * All rights reserved.
5 *
6 * Author: Poul-Henning Kamp <phk@phk.freebsd.dk>
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 * 1. Redistributions of source code must retain the above copyright
12 *    notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 *    notice, this list of conditions and the following disclaimer in the
15 *    documentation and/or other materials provided with the distribution.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED.  IN NO EVENT SHALL AUTHOR OR CONTRIBUTORS BE LIABLE
21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27 * SUCH DAMAGE.
28 *
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.
40 */
41
42#include "config.h"
43
44#include <sys/types.h>
45#include <sys/socket.h>
46
47#include <stdio.h>
48#include <errno.h>
49#include <stdlib.h>
50#include <string.h>
51#include <unistd.h>
52
53#include "cache.h"
54#include "cache_backend.h"
55#include "vrt.h"
56#include "vsha256.h"
57#include "vend.h"
58
59/*--------------------------------------------------------------------*/
60
61struct vdi_random_host {
62        struct director         *backend;
63        double                  weight;
64};
65
66enum crit_e {c_random, c_hash, c_client};
67
68struct vdi_random {
69        unsigned                magic;
70#define VDI_RANDOM_MAGIC        0x3771ae23
71        struct director         dir;
72
73        enum crit_e             criteria;
74        unsigned                retries;
75        double                  tot_weight;
76        struct vdi_random_host  *hosts;
77        unsigned                nhosts;
78};
79
80static struct vbc *
81vdi_random_getfd(const struct director *d, struct sess *sp)
82{
83        int i, k;
84        struct vdi_random *vs;
85        double r, s1;
86        unsigned u = 0;
87        struct vbc *vbe;
88        struct director *d2;
89        struct SHA256Context ctx;
90        uint8_t sign[SHA256_LEN], *hp = NULL;
91
92        CHECK_OBJ_NOTNULL(sp, SESS_MAGIC);
93        CHECK_OBJ_NOTNULL(d, DIRECTOR_MAGIC);
94        CAST_OBJ_NOTNULL(vs, d->priv, VDI_RANDOM_MAGIC);
95
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++;
184        }
185        return (NULL);
186}
187
188static unsigned
189vdi_random_healthy(const struct director *d, const struct sess *sp)
190{
191        struct vdi_random *vs;
192        int i;
193
194        CHECK_OBJ_NOTNULL(d, DIRECTOR_MAGIC);
195        CAST_OBJ_NOTNULL(vs, d->priv, VDI_RANDOM_MAGIC);
196
197        for (i = 0; i < vs->nhosts; i++) {
198                if (VDI_Healthy(vs->hosts[i].backend, sp))
199                        return (1);
200        }
201        return (0);
202}
203
204static void
205vdi_random_fini(const struct director *d)
206{
207        struct vdi_random *vs;
208
209        CHECK_OBJ_NOTNULL(d, DIRECTOR_MAGIC);
210        CAST_OBJ_NOTNULL(vs, d->priv, VDI_RANDOM_MAGIC);
211
212        free(vs->hosts);
213        free(vs->dir.vcl_name);
214        vs->dir.magic = 0;
215        FREE_OBJ(vs);
216}
217
218static void
219vrt_init(struct cli *cli, struct director **bp, int idx,
220    const void *priv, enum crit_e criteria)
221{
222        const struct vrt_dir_random *t;
223        struct vdi_random *vs;
224        const struct vrt_dir_random_entry *te;
225        struct vdi_random_host *vh;
226        int i;
227
228        ASSERT_CLI();
229        (void)cli;
230        t = priv;
231
232        ALLOC_OBJ(vs, VDI_RANDOM_MAGIC);
233        XXXAN(vs);
234        vs->hosts = calloc(sizeof *vh, t->nmember);
235        XXXAN(vs->hosts);
236
237        vs->dir.magic = DIRECTOR_MAGIC;
238        vs->dir.priv = vs;
239        vs->dir.name = "random";
240        REPLACE(vs->dir.vcl_name, t->name);
241        vs->dir.getfd = vdi_random_getfd;
242        vs->dir.fini = vdi_random_fini;
243        vs->dir.healthy = vdi_random_healthy;
244
245        vs->criteria = criteria;
246        vs->retries = t->retries;
247        if (vs->retries == 0)
248                vs->retries = t->nmember;
249        vh = vs->hosts;
250        te = t->members;
251        vs->tot_weight = 0.;
252        for (i = 0; i < t->nmember; i++, vh++, te++) {
253                assert(te->weight > 0.0);
254                vh->weight = te->weight;
255                vs->tot_weight += vh->weight;
256                vh->backend = bp[te->host];
257                AN(vh->backend);
258        }
259        vs->nhosts = t->nmember;
260        bp[idx] = &vs->dir;
261}
262
263void
264VRT_init_dir_random(struct cli *cli, struct director **bp, int idx,
265    const void *priv)
266{
267        vrt_init(cli, bp, idx, priv, c_random);
268}
269
270void
271VRT_init_dir_hash(struct cli *cli, struct director **bp, int idx,
272    const void *priv)
273{
274        vrt_init(cli, bp, idx, priv, c_hash);
275}
276
277void
278VRT_init_dir_client(struct cli *cli, struct director **bp, int idx,
279    const void *priv)
280{
281        vrt_init(cli, bp, idx, priv, c_client);
282}
Note: See TracBrowser for help on using the repository browser.