src/peer_userhash.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    Peer user hash based selection */
  10
  11 #include "squid.h"
  12
  13 #if USE_AUTH
  14
  15 #include "auth/UserRequest.h"
  16 #include "CachePeer.h"
  17 #include "globals.h"
  18 #include "HttpRequest.h"
  19 #include "mgr/Registration.h"
  20 #include "neighbors.h"
  21 #include "PeerSelectState.h"
  22 #include "SquidConfig.h"
  23 #include "Store.h"
  24
  25 #include <cmath>
  26
  27 #define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))
  28
  29 static int n_userhash_peers = 0;
  30 static CachePeer **userhash_peers = NULL;
  31 static OBJH peerUserHashCachemgr;
  32 static void peerUserHashRegisterWithCacheManager(void);
  33
  34 static int
  35 peerSortWeight(const void *a, const void *b)
  36 {
  37     const CachePeer *const *p1 = (const CachePeer *const *)a;
  38     const CachePeer *const *p2 = (const CachePeer *const *)b;
  39     return (*p1)->weight - (*p2)->weight;
  40 }
  41
  42 void
  43 peerUserHashInit(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_userhash_peers; ++k) {
  55         cbdataReferenceDone(userhash_peers[k]);
  56     }
  57
  58     safe_free(userhash_peers);
  59     n_userhash_peers = 0;
  60     /* find out which peers we have */
  61
  62     peerUserHashRegisterWithCacheManager();
  63
  64     for (p = Config.peers; p; p = p->next) {
  65         if (!p->options.userhash)
  66             continue;
  67
  68         assert(p->type == PEER_PARENT);
  69
  70         if (p->weight == 0)
  71             continue;
  72
  73         ++n_userhash_peers;
  74
  75         W += p->weight;
  76     }
  77
  78     if (n_userhash_peers == 0)
  79         return;
  80
  81     userhash_peers = (CachePeer **)xcalloc(n_userhash_peers, sizeof(*userhash_peers));
  82
  83     /* Build a list of the found peers and calculate hashes and load factors */
  84     for (P = userhash_peers, p = Config.peers; p; p = p->next) {
  85         if (!p->options.userhash)
  86             continue;
  87
  88         if (p->weight == 0)
  89             continue;
  90
  91         /* calculate this peers hash */
  92         p->userhash.hash = 0;
  93
  94         for (t = p->name; *t != 0; ++t)
  95             p->userhash.hash += ROTATE_LEFT(p->userhash.hash, 19) + (unsigned int) *t;
  96
  97         p->userhash.hash += p->userhash.hash * 0x62531965;
  98
  99         p->userhash.hash = ROTATE_LEFT(p->userhash.hash, 21);
 100
 101         /* and load factor */
 102         p->userhash.load_factor = ((double) p->weight) / (double) W;
 103
 104         if (floor(p->userhash.load_factor * 1000.0) == 0.0)
 105             p->userhash.load_factor = 0.0;
 106
 107         /* add it to our list of peers */
 108         *P++ = cbdataReference(p);
 109     }
 110
 111     /* Sort our list on weight */
 112     qsort(userhash_peers, n_userhash_peers, sizeof(*userhash_peers), peerSortWeight);
 113
 114     /* Calculate the load factor multipliers X_k
 115      *
 116      * X_1 = pow ((K*p_1), (1/K))
 117      * X_k = ([K-k+1] * [P_k - P_{k-1}])/(X_1 * X_2 * ... * X_{k-1})
 118      * X_k += pow ((X_{k-1}, {K-k+1})
 119      * X_k = pow (X_k, {1/(K-k+1)})
 120      * simplified to have X_1 part of the loop
 121      */
 122     K = n_userhash_peers;
 123
 124     P_last = 0.0;       /* Empty P_0 */
 125
 126     Xn = 1.0;           /* Empty starting point of X_1 * X_2 * ... * X_{x-1} */
 127
 128     X_last = 0.0;       /* Empty X_0, nullifies the first pow statement */
 129
 130     for (k = 1; k <= K; ++k) {
 131         double Kk1 = (double) (K - k + 1);
 132         p = userhash_peers[k - 1];
 133         p->userhash.load_multiplier = (Kk1 * (p->userhash.load_factor - P_last)) / Xn;
 134         p->userhash.load_multiplier += pow(X_last, Kk1);
 135         p->userhash.load_multiplier = pow(p->userhash.load_multiplier, 1.0 / Kk1);
 136         Xn *= p->userhash.load_multiplier;
 137         X_last = p->userhash.load_multiplier;
 138         P_last = p->userhash.load_factor;
 139     }
 140 }
 141
 142 static void
 143 peerUserHashRegisterWithCacheManager(void)
 144 {
 145     Mgr::RegisterAction("userhash", "peer userhash information", peerUserHashCachemgr,
 146                         0, 1);
 147 }
 148
 149 CachePeer *
 150 peerUserHashSelectParent(PeerSelector *ps)
 151 {
 152     int k;
 153     const char *c;
 154     CachePeer *p = NULL;
 155     CachePeer *tp;
 156     unsigned int user_hash = 0;
 157     unsigned int combined_hash;
 158     double score;
 159     double high_score = 0;
 160     const char *key = NULL;
 161
 162     if (n_userhash_peers == 0)
 163         return NULL;
 164
 165     assert(ps);
 166     HttpRequest *request = ps->request;
 167
 168     if (request->auth_user_request != NULL)
 169         key = request->auth_user_request->username();
 170
 171     if (!key)
 172         return NULL;
 173
 174     /* calculate hash key */
 175     debugs(39, 2, "peerUserHashSelectParent: Calculating hash for " << key);
 176
 177     for (c = key; *c != 0; ++c)
 178         user_hash += ROTATE_LEFT(user_hash, 19) + *c;
 179
 180     /* select CachePeer */
 181     for (k = 0; k < n_userhash_peers; ++k) {
 182         tp = userhash_peers[k];
 183         combined_hash = (user_hash ^ tp->userhash.hash);
 184         combined_hash += combined_hash * 0x62531965;
 185         combined_hash = ROTATE_LEFT(combined_hash, 21);
 186         score = combined_hash * tp->userhash.load_multiplier;
 187         debugs(39, 3, "peerUserHashSelectParent: " << tp->name << " combined_hash " << combined_hash  <<
 188                " score " << std::setprecision(0) << score);
 189
 190         if ((score > high_score) && peerHTTPOkay(tp, ps)) {
 191             p = tp;
 192             high_score = score;
 193         }
 194     }
 195
 196     if (p)
 197         debugs(39, 2, "peerUserHashSelectParent: selected " << p->name);
 198
 199     return p;
 200 }
 201
 202 static void
 203 peerUserHashCachemgr(StoreEntry * sentry)
 204 {
 205     CachePeer *p;
 206     int sumfetches = 0;
 207     storeAppendPrintf(sentry, "%24s %10s %10s %10s %10s\n",
 208                       "Hostname",
 209                       "Hash",
 210                       "Multiplier",
 211                       "Factor",
 212                       "Actual");
 213
 214     for (p = Config.peers; p; p = p->next)
 215         sumfetches += p->stats.fetches;
 216
 217     for (p = Config.peers; p; p = p->next) {
 218         storeAppendPrintf(sentry, "%24s %10x %10f %10f %10f\n",
 219                           p->name, p->userhash.hash,
 220                           p->userhash.load_multiplier,
 221                           p->userhash.load_factor,
 222                           sumfetches ? (double) p->stats.fetches / sumfetches : -1.0);
 223     }
 224 }
 225
 226 #endif /* USE_AUTH */
 227