In order to prevent network congestion when transmitting data on the network, it is necessary to limit the outgoing network traffic so that the traffic can be sent out at a relatively uniform speed. The token bucket algorithm realizes this function by controlling the number of data sent to the network and allowing burst data to be sent.

What is a token

A token bucket is probably a bucket with a token in it, so what is a token?

Ziwei gege took the command arrow, can command, command. In the computer world, a token is also a command, a token is an authorization to do something, and without a token, nothing can be done.

Implement the limiter with a token

We use a token to represent the ability to send 1 byte of data. If we send tokens to the program continuously, the program is entitled to send data continuously. When we do not send tokens to the program, the program is effectively blocked from sending data. Let’s talk about a speed limiter, which means that a program can only send a certain amount of data per unit of time. Assuming 10 tokens are issued in a second, the application is limited to sending data at a speed of 10bytes/s. If more than 10bytes of data need to be sent in a second, it will be discarded because there is no token.

Improve the speed limiter – add a bucket

The speed limiter we implement is constant, but in the real world, there is often a sudden demand for transmission (faster delivery, but not for long, and not causing network congestion), and this kind of data hits our speed limiter and cannot be sent because the token is not available.

To the change of speed limiter, still produce 10 token 1 SEC, but we put the token first produced in a bucket, when the program needs to be sent from the bucket token, don’t need, the token will settle in barrels, assuming a bucket of precipitated 10 tokens, program can be sent in 1 seconds at most 20 bytes of data, In addition, because the tokens in the bucket are used up, only 10bytes of data can be sent at most in the next second, which does not cause pressure on the network due to the continuous sending of large amounts of data.

Fifteen lines of Python code practice token buckets

The token bucket needs to generate tokens at a certain speed and put them into the bucket. When the program wants to send data, it takes the tokens out of the bucket. There seems to be a problem here. If we use an endless loop to issue tokens over and over again, the program gets blocked. Is there a better way to do this?

We can calculate the number of tokens that can be fetched in the bucket (no larger than the size of the bucket of course) by subtracting the current time from the last token fetching time and multiplying the token issuing speed, thus avoiding the logic of circular issuing.

Now look at the code:

import time


class TokenBucket(object):

    # rate is the token issuing speed, and capacity is the bucket size
    def __init__(self, rate, capacity):
        self._rate = rate
        self._capacity = capacity
        self._current_amount = 0
        self._last_consume_time = int(time.time())

    # token_amount is the number of tokens needed to send data
    def consume(self, token_amount):
        increment = (int(time.time()) - self._last_consume_time) * self._rate  Count the number of new tokens issued from the last send to this send
        self._current_amount = min(
            increment + self._current_amount, self._capacity)  The number of tokens cannot exceed the capacity of the bucket
        if token_amount > self._current_amount:  # If there are not enough tokens, data cannot be sent
            return False
        self._last_consume_time = int(time.time())
        self._current_amount -= token_amount
        return True
Copy the code

Scan for Python private dishes