Efficient token-bucket-based rate limiter package.

Related tags

ratelimit
Overview

ratelimit

-- import "github.com/juju/ratelimit"

The ratelimit package provides an efficient token bucket implementation. See http://en.wikipedia.org/wiki/Token_bucket.

Usage

func Reader

func Reader(r io.Reader, bucket *Bucket) io.Reader

Reader returns a reader that is rate limited by the given token bucket. Each token in the bucket represents one byte.

func Writer

func Writer(w io.Writer, bucket *Bucket) io.Writer

Writer returns a writer that is rate limited by the given token bucket. Each token in the bucket represents one byte.

type Bucket

type Bucket struct {
}

Bucket represents a token bucket that fills at a predetermined rate. Methods on Bucket may be called concurrently.

func NewBucket

func NewBucket(fillInterval time.Duration, capacity int64) *Bucket

NewBucket returns a new token bucket that fills at the rate of one token every fillInterval, up to the given maximum capacity. Both arguments must be positive. The bucket is initially full.

func NewBucketWithQuantum

func NewBucketWithQuantum(fillInterval time.Duration, capacity, quantum int64) *Bucket

NewBucketWithQuantum is similar to NewBucket, but allows the specification of the quantum size - quantum tokens are added every fillInterval.

func NewBucketWithRate

func NewBucketWithRate(rate float64, capacity int64) *Bucket

NewBucketWithRate returns a token bucket that fills the bucket at the rate of rate tokens per second up to the given maximum capacity. Because of limited clock resolution, at high rates, the actual rate may be up to 1% different from the specified rate.

func (*Bucket) Available

func (tb *Bucket) Available() int64

Available returns the number of available tokens. It will be negative when there are consumers waiting for tokens. Note that if this returns greater than zero, it does not guarantee that calls that take tokens from the buffer will succeed, as the number of available tokens could have changed in the meantime. This method is intended primarily for metrics reporting and debugging.

func (*Bucket) Rate

func (tb *Bucket) Rate() float64

Rate returns the fill rate of the bucket, in tokens per second.

func (*Bucket) Take

func (tb *Bucket) Take(count int64) time.Duration

Take takes count tokens from the bucket without blocking. It returns the time that the caller should wait until the tokens are actually available.

Note that if the request is irrevocable - there is no way to return tokens to the bucket once this method commits us to taking them.

func (*Bucket) TakeAvailable

func (tb *Bucket) TakeAvailable(count int64) int64

TakeAvailable takes up to count immediately available tokens from the bucket. It returns the number of tokens removed, or zero if there are no available tokens. It does not block.

func (*Bucket) TakeMaxDuration

func (tb *Bucket) TakeMaxDuration(count int64, maxWait time.Duration) (time.Duration, bool)

TakeMaxDuration is like Take, except that it will only take tokens from the bucket if the wait time for the tokens is no greater than maxWait.

If it would take longer than maxWait for the tokens to become available, it does nothing and reports false, otherwise it returns the time that the caller should wait until the tokens are actually available, and reports true.

func (*Bucket) Wait

func (tb *Bucket) Wait(count int64)

Wait takes count tokens from the bucket, waiting until they are available.

func (*Bucket) WaitMaxDuration

func (tb *Bucket) WaitMaxDuration(count int64, maxWait time.Duration) bool

WaitMaxDuration is like Wait except that it will only take tokens from the bucket if it needs to wait for no greater than maxWait. It reports whether any tokens have been removed from the bucket If no tokens have been removed, it returns immediately.

Issues
  • Bucket: expose Available() and Capacity()

    Bucket: expose Available() and Capacity()

    Hi,

    The current token bucket implementation is great. Nonetheless we need some underlying data to implement more powerful functionalities.

    For example, if we want to implement a function CanAccept which only checks available tokens without taking it; implement a function that exports rate limiter's metrics to better understand current flow and bottleneck on our services. Both functions will benefit if we can get the underlying data like avail and capacity, including the already public Rate().

    Let me know if there are questions. Highly appreciate it if anyone can help review this issue. Thanks!

    opened by hongchaodeng 7
  • Please tag a release

    Please tag a release

    It'd be very helpful if you could tag a release. Thanks!

    https://dave.cheney.net/2016/06/24/gophers-please-tag-your-releases

    opened by fd0 5
  • Add a Clock interface for testing

    Add a Clock interface for testing

    This adds an interface that is used internally to allow a caller to intercept calls to time.Now() and time.Sleep(), and do better testing.

    Fixes #17

    @howbazaar this is about as simple as it gets. Unfortunately the factory functions are a bit tedious. Could be changed to "WithDeps" (or something like that) and have a Deps struct, but for now that is going to hold exactly 1 field. This code is simple enough that it probably won't accumulate more. Your call.

    opened by thockin 4
  • Bonus Token by adjustavailableTokens

    Bonus Token by adjustavailableTokens

    I noticed that inside the function adjustavailableTokens()

    func (tb *Bucket) adjustavailableTokens(tick int64) {
    	if tb.availableTokens >= tb.capacity {
    		return
    	}
    	tb.availableTokens += (tick - tb.latestTick) * tb.quantum
    	if tb.availableTokens > tb.capacity {
    		tb.availableTokens = tb.capacity
    	}
    	tb.latestTick = tick
    	return
    }
    

    the tb.latestTick is not updated if tb.availableTokens >= tb.capacity

    That makes the description of the variable latestTick holds the latest tick for which we know the number of tokens in the bucket. not so accurate, IMO.

    And I wrote a snippet of code which can produce surprising results:

    func main() {
    	bucket := ratelimit.NewBucketWithQuantum(time.Second*1, 100, 20)
    	fmt.Printf("Avail=%d\n", bucket.Available())
    
    	fmt.Printf("%v\n", time.Now())
    	fmt.Printf("Pause wait for 5s\n")
    	time.Sleep(time.Second * 5)
    	fmt.Printf("%v\n", time.Now())
    	fmt.Printf("Avail=%d\n", bucket.Available())
    
    	fmt.Printf("Request token up to 100\n")
    	cnt := bucket.TakeAvailable(100)
    	fmt.Printf("Token taken=%d\n", cnt)
    
            // It will surprise you.
    	fmt.Printf("Avail=%d\n", bucket.Available())
    }
    

    Output

    Avail=100                                                                                          
    2019-09-26 01:12:47.9410106 +0800 CST m=+0.003992001                                                Pause wait for 5s                                                                                   
    2019-09-26 01:12:52.9614404 +0800 CST m=+5.024421801                                                Avail=100                                                                                           
    Request token up to 100                                                                             
    Token taken=100                                                                                     
    Avail=100             
    

    That is, after taken all tokens out of the bucket, the bucket is still full.

    Is this by design or just an implementation bug?

    opened by kingsamchen 3
  • testing through ratelimit

    testing through ratelimit

    We use ratelimit in Kubernetes. I am working on something that uses it, and I am trying to write a test that doesn't actually take a long time to run. As part of that I inject a fake clock interface. It works really well until it hits the ratelimiter logic.

    ratelimit uses time.Now() and time.Sleep() internally. Would you be opposed to something like NewBucketWithClock(..., clock Clock) where Clock was an interface that wrapped time.Now() and similar functions? Users who don't care will ignore it and get the default (which just calls the real time.Now()) and users who do care could provide a mocked clock. If that is OK, I can try to work up a quick patch.

    Or is there a better way to test through this? I really don't want my test doing a bunch of 100ms sleeps to try to prove that it behaves. I will have a number of cases to test and that adds up fast.

    opened by thockin 2
  • test juju bot integration

    test juju bot integration

    opened by nammn 2
  • bug when system clock rollback

    bug when system clock rollback

    please see this unit test:

    type mockClock struct {
    	mutex sync.RWMutex
    	realStartTime time.Time
    	startTime time.Time
    }
    
    func newMockClock() *mockClock {
    	now := time.Now()
    	return &mockClock{
    		realStartTime: now,
    		startTime: now,
    	}
    }
    
    func (mc *mockClock) Now() time.Time {
    	mc.mutex.RLock()
    	defer mc.mutex.RUnlock()
    	return mc.startTime.Add(time.Now().Sub(mc.realStartTime))
    }
    
    func (mc *mockClock) Sleep(d time.Duration) {
    	time.Sleep(d)
    }
    
    func (mc *mockClock) RollBack(d time.Duration) {
    	mc.mutex.Lock()
    	defer mc.mutex.Unlock()
    	mc.startTime = mc.startTime.Add(-d)
    }
    
    func TestSystemClockRollBack(t *testing.T) {
    	mc := newMockClock()
    	bucket := NewBucketWithRateAndClock(10, 1, mc)
    
    	if bucket.TakeAvailable(1) != 1 {
    		t.Fail()
    	}
    	time.Sleep(time.Second / 10 + 1)
    	if bucket.TakeAvailable(1) != 1 {
    		t.Fail()
    	}
    	time.Sleep(time.Second / 10 + 1)
    	mc.RollBack(time.Hour * 8)
    	bucket.TakeAvailable(1) 
    	time.Sleep(time.Second / 10 + 1)
    	if bucket.TakeAvailable(1) != 1 {
    		t.Fail()
    	}
    	time.Sleep(time.Second / 10 + 1)
    	if bucket.TakeAvailable(1) != 1 {
    		t.Fail()
    	}
    }
    
    opened by qw4990 2
  • Removed defered mutex unlocks in favor of explicit calls

    Removed defered mutex unlocks in favor of explicit calls

    I've been playing around with a few potential changes to this package for potential speed improvements and found that the act of defering the mutex unlocks is a significant slow down to this package. Once these were removed and appropriate adjustments made in the code it appears to have resulted in an 3 times increase in parallel calls to Wait().

    Before:

    go test -bench . -benchmem -cpu 1,2,4,8
    
    PASS
    BenchmarkWait           10000000               152 ns/op               0 B/op          0 allocs/op
    BenchmarkWait-2         10000000               155 ns/op               0 B/op          0 allocs/op
    BenchmarkWait-4         10000000               153 ns/op               0 B/op          0 allocs/op
    BenchmarkWait-8         10000000               152 ns/op               0 B/op          0 allocs/op
    BenchmarkWaitParallel   10000000               160 ns/op               0 B/op          0 allocs/op
    BenchmarkWaitParallel-2 10000000               164 ns/op               0 B/op          0 allocs/op
    BenchmarkWaitParallel-4 10000000               178 ns/op               0 B/op          0 allocs/op
    BenchmarkWaitParallel-8 10000000               185 ns/op               0 B/op          0 allocs/op
    

    After:

    go test -bench . -benchmem -cpu 1,2,4,8
    
    PASS
    BenchmarkWait           30000000                56.1 ns/op             0 B/op          0 allocs/op
    BenchmarkWait-2         30000000                56.0 ns/op             0 B/op          0 allocs/op
    BenchmarkWait-4         30000000                55.8 ns/op             0 B/op          0 allocs/op
    BenchmarkWait-8         30000000                55.8 ns/op             0 B/op          0 allocs/op
    BenchmarkWaitParallel   30000000                56.9 ns/op             0 B/op          0 allocs/op
    BenchmarkWaitParallel-2 30000000                59.3 ns/op             0 B/op          0 allocs/op
    BenchmarkWaitParallel-4 20000000                68.1 ns/op             0 B/op          0 allocs/op
    BenchmarkWaitParallel-8 20000000                70.8 ns/op             0 B/op          0 allocs/op
    
    opened by curlymon 2
  • Does method ratelimit.go , Bucket.abjust has a bug ?

    Does method ratelimit.go , Bucket.abjust has a bug ?

    I'm new in github. Found your package small and more understandable then others.

    But little confused with tb.avail in Bucket.abjust:

    tb.avail += (currentTick - tb.availTick) * tb.quantum

    why used just currentTick , but not currentTick * tb.capacity.

    For example, we have

    t0----------------t1---------------t2 dt = t1-t0 = t2-t1 currentTick = int64(t2.Sub(t0) / dt) = 2. But in such interval [t0,t2] we must have 2 * tb.capacity tokens in the bucket, not just 2.

    opened by stdpmk 2
  • I believe capacity is broken?

    I believe capacity is broken?

    I'm trying out setting a bucket that makes 1 token per second w/ a max of 1 token waiting. Unclear what I'm doing wrong.

    package main
    
    import (
      "fmt"
      "time"
    
      "github.com/juju/ratelimit"
    )
    
    func main() {
      fmt.Printf("[DEBUG]: Creating bucket with capacity = %d\n", 1)
      ratelimiter := ratelimit.NewBucketWithRate(float64(1), 1)
      ticker := time.NewTicker(1 * time.Second)
      quit := make(chan struct{})
      go func() {
        for {
          select {
          case <-ticker.C:
            fmt.Printf("[DEBUG]: current bucket tokens = %d/%d\n", ratelimiter.Available, ratelimiter.Capacity)
            fmt.Printf("%#v\n", ratelimiter)
          case <-quit:
            ticker.Stop()
            return
          }
        }
      }()
    
      block := make(chan bool)
      block <- true
    }
    

    output:

    [DEBUG]: Creating bucket with capacity = 1
    [DEBUG]: current bucket tokens = 8784/8848
    (repeated)
    

    Expected: I figured that it would have a capacity of 1 available and capacity of 1. I'm seeing similar issues using other values than 1 .

    opened by MaerF0x0 1
  • Can you remove Lock

    Can you remove Lock

    In the process of using ratelimit,there's a lock in the source code . can you replace it with atomic?

    func (tb *Bucket) TakeAvailable(count int64) int64 { tb.mu.Lock() defer tb.mu.Unlock() return tb.takeAvailable(tb.clock.Now(), count) }

    opened by maczam 1
  • invalid pseudo-version: tag (v1.0.1) found on revision 59fac5042749 is already canonical, so should not be replaced with a pseudo-version derived from that tag

    invalid pseudo-version: tag (v1.0.1) found on revision 59fac5042749 is already canonical, so should not be replaced with a pseudo-version derived from that tag

    when i use go mod to install this package, it shows up

    cannot load github.com/juju/ratelimit: github.com/juju/[email protected]: invalid pseudo-version: tag (v1.0.1) found on revision 59fac5042749 is already canonical, so should not be replaced with a pseudo-version derived from that tag
    

    looks wrong tag are build?

    opened by Petelin 9
  • Concerns about license of the project.

    Concerns about license of the project.

    Since this project is a common utils, and used by many other open source projects as a vendor dependency, LGPLv3 with static-linking exception may be controversial in some situation for Go language libraries.

    Many open source libraries in Go in licensed in MIT/BSD/Apache, so is it possible to change the license for the project to more permissive license (e.g. MIT/BSD/Apache) or dual license (e.g. LGPL + MIT) ?

    I found similar discuss in https://github.com/davidmoreno/onion/issues/56

    @kingsamchen @nammn

    Thanks!

    opened by chyh1990 0
  • Func `Wait` in package ratelimit could got blocked if time moves backwards for any reason

    Func `Wait` in package ratelimit could got blocked if time moves backwards for any reason

    We import package ratelimit in Kubernetes and met a scenario, not sure whether the issue should be filed here. The scenario is that when time happened moves backwards for any reason, func take that calculate the time to sleep would get a huge number here:

    	endTick := currentTick + (-avail+tb.quantum-1)/tb.quantum
    	endTime := tb.startTime.Add(time.Duration(endTick) * tb.fillInterval)
    	waitTime := endTime.Sub(now)
    	if waitTime > maxWait {
    		return 0, false
    	}
    

    An available way for the issue might be adding a protection before calculating waitTime, say a comparision between now and startTime.

    /cc @thockin

    opened by lichuqiang 1
  • Changing rate on the fly

    Changing rate on the fly

    Hello,

    I'll be honest - my attempt at this was quite unsuccessful as I am not sure I understand the algorithm 100% .. so I'm creating an issue to get your thoughts.

    I would like to change the rate dynamically. I added a SetRate method to the bucket that basically creates and sets a new fillInterval and quantum.. but clearly this is incorrect as the speed of the bucket becomes exponentially slower until it eventually hits zero and stops completely.

    Any advice?

    Cheers,

    Simon

    opened by simon-whitehead 1
Owner
Juju
Juju
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 338 Jul 15, 2021
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 2k Jul 27, 2021
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
A Golang blocking leaky-bucket rate limit implementation

Go rate limiter This package provides a Golang implementation of the leaky-bucket rate limit algorithm. This implementation refills the bucket based o

Uber Go 2.4k Jul 22, 2021
gorilla/csrf provides Cross Site Request Forgery (CSRF) prevention middleware for Go web applications & services 🔒

gorilla/csrf gorilla/csrf is a HTTP middleware library that provides cross-site request forgery (CSRF) protection. It includes: The csrf.Protect middl

Gorilla Web Toolkit 676 Jul 19, 2021
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 66 May 3, 2021
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 Jun 6, 2021
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 582 Jul 21, 2021
HTTP/2 Apple Push Notification service (APNs) provider for Go with token-based connection

APNs Provider HTTP/2 Apple Push Notification service (APNs) provider for Go with token-based connection Example: key, err := apns.AuthKeyFromFile("Aut

Vitaly Berg 14 Jul 11, 2021
Sentinel Go version (Reliability & Resilience)

Sentinel: The Sentinel of Your Microservices Introduction As distributed systems become increasingly popular, the reliability between services is beco

Alibaba 1.6k Jul 20, 2021
Mahi is an all-in-one HTTP service for file uploading, processing, serving, and storage.

Mahi is an all-in-one HTTP service for file uploading, processing, serving, and storage. Mahi supports chunked, resumable, and concurrent uploads. Mahi uses Libvips behind the scenes making it extremely fast and memory efficient.

Rodrigo Lessa 30 Jul 7, 2021
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 7k Jul 23, 2021
Go package for easily rendering JSON, XML, binary data, and HTML templates responses.

Render Render is a package that provides functionality for easily rendering JSON, XML, text, binary data, and HTML templates. This package is based on

Cory Jacobsen 1.5k Jul 27, 2021
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 290 Jun 21, 2021