割り込み順序でキャッシュの嘘を測る

目標

決定的なシミュレーターで、キャッシュの書き込み・読み取りの戦略6つを、同じ割り込みの順序に入れてみて、シナリオごとに古い読み取りの数と最大の古さ(ms)を測ります。最後に、永遠に直らない組み合わせを見分け、数字を根拠に戦略を1つ選びます。

なぜ重要なのか

キャッシュの不整合は、再現が困難です。数msの差で重なった2つのリクエストが作り、翌日に再実行すると消えます。そのため、「書き込み後に削除すれば大丈夫」「TTLがあるから、最大でもTTLの分だけ間違う」のような思い込みが、検証されないまま残ります。操作が終わる時刻を整数のmsで固定したシミュレーターなら、同じ順序を何度でも再実行でき、戦略だけを変えて同じ順序に入れてみることができます。パターンの説明は「Redisとキャッシュ」コースにあるので、ここでは順序と数字だけを見ます。

用意するもの

/opt/fixtures/svccs/cache/の下にあります。読み取り専用で使ってください。

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}}]

このコードブロックの韓国語の説明は、順に、sim.pyはシミュレーターで、冒頭の説明に基本操作・ジェネレーターのルール・コマンドラインの使い方があること、example_strategies.pyは開始用の雛形でwrite_updateとread_asideがあること、scenarios/*.jsonは5つのシナリオで、name・about(説明)・initial・warm(事前に埋めたキー)・ttl_ms・delay_ms・actors(name・kind(readまたはwrite)・key・value・start・操作ごとのミリ秒を持つlat)を持つこと、を述べています。

コマンドライン: python3 /opt/fixtures/svccs/cache/sim.py <시나리오.json> <전략파일.py> <전략이름> > 기록.json(プレースホルダーは、順にシナリオのファイル、戦略のファイル、戦略の名前、記録のファイルです) 戦略の名前はupdate・delete_after・delete_before・double_delete・cas・ttlで、それぞれが使う関数は、sim.pyのSTRATEGIESの表にあります(ttlは、write_delete_after + read_asideに、シナリオのttl_msを渡します)。

記録の形

events(操作が終わった順序、seq・t・actor・op …)、commits(seq・key・version・value・t = コミット時刻・writer)、reads(seq = その読み取りの最後の操作のseq・actor・key・start・t = 終わった時刻・value・version)、final_db、final_cache(キーごとのvalue・version・set_t・expires、またはnull)です。

測定のルール

오래된 읽기  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

このコードブロックの韓国語の説明は、順に、古い読み取りとは、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であること、を述べています。

ステップ

/root/svccs/cache/を作成し、example_strategies.pyを/root/svccs/cache/strategies.pyにコピーしたあと、s1-two-writersシナリオをupdate戦略で実行した記録を、/root/svccs/cache/s1-update.log.jsonに保存します。
strategies.pyにmeasure(log)を「測定のルール」のとおりに作成し、ステップ1の記録を測った結果を、/root/svccs/cache/s1-update.measure.jsonに保存します。採点ツールは、隠しシナリオの記録でmeasureを再び呼び出します。
write_delete_after(コミット → キャッシュ削除)とwrite_delete_before(キャッシュ削除 → コミット)を作成します。書き込み関数は、(key, value, opts)を受け取るジェネレーターです。
is_newer(cached, new)(キャッシュが空か、newが厳密に大きいときだけ真)、write_cas(コミット → 受け取ったバージョンでcache_set_if)、read_aside_cas(read_asideと同じだが、埋めるときにcache_set_if)を作成します。cache_set_ifの最後の引数としてis_newerを渡します。
write_double_delete(キャッシュ削除 → コミット → ("sleep", opts["delay_ms"]) → キャッシュ削除)を作成します。
5つのシナリオ × 6つの戦略をすべて実行してmeasureした結果を、/root/svccs/cache/results.jsonに{시나리오 name: {전략 이름: measure 결과}}の形式で保存します(コード内の韓国語は、順に「シナリオ」「戦略の名前」「結果」を意味する語です)。
ttl戦略のシナリオごとのmax_stale_msを集めて、/root/svccs/cache/ttl.jsonに、ttl_ms(シナリオのttl_ms、整数)・max_stale_ms_by_scenario・exceeds_ttl(max_stale_msがttl_msより大きいシナリオの名前、名前の昇順のリスト)を書きます。採点ツールは、あなたのttl戦略も隠しシナリオで再び実行します。
/root/svccs/cache/choice.jsonに、stuck(戦略ごとに、stuckが真だったシナリオの名前のリスト、ソート済み)・safe(どのシナリオでもstuckでない戦略、ソート済み)・chosen(safeのうち、シナリオごとのmax_stale_msの最大値がもっとも小さいもの、同じならstale_readsの合計が小さいもの、それでも同じなら名前順)・chosen_worst_ms(その最大値)を書きます。

参考

ジェネレーターでx = yield ("db_read", key)と書くと、xに操作の結果が入ります。読み取りの戦略は、読んだ値をreturnします。
採点ツールは、あなたの戦略を隠しシナリオで実行して、操作の記録を1行ずつ基準と突き合わせます。ステップに書かれた順序と引数をそのまま守ってください。操作を1つ足したり引いたりしても、記録が変わります。
strategies.pyは、採点ツールが読み込みます。結果のファイルを作るコードは、別のスクリプトかif __name__ == "__main__":の下に置いてください。
よくある間違い: 古さを書き込みの開始時刻から測ること、stuckなのにmax_stale_msに観測した最大値を書くこと(上限がありません)、is_newerの比較の方向を逆にすること。

シミュレーターを1回実行する

example_strategies.pyを/root/svccs/cache/strategies.pyにコピーし、s1-two-writers.jsonをupdate戦略で実行した記録を、/root/svccs/cache/s1-update.log.jsonに保存してください。

sim.pyは、標準出力に記録のJSONを出します。>でファイルに受け取ってください。記録のeventsを見て、W1の遅いcache_setがW2よりあとに到着する行を探してみてください。

古さをコミットを基準に測る

strategies.pyに、測定のルールどおりmeasure(log)を作成し、ステップ1の記録を測った結果を、/root/svccs/cache/s1-update.measure.jsonに保存してください。採点ツールは、隠しシナリオの記録でmeasureを再び呼び出します。

読み取りのseqとコミットのseqを比較して、「読み取りが終わる前にコミットされたもの」だけを見ます。古さの基準は、返されたバージョンの次のバージョンがコミットされた時刻です。キャッシュに有効期限のない古い値が残っているなら、観測した最大値がいくつであっても、上限はありません。

書き込みのあとに削除、削除のあとに書き込み

strategies.pyにwrite_delete_after(コミット → キャッシュ削除)とwrite_delete_before(キャッシュ削除 → コミット)を作成してください。採点ツールが、隠しシナリオで2つの戦略の操作の記録を基準と突き合わせます。

書き込み関数は、(key, value, opts)を受け取るジェネレーターで、操作を2つyieldします。結果を使わない操作もyieldしないと、シミュレーターが時間を進めません。

バージョンを比較したときだけ上書きする

strategies.pyにis_newer(cached, new)・write_cas・read_aside_casを作成してください。採点ツールは、is_newerを直接呼び出し、cas戦略を隠しシナリオで基準と突き合わせます。

is_newerは、キャッシュにあるバージョン(cached、なければNone)と、入れようとしているバージョン(new)を受け取ります。古い値が新しい値を上書きできないようにするには、どちらが大きい必要があるでしょうか。write_casは、db_writeが返したバージョンを使います。

遅延二重削除

strategies.pyにwrite_double_delete(キャッシュ削除 → コミット → ("sleep", opts["delay_ms"]) → キャッシュ削除)を作成してください。採点ツールが、隠しシナリオで基準と突き合わせます。

sleepは結果のない操作ですが、yieldして初めて、その分の時間が流れます。待つ時間はシナリオごとに異なるので、optsから読み取ってください。

5つのシナリオ × 6つの戦略

5つのシナリオを6つの戦略ですべて実行してmeasureした結果を、/root/svccs/cache/results.jsonに{シナリオのname: {戦略の名前: measureの結果}}の形式で保存してください。

sim.pyをimportして、sim.run_strategy(シナリオ, 戦略モジュール, 名前)を呼び出すと、記録のdictがそのまま得られます。シナリオの名前は、ファイルの中のnameです。

TTLは古さをどこまで抑えるか

ttl戦略のシナリオごとのmax_stale_msを集めて、/root/svccs/cache/ttl.jsonにttl_ms・max_stale_ms_by_scenario・exceeds_ttlを書いてください。採点ツールは、あなたのttl戦略も隠しシナリオで再び実行します。

TTLは、キャッシュに入れた時刻から数えます。コミットよりかなりあとに古い値が入ってくると、どうなるでしょうか。ttl戦略は、read_asideがopts["ttl_ms"]をsetに渡して初めて動作します。

数字で戦略を選ぶ

results.jsonを使って、/root/svccs/cache/choice.jsonにstuck・safe・chosen・chosen_worst_msを書いてください。

1つのシナリオででもstuckなら、その戦略は古さに上限がないので、safeではありません。あるシナリオで古い読み取りが0だったことは、安全の根拠になりません。