src/carp.cc

   1 /*
   2  * Copyright (C) 1996-2021 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 "PeerSelectState.h"
  17 #include "SquidConfig.h"
  18 #include "Store.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(PeerSelector *ps)
 147 {
 148     assert(ps);
 149     HttpRequest *request = ps->request;
 150
 151     int k;
 152     CachePeer *p = NULL;
 153     CachePeer *tp;
 154     unsigned int user_hash = 0;
 155     unsigned int combined_hash;
 156     double score;
 157     double high_score = 0;
 158
 159     if (n_carp_peers == 0)
 160         return NULL;
 161
 162     /* calculate hash key */
 163     debugs(39, 2, "carpSelectParent: Calculating hash for " << request->effectiveRequestUri());
 164
 165     /* select CachePeer */
 166     for (k = 0; k < n_carp_peers; ++k) {
 167         SBuf key;
 168         tp = carp_peers[k];
 169         if (tp->options.carp_key.set) {
 170             // this code follows URI syntax pattern.
 171             // corner cases should use the full effective request URI
 172             if (tp->options.carp_key.scheme) {
 173                 key.append(request->url.getScheme().image());
 174                 if (key.length()) //if the scheme is not empty
 175                     key.append("://");
 176             }
 177             if (tp->options.carp_key.host) {
 178                 key.append(request->url.host());
 179             }
 180             if (tp->options.carp_key.port) {
 181                 key.appendf(":%u", request->url.port());
 182             }
 183             if (tp->options.carp_key.path) {
 184                 // XXX: fix when path and query are separate
 185                 key.append(request->url.path().substr(0,request->url.path().find('?'))); // 0..N
 186             }
 187             if (tp->options.carp_key.params) {
 188                 // XXX: fix when path and query are separate
 189                 SBuf::size_type pos;
 190                 if ((pos=request->url.path().find('?')) != SBuf::npos)
 191                     key.append(request->url.path().substr(pos)); // N..npos
 192             }
 193         }
 194         // if the url-based key is empty, e.g. because the user is
 195         // asking to balance on the path but the request doesn't supply any,
 196         // then fall back to the effective request URI
 197
 198         if (key.isEmpty())
 199             key=request->effectiveRequestUri();
 200
 201         for (const char *c = key.rawContent(), *e=key.rawContent()+key.length(); c < e; ++c)
 202             user_hash += ROTATE_LEFT(user_hash, 19) + *c;
 203         combined_hash = (user_hash ^ tp->carp.hash);
 204         combined_hash += combined_hash * 0x62531965;
 205         combined_hash = ROTATE_LEFT(combined_hash, 21);
 206         score = combined_hash * tp->carp.load_multiplier;
 207         debugs(39, 3, "carpSelectParent: key=" << key << " name=" << tp->name << " combined_hash=" << combined_hash  <<
 208                " score=" << std::setprecision(0) << score);
 209
 210         if ((score > high_score) && peerHTTPOkay(tp, ps)) {
 211             p = tp;
 212             high_score = score;
 213         }
 214     }
 215
 216     if (p)
 217         debugs(39, 2, "carpSelectParent: selected " << p->name);
 218
 219     return p;
 220 }
 221
 222 static void
 223 carpCachemgr(StoreEntry * sentry)
 224 {
 225     CachePeer *p;
 226     int sumfetches = 0;
 227     storeAppendPrintf(sentry, "%24s %10s %10s %10s %10s\n",
 228                       "Hostname",
 229                       "Hash",
 230                       "Multiplier",
 231                       "Factor",
 232                       "Actual");
 233
 234     for (p = Config.peers; p; p = p->next)
 235         sumfetches += p->stats.fetches;
 236
 237     for (p = Config.peers; p; p = p->next) {
 238         storeAppendPrintf(sentry, "%24s %10x %10f %10f %10f\n",
 239                           p->name, p->carp.hash,
 240                           p->carp.load_multiplier,
 241                           p->carp.load_factor,
 242                           sumfetches ? (double) p->stats.fetches / sumfetches : -1.0);
 243     }
 244 }
 245