carp.cc
Go to the documentation of this file.
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 "carp.h"
14 #include "HttpRequest.h"
15 #include "mgr/Registration.h"
16 #include "neighbors.h"
17 #include "PeerSelectState.h"
18 #include "SquidConfig.h"
19 #include "Store.h"
20 
21 #include <cmath>
22 
23 #define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))
24 
25 static int n_carp_peers = 0;
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 static void
39 {
40  Mgr::RegisterAction("carp", "CARP information", carpCachemgr, 0, 1);
41 }
42 
43 void
44 carpInit(void)
45 {
46  int W = 0;
47  int K;
48  int k;
49  double P_last, X_last, Xn;
50  CachePeer *p;
51  CachePeer **P;
52  char *t;
53  /* Clean up */
54 
55  for (k = 0; k < n_carp_peers; ++k) {
57  }
58 
60  n_carp_peers = 0;
61 
62  /* initialize cache manager before we have a chance to leave the execution path */
64 
65  /* find out which peers we have */
66 
67  for (p = Config.peers; p; p = p->next) {
68  if (!p->options.carp)
69  continue;
70 
71  assert(p->type == PEER_PARENT);
72 
73  if (p->weight == 0)
74  continue;
75 
76  ++n_carp_peers;
77 
78  W += p->weight;
79  }
80 
81  if (n_carp_peers == 0)
82  return;
83 
85 
86  /* Build a list of the found peers and calculate hashes and load factors */
87  for (P = carp_peers, p = Config.peers; p; p = p->next) {
88  if (!p->options.carp)
89  continue;
90 
91  if (p->weight == 0)
92  continue;
93 
94  /* calculate this peers hash */
95  p->carp.hash = 0;
96 
97  for (t = p->name; *t != 0; ++t)
98  p->carp.hash += ROTATE_LEFT(p->carp.hash, 19) + (unsigned int) *t;
99 
100  p->carp.hash += p->carp.hash * 0x62531965;
101 
102  p->carp.hash = ROTATE_LEFT(p->carp.hash, 21);
103 
104  /* and load factor */
105  p->carp.load_factor = ((double) p->weight) / (double) W;
106 
107  if (floor(p->carp.load_factor * 1000.0) == 0.0)
108  p->carp.load_factor = 0.0;
109 
110  /* add it to our list of peers */
111  *P = cbdataReference(p);
112  ++P;
113  }
114 
115  /* Sort our list on weight */
117 
118  /* Calculate the load factor multipliers X_k
119  *
120  * X_1 = pow ((K*p_1), (1/K))
121  * X_k = ([K-k+1] * [P_k - P_{k-1}])/(X_1 * X_2 * ... * X_{k-1})
122  * X_k += pow ((X_{k-1}, {K-k+1})
123  * X_k = pow (X_k, {1/(K-k+1)})
124  * simplified to have X_1 part of the loop
125  */
126  K = n_carp_peers;
127 
128  P_last = 0.0; /* Empty P_0 */
129 
130  Xn = 1.0; /* Empty starting point of X_1 * X_2 * ... * X_{x-1} */
131 
132  X_last = 0.0; /* Empty X_0, nullifies the first pow statement */
133 
134  for (k = 1; k <= K; ++k) {
135  double Kk1 = (double) (K - k + 1);
136  p = carp_peers[k - 1];
137  p->carp.load_multiplier = (Kk1 * (p->carp.load_factor - P_last)) / Xn;
138  p->carp.load_multiplier += pow(X_last, Kk1);
139  p->carp.load_multiplier = pow(p->carp.load_multiplier, 1.0 / Kk1);
140  Xn *= p->carp.load_multiplier;
141  X_last = p->carp.load_multiplier;
142  P_last = p->carp.load_factor;
143  }
144 }
145 
146 CachePeer *
148 {
149  assert(ps);
150  HttpRequest *request = ps->request;
151 
152  int k;
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 
160  if (n_carp_peers == 0)
161  return NULL;
162 
163  /* calculate hash key */
164  debugs(39, 2, "carpSelectParent: Calculating hash for " << request->effectiveRequestUri());
165 
166  /* select CachePeer */
167  for (k = 0; k < n_carp_peers; ++k) {
168  SBuf key;
169  tp = carp_peers[k];
170  if (tp->options.carp_key.set) {
171  // this code follows URI syntax pattern.
172  // corner cases should use the full effective request URI
173  if (tp->options.carp_key.scheme) {
174  key.append(request->url.getScheme().image());
175  if (key.length()) //if the scheme is not empty
176  key.append("://");
177  }
178  if (tp->options.carp_key.host) {
179  key.append(request->url.host());
180  }
181  if (tp->options.carp_key.port) {
182  key.appendf(":%u", request->url.port());
183  }
184  if (tp->options.carp_key.path) {
185  // XXX: fix when path and query are separate
186  key.append(request->url.path().substr(0,request->url.path().find('?'))); // 0..N
187  }
188  if (tp->options.carp_key.params) {
189  // XXX: fix when path and query are separate
190  SBuf::size_type pos;
191  if ((pos=request->url.path().find('?')) != SBuf::npos)
192  key.append(request->url.path().substr(pos)); // N..npos
193  }
194  }
195  // if the url-based key is empty, e.g. because the user is
196  // asking to balance on the path but the request doesn't supply any,
197  // then fall back to the effective request URI
198 
199  if (key.isEmpty())
200  key=request->effectiveRequestUri();
201 
202  for (const char *c = key.rawContent(), *e=key.rawContent()+key.length(); c < e; ++c)
203  user_hash += ROTATE_LEFT(user_hash, 19) + *c;
204  combined_hash = (user_hash ^ tp->carp.hash);
205  combined_hash += combined_hash * 0x62531965;
206  combined_hash = ROTATE_LEFT(combined_hash, 21);
207  score = combined_hash * tp->carp.load_multiplier;
208  debugs(39, 3, "carpSelectParent: key=" << key << " name=" << tp->name << " combined_hash=" << combined_hash <<
209  " score=" << std::setprecision(0) << score);
210 
211  if ((score > high_score) && peerHTTPOkay(tp, ps)) {
212  p = tp;
213  high_score = score;
214  }
215  }
216 
217  if (p)
218  debugs(39, 2, "carpSelectParent: selected " << p->name);
219 
220  return p;
221 }
222 
223 static void
225 {
226  CachePeer *p;
227  int sumfetches = 0;
228  storeAppendPrintf(sentry, "%24s %10s %10s %10s %10s\n",
229  "Hostname",
230  "Hash",
231  "Multiplier",
232  "Factor",
233  "Actual");
234 
235  for (p = Config.peers; p; p = p->next)
236  sumfetches += p->stats.fetches;
237 
238  for (p = Config.peers; p; p = p->next) {
239  storeAppendPrintf(sentry, "%24s %10x %10f %10f %10f\n",
240  p->name, p->carp.hash,
241  p->carp.load_multiplier,
242  p->carp.load_factor,
243  sumfetches ? (double) p->stats.fetches / sumfetches : -1.0);
244  }
245 }
246 
static CachePeer ** carp_peers
Definition: carp.cc:26
void * xcalloc(size_t n, size_t sz)
Definition: xalloc.cc:72
int fetches
Definition: CachePeer.h:48
HttpRequest * request
peer_t type
Definition: CachePeer.h:41
bool isEmpty() const
Definition: SBuf.h:424
struct CachePeer::@30 options
void storeAppendPrintf(StoreEntry *e, const char *fmt,...)
Definition: store.cc:872
Definition: SBuf.h:87
#define cbdataReference(var)
Definition: cbdata.h:341
char * name
Definition: CachePeer.h:39
int weight
Definition: CachePeer.h:125
static int peerSortWeight(const void *a, const void *b)
Definition: carp.cc:30
void OBJH(StoreEntry *)
Definition: forward.h:44
#define NULL
Definition: types.h:166
const char * rawContent() const
Definition: SBuf.cc:509
#define debugs(SECTION, LEVEL, CONTENT)
Definition: Debug.h:123
@ PEER_PARENT
Definition: enums.h:30
MemBlob::size_type size_type
Definition: SBuf.h:89
#define ROTATE_LEFT(x, n)
Definition: carp.cc:23
struct CachePeer::@28 stats
struct CachePeer::@30::@36 carp_key
static void carpRegisterWithCacheManager(void)
Definition: carp.cc:38
#define safe_free(x)
Definition: xalloc.h:73
#define assert(EX)
Definition: assert.h:19
static OBJH carpCachemgr
Definition: carp.cc:27
void EVH void double
Definition: stub_event.cc:16
#define cbdataReferenceDone(var)
Definition: cbdata.h:350
size_type length() const
Returns the number of bytes stored in SBuf.
Definition: SBuf.h:408
SBuf & append(const SBuf &S)
Definition: SBuf.cc:185
static const size_type npos
Definition: SBuf.h:92
bool carp
Definition: CachePeer.h:104
char * url
Definition: tcp-banger2.c:114
CachePeer * peers
Definition: SquidConfig.h:252
SBuf & appendf(const char *fmt,...)
Definition: SBuf.cc:229
CachePeer * next
Definition: CachePeer.h:153
int peerHTTPOkay(const CachePeer *p, PeerSelector *ps)
Definition: neighbors.cc:259
CachePeer * carpSelectParent(PeerSelector *ps)
Definition: carp.cc:147
static int n_carp_peers
Definition: carp.cc:25
void RegisterAction(char const *action, char const *desc, OBJH *handler, int pw_req_flag, int atomic)
Definition: Registration.cc:16
struct _request * request(char *urlin)
Definition: tcp-banger2.c:291
void carpInit(void)
Definition: carp.cc:44
class SquidConfig Config
Definition: SquidConfig.cc:12
int unsigned int
Definition: stub_fd.cc:19

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors