peer_sourcehash.cc
Go to the documentation of this file.
1 /*
2  * Copyright (C) 1996-2018 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 source hash based selection */
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_sourcehash_peers = 0;
25 static CachePeer **sourcehash_peers = NULL;
28 
29 static int
30 peerSortWeight(const void *a, const void *b)
31 {
32  const CachePeer *const *p1 = (const CachePeer *const *)a;
33  const CachePeer *const *p2 = (const CachePeer *const *)b;
34  return (*p1)->weight - (*p2)->weight;
35 }
36 
37 void
39 {
40  int W = 0;
41  int K;
42  int k;
43  double P_last, X_last, Xn;
44  CachePeer *p;
45  CachePeer **P;
46  char *t;
47  /* Clean up */
48 
49  for (k = 0; k < n_sourcehash_peers; ++k) {
50  cbdataReferenceDone(sourcehash_peers[k]);
51  }
52 
53  safe_free(sourcehash_peers);
54  n_sourcehash_peers = 0;
55  /* find out which peers we have */
56 
57  for (p = Config.peers; p; p = p->next) {
58  if (!p->options.sourcehash)
59  continue;
60 
61  assert(p->type == PEER_PARENT);
62 
63  if (p->weight == 0)
64  continue;
65 
67 
68  W += p->weight;
69  }
70 
72 
73  if (n_sourcehash_peers == 0)
74  return;
75 
76  sourcehash_peers = (CachePeer **)xcalloc(n_sourcehash_peers, sizeof(*sourcehash_peers));
77 
78  /* Build a list of the found peers and calculate hashes and load factors */
79  for (P = sourcehash_peers, p = Config.peers; p; p = p->next) {
80  if (!p->options.sourcehash)
81  continue;
82 
83  if (p->weight == 0)
84  continue;
85 
86  /* calculate this peers hash */
87  p->sourcehash.hash = 0;
88 
89  for (t = p->name; *t != 0; ++t)
90  p->sourcehash.hash += ROTATE_LEFT(p->sourcehash.hash, 19) + (unsigned int) *t;
91 
92  p->sourcehash.hash += p->sourcehash.hash * 0x62531965;
93 
94  p->sourcehash.hash = ROTATE_LEFT(p->sourcehash.hash, 21);
95 
96  /* and load factor */
97  p->sourcehash.load_factor = ((double) p->weight) / (double) W;
98 
99  if (floor(p->sourcehash.load_factor * 1000.0) == 0.0)
100  p->sourcehash.load_factor = 0.0;
101 
102  /* add it to our list of peers */
103  *P++ = cbdataReference(p);
104  }
105 
106  /* Sort our list on weight */
107  qsort(sourcehash_peers, n_sourcehash_peers, sizeof(*sourcehash_peers), peerSortWeight);
108 
109  /* Calculate the load factor multipliers X_k
110  *
111  * X_1 = pow ((K*p_1), (1/K))
112  * X_k = ([K-k+1] * [P_k - P_{k-1}])/(X_1 * X_2 * ... * X_{k-1})
113  * X_k += pow ((X_{k-1}, {K-k+1})
114  * X_k = pow (X_k, {1/(K-k+1)})
115  * simplified to have X_1 part of the loop
116  */
117  K = n_sourcehash_peers;
118 
119  P_last = 0.0; /* Empty P_0 */
120 
121  Xn = 1.0; /* Empty starting point of X_1 * X_2 * ... * X_{x-1} */
122 
123  X_last = 0.0; /* Empty X_0, nullifies the first pow statement */
124 
125  for (k = 1; k <= K; ++k) {
126  double Kk1 = (double) (K - k + 1);
127  p = sourcehash_peers[k - 1];
128  p->sourcehash.load_multiplier = (Kk1 * (p->sourcehash.load_factor - P_last)) / Xn;
129  p->sourcehash.load_multiplier += pow(X_last, Kk1);
130  p->sourcehash.load_multiplier = pow(p->sourcehash.load_multiplier, 1.0 / Kk1);
131  Xn *= p->sourcehash.load_multiplier;
132  X_last = p->sourcehash.load_multiplier;
133  P_last = p->sourcehash.load_factor;
134  }
135 }
136 
137 static void
139 {
140  Mgr::RegisterAction("sourcehash", "peer sourcehash information",
141  peerSourceHashCachemgr, 0, 1);
142 }
143 
144 CachePeer *
146 {
147  int k;
148  const char *c;
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  const char *key = NULL;
156  char ntoabuf[MAX_IPSTRLEN];
157 
158  if (n_sourcehash_peers == 0)
159  return NULL;
160 
161  assert(ps);
162  HttpRequest *request = ps->request;
163 
164  key = request->client_addr.toStr(ntoabuf, sizeof(ntoabuf));
165 
166  /* calculate hash key */
167  debugs(39, 2, "peerSourceHashSelectParent: Calculating hash for " << key);
168 
169  for (c = key; *c != 0; ++c)
170  user_hash += ROTATE_LEFT(user_hash, 19) + *c;
171 
172  /* select CachePeer */
173  for (k = 0; k < n_sourcehash_peers; ++k) {
174  tp = sourcehash_peers[k];
175  combined_hash = (user_hash ^ tp->sourcehash.hash);
176  combined_hash += combined_hash * 0x62531965;
177  combined_hash = ROTATE_LEFT(combined_hash, 21);
178  score = combined_hash * tp->sourcehash.load_multiplier;
179  debugs(39, 3, "peerSourceHashSelectParent: " << tp->name << " combined_hash " << combined_hash <<
180  " score " << std::setprecision(0) << score);
181 
182  if ((score > high_score) && peerHTTPOkay(tp, ps)) {
183  p = tp;
184  high_score = score;
185  }
186  }
187 
188  if (p)
189  debugs(39, 2, "peerSourceHashSelectParent: selected " << p->name);
190 
191  return p;
192 }
193 
194 static void
196 {
197  CachePeer *p;
198  int sumfetches = 0;
199  storeAppendPrintf(sentry, "%24s %10s %10s %10s %10s\n",
200  "Hostname",
201  "Hash",
202  "Multiplier",
203  "Factor",
204  "Actual");
205 
206  for (p = Config.peers; p; p = p->next)
207  sumfetches += p->stats.fetches;
208 
209  for (p = Config.peers; p; p = p->next) {
210  storeAppendPrintf(sentry, "%24s %10x %10f %10f %10f\n",
211  p->name, p->sourcehash.hash,
212  p->sourcehash.load_multiplier,
213  p->sourcehash.load_factor,
214  sumfetches ? (double) p->stats.fetches / sumfetches : -1.0);
215  }
216 }
217 
HttpRequest * request
#define assert(EX)
Definition: assert.h:17
#define cbdataReferenceDone(var)
Definition: cbdata.h:350
CachePeer * next
Definition: CachePeer.h:154
#define xcalloc
Definition: membanger.c:57
CachePeer * peers
Definition: SquidConfig.h:243
struct _request * request(char *urlin)
Definition: tcp-banger2.c:291
struct CachePeer::@29 stats
#define safe_free(x)
Definition: xalloc.h:73
char * name
Definition: CachePeer.h:40
char * p
Definition: membanger.c:43
void OBJH(StoreEntry *)
Definition: forward.h:44
static OBJH peerSourceHashCachemgr
bool sourcehash
Definition: CachePeer.h:117
#define ROTATE_LEFT(x, n)
static int peerSortWeight(const void *a, const void *b)
#define debugs(SECTION, LEVEL, CONTENT)
Definition: Debug.h:124
#define cbdataReference(var)
Definition: cbdata.h:341
void RegisterAction(char const *action, char const *desc, OBJH *handler, int pw_req_flag, int atomic)
Definition: Registration.cc:16
Ip::Address client_addr
Definition: HttpRequest.h:137
peer_t type
Definition: CachePeer.h:42
int fetches
Definition: CachePeer.h:49
void peerSourceHashInit(void)
CachePeer * peerSourceHashSelectParent(PeerSelector *ps)
bool SIGHDLR int STUB void int
Definition: stub_tools.cc:68
int peerHTTPOkay(const CachePeer *p, PeerSelector *ps)
Definition: neighbors.cc:253
int weight
Definition: CachePeer.h:126
struct CachePeer::@31 options
int a
Definition: membanger.c:50
#define MAX_IPSTRLEN
Length of buffer that needs to be allocated to old a null-terminated IP-string.
Definition: forward.h:23
char * toStr(char *buf, const unsigned int blen, int force=AF_UNSPEC) const
Definition: Address.cc:795
static void peerSourceHashRegisterWithCacheManager(void)
void storeAppendPrintf(StoreEntry *e, const char *fmt,...)
Definition: store.cc:889
static int n_sourcehash_peers
class SquidConfig Config
Definition: SquidConfig.cc:12
#define NULL
Definition: types.h:166

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors