2 * Copyright (C) 1996-2023 The Squid Software Foundation and contributors
4 * Squid software is distributed under GPLv2+ license and includes
5 * contributions from numerous individuals and organizations.
6 * Please see the COPYING and CONTRIBUTORS files for details.
9 /* DEBUG: section 39 Peer user hash based selection */
15 #include "auth/UserRequest.h"
16 #include "base/RunnersRegistry.h"
17 #include "CachePeer.h"
18 #include "CachePeers.h"
20 #include "HttpRequest.h"
21 #include "mgr/Registration.h"
22 #include "neighbors.h"
23 #include "peer_userhash.h"
24 #include "PeerSelectState.h"
25 #include "SquidConfig.h"
30 #define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))
32 /// userhash peers ordered by their userhash weight
36 static const auto hashPeers
= new SelectedCachePeers();
40 static OBJH peerUserHashCachemgr
;
41 static void peerUserHashRegisterWithCacheManager(void);
44 peerSortWeight(const void *a
, const void *b
)
46 const CachePeer
*const *p1
= (const CachePeer
*const *)a
;
47 const CachePeer
*const *p2
= (const CachePeer
*const *)b
;
48 return (*p1
)->weight
- (*p2
)->weight
;
52 peerUserHashInit(void)
55 double P_last
, X_last
, Xn
;
59 UserHashPeers().clear();
60 /* find out which peers we have */
62 peerUserHashRegisterWithCacheManager();
64 RawCachePeers rawUserHashPeers
;
65 for (const auto &p
: CurrentCachePeers()) {
66 const auto peer
= p
.get();
68 if (!p
->options
.userhash
)
71 assert(p
->type
== PEER_PARENT
);
76 rawUserHashPeers
.push_back(peer
);
81 if (rawUserHashPeers
.empty())
84 /* calculate hashes and load factors */
85 for (const auto &p
: rawUserHashPeers
) {
86 /* calculate this peers hash */
89 for (t
= p
->name
; *t
!= 0; ++t
)
90 p
->userhash
.hash
+= ROTATE_LEFT(p
->userhash
.hash
, 19) + (unsigned int) *t
;
92 p
->userhash
.hash
+= p
->userhash
.hash
* 0x62531965;
94 p
->userhash
.hash
= ROTATE_LEFT(p
->userhash
.hash
, 21);
97 p
->userhash
.load_factor
= ((double) p
->weight
) / (double) W
;
99 if (floor(p
->userhash
.load_factor
* 1000.0) == 0.0)
100 p
->userhash
.load_factor
= 0.0;
103 /* Sort our list on weight */
104 qsort(rawUserHashPeers
.data(), rawUserHashPeers
.size(), sizeof(decltype(rawUserHashPeers
)::value_type
), peerSortWeight
);
106 /* Calculate the load factor multipliers X_k
108 * X_1 = pow ((K*p_1), (1/K))
109 * X_k = ([K-k+1] * [P_k - P_{k-1}])/(X_1 * X_2 * ... * X_{k-1})
110 * X_k += pow ((X_{k-1}, {K-k+1})
111 * X_k = pow (X_k, {1/(K-k+1)})
112 * simplified to have X_1 part of the loop
114 const auto K
= rawUserHashPeers
.size();
116 P_last
= 0.0; /* Empty P_0 */
118 Xn
= 1.0; /* Empty starting point of X_1 * X_2 * ... * X_{x-1} */
120 X_last
= 0.0; /* Empty X_0, nullifies the first pow statement */
122 for (size_t k
= 1; k
<= K
; ++k
) {
123 double Kk1
= (double) (K
- k
+ 1);
124 const auto p
= rawUserHashPeers
[k
- 1];
125 p
->userhash
.load_multiplier
= (Kk1
* (p
->userhash
.load_factor
- P_last
)) / Xn
;
126 p
->userhash
.load_multiplier
+= pow(X_last
, Kk1
);
127 p
->userhash
.load_multiplier
= pow(p
->userhash
.load_multiplier
, 1.0 / Kk1
);
128 Xn
*= p
->userhash
.load_multiplier
;
129 X_last
= p
->userhash
.load_multiplier
;
130 P_last
= p
->userhash
.load_factor
;
133 UserHashPeers().assign(rawUserHashPeers
.begin(), rawUserHashPeers
.end());
137 peerUserHashRegisterWithCacheManager(void)
139 Mgr::RegisterAction("userhash", "peer userhash information", peerUserHashCachemgr
,
143 /// reacts to RegisteredRunner events relevant to this module
144 class PeerUserHashRr
: public RegisteredRunner
147 /* RegisteredRunner API */
148 void useConfig() override
{ peerUserHashInit(); }
149 void syncConfig() override
{ peerUserHashInit(); }
152 DefineRunnerRegistrator(PeerUserHashRr
);
155 peerUserHashSelectParent(PeerSelector
*ps
)
158 CachePeer
*p
= nullptr;
159 unsigned int user_hash
= 0;
160 unsigned int combined_hash
;
162 double high_score
= 0;
163 const char *key
= nullptr;
165 if (UserHashPeers().empty())
169 HttpRequest
*request
= ps
->request
;
171 if (request
->auth_user_request
!= nullptr)
172 key
= request
->auth_user_request
->username();
177 /* calculate hash key */
178 debugs(39, 2, "peerUserHashSelectParent: Calculating hash for " << key
);
180 for (c
= key
; *c
!= 0; ++c
)
181 user_hash
+= ROTATE_LEFT(user_hash
, 19) + *c
;
183 /* select CachePeer */
184 for (const auto &tp
: UserHashPeers()) {
186 continue; // peer gone
188 combined_hash
= (user_hash
^ tp
->userhash
.hash
);
189 combined_hash
+= combined_hash
* 0x62531965;
190 combined_hash
= ROTATE_LEFT(combined_hash
, 21);
191 score
= combined_hash
* tp
->userhash
.load_multiplier
;
192 debugs(39, 3, *tp
<< " combined_hash " << combined_hash
<<
193 " score " << std::setprecision(0) << score
);
195 if ((score
> high_score
) && peerHTTPOkay(tp
.get(), ps
)) {
202 debugs(39, 2, "selected " << *p
);
208 peerUserHashCachemgr(StoreEntry
* sentry
)
211 storeAppendPrintf(sentry
, "%24s %10s %10s %10s %10s\n",
218 for (const auto &p
: UserHashPeers()) {
221 sumfetches
+= p
->stats
.fetches
;
224 for (const auto &p
: UserHashPeers()) {
227 storeAppendPrintf(sentry
, "%24s %10x %10f %10f %10f\n",
228 p
->name
, p
->userhash
.hash
,
229 p
->userhash
.load_multiplier
,
230 p
->userhash
.load_factor
,
231 sumfetches
? (double) p
->stats
.fetches
/ sumfetches
: -1.0);
235 #endif /* USE_AUTH */