在漏桶算法中，当队列不满时，实现固定速率的正确逻辑是什么？

Question

我正在学习漏桶算法，并希望通过使用redis和golang编写一些简单的代码来弄脏我的手。

当我在这里搜索关键词redis，漏，桶。有许多类似的问题，如在1，这是很好的。但是，我发现在遍历了这些线程和wiki2之后，我很难理解整个逻辑。我想有些事情我不明白，我也不知道。因此，我想在这里重新措辞，如果我弄错了，请纠正我。

伪码：

key := "ip address, token or anything that can be the representative of a client"
redis_queue_size := 5
interval_between_each_request := 7
request := obtain_http_request_from_somewhere()

if check_current_queue_size() < redis_queue_size:
    if is_queue_empty()
        add_request_to_the_queue() // zadd "ip1" now() now() // now() is something like seconds, milliseconds or nanoseconds e.g. t = 1
        process_request(request)
    else
        now := get_current_time()
        // add_request_to_... retrieves the first element in the queue
        // compute the expected timestamp to execute the request and its current time
        // e.g. zadd "ip1" <time of the first elment in the queue + interval_between_each_request> now
        add_request_to_redis_queue_with_timestamp(now, interval_between_each_request) // e.g. zadd "ip" <timestamp as score> <timestamp a request is allowed to be executed>
        // Below function check_the_time_left...() will check how many time left at which the current request need to wait. 
        // For instance, the first request stored in the queue with the command
        //    zadd "ip1" 1 1  // t = 1
        // and the second request arrives at t = 4 but it is allowed t be executed at t = 8
        //    zadd "ip1" 8 4 // where 4 := now, 8 := 1 + interval_between_each_request
        // so the N will be 4 
        N := check_the_time_left_for_the_current_request_to_execute(now, interval_between_each_request) 
        sleep(N) // now the request wait for 4 seconds before processing the request
        process_request(http_request_obj)
else
    return // discard request

我理解当队列满的时候，下面的请求将被丢弃。但是，我想我可能误解了当队列不满时，如何重新调整传入的请求，使其能够以固定的速率执行。

我很感激你的建议

1. https://stackoverflow.com/search?q=redis+leaky+bucket+&s=aa2eaa93-a6ba-4e31-9a83-68f791c5756e

2. https://en.wikipedia.org/wiki/Leaky_bucket#As_a_queue

Answer 1

如果这是为了简单的速率-使用排序集限制滑动窗口方法，我们看到大多数Redis用户https://github.com/Redislabs-Solution-Architects/RateLimitingExample/blob/sliding_window/app.py实现了

1. 。

1. 如果您设置为漏桶，可以考虑使用每个consumerID的redis流(apiToken/IP地址等)，如下所示：

consumerID请求来了

XADD请求-使用者requests桶大小

如果需要的话，生成一个go例程，如果consumerID获得当前时间，如果XLEN的请求-使用者is为0，退出go例程

XREAD计数number_of_requests_per_period块时间段-1 ms流请求-使用者and获得当前时间和睡眠的剩余时间期间

https://redis.io/commands#stream详细介绍了流是如何工作的

Answer 2

有几种方法可以实现漏桶，但是流程应该有两个独立的部分。一个把东西放进桶里，另一个在一个固定的时间间隔内移除它们，如果有什么东西要移除。

您可以使用一个单独的goroutine，它将在一个设置的间隔内使用这些消息。这将简化您的代码，因为在一个代码路径上，您只需查看队列大小和丢弃数据包，而另一个代码路径只需消耗任何内容。