bloomrate

Documentation

Index

• type BloomRate
  • func NewBloomRate(size int, hashes int, limit rate.Limit, burst int) *BloomRate
  • func (br *BloomRate) Allow(now time.Time, key []byte) bool
• type Rate
  • func (r *Rate) Allow(now time.Time, limit rate.Limit, burst int) bool

Types

type BloomRate

type BloomRate struct {
	// contains filtered or unexported fields
}

BloomRate is kind of like a count-min datastructure, kind of like a bloom filter. The problem it solves is rate limiting a huge number of event types independently, whereas it is okay if occasionally two event types collide and share the same rate limiter. The way it works is there is a large array of rate limiters, and when an event type is rate limited, the event is consistently hashed into the rate limiter array a few times, and if any of the rate limiters allow the event to occur, it occurs.

func NewBloomRate

func NewBloomRate(size int, hashes int, limit rate.Limit, burst int) *BloomRate

NewBloomRate creates a BloomRate with 2^`size` rate limits and `hashes` hashing functions. Rate limiting uses `limit` (events/sec) and `burst` parameters, see the documentation on Rate.

func (*BloomRate) Allow

func (br *BloomRate) Allow(now time.Time, key []byte) bool

Allow takes now as a timestamp and returns whether the current rate allows an event at that time, updating rate limits as appropriate to indicate that the event happened.

type Rate

type Rate atomic.Uint64

Rate is a rate limiter that uses a single uint64 word. The 10 least significant bits represent a counter that allows for burst behavior. As long as the current limiter hasn't expired, the counter is allowed to climb to the burst limit. The remaining 54 significant bits are a timestamp (treated as positive nanoseconds from Unix epoch, with the 9 least significant bits masked off, for a loss of granularity of about half a microsecond). This rate limiter cannot be configured to allow rates higher than 1,956,947 events/second. This timestamp is when the current counter expires. The expiry is bumped every time the counter is bumped. The zero value is valid and works as if no traffic has yet arrived. Note that the burst logic is not exact - there might be a slightly higher amount of requests let through than the provided burst limit, but not in the long term. Also note that this is not a token bucket design - the burst amount is allowed per time window, and the limit remains hit until the time window expires, at which point the burst limit is allowed through again. For this reason, smaller burst amounts are better than larger burst amounts.

func (*Rate) Allow

func (r *Rate) Allow(now time.Time, limit rate.Limit, burst int) bool

Allow takes now as a timestamp, the limit (events/second), and the burst amount, and returns whether the current rate allows it. It is intended that limit and burst are consistent and don't change across calls to Allow, but are stored elsewhere (see BloomRate).