]>
git.ipfire.org Git - thirdparty/squid.git/blob - src/carp.cc
5 * DEBUG: section 39 Cache Array Routing Protocol
6 * AUTHOR: Henrik Nordstrom
7 * BASED ON: carp.c by Eric Stern and draft-vinod-carp-v1-03.txt
9 * SQUID Web Proxy Cache http://www.squid-cache.org/
10 * ----------------------------------------------------------
12 * Squid is the result of efforts by numerous individuals from
13 * the Internet community; see the CONTRIBUTORS file for full
14 * details. Many organizations have provided support for Squid's
15 * development; see the SPONSORS file for full details. Squid is
16 * Copyrighted (C) 2001 by the Regents of the University of
17 * California; see the COPYRIGHT file for full details. Squid
18 * incorporates software developed and/or copyrighted by other
19 * sources; see the CREDITS file for full details.
21 * This program is free software; you can redistribute it and/or modify
22 * it under the terms of the GNU General Public License as published by
23 * the Free Software Foundation; either version 2 of the License, or
24 * (at your option) any later version.
26 * This program is distributed in the hope that it will be useful,
27 * but WITHOUT ANY WARRANTY; without even the implied warranty of
28 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
29 * GNU General Public License for more details.
31 * You should have received a copy of the GNU General Public License
32 * along with this program; if not, write to the Free Software
33 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
38 #include "HttpRequest.h"
39 #include "mgr/Registration.h"
40 #include "neighbors.h"
44 #include "URLScheme.h"
50 #define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))
52 static int n_carp_peers
= 0;
53 static peer
**carp_peers
= NULL
;
54 static OBJH carpCachemgr
;
57 peerSortWeight(const void *a
, const void *b
)
59 const peer
*const *p1
= (const peer
*const *)a
;
60 const peer
*const *p2
= (const peer
*const *)b
;
61 return (*p1
)->weight
- (*p2
)->weight
;
65 carpRegisterWithCacheManager(void)
67 Mgr::RegisterAction("carp", "CARP information", carpCachemgr
, 0, 1);
76 double P_last
, X_last
, Xn
;
82 for (k
= 0; k
< n_carp_peers
; ++k
) {
83 cbdataReferenceDone(carp_peers
[k
]);
86 safe_free(carp_peers
);
89 /* initialize cache manager before we have a chance to leave the execution path */
90 carpRegisterWithCacheManager();
92 /* find out which peers we have */
94 for (p
= Config
.peers
; p
; p
= p
->next
) {
98 assert(p
->type
== PEER_PARENT
);
108 if (n_carp_peers
== 0)
111 carp_peers
= (peer
**)xcalloc(n_carp_peers
, sizeof(*carp_peers
));
113 /* Build a list of the found peers and calculate hashes and load factors */
114 for (P
= carp_peers
, p
= Config
.peers
; p
; p
= p
->next
) {
115 if (!p
->options
.carp
)
121 /* calculate this peers hash */
124 for (t
= p
->name
; *t
!= 0; ++t
)
125 p
->carp
.hash
+= ROTATE_LEFT(p
->carp
.hash
, 19) + (unsigned int) *t
;
127 p
->carp
.hash
+= p
->carp
.hash
* 0x62531965;
129 p
->carp
.hash
= ROTATE_LEFT(p
->carp
.hash
, 21);
131 /* and load factor */
132 p
->carp
.load_factor
= ((double) p
->weight
) / (double) W
;
134 if (floor(p
->carp
.load_factor
* 1000.0) == 0.0)
135 p
->carp
.load_factor
= 0.0;
137 /* add it to our list of peers */
138 *P
= cbdataReference(p
);
142 /* Sort our list on weight */
143 qsort(carp_peers
, n_carp_peers
, sizeof(*carp_peers
), peerSortWeight
);
145 /* Calculate the load factor multipliers X_k
147 * X_1 = pow ((K*p_1), (1/K))
148 * X_k = ([K-k+1] * [P_k - P_{k-1}])/(X_1 * X_2 * ... * X_{k-1})
149 * X_k += pow ((X_{k-1}, {K-k+1})
150 * X_k = pow (X_k, {1/(K-k+1)})
151 * simplified to have X_1 part of the loop
155 P_last
= 0.0; /* Empty P_0 */
157 Xn
= 1.0; /* Empty starting point of X_1 * X_2 * ... * X_{x-1} */
159 X_last
= 0.0; /* Empty X_0, nullifies the first pow statement */
161 for (k
= 1; k
<= K
; ++k
) {
162 double Kk1
= (double) (K
- k
+ 1);
163 p
= carp_peers
[k
- 1];
164 p
->carp
.load_multiplier
= (Kk1
* (p
->carp
.load_factor
- P_last
)) / Xn
;
165 p
->carp
.load_multiplier
+= pow(X_last
, Kk1
);
166 p
->carp
.load_multiplier
= pow(p
->carp
.load_multiplier
, 1.0 / Kk1
);
167 Xn
*= p
->carp
.load_multiplier
;
168 X_last
= p
->carp
.load_multiplier
;
169 P_last
= p
->carp
.load_factor
;
174 carpSelectParent(HttpRequest
* request
)
179 unsigned int user_hash
= 0;
180 unsigned int combined_hash
;
182 double high_score
= 0;
184 if (n_carp_peers
== 0)
187 /* calculate hash key */
188 debugs(39, 2, "carpSelectParent: Calculating hash for " << urlCanonical(request
));
191 for (k
= 0; k
< n_carp_peers
; ++k
) {
194 if (tp
->options
.carp_key
.set
) {
195 //this code follows urlCanonical's pattern.
196 // corner cases should use the canonical URL
197 if (tp
->options
.carp_key
.scheme
) {
198 // temporary, until bug 1961 URL handling is fixed.
199 const URLScheme sch
= request
->protocol
;
200 key
.append(sch
.const_str());
201 if (key
.size()) //if the scheme is not empty
204 if (tp
->options
.carp_key
.host
) {
205 key
.append(request
->GetHost());
207 if (tp
->options
.carp_key
.port
) {
208 static char portbuf
[7];
209 snprintf(portbuf
,7,":%d", request
->port
);
212 if (tp
->options
.carp_key
.path
) {
213 String::size_type pos
;
214 if ((pos
=request
->urlpath
.find('?'))!=String::npos
)
215 key
.append(request
->urlpath
.substr(0,pos
));
217 key
.append(request
->urlpath
);
219 if (tp
->options
.carp_key
.params
) {
220 String::size_type pos
;
221 if ((pos
=request
->urlpath
.find('?'))!=String::npos
)
222 key
.append(request
->urlpath
.substr(pos
,request
->urlpath
.size()));
225 // if the url-based key is empty, e.g. because the user is
226 // asking to balance on the path but the request doesn't supply any,
227 // then fall back to canonical URL
230 key
=urlCanonical(request
);
232 for (const char *c
= key
.rawBuf(), *e
=key
.rawBuf()+key
.size(); c
< e
; ++c
)
233 user_hash
+= ROTATE_LEFT(user_hash
, 19) + *c
;
234 combined_hash
= (user_hash
^ tp
->carp
.hash
);
235 combined_hash
+= combined_hash
* 0x62531965;
236 combined_hash
= ROTATE_LEFT(combined_hash
, 21);
237 score
= combined_hash
* tp
->carp
.load_multiplier
;
238 debugs(39, 3, "carpSelectParent: key=" << key
<< " name=" << tp
->name
<< " combined_hash=" << combined_hash
<<
239 " score=" << std::setprecision(0) << score
);
241 if ((score
> high_score
) && peerHTTPOkay(tp
, request
)) {
248 debugs(39, 2, "carpSelectParent: selected " << p
->name
);
254 carpCachemgr(StoreEntry
* sentry
)
258 storeAppendPrintf(sentry
, "%24s %10s %10s %10s %10s\n",
265 for (p
= Config
.peers
; p
; p
= p
->next
)
266 sumfetches
+= p
->stats
.fetches
;
268 for (p
= Config
.peers
; p
; p
= p
->next
) {
269 storeAppendPrintf(sentry
, "%24s %10x %10f %10f %10f\n",
270 p
->name
, p
->carp
.hash
,
271 p
->carp
.load_multiplier
,
273 sumfetches
? (double) p
->stats
.fetches
/ sumfetches
: -1.0);