Giter Club home page Giter Club logo

token-bucket's Introduction

Token Bucket

This is a threadsafe implementation of the Token Bucket algorithm in PHP. You can use a token bucket to limit an usage rate for a resource (e.g. a stream bandwidth or an API usage).

The token bucket is an abstract metaphor which doesn't have a direction of the resource consumption. I.e. you can limit a rate for consuming or producing. E.g. you can limit the consumption rate of a third party API service, or you can limit the usage rate of your own API service.

Installation

Use Composer:

composer require bandwidth-throttle/token-bucket

Usage

The package is in the namespace bandwidthThrottle\tokenBucket.

Example

This example will limit the rate of a global resource to 10 requests per second for all requests.

use bandwidthThrottle\tokenBucket\Rate;
use bandwidthThrottle\tokenBucket\TokenBucket;
use bandwidthThrottle\tokenBucket\storage\FileStorage;

$storage = new FileStorage(__DIR__ . "/api.bucket");
$rate    = new Rate(10, Rate::SECOND);
$bucket  = new TokenBucket(10, $rate, $storage);
$bucket->bootstrap(10);

if (!$bucket->consume(1, $seconds)) {
    http_response_code(429);
    header(sprintf("Retry-After: %d", floor($seconds)));
    exit();
}

echo "API response";

Note: In this example TokenBucket::bootstrap() is part of the code. This is not recommended for production, as this is producing unnecessary storage communication. TokenBucket::bootstrap() should be part of the application's bootstrap or deploy process.

Scope of the storage

First you need to decide the scope of your resource. I.e. do you want to limit it per request, per user or amongst all requests? You can do this by choosing a Storage implementation of the desired scope:

  • The RequestScope limits the rate only within one request. E.g. to limit the bandwidth of a download. Each requests will have the same bandwidth limit.

  • The SessionScope limits the rate of a resource within a session. The rate is controlled over all requests of one session. E.g. to limit the API usage per user.

  • The GlobalScope limits the rate of a resource for all processes (i.e. requests). E.g. to limit the aggregated download bandwidth of a resource over all processes. This scope permits race conditions between processes. The TokenBucket is therefore synchronized on a shared mutex.

TokenBucket

When you have your storage you can finally instantiate a TokenBucket. The first parameter is the capacity of the bucket. I.e. there will be never more tokens available. This also means that consuming more tokens than the capacity is invalid.

The second parameter is the token-add-Rate. It determines the speed for filling the bucket with tokens. The rate is the amount of tokens added per unit, e.g. new Rate(100, Rate::SECOND) would add 100 tokens per second.

The third parameter is the storage, which is used to persist the token amount of the bucket. The storage does determine the scope of the bucket.

Bootstrapping

A token bucket needs to be bootstrapped. While the method TokenBucket::bootstrap() doesn't have any side effects on an already bootstrapped bucket, it is not recommended do call it for every request. Better include that in your application's bootstrap or deploy process.

Consuming

Now that you have a bootstrapped bucket, you can start consuming tokens. The method TokenBucket::consume() will either return true if the tokens were consumed or false else. If the tokens were consumed your application can continue to serve the resource.

Else if the tokens were not consumed you should not serve the resource. In that case consume() did write a duration of seconds into its second parameter (which was passed by reference). This is the duration until sufficient tokens would be available.

BlockingConsumer

In the first example we did either serve the request or fail with the HTTP status code 429. This is actually a very resource efficient way of throtteling API requests as it doesn't reserve resources on your server.

However sometimes it is desirable not to fail but instead wait a little bit and then continue serving the requests. You can do this by consuming the token bucket with a BlockingConsumer.

use bandwidthThrottle\tokenBucket\Rate;
use bandwidthThrottle\tokenBucket\TokenBucket;
use bandwidthThrottle\tokenBucket\BlockingConsumer;
use bandwidthThrottle\tokenBucket\storage\FileStorage;

$storage  = new FileStorage(__DIR__ . "/api.bucket");
$rate     = new Rate(10, Rate::SECOND);
$bucket   = new TokenBucket(10, $rate, $storage);
$consumer = new BlockingConsumer($bucket);
$bucket->bootstrap(10);

// This will block until one token is available.
$consumer->consume(1);

echo "API response";

This will effectively limit the rate to 10 requests per seconds as well. But in this case the client has not to bother with the 429 error. Instead the connection is just delayed to the desired rate.

License and authors

This project is free and under the WTFPL. Responsible for this project is Markus Malkusch [email protected].

Donations

If you like this project and feel generous donate a few Bitcoins here: 1335STSwu9hST4vcMRppEPgENMHD2r1REK

Build Status

token-bucket's People

Contributors

austinpray avatar deefour avatar drsect0r avatar lloy0076 avatar malkusch avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

token-bucket's Issues

Feature request: refund tokens

Thanks for such a nice pkg! I wonder if there is any method like refund or something that can return the tokens to the bucket.

I used this feature mainly for trade amount limitation. In such a case:

// ...
// consume when an order creating.
$bucket->consume($order->total);
$order->create();
// then order turns to failed.
$order->failed();
$bucket->refund($order->total);

For now I implement this feature on my own. But I think that would be better if there is official support :)

Probable memory eating for Memcached storage

I am talking about Memcached storage implementation (probably other too).
Since you use memcached::set with ttl = 0, old unused buckets will stay in memory forever, and this is not good for websites with bucket-per-ip. For websites with 100000 visitors per day it will eat >100 bytes per record = 10Megabytes, and will grow each day. In a month it will eat ~ 300Megabytes and some vps servers will go down.
I think it should be possible to set ttl to specific reasonable value.

Tokens left

Hi!

Is there any way to know/access to how many tokens are left until reach the time limit?

Thanks!

"Could not write to storage" for FileStorage

When I use next code for bootstrap token bucket:

use bandwidthThrottle\tokenBucket\Rate;
use bandwidthThrottle\tokenBucket\TokenBucket;
use bandwidthThrottle\tokenBucket\storage\FileStorage;

$storage = new FileStorage(__DIR__ . "/api.bucket");
$rate = new Rate(10, Rate::SECOND);
$bucket = new TokenBucket(10, $rate, $storage);
$bucket->bootstrap(10);

On Linux and macOS all works well, but in Windows I get an error:

Could not write to storage.

Maybe it's because the file opens twice, first, in FileStorage::__construct, then file locked by flock and then file opens in FileStorage::bootstrap method.

Using as client

Hello I am just curious if I could use the lib to make calls to an API rest without surpass their limits.

BlockingConsumer: timeout parameter?

Hey. I'm not sure whether a complete deadlock during blocking consumption could somehow occur or not, but isn't it generally healthy to have a failsafe for a blocking operation - such as a configurable timeout setting?

MemcachedStorage CASMutex TimeoutException

The current implementation of MemcachedStorage doesn't work.

When the consume method is called and "$delta < 0", then $this->storage->getMutex()->synchronized keeps looping the "callable $code". This is because "$this->storage->getMutex()->notify()" is never called when "$delta < 0", so "$this->loop->execute($code)" (CASMutex) keeps running and will reach the timeout "malkusch\lock\exception\TimeoutException" "Timeout of 3 seconds exceeded.".

The current implementation of MemcachedStorage uses CAS, where the MemcacheStorage (without D) implementation doesn't. I've created a MemcachedStorage implementation without CAS (also using "MemcachedMutex" instead of "CASMutex") and that seems to work fine. What was the reason to use the CAS tokens?

Timeout of 3 seconds exceeded

I get this error report everytime after some problem happened.Then I review the code in "vendor\malkusch\lock"and find some bug for Redis:If u set a lock for the bucket and the client broke,this lock will never be release so that every request will be stoped by the "setnx".I wonder if u have some solution for this bug,and sorry for my English :p
by zhangxiaohou

Is is possible to use SessionScope to throttle requests by IP address?

Is it possible to use SessionScope to limit requests by an unique identifier such as their IP address?

Ideally something that would be able to 'kick' requests if an IP has made over a set allocation within a set time frame, e.g if the limit is 1000 requests per hour, once they make the 1001th request within that window rather than sleep it will just discard the request until they allowed to make requests again in the next window.

Leaky Bucket vs Token Bucket

This project is great, but relies upon bootstrapping the bucket (ie filling with initial token allocation)

This can be troublesome when dealing with multiple resources that need limiting - eg rate limiting an API by remote IP address. There's no simple way of knowing if you've already bootstrapped for that particular IP without calling the storage, which is an extra overhead.

Instead, I'd propose a leaky bucket design - instead of checking the bucket still has >0 tokens remaining, you reverse it. So the bucket is empty initially, then you 'drain' X tokens per X seconds and each new rate limited request adds a token.

If the bucket is 'full' (ie tokens > limit, means you are filling faster than emptying, but with a 'limit' sized buffer) then you fail the request.

This way, you never need to bootstrap - you always just increment the bucket counter.

Thoughts?

Rate limiting API requests within multiple workers

My use case is :

  • A set of 5 (rabbitmq) workers consume messages, doing one ore more API request per message
  • No more than 10 API requests should be globally (throughout all workers) done for 1 second

Would this repo implementation be fine with this distributed constraint ?
Would this rate of 10 be an absolute limit or an average ?

ext-redis

Is there a way you can make that dependency optional?

Fatal Error: The string is not 64 bit long. PHP 8.2

Fatal error: Uncaught bandwidthThrottle\tokenBucket\storage\StorageException:
The string is not 64 bit long. in \bandwidth-throttle\token-bucket\classes\util\DoublePacker.php: 41

Having this error when applied following code in constructor of ApiController, and tried to use consume:

`function __construct() {

    $this->storage = new FileStorage(__DIR__ . "/api.bucket");
    $this->rate    = new Rate(10, Rate::SECOND);
    $this->bucket  = new TokenBucket(10, $this->rate, $this->storage);
     //Following code executed once, then commented
     //$this->bucket->bootstrap(10);

}`

`protected function checkRateLimit() {

    if (!$this->bucket->consume(1, $seconds)) {
        http_response_code(429);
        header(sprintf("Retry-After: %d", floor($seconds)));
        exit();
    }
    //echo "Continue to API response";
    return true;

}`

I have also noticed FileStorage class is sending blank string to unpack( ) function in Double Packer on line 129.

bandwidthThrottle\tokenBucket\util\DoublePacker: :unpack('')

Please guide what's going wrong here?

Ideal?

I want to rate limit 500 requests an hour to a specific script, by their IP Address.

Is this a good script to do so, any examples?

Does it support redis cluster?

An error happens when I use redis cluster,
Uncaught TypeError: Argument 2 passed to bandwidthThrottle\tokenBucket\storage\PHPRedisStorage::__construct() must be an instance of Redis, instance of RedisCluster given

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.