RateLimiting

Rate Limiting

Time Tick based Approach

To limit the rate of operations per unit time, use time.Tick:

import "time"

rate_per_sec := 10
throttle := time.Tick(1e9 / rate_per_sec)
for req := range requests {
  <-throttle  // rate limit our Service.Method RPCs
  go client.Call("Service.Method", req, ...)
}

To allow some bursts, add a buffer to the throttle:

import "time"

rate_per_sec := 10
burst_limit := 100
tick := time.NewTicker(1e9 / rate_per_sec)
defer tick.Stop()
throttle := make(chan int64, burst_limit)
go func() {
  for ns := range tick {
    select {
      case: throttle <- ns
      default:
    }
  }  // exits after tick.Stop()
}()
for req := range requests {
  <-throttle  // rate limit our Service.Method RPCs
  go client.Call("Service.Method", req, ...)
}

Simpler Approach that doesn't need channels or go routines

Here is a simpler approach that relies on the notion of elapsed time to provide rate control. It is implemented as a package so others can readily use it.

//
// Ratelimiting incoming connections - Small Library
//
// (c) 2013 Sudhi Herle <sudhi-dot-herle-at-gmail-com>
//
// License: GPLv2
//
// Notes:
//  - This is a very simple interface for rate limiting. It
//    implements a token bucket algorithm
//  - Based on Anti Huimaa's very clever token bucket algorithm.
//
// Usage:
//    rl = NewRateLimiter(rate)
//
//    ....
//    if rl.Limit() {
//       drop_connection(conn)
//    }
//
package ratelimit

import "time"

type Ratelimiter struct {
	rate int       // conn/sec
	last time.Time // last time we were polled/asked

	allowance float64
}

// Create new rate limiter that limits at rate/sec
func NewRateLimiter(rate int) (*Ratelimiter, error) {

	r := Ratelimiter{rate: rate, last: time.Now()}

	r.allowance = float64(r.rate)
	return &r, nil
}

// Return true if the current call exceeds the set rate, false
// otherwise
func (r *Ratelimiter) Limit() bool {

	// handle cases where rate in config file is unset - defaulting
	// to "0" (unlimited)
	if r.rate == 0 {
		return false
	}

	rate := float64(r.rate)
	now := time.Now()
	elapsed := now.Sub(r.last)
	r.last = now
	r.allowance += float64(elapsed) * rate

	// Clamp number of tokens in the bucket. Don't let it get
	// unboundedly large
	if r.allowance > rate {
		r.allowance = rate
	}

	var ret bool

	if r.allowance < 1.0 {
		ret = true
	} else {
		r.allowance -= 1.0
		ret = false
	}

	return ret
}

Using this package is quite easy:

    // rate limit at 100/s
    nl = ratelimit.NewRateLimiter(100)

    ....
   // in your event loop or network accept loop, do:
   if rl.Limit() {
       // drop the connection etc.
       // i.e., this new event has exceeded the rate of 100/s
    ... 
   }
   else {
      // .. rate is not exceeded, process as needed
      ...
    }

Anti Huimaa came up with this simple algorithm.

References

time.Tick: http://golang.org/pkg/time/#Tick