]>
Commit | Line | Data |
---|---|---|
f740a279 | 1 | |
afd88fbe | 2 | /* |
67f46679 | 3 | * DEBUG: section 39 Cache Array Routing Protocol |
b3995439 | 4 | * AUTHOR: Henrik Nordstrom |
5 | * BASED ON: carp.c by Eric Stern and draft-vinod-carp-v1-03.txt | |
afd88fbe | 6 | * |
2b6662ba | 7 | * SQUID Web Proxy Cache http://www.squid-cache.org/ |
e25c139f | 8 | * ---------------------------------------------------------- |
9 | * | |
2b6662ba | 10 | * Squid is the result of efforts by numerous individuals from |
11 | * the Internet community; see the CONTRIBUTORS file for full | |
12 | * details. Many organizations have provided support for Squid's | |
13 | * development; see the SPONSORS file for full details. Squid is | |
14 | * Copyrighted (C) 2001 by the Regents of the University of | |
15 | * California; see the COPYRIGHT file for full details. Squid | |
16 | * incorporates software developed and/or copyrighted by other | |
17 | * sources; see the CREDITS file for full details. | |
e25c139f | 18 | * |
afd88fbe | 19 | * This program is free software; you can redistribute it and/or modify |
20 | * it under the terms of the GNU General Public License as published by | |
21 | * the Free Software Foundation; either version 2 of the License, or | |
22 | * (at your option) any later version. | |
26ac0430 | 23 | * |
afd88fbe | 24 | * This program is distributed in the hope that it will be useful, |
25 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
26 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
27 | * GNU General Public License for more details. | |
26ac0430 | 28 | * |
afd88fbe | 29 | * You should have received a copy of the GNU General Public License |
30 | * along with this program; if not, write to the Free Software | |
cbdec147 | 31 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA. |
e25c139f | 32 | * |
0cdcddb9 | 33 | */ |
afd88fbe | 34 | |
582c2af2 | 35 | #include "squid.h" |
a011edee | 36 | #include "CachePeer.h" |
de03b596 | 37 | #include "HttpRequest.h" |
8822ebee | 38 | #include "mgr/Registration.h" |
f0ba2534 | 39 | #include "neighbors.h" |
4d5904f7 | 40 | #include "SquidConfig.h" |
e6ccf245 | 41 | #include "Store.h" |
b1bd952a | 42 | #include "URL.h" |
de03b596 | 43 | #include "URLScheme.h" |
afd88fbe | 44 | |
582c2af2 FC |
45 | #if HAVE_MATH_H |
46 | #include <math.h> | |
47 | #endif | |
48 | ||
b3995439 | 49 | #define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n)))) |
50 | ||
51 | static int n_carp_peers = 0; | |
a3c6762c | 52 | static CachePeer **carp_peers = NULL; |
8ee9b49f | 53 | static OBJH carpCachemgr; |
54 | ||
b3995439 | 55 | static int |
56 | peerSortWeight(const void *a, const void *b) | |
57 | { | |
a3c6762c FC |
58 | const CachePeer *const *p1 = (const CachePeer *const *)a; |
59 | const CachePeer *const *p2 = (const CachePeer *const *)b; | |
b3995439 | 60 | return (*p1)->weight - (*p2)->weight; |
61 | } | |
62 | ||
5f5e883f FC |
63 | static void |
64 | carpRegisterWithCacheManager(void) | |
65 | { | |
8822ebee | 66 | Mgr::RegisterAction("carp", "CARP information", carpCachemgr, 0, 1); |
5f5e883f FC |
67 | } |
68 | ||
afd88fbe | 69 | void |
70 | carpInit(void) | |
71 | { | |
b3995439 | 72 | int W = 0; |
73 | int K; | |
afd88fbe | 74 | int k; |
b3995439 | 75 | double P_last, X_last, Xn; |
a3c6762c FC |
76 | CachePeer *p; |
77 | CachePeer **P; | |
b3995439 | 78 | char *t; |
79 | /* Clean up */ | |
62e76326 | 80 | |
d7ae3534 | 81 | for (k = 0; k < n_carp_peers; ++k) { |
62e76326 | 82 | cbdataReferenceDone(carp_peers[k]); |
b3995439 | 83 | } |
62e76326 | 84 | |
b3995439 | 85 | safe_free(carp_peers); |
86 | n_carp_peers = 0; | |
8cb183ec FC |
87 | |
88 | /* initialize cache manager before we have a chance to leave the execution path */ | |
89 | carpRegisterWithCacheManager(); | |
90 | ||
b3995439 | 91 | /* find out which peers we have */ |
62e76326 | 92 | |
afd88fbe | 93 | for (p = Config.peers; p; p = p->next) { |
62e76326 | 94 | if (!p->options.carp) |
95 | continue; | |
96 | ||
97 | assert(p->type == PEER_PARENT); | |
98 | ||
99 | if (p->weight == 0) | |
100 | continue; | |
101 | ||
d7ae3534 | 102 | ++n_carp_peers; |
62e76326 | 103 | |
104 | W += p->weight; | |
afd88fbe | 105 | } |
62e76326 | 106 | |
b3995439 | 107 | if (n_carp_peers == 0) |
62e76326 | 108 | return; |
109 | ||
a3c6762c | 110 | carp_peers = (CachePeer **)xcalloc(n_carp_peers, sizeof(*carp_peers)); |
62e76326 | 111 | |
b3995439 | 112 | /* Build a list of the found peers and calculate hashes and load factors */ |
113 | for (P = carp_peers, p = Config.peers; p; p = p->next) { | |
62e76326 | 114 | if (!p->options.carp) |
115 | continue; | |
116 | ||
117 | if (p->weight == 0) | |
118 | continue; | |
119 | ||
120 | /* calculate this peers hash */ | |
121 | p->carp.hash = 0; | |
122 | ||
d7ae3534 | 123 | for (t = p->name; *t != 0; ++t) |
62e76326 | 124 | p->carp.hash += ROTATE_LEFT(p->carp.hash, 19) + (unsigned int) *t; |
125 | ||
126 | p->carp.hash += p->carp.hash * 0x62531965; | |
127 | ||
128 | p->carp.hash = ROTATE_LEFT(p->carp.hash, 21); | |
129 | ||
130 | /* and load factor */ | |
131 | p->carp.load_factor = ((double) p->weight) / (double) W; | |
132 | ||
133 | if (floor(p->carp.load_factor * 1000.0) == 0.0) | |
134 | p->carp.load_factor = 0.0; | |
135 | ||
136 | /* add it to our list of peers */ | |
a38ec4b1 FC |
137 | *P = cbdataReference(p); |
138 | ++P; | |
67766c17 | 139 | } |
62e76326 | 140 | |
b3995439 | 141 | /* Sort our list on weight */ |
142 | qsort(carp_peers, n_carp_peers, sizeof(*carp_peers), peerSortWeight); | |
62e76326 | 143 | |
b3995439 | 144 | /* Calculate the load factor multipliers X_k |
145 | * | |
146 | * X_1 = pow ((K*p_1), (1/K)) | |
147 | * X_k = ([K-k+1] * [P_k - P_{k-1}])/(X_1 * X_2 * ... * X_{k-1}) | |
148 | * X_k += pow ((X_{k-1}, {K-k+1}) | |
149 | * X_k = pow (X_k, {1/(K-k+1)}) | |
150 | * simplified to have X_1 part of the loop | |
afd88fbe | 151 | */ |
b3995439 | 152 | K = n_carp_peers; |
62e76326 | 153 | |
b3995439 | 154 | P_last = 0.0; /* Empty P_0 */ |
62e76326 | 155 | |
b3995439 | 156 | Xn = 1.0; /* Empty starting point of X_1 * X_2 * ... * X_{x-1} */ |
62e76326 | 157 | |
b3995439 | 158 | X_last = 0.0; /* Empty X_0, nullifies the first pow statement */ |
62e76326 | 159 | |
d7ae3534 | 160 | for (k = 1; k <= K; ++k) { |
62e76326 | 161 | double Kk1 = (double) (K - k + 1); |
162 | p = carp_peers[k - 1]; | |
163 | p->carp.load_multiplier = (Kk1 * (p->carp.load_factor - P_last)) / Xn; | |
164 | p->carp.load_multiplier += pow(X_last, Kk1); | |
165 | p->carp.load_multiplier = pow(p->carp.load_multiplier, 1.0 / Kk1); | |
166 | Xn *= p->carp.load_multiplier; | |
167 | X_last = p->carp.load_multiplier; | |
168 | P_last = p->carp.load_factor; | |
afd88fbe | 169 | } |
62ee09ca | 170 | } |
62e76326 | 171 | |
a3c6762c | 172 | CachePeer * |
190154cf | 173 | carpSelectParent(HttpRequest * request) |
afd88fbe | 174 | { |
b3995439 | 175 | int k; |
a3c6762c FC |
176 | CachePeer *p = NULL; |
177 | CachePeer *tp; | |
b3995439 | 178 | unsigned int user_hash = 0; |
179 | unsigned int combined_hash; | |
180 | double score; | |
181 | double high_score = 0; | |
b3995439 | 182 | |
183 | if (n_carp_peers == 0) | |
62e76326 | 184 | return NULL; |
b3995439 | 185 | |
b3995439 | 186 | /* calculate hash key */ |
de03b596 | 187 | debugs(39, 2, "carpSelectParent: Calculating hash for " << urlCanonical(request)); |
62e76326 | 188 | |
a3c6762c | 189 | /* select CachePeer */ |
d7ae3534 | 190 | for (k = 0; k < n_carp_peers; ++k) { |
96f6f33b | 191 | String key; |
62e76326 | 192 | tp = carp_peers[k]; |
de03b596 FC |
193 | if (tp->options.carp_key.set) { |
194 | //this code follows urlCanonical's pattern. | |
195 | // corner cases should use the canonical URL | |
196 | if (tp->options.carp_key.scheme) { | |
197 | // temporary, until bug 1961 URL handling is fixed. | |
198 | const URLScheme sch = request->protocol; | |
199 | key.append(sch.const_str()); | |
200 | if (key.size()) //if the scheme is not empty | |
201 | key.append("://"); | |
202 | } | |
203 | if (tp->options.carp_key.host) { | |
204 | key.append(request->GetHost()); | |
205 | } | |
206 | if (tp->options.carp_key.port) { | |
207 | static char portbuf[7]; | |
208 | snprintf(portbuf,7,":%d", request->port); | |
209 | key.append(portbuf); | |
210 | } | |
211 | if (tp->options.carp_key.path) { | |
212 | String::size_type pos; | |
213 | if ((pos=request->urlpath.find('?'))!=String::npos) | |
214 | key.append(request->urlpath.substr(0,pos)); | |
215 | else | |
216 | key.append(request->urlpath); | |
217 | } | |
218 | if (tp->options.carp_key.params) { | |
219 | String::size_type pos; | |
220 | if ((pos=request->urlpath.find('?'))!=String::npos) | |
221 | key.append(request->urlpath.substr(pos,request->urlpath.size())); | |
222 | } | |
96f6f33b | 223 | } |
de03b596 FC |
224 | // if the url-based key is empty, e.g. because the user is |
225 | // asking to balance on the path but the request doesn't supply any, | |
226 | // then fall back to canonical URL | |
227 | ||
228 | if (key.size()==0) | |
229 | key=urlCanonical(request); | |
230 | ||
d7ae3534 | 231 | for (const char *c = key.rawBuf(), *e=key.rawBuf()+key.size(); c < e; ++c) |
de03b596 | 232 | user_hash += ROTATE_LEFT(user_hash, 19) + *c; |
62e76326 | 233 | combined_hash = (user_hash ^ tp->carp.hash); |
234 | combined_hash += combined_hash * 0x62531965; | |
235 | combined_hash = ROTATE_LEFT(combined_hash, 21); | |
236 | score = combined_hash * tp->carp.load_multiplier; | |
de03b596 FC |
237 | debugs(39, 3, "carpSelectParent: key=" << key << " name=" << tp->name << " combined_hash=" << combined_hash << |
238 | " score=" << std::setprecision(0) << score); | |
62e76326 | 239 | |
240 | if ((score > high_score) && peerHTTPOkay(tp, request)) { | |
241 | p = tp; | |
242 | high_score = score; | |
243 | } | |
afd88fbe | 244 | } |
62e76326 | 245 | |
afd88fbe | 246 | if (p) |
d4140027 | 247 | debugs(39, 2, "carpSelectParent: selected " << p->name); |
62e76326 | 248 | |
afd88fbe | 249 | return p; |
250 | } | |
8ee9b49f | 251 | |
252 | static void | |
253 | carpCachemgr(StoreEntry * sentry) | |
254 | { | |
a3c6762c | 255 | CachePeer *p; |
8ee9b49f | 256 | int sumfetches = 0; |
257 | storeAppendPrintf(sentry, "%24s %10s %10s %10s %10s\n", | |
62e76326 | 258 | "Hostname", |
259 | "Hash", | |
260 | "Multiplier", | |
261 | "Factor", | |
262 | "Actual"); | |
263 | ||
8ee9b49f | 264 | for (p = Config.peers; p; p = p->next) |
62e76326 | 265 | sumfetches += p->stats.fetches; |
266 | ||
8ee9b49f | 267 | for (p = Config.peers; p; p = p->next) { |
62e76326 | 268 | storeAppendPrintf(sentry, "%24s %10x %10f %10f %10f\n", |
d4140027 | 269 | p->name, p->carp.hash, |
62e76326 | 270 | p->carp.load_multiplier, |
271 | p->carp.load_factor, | |
272 | sumfetches ? (double) p->stats.fetches / sumfetches : -1.0); | |
8ee9b49f | 273 | } |
8ee9b49f | 274 | } |