README
¶
limits
Lock-free, space efficient, probabilistic data structures for counting things.
Usage
Estimator
An Estimator is an implementation of the count-min sketch
data structure. It can be used to estimate the count of occurrences for
different keys.
est := NewEstimator[string]()
n := est.Incr("key")
println(n) // Prints "1"
n = est.Get("key")
println(n) // Prints "1"
Rate
Rate allows for the estimation of occurrences for different keys in a given
interval. Internally, it uses two Estimators to keep track of the current
interval, as well as one full interval in the past.
Observing an event will increment the count for the provided key, and return the estimated number of occurences in the current interval.
r := NewRate[string](time.Second)
n := r.Observe("key")
println(n) // Prints "1"
You may also obtain the estimated number of occurences in the last full interval
by using the Get method.
r := NewRate[string](time.Second)
n := r.Observe("key"")
println(n) // Prints "1"
n = r.Get("key")
println(n) // Prints "0"
time.Sleep(time.Second)
n = r.Get("key")
println(n) // Prints "1"
A full rate limiting implementation will likely want to check the value of the current interval, as well as the last "full" interval. This is because the current interval may have just started, and thus the value may not be accurate as an estimation of the actual number of occurences per interval period.
// Allow 10 requests per second
const rps = 10
var limiter = NewRate[string](time.Second)
func AllowRequest(key string) bool {
// Increment count, and check the total in the current interval.
if n := limiter.Observe("key"); n > rps {
return false
}
// Check the count in the last full interval.
if n := limiter.Get("key"); n > rps {
return false
}
return true
}
License
Apache-2.0 license
Documentation
¶
Index ¶
Constants ¶
const ( // DefaultHashes represents the default value for the number of hashes. DefaultHashes = 4 // DefaultSlots represents the default value for the number of slots. DefaultSlots = 8192 )
const ( // DefaultRateHashes represents the default value for the number of hashes. DefaultRateHashes = 4 // DefaultRateSlots represents the default value for the number of slots. DefaultRateSlots = 1024 )
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Estimator ¶
type Estimator[K Key] struct { // contains filtered or unexported fields }
Estimator is an implementation of the count-min sketch data structure.
An Estimator instance is lock-free, but is safe to use concurrency from multiple goroutines.
For more info: https://en.wikipedia.org/wiki/Count%E2%80%93min_sketch
func NewEstimator ¶
NewEstimator returns a new Estimator instance using the default hash and slot sizes.
func NewEstimatorWithSize ¶
NewEstimatorWithSize returns a new Estimator instance using the provided number of hashes and slots. This function panics if hashes or slots are less than or equal to zero.
type Rate ¶
type Rate[K Key] struct { // contains filtered or unexported fields }
Rate is a probabilistic rate estimator over a given interval. Internally, it uses multiple `Estimator`s to track the number of events per key.
A Rate instance is lock-free, but is safe to use concurrency from multiple goroutines.
func NewRate ¶
NewRate returns a new Rate instance using the provided interval and default sizes. NewRate panics if interval is smaller than 1 millisecond.
func NewRateWithSize ¶
NewRateWithSize returns a new Rate instance using the provided interval and hash/slot sizes. NewRateWithSize panics if interval is smaller than 1 millisecond.
Source Files