Module Limiter

module Limiter: sig .. end
Implements a token bucket based throttling rate limiter. This module is useful for limiting network clients to a sensible query rate, or in any case where you have jobs that consume a scarce, but replenishable resource.

Unlike a standard token bucket limiter this limiter uses two buckets, an available bucket that tokens are taken from and a hopper that tokens are returned to when the client is finished with them. The available bucket is filled from the hopper at a specified fill rate.

Most use cases are covered by the Token_bucket, Throttle, and Throttled_rate_limiter modules, but the Generic module provides full access to the module internals.

This interface is the simple, non-concurrent interface, and requires machinery on top to implement a specific strategy. See Async_extra for an async-friendly implementation on top of this module.

Most functions in this interface take an explicit time as an argument. now is expected to be monotonically increasing. now's that are set in the past are effectively moved up to the current time of the bucket.

This API allows one to deal with fractional tokens. Note that tokens are divisible into 10k pieces, which limits the effective granularity to which your job request will be rounded.


type t 
type limiter = t 
module Infinite_or_finite: sig .. end
module Token_bucket: sig .. end
Implements a basic token bucket based rate limiter.
module Throttle: sig .. end
Implements a basic throttle.
module Throttled_rate_limiter: sig .. end
A Throttled_rate_limiter combines a Token_bucket and a Throttle.

common read-only operations

val bucket_size : t -> float
val in_bucket : t -> now:Time.t -> float
tokens available to immediately take
val in_hopper : t -> now:Time.t -> float Infinite_or_finite.t
tokens waiting to drop at the hopper_to_bucket_rate_per_sec
val in_flight : t -> now:Time.t -> float
tokens that have been taken, but not yet returned
val in_limiter : t -> now:Time.t -> float Infinite_or_finite.t
total number of tokens in the limiter in_hopper + in_bucket
val in_system : t -> now:Time.t -> float Infinite_or_finite.t
total number of tokens in the entire system in_hopper + in_bucket + in_flight
val hopper_to_bucket_rate_per_sec : t -> float Infinite_or_finite.t
module Expert: sig .. end
expert operations
include Invariant.S
val sexp_of_t : t -> Sexplib.Sexp.t
val sexp_of_limiter : limiter -> Sexplib.Sexp.t

Implements a basic token bucket based rate limiter. Users of the throttle must successfully call try_take before doing work.

Defaults to zero

Implements a basic throttle. Users of the throttle must successfully call start_job before beginning work and must call finish_job once, and only once, when a job is completed.

A Throttled_rate_limiter combines a Token_bucket and a Throttle. Unlike a Token_bucket jobs cannot consume variable numbers of tokens, but the number of outstanding jobs is also limited to max_concurrent_jobs. Like a Throttle finish_job must be called once, and only once when a job is completed.

common read-only operations


tokens available to immediately take

tokens waiting to drop at the hopper_to_bucket_rate_per_sec

tokens that have been taken, but not yet returned

total number of tokens in the limiter in_hopper + in_bucket

total number of tokens in the entire system in_hopper + in_bucket + in_flight

expert operations


- time is the reference time that other time accepting functions will use when they adjust now. It is almost always correct to set this to Time.now.

These tunables can be combined in several ways:

In all cases above throttling and rate limiting combine nicely when the unit of work for both is the same (e.g. one token per message). If the unit of work is different (e.g. rate limit base on a number of tokens equal to message size, but throttle base on simple message count) then a single t probably cannot be used to get the correct behavior, and two instances should be used with tokens taken from both.

returns the earliest time when the requested number of tokens could possibly be delivered. There is no guarantee that the requested number of tokens will actually be available at this time. You must call try_take to actually attempt to take the tokens.

attempts to take the given number of tokens from the bucket. try_take t ~now n succeeds iff in_bucket t ~now >= n.

return the given number of tokens to the hopper. These tokens will fill the tokens available to try_take at the fill_rate. Note that if return is called on more tokens then have actually been removed, this can cause the number of concurrent jobs to exceed max_concurrent_jobs.

Note that, due to rounding issues, one should only return precisely the number of tokens that were previously taken. Returning a sum of different values taken previously may or may not work precisely, depending on the specific floating point numbers used.

sets the target token level for the limiter going forward.

If the system has more tokens than the new target already in it then tokens will be removed (first from the hopper, and then from the bucket) to meet the new maximum. If the target cannot be satisfied by removing tokens from the bucket and hopper (i.e. in_flight is, itself, greater than the new target) the hopper and the bucket will be emptied, and future calls to return_to_hopper will drop tokens until the total number of tokens in the system matches the new target.

Conversely, if in_hopper + in_bucket + in_flight is less than the new target tokens will be added to the hopper such that in_hopper + in_bucket + in_flight = the new max.

NOTE: you should consider calling set_bucket_size after calling set_token_target_level as the bucket_size is often set to a number related to the number of tokens in the system.