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

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors