From 0e4675a9fb1dd125320c02e8d157ec02f5aca70c Mon Sep 17 00:00:00 2001
From: Remi Gacogne <remi.gacogne@powerdns.com>
Date: Mon, 30 Oct 2017 14:52:13 +0100
Subject: [PATCH] rec: Sort NS addresses by speed, remove old ones

We used to not sort the different addresses we had for a given NS
by speed, only taking care of placing the first one in front.
However we also didn't remove existing entries for a given NS,
meaning that if a given IP stopped being advertised it would stay
in our NS speeds map and keep being used to determine the fastest
NS, even if we would only send queries to the new IPs after the
selection. Since we didn't send any query to the old IP anymore,
its latency would only keep decaying meaning the computed latency
of the corresponding NS would only keep decreasing, completely
uncorrelated from its real latency.

This commit removes old entries from the NS speeds map if they are
no longer present when we refresh the addresses of a given NS.
In addition, it orders all NS IPs by decaying latency, meaning new
ones will have a fair chance of being picked up.
---
 pdns/syncres.cc | 48 +++++++++++++++++++++++++++++++++++++-----------
 pdns/syncres.hh | 37 +++++++++++++++++++------------------
 2 files changed, 56 insertions(+), 29 deletions(-)

diff --git a/pdns/syncres.cc b/pdns/syncres.cc
index 98c105e48..40e273b6d 100644
--- a/pdns/syncres.cc
+++ b/pdns/syncres.cc
@@ -609,6 +609,16 @@ static bool ipv6First(const ComboAddress& a, const ComboAddress& b)
 }
 #endif
 
+struct speedOrderCA
+{
+  speedOrderCA(std::map<ComboAddress,double>& speeds): d_speeds(speeds) {}
+  bool operator()(const ComboAddress& a, const ComboAddress& b) const
+  {
+    return d_speeds[a] < d_speeds[b];
+  }
+  std::map<ComboAddress, double>& d_speeds;
+};
+
 /** This function explicitly goes out for A or AAAA addresses
 */
 vector<ComboAddress> SyncRes::getAddrs(const DNSName &qname, unsigned int depth, set<GetBestNSAnswer>& beenthere)
@@ -674,21 +684,37 @@ vector<ComboAddress> SyncRes::getAddrs(const DNSName &qname, unsigned int depth,
   d_DNSSECValidationRequested = oldValidationRequested;
 
   if(ret.size() > 1) {
-    random_shuffle(ret.begin(), ret.end(), dns_random);
+    map<ComboAddress, double> speeds;
 
-    // move 'best' address for this nameserver name up front
-    nsspeeds_t::iterator best = t_sstorage.nsSpeeds.find(qname);
+    auto& collection = t_sstorage.nsSpeeds[qname].d_collection;
+    for(const auto& val: ret) {
+      double speed;
+      speed=collection[val].get(&d_now);
+      speeds[val]=speed;
+    }
 
-    if(best != t_sstorage.nsSpeeds.end())
-      for(ret_t::iterator i=ret.begin(); i != ret.end(); ++i) {
-        if(*i==best->second.d_best) {  // got the fastest one
-          if(i!=ret.begin()) {
-            *i=*ret.begin();
-            *ret.begin()=best->second.d_best;
-          }
-          break;
+    t_sstorage.nsSpeeds[qname].purge(speeds);
+
+    random_shuffle(ret.begin(), ret.end(), dns_random);
+    speedOrderCA so(speeds);
+    stable_sort(ret.begin(), ret.end(), so);
+
+    if(doLog()) {
+      string prefix=d_prefix;
+      prefix.append(depth, ' ');
+      LOG(prefix<<"Nameserver "<<qname<<" IPs: ");
+      bool first = true;
+      for(const auto& addr : ret) {
+        if (first) {
+          first = false;
         }
+        else {
+          LOG(", ");
+        }
+        LOG((addr.toString())<<"(" << (boost::format("%0.2f") % (speeds[addr]/1000.0)).str() <<"ms)");
       }
+      LOG(endl);
+    }
   }
 
   return ret;
diff --git a/pdns/syncres.hh b/pdns/syncres.hh
index a33eb544d..59bd8e253 100644
--- a/pdns/syncres.hh
+++ b/pdns/syncres.hh
@@ -282,18 +282,7 @@ public:
   {
     void submit(const ComboAddress& remote, int usecs, const struct timeval* now)
     {
-      collection_t::iterator pos;
-      for(pos=d_collection.begin(); pos != d_collection.end(); ++pos)
-        if(pos->first==remote)
-          break;
-      if(pos!=d_collection.end()) {
-        pos->second.submit(usecs, now);
-      }
-      else {
-        DecayingEwma de;
-        de.submit(usecs, now);
-        d_collection.push_back(make_pair(remote, de));
-      }
+      d_collection[remote].submit(usecs, now);
     }
 
     double get(const struct timeval* now)
@@ -302,10 +291,10 @@ public:
         return 0;
       double ret=std::numeric_limits<double>::max();
       double tmp;
-      for(collection_t::iterator pos=d_collection.begin(); pos != d_collection.end(); ++pos) {
-        if((tmp=pos->second.get(now)) < ret) {
+      for (auto& entry : d_collection) {
+        if((tmp = entry.second.get(now)) < ret) {
           ret=tmp;
-          d_best=pos->first;
+          d_best=entry.first;
         }
       }
 
@@ -314,13 +303,25 @@ public:
 
     bool stale(time_t limit) const
     {
-      for(collection_t::const_iterator pos=d_collection.begin(); pos != d_collection.end(); ++pos)
-        if(!pos->second.stale(limit))
+      for(const auto& entry : d_collection)
+        if(!entry.second.stale(limit))
           return false;
       return true;
     }
 
-    typedef vector<pair<ComboAddress, DecayingEwma> > collection_t;
+    void purge(const std::map<ComboAddress, double>& keep)
+    {
+      for (auto iter = d_collection.begin(); iter != d_collection.end(); ) {
+        if (keep.find(iter->first) != keep.end()) {
+          ++iter;
+        }
+        else {
+          iter = d_collection.erase(iter);
+        }
+      }
+    }
+
+    typedef std::map<ComboAddress, DecayingEwma> collection_t;
     collection_t d_collection;
     ComboAddress d_best;
   };
-- 
2.40.0