From 50033a8e00c840cd5a43ded5add58965e9e15929 Mon Sep 17 00:00:00 2001
From: Remi Gacogne <remi.gacogne@powerdns.com>
Date: Wed, 22 Jan 2020 18:59:40 +0100
Subject: [PATCH] dnsdist: Speed up the consistent hashing policies with large
 weights

Using a sorted vector provides a much faster lookup time than a
std::set when the number of points on the circle (weight of the
backend) is huge.
A boost::flat_set is almost as fast as a sorted vector but the
insertion time is quite bad.
---
 pdns/dnsdist.hh                        | 2 +-
 pdns/dnsdistdist/dnsdist-backend.cc    | 6 ++++--
 pdns/dnsdistdist/dnsdist-lbpolicies.cc | 2 +-
 3 files changed, 6 insertions(+), 4 deletions(-)

diff --git a/pdns/dnsdist.hh b/pdns/dnsdist.hh
index ce27a4e0fe..bf54a89aeb 100644
--- a/pdns/dnsdist.hh
+++ b/pdns/dnsdist.hh
@@ -772,7 +772,7 @@ struct DownstreamState
     pthread_rwlock_destroy(&d_lock);
   }
   boost::uuids::uuid id;
-  std::set<unsigned int> hashes;
+  std::vector<unsigned int> hashes;
   mutable pthread_rwlock_t d_lock;
   std::vector<int> sockets;
   const std::string sourceItfName;
diff --git a/pdns/dnsdistdist/dnsdist-backend.cc b/pdns/dnsdistdist/dnsdist-backend.cc
index af9439dc08..606977c098 100644
--- a/pdns/dnsdistdist/dnsdist-backend.cc
+++ b/pdns/dnsdistdist/dnsdist-backend.cc
@@ -98,12 +98,14 @@ void DownstreamState::hash()
   auto w = weight;
   WriteLock wl(&d_lock);
   hashes.clear();
+  hashes.reserve(w);
   while (w > 0) {
     std::string uuid = boost::str(boost::format("%s-%d") % id % w);
-    unsigned int wshash = burtleCI((const unsigned char*)uuid.c_str(), uuid.size(), g_hashperturb);
-    hashes.insert(wshash);
+    unsigned int wshash = burtleCI(reinterpret_cast<const unsigned char*>(uuid.c_str()), uuid.size(), g_hashperturb);
+    hashes.push_back(wshash);
     --w;
   }
+  std::sort(hashes.begin(), hashes.end());
 }
 
 void DownstreamState::setId(const boost::uuids::uuid& newId)
diff --git a/pdns/dnsdistdist/dnsdist-lbpolicies.cc b/pdns/dnsdistdist/dnsdist-lbpolicies.cc
index a3175e4e59..aa08a32d23 100644
--- a/pdns/dnsdistdist/dnsdist-lbpolicies.cc
+++ b/pdns/dnsdistdist/dnsdist-lbpolicies.cc
@@ -147,7 +147,7 @@ shared_ptr<DownstreamState> chashedFromHash(const ServerPolicy::NumberedServerVe
           first = server;
         }
 
-        auto hash_it = server->hashes.lower_bound(qhash);
+        auto hash_it = std::lower_bound(server->hashes.begin(), server->hashes.end(), qhash);
         if (hash_it != server->hashes.end()) {
           if (*hash_it < sel) {
             sel = *hash_it;
-- 
2.47.2