FA-73751 / Rate limiter algorithms / Open access
Rate limiter with a bounded per-key state table: new key starts empty · case 01
A new client is denied its first request.
ROOT CAUSE
New keys are created with an empty bucket.
VERIFIED REPAIR
Create new keys with a full bucket.
Unsuccessful approach: Starting with a single token still denies a client's initial burst.
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) >= cap]
if not idle:
out.append('overflow')
continue
del table[idle[0]]
order.remove(idle[0])
table[key] = [0, 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 fixture | Actual | Expected | Outcome |
|---|---|---|---|
| busy key not evicted | [['deny', 'deny', 'deny', 'overflow', 'deny'], ['b', 'c']] | [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']] | Failed |
| lru order refreshed | [['deny', 'deny', 'allow', 'deny', 'deny'], ['c', 'b']] | [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']] | Failed |
| refilled key is idle | [['deny', 'deny', 'overflow', 'deny', 'overflow'], ['b']] | [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']] | Failed |
| new key starts full | [['deny', 'deny', 'deny', 'deny', 'deny', 'allow'], ['b', 'c']] | [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']] | Failed |
| partially refilled not idle | [['deny', 'deny', 'deny', 'overflow', 'deny'], ['b']] | [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']] | Failed |
| random keys | [['deny', 'allow', 'allow', 'deny', 'allow', 'overflow', 'allow', 'allow', 'allow', 'deny', 'deny', 'overflow'], ['a', 'c']] | [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'overflow'], ['a', 'c']] | Failed |
SHA-256 / 115a641c32dff7766db7a7f5c349d2657da19affda17b131a186826899cf8a48
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]
if not idle:
out.append('overflow')
continue
del table[idle[0]]
order.remove(idle[0])
table[key] = [1, 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 fixture | Actual | Expected | Outcome |
|---|---|---|---|
| busy key not evicted | [['allow', 'deny', 'allow', 'overflow', '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', 'deny', 'overflow', 'allow', 'overflow'], ['b']] | [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']] | Failed |
| new key starts full | [['allow', 'deny', 'allow', 'allow', 'deny', 'allow'], ['b', 'c']] | [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']] | Failed |
| partially refilled not idle | [['allow', 'deny', 'deny', 'overflow', 'allow'], ['b']] | [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']] | Failed |
| random keys | [['allow', 'allow', 'allow', 'allow', 'allow', 'overflow', 'allow', 'allow', 'allow', 'allow', 'deny', 'overflow'], ['a', 'c']] | [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'overflow'], ['a', 'c']] | Failed |
SHA-256 / 39770523cbf4baad8c17e1707367c757b8043c3da6d473150ddec94ba2be59a5
3 / The verified repair
Exit 0"""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]
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 fixture | Actual | Expected | Outcome |
|---|---|---|---|
| busy key not evicted | [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']] | [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']] | Passed |
| lru order refreshed | [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']] | [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']] | Passed |
| refilled key is idle | [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']] | [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']] | Passed |
| 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', 'overflow', 'allow'], ['b']] | [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']] | Passed |
| random keys | [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'overflow'], ['a', 'c']] | [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'overflow'], ['a', 'c']] | Passed |
SHA-256 / ef1b25325a55e006b262f045d88040d491bb705d0bb92c784302dab7b3e8c38e
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.461495+00:00.
Case digest / f175e4a2d69d68448446b2ec9bc70a34af813c41b74adfe4116b4d40b692b8c1