{"action":"created","comment":{"url":"https://api.github.com/repos/PuerkitoBio/throttled/pulls/comments/35445148","id":35445148,"diff_hunk":"@@ -80,36 +107,76 @@ func (r *rateLimiter) Start() {\n func (r *rateLimiter) Limit(w http.ResponseWriter, req *http.Request) (<-chan bool, error) {\n \t// Create return channel and initialize\n \tch := make(chan bool, 1)\n+\t// How long until the next request is permitted? Allow the request IFF\n+\t// that is less than zero (in the past).\n+\tvar tat, newTat, now int64\n \tok := true\n \tkey := r.vary.Key(req)\n \n-\t// Get the current count and remaining seconds\n-\tcnt, secs, err := r.store.Incr(key, r.window)\n-\t// Handle the possible situations: error, begin new window, or increment current window.\n-\tswitch {\n-\tcase err != nil && err != ErrNoSuchKey:\n-\t\t// An unexpected error occurred\n-\t\treturn nil, err\n-\tcase err == ErrNoSuchKey || secs <= 0:\n-\t\t// Reset counter\n-\t\tif err := r.store.Reset(key, r.window); err != nil {\n+\ti := 0\n+\tfor {\n+\t\tvar err error\n+\n+\t\tnow = r.clock()\n+\n+\t\t// tat refers to the theoretical arrival time that would be expected\n+\t\t// from equally spaced requests at exactly the rate limit.\n+\t\ttat, err = r.store.Get(key)\n+\t\tif err == store.ErrNoSuchKey {\n+\t\t\ttat = now\n+\t\t} else if err != nil {\n \t\t\treturn nil, err\n \t\t}\n-\t\tcnt = 1\n-\t\tsecs = int(r.window.Seconds())\n-\tdefault:\n-\t\t// If the limit is reached, deny access\n-\t\tif cnt > r.reqs {\n+\n+\t\t// How long until the next request is permitted? Allow the request\n+\t\t// IFF that is less the zero (in the past).\n+\t\tif now < (tat - int64(r.delayVariationTolerance)) {\n \t\t\tok = false\n+\t\t\tbreak\n+\t\t}\n+\n+\t\tif now > tat {\n+\t\t\tnewTat = now + int64(r.emissionInterval)\n+\t\t} else {\n+\t\t\tnewTat = tat + int64(r.emissionInterval)\n+\t\t}\n+\n+\t\tvar updated bool\n+\t\tif err == store.ErrNoSuchKey {\n+\t\t\tupdated, err = r.store.SetNX(key, newTat)\n+\t\t} else {\n+\t\t\tupdated, err = r.store.CompareAndSwap(key, tat, newTat)","path":"rate.go","position":186,"original_position":186,"commit_id":"ee1464ad07acec23ce917dfe205414d96b3775de","original_commit_id":"ee1464ad07acec23ce917dfe205414d96b3775de","user":{"login":"brandur","id":96890,"avatar_url":"https://avatars.githubusercontent.com/u/96890?v=3","gravatar_id":"","url":"https://api.github.com/users/brandur","html_url":"https://github.com/brandur","followers_url":"https://api.github.com/users/brandur/followers","following_url":"https://api.github.com/users/brandur/following{/other_user}","gists_url":"https://api.github.com/users/brandur/gists{/gist_id}","starred_url":"https://api.github.com/users/brandur/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/brandur/subscriptions","organizations_url":"https://api.github.com/users/brandur/orgs","repos_url":"https://api.github.com/users/brandur/repos","events_url":"https://api.github.com/users/brandur/events{/privacy}","received_events_url":"https://api.github.com/users/brandur/received_events","type":"User","site_admin":false},"body":"Correct me if I'm wrong, but the CAS here is to protect against possible contention from other rate limiting that's being run simultaneously against the same key elsewhere right? Isn't the same case possible when the original fetch turns up empty (and thus prompting the `SetNX` down here)?\r\n\r\nAdmittedly, it's probably not a real problem in practice. If the original bucket wasn't set, that probably suggests that not a whole bunch of rate limiting is being run against it.","created_at":"2015-07-24T17:27:25Z","updated_at":"2015-07-24T17:27:25Z","html_url":"https://github.com/PuerkitoBio/throttled/pull/8#discussion_r35445148","pull_request_url":"https://api.github.com/repos/PuerkitoBio/throttled/pulls/8","_links":{"self":{"href":"https://api.github.com/repos/PuerkitoBio/throttled/pulls/comments/35445148"},"html":{"href":"https://github.com/PuerkitoBio/throttled/pull/8#discussion_r35445148"},"pull_request":{"href":"https://api.github.com/repos/PuerkitoBio/throttled/pulls/8"}}},"pull_request":{"url":"https://api.github.com/repos/PuerkitoBio/throttled/pulls/8","id":40314556,"html_url":"https://github.com/PuerkitoBio/throttled/pull/8","diff_url":"https://github.com/PuerkitoBio/throttled/pull/8.diff","patch_url":"https://github.com/PuerkitoBio/throttled/pull/8.patch","issue_url":"https://api.github.com/repos/PuerkitoBio/throttled/issues/8","number":8,"state":"open","locked":false,"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},"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.","created_at":"2015-07-19T20:35:42Z","updated_at":"2015-07-24T17:27:25Z","closed_at":null,"merged_at":null,"merge_commit_sha":"3d6c4991a6623fc1a3a14314313e98017d92d94a","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/PuerkitoBio/throttled/pulls/8/commits","review_comments_url":"https://api.github.com/repos/PuerkitoBio/throttled/pulls/8/comments","review_comment_url":"https://api.github.com/repos/PuerkitoBio/throttled/pulls/comments{/number}","comments_url":"https://api.github.com/repos/PuerkitoBio/throttled/issues/8/comments","statuses_url":"https://api.github.com/repos/PuerkitoBio/throttled/statuses/ee1464ad07acec23ce917dfe205414d96b3775de","head":{"label":"metcalf:am-gcra-rate","ref":"am-gcra-rate","sha":"ee1464ad07acec23ce917dfe205414d96b3775de","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},"repo":{"id":39315762,"name":"throttled","full_name":"metcalf/throttled","owner":{"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},"private":false,"html_url":"https://github.com/metcalf/throttled","description":"throttling strategies for HTTP handlers","fork":true,"url":"https://api.github.com/repos/metcalf/throttled","forks_url":"https://api.github.com/repos/metcalf/throttled/forks","keys_url":"https://api.github.com/repos/metcalf/throttled/keys{/key_id}","collaborators_url":"https://api.github.com/repos/metcalf/throttled/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/metcalf/throttled/teams","hooks_url":"https://api.github.com/repos/metcalf/throttled/hooks","issue_events_url":"https://api.github.com/repos/metcalf/throttled/issues/events{/number}","events_url":"https://api.github.com/repos/metcalf/throttled/events","assignees_url":"https://api.github.com/repos/metcalf/throttled/assignees{/user}","branches_url":"https://api.github.com/repos/metcalf/throttled/branches{/branch}","tags_url":"https://api.github.com/repos/metcalf/throttled/tags","blobs_url":"https://api.github.com/repos/metcalf/throttled/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/metcalf/throttled/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/metcalf/throttled/git/refs{/sha}","trees_url":"https://api.github.com/repos/metcalf/throttled/git/trees{/sha}","statuses_url":"https://api.github.com/repos/metcalf/throttled/statuses/{sha}","languages_url":"https://api.github.com/repos/metcalf/throttled/languages","stargazers_url":"https://api.github.com/repos/metcalf/throttled/stargazers","contributors_url":"https://api.github.com/repos/metcalf/throttled/contributors","subscribers_url":"https://api.github.com/repos/metcalf/throttled/subscribers","subscription_url":"https://api.github.com/repos/metcalf/throttled/subscription","commits_url":"https://api.github.com/repos/metcalf/throttled/commits{/sha}","git_commits_url":"https://api.github.com/repos/metcalf/throttled/git/commits{/sha}","comments_url":"https://api.github.com/repos/metcalf/throttled/comments{/number}","issue_comment_url":"https://api.github.com/repos/metcalf/throttled/issues/comments{/number}","contents_url":"https://api.github.com/repos/metcalf/throttled/contents/{+path}","compare_url":"https://api.github.com/repos/metcalf/throttled/compare/{base}...{head}","merges_url":"https://api.github.com/repos/metcalf/throttled/merges","archive_url":"https://api.github.com/repos/metcalf/throttled/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/metcalf/throttled/downloads","issues_url":"https://api.github.com/repos/metcalf/throttled/issues{/number}","pulls_url":"https://api.github.com/repos/metcalf/throttled/pulls{/number}","milestones_url":"https://api.github.com/repos/metcalf/throttled/milestones{/number}","notifications_url":"https://api.github.com/repos/metcalf/throttled/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/metcalf/throttled/labels{/name}","releases_url":"https://api.github.com/repos/metcalf/throttled/releases{/id}","created_at":"2015-07-18T23:19:28Z","updated_at":"2015-07-18T23:19:28Z","pushed_at":"2015-07-19T20:27:59Z","git_url":"git://github.com/metcalf/throttled.git","ssh_url":"git@github.com:metcalf/throttled.git","clone_url":"https://github.com/metcalf/throttled.git","svn_url":"https://github.com/metcalf/throttled","homepage":"http://0value.com/throttled--guardian-of-the-web-server","size":7875,"stargazers_count":0,"watchers_count":0,"language":"Go","has_issues":false,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"PuerkitoBio:master","ref":"master","sha":"1c8297c643b774435df8df65f7502b37d014fb6b","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},"repo":{"id":16983151,"name":"throttled","full_name":"PuerkitoBio/throttled","owner":{"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},"private":false,"html_url":"https://github.com/PuerkitoBio/throttled","description":"throttling strategies for HTTP handlers","fork":false,"url":"https://api.github.com/repos/PuerkitoBio/throttled","forks_url":"https://api.github.com/repos/PuerkitoBio/throttled/forks","keys_url":"https://api.github.com/repos/PuerkitoBio/throttled/keys{/key_id}","collaborators_url":"https://api.github.com/repos/PuerkitoBio/throttled/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/PuerkitoBio/throttled/teams","hooks_url":"https://api.github.com/repos/PuerkitoBio/throttled/hooks","issue_events_url":"https://api.github.com/repos/PuerkitoBio/throttled/issues/events{/number}","events_url":"https://api.github.com/repos/PuerkitoBio/throttled/events","assignees_url":"https://api.github.com/repos/PuerkitoBio/throttled/assignees{/user}","branches_url":"https://api.github.com/repos/PuerkitoBio/throttled/branches{/branch}","tags_url":"https://api.github.com/repos/PuerkitoBio/throttled/tags","blobs_url":"https://api.github.com/repos/PuerkitoBio/throttled/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/PuerkitoBio/throttled/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/PuerkitoBio/throttled/git/refs{/sha}","trees_url":"https://api.github.com/repos/PuerkitoBio/throttled/git/trees{/sha}","statuses_url":"https://api.github.com/repos/PuerkitoBio/throttled/statuses/{sha}","languages_url":"https://api.github.com/repos/PuerkitoBio/throttled/languages","stargazers_url":"https://api.github.com/repos/PuerkitoBio/throttled/stargazers","contributors_url":"https://api.github.com/repos/PuerkitoBio/throttled/contributors","subscribers_url":"https://api.github.com/repos/PuerkitoBio/throttled/subscribers","subscription_url":"https://api.github.com/repos/PuerkitoBio/throttled/subscription","commits_url":"https://api.github.com/repos/PuerkitoBio/throttled/commits{/sha}","git_commits_url":"https://api.github.com/repos/PuerkitoBio/throttled/git/commits{/sha}","comments_url":"https://api.github.com/repos/PuerkitoBio/throttled/comments{/number}","issue_comment_url":"https://api.github.com/repos/PuerkitoBio/throttled/issues/comments{/number}","contents_url":"https://api.github.com/repos/PuerkitoBio/throttled/contents/{+path}","compare_url":"https://api.github.com/repos/PuerkitoBio/throttled/compare/{base}...{head}","merges_url":"https://api.github.com/repos/PuerkitoBio/throttled/merges","archive_url":"https://api.github.com/repos/PuerkitoBio/throttled/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/PuerkitoBio/throttled/downloads","issues_url":"https://api.github.com/repos/PuerkitoBio/throttled/issues{/number}","pulls_url":"https://api.github.com/repos/PuerkitoBio/throttled/pulls{/number}","milestones_url":"https://api.github.com/repos/PuerkitoBio/throttled/milestones{/number}","notifications_url":"https://api.github.com/repos/PuerkitoBio/throttled/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/PuerkitoBio/throttled/labels{/name}","releases_url":"https://api.github.com/repos/PuerkitoBio/throttled/releases{/id}","created_at":"2014-02-19T12:13:32Z","updated_at":"2015-07-24T03:37:43Z","pushed_at":"2015-07-19T20:35:42Z","git_url":"git://github.com/PuerkitoBio/throttled.git","ssh_url":"git@github.com:PuerkitoBio/throttled.git","clone_url":"https://github.com/PuerkitoBio/throttled.git","svn_url":"https://github.com/PuerkitoBio/throttled","homepage":"http://0value.com/throttled--guardian-of-the-web-server","size":7942,"stargazers_count":319,"watchers_count":319,"language":"Go","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":15,"mirror_url":null,"open_issues_count":1,"forks":15,"open_issues":1,"watchers":319,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/PuerkitoBio/throttled/pulls/8"},"html":{"href":"https://github.com/PuerkitoBio/throttled/pull/8"},"issue":{"href":"https://api.github.com/repos/PuerkitoBio/throttled/issues/8"},"comments":{"href":"https://api.github.com/repos/PuerkitoBio/throttled/issues/8/comments"},"review_comments":{"href":"https://api.github.com/repos/PuerkitoBio/throttled/pulls/8/comments"},"review_comment":{"href":"https://api.github.com/repos/PuerkitoBio/throttled/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/PuerkitoBio/throttled/pulls/8/commits"},"statuses":{"href":"https://api.github.com/repos/PuerkitoBio/throttled/statuses/ee1464ad07acec23ce917dfe205414d96b3775de"}}}}