]>
Commit | Line | Data |
---|---|---|
63104e28 | 1 | /* |
b8ae064d | 2 | * Copyright (C) 1996-2023 The Squid Software Foundation and contributors |
63104e28 | 3 | * |
bbc27441 AJ |
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. | |
63104e28 HN |
7 | */ |
8 | ||
bbc27441 AJ |
9 | /* DEBUG: section 39 Peer source hash based selection */ |
10 | ||
582c2af2 | 11 | #include "squid.h" |
8c469f12 | 12 | #include "base/RunnersRegistry.h" |
a011edee | 13 | #include "CachePeer.h" |
2e24d0bf | 14 | #include "CachePeers.h" |
f4a21650 | 15 | #include "HttpRequest.h" |
8822ebee | 16 | #include "mgr/Registration.h" |
f0ba2534 | 17 | #include "neighbors.h" |
8b082ed9 | 18 | #include "peer_sourcehash.h" |
cb365059 | 19 | #include "PeerSelectState.h" |
4d5904f7 | 20 | #include "SquidConfig.h" |
582c2af2 FC |
21 | #include "Store.h" |
22 | ||
074d6a40 | 23 | #include <cmath> |
63104e28 HN |
24 | |
25 | #define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n)))) | |
26 | ||
2d5ac435 EB |
27 | /// sourcehash peers ordered by their sourcehash weight |
28 | static auto & | |
29 | SourceHashPeers() | |
30 | { | |
31 | static const auto hashPeers = new SelectedCachePeers(); | |
32 | return *hashPeers; | |
33 | } | |
34 | ||
f7e1d9ce | 35 | static OBJH peerSourceHashCachemgr; |
6b661f2e | 36 | static void peerSourceHashRegisterWithCacheManager(void); |
63104e28 HN |
37 | |
38 | static int | |
39 | peerSortWeight(const void *a, const void *b) | |
40 | { | |
a3c6762c FC |
41 | const CachePeer *const *p1 = (const CachePeer *const *)a; |
42 | const CachePeer *const *p2 = (const CachePeer *const *)b; | |
63104e28 HN |
43 | return (*p1)->weight - (*p2)->weight; |
44 | } | |
45 | ||
8c469f12 | 46 | static void |
f7e1d9ce | 47 | peerSourceHashInit(void) |
63104e28 HN |
48 | { |
49 | int W = 0; | |
63104e28 | 50 | double P_last, X_last, Xn; |
63104e28 HN |
51 | char *t; |
52 | /* Clean up */ | |
53 | ||
2d5ac435 | 54 | SourceHashPeers().clear(); |
63104e28 HN |
55 | /* find out which peers we have */ |
56 | ||
2d5ac435 | 57 | RawCachePeers rawSourceHashPeers; |
2e24d0bf | 58 | for (const auto &p: CurrentCachePeers()) { |
2d5ac435 EB |
59 | const auto peer = p.get(); |
60 | ||
f7e1d9ce | 61 | if (!p->options.sourcehash) |
63104e28 HN |
62 | continue; |
63 | ||
64 | assert(p->type == PEER_PARENT); | |
65 | ||
66 | if (p->weight == 0) | |
67 | continue; | |
68 | ||
2d5ac435 | 69 | rawSourceHashPeers.push_back(peer); |
63104e28 HN |
70 | |
71 | W += p->weight; | |
72 | } | |
73 | ||
6b661f2e FC |
74 | peerSourceHashRegisterWithCacheManager(); |
75 | ||
2d5ac435 | 76 | if (rawSourceHashPeers.empty()) |
63104e28 HN |
77 | return; |
78 | ||
2d5ac435 EB |
79 | /* calculate hashes and load factors */ |
80 | for (const auto &p: rawSourceHashPeers) { | |
63104e28 | 81 | /* calculate this peers hash */ |
f7e1d9ce | 82 | p->sourcehash.hash = 0; |
63104e28 | 83 | |
5db6bf73 | 84 | for (t = p->name; *t != 0; ++t) |
f7e1d9ce | 85 | p->sourcehash.hash += ROTATE_LEFT(p->sourcehash.hash, 19) + (unsigned int) *t; |
63104e28 | 86 | |
f7e1d9ce | 87 | p->sourcehash.hash += p->sourcehash.hash * 0x62531965; |
63104e28 | 88 | |
f7e1d9ce | 89 | p->sourcehash.hash = ROTATE_LEFT(p->sourcehash.hash, 21); |
63104e28 HN |
90 | |
91 | /* and load factor */ | |
f7e1d9ce | 92 | p->sourcehash.load_factor = ((double) p->weight) / (double) W; |
63104e28 | 93 | |
f7e1d9ce HN |
94 | if (floor(p->sourcehash.load_factor * 1000.0) == 0.0) |
95 | p->sourcehash.load_factor = 0.0; | |
63104e28 HN |
96 | } |
97 | ||
98 | /* Sort our list on weight */ | |
2d5ac435 | 99 | qsort(rawSourceHashPeers.data(), rawSourceHashPeers.size(), sizeof(decltype(rawSourceHashPeers)::value_type), peerSortWeight); |
63104e28 HN |
100 | |
101 | /* Calculate the load factor multipliers X_k | |
102 | * | |
103 | * X_1 = pow ((K*p_1), (1/K)) | |
104 | * X_k = ([K-k+1] * [P_k - P_{k-1}])/(X_1 * X_2 * ... * X_{k-1}) | |
105 | * X_k += pow ((X_{k-1}, {K-k+1}) | |
106 | * X_k = pow (X_k, {1/(K-k+1)}) | |
107 | * simplified to have X_1 part of the loop | |
108 | */ | |
2d5ac435 | 109 | const auto K = rawSourceHashPeers.size(); |
63104e28 | 110 | |
f53969cc | 111 | P_last = 0.0; /* Empty P_0 */ |
63104e28 | 112 | |
f53969cc | 113 | Xn = 1.0; /* Empty starting point of X_1 * X_2 * ... * X_{x-1} */ |
63104e28 | 114 | |
f53969cc | 115 | X_last = 0.0; /* Empty X_0, nullifies the first pow statement */ |
63104e28 | 116 | |
2d5ac435 | 117 | for (size_t k = 1; k <= K; ++k) { |
63104e28 | 118 | double Kk1 = (double) (K - k + 1); |
2d5ac435 | 119 | const auto p = rawSourceHashPeers[k - 1]; |
f7e1d9ce HN |
120 | p->sourcehash.load_multiplier = (Kk1 * (p->sourcehash.load_factor - P_last)) / Xn; |
121 | p->sourcehash.load_multiplier += pow(X_last, Kk1); | |
122 | p->sourcehash.load_multiplier = pow(p->sourcehash.load_multiplier, 1.0 / Kk1); | |
123 | Xn *= p->sourcehash.load_multiplier; | |
124 | X_last = p->sourcehash.load_multiplier; | |
125 | P_last = p->sourcehash.load_factor; | |
63104e28 | 126 | } |
2d5ac435 EB |
127 | |
128 | SourceHashPeers().assign(rawSourceHashPeers.begin(), rawSourceHashPeers.end()); | |
63104e28 HN |
129 | } |
130 | ||
8c469f12 AR |
131 | /// reacts to RegisteredRunner events relevant to this module |
132 | class PeerSourceHashRr: public RegisteredRunner | |
133 | { | |
134 | public: | |
135 | /* RegisteredRunner API */ | |
136 | void useConfig() override { peerSourceHashInit(); } | |
137 | void syncConfig() override { peerSourceHashInit(); } | |
138 | }; | |
139 | ||
140 | DefineRunnerRegistrator(PeerSourceHashRr); | |
141 | ||
6b661f2e FC |
142 | static void |
143 | peerSourceHashRegisterWithCacheManager(void) | |
63104e28 | 144 | { |
8822ebee | 145 | Mgr::RegisterAction("sourcehash", "peer sourcehash information", |
d9fc6862 | 146 | peerSourceHashCachemgr, 0, 1); |
63104e28 HN |
147 | } |
148 | ||
a3c6762c | 149 | CachePeer * |
cb365059 | 150 | peerSourceHashSelectParent(PeerSelector *ps) |
63104e28 | 151 | { |
63104e28 | 152 | const char *c; |
aee3523a | 153 | CachePeer *p = nullptr; |
63104e28 HN |
154 | unsigned int user_hash = 0; |
155 | unsigned int combined_hash; | |
156 | double score; | |
157 | double high_score = 0; | |
aee3523a | 158 | const char *key = nullptr; |
eec27647 | 159 | char ntoabuf[MAX_IPSTRLEN]; |
63104e28 | 160 | |
2d5ac435 | 161 | if (SourceHashPeers().empty()) |
aee3523a | 162 | return nullptr; |
63104e28 | 163 | |
cb365059 EB |
164 | assert(ps); |
165 | HttpRequest *request = ps->request; | |
166 | ||
4dd643d5 | 167 | key = request->client_addr.toStr(ntoabuf, sizeof(ntoabuf)); |
63104e28 HN |
168 | |
169 | /* calculate hash key */ | |
f7e1d9ce | 170 | debugs(39, 2, "peerSourceHashSelectParent: Calculating hash for " << key); |
63104e28 | 171 | |
5db6bf73 | 172 | for (c = key; *c != 0; ++c) |
63104e28 HN |
173 | user_hash += ROTATE_LEFT(user_hash, 19) + *c; |
174 | ||
a3c6762c | 175 | /* select CachePeer */ |
2d5ac435 EB |
176 | for (const auto &tp: SourceHashPeers()) { |
177 | if (!tp) | |
178 | continue; // peer gone | |
179 | ||
f7e1d9ce | 180 | combined_hash = (user_hash ^ tp->sourcehash.hash); |
63104e28 HN |
181 | combined_hash += combined_hash * 0x62531965; |
182 | combined_hash = ROTATE_LEFT(combined_hash, 21); | |
f7e1d9ce | 183 | score = combined_hash * tp->sourcehash.load_multiplier; |
a555a85b | 184 | debugs(39, 3, *tp << " combined_hash " << combined_hash << |
63104e28 HN |
185 | " score " << std::setprecision(0) << score); |
186 | ||
2d5ac435 EB |
187 | if ((score > high_score) && peerHTTPOkay(tp.get(), ps)) { |
188 | p = tp.get(); | |
63104e28 HN |
189 | high_score = score; |
190 | } | |
191 | } | |
192 | ||
193 | if (p) | |
a555a85b | 194 | debugs(39, 2, "selected " << *p); |
63104e28 HN |
195 | |
196 | return p; | |
197 | } | |
198 | ||
199 | static void | |
f7e1d9ce | 200 | peerSourceHashCachemgr(StoreEntry * sentry) |
63104e28 | 201 | { |
63104e28 HN |
202 | int sumfetches = 0; |
203 | storeAppendPrintf(sentry, "%24s %10s %10s %10s %10s\n", | |
204 | "Hostname", | |
205 | "Hash", | |
206 | "Multiplier", | |
207 | "Factor", | |
208 | "Actual"); | |
209 | ||
2d5ac435 EB |
210 | for (const auto &p: SourceHashPeers()) { |
211 | if (!p) | |
212 | continue; | |
63104e28 | 213 | sumfetches += p->stats.fetches; |
2d5ac435 | 214 | } |
63104e28 | 215 | |
2d5ac435 EB |
216 | for (const auto &p: SourceHashPeers()) { |
217 | if (!p) | |
218 | continue; | |
63104e28 | 219 | storeAppendPrintf(sentry, "%24s %10x %10f %10f %10f\n", |
f7e1d9ce HN |
220 | p->name, p->sourcehash.hash, |
221 | p->sourcehash.load_multiplier, | |
222 | p->sourcehash.load_factor, | |
63104e28 HN |
223 | sumfetches ? (double) p->stats.fetches / sumfetches : -1.0); |
224 | } | |
225 | } | |
f53969cc | 226 |