]>
Commit | Line | Data |
---|---|---|
afd88fbe | 1 | /* |
b8ae064d | 2 | * Copyright (C) 1996-2023 The Squid Software Foundation and contributors |
e25c139f | 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. | |
0cdcddb9 | 7 | */ |
afd88fbe | 8 | |
bbc27441 AJ |
9 | /* DEBUG: section 39 Cache Array Routing Protocol */ |
10 | ||
582c2af2 | 11 | #include "squid.h" |
8c469f12 | 12 | #include "base/RunnersRegistry.h" |
a011edee | 13 | #include "CachePeer.h" |
e7959b56 | 14 | #include "CachePeers.h" |
8b082ed9 | 15 | #include "carp.h" |
de03b596 | 16 | #include "HttpRequest.h" |
8822ebee | 17 | #include "mgr/Registration.h" |
f0ba2534 | 18 | #include "neighbors.h" |
cb365059 | 19 | #include "PeerSelectState.h" |
4d5904f7 | 20 | #include "SquidConfig.h" |
e6ccf245 | 21 | #include "Store.h" |
afd88fbe | 22 | |
074d6a40 | 23 | #include <cmath> |
582c2af2 | 24 | |
b3995439 | 25 | #define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n)))) |
26 | ||
e7959b56 | 27 | /// CARP cache_peers ordered by their CARP weight |
2d5ac435 EB |
28 | static auto & |
29 | CarpPeers() | |
30 | { | |
31 | static const auto carpPeers = new SelectedCachePeers(); | |
32 | return *carpPeers; | |
33 | } | |
e7959b56 | 34 | |
8ee9b49f | 35 | static OBJH carpCachemgr; |
36 | ||
b3995439 | 37 | static int |
38 | peerSortWeight(const void *a, const void *b) | |
39 | { | |
a3c6762c FC |
40 | const CachePeer *const *p1 = (const CachePeer *const *)a; |
41 | const CachePeer *const *p2 = (const CachePeer *const *)b; | |
b3995439 | 42 | return (*p1)->weight - (*p2)->weight; |
43 | } | |
44 | ||
5f5e883f FC |
45 | static void |
46 | carpRegisterWithCacheManager(void) | |
47 | { | |
8822ebee | 48 | Mgr::RegisterAction("carp", "CARP information", carpCachemgr, 0, 1); |
5f5e883f FC |
49 | } |
50 | ||
8c469f12 | 51 | static void |
afd88fbe | 52 | carpInit(void) |
53 | { | |
b3995439 | 54 | int W = 0; |
b3995439 | 55 | double P_last, X_last, Xn; |
b3995439 | 56 | char *t; |
57 | /* Clean up */ | |
62e76326 | 58 | |
2d5ac435 | 59 | CarpPeers().clear(); |
8cb183ec FC |
60 | |
61 | /* initialize cache manager before we have a chance to leave the execution path */ | |
62 | carpRegisterWithCacheManager(); | |
63 | ||
b3995439 | 64 | /* find out which peers we have */ |
62e76326 | 65 | |
e7959b56 | 66 | RawCachePeers rawCarpPeers; |
2e24d0bf EB |
67 | for (const auto &peer: CurrentCachePeers()) { |
68 | const auto p = peer.get(); | |
69 | ||
62e76326 | 70 | if (!p->options.carp) |
71 | continue; | |
72 | ||
73 | assert(p->type == PEER_PARENT); | |
74 | ||
75 | if (p->weight == 0) | |
76 | continue; | |
77 | ||
e7959b56 | 78 | rawCarpPeers.push_back(p); |
62e76326 | 79 | |
80 | W += p->weight; | |
afd88fbe | 81 | } |
62e76326 | 82 | |
e7959b56 | 83 | if (rawCarpPeers.empty()) |
62e76326 | 84 | return; |
85 | ||
e7959b56 EB |
86 | /* calculate hashes and load factors */ |
87 | for (const auto p: rawCarpPeers) { | |
62e76326 | 88 | /* calculate this peers hash */ |
89 | p->carp.hash = 0; | |
90 | ||
d7ae3534 | 91 | for (t = p->name; *t != 0; ++t) |
62e76326 | 92 | p->carp.hash += ROTATE_LEFT(p->carp.hash, 19) + (unsigned int) *t; |
93 | ||
94 | p->carp.hash += p->carp.hash * 0x62531965; | |
95 | ||
96 | p->carp.hash = ROTATE_LEFT(p->carp.hash, 21); | |
97 | ||
98 | /* and load factor */ | |
99 | p->carp.load_factor = ((double) p->weight) / (double) W; | |
100 | ||
101 | if (floor(p->carp.load_factor * 1000.0) == 0.0) | |
102 | p->carp.load_factor = 0.0; | |
67766c17 | 103 | } |
62e76326 | 104 | |
b3995439 | 105 | /* Sort our list on weight */ |
e7959b56 | 106 | qsort(rawCarpPeers.data(), rawCarpPeers.size(), sizeof(decltype(rawCarpPeers)::value_type), peerSortWeight); |
62e76326 | 107 | |
b3995439 | 108 | /* Calculate the load factor multipliers X_k |
109 | * | |
110 | * X_1 = pow ((K*p_1), (1/K)) | |
111 | * X_k = ([K-k+1] * [P_k - P_{k-1}])/(X_1 * X_2 * ... * X_{k-1}) | |
112 | * X_k += pow ((X_{k-1}, {K-k+1}) | |
113 | * X_k = pow (X_k, {1/(K-k+1)}) | |
114 | * simplified to have X_1 part of the loop | |
afd88fbe | 115 | */ |
e7959b56 | 116 | const auto K = rawCarpPeers.size(); |
62e76326 | 117 | |
f53969cc | 118 | P_last = 0.0; /* Empty P_0 */ |
62e76326 | 119 | |
f53969cc | 120 | Xn = 1.0; /* Empty starting point of X_1 * X_2 * ... * X_{x-1} */ |
62e76326 | 121 | |
f53969cc | 122 | X_last = 0.0; /* Empty X_0, nullifies the first pow statement */ |
62e76326 | 123 | |
e7959b56 | 124 | for (size_t k = 1; k <= K; ++k) { |
62e76326 | 125 | double Kk1 = (double) (K - k + 1); |
e7959b56 | 126 | const auto p = rawCarpPeers[k - 1]; |
62e76326 | 127 | p->carp.load_multiplier = (Kk1 * (p->carp.load_factor - P_last)) / Xn; |
128 | p->carp.load_multiplier += pow(X_last, Kk1); | |
129 | p->carp.load_multiplier = pow(p->carp.load_multiplier, 1.0 / Kk1); | |
130 | Xn *= p->carp.load_multiplier; | |
131 | X_last = p->carp.load_multiplier; | |
132 | P_last = p->carp.load_factor; | |
afd88fbe | 133 | } |
e7959b56 | 134 | |
2d5ac435 | 135 | CarpPeers().assign(rawCarpPeers.begin(), rawCarpPeers.end()); |
62ee09ca | 136 | } |
62e76326 | 137 | |
8c469f12 AR |
138 | /// reacts to RegisteredRunner events relevant to this module |
139 | class CarpRr: public RegisteredRunner | |
140 | { | |
141 | public: | |
142 | /* RegisteredRunner API */ | |
143 | void useConfig() override { carpInit(); } | |
144 | void syncConfig() override { carpInit(); } | |
145 | }; | |
146 | ||
147 | DefineRunnerRegistrator(CarpRr); | |
148 | ||
a3c6762c | 149 | CachePeer * |
cb365059 | 150 | carpSelectParent(PeerSelector *ps) |
afd88fbe | 151 | { |
cb365059 EB |
152 | assert(ps); |
153 | HttpRequest *request = ps->request; | |
154 | ||
aee3523a | 155 | CachePeer *p = nullptr; |
b3995439 | 156 | unsigned int user_hash = 0; |
157 | unsigned int combined_hash; | |
158 | double score; | |
159 | double high_score = 0; | |
b3995439 | 160 | |
2d5ac435 | 161 | if (CarpPeers().empty()) |
aee3523a | 162 | return nullptr; |
b3995439 | 163 | |
b3995439 | 164 | /* calculate hash key */ |
851feda6 | 165 | debugs(39, 2, "carpSelectParent: Calculating hash for " << request->effectiveRequestUri()); |
62e76326 | 166 | |
a3c6762c | 167 | /* select CachePeer */ |
2d5ac435 | 168 | for (const auto &tp: CarpPeers()) { |
e7959b56 EB |
169 | if (!tp) |
170 | continue; // peer gone | |
171 | ||
2128aa19 | 172 | SBuf key; |
de03b596 | 173 | if (tp->options.carp_key.set) { |
851feda6 AJ |
174 | // this code follows URI syntax pattern. |
175 | // corner cases should use the full effective request URI | |
de03b596 | 176 | if (tp->options.carp_key.scheme) { |
d31d59d8 | 177 | key.append(request->url.getScheme().image()); |
2128aa19 | 178 | if (key.length()) //if the scheme is not empty |
de03b596 FC |
179 | key.append("://"); |
180 | } | |
181 | if (tp->options.carp_key.host) { | |
5c51bffb | 182 | key.append(request->url.host()); |
de03b596 FC |
183 | } |
184 | if (tp->options.carp_key.port) { | |
380b09ae | 185 | key.appendf(":%hu", request->url.port().value_or(0)); |
de03b596 FC |
186 | } |
187 | if (tp->options.carp_key.path) { | |
51b5dcf5 AJ |
188 | // XXX: fix when path and query are separate |
189 | key.append(request->url.path().substr(0,request->url.path().find('?'))); // 0..N | |
de03b596 FC |
190 | } |
191 | if (tp->options.carp_key.params) { | |
51b5dcf5 AJ |
192 | // XXX: fix when path and query are separate |
193 | SBuf::size_type pos; | |
194 | if ((pos=request->url.path().find('?')) != SBuf::npos) | |
195 | key.append(request->url.path().substr(pos)); // N..npos | |
de03b596 | 196 | } |
96f6f33b | 197 | } |
de03b596 FC |
198 | // if the url-based key is empty, e.g. because the user is |
199 | // asking to balance on the path but the request doesn't supply any, | |
851feda6 | 200 | // then fall back to the effective request URI |
de03b596 | 201 | |
2128aa19 | 202 | if (key.isEmpty()) |
851feda6 | 203 | key=request->effectiveRequestUri(); |
de03b596 | 204 | |
2128aa19 | 205 | for (const char *c = key.rawContent(), *e=key.rawContent()+key.length(); c < e; ++c) |
de03b596 | 206 | user_hash += ROTATE_LEFT(user_hash, 19) + *c; |
62e76326 | 207 | combined_hash = (user_hash ^ tp->carp.hash); |
208 | combined_hash += combined_hash * 0x62531965; | |
209 | combined_hash = ROTATE_LEFT(combined_hash, 21); | |
210 | score = combined_hash * tp->carp.load_multiplier; | |
a555a85b | 211 | debugs(39, 3, *tp << " key=" << key << " combined_hash=" << combined_hash << |
de03b596 | 212 | " score=" << std::setprecision(0) << score); |
62e76326 | 213 | |
e7959b56 EB |
214 | if ((score > high_score) && peerHTTPOkay(tp.get(), ps)) { |
215 | p = tp.get(); | |
62e76326 | 216 | high_score = score; |
217 | } | |
afd88fbe | 218 | } |
62e76326 | 219 | |
afd88fbe | 220 | if (p) |
a555a85b | 221 | debugs(39, 2, "selected " << *p); |
62e76326 | 222 | |
afd88fbe | 223 | return p; |
224 | } | |
8ee9b49f | 225 | |
226 | static void | |
227 | carpCachemgr(StoreEntry * sentry) | |
228 | { | |
8ee9b49f | 229 | int sumfetches = 0; |
230 | storeAppendPrintf(sentry, "%24s %10s %10s %10s %10s\n", | |
62e76326 | 231 | "Hostname", |
232 | "Hash", | |
233 | "Multiplier", | |
234 | "Factor", | |
235 | "Actual"); | |
236 | ||
2d5ac435 | 237 | for (const auto &p: CarpPeers()) { |
e7959b56 EB |
238 | if (!p) |
239 | continue; | |
62e76326 | 240 | sumfetches += p->stats.fetches; |
e7959b56 | 241 | } |
62e76326 | 242 | |
2d5ac435 | 243 | for (const auto &p: CarpPeers()) { |
e7959b56 EB |
244 | if (!p) |
245 | continue; | |
62e76326 | 246 | storeAppendPrintf(sentry, "%24s %10x %10f %10f %10f\n", |
d4140027 | 247 | p->name, p->carp.hash, |
62e76326 | 248 | p->carp.load_multiplier, |
249 | p->carp.load_factor, | |
250 | sumfetches ? (double) p->stats.fetches / sumfetches : -1.0); | |
8ee9b49f | 251 | } |
8ee9b49f | 252 | } |
f53969cc | 253 |