1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

from time import time

class TokenBucket(object):
    """An implementation of the token bucket algorithm.
    
    >>> bucket = TokenBucket(80, 0.5)
    >>> print bucket.consume(10)
    True
    >>> print bucket.consume(90)
    False
    """
    def __init__(self, tokens, fill_rate):
        """tokens is the total tokens in the bucket. fill_rate is the
        rate in tokens/second that the bucket will be refilled."""
        self.capacity = float(tokens)
        self._tokens = float(tokens)
        self.fill_rate = float(fill_rate)
        self.timestamp = time()

    def consume(self, tokens):
        """Consume tokens from the bucket. Returns True if there were
        sufficient tokens otherwise False."""
        if tokens <= self.tokens:
            self._tokens -= tokens
        else:
            return False
        return True

    def get_tokens(self):
        if self._tokens < self.capacity:
            now = time()
            delta = self.fill_rate * (now - self.timestamp)
            self._tokens = min(self.capacity, self._tokens + delta)
            self.timestamp = now
        return self._tokens
    tokens = property(get_tokens)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

if __name__ == "__main__":
    bucket = TokenBucket(80, 1)
    print("tokens = %s" % bucket._tokens)
    print("consume(10) = %s" % bucket.consume(10))
    print("consume(10) = %s" % bucket.consume(10))
    time.sleep(1)
    print("tokens = %s" % bucket._tokens)
    time.sleep(1)
    print("tokens = %s" % bucket._tokens)
    print("consume(90) = %s" % bucket.consume(90))
    print("tokens = %s" % bucket._tokens)
    print("consume(90) = %s" % bucket.consume(90))
    print("tokens = %s" % bucket._tokens)

1
2
3
4
5
6
7
8

➜  /tmp python token_bucket.py
tokens = 80.0
consume(10) = True
consume(10) = True
tokens = 61.0040922165
tokens = 62.0080561638
consume(90) = False
tokens = 62.0081322193

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

const Timer = require('../util/timer');

class RateLimiter {
    /**
     * A utility for limiting the rate of repetitive send operations, such as
     * bluetooth messages being sent to hardware devices. It uses the token bucket
     * strategy: a counter accumulates tokens at a steady rate, and each send costs
     * a token. If no tokens remain, it's not okay to send.
     * @param {number} maxRate the maximum number of sends allowed per second
     * @constructor
     */
    constructor (maxRate) {
        /**
         * The maximum number of tokens.
         * @type {number}
         */
        this._maxTokens = maxRate;

        /**
         * The interval in milliseconds for refilling one token. It is calculated
         * so that the tokens will be filled to maximum in one second.
         * @type {number}
         */
        this._refillInterval = 1000 / maxRate;

        /**
         * The current number of tokens in the bucket.
         * @type {number}
         */
        this._count = this._maxTokens;


        this._timer = new Timer();
        this._timer.start();

        /**
         * The last time in milliseconds when the token count was updated.
         * @type {number}
         */
        this._lastUpdateTime = this._timer.timeElapsed();
    }

    /**
     * Check if it is okay to send a message, by updating the token count,
     * taking a token and then checking if we are still under the rate limit.
     * @return {boolean} true if we are under the rate limit
     */
    okayToSend () {
        // Calculate the number of tokens to refill the bucket with, based on the
        // amount of time since the last refill.
        const now = this._timer.timeElapsed();
        const timeSinceRefill = now - this._lastUpdateTime;
        const refillCount = Math.floor(timeSinceRefill / this._refillInterval);

        // If we're adding at least one token, reset _lastUpdateTime to now.
        // Otherwise, don't reset it so that we can continue measuring time until
        // the next refill.
        if (refillCount > 0) {
            this._lastUpdateTime = now;
        }

        // Refill the tokens up to the maximum
        this._count = Math.min(this._maxTokens, this._count + refillCount);

        // If we have at least one token, use one, and it's okay to send.
        if (this._count > 0) {
            this._count--;
            return true;
        }
        return false;
    }
}

module.exports = RateLimiter;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

const test = require('tap').test;
const RateLimiter = require('../../src/util/rateLimiter.js');
 test('rate limiter', t => {
    const rate = 30;
    const limiter = new RateLimiter(rate);
     // The rate limiter starts with a number of tokens equal to the max rate
    t.equal(limiter._count, rate);
     // Running okayToSend rate times uses up all of the tokens
    for (let i = 0; i < rate; i++) {
        t.true(limiter.okayToSend());
        t.equal(limiter._count, rate - (i + 1));
    }
    t.false(limiter.okayToSend());
     // After a delay of one second divided by the max rate, we should have exactly
    // one more token to use.
    setTimeout(() => {
        t.true(limiter.okayToSend());
        t.false(limiter.okayToSend());
        t.end();
    }, 1000 / rate);
});

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

// const RateLimiter = require('../../util/rateLimiter.js');
// this._rateLimiter = new RateLimiter(30);

    _send (uuid, message) {
        if (!this.getPeripheralIsConnected()) return Promise.resolve();

        if (!this._rateLimiter.okayToSend()) return Promise.resolve();

        return this._ble.write(UUID.IO_SERVICE, uuid, message, 'base64');
    }