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