src/peer_userhash.cc

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