]>
git.ipfire.org Git - thirdparty/squid.git/blob - src/carp.cc
2 * Copyright (C) 1996-2021 The Squid Software Foundation and contributors
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.
9 /* DEBUG: section 39 Cache Array Routing Protocol */
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"
22 #define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))
24 static int n_carp_peers
= 0;
25 static CachePeer
**carp_peers
= NULL
;
26 static OBJH carpCachemgr
;
29 peerSortWeight(const void *a
, const void *b
)
31 const CachePeer
*const *p1
= (const CachePeer
*const *)a
;
32 const CachePeer
*const *p2
= (const CachePeer
*const *)b
;
33 return (*p1
)->weight
- (*p2
)->weight
;
37 carpRegisterWithCacheManager(void)
39 Mgr::RegisterAction("carp", "CARP information", carpCachemgr
, 0, 1);
48 double P_last
, X_last
, Xn
;
54 for (k
= 0; k
< n_carp_peers
; ++k
) {
55 cbdataReferenceDone(carp_peers
[k
]);
58 safe_free(carp_peers
);
61 /* initialize cache manager before we have a chance to leave the execution path */
62 carpRegisterWithCacheManager();
64 /* find out which peers we have */
66 for (p
= Config
.peers
; p
; p
= p
->next
) {
70 assert(p
->type
== PEER_PARENT
);
80 if (n_carp_peers
== 0)
83 carp_peers
= (CachePeer
**)xcalloc(n_carp_peers
, sizeof(*carp_peers
));
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
) {
93 /* calculate this peers hash */
96 for (t
= p
->name
; *t
!= 0; ++t
)
97 p
->carp
.hash
+= ROTATE_LEFT(p
->carp
.hash
, 19) + (unsigned int) *t
;
99 p
->carp
.hash
+= p
->carp
.hash
* 0x62531965;
101 p
->carp
.hash
= ROTATE_LEFT(p
->carp
.hash
, 21);
103 /* and load factor */
104 p
->carp
.load_factor
= ((double) p
->weight
) / (double) W
;
106 if (floor(p
->carp
.load_factor
* 1000.0) == 0.0)
107 p
->carp
.load_factor
= 0.0;
109 /* add it to our list of peers */
110 *P
= cbdataReference(p
);
114 /* Sort our list on weight */
115 qsort(carp_peers
, n_carp_peers
, sizeof(*carp_peers
), peerSortWeight
);
117 /* Calculate the load factor multipliers X_k
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
127 P_last
= 0.0; /* Empty P_0 */
129 Xn
= 1.0; /* Empty starting point of X_1 * X_2 * ... * X_{x-1} */
131 X_last
= 0.0; /* Empty X_0, nullifies the first pow statement */
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
;
146 carpSelectParent(PeerSelector
*ps
)
149 HttpRequest
*request
= ps
->request
;
154 unsigned int user_hash
= 0;
155 unsigned int combined_hash
;
157 double high_score
= 0;
159 if (n_carp_peers
== 0)
162 /* calculate hash key */
163 debugs(39, 2, "carpSelectParent: Calculating hash for " << request
->effectiveRequestUri());
165 /* select CachePeer */
166 for (k
= 0; k
< n_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
177 if (tp
->options
.carp_key
.host
) {
178 key
.append(request
->url
.host());
180 if (tp
->options
.carp_key
.port
) {
181 key
.appendf(":%u", request
->url
.port());
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
187 if (tp
->options
.carp_key
.params
) {
188 // XXX: fix when path and query are separate
190 if ((pos
=request
->url
.path().find('?')) != SBuf::npos
)
191 key
.append(request
->url
.path().substr(pos
)); // N..npos
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
199 key
=request
->effectiveRequestUri();
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
);
210 if ((score
> high_score
) && peerHTTPOkay(tp
, ps
)) {
217 debugs(39, 2, "carpSelectParent: selected " << p
->name
);
223 carpCachemgr(StoreEntry
* sentry
)
227 storeAppendPrintf(sentry
, "%24s %10s %10s %10s %10s\n",
234 for (p
= Config
.peers
; p
; p
= p
->next
)
235 sumfetches
+= p
->stats
.fetches
;
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
,
242 sumfetches
? (double) p
->stats
.fetches
/ sumfetches
: -1.0);