FAILURE MAP
← Case archive

FA-73756 / Rate limiter algorithms / Open access

Rate limiter with a bounded per-key state table: any key with tokens counts as idle · case 01

A partially throttled key is evicted and its restrictions are forgotten.

Verified by executionVariant 1 · 6 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

Idleness only requires a positive refilled balance.

THE FAILURE

Idleness only requires a positive refilled balance.

Unsuccessful approach: Allowing one missing token still evicts keys that are being throttled.

Case contract

Input {max_keys, capacity, rate, requests [[t_s, key]]} with nondecreasing whole seconds. Each key has a token bucket (starts full, cost 1). The table holds at most max_keys keys; a new key may only evict the least recently used key whose bucket would be full after refill at the current time (so eviction cannot reset anyone's limit); if no key is idle the request is "overflow" and nothing changes. Every admitted or denied request refreshes the key's recency. Return [results, keys in LRU order].

Why this case matters

Edge limiters cap memory with a fixed-size key table; evicting a key that is still being throttled hands an attacker a fresh bucket.

1 / The failure

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(x):
    maxk = x['max_keys']
    cap = x['capacity']
    rate = x['rate']
    table = {}
    order = []
    out = []
    for t, key in x['requests']:
        if key not in table:
            if len(table) >= maxk:
                idle = [k for k in order if min(cap, table[k][0] + (t - table[k][1]) * rate) > 0]
                if not idle:
                    out.append('overflow')
                    continue
                del table[idle[0]]
                order.remove(idle[0])
            table[key] = [cap, t]
        else:
            order.remove(key)
        order.append(key)
        st = table[key]
        st[0] = min(cap, st[0] + (t - st[1]) * rate)
        st[1] = t
        if st[0] >= 1:
            st[0] -= 1
            out.append('allow')
        else:
            out.append('deny')
    return [out, order]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['busy key not evicted',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [4, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
  ['lru order refreshed',
   {'capacity': 1,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [10, 'b']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
  ['refilled key is idle',
   {'capacity': 3,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [3, 'b'], [4, 'a']]},
   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
  ['new key starts full',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [7, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
  ['partially refilled not idle',
   {'capacity': 4,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [4, 'b']]},
   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
  ['random keys',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[2, 'a'],
                 [3, 'a'],
                 [4, 'a'],
                 [6, 'd'],
                 [7, 'a'],
                 [7, 'c'],
                 [9, 'a'],
                 [9, 'd'],
                 [10, 'a'],
                 [10, 'c'],
                 [10, 'c'],
                 [10, 'd']]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'overflow'],
    ['a', 'c']]]],
 [['busy key not evicted',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [5, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
  ['lru order refreshed',
   {'capacity': 1,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [11, 'b']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
  ['refilled key is idle',
   {'capacity': 3,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [4, 'b'], [5, 'a']]},
   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
  ['new key starts full',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [8, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
  ['partially refilled not idle',
   {'capacity': 4,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [5, 'b']]},
   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
  ['random keys',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'b'],
                 [1, 'd'],
                 [2, 'a'],
                 [3, 'c'],
                 [3, 'd'],
                 [4, 'a'],
                 [5, 'b'],
                 [5, 'b'],
                 [8, 'a'],
                 [9, 'b'],
                 [9, 'd'],
                 [10, 'c']]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    ['d', 'c']]]],
 [['busy key not evicted',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [6, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
  ['lru order refreshed',
   {'capacity': 1,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [12, 'b']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
  ['refilled key is idle',
   {'capacity': 3,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [5, 'b'], [6, 'a']]},
   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
  ['new key starts full',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [9, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
  ['partially refilled not idle',
   {'capacity': 4,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [6, 'b']]},
   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
  ['random keys',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[1, 'a'],
                 [4, 'c'],
                 [5, 'a'],
                 [5, 'c'],
                 [6, 'c'],
                 [7, 'b'],
                 [7, 'b'],
                 [7, 'c'],
                 [7, 'd'],
                 [7, 'd'],
                 [9, 'b'],
                 [10, 'd']]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'overflow',
     'overflow',
     'allow',
     'allow'],
    ['b', 'd']]]],
 [['busy key not evicted',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [7, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
  ['lru order refreshed',
   {'capacity': 1,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [13, 'b']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
  ['refilled key is idle',
   {'capacity': 3,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [6, 'b'], [7, 'a']]},
   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
  ['new key starts full',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [10, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
  ['partially refilled not idle',
   {'capacity': 4,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [7, 'b']]},
   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
  ['random keys',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'c'],
                 [2, 'a'],
                 [3, 'd'],
                 [5, 'b'],
                 [6, 'b'],
                 [6, 'd'],
                 [7, 'a'],
                 [7, 'a'],
                 [7, 'd'],
                 [8, 'c'],
                 [9, 'd'],
                 [10, 'b']]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    ['d', 'b']]]],
 [['busy key not evicted',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [8, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
  ['lru order refreshed',
   {'capacity': 1,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [14, 'b']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
  ['refilled key is idle',
   {'capacity': 3,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [7, 'b'], [8, 'a']]},
   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
  ['new key starts full',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [11, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
  ['partially refilled not idle',
   {'capacity': 4,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [8, 'b']]},
   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
  ['random keys',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'],
                 [1, 'a'],
                 [1, 'c'],
                 [2, 'd'],
                 [3, 'c'],
                 [4, 'd'],
                 [6, 'a'],
                 [8, 'b'],
                 [8, 'd'],
                 [9, 'b'],
                 [10, 'b'],
                 [10, 'b']]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    ['d', 'b']]]]]
for label, args, expected in cases[N - 1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
busy key not evicted[['allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']][['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]Failed
lru order refreshed[['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']][['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]Passed
refilled key is idle[['allow', 'allow', 'allow', 'allow', 'allow'], ['a']][['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]Failed
new key starts full[['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']][['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]Passed
partially refilled not idle[['allow', 'allow', 'allow', 'allow', 'allow'], ['b']][['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]Failed
random keys[['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'd']][['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'overflow'], ['a', 'c']]Failed

SHA-256 / 6e27cc1885ee812e09e12bccf3ab33f9b822c1a28e3751386330970585910c94

2 / The unsuccessful fix

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(x):
    maxk = x['max_keys']
    cap = x['capacity']
    rate = x['rate']
    table = {}
    order = []
    out = []
    for t, key in x['requests']:
        if key not in table:
            if len(table) >= maxk:
                idle = [k for k in order if min(cap, table[k][0] + (t - table[k][1]) * rate) >= cap - 1]
                if not idle:
                    out.append('overflow')
                    continue
                del table[idle[0]]
                order.remove(idle[0])
            table[key] = [cap, t]
        else:
            order.remove(key)
        order.append(key)
        st = table[key]
        st[0] = min(cap, st[0] + (t - st[1]) * rate)
        st[1] = t
        if st[0] >= 1:
            st[0] -= 1
            out.append('allow')
        else:
            out.append('deny')
    return [out, order]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['busy key not evicted',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [4, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
  ['lru order refreshed',
   {'capacity': 1,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [10, 'b']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
  ['refilled key is idle',
   {'capacity': 3,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [3, 'b'], [4, 'a']]},
   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
  ['new key starts full',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [7, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
  ['partially refilled not idle',
   {'capacity': 4,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [4, 'b']]},
   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
  ['random keys',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[2, 'a'],
                 [3, 'a'],
                 [4, 'a'],
                 [6, 'd'],
                 [7, 'a'],
                 [7, 'c'],
                 [9, 'a'],
                 [9, 'd'],
                 [10, 'a'],
                 [10, 'c'],
                 [10, 'c'],
                 [10, 'd']]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'overflow'],
    ['a', 'c']]]],
 [['busy key not evicted',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [5, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
  ['lru order refreshed',
   {'capacity': 1,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [11, 'b']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
  ['refilled key is idle',
   {'capacity': 3,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [4, 'b'], [5, 'a']]},
   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
  ['new key starts full',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [8, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
  ['partially refilled not idle',
   {'capacity': 4,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [5, 'b']]},
   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
  ['random keys',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'b'],
                 [1, 'd'],
                 [2, 'a'],
                 [3, 'c'],
                 [3, 'd'],
                 [4, 'a'],
                 [5, 'b'],
                 [5, 'b'],
                 [8, 'a'],
                 [9, 'b'],
                 [9, 'd'],
                 [10, 'c']]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    ['d', 'c']]]],
 [['busy key not evicted',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [6, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
  ['lru order refreshed',
   {'capacity': 1,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [12, 'b']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
  ['refilled key is idle',
   {'capacity': 3,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [5, 'b'], [6, 'a']]},
   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
  ['new key starts full',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [9, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
  ['partially refilled not idle',
   {'capacity': 4,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [6, 'b']]},
   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
  ['random keys',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[1, 'a'],
                 [4, 'c'],
                 [5, 'a'],
                 [5, 'c'],
                 [6, 'c'],
                 [7, 'b'],
                 [7, 'b'],
                 [7, 'c'],
                 [7, 'd'],
                 [7, 'd'],
                 [9, 'b'],
                 [10, 'd']]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'overflow',
     'overflow',
     'allow',
     'allow'],
    ['b', 'd']]]],
 [['busy key not evicted',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [7, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
  ['lru order refreshed',
   {'capacity': 1,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [13, 'b']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
  ['refilled key is idle',
   {'capacity': 3,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [6, 'b'], [7, 'a']]},
   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
  ['new key starts full',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [10, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
  ['partially refilled not idle',
   {'capacity': 4,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [7, 'b']]},
   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
  ['random keys',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'c'],
                 [2, 'a'],
                 [3, 'd'],
                 [5, 'b'],
                 [6, 'b'],
                 [6, 'd'],
                 [7, 'a'],
                 [7, 'a'],
                 [7, 'd'],
                 [8, 'c'],
                 [9, 'd'],
                 [10, 'b']]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    ['d', 'b']]]],
 [['busy key not evicted',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [8, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
  ['lru order refreshed',
   {'capacity': 1,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [14, 'b']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
  ['refilled key is idle',
   {'capacity': 3,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [7, 'b'], [8, 'a']]},
   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
  ['new key starts full',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [11, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
  ['partially refilled not idle',
   {'capacity': 4,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [8, 'b']]},
   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
  ['random keys',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'],
                 [1, 'a'],
                 [1, 'c'],
                 [2, 'd'],
                 [3, 'c'],
                 [4, 'd'],
                 [6, 'a'],
                 [8, 'b'],
                 [8, 'd'],
                 [9, 'b'],
                 [10, 'b'],
                 [10, 'b']]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    ['d', 'b']]]]]
for label, args, expected in cases[N - 1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
busy key not evicted[['allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']][['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]Failed
lru order refreshed[['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']][['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]Passed
refilled key is idle[['allow', 'allow', 'allow', 'allow', 'allow'], ['a']][['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]Failed
new key starts full[['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']][['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]Passed
partially refilled not idle[['allow', 'allow', 'allow', 'allow', 'allow'], ['b']][['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]Failed
random keys[['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'd']][['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'overflow'], ['a', 'c']]Failed

SHA-256 / b9b3fca8be9f2d93c2f3a2e8fd0668452835037ff61d711eaa3f1034d621896b

HELD IN THE MEMBER ARCHIVE

The verified repair and its recorded checks are member-only.

This mechanism has 6 recorded checks per implementation. The open-access tier publishes the failure and the unsuccessful fix; the repaired source that passes every check, and the observations that prove it, are available to members.

Every case sharing this mechanism uses the same contract and the same repair, so this one record is held back for all of them.

Member access is invitation-based. Sign in with your invited account to inspect the repair.

Sign in to the archive ↗

Verification & scope

A deterministic, bounded teaching model with stipulated constants and pre-hashed or explicitly hashed inputs; it is not a production implementation and makes no claim of conformance to any library or paper beyond the stated contract. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.

Observations recorded using Python 3.12.14 at 2026-09-29T14:48:50.501253+00:00.

Case digest / 269b650c4d42733fa06016cc6093b10dd41f51a04e4103cdb7f32e6f5c5df7c3