A Golang blocking leaky-bucket rate limit implementation

Overview

Go rate limiter GoDoc Coverage Status test

This package provides a Golang implementation of the leaky-bucket rate limit algorithm. This implementation refills the bucket based on the time elapsed between requests instead of requiring an interval clock to fill the bucket discretely.

Create a rate limiter with a maximum number of operations to perform per second. Call Take() before each operation. Take will sleep until you can continue.

import (
	"fmt"
	"time"

	"go.uber.org/ratelimit"
)

func main() {
    rl := ratelimit.New(100) // per second

    prev := time.Now()
    for i := 0; i < 10; i++ {
        now := rl.Take()
        fmt.Println(i, now.Sub(prev))
        prev = now
    }

    // Output:
    // 0 0
    // 1 10ms
    // 2 10ms
    // 3 10ms
    // 4 10ms
    // 5 10ms
    // 6 10ms
    // 7 10ms
    // 8 10ms
    // 9 10ms
}
Issues
  • New atomic-based implementation squeezed into int64

    New atomic-based implementation squeezed into int64

    Hi everyone, It's been a few years since we introduced the atomic-based rate limiter. Since then, after numerous changes to the runtime scheduler, mutex-based implementation has become much more stable. So I found a way to improve atomic-based implementation further and squeeze its state into one int64. The new implementation is much faster, stable under contention, and has zero allocations.

    Benchmarks on 8 core i7 intel machine: chart 1

    Benchmarks on 8 core M1 machine: chart 2

    opened by storozhukBM 10
  • Update the Limiter interface to accept a context.Context object

    Update the Limiter interface to accept a context.Context object

    This also removes the Clock abstraction, since there doesn't seem to be a way to create timers using the mock clock effectively, and it isn't used in yab at all. I can add it back in and try to munge it to work if it has value.

    opened by achals 9
  • Feature Request: Allow updating the limit

    Feature Request: Allow updating the limit

    Goal: To use this library with an adaptive rate limiter algorithm like Vegas or AIMD

    Problem: Right now the library exposes no way to update the rates dynamically.

    There are two ways to solve for this

    1. Create a new rate limiter every time I want to update limits
    2. Dynamically update the rate limit on the object

    Would like feedback on which is the preferred approach. Or if there is any other way.

    opened by prathik 8
  • Atomic based limiter

    Atomic based limiter

    Hi, I've made your limiter implementation atomic based. It is a little bit harder but in generally faster and has no goroutine scalability issues that any mutex based implementation have. Checkout this relation between RateLimiter latency and count of goroutines: limiter_scalability Original implementation moved to mutexbased.go file, so you can run benchmarks and play with other tests. But I'd suggest to leave only one implementation after all.

    [Side note] This wired latency spike in mutex based implementation is a direct illustration of mutex falling into starvation mode.

    Full benchmarking results here

    opened by storozhukBM 8
  • Add Per option

    Add Per option

    Commits are individually reviewable. The first changes address nits I missed in review.

    The final change addresses #17 by adding an option called Per that reads ratelimit.New(1, Per(time.Second)) for a 1Hz rate limiter.

    opened by kriskowal 7
  • Parity with yab ratelimit

    Parity with yab ratelimit

    I was trawling through the yab ratelimiting code, and noticed that the interface exposed there is different (and IMO nicer) than the interface in this package.

    Is this package intended to be kept updated? If so, would it be possible to update the implementation to bring it up the parity? I'd be more than happy to contribute a PR if it would help. It would be great to be able to use rate limiting logic independently of yab.

    opened by achals 6
  • Fix no slack option for int64 based option

    Fix no slack option for int64 based option

    This PR fixes the issue found by @twelsh-aw with int64 based implementation https://github.com/uber-go/ratelimit/issues/90

    Our tests did not detect this issue, so we have a separate PR https://github.com/uber-go/ratelimit/pull/93 that enhances our tests approach to detect potential errors better.

    opened by storozhukBM 5
  • Add a test verifying initial startup sequence

    Add a test verifying initial startup sequence

    See https://github.com/uber-go/ratelimit/pull/95#discussion_r915251700

    From that discussion I wasn't sure whether the proposed the initial startup sequence of the limiter - i.e. whether at startup we always block, or always allow.

    Since we didn't seem to have that codified (perhaps apart from the example_test.go) this PR adds a test to verify this.

    This is still slightly (2/1000) flaky, but I think that's good enough to add this in - should be valuable anyway.

    opened by rabbbit 4
  • Only benchmark on the latest Go version

    Only benchmark on the latest Go version

    See https://github.com/uber-go/ratelimit/issues/86#issuecomment-1146895304

    Also:

    • update to checkoutv3 (why not)
    • use setup-go action to both:
      • pick up the lastest go version
      • do appropriate caching
    opened by rabbbit 4
  • Get rid of internal/clock - Consolidate AfterFunc and Sleep in tests

    Get rid of internal/clock - Consolidate AfterFunc and Sleep in tests

    Resolves #3

    Was looking at the open issues and #3 seemed to make sense - it was also something that I saw in #37 so I thought I'd take a stab.

    The reasoning is that less code + smaller interface is a good thing.

    During the diff it turned out that:

    • our internal/clock has no tests
    • our internal/clock has at least two bugs:
      • one that I'm fixing here, related to not executing two timers if they're scheduled at the "now" boundry
      • one regarding adding time but not having a timer set for that specific time (not a problem for us, so not touching it)

    By dropping afterFunc into Sleep we're able to deprecate the internal fork altogether - there is a missing nap in andres-erbsen/clock.AfterFunc that meant we needed our own fork. Now it's not needed.

    opened by rabbbit 4
  • Prefactor types into a separarate types package

    Prefactor types into a separarate types package

    This came up in #37 where we ended up in a dependency loop.

    • main package was importing a specific rate limiter type
    • both rate limiters needed to import Clock types from main package

    By moving it to a separate package we avoid that loop.

    If we decide to go ahead with #37, this will also be necessary to have a "common config type" that can be re-used between all N alternative limiters.

    opened by rabbbit 4
  • Fix test approach for detecting issues

    Fix test approach for detecting issues

    The problem in the previous approach was that mock time literally didn't run between limite.Take() calls, so now.Sub(oldState.last) would always be 0 that can be problematic for some issues detection.

    This PR adds time increments between limite.Take() calls in (r *runnerImpl) startTaking. Unfortunately our library for clock mocking github.com/benbjohnson/clock has some races reported here https://github.com/benbjohnson/clock/issues/44 and here https://github.com/benbjohnson/clock/pull/42.

    So I decided to use the time mocking approach that Ian Lance Taylor used 19 days ago in https://github.com/golang/time repository here https://github.com/golang/time/commit/579cf78fd858857c0d766e0d63eb2b0ccf29f436

    Note: this tests approach detects an error in int64 based limiter implementation that the previous test didn't manage to catch.

    opened by storozhukBM 13
  • atomicInt64Limiter WithoutSlack doesn't block

    atomicInt64Limiter WithoutSlack doesn't block

    First off thanks for the library :)

    Saw that a new rate limiter was introduced that benchmarked a lot better and pulled it down to try it out.

    Noticed that when running WithoutSlack, it just allows everything through instead of waiting because all subsequent Take() calls fall into the case now-timeOfNextPermissionIssue > int64(t.maxSlack)

    Easiest way to repro is using your example_test.go:

    • Using rl := ratelimit.New(100) (slack=10):
    go test -run Example -count=1
    === RUN   Example
    --- PASS: Example (0.09s)
    PASS
    ok      command-line-arguments  0.207s
    
    • Using rl := ratelimit.New(100, ratelimit.WithoutSlack)
    go test -run Example -count=1   
    --- FAIL: Example (0.01s)
    got:
    1 10ms
    2 775µs
    3 3µs
    4 2µs
    5 10µs
    6 2µs
    7 2µs
    8 2µs
    9 2µs
    want:
    1 10ms
    2 10ms
    3 10ms
    4 10ms
    5 10ms
    6 10ms
    7 10ms
    8 10ms
    9 10ms
    FAIL
    FAIL    command-line-arguments  0.126s
    FAIL
    
    • Using 0.2.0 rl :=newAtomicBased(100, WithoutSlack)
    go test -run Example -count=1
    PASS
    ok      go.uber.org/ratelimit   0.323s
    

    I am not 100% sure why the other units with mocked clocks are passing, but your example test and my application tests fail consistently with this new limiter. On darwin if that helps.

    opened by twelsh-aw 10
  • Adding support for an `Allow` method

    Adding support for an `Allow` method

    This package initially seemed ideal for my use case - It supports refilling at a certain rate (so limits such as 10 per 2 minutes are possible) however only exposing Take means that it can't be used in a context where you want to return a 429 HTTP response (this would block the response which is not the behaviour I'm looking for).

    I have seen mentioned on other issues that no other features are planned, but I wanted to ask - if I made a pull request which supported an Allow method which simply returns whether a call to Take would block or not, would a merge be considered for this?

    opened by alexgokhale 10
  • Support for increasing/decreasing limits on the fly

    Support for increasing/decreasing limits on the fly

    This allows to implement nice things!

    An example: Implement an adaptative rate limiting from outside de library, enabling algorithms like:

    1. start with a small ratelimiting value
    2. periodically increase it by a small amount
    3. notice errors, drop the rate limit by X%
    4. potentially change the value of X (increase or decrease, make the algo converge better to optimal ratelimit)
    5. loop back to 2

    A suggestion for implementation is to keep a count of how many times Take was called in the given window and, when we increase or decrease, recalculate the sleep time. In case the window is already exploded (eg 10 per second is decreased to 5 per second, but in this second we already did 8 requests), then the next Take will wait for the whole window to finish.

    From the current implementation I see there is no time window management, just a basic calculation of how much time we need to sleep in average between calls. This would maybe involve that, something to consider the complexity

    opened by bcap 2
  • If add some check in New function?

    If add some check in New function?

    when I use ticker := ratelimit.New(0) the code will throw exception, but when I use negative I works ok but loss my mind. ticker := ratelimit.New(-1) Pre-Request wait 10s. if need add some check in when new a litter?

    opened by GuoGuiRong 0
Owner
Uber Go
Uber's open source software for Go development
Uber Go
Simple middleware to rate-limit HTTP requests.

Tollbooth This is a generic middleware to rate-limit HTTP requests. NOTE 1: This library is considered finished. NOTE 2: Major version changes are bac

Didip Kerabat 2.3k Aug 2, 2022
Simple, thread-safe Go rate-limiter

RateLimit Simple, thread-safe Go rate-limiter. Inspired by Antti Huima's algorithm on http://stackoverflow.com/a/668327 Example package main import (

Black Square Media 68 May 11, 2022
A timed rate limiter for Go

go-rate go-rate is a rate limiter designed for a range of use cases, including server side spam protection and preventing saturation of APIs you consu

Michael Alexander 363 Jul 27, 2022
Go package for rate limiter collection

rlc A rate limiter collection for Go. Pick up one of the rate limiters to throttle requests and control quota. RLC Slider TokenBucket RLC RLC is a rat

Alex Xu 15 Jul 6, 2021
This repository contains rest api implementation with golang

?? go-rest This repository contains rest api implementation with golang ⚡ LIVE To check out the live demo of this app ABOUT ?? Building a Rest API ??

null 3 Apr 20, 2022
An experimental GraphQL implementation with Go.

Description An experimental GraphQL implementation with Go. This repo focuses on improve GraphQL Parse and Resolve speed t

karminski-牙医 57 Jun 16, 2022
An efficient and feature complete Hystrix like Go implementation of the circuit breaker pattern.

Circuit Circuit is an efficient and feature complete Hystrix like Go implementation of the circuit breaker pattern. Learn more about the problems Hyst

Jack Lindamood 654 Jul 19, 2022
Minimalist net/http middleware for golang

interpose Interpose is a minimalist net/http middleware framework for golang. It uses http.Handler as its core unit of functionality, minimizing compl

James Pirruccello 295 Apr 5, 2022
Idiomatic HTTP Middleware for Golang

Negroni Notice: This is the library formerly known as github.com/codegangsta/negroni -- Github will automatically redirect requests to this repository

null 7.2k Aug 6, 2022
A tiny http middleware for Golang with added handlers for common needs.

rye A simple library to support http services. Currently, rye provides a middleware handler which can be used to chain http handlers together while pr

InVision 97 Feb 9, 2022
A golang framework like koa.js

koa.go Expressive HTTP middleware framework for Golang to make web applications and APIs more enjoyable to write like Koa.js. Koa's middleware stack f

Ya Hui Liang(Ryou) 28 Jul 28, 2022
A golang registry for global request variables.

context ?? This library is in maintenance mode. ⚠ ⚠ ⚠ Note ⚠ ⚠ ⚠ gorilla/context, having been born well before context.Context existed, does not play

Gorilla Web Toolkit 417 Jun 22, 2022
A Concurrent HTTP Static file server using golang .

A Concurrent HTTP static server using Golang. Serve Static files like HTML,CSS,Js,Images,Videos ,ect. using HTTP. It is Concurrent and Highly Scalable.Try now!

sambath kumar B 4 Dec 19, 2021
Ratelimit - This package provides a Golang implementation of the leaky-bucket rate limit algorithm

Go rate limiter This package provides a Golang implementation of the leaky-bucke

gofaquan 1 Jul 26, 2022
An idiomatic Go implementation of Leaky bucket.

lbucket lbucket is an idiomatic Go leaky bucket implementation. The library make use of plain old Go stdlib; in other words, there are no third-party

Alex Rios 11 Apr 17, 2022
Docker-hub-rate-limit - Show pulling rate status of Docker-hub

Docker-Hub Pull Rate Status This tool shows current status of docker hub pull ra

Tak 1 Jan 28, 2022
Pacemaker - Rate limit library. Currently implemented rate limits are

PaceMaker Rate limit library. Currently implemented rate limits are Fixed window

Marquitos 2 Apr 2, 2022
Resize upladed images to s3 bucket with given sizes, and uploades new images back to bucket

Features Resize upladed images to s3 bucket with given sizes, and uploades new images back to bucket Environment Variables IMAGE_SIZES - formax 200x20

null 1 Feb 2, 2022
Convert JPEG images from S3 bucket to BMP, GIF, PNG into another bucket

aws-lambda Convert JPEG images from S3 bucket to BMP, GIF, PNG into another bucket Setup two buckets jpeg-images for source jpeg images converted-jpeg

Volodymyr Tochytskyi 0 Feb 13, 2022
Limit-order-book - Limit order books keep records of orders for a given symbol to be traded

Limit Order Book Limit order books keep records of orders for a given symbol to

Michael Bowler 0 Jan 17, 2022
Efficient token-bucket-based rate limiter package.

ratelimit -- import "github.com/juju/ratelimit" The ratelimit package provides an efficient token bucket implementation. See http://en.wikipedia.org/w

Juju 2.4k Aug 3, 2022
Dead simple rate limit middleware for Go.

Limiter Dead simple rate limit middleware for Go. Simple API "Store" approach for backend Redis support (but not tied too) Middlewares: HTTP, FastHTTP

Ulule 1.6k Jul 29, 2022
Simple middleware to rate-limit HTTP requests.

Tollbooth This is a generic middleware to rate-limit HTTP requests. NOTE 1: This library is considered finished. NOTE 2: Major version changes are bac

Didip Kerabat 2.3k Aug 2, 2022
Dead simple rate limit middleware for Go.

Limiter Dead simple rate limit middleware for Go. Simple API "Store" approach for backend Redis support (but not tied too) Middlewares: HTTP, FastHTTP

Ulule 1.6k Aug 3, 2022
Simple middleware to rate-limit HTTP requests.

Tollbooth This is a generic middleware to rate-limit HTTP requests. NOTE 1: This library is considered finished. NOTE 2: Major version changes are bac

Didip Kerabat 2.3k Aug 2, 2022
Automatically create global & local Rate Limit in Istio, support EnvoyFilter versioning!

istio-ratelimit-operator Istio ratelimit operator provide an easy way to configure Global or Local Ratelimit in Istio mesh. Istio ratelimit operator a

Zufar Dhiyaulhaq 20 Jul 18, 2022
Dhrate - Quickly check Dockerhub rate (limit) as an unauthenticated user

Dockerhub Rate A small Go program that returns the Dockerhub rate of an unauthen

Michael Peter 0 Feb 7, 2022
A concurrent rate limiter library for Golang based on Sliding-Window rate limiter algorithm.

ratelimiter A generic concurrent rate limiter library for Golang based on Sliding-window rate limitng algorithm. The implementation of rate-limiter al

Narasimha Prasanna HN 216 Jul 27, 2022
A very simple rate limiter in go, made as a learning project to learn go and rate limiting patterns!

rate-limiter-go A very simple rate limiter in go, made as a learning project to learn go and rate limiting patterns! Demo: Running the project: To exe

Jean-Raphaël Poulin Arguin 1 Jun 1, 2022