restrictor

README

restrictor

This is a rate limiter using sliding window counter algorithm implemented with Golang.

Other libraries which uses 'token bucket'(in 'time/rate' standard library) only support 'request per second' senario. This library can support 'xx request per xx minutes(or hours or days)'.

How to get

go get github.com/EagleChen/restrictor

How to use

// first, create a 'store' to store various limiters for each key
store, err := NewMemoryStore()
// in case there are many backend servers using one central limiter store
// use 'NewRedisStore' instead

// second, create restrictor
// 500 request every 5 minutes
// 60 is the internal bucket number. This number will affect the deviation
// Usually pick some number from 60 to 100.
r := NewRestrictor(5 * time.Minute, 500, 60, store)

// third, check limit
// yourKey might be an IP addr, a user id, etc.
if reached, err := r.LimitReached(yourKey); reached || err != nil {
    // limit is reached or some error returned, notify uesr
} else {
    // go on do the real job
}

What is the 'internal bucket number' for?

Under high load, requests(limit check times) in a window may be very large. It's not efficient to store all the request with timestamp. Instead, this implementation divides a window into many 'buckets'. Each 'bucket' is to record the request count in a short time(during rate calculation, all the requests in one bucket seems like happening at the same time). Say there are 10 billion requests in a window, in case of 60 buckets, it's enough to use 60 numbers to record the requests. It's much more CPU and Memory efficient.

However, this kind of 'approximation' will make the rate limiter not very accurate. Larger number of buckets means more accurate but less efficient, so please choose your 'bucket number' according to your use senario.

Other Related Resource

Related Blog Post(in Chinese): 访问频率限制——窗口相关算法

Documentation

Overview

Package restrictor is a generated protocol buffer package.

It is generated from these files:

limiter.proto

It has these top-level messages:

Limiter

Index

• Variables
• type Limiter
  • func NewLimiter() *Limiter
  • func (*Limiter) Descriptor() ([]byte, []int)
  • func (this *Limiter) Equal(that interface{}) bool
  • func (m *Limiter) GetBuckets() map[uint32]uint32
  • func (lmt *Limiter) GetCount(window uint32, now time.Time) (total uint32)
  • func (m *Limiter) GetFullUntil() uint32
  • func (this *Limiter) GoString() string
  • func (lmt *Limiter) LimitReached(window, upperLimit, interval uint32, now time.Time) (reached bool, count uint32, lmtChanged bool, expireChanged bool)
  • func (m *Limiter) Marshal() (dAtA []byte, err error)
  • func (m *Limiter) MarshalTo(dAtA []byte) (int, error)
  • func (*Limiter) ProtoMessage()
  • func (m *Limiter) Reset()
  • func (m *Limiter) Size() (n int)
  • func (this *Limiter) String() string
  • func (m *Limiter) Unmarshal(dAtA []byte) error
• type Restrictor
  • func NewRestrictor(window time.Duration, limit, numberOfBuckets uint32, store Store) Restrictor
  • func (r *Restrictor) GetCount(key string, window time.Duration) (count uint32, err error)
  • func (r *Restrictor) LimitReached(key string) (bool, error)
  • func (r *Restrictor) LimitReachedAtTime(now time.Time, key string) (bool, error)
  • func (r *Restrictor) LimitReachedAtTimeWithCount(now time.Time, key string) (bool, uint32, error)
  • func (r *Restrictor) LimitReachedWithCount(key string) (bool, uint32, error)
• type Store
  • func NewMemoryStore() (Store, error)
  • func NewRedisStore(rawurl string, options ...redis.DialOption) (Store, error)

Variables

var (
	ErrInvalidLengthLimiter = fmt.Errorf("proto: negative length found during unmarshaling")
	ErrIntOverflowLimiter   = fmt.Errorf("proto: integer overflow")
)

Types

type Limiter

type Limiter struct {
	FullUntil uint32            `protobuf:"varint,2,opt,name=fullUntil,proto3" json:"fullUntil,omitempty"`
	Buckets   map[uint32]uint32 `` /* 150-byte string literal not displayed */
}

func NewLimiter

func NewLimiter() *Limiter

NewLimiter creates a limiter

func (*Limiter) Descriptor

func (*Limiter) Descriptor() ([]byte, []int)

func (*Limiter) Equal

func (this *Limiter) Equal(that interface{}) bool

func (*Limiter) GetBuckets

func (m *Limiter) GetBuckets() map[uint32]uint32

func (*Limiter) GetCount

func (lmt *Limiter) GetCount(window uint32, now time.Time) (total uint32)

GetCount returns count of objects in bucket within defined time window. Does not modify data (read only).

func (*Limiter) GetFullUntil

func (m *Limiter) GetFullUntil() uint32

func (*Limiter) GoString

func (this *Limiter) GoString() string

func (*Limiter) LimitReached

func (lmt *Limiter) LimitReached(window, upperLimit, interval uint32,
	now time.Time) (reached bool, count uint32, lmtChanged bool, expireChanged bool)

LimitReached checks whether limits reached side effect: the limiter itself is modified if limit is not reached yet

func (*Limiter) Marshal

func (m *Limiter) Marshal() (dAtA []byte, err error)

func (*Limiter) MarshalTo

func (m *Limiter) MarshalTo(dAtA []byte) (int, error)

func (*Limiter) ProtoMessage

func (*Limiter) ProtoMessage()

func (*Limiter) Reset

func (m *Limiter) Reset()

func (*Limiter) Size

func (m *Limiter) Size() (n int)

func (*Limiter) String

func (this *Limiter) String() string

func (*Limiter) Unmarshal

func (m *Limiter) Unmarshal(dAtA []byte) error

type Restrictor

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

Restrictor holds general information of limits

func NewRestrictor

func NewRestrictor(window time.Duration, limit, numberOfBuckets uint32,
	store Store) Restrictor

NewRestrictor creates a restrictor window should not be too large, it will be converted to 'seconds' limit is the max number of requests allowed in a window numberOfBuckets is number of buckets in the sliding window, usually around 100

func (*Restrictor) GetCount

func (r *Restrictor) GetCount(key string, window time.Duration) (count uint32, err error)

GetCount returns number of records 'now' within defined time window. Does not modify data (read only).

func (*Restrictor) LimitReached

func (r *Restrictor) LimitReached(key string) (bool, error)

LimitReached check whether limit has been reached now

func (*Restrictor) LimitReachedAtTime

func (r *Restrictor) LimitReachedAtTime(now time.Time, key string) (bool, error)

LimitReachedAtTime check whether limit has been reached at time 'now'

func (*Restrictor) LimitReachedAtTimeWithCount

func (r *Restrictor) LimitReachedAtTimeWithCount(now time.Time, key string) (bool, uint32, error)

LimitReachedAtTimeWithCount check whether limit has been reached at time 'now'

func (*Restrictor) LimitReachedWithCount

func (r *Restrictor) LimitReachedWithCount(key string) (bool, uint32, error)

LimitReachedWithCount check whether limit has been reached now and returns current count for key within time window.

type Store

type Store interface {
	GetLimiter(key string) (*Limiter, time.Time, bool)
	// expireAfter is in seconds
	SetLimiter(key string, value *Limiter, expireAfter int) error

	TryLock(key, mark string) (bool, error)
	Unlock(key, mark string) error
}

Store is the interface for central storage

func NewMemoryStore

func NewMemoryStore() (Store, error)

NewMemoryStore creates an in-memory store

func NewRedisStore

func NewRedisStore(rawurl string, options ...redis.DialOption) (Store, error)

NewRedisStore creates an store using redis