]>
Commit | Line | Data |
---|---|---|
63104e28 | 1 | /* |
4ac4a490 | 2 | * Copyright (C) 1996-2017 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" |
a011edee | 12 | #include "CachePeer.h" |
f4a21650 | 13 | #include "HttpRequest.h" |
8822ebee | 14 | #include "mgr/Registration.h" |
f0ba2534 | 15 | #include "neighbors.h" |
4d5904f7 | 16 | #include "SquidConfig.h" |
582c2af2 FC |
17 | #include "Store.h" |
18 | ||
074d6a40 | 19 | #include <cmath> |
63104e28 HN |
20 | |
21 | #define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n)))) | |
22 | ||
f7e1d9ce | 23 | static int n_sourcehash_peers = 0; |
a3c6762c | 24 | static CachePeer **sourcehash_peers = NULL; |
f7e1d9ce | 25 | static OBJH peerSourceHashCachemgr; |
6b661f2e | 26 | static void peerSourceHashRegisterWithCacheManager(void); |
63104e28 HN |
27 | |
28 | static int | |
29 | peerSortWeight(const void *a, const void *b) | |
30 | { | |
a3c6762c FC |
31 | const CachePeer *const *p1 = (const CachePeer *const *)a; |
32 | const CachePeer *const *p2 = (const CachePeer *const *)b; | |
63104e28 HN |
33 | return (*p1)->weight - (*p2)->weight; |
34 | } | |
35 | ||
36 | void | |
f7e1d9ce | 37 | peerSourceHashInit(void) |
63104e28 HN |
38 | { |
39 | int W = 0; | |
40 | int K; | |
41 | int k; | |
42 | double P_last, X_last, Xn; | |
a3c6762c FC |
43 | CachePeer *p; |
44 | CachePeer **P; | |
63104e28 HN |
45 | char *t; |
46 | /* Clean up */ | |
47 | ||
5db6bf73 | 48 | for (k = 0; k < n_sourcehash_peers; ++k) { |
f7e1d9ce | 49 | cbdataReferenceDone(sourcehash_peers[k]); |
63104e28 HN |
50 | } |
51 | ||
f7e1d9ce HN |
52 | safe_free(sourcehash_peers); |
53 | n_sourcehash_peers = 0; | |
63104e28 HN |
54 | /* find out which peers we have */ |
55 | ||
56 | for (p = Config.peers; p; p = p->next) { | |
f7e1d9ce | 57 | if (!p->options.sourcehash) |
63104e28 HN |
58 | continue; |
59 | ||
60 | assert(p->type == PEER_PARENT); | |
61 | ||
62 | if (p->weight == 0) | |
63 | continue; | |
64 | ||
5db6bf73 | 65 | ++n_sourcehash_peers; |
63104e28 HN |
66 | |
67 | W += p->weight; | |
68 | } | |
69 | ||
6b661f2e FC |
70 | peerSourceHashRegisterWithCacheManager(); |
71 | ||
f7e1d9ce | 72 | if (n_sourcehash_peers == 0) |
63104e28 HN |
73 | return; |
74 | ||
a3c6762c | 75 | sourcehash_peers = (CachePeer **)xcalloc(n_sourcehash_peers, sizeof(*sourcehash_peers)); |
63104e28 HN |
76 | |
77 | /* Build a list of the found peers and calculate hashes and load factors */ | |
f7e1d9ce HN |
78 | for (P = sourcehash_peers, p = Config.peers; p; p = p->next) { |
79 | if (!p->options.sourcehash) | |
63104e28 HN |
80 | continue; |
81 | ||
82 | if (p->weight == 0) | |
83 | continue; | |
84 | ||
85 | /* calculate this peers hash */ | |
f7e1d9ce | 86 | p->sourcehash.hash = 0; |
63104e28 | 87 | |
5db6bf73 | 88 | for (t = p->name; *t != 0; ++t) |
f7e1d9ce | 89 | p->sourcehash.hash += ROTATE_LEFT(p->sourcehash.hash, 19) + (unsigned int) *t; |
63104e28 | 90 | |
f7e1d9ce | 91 | p->sourcehash.hash += p->sourcehash.hash * 0x62531965; |
63104e28 | 92 | |
f7e1d9ce | 93 | p->sourcehash.hash = ROTATE_LEFT(p->sourcehash.hash, 21); |
63104e28 HN |
94 | |
95 | /* and load factor */ | |
f7e1d9ce | 96 | p->sourcehash.load_factor = ((double) p->weight) / (double) W; |
63104e28 | 97 | |
f7e1d9ce HN |
98 | if (floor(p->sourcehash.load_factor * 1000.0) == 0.0) |
99 | p->sourcehash.load_factor = 0.0; | |
63104e28 HN |
100 | |
101 | /* add it to our list of peers */ | |
102 | *P++ = cbdataReference(p); | |
103 | } | |
104 | ||
105 | /* Sort our list on weight */ | |
f7e1d9ce | 106 | qsort(sourcehash_peers, n_sourcehash_peers, sizeof(*sourcehash_peers), peerSortWeight); |
63104e28 HN |
107 | |
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 | |
115 | */ | |
f7e1d9ce | 116 | K = n_sourcehash_peers; |
63104e28 | 117 | |
f53969cc | 118 | P_last = 0.0; /* Empty P_0 */ |
63104e28 | 119 | |
f53969cc | 120 | Xn = 1.0; /* Empty starting point of X_1 * X_2 * ... * X_{x-1} */ |
63104e28 | 121 | |
f53969cc | 122 | X_last = 0.0; /* Empty X_0, nullifies the first pow statement */ |
63104e28 | 123 | |
5db6bf73 | 124 | for (k = 1; k <= K; ++k) { |
63104e28 | 125 | double Kk1 = (double) (K - k + 1); |
f7e1d9ce HN |
126 | p = sourcehash_peers[k - 1]; |
127 | p->sourcehash.load_multiplier = (Kk1 * (p->sourcehash.load_factor - P_last)) / Xn; | |
128 | p->sourcehash.load_multiplier += pow(X_last, Kk1); | |
129 | p->sourcehash.load_multiplier = pow(p->sourcehash.load_multiplier, 1.0 / Kk1); | |
130 | Xn *= p->sourcehash.load_multiplier; | |
131 | X_last = p->sourcehash.load_multiplier; | |
132 | P_last = p->sourcehash.load_factor; | |
63104e28 HN |
133 | } |
134 | } | |
135 | ||
6b661f2e FC |
136 | static void |
137 | peerSourceHashRegisterWithCacheManager(void) | |
63104e28 | 138 | { |
8822ebee | 139 | Mgr::RegisterAction("sourcehash", "peer sourcehash information", |
d9fc6862 | 140 | peerSourceHashCachemgr, 0, 1); |
63104e28 HN |
141 | } |
142 | ||
a3c6762c | 143 | CachePeer * |
f7e1d9ce | 144 | peerSourceHashSelectParent(HttpRequest * request) |
63104e28 HN |
145 | { |
146 | int k; | |
147 | const char *c; | |
a3c6762c FC |
148 | CachePeer *p = NULL; |
149 | CachePeer *tp; | |
63104e28 HN |
150 | unsigned int user_hash = 0; |
151 | unsigned int combined_hash; | |
152 | double score; | |
153 | double high_score = 0; | |
154 | const char *key = NULL; | |
eec27647 | 155 | char ntoabuf[MAX_IPSTRLEN]; |
63104e28 | 156 | |
f7e1d9ce | 157 | if (n_sourcehash_peers == 0) |
63104e28 HN |
158 | return NULL; |
159 | ||
4dd643d5 | 160 | key = request->client_addr.toStr(ntoabuf, sizeof(ntoabuf)); |
63104e28 HN |
161 | |
162 | /* calculate hash key */ | |
f7e1d9ce | 163 | debugs(39, 2, "peerSourceHashSelectParent: Calculating hash for " << key); |
63104e28 | 164 | |
5db6bf73 | 165 | for (c = key; *c != 0; ++c) |
63104e28 HN |
166 | user_hash += ROTATE_LEFT(user_hash, 19) + *c; |
167 | ||
a3c6762c | 168 | /* select CachePeer */ |
5db6bf73 | 169 | for (k = 0; k < n_sourcehash_peers; ++k) { |
f7e1d9ce HN |
170 | tp = sourcehash_peers[k]; |
171 | combined_hash = (user_hash ^ tp->sourcehash.hash); | |
63104e28 HN |
172 | combined_hash += combined_hash * 0x62531965; |
173 | combined_hash = ROTATE_LEFT(combined_hash, 21); | |
f7e1d9ce | 174 | score = combined_hash * tp->sourcehash.load_multiplier; |
26ac0430 | 175 | debugs(39, 3, "peerSourceHashSelectParent: " << tp->name << " combined_hash " << combined_hash << |
63104e28 HN |
176 | " score " << std::setprecision(0) << score); |
177 | ||
178 | if ((score > high_score) && peerHTTPOkay(tp, request)) { | |
179 | p = tp; | |
180 | high_score = score; | |
181 | } | |
182 | } | |
183 | ||
184 | if (p) | |
f7e1d9ce | 185 | debugs(39, 2, "peerSourceHashSelectParent: selected " << p->name); |
63104e28 HN |
186 | |
187 | return p; | |
188 | } | |
189 | ||
190 | static void | |
f7e1d9ce | 191 | peerSourceHashCachemgr(StoreEntry * sentry) |
63104e28 | 192 | { |
a3c6762c | 193 | CachePeer *p; |
63104e28 HN |
194 | int sumfetches = 0; |
195 | storeAppendPrintf(sentry, "%24s %10s %10s %10s %10s\n", | |
196 | "Hostname", | |
197 | "Hash", | |
198 | "Multiplier", | |
199 | "Factor", | |
200 | "Actual"); | |
201 | ||
202 | for (p = Config.peers; p; p = p->next) | |
203 | sumfetches += p->stats.fetches; | |
204 | ||
205 | for (p = Config.peers; p; p = p->next) { | |
206 | storeAppendPrintf(sentry, "%24s %10x %10f %10f %10f\n", | |
f7e1d9ce HN |
207 | p->name, p->sourcehash.hash, |
208 | p->sourcehash.load_multiplier, | |
209 | p->sourcehash.load_factor, | |
63104e28 HN |
210 | sumfetches ? (double) p->stats.fetches / sumfetches : -1.0); |
211 | } | |
212 | } | |
f53969cc | 213 |