{"action":"created","issue":{"url":"https://api.github.com/repos/throttled/throttled/issues/8","labels_url":"https://api.github.com/repos/throttled/throttled/issues/8/labels{/name}","comments_url":"https://api.github.com/repos/throttled/throttled/issues/8/comments","events_url":"https://api.github.com/repos/throttled/throttled/issues/8/events","html_url":"https://github.com/throttled/throttled/pull/8","id":95946787,"number":8,"title":"Replace fixed-window rate-limiting with leaky bucket-type scheduling.","user":{"login":"metcalf","id":16716,"avatar_url":"https://avatars.githubusercontent.com/u/16716?v=3","gravatar_id":"","url":"https://api.github.com/users/metcalf","html_url":"https://github.com/metcalf","followers_url":"https://api.github.com/users/metcalf/followers","following_url":"https://api.github.com/users/metcalf/following{/other_user}","gists_url":"https://api.github.com/users/metcalf/gists{/gist_id}","starred_url":"https://api.github.com/users/metcalf/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/metcalf/subscriptions","organizations_url":"https://api.github.com/users/metcalf/orgs","repos_url":"https://api.github.com/users/metcalf/repos","events_url":"https://api.github.com/users/metcalf/events{/privacy}","received_events_url":"https://api.github.com/users/metcalf/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":13,"created_at":"2015-07-19T20:35:42Z","updated_at":"2015-07-28T21:33:54Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/throttled/throttled/pulls/8","html_url":"https://github.com/throttled/throttled/pull/8","diff_url":"https://github.com/throttled/throttled/pull/8.diff","patch_url":"https://github.com/throttled/throttled/pull/8.patch"},"body":"This replaces the fixed-window rate-limiting algorithm with a generic cell rate algorithm as described in:\r\nhttps://en.wikipedia.org/wiki/Generic_cell_rate_algorithm\r\n\r\nWe use GCRA for some internal rate limiting libraries at Stripe and I wanted to try incorporating it into another project. My code here could probably use some work to make it consistent with the existing style of the library. I wanted to open a PR early to get your feedback on whether this kind of semantic change is something you'd be willing to consider.\r\n\r\nI believe that fixed windows have some problems that don't affect sliding window algorithms. Namely:\r\n* If a client exhausts the rate-limit at the beginning of a fixed window, they have to wait until the end of the window before making *any* additional requests. Imagine a client that makes a steady stream of user-facing requests well below the rate limit. If the same client then initiates a batch job that quickly exhausts the limit, the service will be completely unavailable until the next window reset. Under a moving window, a naive batch job (or malicious user) may crash while without leaving the service completely unavailable.\r\n* The fixed window also doesn't guarantee a maximum number of requests, N, per period. To make 2N-1 requests in a single period a client may:\r\n  * Make 1 request, note the reset time.\r\n  * Wait until shortly before the reset time and make N-1 requests.\r\n  * Wait until just after the reset time and make N requests.\r\n\r\nThere are a few other behavioral differences worth noting:\r\n* GCRA requires less memory (a single integer per key instead of two).\r\n* The `Store` interface is completely different. Notably it requires an atomic compare-and-swap operation instead of an atomic increment.\r\n* The semantics of the HTTP headers change somewhat though are largely compatible with their original meanings.\r\n\r\nIn the process of rewriting the memStore, I replaced the groupcache LRU implementation with a threadsafe implementation by Hashicorp. My parallel tests encountered errors when parallel threads contended for a small LRU pool. The new store implementations pass Go race detection."},"comment":{"url":"https://api.github.com/repos/throttled/throttled/issues/comments/125759775","html_url":"https://github.com/throttled/throttled/pull/8#issuecomment-125759775","issue_url":"https://api.github.com/repos/throttled/throttled/issues/8","id":125759775,"user":{"login":"PuerkitoBio","id":692384,"avatar_url":"https://avatars.githubusercontent.com/u/692384?v=3","gravatar_id":"","url":"https://api.github.com/users/PuerkitoBio","html_url":"https://github.com/PuerkitoBio","followers_url":"https://api.github.com/users/PuerkitoBio/followers","following_url":"https://api.github.com/users/PuerkitoBio/following{/other_user}","gists_url":"https://api.github.com/users/PuerkitoBio/gists{/gist_id}","starred_url":"https://api.github.com/users/PuerkitoBio/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/PuerkitoBio/subscriptions","organizations_url":"https://api.github.com/users/PuerkitoBio/orgs","repos_url":"https://api.github.com/users/PuerkitoBio/repos","events_url":"https://api.github.com/users/PuerkitoBio/events{/privacy}","received_events_url":"https://api.github.com/users/PuerkitoBio/received_events","type":"User","site_admin":false},"created_at":"2015-07-28T21:33:54Z","updated_at":"2015-07-28T21:33:54Z","body":"+1. I will also invite @dchest from StableLib to the org, he has good knowledge of the package and is interested in helping out."}}