3 * DEBUG: section 39 Peer user hash based selection
4 * AUTHOR: Henrik Nordstrom
7 * SQUID Web Proxy Cache http://www.squid-cache.org/
8 * ----------------------------------------------------------
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.
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.
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.
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.
39 #include "auth/UserRequest.h"
40 #include "CachePeer.h"
42 #include "HttpRequest.h"
43 #include "mgr/Registration.h"
44 #include "neighbors.h"
45 #include "SquidConfig.h"
52 #define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))
54 static int n_userhash_peers
= 0;
55 static CachePeer
**userhash_peers
= NULL
;
56 static OBJH peerUserHashCachemgr
;
57 static void peerUserHashRegisterWithCacheManager(void);
60 peerSortWeight(const void *a
, const void *b
)
62 const CachePeer
*const *p1
= (const CachePeer
*const *)a
;
63 const CachePeer
*const *p2
= (const CachePeer
*const *)b
;
64 return (*p1
)->weight
- (*p2
)->weight
;
68 peerUserHashInit(void)
73 double P_last
, X_last
, Xn
;
79 for (k
= 0; k
< n_userhash_peers
; ++k
) {
80 cbdataReferenceDone(userhash_peers
[k
]);
83 safe_free(userhash_peers
);
85 /* find out which peers we have */
87 peerUserHashRegisterWithCacheManager();
89 for (p
= Config
.peers
; p
; p
= p
->next
) {
90 if (!p
->options
.userhash
)
93 assert(p
->type
== PEER_PARENT
);
103 if (n_userhash_peers
== 0)
106 userhash_peers
= (CachePeer
**)xcalloc(n_userhash_peers
, sizeof(*userhash_peers
));
108 /* Build a list of the found peers and calculate hashes and load factors */
109 for (P
= userhash_peers
, p
= Config
.peers
; p
; p
= p
->next
) {
110 if (!p
->options
.userhash
)
116 /* calculate this peers hash */
117 p
->userhash
.hash
= 0;
119 for (t
= p
->name
; *t
!= 0; ++t
)
120 p
->userhash
.hash
+= ROTATE_LEFT(p
->userhash
.hash
, 19) + (unsigned int) *t
;
122 p
->userhash
.hash
+= p
->userhash
.hash
* 0x62531965;
124 p
->userhash
.hash
= ROTATE_LEFT(p
->userhash
.hash
, 21);
126 /* and load factor */
127 p
->userhash
.load_factor
= ((double) p
->weight
) / (double) W
;
129 if (floor(p
->userhash
.load_factor
* 1000.0) == 0.0)
130 p
->userhash
.load_factor
= 0.0;
132 /* add it to our list of peers */
133 *P
++ = cbdataReference(p
);
136 /* Sort our list on weight */
137 qsort(userhash_peers
, n_userhash_peers
, sizeof(*userhash_peers
), peerSortWeight
);
139 /* Calculate the load factor multipliers X_k
141 * X_1 = pow ((K*p_1), (1/K))
142 * X_k = ([K-k+1] * [P_k - P_{k-1}])/(X_1 * X_2 * ... * X_{k-1})
143 * X_k += pow ((X_{k-1}, {K-k+1})
144 * X_k = pow (X_k, {1/(K-k+1)})
145 * simplified to have X_1 part of the loop
147 K
= n_userhash_peers
;
149 P_last
= 0.0; /* Empty P_0 */
151 Xn
= 1.0; /* Empty starting point of X_1 * X_2 * ... * X_{x-1} */
153 X_last
= 0.0; /* Empty X_0, nullifies the first pow statement */
155 for (k
= 1; k
<= K
; ++k
) {
156 double Kk1
= (double) (K
- k
+ 1);
157 p
= userhash_peers
[k
- 1];
158 p
->userhash
.load_multiplier
= (Kk1
* (p
->userhash
.load_factor
- P_last
)) / Xn
;
159 p
->userhash
.load_multiplier
+= pow(X_last
, Kk1
);
160 p
->userhash
.load_multiplier
= pow(p
->userhash
.load_multiplier
, 1.0 / Kk1
);
161 Xn
*= p
->userhash
.load_multiplier
;
162 X_last
= p
->userhash
.load_multiplier
;
163 P_last
= p
->userhash
.load_factor
;
168 peerUserHashRegisterWithCacheManager(void)
170 Mgr::RegisterAction("userhash", "peer userhash information", peerUserHashCachemgr
,
175 peerUserHashSelectParent(HttpRequest
* request
)
181 unsigned int user_hash
= 0;
182 unsigned int combined_hash
;
184 double high_score
= 0;
185 const char *key
= NULL
;
187 if (n_userhash_peers
== 0)
190 if (request
->auth_user_request
!= NULL
)
191 key
= request
->auth_user_request
->username();
196 /* calculate hash key */
197 debugs(39, 2, "peerUserHashSelectParent: Calculating hash for " << key
);
199 for (c
= key
; *c
!= 0; ++c
)
200 user_hash
+= ROTATE_LEFT(user_hash
, 19) + *c
;
202 /* select CachePeer */
203 for (k
= 0; k
< n_userhash_peers
; ++k
) {
204 tp
= userhash_peers
[k
];
205 combined_hash
= (user_hash
^ tp
->userhash
.hash
);
206 combined_hash
+= combined_hash
* 0x62531965;
207 combined_hash
= ROTATE_LEFT(combined_hash
, 21);
208 score
= combined_hash
* tp
->userhash
.load_multiplier
;
209 debugs(39, 3, "peerUserHashSelectParent: " << tp
->name
<< " combined_hash " << combined_hash
<<
210 " score " << std::setprecision(0) << score
);
212 if ((score
> high_score
) && peerHTTPOkay(tp
, request
)) {
219 debugs(39, 2, "peerUserHashSelectParent: selected " << p
->name
);
225 peerUserHashCachemgr(StoreEntry
* sentry
)
229 storeAppendPrintf(sentry
, "%24s %10s %10s %10s %10s\n",
236 for (p
= Config
.peers
; p
; p
= p
->next
)
237 sumfetches
+= p
->stats
.fetches
;
239 for (p
= Config
.peers
; p
; p
= p
->next
) {
240 storeAppendPrintf(sentry
, "%24s %10x %10f %10f %10f\n",
241 p
->name
, p
->userhash
.hash
,
242 p
->userhash
.load_multiplier
,
243 p
->userhash
.load_factor
,
244 sumfetches
? (double) p
->stats
.fetches
/ sumfetches
: -1.0);
248 #endif /* USE_AUTH */