Golang implementation of Sliding Window Algorithm for distributed rate limiting.

Overview

slidingwindow

Golang implementation of Sliding Window Algorithm for distributed rate limiting.

Installation

$ go get -u github.com/RussellLuo/slidingwindow

Design

slidingwindow is an implementation of the scalable rate limiting algorithm used by Kong.

Suppose we have a limiter that permits 100 events per minute, and now the time comes at the "75s" point, then the internal windows will be as below:

slidingwindow

In this situation, the limiter has permitted 12 events during the current window, which started 15 seconds ago, and 86 events during the entire previous window. Then the count approximation during the sliding window can be calculated like this:

count = 86 * ((60-15)/60) + 12
      = 86 * 0.75 + 12
      = 76.5 events

Test Utility

prom_reports

For details, see testutil.

Documentation

For usage and examples see the Godoc.

License

MIT

Issues
  • Expose windows Count

    Expose windows Count

    Hi!

    I would like to propose exposing the Count of the curr and prev windows inside Limiter. On my usage, I have a map with values of type Limiter, and I would like to remove keys from the map according to whether the inner Counter of a limiter is empty (zero).

    Would very much appreciate it, thanks in advance!

    opened by giladlev23 19
  • Limiter starts out allowing too many through?

    Limiter starts out allowing too many through?

    Using the below code (clone-able from gist here), I expect to see output like:

    [{allowed:1000 disallowed:12445195} {allowed:1001 disallowed:12568861} {allowed:999 disallowed:12469467}]
    

    But instead I get this kind of thing:

    [{allowed:1553 disallowed:12445195} {allowed:1001 disallowed:12568861} {allowed:999 disallowed:12469467}]
    

    Note that the first 1-second bucket allowed 1553 rather than 1000. The exact number varies between runs, but it's always significantly more than 1000.

    Why is that? (Is it something about the handling of the "previous" window when there is no previous?)

    I'm concerned because I plan on aggressively removing limiters when they haven't been used for a few windows (because that would be a rate limit reset anyway), but I don't really want to frequently go over the limit by ~50%.

    package main
    
    import (
    	"fmt"
    	"time"
    
    	sw "github.com/RussellLuo/slidingwindow"
    )
    
    func main() {
    	const histogramBucketSize = time.Second
    	const totalBuckets = 3
    	const allowedPerBucket = 1000
    
    	type histoEntry struct {
    		allowed    int64
    		disallowed int64
    	}
    	allowedHistogram := make([]histoEntry, totalBuckets)
    
    	lim, _ := sw.NewLimiter(histogramBucketSize, allowedPerBucket, func() (sw.Window, sw.StopFunc) {
    		return sw.NewLocalWindow()
    	})
    
    	start := time.Now()
    	for {
    		bucket := time.Now().Sub(start) / histogramBucketSize
    
    		if bucket >= totalBuckets {
    			break
    		}
    
    		if lim.Allow() {
    			allowedHistogram[bucket].allowed++
    		} else {
    			allowedHistogram[bucket].disallowed++
    		}
    	}
    
    	fmt.Printf("%+v\n", allowedHistogram)
    }
    
    opened by adam-p 7
  • Add LICENSE

    Add LICENSE

    Just mentioning in the README won't be enough, the license file also should be present with the source code.

    Also, godoc refuses to display the docs, since it does not have a license - https://pkg.go.dev/github.com/RussellLuo/slidingwindow?tab=doc

    opened by avinassh 5
  • Multiple windows per one synchronizer

    Multiple windows per one synchronizer

    Good day!

    Is it possible to use one synchronizer with multiple windows and multiple limiters (ie: multiple clients)?

    Pseudo code

    synchronizer := NewNonBlockingSynchronizer()
    for _, key := range keys {
      limiter, stop := slidingwindow.NewLimiter(interval, rate, func() (slidingwindow.Window, slidingwindow.StopFunc) {
        return slidingwindow.NewSyncWindow(key, synchronizer)
      })
    }
    

    SyncWindow code always starts Synchronizer

    https://github.com/RussellLuo/slidingwindow/blob/535bb99d338b683541b351a78e631a022554723b/window.go#L94

    however, in NonBlockingSynchronizer there are no checks for a double launch

    https://github.com/RussellLuo/slidingwindow/blob/535bb99d338b683541b351a78e631a022554723b/synchronizer.go#L131

    So I suspect that the number of goroutines will be roughly equal to the number of limiters, that sounds quite overkill. Is it a bug, feature, or I missed something?

    opened by reddec 1
Owner
Luo Peng
Luo Peng
A little ping pong service that implements rate limiting with golang

Fred the Guardian Introduction Writing a little ping pong service that implements rate limiting with the programming language golang. Requirements Web

null 0 Jan 2, 2022
HTTP rate limiting module for Caddy 2

This module implements both internal and distributed HTTP rate limiting. Requests can be rejected after a specified rate limit is hit.

Matt Holt 76 Jun 18, 2022
Light weight http rate limiting proxy

Introduction Light weight http rate limiting proxy. The proxy will perform rate limiting based on the rules defined in the configuration file. If no r

DHIS2 Platform Engineering 11 Apr 22, 2022
A Caddy v2 extension to apply rate-limiting for HTTP requests

ratelimit A Caddy v2 extension to apply rate-limiting for HTTP requests. Installation $ xcaddy build --with github.com/owlwang/caddy-ratelimit Caddyfi

owlwang 0 Jan 28, 2022
Ratelimit - This package provides a Golang implementation of the leaky-bucket rate limit algorithm

Go rate limiter This package provides a Golang implementation of the leaky-bucke

gofaquan 1 Feb 16, 2022
Pacemaker - Rate limit library. Currently implemented rate limits are

PaceMaker Rate limit library. Currently implemented rate limits are Fixed window

Marquitos 2 Apr 2, 2022
Redis-rate-limiter - An abstraction over redist rate/v9 package

RATE_LIMIT_POC Notes This POC is based on github.com/go-redis/redis_rate/v9 pack

Deepak Pathak 0 Feb 14, 2022
Gcra - Package gcra implements the generic cell rate algorithm

gcra Package gcra implements the generic cell rate algorithm (GCRA). Example opt

Joël Gähwiler 0 Jan 23, 2022
Go forward proxy with bandwidth limiting.

Goforward Go forward proxy with rate limiting. The code is based on Michał Łowicki's 100 LOC forward proxy. Download Releases can be downloaded from h

James Moriarty 16 Jan 9, 2022
Simple-request-limiter - Example of limiting API requests using standard Go library

Route: http://localhost:8080/urls example of body in POST request that was used:

null 0 Feb 2, 2022
A rate limiter for Golang, with ETCD data bindings

Go Rate limiter This package allows us to have a distributed rate limiter, using Redis as a central counter. The limits that are set are only "soft" l

Nadir Hamid 0 Dec 9, 2021
A rate limiter for the gin framework

GinRateLimit GinRateLimit is a rate limiter for the gin framework. By default, it can only store rate limit info in memory. If you want to store it so

null 1 Dec 22, 2021
Common rate-limiter implementations

Overview An example Rate Limiter library used to control the rate that events occur, but these can also be used as thresholds that should replenish ov

Chris Wojno 0 Dec 1, 2021
Go rate limiter used to ensure a minimum duration between executions.

Ratelimiter Rate limiter used to ensure a minimum duration between executions. Additionally supports the optional limit of max queue size. This can be

Branden 1 Jan 21, 2022
Dhrate - Quickly check Dockerhub rate (limit) as an unauthenticated user

Dockerhub Rate A small Go program that returns the Dockerhub rate of an unauthen

Michael Peter 0 Feb 7, 2022
Tapestry is an underlying distributed object location and retrieval system (DOLR) which can be used to store and locate objects. This distributed system provides an interface for storing and retrieving key-value pairs.

Tapestry This project implements Tapestry, an underlying distributed object location and retrieval system (DOLR) which can be used to store and locate

Han Cai 1 Mar 16, 2022
Assembly-optimized MD4 hash algorithm in Go

md4 MD4 hash algorithm in Go. Assembly-optimized for amd64 platforms. MD4 is cryptographically broken and should should only be used where compatibili

Michael McLoughlin 15 Apr 14, 2022
EVM-compatible chain secured by the Lachesis consensus algorithm

ICICB galaxy EVM-compatible chain secured by the Lachesis consensus algorithm. Building the source Building galaxy requires both a Go (version 1.14 or

Galaxy developer Team 10 Jan 8, 2022
A cloud native distributed streaming network telemetry.

Panoptes Streaming Panoptes Streaming is a cloud native distributed streaming network telemetry. It can be installed as a single binary or clustered n

Yahoo 34 Apr 19, 2022