Efficient way to implement a rate-limiting or throttling algorithm for web requests in App Engine?

Question

I am looking for the efficient way to implement a moving time window rate limiting algorithm for a web application. By that I'm looking for a scalable algorithm.

So far, I'm thinking to use a sharding counter and the memcache.

Here the algorithm in a pseudo language:

For each request:
1: get the number of requests in the last N minutes from memcache
2: if nothing found in the memcache (memcache flushed or first call?)
3:   get the number of requests in the last N minutes from ndb (expensive!)
4: if the number is to high
5:   block the request
6: increment the sharding counter
7: increment the memcache value (failsafe, if an error occurs here ignore it)
8: process the request

The other questions I've found so far do not apply to the context of App Engine.

Answer 1

You could do something like this entirely in memcache, though it wouldn't survive random key eviction or flushing:

# Create a key based on time truncated to the minute.
key = 'X' + str(datetime.datetime.utcnow().replace(second=0, microsecond=0))
# Initialize the key and have it expire after a while.
if not memcache.add(key, 1, time=90):
    # If the key already exists, increment the value and save the result.
    count = memcache.incr(key)
    # Do something if it's greater than your per minute rate limit.
    if count > MAX_X_PER_MINUTE:
        raise Error