http: use Retry-After HTTP header to optimize retries

Some mirrors like snapshot.debian.org apply strict http rate limits.
While apt already has an exponential backoff mechanism implemented, this
is not sufficient due to the following reasons:

1. all retries happen roughly at the same time
2. the retry-after information from the server is not used

We fix this by improving the algorithm: First, if present, the timestamp
or duration of the Retry-After header is added to the exponential
backoff, optimizing for success-on-second-try. Second, a random delay is
added (delay += [0, delay]) to distribute the retries to not immediately
run into the limit again. To avoid super-long delays, this is capped by
the configured maximum delay. This logic only becomes active if the
option Acquire::Retries::HandleRetryAfter is enabled.

Signed-off-by: Felix Moessbauer <felix.moessbauer@siemens.com>

6 files changed, 59 insertions, 6 deletions

diff --git a/apt-pkg/acquire-method.cc b/apt-pkg/acquire-method.cc
index 7b1f4f1b5..13f3fa4dd 100644
--- a/apt-pkg/acquire-method.cc
+++ b/apt-pkg/acquire-method.cc
@@ -145,9 +145,15 @@ void pkgAcqMethod::Fail(bool Transient)
 
    Fail("", Transient);
 }
+
+void pkgAcqMethod::Fail(std::string Err, bool Tansient)
+{
+   std::unordered_map<std::string, std::string> fields;
+   FailWithContext(Err, Tansient, fields);
+}
 									/*}}}*/
 // AcqMethod::Fail - A fetch has failed					/*{{{*/
-void pkgAcqMethod::Fail(string Err, bool Transient)
+void pkgAcqMethod::FailWithContext(std::string Err, bool Transient, std::unordered_map<std::string, std::string> &fields)
 {
 
    if (not _error->empty())
@@ -175,7 +181,6 @@ void pkgAcqMethod::Fail(string Err, bool Transient)
    if (IP.empty() == false && _config->FindB("Acquire::Failure::ShowIP", true) == true)
       Err.append(" ").append(IP);
 
-   std::unordered_map<std::string, std::string> fields;
    if (Queue != nullptr)
       try_emplace(fields, "URI", Queue->Uri);
    else
diff --git a/apt-pkg/acquire-method.h b/apt-pkg/acquire-method.h
index edee93996..387d0984d 100644
--- a/apt-pkg/acquire-method.h
+++ b/apt-pkg/acquire-method.h
@@ -92,6 +92,7 @@ class APT_PUBLIC pkgAcqMethod
 
    // Outgoing messages
    void Fail(bool Transient = false);
+   void FailWithContext(std::string Why, bool Transient, std::unordered_map<std::string, std::string> &fields);
    inline void Fail(const char *Why, bool Transient = false) {Fail(std::string(Why),Transient);};
    virtual void Fail(std::string Why, bool Transient = false);
    virtual void URIStart(FetchResult &Res);
diff --git a/apt-pkg/acquire-worker.cc b/apt-pkg/acquire-worker.cc
index 4840ea16a..f4326ab03 100644
--- a/apt-pkg/acquire-worker.cc
+++ b/apt-pkg/acquire-worker.cc
@@ -603,8 +603,8 @@ bool pkgAcquire::Worker::RunMessages()
 	    {
 	       std::string const failReason = LookupTag(Message, "FailReason");
 	       {
-		  auto const reasons = { "Timeout", "ConnectionRefused",
-		     "ConnectionTimedOut", "ResolveFailure", "TmpResolveFailure" };
+		  auto const reasons = {"Timeout", "ConnectionRefused",
+					"ConnectionTimedOut", "ResolveFailure", "TmpResolveFailure", "TooManyRequests"};
 		  errTransient = std::find(std::begin(reasons), std::end(reasons), failReason) != std::end(reasons);
 	       }
 	       if (errTransient == false)
@@ -636,6 +636,7 @@ void pkgAcquire::Worker::HandleFailure(std::vector<pkgAcquire::Item *> const &It
 				       std::string const &Message, bool const errTransient, bool const errAuthErr)
 {
    auto currentTime = clock::now();
+   auto currentWall = std::chrono::system_clock::now();
    for (auto const Owner : ItmOwners)
    {
       std::string NewURI;
@@ -648,7 +649,24 @@ void pkgAcquire::Worker::HandleFailure(std::vector<pkgAcquire::Item *> const &It
 	 {
 	    auto Iter = _config->FindI("Acquire::Retries", 3) - Owner->Retries - 1;
 	    auto const MaxDur = _config->FindI("Acquire::Retries::Delay::Maximum", 30);
-	    auto Dur =  std::chrono::seconds(std::min(1 << Iter, MaxDur));
+	    auto const handleRetryAfter = _config->FindB("Acquire::Retries::HandleRetryAfter", false);
+	    auto Dur = std::chrono::seconds(1 << Iter);
+	    auto const retryAfterStr = LookupTag(Message, "Retry-After");
+	    auto const failReason = LookupTag(Message, "FailReason");
+	    if (failReason == "TooManyRequests" && !retryAfterStr.empty() && handleRetryAfter)
+	    {
+	       // The webserver gave a retry time. Use it, but also add exponential
+	       // backoff waiting as we might not be the only client.
+	       const auto retryAfter = std::chrono::seconds(std::strtoul(retryAfterStr.c_str(), nullptr, 10));
+	       const auto epochCurrent = std::chrono::duration_cast<std::chrono::seconds>(currentWall.time_since_epoch());
+	       // If the retryAfter is in the past, we can just continue.
+	       if (retryAfter > epochCurrent)
+		  Dur += retryAfter - epochCurrent;
+	       // Usually, all requests run into the rate limit at the same time.
+	       // Distribute the retries to avoid hitting the limit again.
+	       Dur += std::chrono::seconds(std::rand() % Dur.count());
+	    }
+	    Dur = std::min(Dur, std::chrono::seconds(MaxDur));
 	    if (_config->FindB("Debug::Acquire::Retries"))
 	       std::clog << "Delaying " << SavedDesc.Description << " by " << Dur.count() << " seconds" << std::endl;
 	    Owner->FetchAfter(currentTime + Dur);
diff --git a/doc/examples/configure-index b/doc/examples/configure-index
index 72ce1fe3a..feadca8d2 100644
--- a/doc/examples/configure-index
+++ b/doc/examples/configure-index
@@ -249,6 +249,7 @@ Acquire
       Delay "<BOOL>" {   // whether to backoff between retries using the delay: method
         Maximum "<INT>"; // maximum number of seconds to delay an item per retry
       };
+      HandleRetryAfter "<BOOL>"; // whether to respect the wait time of the Retry-After header
   };
   Source-Symlinks "<BOOL>";
   ForceHash "<STRING>"; // hashmethod used for expected hash: sha256, sha1 or md5sum
diff --git a/methods/basehttp.cc b/methods/basehttp.cc
index 26b633cba..d335e6fa0 100644
--- a/methods/basehttp.cc
+++ b/methods/basehttp.cc
@@ -263,6 +263,21 @@ bool RequestState::HeaderLine(string const &Line)			/*{{{*/
       return true;
    }
 
+   if (stringcasecmp(Tag, "Retry-After:") == 0)
+   {
+      unsigned long _retry_after_s;
+      if (RFC1123StrToTime(Val, RetryAfter))
+      {
+	 return true;
+      }
+      if (StrToNum(Val.c_str(), _retry_after_s, 4, 10) == 1)
+      {
+	 RetryAfter = time(nullptr) + _retry_after_s;
+	 return true;
+      }
+      return _error->Error(_("Unknown date format"));
+   }
+
    if (Server->RangesAllowed && stringcasecmp(Tag, "Via:") == 0)
    {
       auto const parts = VectorizeString(Val, ' ');
@@ -884,7 +899,19 @@ int BaseHttpMethod::Loop()
 	       599, // Network Connect Timeout Error
 	    };
 	    if (std::find(std::begin(TransientCodes), std::end(TransientCodes), Req.Result) != std::end(TransientCodes))
-	       Fail(true);
+	    {
+	       if (Req.RetryAfter)
+	       {
+		  std::unordered_map<std::string, std::string> fields;
+		  fields["Retry-After"] = std::to_string(Req.RetryAfter);
+		  SetFailReason("TooManyRequests");
+		  FailWithContext(std::string("TooManyRequests"), true, fields);
+	       }
+	       else
+	       {
+		  Fail(true);
+	       }
+	    }
 	    else
 	       Fail();
 	    break;
diff --git a/methods/basehttp.h b/methods/basehttp.h
index 080ea527e..c077ea384 100644
--- a/methods/basehttp.h
+++ b/methods/basehttp.h
@@ -57,6 +57,7 @@ struct RequestState
    enum {Chunked,Stream,Closes} Encoding = Closes;
    enum {Header, Data} State = Header;
    std::string Location;
+   time_t RetryAfter = 0;
 
    FileFd File;