simpleRateLimiter.go

// NewRateLimiter returns a rate limiter function returning false 
// when the event must be rejected, and true when it must be accepted. 
// The rate is expressed in Hz (events/seconds). It simply ensures that
// the time interval between two accept satisfies the rate criteria. It
// is equivalent to the token bucket algorithm with a bucket size of one.
func NewRateLimiter(rate float64) func() bool {
	var stamp time.Time // time stamp of last accepted event
	return func() bool {
		now := time.Now()
		if now.Sub(stamp).Seconds() *rate < 1. {
			return false
		}
		stamp = now
		return true
	}
}

// The following is a usage example with a rate limiting middelware.
func rateLimiter(rate float64, f http.HandlerFunc) http.HandlerFunc {
  rl := NewRateLimiter(rate)
  return func(w http.ResponseWriter, r *http.Request) {
    if !rl() {
      http.Error(w, "too many requests, retry later", http.StatusTooManyRequests)
      return
    }
    f(w, r)
  }
}

// some example server action
func hello(w http.ResponseWriter, r *http.Request) {
  fmt.Fprintln(w, "hello !")
}

func main() {
  http.HandleFunc("/", rateLimiter(1, hello)) // accept at most one request per second
  http.ListenAndServe(":8080", nil)
}

This is the most simple rate limiter that ensures that the rate of accepted events is always smaller or equal to the specified rate. It does so by simply ensuring that the time interval between two consecutive requests is not below the limit imposed by the rate. The benefit of this method is that all it needs is to keep track of the time stamp of the last accepted event.

This trivial algorithm is easily and efficiently adapted to a distributed architecture when the rate control must be shared among multiple instances (e.g. load balancing) or when a distinct rate control is to be applied on different kind of requests (e.g. per users).

It is not equivalent to ensuring that there is no more than n events in deltaT duration. This would require to keep track of the time stamps of at most the last n accepted events. The memory complexity is then O(n) instead of O(1) as with the above algorithm.

The rate controller may also be used for sampling at regular time interval.