Rate Limiting the right way

By Vagmi on 11 Nov 2016

While dealing with external services you would want to throttle requests. In Go, its pretty simple to implement it with something like this.

1
2
3
4
5
6
rate := time.Second / 10 // 10 requests a second
limit := time.Tick(rate)
for req := range messages {
	<-rate
	go makeRequest(req)
}

While this works for tens of operations a second, this does not scale for 1000s of operations a second. We have been working with an AMQP queue that needs to be drained with back pressure. Our downstream system is sending SMSs using a gateway and can only send a prescribed amount of SMSs but it is greater than tens of operations a second. There is a supplementary time package which provides rate limiting that works with token buckets.

The token bucket is an algorithm used in packet switched computer networks and telecommunications networks. It can be used to check that data transmissions, in the form of packets, conform to defined limits on bandwidth and burstiness (a measure of the unevenness or variations in the traffic flow). It can also be used as a scheduling algorithm to determine the timing of transmissions that will comply with the limits set for the bandwidth and burstiness. - Wikipedia

So you start off by creating a limit which defines the interval. For example, if you would like for 2000 events a minute.

1
2
3
ratePerMin := float64(2000)
intervalMsec := time.Duration((1/ratePerMin)*60*1000) * time.Millisecond
limit := rate.Every(intervalMsec)

You would then create a limiter that would setup the burst rate per second. So in our case you would want something like this.

1
limiter := rate.NewLimiter(limit, 33)

Then you can reserve a token and sleep for the duration indicated by the reservation.

1
2
3
4
5
6
7
8
9
10
11
count := 0
go func() {
	for {
		r := limiter.Reserve()
		if !r.OK() {
			return
		}
		time.Sleep(r.Delay())
		count++
	}
}()

You can verify if things are going fine by printing the value every second.

1
2
3
4
5
6
7
8
9
10
11
secondTimer := time.Tick(1 * time.Second)
go func() {
	for {
		currTime := <-secondTimer
		fmt.Printf(
			"at %v the count is %d\n",
			currTime.Format("15:04:05"),
			count,
		)
	}
}()

You can also reserve multiple tokens at a time and do as many operations. This will ensure that the scheduling overhead on the goroutine is avoided.

comments powered by Disqus