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