[time] x/time/rate: provides a rate limiter.

[Sameer Ajmani (Gerrit)]

Reviewers: Russ Cox

Sameer Ajmani uploaded a change:
https://go-review.googlesource.com/16672

x/time/rate: provides a rate limiter.

The rate limiter works with golang.org/x/net/context's cancelation
mechanism: the Wait method blocks until the limiter permits the
operation to proceed or the context is canceled (in which case the
requested rate allocation is remitted for use by other operations).

Co-author: Arkadi Pyuro <ark...@google.com>

Change-Id: I841db4e61fd169ac119fdc43105a1e16ca97e0a2
---
A rate/rate.go
A rate/rate_test.go
2 files changed, 823 insertions(+), 0 deletions(-)



diff --git a/rate/rate.go b/rate/rate.go
new file mode 100644
index 0000000..a2fc2e7
--- /dev/null
+++ b/rate/rate.go
@@ -0,0 +1,369 @@
+// Package rate provides a rate limiter.
+package rate
+
+import (
+ "fmt"
+ "math"
+ "sync"
+ "time"
+
+ "golang.org/x/net/context"
+)
+
+// Inf is the infinite rate limit; it allows all events (even if burst is
zero).
+const Inf = Limit(math.MaxFloat64)
+
+// Limit defines the maximum frequency of some events.
+// Limit is represented as number of events per second.
+// A zero Limit allows no events.
+type Limit float64
+
+// Every converts a minimum time interval between events to a Limit.
+func Every(interval time.Duration) Limit {
+ if interval <= 0 {
+ return Inf
+ }
+ return 1 / Limit(interval.Seconds())
+}
+
+// Limiter controls the minimum interval between events.
+// The zero value is a valid Limiter, but it will reject all events.
+// Use NewLimiter to create non-zero Limiters.
+type Limiter struct {
+ limit Limit
+ burst int
+ drop bool
+
+ mu sync.Mutex
+ tokens float64
+ dropped int
+ // last is the last time the limiter's tokens field was updated
+ last time.Time
+ // lastEvent is the latest time of a rate-limited event (past or future)
+ lastEvent time.Time
+}
+
+// Limit is the maximum rate at which events may happen.
+func (lim *Limiter) Limit() Limit {
+ lim.mu.Lock()
+ defer lim.mu.Unlock()
+ return lim.limit
+}
+
+// Burst controls how tightly Limiter enforces limit. Burst is the
+// maximum n that AllowN accepts, so higher Burst values allow more
+// events to happen at once.
+// A zero Burst allows no events (unless limit == Inf).
+func (lim *Limiter) Burst() int {
+ return lim.burst
+}
+
+// Drop specifies how the Limiter behaves if time jumps backwards.
+// If true, the Limiter may drop events until the clock catches up;
+// otherwise the Limiter may exceed its Limit to catch up.
+// Drop is false by default; pass rate.Drop(true) to NewLimiter to enable
it.
+func (lim *Limiter) Drop() bool {
+ return lim.drop
+}
+
+// LimiterOption specifies additional options for NewLimiter
+type LimiterOption func(*Limiter)
+
+// Drop returns a LimiterOption which sets a Limiter's drop parameter,
which specifies
+// how the Limiter behaves if time jumps backwards. If true, the Limiter
may drop events
+// until the clock catches up; otherwise the Limiter may exceed its Limit
to catch up.
+func Drop(drop bool) LimiterOption {
+ return func(lim *Limiter) {
+ lim.drop = drop
+ }
+}
+
+// NewLimiter returns a new Limiter with parameters limit, burst,
+// and additional parameters specified by options.
+//
+// Limit is the maximum rate at which events may happen.
+// Burst controls how tightly the Limiter enforces the limit. Higher burst
+// values allow more events to happen at once. A zero burst allows no
events
+// unless limit == Inf.
+func NewLimiter(limit Limit, burst int, options ...LimiterOption) *Limiter
{
+ lim := &Limiter{
+ limit: limit,
+ burst: burst,
+ }
+ for _, op := range options {
+ op(lim)
+ }
+ return lim
+}
+
+// Allow is shorthand for AllowN(time.Now(), 1).
+func (lim *Limiter) Allow() (ok bool, dropped int) {
+ return lim.AllowN(time.Now(), 1)
+}
+
+// AllowN returns ok=true if n events may happen at time now. If ok=true,
+// dropped is the sum of all n since the last successful AllowN.
Otherwise,
+// ok=false and dropped includes this n.
+// Use this method if you intend to drop / skip events that exceed the
rate limit.
+// Otherwise use ReserveN or WaitN.
+func (lim *Limiter) AllowN(now time.Time, n int) (ok bool, dropped int) {
+ var zeroDuration time.Duration
+ _, dropped, ok = lim.reserveN(now, n, &zeroDuration)
+ return
+}
+
+// A Reservation holds information about events that are permitted by a
Limiter to happen after a delay.
+// A Reservation may be canceled, which may enable the Limiter to permit
additional events.
+type Reservation struct {
+ lim *Limiter
+ tokens int
+ timeToAct time.Time
+ // This is the Limit at reservation time, it can change later.
+ limit Limit
+}
+
+// Delay is shorthand for DelayFrom(time.Now())
+func (r Reservation) Delay() time.Duration {
+ return r.DelayFrom(time.Now())
+}
+
+// DelayFrom returns the duration for which the reservation holder must
wait before taking the reserved action.
+// Zero duration means act immediately.
+func (r Reservation) DelayFrom(now time.Time) time.Duration {
+ delay := r.timeToAct.Sub(now)
+ if delay < 0 {
+ return 0
+ }
+ return delay
+}
+
+// Cancel is shorthand for CancelAt(time.Now())
+func (r Reservation) Cancel() {
+ r.CancelAt(time.Now())
+ return
+}
+
+// CancelAt indicates that the reservation holder will not perform the
reserved action
+// and reverses the effects of this Reservation on the rate limit as much
as possible,
+// considering that other reservations may have already been made.
+func (r Reservation) CancelAt(now time.Time) {
+ r.lim.mu.Lock()
+ defer r.lim.mu.Unlock()
+
+ if r.lim.limit == Inf || r.tokens == 0 || r.timeToAct.Before(now) {
+ return
+ }
+
+ // calculate tokens to restore
+ // The duration between lim.lastEvent and r.timeToAct tells us how many
tokens were reserved
+ // after r was obtained. These tokens should not be restored.
+ restoreTokens := float64(r.tokens) -
r.limit.tokensFromDuration(r.lim.lastEvent.Sub(r.timeToAct))
+ if restoreTokens <= 0 {
+ return
+ }
+ // advance time to now
+ now, _, tokens := r.lim.advance(now)
+ // calculate new number of tokens
+ tokens += restoreTokens
+ if burst := float64(r.lim.burst); tokens > burst {
+ tokens = burst
+ }
+ // update state
+ r.lim.last = now
+ r.lim.tokens = tokens
+ if r.timeToAct == r.lim.lastEvent {
+ prevEvent :=
r.timeToAct.Add(r.limit.durationFromTokens(float64(-r.tokens)))
+ if !prevEvent.Before(now) {
+ r.lim.lastEvent = prevEvent
+ }
+ }
+
+ return
+}
+
+// Reserve is shorthand for ReserveN(time.Now(), 1)
+func (lim *Limiter) Reserve() (r Reservation, ok bool) {
+ return lim.ReserveN(time.Now(), 1)
+}
+
+// ReserveN returns a Reservation that indicates how long the caller must
wait before n events happen.
+// The Limiter takes this Reservation into account when allowing future
events.
+// ReserveN returns ok=false if n exceeds lim.burst.
+// Usage example:
+// r, ok := lim.ReserveN(time.Now(), 1)
+// if !ok {
+// // Not allowed to act! Did you remember to set lim.burst to be > 0 ?
+// }
+// time.Sleep(r.Delay())
+// Act()
+// Use this method if you wish to wait and slow down in accordance with
the rate limit without dropping events.
+// To drop or skip events exceeding rate limit, use AllowN instead.
+func (lim *Limiter) ReserveN(now time.Time, n int) (r Reservation, ok
bool) {
+ r, _, ok = lim.reserveN(now, n, nil)
+ return
+}
+
+// Wait is shorthand for WaitN(ctx, 1).
+func (lim *Limiter) Wait(ctx context.Context) (err error) {
+ return lim.WaitN(ctx, 1)
+}
+
+// WaitN blocks until lim permits n events to happen.
+// It returns an error if n exceeds lim.burst, ctx.Done is closed, or the
+// expected wait time exceeds ctx.Deadline.
+func (lim *Limiter) WaitN(ctx context.Context, n int) (err error) {
+ if n > lim.burst {
+ return fmt.Errorf("rate: Wait(n=%d) exceeds limiter's burst %d", n,
lim.burst)
+ }
+ // Check if ctx is already cancelled
+ select {
+ case <-ctx.Done():
+ return ctx.Err()
+ default:
+ }
+ // Determine wait limit
+ now := time.Now()
+ var waitLimit *time.Duration
+ if deadline, ok := ctx.Deadline(); ok {
+ waitToDeadline := deadline.Sub(now)
+ waitLimit = &waitToDeadline
+ }
+ // Reserve
+ r, _, ok := lim.reserveN(now, n, waitLimit)
+ if !ok {
+ return fmt.Errorf("rate: Wait(n=%d) would exceed context deadline", n)
+ }
+ // Wait
+ t := time.NewTimer(r.DelayFrom(now))
+ defer t.Stop()
+ select {
+ case <-t.C:
+ // We can proceed.
+ return nil
+ case <-ctx.Done():
+ // Context was canceled before we could proceed. Cancel the
+ // reservation, which may permit other events to proceed sooner.
+ r.Cancel()
+ return ctx.Err()
+ }
+}
+
+// SetLimit is shorthand for SetLimitAt(time.Now(), newLimit).
+func (lim *Limiter) SetLimit(newLimit Limit) {
+ lim.SetLimitAt(time.Now(), newLimit)
+}
+
+// SetLimitAt sets a new Limit for the limiter. The new Limit, and Burst,
may be violated
+// or underutilized by those which reserved (using Reserve/N or Wait/N)
but did not yet act
+// before SetLimitAt was called.
+func (lim *Limiter) SetLimitAt(now time.Time, newLimit Limit) {
+ lim.mu.Lock()
+ defer lim.mu.Unlock()
+
+ now, _, tokens := lim.advance(now)
+
+ lim.last = now
+ lim.tokens = tokens
+ lim.limit = newLimit
+}
+
+// reserveN is a helper method that implements Allow/N, Peek/N and
Reserve/N
+// maxFutureReserve specifies the maximum reservation wait duration
allowed (nil if there is no limit).
+func (lim *Limiter) reserveN(now time.Time, n int, maxFutureReserve
*time.Duration) (r Reservation, dropped int, ok bool) {
+ lim.mu.Lock()
+ defer lim.mu.Unlock()
+
+ if lim.limit == Inf {
+ return Reservation{
+ lim: lim,
+ tokens: n,
+ timeToAct: now,
+ }, 0, true
+ }
+
+ now, last, tokens := lim.advance(now)
+
+ // Calculate the remaining number of tokens resulting from the request.
+ tokens -= float64(n)
+
+ // Calculate the wait duration
+ var waitDuration time.Duration
+ if tokens < 0 {
+ waitDuration = lim.limit.durationFromTokens(-tokens)
+ }
+
+ // Decide result
+ if (n > lim.burst) || (maxFutureReserve != nil && waitDuration >
*maxFutureReserve) {
+ ok = false
+ } else {
+ ok = true
+ }
+
+ // Prepare reservation
+ r = Reservation{
+ lim: lim,
+ tokens: n,
+ timeToAct: now.Add(waitDuration),
+ limit: lim.limit,
+ }
+ if !ok {
+ r.tokens = 0
+ }
+
+ // Update state
+ if ok {
+ dropped = lim.dropped
+ lim.dropped = 0
+ lim.last = now
+ lim.tokens = tokens
+ lim.lastEvent = r.timeToAct
+ } else {
+ lim.dropped += n
+ dropped = lim.dropped
+ lim.last = last
+ }
+
+ return r, dropped, ok
+}
+
+// advance calculates and returns an updated state for lim resulting from
the passage of time.
+// lim is not changed.
+func (lim *Limiter) advance(now time.Time) (newNow time.Time, newLast
time.Time, newTokens float64) {
+ last := lim.last
+ if now.Before(last) {
+ if lim.drop {
+ now = last
+ } else {
+ last = now
+ }
+ }
+
+ // Avoid making delta overflow below when last is very old.
+ maxElapsed := lim.limit.durationFromTokens(float64(lim.burst) -
lim.tokens)
+ elapsed := now.Sub(last)
+ if elapsed > maxElapsed {
+ elapsed = maxElapsed
+ }
+
+ // Calculate the new number of tokens, due to time that passed.
+ delta := lim.limit.tokensFromDuration(elapsed)
+ tokens := lim.tokens + delta
+ if burst := float64(lim.burst); tokens > burst {
+ tokens = burst
+ }
+
+ return now, last, tokens
+}
+
+// durationFromTokens is a unit conversion function from the number of
tokens to the duration
+// of time it takes to accumulate them at a rate of limit tokens per second
+func (limit Limit) durationFromTokens(tokens float64) time.Duration {
+ seconds := tokens / float64(limit)
+ return time.Nanosecond * time.Duration(1e9*seconds)
+}
+
+// tokensFromDuration is a unit conversion function from a time duration
to the number of tokens
+// which could be accumulated during that duration at a rate of limit
tokens per second
+func (limit Limit) tokensFromDuration(d time.Duration) float64 {
+ return d.Seconds() * float64(limit)
+}
diff --git a/rate/rate_test.go b/rate/rate_test.go
new file mode 100644
index 0000000..8cf9119
--- /dev/null
+++ b/rate/rate_test.go
@@ -0,0 +1,454 @@
+package rate
+
+import (
+ "math"
+ "sync"
+ "sync/atomic"
+ "testing"
+ "time"
+
+ "golang.org/x/net/context"
+)
+
+func TestLimit(t *testing.T) {
+ if Limit(10) == Inf {
+ t.Errorf("Limit(10) == Inf should be false")
+ }
+}
+
+func closeEnough(a, b Limit) bool {
+ return (math.Abs(float64(a)/float64(b)) - 1.0) < 1e-9
+}
+
+func TestEvery(t *testing.T) {
+ cases := []struct {
+ interval time.Duration
+ lim Limit
+ }{
+ {0, Inf},
+ {-1, Inf},
+ {1 * time.Nanosecond, Limit(1e9)},
+ {1 * time.Microsecond, Limit(1e6)},
+ {1 * time.Millisecond, Limit(1e3)},
+ {10 * time.Millisecond, Limit(100)},
+ {100 * time.Millisecond, Limit(10)},
+ {1 * time.Second, Limit(1)},
+ {2 * time.Second, Limit(0.5)},
+ {time.Duration(2.5 * float64(time.Second)), Limit(0.4)},
+ {4 * time.Second, Limit(0.25)},
+ {10 * time.Second, Limit(0.1)},
+ {time.Duration(math.MaxInt64), Limit(1e9 / float64(math.MaxInt64))},
+ }
+ for _, tc := range cases {
+ lim := Every(tc.interval)
+ if !closeEnough(lim, tc.lim) {
+ t.Errorf("Every(%v) = %v want %v", tc.interval, lim, tc.lim)
+ }
+ }
+}
+
+const (
+ d = 100 * time.Millisecond
+)
+
+var (
+ t0 = time.Now()
+ t1 = t0.Add(time.Duration(1) * d)
+ t2 = t0.Add(time.Duration(2) * d)
+ t3 = t0.Add(time.Duration(3) * d)
+ t4 = t0.Add(time.Duration(4) * d)
+ t5 = t0.Add(time.Duration(5) * d)
+ t9 = t0.Add(time.Duration(9) * d)
+)
+
+type allow struct {
+ t time.Time
+ n int
+ ok bool
+ dropped int
+}
+
+func run(t *testing.T, lim *Limiter, allows []allow) {
+ for i, allow := range allows {
+ ok, dropped := lim.AllowN(allow.t, allow.n)
+ if ok != allow.ok || dropped != allow.dropped {
+ t.Errorf("step %d: lim.AllowN(%v, %v) = (%v, %v) want (%v, %v)",
+ i, allow.t, allow.n, ok, dropped, allow.ok, allow.dropped)
+ }
+ }
+}
+
+func TestLimiterBurst1(t *testing.T) {
+ run(t, NewLimiter(10, 1), []allow{
+ {t0, 1, true, 0},
+ {t0, 1, false, 1},
+ {t0, 1, false, 2},
+ {t1, 1, true, 2},
+ {t1, 1, false, 1},
+ {t1, 1, false, 2},
+ {t2, 2, false, 4}, // burst size is 1, so n=2 always fails
+ {t2, 1, true, 4},
+ {t2, 1, false, 1},
+ })
+}
+
+func TestLimiterBurst3(t *testing.T) {
+ run(t, NewLimiter(10, 3, Drop(false)), []allow{
+ {t0, 2, true, 0},
+ {t0, 2, false, 2},
+ {t0, 1, true, 2},
+ {t0, 1, false, 1},
+ {t1, 4, false, 5},
+ {t2, 1, true, 5},
+ {t3, 1, true, 0},
+ {t4, 1, true, 0},
+ {t4, 1, true, 0},
+ {t4, 1, false, 1},
+ {t4, 1, false, 2},
+ {t9, 3, true, 2},
+ {t9, 0, true, 0},
+ })
+}
+
+func TestLimiterJumpBackwards(t *testing.T) {
+ run(t, NewLimiter(10, 3), []allow{
+ {t1, 1, true, 0}, // start at t1
+ {t0, 1, true, 0}, // jump back to t0, two tokens remain
+ {t0, 1, true, 0},
+ {t0, 1, false, 1},
+ {t0, 1, false, 2},
+ {t1, 1, true, 2}, // got a token
+ {t1, 1, false, 1},
+ {t1, 1, false, 2},
+ {t2, 1, true, 2}, // got another token
+ {t2, 1, false, 1},
+ {t2, 1, false, 2},
+ })
+}
+
+func TestLimiterJumpBackwardsDrop(t *testing.T) {
+ run(t, NewLimiter(10, 3, Drop(true)), []allow{
+ {t1, 1, true, 0}, // start at t1
+ {t0, 1, true, 0}, // jump back to t0, two tokens remain
+ {t0, 1, true, 0},
+ {t0, 1, false, 1},
+ {t0, 1, false, 2},
+ {t1, 1, false, 3}, // clock still behind limiter, so no tokens
+ {t1, 1, false, 4},
+ {t1, 1, false, 5},
+ {t2, 1, true, 5}, // clock has caught up: got a new token, yay!
+ {t2, 1, false, 1},
+ {t2, 1, false, 2},
+ {t3, 1, true, 2}, // got another token
+ {t3, 1, false, 1},
+ })
+}
+
+func TestSimultaneousRequests(t *testing.T) {
+ const (
+ limit = 1
+ burst = 5
+ numRequests = 15
+ )
+ var (
+ wg sync.WaitGroup
+ numOK = uint32(0)
+ )
+
+ // Very slow replenishing bucket.
+ lim := NewLimiter(limit, burst)
+
+ // Tries to take a token, atomically updates the counter and decreases
the wait
+ // group counter.
+ f := func() {
+ defer wg.Done()
+ if ok, _ := lim.Allow(); ok {
+ atomic.AddUint32(&numOK, 1)
+ }
+ }
+
+ wg.Add(numRequests)
+ for i := 0; i < numRequests; i++ {
+ go f()
+ }
+ wg.Wait()
+ if numOK != burst {
+ t.Errorf("numOK = %d, want %d", numOK, burst)
+ }
+}
+
+func TestLongRunningQPS(t *testing.T) {
+ // The test runs for a few seconds executing many requests and then checks
+ // that overall number of requests is reasonable.
+ const (
+ limit = 100
+ burst = 100
+ )
+ var numOK = int32(0)
+
+ lim := NewLimiter(limit, burst)
+
+ var wg sync.WaitGroup
+ f := func() {
+ if ok, _ := lim.Allow(); ok {
+ atomic.AddInt32(&numOK, 1)
+ }
+ wg.Done()
+ }
+
+ start := time.Now()
+ end := start.Add(5 * time.Second)
+ for time.Now().Before(end) {
+ wg.Add(1)
+ go f()
+
+ // This will still offer ~500 requests per second, but won't consume
+ // outrageous amount of CPU.
+ time.Sleep(2 * time.Millisecond)
+ }
+ wg.Wait()
+ elapsed := time.Since(start)
+ ideal := burst + (limit * float64(elapsed) / float64(time.Second))
+
+ // We should never get more requests than allowed.
+ if want := int32(ideal + 1); numOK > want {
+ t.Errorf("numOK = %d, want %d (ideal %f)", numOK, want, ideal)
+ }
+ // We should get very close to the number of requests allowed.
+ if want := int32(0.999 * ideal); numOK < want {
+ t.Errorf("numOK = %d, want %d (ideal %f)", numOK, want, ideal)
+ }
+}
+
+type request struct {
+ t time.Time
+ n int
+ act time.Time
+ dropped int
+ ok bool
+}
+
+// dFromDuration converts a duration to a multiple of the global constant d
+func dFromDuration(dur time.Duration) int {
+ // Adding a millisecond to be swallowed by the integer division
+ // because we don't care about small inaccuracies
+ return int((dur + time.Millisecond) / d)
+}
+
+// dSince returns multiples of d since t0
+func dSince(t time.Time) int {
+ return dFromDuration(t.Sub(t0))
+}
+
+func runReserve(t *testing.T, lim *Limiter, req request) Reservation {
+ return runReserveMax(t, lim, req, nil)
+}
+
+func runReserveMax(t *testing.T, lim *Limiter, req request, maxReserve
*time.Duration) Reservation {
+ r, dropped, ok := lim.reserveN(req.t, req.n, maxReserve)
+ if dSince(r.timeToAct) != dSince(req.act) || dropped != req.dropped ||
ok != req.ok {
+ t.Errorf("lim.reserveN(t%d, %v, %v) = (t%d, %v, %v) want (t%d, %v, %v)",
+ dSince(req.t), req.n, maxReserve, dSince(r.timeToAct), dropped, ok,
dSince(req.act), req.dropped, req.ok)
+ }
+ return r
+}
+
+func TestSimpleReserve(t *testing.T) {
+ lim := NewLimiter(10, 2)
+
+ runReserve(t, lim, request{t0, 2, t0, 0, true})
+ runReserve(t, lim, request{t0, 2, t2, 0, true})
+ runReserve(t, lim, request{t3, 2, t4, 0, true})
+}
+
+func TestMix(t *testing.T) {
+ lim := NewLimiter(10, 2)
+
+ runReserve(t, lim, request{t0, 3, t1, 3, false}) // should return false
because n > Burst
+ runReserve(t, lim, request{t0, 2, t0, 3, true})
+ run(t, lim, []allow{{t1, 2, false, 2}}) // not enought tokens - don't
allow
+ runReserve(t, lim, request{t1, 2, t2, 2, true})
+ run(t, lim, []allow{{t1, 1, false, 1}}) // negative tokens - don't allow
+ run(t, lim, []allow{{t3, 1, true, 1}})
+}
+
+func TestCancelInvalid(t *testing.T) {
+ lim := NewLimiter(10, 2)
+
+ runReserve(t, lim, request{t0, 2, t0, 0, true})
+ r := runReserve(t, lim, request{t0, 3, t3, 3, false})
+ r.CancelAt(t0) // should have no effect
+ runReserve(t, lim, request{t0, 2, t2, 3, true}) // did not get extra
tokens
+}
+
+func TestCancelLast(t *testing.T) {
+ lim := NewLimiter(10, 2)
+
+ runReserve(t, lim, request{t0, 2, t0, 0, true})
+ r := runReserve(t, lim, request{t0, 2, t2, 0, true})
+ r.CancelAt(t1) // got 2 tokens back
+ runReserve(t, lim, request{t1, 2, t2, 0, true})
+}
+
+func TestCancelTooLate(t *testing.T) {
+ lim := NewLimiter(10, 2)
+
+ runReserve(t, lim, request{t0, 2, t0, 0, true})
+ r := runReserve(t, lim, request{t0, 2, t2, 0, true})
+ r.CancelAt(t3) // too late to cancel - should have no effect
+ runReserve(t, lim, request{t3, 2, t4, 0, true})
+}
+
+func TestCancel0Tokens(t *testing.T) {
+ lim := NewLimiter(10, 2)
+
+ runReserve(t, lim, request{t0, 2, t0, 0, true})
+ r := runReserve(t, lim, request{t0, 1, t1, 0, true})
+ runReserve(t, lim, request{t0, 1, t2, 0, true})
+ r.CancelAt(t0) // got 0 tokens back
+ runReserve(t, lim, request{t0, 1, t3, 0, true})
+}
+
+func TestCancel1Token(t *testing.T) {
+ lim := NewLimiter(10, 2)
+
+ runReserve(t, lim, request{t0, 2, t0, 0, true})
+ r := runReserve(t, lim, request{t0, 2, t2, 0, true})
+ runReserve(t, lim, request{t0, 1, t3, 0, true})
+ r.CancelAt(t2) // got 1 token back
+ runReserve(t, lim, request{t2, 2, t4, 0, true})
+}
+
+func TestCancelMulti(t *testing.T) {
+ lim := NewLimiter(10, 4)
+
+ runReserve(t, lim, request{t0, 4, t0, 0, true})
+ rA := runReserve(t, lim, request{t0, 3, t3, 0, true})
+ runReserve(t, lim, request{t0, 1, t4, 0, true})
+ rC := runReserve(t, lim, request{t0, 1, t5, 0, true})
+ rC.CancelAt(t1) // get 1 token back
+ rA.CancelAt(t1) // get 2 tokens back, as if C was never reserved
+ runReserve(t, lim, request{t1, 3, t5, 0, true})
+}
+
+func TestReserveJumpBack(t *testing.T) {
+ lim := NewLimiter(10, 2, Drop(false))
+
+ runReserve(t, lim, request{t1, 2, t1, 0, true}) // start at t1
+ runReserve(t, lim, request{t0, 1, t1, 0, true}) // should violate
Limit,Burst
+ runReserve(t, lim, request{t2, 2, t3, 0, true})
+}
+
+func TestReserveJumpBackCancel(t *testing.T) {
+ lim := NewLimiter(10, 2, Drop(false))
+
+ runReserve(t, lim, request{t1, 2, t1, 0, true}) // start at t1
+ r := runReserve(t, lim, request{t1, 2, t3, 0, true})
+ runReserve(t, lim, request{t1, 1, t4, 0, true})
+ r.CancelAt(t0) // cancel at t0, get 1
token back
+ runReserve(t, lim, request{t1, 2, t4, 0, true}) // should violate
Limit,Burst
+}
+
+func TestReserveJumpBackDrop(t *testing.T) {
+ lim := NewLimiter(10, 2, Drop(true))
+
+ runReserve(t, lim, request{t1, 2, t1, 0, true}) // start at t1
+ runReserve(t, lim, request{t0, 1, t2, 0, true}) // should not violate
Limit,Burst
+ runReserve(t, lim, request{t2, 2, t4, 0, true})
+}
+
+func TestReserveJumpBackCancelDrop(t *testing.T) {
+ lim := NewLimiter(10, 2, Drop(true))
+
+ runReserve(t, lim, request{t1, 2, t1, 0, true}) // start at t1
+ r := runReserve(t, lim, request{t1, 2, t3, 0, true})
+ runReserve(t, lim, request{t1, 1, t4, 0, true})
+ r.CancelAt(t0) // cancel at t0 - get 1
token back
+ runReserve(t, lim, request{t1, 2, t5, 0, true}) // should not violate
Limit,Burst
+}
+
+func TestReserveSetLimit(t *testing.T) {
+ lim := NewLimiter(5, 2)
+
+ runReserve(t, lim, request{t0, 2, t0, 0, true})
+ runReserve(t, lim, request{t0, 2, t4, 0, true})
+ lim.SetLimitAt(t2, 10)
+ runReserve(t, lim, request{t2, 1, t4, 0, true}) // violates Limit and
Burst
+}
+
+func TestReserveSetLimitCancel(t *testing.T) {
+ lim := NewLimiter(5, 2)
+
+ runReserve(t, lim, request{t0, 2, t0, 0, true})
+ r := runReserve(t, lim, request{t0, 2, t4, 0, true})
+ lim.SetLimitAt(t2, 10)
+ r.CancelAt(t2) // 2 tokens back
+ runReserve(t, lim, request{t2, 2, t3, 0, true})
+}
+
+func TestReserveMax(t *testing.T) {
+ lim := NewLimiter(10, 2)
+ maxT := d
+
+ runReserveMax(t, lim, request{t0, 2, t0, 0, true}, &maxT)
+ runReserveMax(t, lim, request{t0, 1, t1, 0, true}, &maxT) // reserve for
close future
+ runReserveMax(t, lim, request{t0, 1, t2, 1, false}, &maxT) // time to act
too far in the future
+}
+
+type wait struct {
+ name string
+ ctx context.Context
+ n int
+ delay int // in multiples of d
+ nilErr bool
+}
+
+func runWait(t *testing.T, lim *Limiter, w wait) {
+ start := time.Now()
+ err := lim.WaitN(w.ctx, w.n)
+ delay := time.Now().Sub(start)
+ if (w.nilErr && err != nil) || (!w.nilErr && err == nil) || w.delay !=
dFromDuration(delay) {
+ errString := "<nil>"
+ if !w.nilErr {
+ errString = "<non-nil error>"
+ }
+ t.Errorf("lim.WaitN(%v, lim, %v) = %v with delay %v ; want %v with
delay %v",
+ w.name, w.n, err, delay, errString, d*time.Duration(w.delay))
+ }
+}
+
+func TestWaitSimple(t *testing.T) {
+ lim := NewLimiter(10, 3)
+
+ ctx, cancel := context.WithCancel(context.Background())
+ cancel()
+ runWait(t, lim, wait{"already-cancelled", ctx, 1, 0, false})
+
+ runWait(t, lim, wait{"n-gt-burst", context.Background(), 4, 0, false})
+
+ runWait(t, lim, wait{"act-now", context.Background(), 2, 0, true})
+ runWait(t, lim, wait{"act-later", context.Background(), 3, 2, true})
+}
+
+func TestWaitCancel(t *testing.T) {
+ lim := NewLimiter(10, 3)
+
+ ctx, cancel := context.WithCancel(context.Background())
+ runWait(t, lim, wait{"act-now", ctx, 2, 0, true}) // after this
lim.tokens = 1
+ go func() {
+ time.Sleep(d)
+ cancel()
+ }()
+ runWait(t, lim, wait{"will-cancel", ctx, 3, 1, false})
+ // should get 3 tokens back, and have lim.tokens = 2
+ t.Logf("tokens:%v last:%v lastEvent:%v", lim.tokens, lim.last,
lim.lastEvent)
+ runWait(t, lim, wait{"act-now-after-cancel", context.Background(), 2, 0,
true})
+}
+
+func TestWaitTimeout(t *testing.T) {
+ lim := NewLimiter(10, 3)
+
+ ctx, _ := context.WithTimeout(context.Background(), d)
+ runWait(t, lim, wait{"act-now", ctx, 2, 0, true})
+ runWait(t, lim, wait{"w-timeout-err", ctx, 3, 0, false})
+}

--
https://go-review.googlesource.com/16672
Gerrit-Reviewer: Russ Cox <r...@golang.org>

[Brad Fitzpatrick (Gerrit)]

Brad Fitzpatrick has posted comments on this change.

x/time/rate: provides a rate limiter.

Patch Set 1:

(4 comments)

Thanks for releasing this.

https://go-review.googlesource.com/#/c/16672/1/rate/rate.go
File rate/rate.go:

Line 1: // Package rate provides a rate limiter.
missing copyright


Line 126: func (r Reservation) Delay() time.Duration {
Reservations is kinda borderline large for having value-typed methods, no?

I guess you want it to not allocate, returning from Limiter.Reserve, huh?
If so, add a comment inside the "type Reservation struct" saying so and why.

I'd also include a warning to not add more fields and to keep the struct
small.


Line 184: // Reserve is shorthand for ReserveN(time.Now(), 1)
end in a period? You do on e.g. line 206.


https://go-review.googlesource.com/#/c/16672/1/rate/rate_test.go
File rate/rate_test.go:

Line 1: package rate
copyright


--
https://go-review.googlesource.com/16672
Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>
Gerrit-Reviewer: Russ Cox <r...@golang.org>
Gerrit-HasComments: Yes

[Sameer Ajmani (Gerrit)]

Sameer Ajmani uploaded a new patch set:

https://go-review.googlesource.com/16672

x/time/rate: provides a rate limiter.

The rate limiter works with golang.org/x/net/context's cancelation
mechanism: the Wait method blocks until the limiter permits the
operation to proceed or the context is canceled (in which case the
requested rate allocation is remitted for use by other operations).

Co-author: Arkadi Pyuro <ark...@google.com>

Change-Id: I841db4e61fd169ac119fdc43105a1e16ca97e0a2
---
A rate/rate.go
A rate/rate_test.go

2 files changed, 831 insertions(+), 0 deletions(-)

[Sameer Ajmani (Gerrit)]

Sameer Ajmani has posted comments on this change.

x/time/rate: provides a rate limiter.

Patch Set 1:

(4 comments)

https://go-review.googlesource.com/#/c/16672/1/rate/rate.go
File rate/rate.go:

Line 1: // Package rate provides a rate limiter.
> missing copyright
Done

Line 126: func (r Reservation) Delay() time.Duration {
> Reservations is kinda borderline large for having value-typed methods, no?

Changed to *Reservation (rsc made the same comment).

Line 184: // Reserve is shorthand for ReserveN(time.Now(), 1)
> end in a period? You do on e.g. line 206.

Done

https://go-review.googlesource.com/#/c/16672/1/rate/rate_test.go
File rate/rate_test.go:

Line 1: package rate
> copyright

Done

--
https://go-review.googlesource.com/16672
Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>
Gerrit-Reviewer: Russ Cox <r...@golang.org>

Gerrit-Reviewer: Sameer Ajmani <sam...@golang.org>
Gerrit-HasComments: Yes

[Sameer Ajmani]

Updated.  Not sure if it sent mail.

[Brad Fitzpatrick]

It did email, but I wasn't sure whether I was the correct reviewer here.

I thought I was just making some drive-by comments.

If I'm the best/only reviewer, let me know?

[Sameer Ajmani]

You appear to be the only reviewer, and therefore the best reviewer. Ever.

[Russ Cox (Gerrit)]

Russ Cox has posted comments on this change.

x/time/rate: provides a rate limiter.

Patch Set 2:

(3 comments)

I'll review it too. I didn't realize it was originally addressed to me, and
I saw Brad commenting, and I figured you'd ask if you wanted my comments
specifically. But now that I look, there are things that could use
adjustment.

More comments to follow. These might not make sense just yet but I can't
send this message without sending the 3 comments below.

https://go-review.googlesource.com/#/c/16672/2/rate/rate.go
File rate/rate.go:

Line 50: // Limit is the maximum rate at which events may happen.
Limit returns the maximum overall event rate.


Line 57: // Burst controls how tightly Limiter enforces limit. Burst is the
Burst returns the maximum burst size.


Line 65: // Drop specifies how the Limiter behaves if time jumps backwards.
Can we drop this from the API? I really don't want to see discussion of
time jumping backwards.

--
https://go-review.googlesource.com/16672
Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>
Gerrit-Reviewer: Russ Cox <r...@golang.org>

[Russ Cox (Gerrit)]

Russ Cox has posted comments on this change.

x/time/rate: provides a rate limiter.

Patch Set 2:

(4 comments)

https://go-review.googlesource.com/#/c/16672/2/rate/rate.go
File rate/rate.go:

Line 33: // Limiter controls the minimum interval between events.
// A Limiter controls how frequently events can happen.
// It is defined by two settings, limit and burst.
// The limit is the target average number of events per second,
// and the burst is the number of events allowed beyond that average
// at any point in time.
// That is, in any given time interval of t seconds,
// the Limiter allows at most t*limit + burst events.
//
// A Limiter is safe for simultaneous use by multiple goroutines.
//
// The zero Limiter has limit and burst set to 0 and therefore allows no
events.

// Use NewLimiter to create non-zero Limiters.

This might be missing discussion of Inf, depending on what the semantics of
Inf actually are.

Also given that SetLimit exists I don't see why one must use NewLimiter to
create non-zero Limiters. And why is there SetLimit but not SetBurst?
And if we have setters, why do we have options too? Why not make the
options just more setters?

Line 65: // Drop specifies how the Limiter behaves if time jumps backwards.
> Can we drop this from the API? I really don't want to see discussion of
> tim

If not, at the least this definition belongs on the Drop option
constructor, not here. The text here makes it sound like Drop (this method)
_does_ something. It doesn't - it's just a getter.

// Drop returns the Limiter's Drop option setting.


Line 76: // Drop returns a LimiterOption which sets a Limiter's drop
parameter, which specifies
The bool here is unnecessary. The default must be one or the other of the
settings. It's confusing to have both. I don't actually understand the
settings being described. The bool should go away and the overall comment
should look like:

// Drop returns a LimiterOption that causes the Limiter to XXX.
// By default, the Limiter does YYY.


Line 87: //
Delete from here down. Leave the definition on the type.

[Russ Cox (Gerrit)]

Russ Cox has posted comments on this change.

x/time/rate: provides a rate limiter.

Patch Set 2:

(3 comments)

https://go-review.googlesource.com/#/c/16672/2/rate/rate.go
File rate/rate.go:

Line 33: // Limiter controls the minimum interval between events.
> // A Limiter controls how frequently events can happen.

// A Limiter controls how frequently events are allowed to happen.
// It implements a "token bucket" of size b, initially full and refilled
// at rate r tokens per second.
// Informally, in any large enough time interval, the Limiter limits the
// rate to r tokens per second, with a maximum burst size of b events.
// As a special case, if r == Inf (the infinite rate), b is ignored.
// See https://en.wikipedia.org/wiki/Token_bucket for more about token
buckets.

more here just a brief mention of Allow, Reserve, Wait.


Line 276: func (lim *Limiter) reserveN(now time.Time, n int,
maxFutureReserve *time.Duration) (r *Reservation, dropped int, ok bool) {
If you make this result a non-pointer (just Reservation) then you can avoid
allocation in functions like AllowN that do not return a *Reservation to
the client.


Line 300: if (n > lim.burst) || (maxFutureReserve != nil && waitDuration >
*maxFutureReserve) {
ok = n <= lim.burst && (maxFutureReserve == nil || waitDuration <=
*maxFutureReserve)

Would be simpler with

const maxDuration = time.Duration(uint64(^0))

and then pass in maxDuration instead of nil and make maxFutureReserve a
plain time.Duration, not a pointer. (As written nil means infinity but a
real infinity would be simpler.)

[Sameer Ajmani (Gerrit)]

Sameer Ajmani uploaded a new patch set:

https://go-review.googlesource.com/16672

x/time/rate: provides a rate limiter.

The rate limiter works with golang.org/x/net/context's cancelation
mechanism: the Wait method blocks until the limiter permits the
operation to proceed or the context is canceled (in which case the
requested rate allocation is remitted for use by other operations).

Co-author: Arkadi Pyuro <ark...@google.com>

Change-Id: I841db4e61fd169ac119fdc43105a1e16ca97e0a2
---
A rate/rate.go
A rate/rate_test.go

2 files changed, 772 insertions(+), 0 deletions(-)

[Sameer Ajmani (Gerrit)]

Sameer Ajmani has posted comments on this change.

x/time/rate: provides a rate limiter.

Patch Set 2:

(8 comments)

https://go-review.googlesource.com/#/c/16672/2/rate/rate.go
File rate/rate.go:

Line 33: // Limiter controls the minimum interval between events.

> // A Limiter controls how frequently events are allowed to happen.

Done

Line 50: // Limit is the maximum rate at which events may happen.
> Limit returns the maximum overall event rate.

Done

Line 57: // Burst controls how tightly Limiter enforces limit. Burst is the
> Burst returns the maximum burst size.

Done


Line 65: // Drop specifies how the Limiter behaves if time jumps backwards.

> If not, at the least this definition belongs on the Drop option
> constructor

Done


Line 76: // Drop returns a LimiterOption which sets a Limiter's drop
parameter, which specifies

> The bool here is unnecessary. The default must be one or the other of the
> s

Done

Line 87: //
> Delete from here down. Leave the definition on the type.

Done

Line 276: func (lim *Limiter) reserveN(now time.Time, n int,
maxFutureReserve *time.Duration) (r *Reservation, dropped int, ok bool) {
> If you make this result a non-pointer (just Reservation) then you can
> avoid

Done


Line 300: if (n > lim.burst) || (maxFutureReserve != nil && waitDuration >
*maxFutureReserve) {

> ok = n <= lim.burst && (maxFutureReserve == nil || waitDuration <=
> *maxFutu

Done

--
https://go-review.googlesource.com/16672
Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>
Gerrit-Reviewer: Russ Cox <r...@golang.org>
Gerrit-Reviewer: Sameer Ajmani <sam...@golang.org>

Gerrit-HasComments: Yes

[Sameer Ajmani (Gerrit)]

Sameer Ajmani has posted comments on this change.

x/time/rate: provides a rate limiter.

Patch Set 3:

(1 comment)

https://go-review.googlesource.com/#/c/16672/3/rate/rate.go
File rate/rate.go:

PS3, Line 76: LimiterOption
Now that we've dropped Drop, there are no remaining options. Should we
drop LimiterOption, too, or retain it to permit future expansion? This
package is not covered by the Go1 compatibility guarantee, but my
experience inside Google is that even adding variadic parameters to an
existing function can break client code.

[Russ Cox (Gerrit)]

Russ Cox has posted comments on this change.

x/time/rate: provides a rate limiter.

Patch Set 3:

(2 comments)

(So I would probably suggest dropping LimiterOption.)

https://go-review.googlesource.com/#/c/16672/2/rate/rate.go
File rate/rate.go:

Line 113: }
The 'dropped' result is completely unused in Google except for the test.
Lets drop it.

https://go-review.googlesource.com/#/c/16672/3/rate/rate.go
File rate/rate.go:

PS3, Line 76: LimiterOption
> Now that we've dropped Drop, there are no remaining options. Should we
> dro

The question is whether you want to support future options by
using ...LimiterOption as here or by adding explicit setters. Drop had
both, which was a bit weird. Given that there are already some setters,
saying we'll do future options with setters doesn't seem so bad.

[Russ Cox (Gerrit)]

Russ Cox has posted comments on this change.

x/time/rate: provides a rate limiter.

Patch Set 3:

(6 comments)

this looks awful below but i think it looks good on the actual diff view.

https://go-review.googlesource.com/#/c/16672/3/rate/rate.go
File rate/rate.go:

Line 44: // Limiter has three main methods, Allow, Reserve, and Wait.
I think I would break the usual alphabetical rule and describe Wait first,
since we think it's the common one, right?

// Limiter's most commonly-used method is Wait, which consumes a token.
// Wait consumes a token. If no tokens are available, Wait blocks as
necessary until one becomes
// available or the Wait is cancelled using a context.Context.
//
// The methods Allow and Reserve are lower-level forms of that operation.
// Allow consumes a token. If no tokens are available, Allow returns false.
// Reserve consumes a token. If no tokens are available, Reserve consumes
// a future token and reports how long the caller must wait before using it.

Not perfectly thrilled with that but it's getting there.

// Limiter has three main methods: Allow, Reserve, and Wait.
// Most callers should use Wait.
//
// Each of the three methods consumes a single token.
// They differ in their behavior when no token is available.
// If no token is available, Allow returns false.
// If no token is available, Reserve returns a reservation for a future
token
// and the amount of time the caller must wait before using it.
// If no token is available, Wait blocks until one can be obtained
// or its associated context.Context is cancelled.


Line 45: // Allow attempts to consume n tokens and returns whether it
succeeded.
s/returns whether/reports whether/


Line 46: // Reserve consumes n tokens and returns how long the caller must
wait before
s/returns/reports/


Line 48: // Wait blocks until it can consume n tokens or until the provided
Context's
... provided Context is cancelled? Context is closed? Is there some less
operational description of what the condition is?


Line 69: // Burst returns the maximum burst size. Burst is the maximum n
that AllowN
The mention of AllowN is


Line 213: case <-ctx.Done():
Does this work with ctx==nil? It would be nice to be able to pass ctx==nil
to mean I don't have a deadline (maybe I don't use contexts at all). Or is
the idea that people should be forced to use a context?

[Sameer Ajmani (Gerrit)]

Sameer Ajmani uploaded a new patch set:

https://go-review.googlesource.com/16672

x/time/rate: provides a rate limiter.

The rate limiter works with golang.org/x/net/context's cancelation
mechanism: the Wait method blocks until the limiter permits the
operation to proceed or the context is canceled (in which case the
requested rate allocation is remitted for use by other operations).

Co-author: Arkadi Pyuro <ark...@google.com>

Change-Id: I841db4e61fd169ac119fdc43105a1e16ca97e0a2
---
A rate/rate.go
A rate/rate_test.go

2 files changed, 773 insertions(+), 0 deletions(-)

[Sameer Ajmani (Gerrit)]

Sameer Ajmani has posted comments on this change.

x/time/rate: provides a rate limiter.

Patch Set 3:

(7 comments)

https://go-review.googlesource.com/#/c/16672/2/rate/rate.go
File rate/rate.go:

Line 113: }
> The 'dropped' result is completely unused in Google except for the test.
> Le

Done

https://go-review.googlesource.com/#/c/16672/3/rate/rate.go
File rate/rate.go:

Line 44: // Limiter has three main methods, Allow, Reserve, and Wait.
> I think I would break the usual alphabetical rule and describe Wait first,

Done


Line 46: // Reserve consumes n tokens and returns how long the caller must
wait before
> s/returns/reports/
Done

Line 48: // Wait blocks until it can consume n tokens or until the provided
Context's
> ... provided Context is cancelled? Context is closed? Is there some less
> op

Done

Line 69: // Burst returns the maximum burst size. Burst is the maximum n
that AllowN
> The mention of AllowN is

Done


PS3, Line 76: LimiterOption

> The question is whether you want to support future options by
> using ...Limi

Done

Line 213: case <-ctx.Done():
> Does this work with ctx==nil? It would be nice to be able to pass ctx==nil

No, we don't support ctx==nil, and neither do the functions in package
context. This is intentional: since Context is an interface, it's awkward
for functions that take a Context to handle nil gracefully. Passing
context.Background or context.TODO is the right solution (depending on
whether the call site may ever get a context later).

Callers who just want to Wait with no context can call lim.Reserve then
time.Sleep(r.Delay()).

--
https://go-review.googlesource.com/16672
Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>
Gerrit-Reviewer: Russ Cox <r...@golang.org>
Gerrit-Reviewer: Sameer Ajmani <sam...@golang.org>

Gerrit-HasComments: Yes

[Russ Cox (Gerrit)]

Russ Cox has posted comments on this change.

x/time/rate: provides a rate limiter.

Patch Set 3:

(1 comment)

https://go-review.googlesource.com/#/c/16672/3/rate/rate.go
File rate/rate.go:

Line 213: case <-ctx.Done():

> No, we don't support ctx==nil, and neither do the functions in package
> cont

It seems unreasonable that in a simple program that just wants to space out
its requests I can't just use plain "Wait". I understand wanting to
incorporate context, but I am less convinced about forcing it on people.
Maybe there should be Wait(), WaitN(n int), and WaitContext(ctx
context.Context, n int). Or maybe Wait should be able to deal with ctx==nil.

[Sameer Ajmani (Gerrit)]

Sameer Ajmani has posted comments on this change.

x/time/rate: provides a rate limiter.

Patch Set 3:

(1 comment)

https://go-review.googlesource.com/#/c/16672/3/rate/rate.go
File rate/rate.go:

Line 213: case <-ctx.Done():

> It seems unreasonable that in a simple program that just wants to space
> out

Why can't they just write
if r, ok := lim.Reserve(); ok {
time.Sleep(r.Delay())
}
You could even ignore ok if you know burst is large enough.

[Sameer Ajmani (Gerrit)]

Sameer Ajmani has posted comments on this change.

x/time/rate: provides a rate limiter.

Patch Set 3:

(1 comment)

https://go-review.googlesource.com/#/c/16672/3/rate/rate.go
File rate/rate.go:

Line 213: case <-ctx.Done():

> Why can't they just write

We could simplify this even further by removing the ok boolean from
lim.Reserve and making it panic if n > burst. Then the user just writes
time.Sleep(lim.Reserve().Delay()).

This might be bad though if we support lim.SetBurst later.

[Sameer Ajmani (Gerrit)]

Sameer Ajmani has posted comments on this change.

x/time/rate: provides a rate limiter.

Patch Set 3:

(1 comment)

https://go-review.googlesource.com/#/c/16672/3/rate/rate.go
File rate/rate.go:

Line 213: case <-ctx.Done():

> We could simplify this even further by removing the ok boolean from
> lim.Res

I just audited all the uses of (*rate.Limiter).Wait inside Google, and none
of them pass context.Background() to Wait; they all pass some more-specific
ctx. I think it's reasonable to expect that most uses of Wait should be
using a context.

[Russ Cox (Gerrit)]

Russ Cox has posted comments on this change.

x/time/rate: provides a rate limiter.

Patch Set 4:

I wonder if the Reservation should have an Err() error method, so that
Reserve and ReserveN can return just a *Reservation. Then code that knows
it is passing a constant N < burst size (like 1) can use

time.Sleep(r.Reserve().Delay())

The changes to Reservation would be:
- add Err() error method
- have Delay, DelayFrom, Cancel, CancelAt panic if the reservation is
invalid (if Err() != nil)
- return *Reservation, not (*Reservation, bool) from
rate.Reserve, .ReserveN.

An argument could also be made for making Delay, DelayFrom return a very
long time and Cancel, CancelAt be no-ops on invalid reservations. That
would make things like a select with case <-time.After(reserved.Delay())
work properly instead of panic.

I'm okay with either one, as long as it makes waiting without cancellation
a one-line call provided I know I'm not exceeding the burst limit.

--
https://go-review.googlesource.com/16672
Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>
Gerrit-Reviewer: Russ Cox <r...@golang.org>
Gerrit-Reviewer: Sameer Ajmani <sam...@golang.org>

Gerrit-HasComments: No

[Sameer Ajmani (Gerrit)]

Sameer Ajmani uploaded a new patch set:

https://go-review.googlesource.com/16672

x/time/rate: provides a rate limiter.

The rate limiter works with golang.org/x/net/context's cancelation
mechanism: the Wait method blocks until the limiter permits the
operation to proceed or the context is canceled (in which case the
requested rate allocation is remitted for use by other operations).

Co-author: Arkadi Pyuro <ark...@google.com>

Change-Id: I841db4e61fd169ac119fdc43105a1e16ca97e0a2
---
A rate/rate.go
A rate/rate_test.go

2 files changed, 789 insertions(+), 0 deletions(-)

[Sameer Ajmani (Gerrit)]

Sameer Ajmani has posted comments on this change.

x/time/rate: provides a rate limiter.

Patch Set 5:

Done. Called the method OK() instead of Err(), and made Delay return a
large duration and Cancel a no-op if the reservation is not OK.

> I wonder if the Reservation should have an Err() error method, so
> that Reserve and ReserveN can return just a *Reservation. Then code
> that knows it is passing a constant N < burst size (like 1) can use
>
> time.Sleep(r.Reserve().Delay())
>
> The changes to Reservation would be:
> - add Err() error method
> - have Delay, DelayFrom, Cancel, CancelAt panic if the reservation
> is invalid (if Err() != nil)
> - return *Reservation, not (*Reservation, bool) from rate.Reserve,
> .ReserveN.
>
> An argument could also be made for making Delay, DelayFrom return a
> very long time and Cancel, CancelAt be no-ops on invalid
> reservations. That would make things like a select with case
> <-time.After(reserved.Delay()) work properly instead of panic.
>
> I'm okay with either one, as long as it makes waiting without
> cancellation a one-line call provided I know I'm not exceeding the
> burst limit.

--
https://go-review.googlesource.com/16672
Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>
Gerrit-Reviewer: Russ Cox <r...@golang.org>
Gerrit-Reviewer: Sameer Ajmani <sam...@golang.org>

Gerrit-HasComments: No

[Russ Cox (Gerrit)]

Russ Cox has posted comments on this change.

x/time/rate: provides a rate limiter.

Patch Set 5: Code-Review+2

[Sameer Ajmani (Gerrit)]

Sameer Ajmani has submitted this change and it was merged.

x/time/rate: provides a rate limiter.

The rate limiter works with golang.org/x/net/context's cancelation
mechanism: the Wait method blocks until the limiter permits the
operation to proceed or the context is canceled (in which case the
requested rate allocation is remitted for use by other operations).

Co-author: Arkadi Pyuro <ark...@google.com>

Change-Id: I841db4e61fd169ac119fdc43105a1e16ca97e0a2

Reviewed-on: https://go-review.googlesource.com/16672
Reviewed-by: Russ Cox <r...@golang.org>

---
A rate/rate.go
A rate/rate_test.go

2 files changed, 789 insertions(+), 0 deletions(-)

Approvals:
Russ Cox: Looks good to me, approved