class Datadog::Sampling::TokenBucket

Implementation of the Token Bucket metering algorithm for rate limiting.

@see en.wikipedia.org/wiki/Token_bucket Token bucket

Attributes

max_tokens[R]
rate[R]

Public Class Methods

new(rate, max_tokens = rate) click to toggle source

@param rate [Numeric] Allowance rate, in units per second

if rate is negative, always allow
if rate is zero, never allow

@param max_tokens [Numeric] Limit of available tokens

# File lib/ddtrace/sampling/rate_limiter.rb, line 35
def initialize(rate, max_tokens = rate)
  @rate = rate
  @max_tokens = max_tokens

  @tokens = max_tokens
  @total_messages = 0
  @conforming_messages = 0
  @prev_conforming_messages = nil
  @prev_total_messages = nil
  @current_window = nil

  @last_refill = Utils::Time.get_time
end

Public Instance Methods

allow?(size) click to toggle source

Checks if a message of provided size conforms with the current bucket limit.

If it does, return true and remove size tokens from the bucket. If it does not, return false without affecting the tokens from the bucket.

@return [Boolean] true if message conforms with current bucket limit

# File lib/ddtrace/sampling/rate_limiter.rb, line 58
def allow?(size)
  allowed = should_allow?(size)
  update_rate_counts(allowed)
  allowed
end
available_tokens() click to toggle source

@return [Numeric] number of tokens currently available

# File lib/ddtrace/sampling/rate_limiter.rb, line 92
def available_tokens
  @tokens
end
current_window_rate() click to toggle source

Ratio of 'conformance' per 'total messages' checked on this bucket

Returns 1.0 when no messages have been checked yet.

@return [Float] Conformance ratio, between +[0,1]+

# File lib/ddtrace/sampling/rate_limiter.rb, line 85
def current_window_rate
  return 1.0 if @total_messages.zero?

  @conforming_messages.to_f / @total_messages
end
effective_rate() click to toggle source

Ratio of 'conformance' per 'total messages' checked averaged for the past 2 buckets

Returns 1.0 when no messages have been checked yet.

@return [Float] Conformance ratio, between +[0,1]+

# File lib/ddtrace/sampling/rate_limiter.rb, line 70
def effective_rate
  return 0.0 if @rate.zero?
  return 1.0 if @rate < 0 || @total_messages.zero?

  return current_window_rate if @prev_conforming_messages.nil? || @prev_total_messages.nil?

  (@conforming_messages.to_f + @prev_conforming_messages.to_f) / (@total_messages + @prev_total_messages)
end

Private Instance Methods

increment_conforming_count() click to toggle source
# File lib/ddtrace/sampling/rate_limiter.rb, line 118
def increment_conforming_count
  @conforming_messages += 1
end
increment_total_count() click to toggle source
# File lib/ddtrace/sampling/rate_limiter.rb, line 114
def increment_total_count
  @total_messages += 1
end
refill_since_last_message() click to toggle source
# File lib/ddtrace/sampling/rate_limiter.rb, line 98
def refill_since_last_message
  now = Utils::Time.get_time
  elapsed = now - @last_refill

  # Update the number of available tokens, but ensure we do not exceed the max
  # we return the min of tokens + rate*elapsed, or max tokens
  refill_tokens(@rate * elapsed)

  @last_refill = now
end
refill_tokens(size) click to toggle source
# File lib/ddtrace/sampling/rate_limiter.rb, line 109
def refill_tokens(size)
  @tokens += size
  @tokens = @max_tokens if @tokens > @max_tokens
end
should_allow?(size) click to toggle source
# File lib/ddtrace/sampling/rate_limiter.rb, line 122
def should_allow?(size)
  # rate limit of 0 blocks everything
  return false if @rate.zero?

  # negative rate limit disables rate limiting
  return true if @rate < 0

  refill_since_last_message

  # if tokens < 1 we don't allow?
  return false if @tokens < size

  @tokens -= size

  true
end
update_rate_counts(allowed) click to toggle source

Sets and Updates the past two 1 second windows for which the rate limiter must compute it's rate over and updates the total count, and conforming message count if allowed

# File lib/ddtrace/sampling/rate_limiter.rb, line 142
def update_rate_counts(allowed)
  now = Utils::Time.get_time

  # No tokens have been seen yet, start a new window
  if @current_window.nil?
    @current_window = now
  # If more than 1 second has past since last window, reset
  elsif now - @current_window >= 1
    @prev_conforming_messages = @conforming_messages
    @prev_total_messages = @total_messages
    @conforming_messages = 0
    @total_messages = 0
    @current_window = now
  end

  increment_conforming_count if allowed

  increment_total_count
end