Implement exponential back-off mechanism and enforce it at the URLRequestHttpJob level.

net/url_request/request_throttler_entry.h

+// Copyright (c) 2010 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef NET_URL_REQUEST_REQUEST_THROTTLER_ENTRY_H_
+#define NET_URL_REQUEST_REQUEST_THROTTLER_ENTRY_H_
+
+#include "net/url_request/request_throttler_entry_interface.h"
+
+#include <queue>
+#include <string>
+
+#include "base/lock.h"
+
+// RequestThrottlerEntry represents an entry of RequestThrottlerManager.
+// It analyzes requests of a specific URL over some period of time, in order to
+// deduce the back-off time for every request.
+// The back-off algorithm consists of two parts. Firstly, exponential back-off
+// is used when receiving 5XX server errors or malformed response bodies.
+// The exponential back-off rule is enforced by URLRequestHttpJob. Any request
+// sent during the back-off period will be cancelled.
+// Secondly, a sliding window is used to count recent requests to a given
+// destination and provide guidance (to the application level only) on whether
+// too many requests have been sent and when a good time to send the next one
+// would be. This is never used to deny requests at the network level.
+class RequestThrottlerEntry : public RequestThrottlerEntryInterface {
+ public:
+  // Sliding window period.
+  static const int kDefaultSlidingWindowPeriodMs;
+
+  // Maximum number of requests allowed in sliding window period.
+  static const int kDefaultMaxSendThreshold;
+
+  // Initial delay for exponential back-off.
+  static const int kDefaultInitialBackoffMs;
+
+  // Additional constant to adjust back-off.
+  static const int kDefaultAdditionalConstantMs;
+
+  // Factor by which the waiting time will be multiplied.
+  static const double kDefaultMultiplyFactor;
+
+  // Fuzzing percentage. ex: 10% will spread requests randomly
+  // between 90%-100% of the calculated time.
+  static const double kDefaultJitterFactor;
+
+  // Maximum amount of time we are willing to delay our request.
+  static const int kDefaultMaximumBackoffMs;
+
+  // Time after which the entry is considered outdated.
+  static const int kDefaultEntryLifetimeMs;
+
+  // Name of the header that servers can use to ask clients to delay their next
+  // request.
+  static const char kRetryHeaderName[];
+
+  RequestThrottlerEntry();
+
+  // The life span of instances created with this constructor is set to
+  // infinite.
+  RequestThrottlerEntry(int sliding_window_period_ms,
+                        int max_send_threshold,
+                        int initial_backoff_ms,
+                        int additional_constant_ms,
+                        double multiply_factor,
+                        double jitter_factor,
+                        int maximum_backoff_ms);
+
+  // Implementation of RequestThrottlerEntryInterface.
+  virtual bool IsDuringExponentialBackoff() const;
+  virtual int64 GetRecommendedDelayForNextRequest();
+  virtual void UpdateWithResponse(
+      const RequestThrottlerHeaderInterface* response);
+
+  // Used by the manager, returns true if the entry needs to be garbage
+  // collected.
+  bool IsEntryOutdated() const;
+
+  // Used by the manager, enables the manager to flag the last successful
+  // request as a failure.
+  void ReceivedContentWasMalformed();
+
+ protected:
+  // This struct is used to save the state of the entry each time we are updated
+  // with a response header so we can regenerate it if we are informed that one
+  // of our bodies was malformed.
+  struct OldValues {
+    base::TimeTicks exponential_backoff_release_time;
+    int failure_count;
+  };
+
+  virtual ~RequestThrottlerEntry();
+
+  void Initialize();
+
+  // Calculates the release time for exponential back-off.
+  base::TimeTicks CalculateExponentialBackoffReleaseTime();
+
+  // Equivalent to TimeTicks::Now(), virtual to be mockable for testing purpose.
+  virtual base::TimeTicks GetTimeNow() const;
+
+  // Used internally to increase release time following a retry-after header.
+  void HandleCustomRetryAfter(const std::string& header_value);
+
+  // Saves the state of the object to be able to regenerate it.
+  // Must be informed of the state of the response.
+  void SaveState();
+
+  // Timestamp calculated by the exponential back-off algorithm at which we are
+  // allowed to start sending requests again.
+  base::TimeTicks exponential_backoff_release_time_;
+
+  // Number of times we encounter server errors or malformed response bodies.
+  int failure_count_;
+
+  // Set to true if we are currently tracking requests with server errors or
+  // malformed response bodies, in order to calculate the exponential back-off
+  // release time.
+  bool tracking_exponential_backoff_;
+
+  OldValues old_values_;

[Jói, 2010/11/12 19:14:24]

(Outdated comment because of my comment in the unit test file, but leaving here
for posterity):

Move the definition of the OldValues struct to right above this, to make the
documentation of that struct more obviously cover this. Alternatively, document
this as "See description of OldValues struct above."

[yzshen, 2010/11/17 07:31:43]

Removed OldValues and will keep your suggestion in mind.

+
+  // Timestamp calculated by the sliding window algorithm at which we are
+  // allowed to start sending requests again.

[Jói, 2010/11/12 19:14:24]

This comment makes it sound like we will deny requests within the period; maybe
reword to something like:

// Timestamp calculated by the sliding window algorithm
// for when we advise clients the next request should be
// made, at the earliest. Advisory only, not used to deny
// requests.

[yzshen, 2010/11/17 07:31:43]

Done.

+  base::TimeTicks sliding_window_release_time_;
+
+  // A list of the recent send events. We use them to decide whether there are
+  // too many requests sent in sliding window.
+  std::queue<base::TimeTicks> send_log_;
+
+  const int sliding_window_period_ms_;

[Jói, 2010/11/12 19:14:24]

for any of these constants in milliseconds that get calculated over to a
base::TimeDelta in the code, could we just store the constant as a
base::TimeDelta instead?

[yzshen, 2010/11/17 07:31:43]

Done. I think only the first one is always used as TimeDelta.

+  const int max_send_threshold_;
+  const int initial_backoff_ms_;
+  const int additional_constant_ms_;
+  const double multiply_factor_;
+  const double jitter_factor_;
+  const int maximum_backoff_ms_;
+  // Set to -1 if the entry never expires.
+  const int entry_lifetime_ms_;
+
+  // Lock to protect the non-static data members.
+  mutable Lock lock_;
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(RequestThrottlerEntry);
+};
+
+#endif  // NET_URL_REQUEST_REQUEST_THROTTLER_ENTRY_H_