The limit was per key and the caller chose the key

# Self-authored for the EML case corpus (no external origin). The rate limiter
# allows 100 requests a minute per client, and it has never allowed a bucket to
# exceed 100. What it allowed in total is computed below.
#
# Limiting per client rather than in total is the right design. A single global
# limit means one heavy caller starves everyone else, and that is the failure
# the per-key limiter was built to prevent. It prevents it. Every bucket is
# under its limit, on every minute, and that is not a rounding of the truth.
#
# The key comes from a header the caller sends, which is also reasonable on its
# face: it is the only identifier available before authentication runs, it lets
# one account separate its own workloads, and partners asked for exactly that
# so their batch jobs would not throttle their interactive traffic.
#
# A limit is only a limit if the thing being counted is outside the counted
# party's control. When the caller chooses the key, the caller chooses how many
# buckets to be, and the limiter enforces every one of them perfectly.

100 => per_key_limit
60 => bucket_ttl_minutes

# [client, distinct keys presented, requests sent per minute]
[["web app", 1, 90], ["mobile app", 1, 100], ["partner batch", 1, 340], ["indexing bot", 40, 4000]] => clients

def allowed_by_key(c):
    c[1] * per_key_limit => cap
    if c[2] < cap:
        return c[2]
    return cap

def allowed_by_account(c):
    if c[2] < per_key_limit:
        return c[2]
    return per_key_limit

("limit : %s requests per minute per key" % str(per_key_limit))^0
"key   : the X-Client-Id header, chosen by the caller" ^0
"" ^0

"client           keys   sent    allowed   rejected   buckets over limit" ^0
0 => sent_total
0 => allowed_total
0 => keys_total
for c in clients:
    allowed_by_key(c) => allowed
    sent_total + c[2] => sent_total
    allowed_total + allowed => allowed_total
    keys_total + c[1] => keys_total
    ("  %-16s %-6s %-7s %-9s %-10s %s" % (c[0], str(c[1]), str(c[2]), str(allowed), str(c[2] - allowed), "0"))^0
"" ^0

("  requests sent     : %s per minute" % str(sent_total))^0
("  requests allowed  : %s per minute" % str(allowed_total))^0
("  buckets over their limit : 0, on every minute since the limiter shipped" )^0
"" ^0

# ---- what one client took ----

clients[3] => bot
("the largest caller" )^0
("  keys presented        : %s" % str(bot[1]))^0
("  effective limit       : %s per minute" % str(bot[1] * per_key_limit))^0
("  times the stated limit : %s" % str(bot[1]))^0
("  share of all allowed traffic : %s percent" % str(int(allowed_by_key(bot) * 100 / allowed_total)))^0
"  it is one of four clients and it is not breaking any rule the limiter" ^0
"  is able to express" ^0
"" ^0

# ---- the control ----
#
# The same four clients, the same limiter, the same limit. The key is derived
# from the authenticated account instead of from the request.

0 => acct_allowed
for c in clients:
    acct_allowed + allowed_by_account(c) => acct_allowed

"control - the same limiter keyed on the authenticated account" ^0
"client           sent    allowed   rejected" ^0
for c in clients:
    allowed_by_account(c) => allowed
    ("  %-16s %-7s %-9s %s" % (c[0], str(c[2]), str(allowed), str(c[2] - allowed)))^0
("  requests allowed : %s, against %s" % (str(acct_allowed), str(allowed_total)))^0
("  difference       : %s per minute" % str(allowed_total - acct_allowed))^0
"  the limiter code is not edited, only where the key comes from" ^0
"" ^0

# ---- the control that made it invisible ----

"control - the three clients that present one key" ^0
0 => honest_sent
0 => honest_allowed
for c in clients:
    if c[1] == 1:
        honest_sent + c[2] => honest_sent
        honest_allowed + allowed_by_key(c) => honest_allowed
("  sent    : %s" % str(honest_sent))^0
("  allowed : %s" % str(honest_allowed))^0
("  the partner batch is throttled from %s to %s, correctly" % (str(clients[2][2]), str(allowed_by_key(clients[2]))))^0
"  the limiter is exactly right for every caller that does not rotate" ^0
"  which is every caller anyone tested it with" ^0
"" ^0

# ---- the second cost ----

bot[1] * bucket_ttl_minutes => live_buckets
"what the keys cost besides the limit" ^0
("  new keys per minute from one client : %s" % str(bot[1]))^0
("  bucket lifetime                     : %s minutes" % str(bucket_ttl_minutes))^0
("  live buckets from that client       : %s" % str(live_buckets))^0
("  live buckets from the other three   : %s" % str(len(clients) - 1))^0
"  the table is keyed by a value the caller invents, so its size is also" ^0
"  chosen by the caller" ^0
"" ^0

# ---- what the limiter can and cannot see ----

"what the limiter measures" ^0
"  requests per key      : correct, always" ^0
"  keys per account      : not measured, no such counter" ^0
"  requests per account  : not measured, the account is resolved later" ^0
"  the quantity the limit is meant to bound is the one with no counter" ^0
"" ^0

"Per-key limiting stops one caller starving the rest, and no bucket has ever" ^0
("exceeded %s. The key is a header the caller sends, so the caller chooses how" % str(per_key_limit))^0
("many buckets to be: %s keys buy %s requests a minute, and keying on the" % (str(bot[1]), str(allowed_by_key(bot))))^0
("account instead allows %s across all four clients rather than %s." % (str(acct_allowed), str(allowed_total)))^0

per_key_limit = 100
bucket_ttl_minutes = 60
clients = [["web app", 1, 90], ["mobile app", 1, 100], ["partner batch", 1, 340], ["indexing bot", 40, 4000]]

def allowed_by_key(c):
    cap = c[1] * per_key_limit
    if c[2] < cap:
        return c[2]
    return cap

def allowed_by_account(c):
    if c[2] < per_key_limit:
        return c[2]
    return per_key_limit

print("limit : %s requests per minute per key" % str(per_key_limit))
print("key   : the X-Client-Id header, chosen by the caller")
print("")
print("client           keys   sent    allowed   rejected   buckets over limit")
sent_total = 0
allowed_total = 0
keys_total = 0
for c in clients:
    allowed = allowed_by_key(c)
    sent_total = sent_total + c[2]
    allowed_total = allowed_total + allowed
    keys_total = keys_total + c[1]
    print("  %-16s %-6s %-7s %-9s %-10s %s" % (c[0], str(c[1]), str(c[2]), str(allowed), str(c[2] - allowed), "0"))
print("")
print("  requests sent     : %s per minute" % str(sent_total))
print("  requests allowed  : %s per minute" % str(allowed_total))
print("  buckets over their limit : 0, on every minute since the limiter shipped")
print("")
bot = clients[3]
print("the largest caller")
print("  keys presented        : %s" % str(bot[1]))
print("  effective limit       : %s per minute" % str(bot[1] * per_key_limit))
print("  times the stated limit : %s" % str(bot[1]))
print("  share of all allowed traffic : %s percent" % str(int(allowed_by_key(bot) * 100 / allowed_total)))
print("  it is one of four clients and it is not breaking any rule the limiter")
print("  is able to express")
print("")
acct_allowed = 0
for c in clients:
    acct_allowed = acct_allowed + allowed_by_account(c)
print("control - the same limiter keyed on the authenticated account")
print("client           sent    allowed   rejected")
for c in clients:
    allowed = allowed_by_account(c)
    print("  %-16s %-7s %-9s %s" % (c[0], str(c[2]), str(allowed), str(c[2] - allowed)))
print("  requests allowed : %s, against %s" % (str(acct_allowed), str(allowed_total)))
print("  difference       : %s per minute" % str(allowed_total - acct_allowed))
print("  the limiter code is not edited, only where the key comes from")
print("")
print("control - the three clients that present one key")
honest_sent = 0
honest_allowed = 0
for c in clients:
    if c[1] == 1:
        honest_sent = honest_sent + c[2]
        honest_allowed = honest_allowed + allowed_by_key(c)
print("  sent    : %s" % str(honest_sent))
print("  allowed : %s" % str(honest_allowed))
print("  the partner batch is throttled from %s to %s, correctly" % (str(clients[2][2]), str(allowed_by_key(clients[2]))))
print("  the limiter is exactly right for every caller that does not rotate")
print("  which is every caller anyone tested it with")
print("")
live_buckets = bot[1] * bucket_ttl_minutes
print("what the keys cost besides the limit")
print("  new keys per minute from one client : %s" % str(bot[1]))
print("  bucket lifetime                     : %s minutes" % str(bucket_ttl_minutes))
print("  live buckets from that client       : %s" % str(live_buckets))
print("  live buckets from the other three   : %s" % str(len(clients) - 1))
print("  the table is keyed by a value the caller invents, so its size is also")
print("  chosen by the caller")
print("")
print("what the limiter measures")
print("  requests per key      : correct, always")
print("  keys per account      : not measured, no such counter")
print("  requests per account  : not measured, the account is resolved later")
print("  the quantity the limit is meant to bound is the one with no counter")
print("")
print("Per-key limiting stops one caller starving the rest, and no bucket has ever")
print("exceeded %s. The key is a header the caller sends, so the caller chooses how" % str(per_key_limit))
print("many buckets to be: %s keys buy %s requests a minute, and keying on the" % (str(bot[1]), str(allowed_by_key(bot))))
print("account instead allows %s across all four clients rather than %s." % (str(acct_allowed), str(allowed_total)))

limit : 100 requests per minute per key
key   : the X-Client-Id header, chosen by the caller

client           keys   sent    allowed   rejected   buckets over limit
  web app          1      90      90        0          0
  mobile app       1      100     100       0          0
  partner batch    1      340     100       240        0
  indexing bot     40     4000    4000      0          0

  requests sent     : 4530 per minute
  requests allowed  : 4290 per minute
  buckets over their limit : 0, on every minute since the limiter shipped

the largest caller
  keys presented        : 40
  effective limit       : 4000 per minute
  times the stated limit : 40
  share of all allowed traffic : 93 percent
  it is one of four clients and it is not breaking any rule the limiter
  is able to express

control - the same limiter keyed on the authenticated account
client           sent    allowed   rejected
  web app          90      90        0
  mobile app       100     100       0
  partner batch    340     100       240
  indexing bot     4000    100       3900
  requests allowed : 390, against 4290
  difference       : 3900 per minute
  the limiter code is not edited, only where the key comes from

control - the three clients that present one key
  sent    : 530
  allowed : 290
  the partner batch is throttled from 340 to 100, correctly
  the limiter is exactly right for every caller that does not rotate
  which is every caller anyone tested it with

what the keys cost besides the limit
  new keys per minute from one client : 40
  bucket lifetime                     : 60 minutes
  live buckets from that client       : 2400
  live buckets from the other three   : 3
  the table is keyed by a value the caller invents, so its size is also
  chosen by the caller

what the limiter measures
  requests per key      : correct, always
  keys per account      : not measured, no such counter
  requests per account  : not measured, the account is resolved later
  the quantity the limit is meant to bound is the one with no counter

Per-key limiting stops one caller starving the rest, and no bucket has ever
exceeded 100. The key is a header the caller sends, so the caller chooses how
many buckets to be: 40 keys buy 4000 requests a minute, and keying on the
account instead allows 390 across all four clients rather than 4290.

Trace event types