]>
Commit | Line | Data |
---|---|---|
b6e26895 RG |
1 | /* |
2 | * This file is part of PowerDNS or dnsdist. | |
3 | * Copyright -- PowerDNS.COM B.V. and its contributors | |
4 | * | |
5 | * This program is free software; you can redistribute it and/or modify | |
6 | * it under the terms of version 2 of the GNU General Public License as | |
7 | * published by the Free Software Foundation. | |
8 | * | |
9 | * In addition, for the avoidance of any doubt, permission is granted to | |
10 | * link this program with OpenSSL and to (re)distribute the binaries | |
11 | * produced as the result of such linking. | |
12 | * | |
13 | * This program is distributed in the hope that it will be useful, | |
14 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
15 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
16 | * GNU General Public License for more details. | |
17 | * | |
18 | * You should have received a copy of the GNU General Public License | |
19 | * along with this program; if not, write to the Free Software | |
20 | * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. | |
21 | */ | |
22 | ||
23 | #include "dnsdist.hh" | |
24 | #include "dnsdist-lbpolicies.hh" | |
a9599e73 | 25 | #include "dnsdist-lua-ffi.hh" |
b6e26895 RG |
26 | #include "dolog.hh" |
27 | ||
28 | GlobalStateHolder<ServerPolicy> g_policy; | |
29 | bool g_roundrobinFailOnNoServer{false}; | |
30 | ||
31 | // get server with least outstanding queries, and within those, with the lowest order, and within those: the fastest | |
32 | shared_ptr<DownstreamState> leastOutstanding(const ServerPolicy::NumberedServerVector& servers, const DNSQuestion* dq) | |
33 | { | |
34 | if (servers.size() == 1 && servers[0].second->isUp()) { | |
35 | return servers[0].second; | |
36 | } | |
37 | ||
0d122397 | 38 | vector<pair<tuple<int,int,double>, size_t>> poss; |
b6e26895 RG |
39 | /* so you might wonder, why do we go through this trouble? The data on which we sort could change during the sort, |
40 | which would suck royally and could even lead to crashes. So first we snapshot on what we sort, and then we sort */ | |
41 | poss.reserve(servers.size()); | |
0d122397 RG |
42 | size_t position = 0; |
43 | for(const auto& d : servers) { | |
b6e26895 | 44 | if(d.second->isUp()) { |
0d122397 | 45 | poss.emplace_back(make_tuple(d.second->outstanding.load(), d.second->order, d.second->latencyUsec), position); |
b6e26895 | 46 | } |
0d122397 | 47 | ++position; |
b6e26895 | 48 | } |
0d122397 RG |
49 | |
50 | if (poss.empty()) { | |
b6e26895 | 51 | return shared_ptr<DownstreamState>(); |
0d122397 RG |
52 | } |
53 | ||
b6e26895 | 54 | nth_element(poss.begin(), poss.begin(), poss.end(), [](const decltype(poss)::value_type& a, const decltype(poss)::value_type& b) { return a.first < b.first; }); |
0d122397 | 55 | return servers.at(poss.begin()->second).second; |
b6e26895 RG |
56 | } |
57 | ||
58 | shared_ptr<DownstreamState> firstAvailable(const ServerPolicy::NumberedServerVector& servers, const DNSQuestion* dq) | |
59 | { | |
60 | for(auto& d : servers) { | |
61 | if(d.second->isUp() && d.second->qps.check()) | |
62 | return d.second; | |
63 | } | |
64 | return leastOutstanding(servers, dq); | |
65 | } | |
66 | ||
439de524 RG |
67 | double g_weightedBalancingFactor = 0; |
68 | ||
cc958b79 | 69 | static shared_ptr<DownstreamState> valrandom(unsigned int val, const ServerPolicy::NumberedServerVector& servers) |
b6e26895 | 70 | { |
cc958b79 RG |
71 | vector<pair<int, size_t>> poss; |
72 | poss.reserve(servers.size()); | |
b6e26895 RG |
73 | int sum = 0; |
74 | int max = std::numeric_limits<int>::max(); | |
439de524 | 75 | double targetLoad = std::numeric_limits<double>::max(); |
b6e26895 | 76 | |
439de524 RG |
77 | if (g_weightedBalancingFactor > 0) { |
78 | /* we start with one, representing the query we are currently handling */ | |
79 | double currentLoad = 1; | |
80 | size_t totalWeight = 0; | |
81 | for (const auto& pair : servers) { | |
82 | if (pair.second->isUp()) { | |
83 | currentLoad += pair.second->outstanding; | |
84 | totalWeight += pair.second->weight; | |
85 | } | |
86 | } | |
87 | ||
88 | if (totalWeight > 0) { | |
89 | targetLoad = (currentLoad / totalWeight) * g_weightedBalancingFactor; | |
90 | } | |
91 | } | |
92 | ||
93 | for (const auto& d : servers) { // w=1, w=10 -> 1, 11 | |
94 | if (d.second->isUp() && (g_weightedBalancingFactor == 0 || (d.second->outstanding <= (targetLoad * d.second->weight)))) { | |
b6e26895 | 95 | // Don't overflow sum when adding high weights |
439de524 | 96 | if (d.second->weight > max - sum) { |
b6e26895 RG |
97 | sum = max; |
98 | } else { | |
99 | sum += d.second->weight; | |
100 | } | |
101 | ||
cc958b79 | 102 | poss.emplace_back(sum, d.first); |
b6e26895 RG |
103 | } |
104 | } | |
105 | ||
106 | // Catch poss & sum are empty to avoid SIGFPE | |
cc958b79 | 107 | if (poss.empty()) { |
b6e26895 | 108 | return shared_ptr<DownstreamState>(); |
cc958b79 | 109 | } |
b6e26895 RG |
110 | |
111 | int r = val % sum; | |
112 | auto p = upper_bound(poss.begin(), poss.end(),r, [](int r_, const decltype(poss)::value_type& a) { return r_ < a.first;}); | |
cc958b79 | 113 | if (p == poss.end()) { |
b6e26895 | 114 | return shared_ptr<DownstreamState>(); |
cc958b79 RG |
115 | } |
116 | ||
117 | return servers.at(p->second - 1).second; | |
b6e26895 RG |
118 | } |
119 | ||
120 | shared_ptr<DownstreamState> wrandom(const ServerPolicy::NumberedServerVector& servers, const DNSQuestion* dq) | |
121 | { | |
cc958b79 | 122 | return valrandom(random(), servers); |
b6e26895 RG |
123 | } |
124 | ||
125 | uint32_t g_hashperturb; | |
126 | double g_consistentHashBalancingFactor = 0; | |
cc958b79 RG |
127 | |
128 | shared_ptr<DownstreamState> whashedFromHash(const ServerPolicy::NumberedServerVector& servers, size_t hash) | |
129 | { | |
130 | return valrandom(hash, servers); | |
131 | } | |
132 | ||
b6e26895 RG |
133 | shared_ptr<DownstreamState> whashed(const ServerPolicy::NumberedServerVector& servers, const DNSQuestion* dq) |
134 | { | |
cc958b79 | 135 | return whashedFromHash(servers, dq->qname->hash(g_hashperturb)); |
b6e26895 RG |
136 | } |
137 | ||
cc958b79 | 138 | shared_ptr<DownstreamState> chashedFromHash(const ServerPolicy::NumberedServerVector& servers, size_t qhash) |
b6e26895 | 139 | { |
b6e26895 RG |
140 | unsigned int sel = std::numeric_limits<unsigned int>::max(); |
141 | unsigned int min = std::numeric_limits<unsigned int>::max(); | |
142 | shared_ptr<DownstreamState> ret = nullptr, first = nullptr; | |
143 | ||
144 | double targetLoad = std::numeric_limits<double>::max(); | |
145 | if (g_consistentHashBalancingFactor > 0) { | |
146 | /* we start with one, representing the query we are currently handling */ | |
147 | double currentLoad = 1; | |
439de524 | 148 | size_t totalWeight = 0; |
b6e26895 | 149 | for (const auto& pair : servers) { |
439de524 RG |
150 | if (pair.second->isUp()) { |
151 | currentLoad += pair.second->outstanding; | |
152 | totalWeight += pair.second->weight; | |
153 | } | |
154 | } | |
155 | ||
156 | if (totalWeight > 0) { | |
157 | targetLoad = (currentLoad / totalWeight) * g_consistentHashBalancingFactor; | |
b6e26895 | 158 | } |
b6e26895 RG |
159 | } |
160 | ||
161 | for (const auto& d: servers) { | |
439de524 | 162 | if (d.second->isUp() && (g_consistentHashBalancingFactor == 0 || d.second->outstanding <= (targetLoad * d.second->weight))) { |
b6e26895 RG |
163 | // make sure hashes have been computed |
164 | if (d.second->hashes.empty()) { | |
165 | d.second->hash(); | |
166 | } | |
167 | { | |
168 | ReadLock rl(&(d.second->d_lock)); | |
169 | const auto& server = d.second; | |
170 | // we want to keep track of the last hash | |
171 | if (min > *(server->hashes.begin())) { | |
172 | min = *(server->hashes.begin()); | |
173 | first = server; | |
174 | } | |
175 | ||
50033a8e | 176 | auto hash_it = std::lower_bound(server->hashes.begin(), server->hashes.end(), qhash); |
b6e26895 RG |
177 | if (hash_it != server->hashes.end()) { |
178 | if (*hash_it < sel) { | |
179 | sel = *hash_it; | |
180 | ret = server; | |
181 | } | |
182 | } | |
183 | } | |
184 | } | |
185 | } | |
186 | if (ret != nullptr) { | |
187 | return ret; | |
188 | } | |
189 | if (first != nullptr) { | |
190 | return first; | |
191 | } | |
192 | return shared_ptr<DownstreamState>(); | |
193 | } | |
194 | ||
cc958b79 RG |
195 | shared_ptr<DownstreamState> chashed(const ServerPolicy::NumberedServerVector& servers, const DNSQuestion* dq) |
196 | { | |
197 | return chashedFromHash(servers, dq->qname->hash(g_hashperturb)); | |
198 | } | |
199 | ||
b6e26895 RG |
200 | shared_ptr<DownstreamState> roundrobin(const ServerPolicy::NumberedServerVector& servers, const DNSQuestion* dq) |
201 | { | |
202 | ServerPolicy::NumberedServerVector poss; | |
203 | ||
204 | for(auto& d : servers) { | |
205 | if(d.second->isUp()) { | |
206 | poss.push_back(d); | |
207 | } | |
208 | } | |
209 | ||
210 | const auto *res=&poss; | |
211 | if(poss.empty() && !g_roundrobinFailOnNoServer) | |
212 | res = &servers; | |
213 | ||
214 | if(res->empty()) | |
215 | return shared_ptr<DownstreamState>(); | |
216 | ||
217 | static unsigned int counter; | |
b6e26895 RG |
218 | return (*res)[(counter++) % res->size()].second; |
219 | } | |
220 | ||
221 | ServerPolicy::NumberedServerVector getDownstreamCandidates(const pools_t& pools, const std::string& poolName) | |
222 | { | |
223 | std::shared_ptr<ServerPool> pool = getPool(pools, poolName); | |
224 | return pool->getServers(); | |
225 | } | |
226 | ||
227 | std::shared_ptr<ServerPool> createPoolIfNotExists(pools_t& pools, const string& poolName) | |
228 | { | |
229 | std::shared_ptr<ServerPool> pool; | |
230 | pools_t::iterator it = pools.find(poolName); | |
231 | if (it != pools.end()) { | |
232 | pool = it->second; | |
233 | } | |
234 | else { | |
235 | if (!poolName.empty()) | |
236 | vinfolog("Creating pool %s", poolName); | |
237 | pool = std::make_shared<ServerPool>(); | |
238 | pools.insert(std::pair<std::string,std::shared_ptr<ServerPool> >(poolName, pool)); | |
239 | } | |
240 | return pool; | |
241 | } | |
242 | ||
243 | void setPoolPolicy(pools_t& pools, const string& poolName, std::shared_ptr<ServerPolicy> policy) | |
244 | { | |
245 | std::shared_ptr<ServerPool> pool = createPoolIfNotExists(pools, poolName); | |
246 | if (!poolName.empty()) { | |
247 | vinfolog("Setting pool %s server selection policy to %s", poolName, policy->name); | |
248 | } else { | |
249 | vinfolog("Setting default pool server selection policy to %s", policy->name); | |
250 | } | |
251 | pool->policy = policy; | |
252 | } | |
253 | ||
254 | void addServerToPool(pools_t& pools, const string& poolName, std::shared_ptr<DownstreamState> server) | |
255 | { | |
256 | std::shared_ptr<ServerPool> pool = createPoolIfNotExists(pools, poolName); | |
257 | if (!poolName.empty()) { | |
258 | vinfolog("Adding server to pool %s", poolName); | |
259 | } else { | |
260 | vinfolog("Adding server to default pool"); | |
261 | } | |
262 | pool->addServer(server); | |
263 | } | |
264 | ||
265 | void removeServerFromPool(pools_t& pools, const string& poolName, std::shared_ptr<DownstreamState> server) | |
266 | { | |
267 | std::shared_ptr<ServerPool> pool = getPool(pools, poolName); | |
268 | ||
269 | if (!poolName.empty()) { | |
270 | vinfolog("Removing server from pool %s", poolName); | |
271 | } | |
272 | else { | |
273 | vinfolog("Removing server from default pool"); | |
274 | } | |
275 | ||
276 | pool->removeServer(server); | |
277 | } | |
278 | ||
279 | std::shared_ptr<ServerPool> getPool(const pools_t& pools, const std::string& poolName) | |
280 | { | |
281 | pools_t::const_iterator it = pools.find(poolName); | |
282 | ||
283 | if (it == pools.end()) { | |
284 | throw std::out_of_range("No pool named " + poolName); | |
285 | } | |
286 | ||
287 | return it->second; | |
288 | } | |
a9599e73 RG |
289 | |
290 | std::shared_ptr<DownstreamState> getSelectedBackendFromPolicy(const ServerPolicy& policy, const ServerPolicy::NumberedServerVector& servers, DNSQuestion& dq) | |
291 | { | |
292 | std::shared_ptr<DownstreamState> selectedBackend{nullptr}; | |
293 | ||
294 | if (policy.isLua) { | |
295 | if (!policy.isFFI) { | |
296 | std::lock_guard<std::mutex> lock(g_luamutex); | |
297 | selectedBackend = policy.policy(servers, &dq); | |
298 | } | |
299 | else { | |
300 | dnsdist_ffi_dnsquestion_t dnsq(&dq); | |
301 | dnsdist_ffi_servers_list_t serversList(servers); | |
302 | unsigned int selected = 0; | |
303 | { | |
304 | std::lock_guard<std::mutex> lock(g_luamutex); | |
305 | selected = policy.ffipolicy(&serversList, &dnsq); | |
306 | } | |
307 | selectedBackend = servers.at(selected).second; | |
308 | } | |
309 | } | |
310 | else { | |
311 | selectedBackend = policy.policy(servers, &dq); | |
312 | } | |
313 | ||
314 | return selectedBackend; | |
315 | } |