| I was not very impressed by the token bucket example. Firstly, it is totally ridiculous to need to write your own implementation of gcd and the comment is silly and unnecessary. Secondly, the implementation for the token bucket seems to just be bad. A simpler implementation is as follows: - Input number of tokens and refill time. - Output the constant state describing the limiter: the max number of tokens and the time to get a single token (= refill time / size, ignoring rounding issues which shouldn’t generally matter if your times are in nanos) - The only mutable state is a single time instant: the time when the limiter becomes full - to attempt to take a token, compute max(0,full_time - now) / new_token_time and if this is less than or equal to the size of the bucket minus the number of tokens you want, you may withdraw and set full_time := max(full_time, now) + tokens_to_withdraw * new_token_time If that division is concerning then you should either attempt to withdraw from the rate limiter less frequently or you should not be using one at all. The rest of the code is about scheduling events to happen when there are free tokens in the ratelimiter. This is a different problem and also over-complicated. You should either poll and retry periodically with your most important event (rather than whatever event you thought was most important when the bucket became empty) though you then want to be careful about stale tasks never running, or you should just have a queue of pairs (Task, cost) where cost is an int. after withdrawing tokens from the ratelimiter or when the queue transitions from empty to non-empty, peek the top item and set a timer for rl.full_time - rl.new_token_time * (rl.size - cost) and when the timer fires (or immediately if the time was in the past) you can dequeue, withdraw cost tokens, and run that top task (then repeat.) |