carp.cc
Go to the documentation of this file.
1/*
2 * Copyright (C) 1996-2022 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
25static int n_carp_peers = 0;
26static CachePeer **carp_peers = nullptr;
28
29static int
30peerSortWeight(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
37static void
39{
40 Mgr::RegisterAction("carp", "CARP information", carpCachemgr, 0, 1);
41}
42
43void
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
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
146CachePeer *
148{
149 assert(ps);
151
152 int k;
153 CachePeer *p = nullptr;
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 nullptr;
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
223static 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
class SquidConfig Config
Definition: SquidConfig.cc:12
#define assert(EX)
Definition: assert.h:19
static void carpRegisterWithCacheManager(void)
Definition: carp.cc:38
CachePeer * carpSelectParent(PeerSelector *ps)
Definition: carp.cc:147
static int n_carp_peers
Definition: carp.cc:25
static OBJH carpCachemgr
Definition: carp.cc:27
#define ROTATE_LEFT(x, n)
Definition: carp.cc:23
void carpInit(void)
Definition: carp.cc:44
static int peerSortWeight(const void *a, const void *b)
Definition: carp.cc:30
static CachePeer ** carp_peers
Definition: carp.cc:26
#define cbdataReferenceDone(var)
Definition: cbdata.h:350
#define cbdataReference(var)
Definition: cbdata.h:341
int weight
Definition: CachePeer.h:125
struct CachePeer::@33::@39 carp_key
struct CachePeer::@33 options
peer_t type
Definition: CachePeer.h:41
bool scheme
Definition: CachePeer.h:107
char * host
Definition: CachePeer.h:40
unsigned short port
Definition: CachePeer.h:73
CachePeer * next
Definition: CachePeer.h:153
struct CachePeer::@31 stats
bool params
Definition: CachePeer.h:111
char * name
Definition: CachePeer.h:39
bool carp
Definition: CachePeer.h:104
int fetches
Definition: CachePeer.h:48
bool path
Definition: CachePeer.h:110
bool set
Definition: CachePeer.h:106
HttpRequest * request
Definition: SBuf.h:94
const char * rawContent() const
Definition: SBuf.cc:509
static const size_type npos
Definition: SBuf.h:99
size_type length() const
Returns the number of bytes stored in SBuf.
Definition: SBuf.h:415
bool isEmpty() const
Definition: SBuf.h:431
SBuf & append(const SBuf &S)
Definition: SBuf.cc:185
MemBlob::size_type size_type
Definition: SBuf.h:96
SBuf & appendf(const char *fmt,...)
Definition: SBuf.cc:229
CachePeer * peers
Definition: SquidConfig.h:245
#define debugs(SECTION, LEVEL, CONTENT)
Definition: Stream.h:196
@ PEER_PARENT
Definition: enums.h:30
void OBJH(StoreEntry *)
Definition: forward.h:44
void RegisterAction(char const *action, char const *desc, OBJH *handler, int pw_req_flag, int atomic)
Definition: Registration.cc:16
int peerHTTPOkay(const CachePeer *p, PeerSelector *ps)
Definition: neighbors.cc:258
void storeAppendPrintf(StoreEntry *e, const char *fmt,...)
Definition: store.cc:828
char * url
Definition: tcp-banger2.c:114
void EVH void double
Definition: stub_event.cc:16
int unsigned int
Definition: stub_fd.cc:19
struct _request * request(char *urlin)
Definition: tcp-banger2.c:291
void * xcalloc(size_t n, size_t sz)
Definition: xalloc.cc:71
#define safe_free(x)
Definition: xalloc.h:73

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors