peer_sourcehash.cc
Go to the documentation of this file.
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 Peer source hash based selection */
10
11#include "squid.h"
12#include "CachePeer.h"
13#include "CachePeers.h"
14#include "HttpRequest.h"
15#include "mgr/Registration.h"
16#include "neighbors.h"
17#include "peer_sourcehash.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
27static auto &
29{
30 static const auto hashPeers = new SelectedCachePeers();
31 return *hashPeers;
32}
33
36
37static int
38peerSortWeight(const void *a, const void *b)
39{
40 const CachePeer *const *p1 = (const CachePeer *const *)a;
41 const CachePeer *const *p2 = (const CachePeer *const *)b;
42 return (*p1)->weight - (*p2)->weight;
43}
44
45void
47{
48 int W = 0;
49 double P_last, X_last, Xn;
50 char *t;
51 /* Clean up */
52
53 SourceHashPeers().clear();
54 /* find out which peers we have */
55
56 RawCachePeers rawSourceHashPeers;
57 for (const auto &p: CurrentCachePeers()) {
58 const auto peer = p.get();
59
60 if (!p->options.sourcehash)
61 continue;
62
63 assert(p->type == PEER_PARENT);
64
65 if (p->weight == 0)
66 continue;
67
68 rawSourceHashPeers.push_back(peer);
69
70 W += p->weight;
71 }
72
74
75 if (rawSourceHashPeers.empty())
76 return;
77
78 /* calculate hashes and load factors */
79 for (const auto &p: rawSourceHashPeers) {
80 /* calculate this peers hash */
81 p->sourcehash.hash = 0;
82
83 for (t = p->name; *t != 0; ++t)
84 p->sourcehash.hash += ROTATE_LEFT(p->sourcehash.hash, 19) + (unsigned int) *t;
85
86 p->sourcehash.hash += p->sourcehash.hash * 0x62531965;
87
88 p->sourcehash.hash = ROTATE_LEFT(p->sourcehash.hash, 21);
89
90 /* and load factor */
91 p->sourcehash.load_factor = ((double) p->weight) / (double) W;
92
93 if (floor(p->sourcehash.load_factor * 1000.0) == 0.0)
94 p->sourcehash.load_factor = 0.0;
95 }
96
97 /* Sort our list on weight */
98 qsort(rawSourceHashPeers.data(), rawSourceHashPeers.size(), sizeof(decltype(rawSourceHashPeers)::value_type), peerSortWeight);
99
100 /* Calculate the load factor multipliers X_k
101 *
102 * X_1 = pow ((K*p_1), (1/K))
103 * X_k = ([K-k+1] * [P_k - P_{k-1}])/(X_1 * X_2 * ... * X_{k-1})
104 * X_k += pow ((X_{k-1}, {K-k+1})
105 * X_k = pow (X_k, {1/(K-k+1)})
106 * simplified to have X_1 part of the loop
107 */
108 const auto K = rawSourceHashPeers.size();
109
110 P_last = 0.0; /* Empty P_0 */
111
112 Xn = 1.0; /* Empty starting point of X_1 * X_2 * ... * X_{x-1} */
113
114 X_last = 0.0; /* Empty X_0, nullifies the first pow statement */
115
116 for (size_t k = 1; k <= K; ++k) {
117 double Kk1 = (double) (K - k + 1);
118 const auto p = rawSourceHashPeers[k - 1];
119 p->sourcehash.load_multiplier = (Kk1 * (p->sourcehash.load_factor - P_last)) / Xn;
120 p->sourcehash.load_multiplier += pow(X_last, Kk1);
121 p->sourcehash.load_multiplier = pow(p->sourcehash.load_multiplier, 1.0 / Kk1);
122 Xn *= p->sourcehash.load_multiplier;
123 X_last = p->sourcehash.load_multiplier;
124 P_last = p->sourcehash.load_factor;
125 }
126
127 SourceHashPeers().assign(rawSourceHashPeers.begin(), rawSourceHashPeers.end());
128}
129
130static void
132{
133 Mgr::RegisterAction("sourcehash", "peer sourcehash information",
135}
136
137CachePeer *
139{
140 const char *c;
141 CachePeer *p = nullptr;
142 unsigned int user_hash = 0;
143 unsigned int combined_hash;
144 double score;
145 double high_score = 0;
146 const char *key = nullptr;
147 char ntoabuf[MAX_IPSTRLEN];
148
149 if (SourceHashPeers().empty())
150 return nullptr;
151
152 assert(ps);
153 HttpRequest *request = ps->request;
154
155 key = request->client_addr.toStr(ntoabuf, sizeof(ntoabuf));
156
157 /* calculate hash key */
158 debugs(39, 2, "peerSourceHashSelectParent: Calculating hash for " << key);
159
160 for (c = key; *c != 0; ++c)
161 user_hash += ROTATE_LEFT(user_hash, 19) + *c;
162
163 /* select CachePeer */
164 for (const auto &tp: SourceHashPeers()) {
165 if (!tp)
166 continue; // peer gone
167
168 combined_hash = (user_hash ^ tp->sourcehash.hash);
169 combined_hash += combined_hash * 0x62531965;
170 combined_hash = ROTATE_LEFT(combined_hash, 21);
171 score = combined_hash * tp->sourcehash.load_multiplier;
172 debugs(39, 3, *tp << " combined_hash " << combined_hash <<
173 " score " << std::setprecision(0) << score);
174
175 if ((score > high_score) && peerHTTPOkay(tp.get(), ps)) {
176 p = tp.get();
177 high_score = score;
178 }
179 }
180
181 if (p)
182 debugs(39, 2, "selected " << *p);
183
184 return p;
185}
186
187static void
189{
190 int sumfetches = 0;
191 storeAppendPrintf(sentry, "%24s %10s %10s %10s %10s\n",
192 "Hostname",
193 "Hash",
194 "Multiplier",
195 "Factor",
196 "Actual");
197
198 for (const auto &p: SourceHashPeers()) {
199 if (!p)
200 continue;
201 sumfetches += p->stats.fetches;
202 }
203
204 for (const auto &p: SourceHashPeers()) {
205 if (!p)
206 continue;
207 storeAppendPrintf(sentry, "%24s %10x %10f %10f %10f\n",
208 p->name, p->sourcehash.hash,
209 p->sourcehash.load_multiplier,
210 p->sourcehash.load_factor,
211 sumfetches ? (double) p->stats.fetches / sumfetches : -1.0);
212 }
213}
214
const CachePeers & CurrentCachePeers()
Definition: CachePeers.cc:41
std::vector< CachePeer *, PoolingAllocator< CachePeer * > > RawCachePeers
Temporary, local storage of raw pointers to zero or more Config.peers.
Definition: CachePeers.h:66
std::vector< CbcPointer< CachePeer >, PoolingAllocator< CbcPointer< CachePeer > > > SelectedCachePeers
Definition: CachePeers.h:63
#define assert(EX)
Definition: assert.h:17
int weight
Definition: CachePeer.h:151
Ip::Address client_addr
Definition: HttpRequest.h:149
char * toStr(char *buf, const unsigned int blen, int force=AF_UNSPEC) const
Definition: Address.cc:792
HttpRequest * request
#define debugs(SECTION, LEVEL, CONTENT)
Definition: Stream.h:194
@ PEER_PARENT
Definition: enums.h:30
#define MAX_IPSTRLEN
Length of buffer that needs to be allocated to old a null-terminated IP-string.
Definition: forward.h:25
void OBJH(StoreEntry *)
Definition: forward.h:44
void RegisterAction(char const *action, char const *desc, OBJH *handler, int pw_req_flag, int atomic)
Definition: Registration.cc:16
int peerHTTPOkay(const CachePeer *p, PeerSelector *ps)
Definition: neighbors.cc:257
static void peerSourceHashRegisterWithCacheManager(void)
static OBJH peerSourceHashCachemgr
void peerSourceHashInit(void)
static auto & SourceHashPeers()
sourcehash peers ordered by their sourcehash weight
#define ROTATE_LEFT(x, n)
CachePeer * peerSourceHashSelectParent(PeerSelector *ps)
static int peerSortWeight(const void *a, const void *b)
void storeAppendPrintf(StoreEntry *e, const char *fmt,...)
Definition: store.cc:841
void EVH void double
Definition: stub_event.cc:16
int unsigned int
Definition: stub_fd.cc:19

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors