src/carp.cc

   1 /*
   2  * Copyright (C) 1996-2015 The Squid Software Foundation and contributors
   3  *
   4  * Squid software is distributed under GPLv2+ license and includes
   5  * contributions from numerous individuals and organizations.
   6  * Please see the COPYING and CONTRIBUTORS files for details.
   7  */
   8
   9 /* DEBUG: section 39    Cache Array Routing Protocol */
  10
  11 #include "squid.h"
  12 #include "CachePeer.h"
  13 #include "HttpRequest.h"
  14 #include "mgr/Registration.h"
  15 #include "neighbors.h"
  16 #include "SquidConfig.h"
  17 #include "Store.h"
  18 #include "URL.h"
  19
  20 #include <cmath>
  21
  22 #define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))
  23
  24 static int n_carp_peers = 0;
  25 static CachePeer **carp_peers = NULL;
  26 static OBJH carpCachemgr;
  27
  28 static int
  29 peerSortWeight(const void *a, const void *b)
  30 {
  31     const CachePeer *const *p1 = (const CachePeer *const *)a;
  32     const CachePeer *const *p2 = (const CachePeer *const *)b;
  33     return (*p1)->weight - (*p2)->weight;
  34 }
  35
  36 static void
  37 carpRegisterWithCacheManager(void)
  38 {
  39     Mgr::RegisterAction("carp", "CARP information", carpCachemgr, 0, 1);
  40 }
  41
  42 void
  43 carpInit(void)
  44 {
  45     int W = 0;
  46     int K;
  47     int k;
  48     double P_last, X_last, Xn;
  49     CachePeer *p;
  50     CachePeer **P;
  51     char *t;
  52     /* Clean up */
  53
  54     for (k = 0; k < n_carp_peers; ++k) {
  55         cbdataReferenceDone(carp_peers[k]);
  56     }
  57
  58     safe_free(carp_peers);
  59     n_carp_peers = 0;
  60
  61     /* initialize cache manager before we have a chance to leave the execution path */
  62     carpRegisterWithCacheManager();
  63
  64     /* find out which peers we have */
  65
  66     for (p = Config.peers; p; p = p->next) {
  67         if (!p->options.carp)
  68             continue;
  69
  70         assert(p->type == PEER_PARENT);
  71
  72         if (p->weight == 0)
  73             continue;
  74
  75         ++n_carp_peers;
  76
  77         W += p->weight;
  78     }
  79
  80     if (n_carp_peers == 0)
  81         return;
  82
  83     carp_peers = (CachePeer **)xcalloc(n_carp_peers, sizeof(*carp_peers));
  84
  85     /* Build a list of the found peers and calculate hashes and load factors */
  86     for (P = carp_peers, p = Config.peers; p; p = p->next) {
  87         if (!p->options.carp)
  88             continue;
  89
  90         if (p->weight == 0)
  91             continue;
  92
  93         /* calculate this peers hash */
  94         p->carp.hash = 0;
  95
  96         for (t = p->name; *t != 0; ++t)
  97             p->carp.hash += ROTATE_LEFT(p->carp.hash, 19) + (unsigned int) *t;
  98
  99         p->carp.hash += p->carp.hash * 0x62531965;
 100
 101         p->carp.hash = ROTATE_LEFT(p->carp.hash, 21);
 102
 103         /* and load factor */
 104         p->carp.load_factor = ((double) p->weight) / (double) W;
 105
 106         if (floor(p->carp.load_factor * 1000.0) == 0.0)
 107             p->carp.load_factor = 0.0;
 108
 109         /* add it to our list of peers */
 110         *P = cbdataReference(p);
 111         ++P;
 112     }
 113
 114     /* Sort our list on weight */
 115     qsort(carp_peers, n_carp_peers, sizeof(*carp_peers), peerSortWeight);
 116
 117     /* Calculate the load factor multipliers X_k
 118      *
 119      * X_1 = pow ((K*p_1), (1/K))
 120      * X_k = ([K-k+1] * [P_k - P_{k-1}])/(X_1 * X_2 * ... * X_{k-1})
 121      * X_k += pow ((X_{k-1}, {K-k+1})
 122      * X_k = pow (X_k, {1/(K-k+1)})
 123      * simplified to have X_1 part of the loop
 124      */
 125     K = n_carp_peers;
 126
 127     P_last = 0.0;       /* Empty P_0 */
 128
 129     Xn = 1.0;           /* Empty starting point of X_1 * X_2 * ... * X_{x-1} */
 130
 131     X_last = 0.0;       /* Empty X_0, nullifies the first pow statement */
 132
 133     for (k = 1; k <= K; ++k) {
 134         double Kk1 = (double) (K - k + 1);
 135         p = carp_peers[k - 1];
 136         p->carp.load_multiplier = (Kk1 * (p->carp.load_factor - P_last)) / Xn;
 137         p->carp.load_multiplier += pow(X_last, Kk1);
 138         p->carp.load_multiplier = pow(p->carp.load_multiplier, 1.0 / Kk1);
 139         Xn *= p->carp.load_multiplier;
 140         X_last = p->carp.load_multiplier;
 141         P_last = p->carp.load_factor;
 142     }
 143 }
 144
 145 CachePeer *
 146 carpSelectParent(HttpRequest * request)
 147 {
 148     int k;
 149     CachePeer *p = NULL;
 150     CachePeer *tp;
 151     unsigned int user_hash = 0;
 152     unsigned int combined_hash;
 153     double score;
 154     double high_score = 0;
 155
 156     if (n_carp_peers == 0)
 157         return NULL;
 158
 159     /* calculate hash key */
 160     debugs(39, 2, "carpSelectParent: Calculating hash for " << request->effectiveRequestUri());
 161
 162     /* select CachePeer */
 163     for (k = 0; k < n_carp_peers; ++k) {
 164         SBuf key;
 165         tp = carp_peers[k];
 166         if (tp->options.carp_key.set) {
 167             // this code follows URI syntax pattern.
 168             // corner cases should use the full effective request URI
 169             if (tp->options.carp_key.scheme) {
 170                 key.append(request->url.getScheme().c_str());
 171                 if (key.length()) //if the scheme is not empty
 172                     key.append("://");
 173             }
 174             if (tp->options.carp_key.host) {
 175                 key.append(request->url.host());
 176             }
 177             if (tp->options.carp_key.port) {
 178                 key.appendf(":%u", request->url.port());
 179             }
 180             if (tp->options.carp_key.path) {
 181                 // XXX: fix when path and query are separate
 182                 key.append(request->url.path().substr(0,request->url.path().find('?'))); // 0..N
 183             }
 184             if (tp->options.carp_key.params) {
 185                 // XXX: fix when path and query are separate
 186                 SBuf::size_type pos;
 187                 if ((pos=request->url.path().find('?')) != SBuf::npos)
 188                     key.append(request->url.path().substr(pos)); // N..npos
 189             }
 190         }
 191         // if the url-based key is empty, e.g. because the user is
 192         // asking to balance on the path but the request doesn't supply any,
 193         // then fall back to the effective request URI
 194
 195         if (key.isEmpty())
 196             key=request->effectiveRequestUri();
 197
 198         for (const char *c = key.rawContent(), *e=key.rawContent()+key.length(); c < e; ++c)
 199             user_hash += ROTATE_LEFT(user_hash, 19) + *c;
 200         combined_hash = (user_hash ^ tp->carp.hash);
 201         combined_hash += combined_hash * 0x62531965;
 202         combined_hash = ROTATE_LEFT(combined_hash, 21);
 203         score = combined_hash * tp->carp.load_multiplier;
 204         debugs(39, 3, "carpSelectParent: key=" << key << " name=" << tp->name << " combined_hash=" << combined_hash  <<
 205                " score=" << std::setprecision(0) << score);
 206
 207         if ((score > high_score) && peerHTTPOkay(tp, request)) {
 208             p = tp;
 209             high_score = score;
 210         }
 211     }
 212
 213     if (p)
 214         debugs(39, 2, "carpSelectParent: selected " << p->name);
 215
 216     return p;
 217 }
 218
 219 static void
 220 carpCachemgr(StoreEntry * sentry)
 221 {
 222     CachePeer *p;
 223     int sumfetches = 0;
 224     storeAppendPrintf(sentry, "%24s %10s %10s %10s %10s\n",
 225                       "Hostname",
 226                       "Hash",
 227                       "Multiplier",
 228                       "Factor",
 229                       "Actual");
 230
 231     for (p = Config.peers; p; p = p->next)
 232         sumfetches += p->stats.fetches;
 233
 234     for (p = Config.peers; p; p = p->next) {
 235         storeAppendPrintf(sentry, "%24s %10x %10f %10f %10f\n",
 236                           p->name, p->carp.hash,
 237                           p->carp.load_multiplier,
 238                           p->carp.load_factor,
 239                           sumfetches ? (double) p->stats.fetches / sumfetches : -1.0);
 240     }
 241 }
 242