]>
Commit | Line | Data |
---|---|---|
63104e28 HN |
1 | |
2 | /* | |
eec27647 | 3 | * DEBUG: section 39 Peer source hash based selection |
63104e28 | 4 | * AUTHOR: Henrik Nordstrom |
eec27647 | 5 | * BASED ON: carp.cc |
63104e28 HN |
6 | * |
7 | * SQUID Web Proxy Cache http://www.squid-cache.org/ | |
8 | * ---------------------------------------------------------- | |
9 | * | |
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. | |
18 | * | |
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 | * |
63104e28 HN |
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 | * |
63104e28 HN |
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 | |
31 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA. | |
32 | * | |
33 | */ | |
34 | ||
582c2af2 | 35 | #include "squid.h" |
f4a21650 | 36 | #include "HttpRequest.h" |
8822ebee | 37 | #include "mgr/Registration.h" |
f0ba2534 | 38 | #include "neighbors.h" |
582c2af2 FC |
39 | #include "Store.h" |
40 | ||
41 | #if HAVE_MATH_H | |
42 | #include <math.h> | |
43 | #endif | |
63104e28 HN |
44 | |
45 | #define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n)))) | |
46 | ||
f7e1d9ce HN |
47 | static int n_sourcehash_peers = 0; |
48 | static peer **sourcehash_peers = NULL; | |
49 | static OBJH peerSourceHashCachemgr; | |
6b661f2e | 50 | static void peerSourceHashRegisterWithCacheManager(void); |
63104e28 HN |
51 | |
52 | static int | |
53 | peerSortWeight(const void *a, const void *b) | |
54 | { | |
55 | const peer *const *p1 = (const peer *const *)a; | |
56 | const peer *const *p2 = (const peer *const *)b; | |
57 | return (*p1)->weight - (*p2)->weight; | |
58 | } | |
59 | ||
60 | void | |
f7e1d9ce | 61 | peerSourceHashInit(void) |
63104e28 HN |
62 | { |
63 | int W = 0; | |
64 | int K; | |
65 | int k; | |
66 | double P_last, X_last, Xn; | |
67 | peer *p; | |
68 | peer **P; | |
69 | char *t; | |
70 | /* Clean up */ | |
71 | ||
5db6bf73 | 72 | for (k = 0; k < n_sourcehash_peers; ++k) { |
f7e1d9ce | 73 | cbdataReferenceDone(sourcehash_peers[k]); |
63104e28 HN |
74 | } |
75 | ||
f7e1d9ce HN |
76 | safe_free(sourcehash_peers); |
77 | n_sourcehash_peers = 0; | |
63104e28 HN |
78 | /* find out which peers we have */ |
79 | ||
80 | for (p = Config.peers; p; p = p->next) { | |
f7e1d9ce | 81 | if (!p->options.sourcehash) |
63104e28 HN |
82 | continue; |
83 | ||
84 | assert(p->type == PEER_PARENT); | |
85 | ||
86 | if (p->weight == 0) | |
87 | continue; | |
88 | ||
5db6bf73 | 89 | ++n_sourcehash_peers; |
63104e28 HN |
90 | |
91 | W += p->weight; | |
92 | } | |
93 | ||
6b661f2e FC |
94 | peerSourceHashRegisterWithCacheManager(); |
95 | ||
f7e1d9ce | 96 | if (n_sourcehash_peers == 0) |
63104e28 HN |
97 | return; |
98 | ||
f7e1d9ce | 99 | sourcehash_peers = (peer **)xcalloc(n_sourcehash_peers, sizeof(*sourcehash_peers)); |
63104e28 HN |
100 | |
101 | /* Build a list of the found peers and calculate hashes and load factors */ | |
f7e1d9ce HN |
102 | for (P = sourcehash_peers, p = Config.peers; p; p = p->next) { |
103 | if (!p->options.sourcehash) | |
63104e28 HN |
104 | continue; |
105 | ||
106 | if (p->weight == 0) | |
107 | continue; | |
108 | ||
109 | /* calculate this peers hash */ | |
f7e1d9ce | 110 | p->sourcehash.hash = 0; |
63104e28 | 111 | |
5db6bf73 | 112 | for (t = p->name; *t != 0; ++t) |
f7e1d9ce | 113 | p->sourcehash.hash += ROTATE_LEFT(p->sourcehash.hash, 19) + (unsigned int) *t; |
63104e28 | 114 | |
f7e1d9ce | 115 | p->sourcehash.hash += p->sourcehash.hash * 0x62531965; |
63104e28 | 116 | |
f7e1d9ce | 117 | p->sourcehash.hash = ROTATE_LEFT(p->sourcehash.hash, 21); |
63104e28 HN |
118 | |
119 | /* and load factor */ | |
f7e1d9ce | 120 | p->sourcehash.load_factor = ((double) p->weight) / (double) W; |
63104e28 | 121 | |
f7e1d9ce HN |
122 | if (floor(p->sourcehash.load_factor * 1000.0) == 0.0) |
123 | p->sourcehash.load_factor = 0.0; | |
63104e28 HN |
124 | |
125 | /* add it to our list of peers */ | |
126 | *P++ = cbdataReference(p); | |
127 | } | |
128 | ||
129 | /* Sort our list on weight */ | |
f7e1d9ce | 130 | qsort(sourcehash_peers, n_sourcehash_peers, sizeof(*sourcehash_peers), peerSortWeight); |
63104e28 HN |
131 | |
132 | /* Calculate the load factor multipliers X_k | |
133 | * | |
134 | * X_1 = pow ((K*p_1), (1/K)) | |
135 | * X_k = ([K-k+1] * [P_k - P_{k-1}])/(X_1 * X_2 * ... * X_{k-1}) | |
136 | * X_k += pow ((X_{k-1}, {K-k+1}) | |
137 | * X_k = pow (X_k, {1/(K-k+1)}) | |
138 | * simplified to have X_1 part of the loop | |
139 | */ | |
f7e1d9ce | 140 | K = n_sourcehash_peers; |
63104e28 HN |
141 | |
142 | P_last = 0.0; /* Empty P_0 */ | |
143 | ||
144 | Xn = 1.0; /* Empty starting point of X_1 * X_2 * ... * X_{x-1} */ | |
145 | ||
146 | X_last = 0.0; /* Empty X_0, nullifies the first pow statement */ | |
147 | ||
5db6bf73 | 148 | for (k = 1; k <= K; ++k) { |
63104e28 | 149 | double Kk1 = (double) (K - k + 1); |
f7e1d9ce HN |
150 | p = sourcehash_peers[k - 1]; |
151 | p->sourcehash.load_multiplier = (Kk1 * (p->sourcehash.load_factor - P_last)) / Xn; | |
152 | p->sourcehash.load_multiplier += pow(X_last, Kk1); | |
153 | p->sourcehash.load_multiplier = pow(p->sourcehash.load_multiplier, 1.0 / Kk1); | |
154 | Xn *= p->sourcehash.load_multiplier; | |
155 | X_last = p->sourcehash.load_multiplier; | |
156 | P_last = p->sourcehash.load_factor; | |
63104e28 HN |
157 | } |
158 | } | |
159 | ||
6b661f2e FC |
160 | static void |
161 | peerSourceHashRegisterWithCacheManager(void) | |
63104e28 | 162 | { |
8822ebee | 163 | Mgr::RegisterAction("sourcehash", "peer sourcehash information", |
d9fc6862 | 164 | peerSourceHashCachemgr, 0, 1); |
63104e28 HN |
165 | } |
166 | ||
167 | peer * | |
f7e1d9ce | 168 | peerSourceHashSelectParent(HttpRequest * request) |
63104e28 HN |
169 | { |
170 | int k; | |
171 | const char *c; | |
172 | peer *p = NULL; | |
173 | peer *tp; | |
174 | unsigned int user_hash = 0; | |
175 | unsigned int combined_hash; | |
176 | double score; | |
177 | double high_score = 0; | |
178 | const char *key = NULL; | |
eec27647 | 179 | char ntoabuf[MAX_IPSTRLEN]; |
63104e28 | 180 | |
f7e1d9ce | 181 | if (n_sourcehash_peers == 0) |
63104e28 HN |
182 | return NULL; |
183 | ||
eec27647 | 184 | key = request->client_addr.NtoA(ntoabuf, sizeof(ntoabuf)); |
63104e28 HN |
185 | |
186 | /* calculate hash key */ | |
f7e1d9ce | 187 | debugs(39, 2, "peerSourceHashSelectParent: Calculating hash for " << key); |
63104e28 | 188 | |
5db6bf73 | 189 | for (c = key; *c != 0; ++c) |
63104e28 HN |
190 | user_hash += ROTATE_LEFT(user_hash, 19) + *c; |
191 | ||
192 | /* select peer */ | |
5db6bf73 | 193 | for (k = 0; k < n_sourcehash_peers; ++k) { |
f7e1d9ce HN |
194 | tp = sourcehash_peers[k]; |
195 | combined_hash = (user_hash ^ tp->sourcehash.hash); | |
63104e28 HN |
196 | combined_hash += combined_hash * 0x62531965; |
197 | combined_hash = ROTATE_LEFT(combined_hash, 21); | |
f7e1d9ce | 198 | score = combined_hash * tp->sourcehash.load_multiplier; |
26ac0430 | 199 | debugs(39, 3, "peerSourceHashSelectParent: " << tp->name << " combined_hash " << combined_hash << |
63104e28 HN |
200 | " score " << std::setprecision(0) << score); |
201 | ||
202 | if ((score > high_score) && peerHTTPOkay(tp, request)) { | |
203 | p = tp; | |
204 | high_score = score; | |
205 | } | |
206 | } | |
207 | ||
208 | if (p) | |
f7e1d9ce | 209 | debugs(39, 2, "peerSourceHashSelectParent: selected " << p->name); |
63104e28 HN |
210 | |
211 | return p; | |
212 | } | |
213 | ||
214 | static void | |
f7e1d9ce | 215 | peerSourceHashCachemgr(StoreEntry * sentry) |
63104e28 HN |
216 | { |
217 | peer *p; | |
218 | int sumfetches = 0; | |
219 | storeAppendPrintf(sentry, "%24s %10s %10s %10s %10s\n", | |
220 | "Hostname", | |
221 | "Hash", | |
222 | "Multiplier", | |
223 | "Factor", | |
224 | "Actual"); | |
225 | ||
226 | for (p = Config.peers; p; p = p->next) | |
227 | sumfetches += p->stats.fetches; | |
228 | ||
229 | for (p = Config.peers; p; p = p->next) { | |
230 | storeAppendPrintf(sentry, "%24s %10x %10f %10f %10f\n", | |
f7e1d9ce HN |
231 | p->name, p->sourcehash.hash, |
232 | p->sourcehash.load_multiplier, | |
233 | p->sourcehash.load_factor, | |
63104e28 HN |
234 | sumfetches ? (double) p->stats.fetches / sumfetches : -1.0); |
235 | } | |
236 | } |