Geek Answers Handbook

Membrane speed limiting algorithm? (Token bucket?)

I’m looking for an effective approach to request speed limits from the Google App Engine to a third-party service. The cost of third-party services limits requests based on a separate account, and on the Google App Engine side, most of the work is done inside tasks. Tokens are a great general algorithm.

Q: what approach can be used to effectively limit bids for each account, and not for maintenance?

This should not include setting bids in the GAE task queues, as the number of requests per account and the number of accounts served will vary greatly. For performance reasons, I'm most interested in memcache-based ideas (incr / decr?)!

I think it comes down to a memcache-based slave token?

Thoughts?

+4
source share
3 answers

I saved this project as a bookmark a while ago: http://code.google.com/p/gaedjango-ratelimitcache/

Not quite the answer to your specific question, but maybe this will help you get started.

+1
source

I know this is an old question, but it is the best search result, and I thought that others might find an alternative that I made useful. This is a bit more granular (up to the second), simple (only one function) and executor (only one search in memcache) than the solution above:

import webapp2 from functools import wraps from google.appengine.api import memcache def rate_limit(seconds_per_request=1): def rate_limiter(function): @wraps(function) def wrapper(self, *args, **kwargs): added = memcache.add('%s:%s' % (self.__class__.__name__, self.request.remote_addr or ''), 1, time=seconds_per_request, namespace='rate_limiting') if not added: self.response.write('Rate limit exceeded.') self.response.set_status(429) return return function(self, *args, **kwargs) return wrapper return rate_limiter class ExampleHandler(webapp2.RequestHandler): @rate_limit(seconds_per_request=2) def get(self): self.response.write('Hello, webapp2!')
+1
source

Here's how I implemented marker token with memcache in GAE:

Edit: take a (different) hit.

This is partly borrowed from https://github.com/simonw/ratelimitcache/blob/master/ratelimitcache.py

 def throttle(key, rate_count, rate_seconds, tries=3): ''' returns True if throttled (not enough tokens available) else False implements token bucket algorithm ''' client = memcache.Client(CLIENT_ARGS) for _ in range(tries): now = int(time.time()) keys = ['%s-%s' % (key, str(now-i)) for i in range(rate_seconds)] client.add(keys[0], 0, time=rate_seconds+1) tokens = client.get_multi(keys[1:]) tokens[keys[0]] = client.gets(keys[0]) if sum(tokens.values()) >= rate_count: return True if client.cas(keys[0], tokens[keys[0]] + 1, time=rate_seconds+1) != 0: return False logging.error('cache contention error') return True

Here are some usage examples:

 def test_that_it_throttles_too_many_requests(self): burst = 1 interval = 1 assert shared.rate_limit.throttle('test', burst, interval) is False assert shared.rate_limit.throttle('test', burst, interval) is True def test_that_it_doesnt_throttle_burst_of_requests(self): burst = 16 interval = 1 for i in range(burst): assert shared.rate_limit.throttle('test', burst, interval) is False time.sleep(interval + 1) # memcache has 1 second granularity for i in range(burst): assert shared.rate_limit.throttle('test', burst, interval) is False
+1
source

More articles:


All Articles