Distributed RateLimiting Service

Gubernator

Gubernator is a distributed, high performance, cloud native and stateless rate-limiting service.

Features

• Gubernator evenly distributes rate limit requests across the entire cluster, which means you can scale the system by simply adding more nodes.
• Gubernator doesn’t rely on external caches like memcached or redis, as such there is no deployment synchronization with a dependant service. This makes dynamically growing or shrinking the cluster in an orchestration system like kubernetes or nomad trivial.
• Gubernator holds no state on disk, It’s configuration is passed to it by the client on a per-request basis.
• Gubernator provides both GRPC and HTTP access to the API.
• It Can be run as a sidecar to services that need rate limiting or as a separate service.
• It Can be used as a library to implement a domain-specific rate limiting service.
• Supports optional eventually consistent rate limit distribution for extremely high throughput environments. (See GLOBAL behavior architecture.md)
• Gubernator is the english pronunciation of governor in Russian, also it sounds cool.

Design

Stateless configuration

Gubernator is stateless in that it doesn’t require disk space to operate. No configuration or cache data is ever synced to disk. This is because every request to gubernator includes the config for the rate limit. At first you might think this an unnecessary overhead to each request. However, In reality a rate limit config is made up of only 4, 64bit integers.

Sharded across the cluster

Each rate limit lives on one owning node, chosen by consistent hashing on its name and unique_key, so every node holds only its share of the rate limits. A node that receives a request for a key it doesn't own forwards it to the owner. GLOBAL requests are the exception, see architecture.md.

More on the design

architecture.md covers the rest.

• Batching. Requests a node forwards to the same peer within 500 microseconds go out as one call.
• GLOBAL. For limits that every request touches, any node answers from its own cache and the owner reconciles asynchronously, trading consistency for scale.
• Workers. Inside a node, keys are sharded again across workers that each own their cache slice, so the cache needs no mutex.
• Cluster changes. Peer discovery rebuilds the hash ring when nodes join or leave, and forwarded calls retry against the new owner.
• Library. Embed Gubernator in a Go service and join the cluster as a full member.

Planned

These are designed and not part of the current release.

• Lock-free cache (v3.0). The v3.0 branch makes Otter the default cache. Otter is a lock-free S3-FIFO design, the next step away from synchronization on the hot path (PR #15, background in Synchronization is bad for scale).
• Multi-region forwarding. The MULTI_REGION behavior in gubernator.proto and the RegionPicker are the start of pushing rate limits between regions. Forwarding is not implemented today.

Quick Start

# Download the docker-compose file
$ curl -O https://raw.githubusercontent.com/gubernator-io/gubernator/master/docker-compose.yaml
# Run the docker container
$ docker-compose up -d

Now you can make rate limit requests via CURL

# Hit the HTTP API at localhost:1050 (GRPC is at 1051)
$ curl http://localhost:1050/v1/HealthCheck

# Make a rate limit request
$ curl http://localhost:1050/v1/GetRateLimits \
  --header 'Content-Type: application/json' \
  --data '{
    "requests": [
        {
            "name": "requests_per_sec",
            "uniqueKey": "account:12345",
            "hits": "1",
            "limit": "10",
            "duration": "1000"
        }
    ]
}'

ProtoBuf Structure

An example rate limit request sent via GRPC might look like the following

rate_limits:
    # Scopes the request to a specific rate limit
  - name: requests_per_sec
    # A unique_key that identifies this instance of a rate limit request
    unique_key: account_id=123|source_ip=172.0.0.1
    # The number of hits we are requesting
    hits: 1
    # The total number of requests allowed for this rate limit
    limit: 100
    # The duration of the rate limit in milliseconds
    duration: 1000
    # The algorithm used to calculate the rate limit
    # 0 = Token Bucket
    # 1 = Leaky Bucket
    algorithm: 0
    # The behavior of the rate limit in gubernator.
    # 0 = BATCHING (Enables batching of requests to peers)
    # 1 = NO_BATCHING (Disables batching)
    # 2 = GLOBAL (Enable global caching for this rate limit)
    behavior: 0

An example response would be

rate_limits:
    # The status of the rate limit.  OK = 0, OVER_LIMIT = 1
  - status: 0,
    # The current configured limit
    limit: 10,
    # The number of requests remaining
    remaining: 7,
    # A unix timestamp in milliseconds of when the bucket will reset, or if 
    # OVER_LIMIT is set it is the time at which the rate limit will no 
    # longer return OVER_LIMIT.
    reset_time: 1551309219226,
    # Additional metadata about the request the client might find useful
    metadata:
      # This is the name of the coordinator that rate limited this request
      "owner": "api-n03.staging.us-east-1.mailgun.org:9041"

Rate limit Algorithm

Gubernator currently supports 2 rate limit algorithms.

1. Token Bucket implementation starts with an empty bucket, then each Hit adds a token to the bucket until the bucket is full. Once the bucket is full, requests will return OVER_LIMIT until the reset_time is reached at which point the bucket is emptied and requests will return UNDER_LIMIT. This algorithm is useful for enforcing very bursty limits. (IE: Applications where a single request can add more than 1 hit to the bucket; or non network based queuing systems.) The downside to this implementation is that once you have hit the limit no more requests are allowed until the configured rate limit duration resets the bucket to zero.

2. Leaky Bucket is implemented similarly to Token Bucket where OVER_LIMIT is returned when the bucket is full. However tokens leak from the bucket at a consistent rate which is calculated as duration / limit. This algorithm is useful for metering, as the bucket leaks allowing traffic to continue without the need to wait for the configured rate limit duration to reset the bucket to zero.

   Changing burst on an existing leaky bucket moves remaining by the difference (remaining += new_burst - old_burst), never below zero. A burst of 0 means limit, so changing limit alone has the same effect. Raising burst from 5 to 8 with nothing remaining leaves 3, not a full bucket. Lowering it from 5 to 3 with 2.5 remaining leaves 0.5, which the API reports as 0. Use RESET_REMAINING to refill.

Performance

In our production environment, for every request to our API we send 2 rate limit requests to gubernator for rate limit evaluation, one to rate the HTTP request and the other is to rate the number of recipients a user can send an email too within the specific duration. Under this setup a single gubernator node fields over 2,000 requests a second with most batched responses returned in under 1 millisecond.

Peer requests forwarded to owning nodes typically respond in under 30 microseconds.

NOTE The above graphs only report the slowest request within the 1 second sample time. So you are seeing the slowest requests that gubernator fields to clients.

Gubernator allows users to choose non-batching behavior which would further reduce latency for client rate limit requests. However because of throughput requirements our production environment uses Behaviour=BATCHING with the default 500 microsecond window. In production we have observed batch sizes of 1,000 during peak API usage. Other users who don’t have the same high traffic demands could disable batching and would see lower latencies but at the cost of throughput.

Gregorian Behavior

Users may choose a behavior called DURATION_IS_GREGORIAN which changes the behavior of the Duration field. When Behavior is set to DURATION_IS_GREGORIAN the Duration of the rate limit is reset whenever the end of selected gregorian calendar interval is reached.

This is useful when you want to impose daily or monthly limits on a resource. Using this behavior you know when the end of the day or month is reached the limit on the resource is reset regardless of when the first rate limit request was received by Gubernator.

Given the following Duration values

• 0 = Minutes
• 1 = Hours
• 2 = Days
• 3 = Weeks
• 4 = Months
• 5 = Years

Examples when using Behavior = DURATION_IS_GREGORIAN

• If Duration = 2 (Days) then the rate limit will reset to Current = 0 at the end of the current day the rate limit was created.
• If Duration = 0 (Minutes) then the rate limit will reset to Current = 0 at the end of the minute the rate limit was created.
• If Duration = 4 (Months) then the rate limit will reset to Current = 0 at the end of the month the rate limit was created.

Reset Remaining Behavior

Users may add behavior Behavior_RESET_REMAINING to the rate check request. This will reset the rate limit as if created new on first use.

When using Reset Remaining, the Hits field should be 0.

Drain Over Limit Behavior

Users may add behavior Behavior_DRAIN_OVER_LIMIT to the rate check request. A GetRateLimits call drains the remaining counter on first over limit event. Then, successive GetRateLimits calls will return zero remaining counter and not any residual value. This behavior works best with token bucket algorithm because the Remaining counter will stay zero after an over limit until reset time, whereas leaky bucket algorithm will immediately update Remaining to a non-zero value.

This facilitates scenarios that require an over limit event to stay over limit until the rate limit resets. This approach is necessary if a process must make two rate checks, before and after a process, and the Hit amount is not known until after the process.

• Before process: Call GetRateLimits with Hits=0 to check the value of Remaining counter. If Remaining is zero, it's known that the rate limit is depleted and the process can be aborted.
• After process: Call GetRateLimits with a user specified Hits value. If the call returns over limit, the process cannot be aborted because it had already completed. Using DRAIN_OVER_LIMIT behavior, the Remaining count will be drained to zero.

Once an over limit occurs in the "After" step, successive processes will detect the over limit state in the "Before" step.

Scheduled Admission (max_wait)

A service that paces its calls to a third party's quota, with several processes sharing one rate limit and a deadline on every call, can set max_wait on a LEAKY_BUCKET request. max_wait is the longest, in milliseconds, the caller is willing to wait. The caller gets one answer in one call and never asks again for that request.

status	retry_after	Bucket charged?	Caller does
UNDER_LIMIT	0	Yes, unless hits is 0	Act now.
SCHEDULED	>= 1	Yes	Sleep retry_after milliseconds, then act. Do not call Gubernator again.
OVER_LIMIT	>= 1	No	Give up now. The value is the wait that would have been needed.
NEVER_FITS	0	No	Give up. hits exceed burst, or the key already exists and its limit or duration is not positive, so no wait helps.

retry_after is a relative number of milliseconds, measured from when the owning peer answered. SCHEDULED and NEVER_FITS are only sent to a request with max_wait > 0, so existing clients, which read every status other than OVER_LIMIT as allowed, never see them.

Ten requests per minute (6000ms per token), burst 10 and max_wait 120000, with 31 requests at once, gives requests 1 to 10 UNDER_LIMIT, request 11 SCHEDULED with retry_after 6000, request 12 12000, and so on up to request 30 at 120000. Request 31 gets OVER_LIMIT with retry_after 126000 and is not charged.

max_wait combines only with LEAKY_BUCKET. TOKEN_BUCKET, GLOBAL (including GUBER_FORCE_GLOBAL), DURATION_IS_GREGORIAN, DRAIN_OVER_LIMIT, RESET_REMAINING, negative hits and a negative max_wait come back as a per-request error. Check error first and ignore every other field when it is set.

GUBER_SCHEDULE_MAX_WAIT (default 5m) caps the wait the server will book, whatever max_wait says. When the ceiling refuses a request, retry_after is at or below the caller's own max_wait, while a refusal for the caller's own deadline returns a larger one. Retrying at once with the same deadline is refused again; the wait only shrinks as the existing bookings pass.

Pacing outbound calls

resp := getRateLimit(ctx, &gubernator.RateLimitReq{
    Name: "vendor_api", UniqueKey: "shared", Algorithm: gubernator.Algorithm_LEAKY_BUCKET,
    Limit: 9, Duration: gubernator.Minute, Burst: 1, Hits: 1,
    MaxWait: deadline.Milliseconds(), // the caller's deadline for acting, not an RPC timeout
})
switch {
case resp.Error != "":
    // Fix the request or fail the call.
case resp.Status == gubernator.Status_UNDER_LIMIT:
    callVendor()
case resp.Status == gubernator.Status_SCHEDULED:
    time.Sleep(time.Duration(resp.RetryAfter) * time.Millisecond)
    callVendor()
default: // OVER_LIMIT or NEVER_FITS
    failFast()
}

• Leave headroom. Gubernator promises that calls on a key conform to the configured leaky bucket if every caller acts at its granted time. It promises nothing about the third party. Set the limit about 10% below the real quota, more at high rates or when callers wake up late, and use burst 1 when the third party counts calls in fixed windows. A leaky bucket with burst equal to limit allows a full burst and then one call per rate, which is 19 calls inside one 60 second window for a 10 per minute quota.
• State loss forgets bookings. A restart without a Store, an LRU cache eviction, or a hash ring change that moves the key gives it a full bucket again. Callers can then over-send by up to GUBER_SCHEDULE_MAX_WAIT worth of quota plus one burst, once per loss. A non-zero gubernator_scheduled_debt_evictions_count means eviction is dropping bookings from the cache, and gubernator_scheduled_debt_lost_tokens is how much. They are lost for good unless a Store still holds the bucket, so raise GUBER_CACHE_SIZE.
• A plain request on a key in debt is refused. While scheduled traffic holds a key in debt (its balance is below zero), a request without max_wait gets OVER_LIMIT with remaining 0, because admitting it would spend a slot already promised. remaining is never negative. RESET_REMAINING still resets the bucket, and is counted in gubernator_scheduled_debt_reset_count.
• Changing limit or duration keeps booked slots. On a key in debt, the debt is rescaled by old rate over new rate, so it clears at the same moment and every granted slot keeps its time. Raising the limit does not let new callers jump ahead of slots already promised. A request with RESET_REMAINING forgives the debt instead. A DURATION_IS_GREGORIAN request, or one whose new limit or duration is zero or negative, leaves the stored limit and duration unchanged while the key is in debt. Switching the key to TOKEN_BUCKET forgives the debt, as the algorithm field documents, and is counted in gubernator_scheduled_debt_reset_count.
• A refund on a key in debt is dropped. A plain request with negative hits on a key in debt answers UNDER_LIMIT with remaining 0 and changes nothing, because paying the debt back would hand a booked slot to a later caller. The refund is not applied.
• A forward error can leave a booking behind. A max_wait request is never retried. If the owner books it and the reply is lost on the way back, the caller gets an error and the slot stays booked until it passes, so later callers wait behind it. Treat that error as a failed call, not as proof that nothing was charged.
• Detect an old server. An owner that predates max_wait ignores it. It answers OVER_LIMIT with retry_after 0, which a current owner never sends to a request with max_wait.
• Upgrade every peer first. An older forwarding peer batches and retries requests, which can book one request several times. Set max_wait only after every peer runs this version.
• JSON gateway. max_wait and retry_after are int64, so the HTTP API writes them as strings ("max_wait": "120000", "retry_after": "6000") and accepts either form on input. Every rate limit in a GetRateLimits response now includes "retry_after": "0".

Gubernator as a library

Importing the module requires Go 1.26.10 or newer.

If you are using golang, you can use Gubernator as a library. This is useful if you wish to implement a rate limit service with your own company specific model on top. We do this internally here at mailgun with a service we creatively called ratelimits which keeps track of the limits imposed on a per account basis. In this way you can utilize the power and speed of Gubernator but still layer business logic and integrate domain specific problems into your rate limiting service.

When you use the library, your service becomes a full member of the cluster participating in the same consistent hashing and caching as a stand alone Gubernator server would. All you need to do is provide the GRPC server instance and tell Gubernator where the peers in your cluster are located. The cmd/gubernator/main.go is a great example of how to use Gubernator as a library.

Optional Disk Persistence

While the Gubernator server currently doesn't directly support disk persistence, the Gubernator library does provide interfaces through which library users can implement persistence. The Gubernator library has two interfaces available for disk persistence. Depending on the use case an implementor can implement the Loader interface and only support persistence of rate limits at startup and shutdown, or users can implement the Store interface and Gubernator will continuously call OnChange() and Get() to keep the in memory cache and persistent store up to date with the latest rate limit data. Both interfaces can be implemented simultaneously to ensure data is always saved to persistent storage.

For those who choose to implement the Store interface, it is not required to store ALL the rate limits received via OnChange(). For instance; If you wish to support rate limit durations longer than a minute, day or month, calls to OnChange() can check the duration of a rate limit and decide to only persist those rate limits that have durations over a self determined limit.

API

All methods are accessed via GRPC but are also exposed via HTTP using the GRPC Gateway

Health Check

Health check returns unhealthy in the event a peer is reported by etcd or kubernetes as up but the server instance is unable to contact that peer via it's advertised address.

GRPC

rpc HealthCheck (HealthCheckReq) returns (HealthCheckResp)

HTTP

GET /v1/HealthCheck

Example response:

{
  "status": "healthy",
  "peer_count": 3
}

Get Rate Limit

Rate limits can be applied or retrieved using this interface. If the client makes a request to the server with hits: 0 then current state of the rate limit is retrieved but not incremented.

GRPC

rpc GetRateLimits (GetRateLimitsReq) returns (GetRateLimitsResp)

HTTP

POST /v1/GetRateLimits

Example Payload

{
  "requests": [
    {
      "name": "requests_per_sec",
      "uniqueKey": "account:12345",
      "hits": "1",
      "limit": "10",
      "duration": "1000"
    }
  ]
}

Example response:

{
  "responses": [
    {
      "status": "UNDER_LIMIT",
      "limit": "10",
      "remaining": "9",
      "reset_time": "1690855128786",
      "error": "",
      "metadata": {
        "owner": "gubernator:1051"
      },
      "retry_after": "0"
    }
  ]
}

Deployment

NOTE: Gubernator discovers peers with memberlist gossip (the default), etcd, the Kubernetes EndpointSlice API, or round-robin DNS. The docker-compose method is the simplest way to try gubernator out.

Docker with existing etcd cluster

$ docker run -p 1051:1051 -p 1050:1050 -e GUBER_ETCD_ENDPOINTS=etcd1:2379,etcd2:2379 \
   ghcr.io/gubernator-io/gubernator:latest

# Hit the HTTP API at localhost:1050
$ curl http://localhost:1050/v1/HealthCheck

Kubernetes (Helm)

A Helm chart is published as an OCI artifact on every release. Requires Helm 3.8+.

helm install gubernator oci://ghcr.io/gubernator-io/charts/gubernator \
  --version <version> \
  --namespace gubernator --create-namespace

See contrib/charts/gubernator/README.md for the full values reference, autoscaling options (HPA and KEDA), RBAC setup, and monitoring configuration.

Kubernetes (manual)

# Download the kubernetes deployment spec
$ curl -O https://raw.githubusercontent.com/gubernator-io/gubernator/master/k8s-deployment.yaml

# Edit the deployment file to change the environment config variables
$ vi k8s-deployment.yaml

# Create the deployment (includes headless service spec)
$ kubectl create -f k8s-deployment.yaml

Round-robin DNS

If your DNS service supports auto-registration (for example AWS Route53 service discovery or Kubernetes headless services), you can use a fully-qualified domain name for both client discovery and peer discovery.

GUBER_PEER_DISCOVERY_TYPE=dns
GUBER_DNS_FQDN=gubernator.default.svc.cluster.local.

Single datacenter — leave GUBER_DATA_CENTER unset. All peers resolved from any FQDN are treated as local.

Multi-datacenter (planned) — cross-datacenter forwarding is not implemented yet, see Planned. DNS peer discovery already sorts peers into datacenters, but nothing forwards across datacenters yet. Unlike etcd and member-list, where GUBER_DATA_CENTER is arbitrary metadata each peer advertises (e.g., "us-east-1"), DNS carries no metadata, so the FQDN a peer's IP was resolved from becomes its datacenter name. GUBER_DATA_CENTER must be set to the exact FQDN of the local cluster:

# On instances in the EKS cluster:
GUBER_DATA_CENTER=gubernator.svc.eks-cluster.
GUBER_DNS_FQDN=gubernator.svc.eks-cluster.,gubernator.svc.gke-cluster.,gubernator.svc.aks-cluster.

# On instances in the GKE cluster:
GUBER_DATA_CENTER=gubernator.svc.gke-cluster.
GUBER_DNS_FQDN=gubernator.svc.eks-cluster.,gubernator.svc.gke-cluster.,gubernator.svc.aks-cluster.

Peers resolved from the local FQDN go to the local picker. Peers from other FQDNs go to the RegionPicker, which holds them but does not yet forward to them.

TLS

Gubernator supports TLS for both HTTP and GRPC connections. You can see an example with self signed certs by running docker-compose-tls.yaml

# Run docker compose
$ docker-compose -f docker-compose-tls.yaml up -d

# Hit the HTTP API at localhost:1050 (GRPC is at 1051)
$ curl --cacert certs/ca.cert --cert certs/gubernator.pem --key certs/gubernator.key  https://localhost:1050/v1/HealthCheck

Configuration

Gubernator is configured via environment variables with an optional --config flag which takes a file of key/values and places them into the local environment before startup.

See the example.conf for all available config options and their descriptions. GUBER_SCHEDULE_MAX_WAIT (default 5m) sets the longest wait the server books for a request that sets max_wait.

Architecture

See architecture.md for a full description of the architecture and the inner workings of gubernator.

Monitoring

Gubernator publishes Prometheus metrics for realtime monitoring. See prometheus.md for details.

OpenTelemetry Tracing (OTEL)

Gubernator supports OpenTelemetry. See tracing.md for details.

Contributing

• Please read the Contributing Docs
• Open a Pull Request!
• Join our Discord