OLD | NEW |
| (Empty) |
1 // Copyright (c) 2006-2008 The Chromium Authors. All rights reserved. | |
2 // Use of this source code is governed by a BSD-style license that can be | |
3 // found in the LICENSE file. | |
4 // | |
5 // This file implements backoff in the suggest system so that we don't | |
6 // DOS the Suggest servers when using URLFetcher. | |
7 | |
8 #ifndef CHROME_BROWSER_URL_FETCHER_PROTECT_H__ | |
9 #define CHROME_BROWSER_URL_FETCHER_PROTECT_H__ | |
10 | |
11 #include <map> | |
12 #include <queue> | |
13 #include <string> | |
14 | |
15 #include "base/lock.h" | |
16 #include "base/logging.h" | |
17 #include "base/scoped_ptr.h" | |
18 #include "base/time.h" | |
19 | |
20 | |
21 // This class is used to manage one service's rate protection. It maintains | |
22 // a queue of connection successes and failures and analyzes the requests | |
23 // over some period of time, in order to deduce the backoff time of every | |
24 // request. | |
25 // The backoff algorithm consists of two parts. Firstly, avoid too many | |
26 // send events in a sliding window. That will prevent traffic overload. | |
27 // Secondly, exponential backoff is used when receiving an error message | |
28 // from server. Exponential backoff period is calculated using the following | |
29 // formula: | |
30 // | |
31 // initial backoff time (the first time to receive error) | |
32 // backoff = k * current_backoff + c (the second, third, ... error) | |
33 // maximum backoff time (when backoff > maximum backoff time) | |
34 // | |
35 // where |k| is the multiplier, and |c| is the constant factor. | |
36 class URLFetcherProtectEntry { | |
37 public: | |
38 enum EventType { | |
39 SEND, // request will be sent out | |
40 SUCCESS, // successful response | |
41 FAILURE // no response or error | |
42 }; | |
43 | |
44 URLFetcherProtectEntry(); | |
45 URLFetcherProtectEntry(int sliding_window_period, int max_send_threshold, | |
46 int max_retries, int initial_timeout, | |
47 double multiplier, int constant_factor, | |
48 int maximum_timeout); | |
49 | |
50 | |
51 virtual ~URLFetcherProtectEntry() { } | |
52 | |
53 // When a connection event happens, log it to the queue, and recalculate | |
54 // the timeout period. It returns the backoff time, in milliseconds, that | |
55 // indicates to the sender how long should it wait before sending the request. | |
56 // If the request is allowed to be sent immediately, the backoff time is 0. | |
57 int UpdateBackoff(EventType event_type); | |
58 | |
59 // Returns the max retries allowed. | |
60 int max_retries() const { | |
61 return max_retries_; | |
62 } | |
63 | |
64 private: | |
65 // When a request comes, calculate the release time for it. | |
66 // Returns the backoff time before sending. | |
67 base::TimeDelta AntiOverload(); | |
68 // Resets backoff when service is ok. | |
69 // Returns the backoff time before sending. | |
70 base::TimeDelta ResetBackoff(); | |
71 // Calculates new backoff when encountering a failure. | |
72 // Returns the backoff time before sending. | |
73 base::TimeDelta IncreaseBackoff(); | |
74 | |
75 // Default parameters. Time is in milliseconds. | |
76 static const int kDefaultSlidingWindowPeriod; | |
77 static const int kDefaultMaxSendThreshold; | |
78 static const int kDefaultMaxRetries; | |
79 static const int kDefaultInitialTimeout; | |
80 static const double kDefaultMultiplier; | |
81 static const int kDefaultConstantFactor; | |
82 static const int kDefaultMaximumTimeout; | |
83 | |
84 // time to consider events when checking backoff | |
85 int sliding_window_period_; | |
86 | |
87 // maximum number of requests allowed in sliding window period | |
88 int max_send_threshold_; | |
89 // maximum retris allowed | |
90 int max_retries_; | |
91 | |
92 // initial timeout on first failure | |
93 int initial_timeout_; | |
94 // factor by which to multiply on exponential backoff (e.g., 2.0) | |
95 double multiplier_; | |
96 // constant time term to add to each attempt | |
97 int constant_factor_; | |
98 // maximum amount of time between requests | |
99 int maximum_timeout_; | |
100 | |
101 // current exponential backoff period | |
102 int timeout_period_; | |
103 // time that protection is scheduled to end | |
104 base::TimeTicks release_time_; | |
105 | |
106 // Sets up a lock to ensure thread safe. | |
107 Lock lock_; | |
108 | |
109 // A list of the recent send events. We ues them to decide whether | |
110 // there are too many requests sent in sliding window. | |
111 std::queue<base::TimeTicks> send_log_; | |
112 | |
113 DISALLOW_COPY_AND_ASSIGN(URLFetcherProtectEntry); | |
114 }; | |
115 | |
116 | |
117 // This singleton class is used to manage all protect entries. | |
118 // Now we use the host name as service id. | |
119 class URLFetcherProtectManager { | |
120 public: | |
121 ~URLFetcherProtectManager(); | |
122 | |
123 // Returns the global instance of this class. | |
124 static URLFetcherProtectManager* GetInstance(); | |
125 | |
126 // Registers a new entry in this service. If the entry already exists, | |
127 // just returns it. | |
128 URLFetcherProtectEntry* Register(std::string id); | |
129 // Always registers the entry even when it exists. | |
130 URLFetcherProtectEntry* Register(std::string id, | |
131 URLFetcherProtectEntry* entry); | |
132 | |
133 private: | |
134 URLFetcherProtectManager() { } | |
135 | |
136 typedef std::map<const std::string, URLFetcherProtectEntry*> ProtectService; | |
137 | |
138 static Lock lock_; | |
139 static scoped_ptr<URLFetcherProtectManager> protect_manager_; | |
140 ProtectService services_; | |
141 | |
142 DISALLOW_COPY_AND_ASSIGN(URLFetcherProtectManager); | |
143 }; | |
144 | |
145 #endif // CHROME_BROWSER_URL_FETCHER_PROTECT_H__ | |
OLD | NEW |