Token bucket is not related to a specific window. Hence, the key we used for the algorithm must just include the identifier. This is basically a breaking change, but it is needed for the correctness of the algorithm.
We were evicting the bucket at a fixed interval, without thinking about the tokens used from the bucket, no matter what. This is wrong, we need to have a max idle time equal to the interval * number of intervals needed to fill the token. Only after this time, it is safe to evict the bucket, because evicted buckets start with tokens equal to max tokens. Since we don't have a max idle in Redis, we will have to invent our own with TTLs by updating the TTL each time we access the bucket.
See https://github.com/upstash/ratelimit-python/pull/9 and https://github.com/upstash/ratelimit/pull/54 for more information.