7 ms·
Both should work. Token buckets only have to store two things (count and timestamp) where a timestamp set has to store all N timestamps. I like the simper appro
by ptarjan 9y ago
Both should work. Token buckets only have to store two things (count and timestamp) where a timestamp set has to store all N timestamps. I like the simper approach since I don't actually need access to all the timestamps.
If you look at the concurrent request limiter I do indeed keep all the timestamps there in a Redis set. That one was more error prone to write in practice as I often would accidentally hit Redis storage limits.
- bigdubs 9y ago~previous statement was incorrect~
- ptarjan 9y agoIn a token bucket algorithm you don't actually have a separate replenish step, it is baked into the next check you do. Similar to how in the example you linked the removal of the old entries is baked into the check step. Check out my example: https://gist.github.com/ptarjan/e38f45f2dfe601419ca3af937fff574d#file-request_rate_limiter-lua https://gist.github.com/ptarjan/e38f45f2dfe601419ca3af937fff... on line 23 with local filled_tokens = math.min(capacity, last_tokens+(delta*rate)) that adds in any tokens that should drip into the bucket since the last check.
- bigdubs 9y agosorry was thinking of something else. yeah the algo is pretty standard, what we found is some edge cases get super weird, namely if you check on regular intervals you'll get false positives, vs. bursty calls https://play.golang.org/p/Ujp7yeFQ3L https://play.golang.org/p/Ujp7yeFQ3L
- mritun 9y agoThere is no replenishing process, its just a conceptual thing. In code one just computes time difference and then multiplies that with fill rate to determine tokens to fill before deducting any. Token buckets are popular because they work well, require fixed size storage and are extremely simple to implement and test.