src/carp.cc

   1 /*
   2  * Copyright (C) 1996-2025 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 "base/RunnersRegistry.h"
  13 #include "CachePeer.h"
  14 #include "CachePeers.h"
  15 #include "carp.h"
  16 #include "HttpRequest.h"
  17 #include "mgr/Registration.h"
  18 #include "neighbors.h"
  19 #include "PeerSelectState.h"
  20 #include "SquidConfig.h"
  21 #include "Store.h"
  22
  23 #include <cmath>
  24
  25 #define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))
  26
  27 /// CARP cache_peers ordered by their CARP weight
  28 static auto &
  29 CarpPeers()
  30 {
  31     static const auto carpPeers = new SelectedCachePeers();
  32     return *carpPeers;
  33 }
  34
  35 static OBJH carpCachemgr;
  36
  37 static int
  38 peerSortWeight(const void *a, const void *b)
  39 {
  40     const CachePeer *const *p1 = (const CachePeer *const *)a;
  41     const CachePeer *const *p2 = (const CachePeer *const *)b;
  42     return (*p1)->weight - (*p2)->weight;
  43 }
  44
  45 static void
  46 carpRegisterWithCacheManager(void)
  47 {
  48     Mgr::RegisterAction("carp", "CARP information", carpCachemgr, 0, 1);
  49 }
  50
  51 static void
  52 carpInit(void)
  53 {
  54     int W = 0;
  55     double P_last, X_last, Xn;
  56     char *t;
  57     /* Clean up */
  58
  59     CarpPeers().clear();
  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     RawCachePeers rawCarpPeers;
  67     for (const auto &peer: CurrentCachePeers()) {
  68         const auto p = peer.get();
  69
  70         if (!p->options.carp)
  71             continue;
  72
  73         assert(p->type == PEER_PARENT);
  74
  75         if (p->weight == 0)
  76             continue;
  77
  78         rawCarpPeers.push_back(p);
  79
  80         W += p->weight;
  81     }
  82
  83     if (rawCarpPeers.empty())
  84         return;
  85
  86     /* calculate hashes and load factors */
  87     for (const auto p: rawCarpPeers) {
  88         /* calculate this peers hash */
  89         p->carp.hash = 0;
  90
  91         for (t = p->name; *t != 0; ++t)
  92             p->carp.hash += ROTATE_LEFT(p->carp.hash, 19) + (unsigned int) *t;
  93
  94         p->carp.hash += p->carp.hash * 0x62531965;
  95
  96         p->carp.hash = ROTATE_LEFT(p->carp.hash, 21);
  97
  98         /* and load factor */
  99         p->carp.load_factor = ((double) p->weight) / (double) W;
 100
 101         if (floor(p->carp.load_factor * 1000.0) == 0.0)
 102             p->carp.load_factor = 0.0;
 103     }
 104
 105     /* Sort our list on weight */
 106     qsort(rawCarpPeers.data(), rawCarpPeers.size(), sizeof(decltype(rawCarpPeers)::value_type), peerSortWeight);
 107
 108     /* Calculate the load factor multipliers X_k
 109      *
 110      * X_1 = pow ((K*p_1), (1/K))
 111      * X_k = ([K-k+1] * [P_k - P_{k-1}])/(X_1 * X_2 * ... * X_{k-1})
 112      * X_k += pow ((X_{k-1}, {K-k+1})
 113      * X_k = pow (X_k, {1/(K-k+1)})
 114      * simplified to have X_1 part of the loop
 115      */
 116     const auto K = rawCarpPeers.size();
 117
 118     P_last = 0.0;       /* Empty P_0 */
 119
 120     Xn = 1.0;           /* Empty starting point of X_1 * X_2 * ... * X_{x-1} */
 121
 122     X_last = 0.0;       /* Empty X_0, nullifies the first pow statement */
 123
 124     for (size_t k = 1; k <= K; ++k) {
 125         double Kk1 = (double) (K - k + 1);
 126         const auto p = rawCarpPeers[k - 1];
 127         p->carp.load_multiplier = (Kk1 * (p->carp.load_factor - P_last)) / Xn;
 128         p->carp.load_multiplier += pow(X_last, Kk1);
 129         p->carp.load_multiplier = pow(p->carp.load_multiplier, 1.0 / Kk1);
 130         Xn *= p->carp.load_multiplier;
 131         X_last = p->carp.load_multiplier;
 132         P_last = p->carp.load_factor;
 133     }
 134
 135     CarpPeers().assign(rawCarpPeers.begin(), rawCarpPeers.end());
 136 }
 137
 138 /// reacts to RegisteredRunner events relevant to this module
 139 class CarpRr: public RegisteredRunner
 140 {
 141 public:
 142     /* RegisteredRunner API */
 143     void useConfig() override { carpInit(); }
 144     void syncConfig() override { carpInit(); }
 145 };
 146
 147 DefineRunnerRegistrator(CarpRr);
 148
 149 CachePeer *
 150 carpSelectParent(PeerSelector *ps)
 151 {
 152     assert(ps);
 153     HttpRequest *request = ps->request;
 154
 155     CachePeer *p = nullptr;
 156     unsigned int user_hash = 0;
 157     unsigned int combined_hash;
 158     double score;
 159     double high_score = 0;
 160
 161     if (CarpPeers().empty())
 162         return nullptr;
 163
 164     /* calculate hash key */
 165     debugs(39, 2, "carpSelectParent: Calculating hash for " << request->effectiveRequestUri());
 166
 167     /* select CachePeer */
 168     for (const auto &tp: CarpPeers()) {
 169         if (!tp)
 170             continue; // peer gone
 171
 172         SBuf key;
 173         if (tp->options.carp_key.set) {
 174             // this code follows URI syntax pattern.
 175             // corner cases should use the full effective request URI
 176             if (tp->options.carp_key.scheme) {
 177                 key.append(request->url.getScheme().image());
 178                 if (key.length()) //if the scheme is not empty
 179                     key.append("://");
 180             }
 181             if (tp->options.carp_key.host) {
 182                 key.append(request->url.host());
 183             }
 184             if (tp->options.carp_key.port) {
 185                 key.appendf(":%hu", request->url.port().value_or(0));
 186             }
 187             if (tp->options.carp_key.path) {
 188                 // XXX: fix when path and query are separate
 189                 key.append(request->url.path().substr(0,request->url.path().find('?'))); // 0..N
 190             }
 191             if (tp->options.carp_key.params) {
 192                 // XXX: fix when path and query are separate
 193                 SBuf::size_type pos;
 194                 if ((pos=request->url.path().find('?')) != SBuf::npos)
 195                     key.append(request->url.path().substr(pos)); // N..npos
 196             }
 197         }
 198         // if the url-based key is empty, e.g. because the user is
 199         // asking to balance on the path but the request doesn't supply any,
 200         // then fall back to the effective request URI
 201
 202         if (key.isEmpty())
 203             key=request->effectiveRequestUri();
 204
 205         for (const char *c = key.rawContent(), *e=key.rawContent()+key.length(); c < e; ++c)
 206             user_hash += ROTATE_LEFT(user_hash, 19) + *c;
 207         combined_hash = (user_hash ^ tp->carp.hash);
 208         combined_hash += combined_hash * 0x62531965;
 209         combined_hash = ROTATE_LEFT(combined_hash, 21);
 210         score = combined_hash * tp->carp.load_multiplier;
 211         debugs(39, 3, *tp << " key=" << key << " combined_hash=" << combined_hash  <<
 212                " score=" << std::setprecision(0) << score);
 213
 214         if ((score > high_score) && peerHTTPOkay(tp.get(), ps)) {
 215             p = tp.get();
 216             high_score = score;
 217         }
 218     }
 219
 220     if (p)
 221         debugs(39, 2, "selected " << *p);
 222
 223     return p;
 224 }
 225
 226 static void
 227 carpCachemgr(StoreEntry * sentry)
 228 {
 229     int sumfetches = 0;
 230     storeAppendPrintf(sentry, "%24s %10s %10s %10s %10s\n",
 231                       "Hostname",
 232                       "Hash",
 233                       "Multiplier",
 234                       "Factor",
 235                       "Actual");
 236
 237     for (const auto &p: CarpPeers()) {
 238         if (!p)
 239             continue;
 240         sumfetches += p->stats.fetches;
 241     }
 242
 243     for (const auto &p: CarpPeers()) {
 244         if (!p)
 245             continue;
 246         storeAppendPrintf(sentry, "%24s %10x %10f %10f %10f\n",
 247                           p->name, p->carp.hash,
 248                           p->carp.load_multiplier,
 249                           p->carp.load_factor,
 250                           sumfetches ? (double) p->stats.fetches / sumfetches : -1.0);
 251     }
 252 }
 253