title: Techniques to measure/enforce a quota on customer web requests
body: <p>I have a webapp with several homogenous web frontends (specifically, I'm running on App Engine) for a B2B application.  I need to design a short-term quota system so that I can reject traffic if a customer's burst request rate exceeds their quota.  The number of customers that need to be supported is in the tens of thousands range.  The time-scale over which I want to measure these quotas will be somewhere in the "minutes" range; at most an hour.</p>
  
  <p>E.g. if the time scale is 10 minutes and customer X is making requests way above their quota, then I'm fine with the system serving <em>all</em> of their requests until they exhaust the number of requests they are allowed every 10 minutes, then rejecting all of their requests for the remainder of that 10 minute window, then starting the process over for the next 10 minute window.</p>
  
  <p>Half-baked solutions that I have considered:</p>
  
  <ul>
  <li><p>Get a beefy Redis box.  On every request (or perhaps some fixed % of them, e.g. 1-in-10, to lighten the load) from customer X, make a GET to a count-of-X variable.  If it's > their quota-per-10-minutes, reject the request.  Else, make a INCR to the count-of-X variable and serve the request.  Every 10 minutes, SET the counts of all customers to 0.</p></li>
  <li><p>Similar to above, except use memcache since that service is built into app engine so I don't need to run my own boxes.  If a memcache value gets lost, oh well - we might not throttle like we should during that time window (as long as the time window is short enough, we probably don't care too much).</p></li>
  <li><p>Each webserver stores global per-customer counters for new-requests-seen-by-me and requests-seen-globally.  Every second (or so) each webserver pushes its new-requests-seen-by-me value (for every customer) to some centralized pub-sub-like service that redistributes that value to all webservers (which they add to their requests-seen-globally value).  Webservers user their requests-seen-globally value (which is always slightly stale) to decide whether to serve or reject requests.</p></li>
  </ul>