Measure the Cache's Lies by Interleaving Order

Goal

You will run six cache write and read strategies through the same cut-in orders in a deterministic simulator, and measure the number of stale reads and the maximum staleness (ms) for each scenario. At the end you will pick out the combinations that never get fixed and choose one strategy based on the numbers.

Why it matters

Cache inconsistency is hard to reproduce. Two requests overlapping by a few ms create it, and it disappears when you rerun it the next day. So beliefs such as "write then delete is fine" and "with a TTL it is wrong for at most the TTL" remain without verification. In a simulator where the time each operation finishes is pinned as an integer number of ms, you can rerun the same order again and again, and swap only the strategy to put it through the same order. The pattern explanations are in the "Redis and Caching" course, so here you look only at orders and numbers.

Materials

They are under /opt/fixtures/svccs/cache/. Only read them.

sim.py                 시뮬레이터. 맨 위 설명에 원시 연산·제너레이터 규칙·명령줄 사용법이 있다
example_strategies.py  시작 틀 — write_update 와 read_aside
scenarios/*.json       시나리오 다섯. name · about(설명) · initial · warm(미리 채운 키) · ttl_ms · delay_ms ·
                       actors[{name, kind(read|write), key, value, start, lat{연산: ms}}]

Command line: python3 /opt/fixtures/svccs/cache/sim.py <시나리오.json> <전략파일.py> <전략이름> > 기록.json (the arguments are the scenario file, the strategy file, and the strategy name, and the output is redirected to a log file). The strategy names are update·delete_after·delete_before·double_delete·cas·ttl, and the function each one uses is in the STRATEGIES table of sim.py (ttl gives the scenario's ttl_ms to write_delete_after + read_aside).

Shape of the log

events (in the order operations finished, seq·t·actor·op …), commits (seq·key·version·value·t = commit time·writer), reads (seq = the seq of that read's last operation · actor · key · start · t = finish time · value · version), final_db, and final_cache (for each key, value·version·set_t·expires or null).

Measurement rule

오래된 읽기  r 보다 작은 seq 로 커밋된 같은 키의 버전 중 가장 큰 것이 r.version 보다 크다
오래됨(ms)   r.t − (버전 r.version+1 커밋의 t)            ← 쓰기를 시작한 시각이 아니다
stuck        끝났을 때 final_cache 의 항목이 expires 가 null 이고 version 이 final_db 보다 작다
돌려줄 것    {"stale_reads": 정수, "max_stale_ms": 정수 또는 null, "stuck": 불리언}
             stuck 이면 max_stale_ms 는 null(상한 없음), 오래된 읽기가 없으면 0

Steps

1. Create /root/svccs/cache/, copy example_strategies.py to /root/svccs/cache/strategies.py, and save the log from running the s1-two-writers scenario with the update strategy to /root/svccs/cache/s1-update.log.json.
2. In strategies.py, create measure(log) following the "Measurement rule," and save the result of measuring the step 1 log to /root/svccs/cache/s1-update.measure.json. The grader calls measure again with the logs of hidden scenarios.
3. Create write_delete_after (commit → cache delete) and write_delete_before (cache delete → commit). A write function is a generator that takes (key, value, opts).
4. Create is_newer(cached, new) (true only when the cache is empty or new is strictly greater), write_cas (commit → cache_set_if with the version it received), and read_aside_cas (the same as read_aside, but uses cache_set_if when filling). Give cache_set_if the function is_newer as its last argument.
5. Create write_double_delete (cache delete → commit → ("sleep", opts["delay_ms"]) → cache delete).
6. Run all five scenarios × six strategies, and save the measure results to /root/svccs/cache/results.json as {시나리오 name: {전략 이름: measure 결과}} (scenario name → strategy name → measure result).
7. Collect the max_stale_ms of the ttl strategy for each scenario, and in /root/svccs/cache/ttl.json write ttl_ms (the ttl_ms of the scenarios, an integer), max_stale_ms_by_scenario, and exceeds_ttl (a list of the scenario names whose max_stale_ms is greater than ttl_ms, in alphabetical order). The grader also reruns your ttl strategy on the hidden scenarios.
8. In /root/svccs/cache/choice.json, write stuck (for each strategy, the list of scenario names where stuck was true, sorted), safe (the strategies that are not stuck in any scenario, sorted), chosen (among safe, the one whose maximum over scenarios of max_stale_ms is smallest; if equal, the one with the smaller sum of stale_reads; if still equal, by name), and chosen_worst_ms (that maximum).

Notes

• If you write x = yield ("db_read", key) in a generator, the result of the operation goes into x. A read strategy returns the value it read.
• The grader runs your strategies on the hidden scenarios and compares the operation log line by line with the reference. Keep the order and arguments written in the steps as they are: adding or removing even one operation changes the log.
• The grader imports strategies.py. Put the code that produces the result files in a separate script or under if __name__ == "__main__":.
• Common mistakes: measuring staleness from the time the write started, writing the observed maximum in max_stale_ms when stuck (there is no upper bound), and reversing the comparison direction of is_newer.

Run the simulator once

Copy example_strategies.py to /root/svccs/cache/strategies.py, and save the log from running s1-two-writers.json with the update strategy to /root/svccs/cache/s1-update.log.json.

sim.py prints the log JSON to standard output. Capture it to a file with >. Scan the events of the log and look for the line where W1's late cache_set arrives after W2.

Measure staleness relative to the commit

Create measure(log) in strategies.py following the measurement rule, and save the result of measuring the step 1 log to /root/svccs/cache/s1-update.measure.json. The grader calls measure again with the logs of hidden scenarios.

Compare the seq of the read with the seq of the commits and look only at those "committed before the read finished." The reference for staleness is the time at which the version right after the returned version was committed. If an old value with no expiry remains in the cache, there is no upper bound, whatever maximum you observed.

Write then delete, delete then write

Create write_delete_after (commit → cache delete) and write_delete_before (cache delete → commit) in strategies.py. The grader compares the operation logs of the two strategies on hidden scenarios with the reference.

A write function is a generator that takes (key, value, opts) and yields two operations. You must yield even an operation whose result you do not use, or the simulator does not let time pass.

Overwrite only by comparing versions

Create is_newer(cached, new), write_cas, and read_aside_cas in strategies.py. The grader calls is_newer directly, and compares the cas strategy on hidden scenarios with the reference.

is_newer takes the version in the cache (cached, None if absent) and the version you want to put in (new). To keep an old value from overwriting a new one, which side has to be greater? write_cas uses the version that db_write returned.

Delayed double delete

Create write_double_delete (cache delete → commit → ("sleep", opts["delay_ms"]) → cache delete) in strategies.py. The grader compares it with the reference on hidden scenarios.

sleep is an operation with no result, but you must yield it for that much time to pass. The waiting time differs for each scenario, so read it from opts.

Five scenarios × six strategies

Run all five scenarios with all six strategies, and save the measure results to /root/svccs/cache/results.json as {scenario name: {strategy name: measure result}}.

If you import sim.py and call sim.run_strategy(scenario, strategy module, name), you get the log dict directly. The scenario name is the name inside the file.

How far does a TTL bound staleness

Collect the max_stale_ms of the ttl strategy for each scenario, and write ttl_ms, max_stale_ms_by_scenario, and exceeds_ttl to /root/svccs/cache/ttl.json. The grader also reruns your ttl strategy on hidden scenarios.

A TTL is counted from the time the value is put into the cache. What happens if an old value comes in well after the commit? The ttl strategy works only if read_aside passes opts["ttl_ms"] to set.

Choose a strategy by the numbers

From results.json, write stuck, safe, chosen, and chosen_worst_ms to /root/svccs/cache/choice.json.

If a strategy is stuck in even one scenario, its staleness has no upper bound, so it is not safe. That the stale reads were 0 in some scenario is not evidence of safety.