{"abstract":"A new client is denied its first request.","category":"Rate limiter algorithms","checks":6,"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].","evaluation_group":"w2-rate_limiter_algorithms-bounded-state-table","failed_approach":"Starting with a single token still denies a client's initial burst.","family":"w2-rate_limiter_algorithms-bounded-state-table-new-key-state","id":"FA-73751","implementations":{"attempt":{"sha256":"39770523cbf4baad8c17e1707367c757b8043c3da6d473150ddec94ba2be59a5","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(x):\n    maxk = x['max_keys']\n    cap = x['capacity']\n    rate = x['rate']\n    table = {}\n    order = []\n    out = []\n    for t, key in x['requests']:\n        if key not in table:\n            if len(table) >= maxk:\n                idle = [k for k in order if min(cap, table[k][0] + (t - table[k][1]) * rate) >= cap]\n                if not idle:\n                    out.append('overflow')\n                    continue\n                del table[idle[0]]\n                order.remove(idle[0])\n            table[key] = [1, t]\n        else:\n            order.remove(key)\n        order.append(key)\n        st = table[key]\n        st[0] = min(cap, st[0] + (t - st[1]) * rate)\n        st[1] = t\n        if st[0] >= 1:\n            st[0] -= 1\n            out.append('allow')\n        else:\n            out.append('deny')\n    return [out, order]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[['busy key not evicted',\n   {'capacity': 2,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [4, 'c']]},\n   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],\n  ['lru order refreshed',\n   {'capacity': 1,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [10, 'b']]},\n   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],\n  ['refilled key is idle',\n   {'capacity': 3,\n    'max_keys': 1,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [3, 'b'], [4, 'a']]},\n   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],\n  ['new key starts full',\n   {'capacity': 2,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [7, 'c']]},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],\n  ['partially refilled not idle',\n   {'capacity': 4,\n    'max_keys': 1,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [4, 'b']]},\n   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],\n  ['random keys',\n   {'capacity': 2,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[2, 'a'],\n                 [3, 'a'],\n                 [4, 'a'],\n                 [6, 'd'],\n                 [7, 'a'],\n                 [7, 'c'],\n                 [9, 'a'],\n                 [9, 'd'],\n                 [10, 'a'],\n                 [10, 'c'],\n                 [10, 'c'],\n                 [10, 'd']]},\n   [['allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'overflow'],\n    ['a', 'c']]]],\n [['busy key not evicted',\n   {'capacity': 2,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [5, 'c']]},\n   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],\n  ['lru order refreshed',\n   {'capacity': 1,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [11, 'b']]},\n   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],\n  ['refilled key is idle',\n   {'capacity': 3,\n    'max_keys': 1,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [4, 'b'], [5, 'a']]},\n   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],\n  ['new key starts full',\n   {'capacity': 2,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [8, 'c']]},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],\n  ['partially refilled not idle',\n   {'capacity': 4,\n    'max_keys': 1,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [5, 'b']]},\n   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],\n  ['random keys',\n   {'capacity': 2,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'b'],\n                 [1, 'd'],\n                 [2, 'a'],\n                 [3, 'c'],\n                 [3, 'd'],\n                 [4, 'a'],\n                 [5, 'b'],\n                 [5, 'b'],\n                 [8, 'a'],\n                 [9, 'b'],\n                 [9, 'd'],\n                 [10, 'c']]},\n   [['allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow'],\n    ['d', 'c']]]],\n [['busy key not evicted',\n   {'capacity': 2,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [6, 'c']]},\n   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],\n  ['lru order refreshed',\n   {'capacity': 1,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [12, 'b']]},\n   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],\n  ['refilled key is idle',\n   {'capacity': 3,\n    'max_keys': 1,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [5, 'b'], [6, 'a']]},\n   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],\n  ['new key starts full',\n   {'capacity': 2,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [9, 'c']]},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],\n  ['partially refilled not idle',\n   {'capacity': 4,\n    'max_keys': 1,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [6, 'b']]},\n   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],\n  ['random keys',\n   {'capacity': 2,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[1, 'a'],\n                 [4, 'c'],\n                 [5, 'a'],\n                 [5, 'c'],\n                 [6, 'c'],\n                 [7, 'b'],\n                 [7, 'b'],\n                 [7, 'c'],\n                 [7, 'd'],\n                 [7, 'd'],\n                 [9, 'b'],\n                 [10, 'd']]},\n   [['allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'overflow',\n     'overflow',\n     'allow',\n     'allow'],\n    ['b', 'd']]]],\n [['busy key not evicted',\n   {'capacity': 2,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [7, 'c']]},\n   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],\n  ['lru order refreshed',\n   {'capacity': 1,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [13, 'b']]},\n   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],\n  ['refilled key is idle',\n   {'capacity': 3,\n    'max_keys': 1,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [6, 'b'], [7, 'a']]},\n   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],\n  ['new key starts full',\n   {'capacity': 2,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [10, 'c']]},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],\n  ['partially refilled not idle',\n   {'capacity': 4,\n    'max_keys': 1,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [7, 'b']]},\n   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],\n  ['random keys',\n   {'capacity': 2,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'c'],\n                 [2, 'a'],\n                 [3, 'd'],\n                 [5, 'b'],\n                 [6, 'b'],\n                 [6, 'd'],\n                 [7, 'a'],\n                 [7, 'a'],\n                 [7, 'd'],\n                 [8, 'c'],\n                 [9, 'd'],\n                 [10, 'b']]},\n   [['allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow'],\n    ['d', 'b']]]],\n [['busy key not evicted',\n   {'capacity': 2,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [8, 'c']]},\n   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],\n  ['lru order refreshed',\n   {'capacity': 1,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [14, 'b']]},\n   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],\n  ['refilled key is idle',\n   {'capacity': 3,\n    'max_keys': 1,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [7, 'b'], [8, 'a']]},\n   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],\n  ['new key starts full',\n   {'capacity': 2,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [11, 'c']]},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],\n  ['partially refilled not idle',\n   {'capacity': 4,\n    'max_keys': 1,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [8, 'b']]},\n   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],\n  ['random keys',\n   {'capacity': 2,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'a'],\n                 [1, 'a'],\n                 [1, 'c'],\n                 [2, 'd'],\n                 [3, 'c'],\n                 [4, 'd'],\n                 [6, 'a'],\n                 [8, 'b'],\n                 [8, 'd'],\n                 [9, 'b'],\n                 [10, 'b'],\n                 [10, 'b']]},\n   [['allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow'],\n    ['d', 'b']]]]]\nfor label, args, expected in cases[N - 1]:\n    check(label, solve(args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"},"broken":{"sha256":"115a641c32dff7766db7a7f5c349d2657da19affda17b131a186826899cf8a48","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(x):\n    maxk = x['max_keys']\n    cap = x['capacity']\n    rate = x['rate']\n    table = {}\n    order = []\n    out = []\n    for t, key in x['requests']:\n        if key not in table:\n            if len(table) >= maxk:\n                idle = [k for k in order if min(cap, table[k][0] + (t - table[k][1]) * rate) >= cap]\n                if not idle:\n                    out.append('overflow')\n                    continue\n                del table[idle[0]]\n                order.remove(idle[0])\n            table[key] = [0, t]\n        else:\n            order.remove(key)\n        order.append(key)\n        st = table[key]\n        st[0] = min(cap, st[0] + (t - st[1]) * rate)\n        st[1] = t\n        if st[0] >= 1:\n            st[0] -= 1\n            out.append('allow')\n        else:\n            out.append('deny')\n    return [out, order]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[['busy key not evicted',\n   {'capacity': 2,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [4, 'c']]},\n   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],\n  ['lru order refreshed',\n   {'capacity': 1,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [10, 'b']]},\n   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],\n  ['refilled key is idle',\n   {'capacity': 3,\n    'max_keys': 1,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [3, 'b'], [4, 'a']]},\n   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],\n  ['new key starts full',\n   {'capacity': 2,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [7, 'c']]},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],\n  ['partially refilled not idle',\n   {'capacity': 4,\n    'max_keys': 1,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [4, 'b']]},\n   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],\n  ['random keys',\n   {'capacity': 2,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[2, 'a'],\n                 [3, 'a'],\n                 [4, 'a'],\n                 [6, 'd'],\n                 [7, 'a'],\n                 [7, 'c'],\n                 [9, 'a'],\n                 [9, 'd'],\n                 [10, 'a'],\n                 [10, 'c'],\n                 [10, 'c'],\n                 [10, 'd']]},\n   [['allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'overflow'],\n    ['a', 'c']]]],\n [['busy key not evicted',\n   {'capacity': 2,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [5, 'c']]},\n   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],\n  ['lru order refreshed',\n   {'capacity': 1,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [11, 'b']]},\n   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],\n  ['refilled key is idle',\n   {'capacity': 3,\n    'max_keys': 1,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [4, 'b'], [5, 'a']]},\n   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],\n  ['new key starts full',\n   {'capacity': 2,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [8, 'c']]},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],\n  ['partially refilled not idle',\n   {'capacity': 4,\n    'max_keys': 1,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [5, 'b']]},\n   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],\n  ['random keys',\n   {'capacity': 2,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'b'],\n                 [1, 'd'],\n                 [2, 'a'],\n                 [3, 'c'],\n                 [3, 'd'],\n                 [4, 'a'],\n                 [5, 'b'],\n                 [5, 'b'],\n                 [8, 'a'],\n                 [9, 'b'],\n                 [9, 'd'],\n                 [10, 'c']]},\n   [['allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow'],\n    ['d', 'c']]]],\n [['busy key not evicted',\n   {'capacity': 2,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [6, 'c']]},\n   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],\n  ['lru order refreshed',\n   {'capacity': 1,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [12, 'b']]},\n   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],\n  ['refilled key is idle',\n   {'capacity': 3,\n    'max_keys': 1,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [5, 'b'], [6, 'a']]},\n   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],\n  ['new key starts full',\n   {'capacity': 2,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [9, 'c']]},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],\n  ['partially refilled not idle',\n   {'capacity': 4,\n    'max_keys': 1,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [6, 'b']]},\n   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],\n  ['random keys',\n   {'capacity': 2,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[1, 'a'],\n                 [4, 'c'],\n                 [5, 'a'],\n                 [5, 'c'],\n                 [6, 'c'],\n                 [7, 'b'],\n                 [7, 'b'],\n                 [7, 'c'],\n                 [7, 'd'],\n                 [7, 'd'],\n                 [9, 'b'],\n                 [10, 'd']]},\n   [['allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'overflow',\n     'overflow',\n     'allow',\n     'allow'],\n    ['b', 'd']]]],\n [['busy key not evicted',\n   {'capacity': 2,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [7, 'c']]},\n   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],\n  ['lru order refreshed',\n   {'capacity': 1,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [13, 'b']]},\n   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],\n  ['refilled key is idle',\n   {'capacity': 3,\n    'max_keys': 1,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [6, 'b'], [7, 'a']]},\n   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],\n  ['new key starts full',\n   {'capacity': 2,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [10, 'c']]},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],\n  ['partially refilled not idle',\n   {'capacity': 4,\n    'max_keys': 1,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [7, 'b']]},\n   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],\n  ['random keys',\n   {'capacity': 2,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'c'],\n                 [2, 'a'],\n                 [3, 'd'],\n                 [5, 'b'],\n                 [6, 'b'],\n                 [6, 'd'],\n                 [7, 'a'],\n                 [7, 'a'],\n                 [7, 'd'],\n                 [8, 'c'],\n                 [9, 'd'],\n                 [10, 'b']]},\n   [['allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow'],\n    ['d', 'b']]]],\n [['busy key not evicted',\n   {'capacity': 2,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [8, 'c']]},\n   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],\n  ['lru order refreshed',\n   {'capacity': 1,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [14, 'b']]},\n   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],\n  ['refilled key is idle',\n   {'capacity': 3,\n    'max_keys': 1,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [7, 'b'], [8, 'a']]},\n   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],\n  ['new key starts full',\n   {'capacity': 2,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [11, 'c']]},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],\n  ['partially refilled not idle',\n   {'capacity': 4,\n    'max_keys': 1,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [8, 'b']]},\n   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],\n  ['random keys',\n   {'capacity': 2,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'a'],\n                 [1, 'a'],\n                 [1, 'c'],\n                 [2, 'd'],\n                 [3, 'c'],\n                 [4, 'd'],\n                 [6, 'a'],\n                 [8, 'b'],\n                 [8, 'd'],\n                 [9, 'b'],\n                 [10, 'b'],\n                 [10, 'b']]},\n   [['allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow'],\n    ['d', 'b']]]]]\nfor label, args, expected in cases[N - 1]:\n    check(label, solve(args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"},"fixed":{"sha256":"ef1b25325a55e006b262f045d88040d491bb705d0bb92c784302dab7b3e8c38e","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(x):\n    maxk = x['max_keys']\n    cap = x['capacity']\n    rate = x['rate']\n    table = {}\n    order = []\n    out = []\n    for t, key in x['requests']:\n        if key not in table:\n            if len(table) >= maxk:\n                idle = [k for k in order if min(cap, table[k][0] + (t - table[k][1]) * rate) >= cap]\n                if not idle:\n                    out.append('overflow')\n                    continue\n                del table[idle[0]]\n                order.remove(idle[0])\n            table[key] = [cap, t]\n        else:\n            order.remove(key)\n        order.append(key)\n        st = table[key]\n        st[0] = min(cap, st[0] + (t - st[1]) * rate)\n        st[1] = t\n        if st[0] >= 1:\n            st[0] -= 1\n            out.append('allow')\n        else:\n            out.append('deny')\n    return [out, order]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[['busy key not evicted',\n   {'capacity': 2,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [4, 'c']]},\n   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],\n  ['lru order refreshed',\n   {'capacity': 1,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [10, 'b']]},\n   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],\n  ['refilled key is idle',\n   {'capacity': 3,\n    'max_keys': 1,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [3, 'b'], [4, 'a']]},\n   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],\n  ['new key starts full',\n   {'capacity': 2,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [7, 'c']]},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],\n  ['partially refilled not idle',\n   {'capacity': 4,\n    'max_keys': 1,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [4, 'b']]},\n   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],\n  ['random keys',\n   {'capacity': 2,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[2, 'a'],\n                 [3, 'a'],\n                 [4, 'a'],\n                 [6, 'd'],\n                 [7, 'a'],\n                 [7, 'c'],\n                 [9, 'a'],\n                 [9, 'd'],\n                 [10, 'a'],\n                 [10, 'c'],\n                 [10, 'c'],\n                 [10, 'd']]},\n   [['allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'overflow'],\n    ['a', 'c']]]],\n [['busy key not evicted',\n   {'capacity': 2,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [5, 'c']]},\n   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],\n  ['lru order refreshed',\n   {'capacity': 1,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [11, 'b']]},\n   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],\n  ['refilled key is idle',\n   {'capacity': 3,\n    'max_keys': 1,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [4, 'b'], [5, 'a']]},\n   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],\n  ['new key starts full',\n   {'capacity': 2,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [8, 'c']]},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],\n  ['partially refilled not idle',\n   {'capacity': 4,\n    'max_keys': 1,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [5, 'b']]},\n   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],\n  ['random keys',\n   {'capacity': 2,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'b'],\n                 [1, 'd'],\n                 [2, 'a'],\n                 [3, 'c'],\n                 [3, 'd'],\n                 [4, 'a'],\n                 [5, 'b'],\n                 [5, 'b'],\n                 [8, 'a'],\n                 [9, 'b'],\n                 [9, 'd'],\n                 [10, 'c']]},\n   [['allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow'],\n    ['d', 'c']]]],\n [['busy key not evicted',\n   {'capacity': 2,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [6, 'c']]},\n   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],\n  ['lru order refreshed',\n   {'capacity': 1,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [12, 'b']]},\n   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],\n  ['refilled key is idle',\n   {'capacity': 3,\n    'max_keys': 1,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [5, 'b'], [6, 'a']]},\n   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],\n  ['new key starts full',\n   {'capacity': 2,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [9, 'c']]},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],\n  ['partially refilled not idle',\n   {'capacity': 4,\n    'max_keys': 1,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [6, 'b']]},\n   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],\n  ['random keys',\n   {'capacity': 2,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[1, 'a'],\n                 [4, 'c'],\n                 [5, 'a'],\n                 [5, 'c'],\n                 [6, 'c'],\n                 [7, 'b'],\n                 [7, 'b'],\n                 [7, 'c'],\n                 [7, 'd'],\n                 [7, 'd'],\n                 [9, 'b'],\n                 [10, 'd']]},\n   [['allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'overflow',\n     'overflow',\n     'allow',\n     'allow'],\n    ['b', 'd']]]],\n [['busy key not evicted',\n   {'capacity': 2,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [7, 'c']]},\n   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],\n  ['lru order refreshed',\n   {'capacity': 1,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [13, 'b']]},\n   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],\n  ['refilled key is idle',\n   {'capacity': 3,\n    'max_keys': 1,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [6, 'b'], [7, 'a']]},\n   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],\n  ['new key starts full',\n   {'capacity': 2,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [10, 'c']]},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],\n  ['partially refilled not idle',\n   {'capacity': 4,\n    'max_keys': 1,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [7, 'b']]},\n   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],\n  ['random keys',\n   {'capacity': 2,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'c'],\n                 [2, 'a'],\n                 [3, 'd'],\n                 [5, 'b'],\n                 [6, 'b'],\n                 [6, 'd'],\n                 [7, 'a'],\n                 [7, 'a'],\n                 [7, 'd'],\n                 [8, 'c'],\n                 [9, 'd'],\n                 [10, 'b']]},\n   [['allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow'],\n    ['d', 'b']]]],\n [['busy key not evicted',\n   {'capacity': 2,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [8, 'c']]},\n   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],\n  ['lru order refreshed',\n   {'capacity': 1,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [14, 'b']]},\n   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],\n  ['refilled key is idle',\n   {'capacity': 3,\n    'max_keys': 1,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [7, 'b'], [8, 'a']]},\n   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],\n  ['new key starts full',\n   {'capacity': 2,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [11, 'c']]},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],\n  ['partially refilled not idle',\n   {'capacity': 4,\n    'max_keys': 1,\n    'rate': 1,\n    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [8, 'b']]},\n   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],\n  ['random keys',\n   {'capacity': 2,\n    'max_keys': 2,\n    'rate': 1,\n    'requests': [[0, 'a'],\n                 [1, 'a'],\n                 [1, 'c'],\n                 [2, 'd'],\n                 [3, 'c'],\n                 [4, 'd'],\n                 [6, 'a'],\n                 [8, 'b'],\n                 [8, 'd'],\n                 [9, 'b'],\n                 [10, 'b'],\n                 [10, 'b']]},\n   [['allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow'],\n    ['d', 'b']]]]]\nfor label, args, expected in cases[N - 1]:\n    check(label, solve(args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"}},"limitations":"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.","method":"Deterministic executable model with adversarial boundary fixtures.","provenance":{"created_by":"Failure Map","dependencies":"Python standard library","family":"w2-rate_limiter_algorithms-bounded-state-table-new-key-state","generated_at":"2026-09-29T14:48:50.461495+00:00","license":"CC0-1.0","python":"3.12.14","seed":1,"split":"open-access"},"relevance":"Edge limiters cap memory with a fixed-size key table; evicting a key that is still being throttled hands an attacker a fresh bucket.","repair":"Create new keys with a full bucket.","root_cause":"New keys are created with an empty bucket.","sha256":"f175e4a2d69d68448446b2ec9bc70a34af813c41b74adfe4116b4d40b692b8c1","title":"Rate limiter with a bounded per-key state table: new key starts empty · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verification":{"attempt":{"elapsed_ms":37.81,"exit_code":1,"observations":[{"actual":[["allow","deny","allow","overflow","allow"],["b","c"]],"check":"busy key not evicted","expected":[["allow","allow","allow","allow","allow"],["a","c"]],"passed":false},{"actual":[["allow","allow","allow","allow","allow"],["c","b"]],"check":"lru order refreshed","expected":[["allow","allow","allow","allow","allow"],["c","b"]],"passed":true},{"actual":[["allow","deny","overflow","allow","overflow"],["b"]],"check":"refilled key is idle","expected":[["allow","allow","overflow","allow","allow"],["a"]],"passed":false},{"actual":[["allow","deny","allow","allow","deny","allow"],["b","c"]],"check":"new key starts full","expected":[["allow","allow","allow","allow","allow","allow"],["b","c"]],"passed":false},{"actual":[["allow","deny","deny","overflow","allow"],["b"]],"check":"partially refilled not idle","expected":[["allow","allow","allow","overflow","allow"],["b"]],"passed":false},{"actual":[["allow","allow","allow","allow","allow","overflow","allow","allow","allow","allow","deny","overflow"],["a","c"]],"check":"random keys","expected":[["allow","allow","allow","allow","allow","allow","allow","allow","allow","allow","allow","overflow"],["a","c"]],"passed":false}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"busy key not evicted\", \"actual\": [[\"allow\", \"deny\", \"allow\", \"overflow\", \"allow\"], [\"b\", \"c\"]], \"expected\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\"], [\"a\", \"c\"]], \"passed\": false}, {\"check\": \"lru order refreshed\", \"actual\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\"], [\"c\", \"b\"]], \"expected\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\"], [\"c\", \"b\"]], \"passed\": true}, {\"check\": \"refilled key is idle\", \"actual\": [[\"allow\", \"deny\", \"overflow\", \"allow\", \"overflow\"], [\"b\"]], \"expected\": [[\"allow\", \"allow\", \"overflow\", \"allow\", \"allow\"], [\"a\"]], \"passed\": false}, {\"check\": \"new key starts full\", \"actual\": [[\"allow\", \"deny\", \"allow\", \"allow\", \"deny\", \"allow\"], [\"b\", \"c\"]], \"expected\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\"], [\"b\", \"c\"]], \"passed\": false}, {\"check\": \"partially refilled not idle\", \"actual\": [[\"allow\", \"deny\", \"deny\", \"overflow\", \"allow\"], [\"b\"]], \"expected\": [[\"allow\", \"allow\", \"allow\", \"overflow\", \"allow\"], [\"b\"]], \"passed\": false}, {\"check\": \"random keys\", \"actual\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"overflow\", \"allow\", \"allow\", \"allow\", \"allow\", \"deny\", \"overflow\"], [\"a\", \"c\"]], \"expected\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"overflow\"], [\"a\", \"c\"]], \"passed\": false}], \"passed\": false}\n"},"broken":{"elapsed_ms":41.394,"exit_code":1,"observations":[{"actual":[["deny","deny","deny","overflow","deny"],["b","c"]],"check":"busy key not evicted","expected":[["allow","allow","allow","allow","allow"],["a","c"]],"passed":false},{"actual":[["deny","deny","allow","deny","deny"],["c","b"]],"check":"lru order refreshed","expected":[["allow","allow","allow","allow","allow"],["c","b"]],"passed":false},{"actual":[["deny","deny","overflow","deny","overflow"],["b"]],"check":"refilled key is idle","expected":[["allow","allow","overflow","allow","allow"],["a"]],"passed":false},{"actual":[["deny","deny","deny","deny","deny","allow"],["b","c"]],"check":"new key starts full","expected":[["allow","allow","allow","allow","allow","allow"],["b","c"]],"passed":false},{"actual":[["deny","deny","deny","overflow","deny"],["b"]],"check":"partially refilled not idle","expected":[["allow","allow","allow","overflow","allow"],["b"]],"passed":false},{"actual":[["deny","allow","allow","deny","allow","overflow","allow","allow","allow","deny","deny","overflow"],["a","c"]],"check":"random keys","expected":[["allow","allow","allow","allow","allow","allow","allow","allow","allow","allow","allow","overflow"],["a","c"]],"passed":false}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"busy key not evicted\", \"actual\": [[\"deny\", \"deny\", \"deny\", \"overflow\", \"deny\"], [\"b\", \"c\"]], \"expected\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\"], [\"a\", \"c\"]], \"passed\": false}, {\"check\": \"lru order refreshed\", \"actual\": [[\"deny\", \"deny\", \"allow\", \"deny\", \"deny\"], [\"c\", \"b\"]], \"expected\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\"], [\"c\", \"b\"]], \"passed\": false}, {\"check\": \"refilled key is idle\", \"actual\": [[\"deny\", \"deny\", \"overflow\", \"deny\", \"overflow\"], [\"b\"]], \"expected\": [[\"allow\", \"allow\", \"overflow\", \"allow\", \"allow\"], [\"a\"]], \"passed\": false}, {\"check\": \"new key starts full\", \"actual\": [[\"deny\", \"deny\", \"deny\", \"deny\", \"deny\", \"allow\"], [\"b\", \"c\"]], \"expected\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\"], [\"b\", \"c\"]], \"passed\": false}, {\"check\": \"partially refilled not idle\", \"actual\": [[\"deny\", \"deny\", \"deny\", \"overflow\", \"deny\"], [\"b\"]], \"expected\": [[\"allow\", \"allow\", \"allow\", \"overflow\", \"allow\"], [\"b\"]], \"passed\": false}, {\"check\": \"random keys\", \"actual\": [[\"deny\", \"allow\", \"allow\", \"deny\", \"allow\", \"overflow\", \"allow\", \"allow\", \"allow\", \"deny\", \"deny\", \"overflow\"], [\"a\", \"c\"]], \"expected\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"overflow\"], [\"a\", \"c\"]], \"passed\": false}], \"passed\": false}\n"},"fixed":{"elapsed_ms":39.92,"exit_code":0,"observations":[{"actual":[["allow","allow","allow","allow","allow"],["a","c"]],"check":"busy key not evicted","expected":[["allow","allow","allow","allow","allow"],["a","c"]],"passed":true},{"actual":[["allow","allow","allow","allow","allow"],["c","b"]],"check":"lru order refreshed","expected":[["allow","allow","allow","allow","allow"],["c","b"]],"passed":true},{"actual":[["allow","allow","overflow","allow","allow"],["a"]],"check":"refilled key is idle","expected":[["allow","allow","overflow","allow","allow"],["a"]],"passed":true},{"actual":[["allow","allow","allow","allow","allow","allow"],["b","c"]],"check":"new key starts full","expected":[["allow","allow","allow","allow","allow","allow"],["b","c"]],"passed":true},{"actual":[["allow","allow","allow","overflow","allow"],["b"]],"check":"partially refilled not idle","expected":[["allow","allow","allow","overflow","allow"],["b"]],"passed":true},{"actual":[["allow","allow","allow","allow","allow","allow","allow","allow","allow","allow","allow","overflow"],["a","c"]],"check":"random keys","expected":[["allow","allow","allow","allow","allow","allow","allow","allow","allow","allow","allow","overflow"],["a","c"]],"passed":true}],"passed":true,"stderr":"","stdout":"{\"observations\": [{\"check\": \"busy key not evicted\", \"actual\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\"], [\"a\", \"c\"]], \"expected\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\"], [\"a\", \"c\"]], \"passed\": true}, {\"check\": \"lru order refreshed\", \"actual\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\"], [\"c\", \"b\"]], \"expected\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\"], [\"c\", \"b\"]], \"passed\": true}, {\"check\": \"refilled key is idle\", \"actual\": [[\"allow\", \"allow\", \"overflow\", \"allow\", \"allow\"], [\"a\"]], \"expected\": [[\"allow\", \"allow\", \"overflow\", \"allow\", \"allow\"], [\"a\"]], \"passed\": true}, {\"check\": \"new key starts full\", \"actual\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\"], [\"b\", \"c\"]], \"expected\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\"], [\"b\", \"c\"]], \"passed\": true}, {\"check\": \"partially refilled not idle\", \"actual\": [[\"allow\", \"allow\", \"allow\", \"overflow\", \"allow\"], [\"b\"]], \"expected\": [[\"allow\", \"allow\", \"allow\", \"overflow\", \"allow\"], [\"b\"]], \"passed\": true}, {\"check\": \"random keys\", \"actual\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"overflow\"], [\"a\", \"c\"]], \"expected\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"overflow\"], [\"a\", \"c\"]], \"passed\": true}], \"passed\": true}\n"}},"verified":true,"visibility":"public"}