x/sync/singleflight の注意点とゼロタイムキャッシュ

ISUCON7 の本戦では、更新処理の直後に、その更新操作を反映したデータを返さないといけない、しかもそのデータの計算がとても重いという問題を出題しました。

もともと ISUCON では「POSTが200を返したら、それ以降のGETリクエストにはその結果が反映されてなければいけない」というルールが課されることが多いのですが、今回の問題もそのバリエーションの一つといえます。

さて、今年になって singleflight を知り、この種の課題にも使えそうだと思っていました。
(参考 golang.org/x/sync/singleflightで重複呼び出しを排除する)

そこで今年の問題を事前に Go でチューニングして見るときに試してみたのですが、普通に適用しただけでは整合性が取れずに失敗してしまいました。そこで調べた singleflight の注意点とワークアラウンドを紹介しておきます。

singleflight の動作

Singleflight の主目的は、Thundering Herd問題の解決です。

例えば有効期限付きのキャッシュがあったとして、並列でそのリソースにアクセスされているときに有効期限が切れてしまうと、キャッシュを更新するためにソースに並列でリクエストを投げてしまうというのがキャッシュのThundering Herd問題です。次の図を見てください。

AとBが平行にSingleflight経由でCalcを呼び出していますが、Bが呼び出したときにはすでにAからのリクエストを実行中であるために、その結果を共有されるだけで実際の計算はされません。

これは一定時間でExpireするキャッシュを更新するときなどには全く問題ない挙動なのですが、Bが呼び出し前に更新処理をしていたときは問題が起こります。

上の図で、BはDataに対して Mod 2 という更新操作を行っていました。しかしその後Singleflight経由で呼び出したCalcは、その更新がされる前の状態をもとにした計算結果を返しています。これがクライアントにとって不整合として見える場合には、 singleflight をそのまま利用することはできません。

ワークアラウンド

こういったユースケースでも singleflight を使いつつ整合性を維持する方法として、ロックがあります。

上のシーケンス図で言えば、 "Mod 1" や "Get" といったデータアクセスは、図では明記されていないものの sync.Mutex などで排他されていると思います。この Mutex を、 Get の間だけでなく、 Calc が計算して、結果をまっている全部のクライアントに返すまでロックし続けます。そうすると "Mod 2" がロック待ちになるために実行できません。結果として B は、 "Mod 2" が反映されていないレスポンスを取得する危険を避けることができます。

ゼロタイムキャッシュ

pixiv private isucon 2016 攻略 (4/5) でも使っていた、個人的にゼロタイムキャッシュと呼んでいる手法は、整合性の問題を発生させません。そのため非常にISUCON向きです。

この手法をシーケンス図で表すと次のような感じになります。

(PlantUML)

Aのための計算を始めたあとにBとCから要求が来ますが、BとCにはAの要求を共有しません。Aのための計算が終わってから、BとCのための計算を始めます。BとCが受け取るレスポンスには、Bが行った"Mod 2"とCが行った"Mod 3"の両方が反映されていることになります。

今までイディオムとして繰り返し書いていましたが、 singleflight を真似てライブラリにしてみました。

• リポジトリ
• サンプルコード

サンプルコードは、100goroutineから10回ずつあるメソッドを呼び出すものです。実行すると次のような出力になります。

direct: called 1000 times, 0 errors
singleflight: called 145 times, 140 errors
ZeroTimeCache: called 151 times, 0 errors
ZeroTimeCacheDelay: called 19 times, 0 errors

• directは直接呼び出した場合で、1000回実際の呼び出しが発生しています。
• singleflightはsingleflight経由で呼び出した場合で、対象メソッドの呼び出しは145回に抑えられているものの、140回更新が反映されてない結果を観測してます。
• ZeroTimeCacheはこのライブラリを経由して呼び出した場合で、対象メソッドの呼び出しを151回に抑えつつ、整合性も保たれています。
• ZeroTimeCacheDelayはさらに、キャッシュ中で対象メソッドを呼び出す直前にsleepを挟んでいるものです。これで高並列度＆高頻度のゼロタイムキャッシュ呼び出しがビジーループにならなくなるのでCPUの空き時間を確保することができます。対象メソッドの呼び出し回数は19回まで減らすことができました。

まだドキュメントもREADMEも用意していませんが、コードはごくシンプルなので、ぜひ直接コードを読んでみてください。

うまくいかないワークアラウンド: ２回 Do() を呼ぶ

singleflight とゼロタイムキャッシュのシーケンス図を見ると、Bは singleflight.Do() を２回呼べば「今処理中」ではなくて「次」の結果を待てるようになって、ゼロタイムキャッシュと同じにできそうに見えます。

しかし、これはうまく行きません。 singleflight の最後のレスポンスを処理する部分は、共有ロックの取得を必要とするので場合によっては待ち時間が大きくなります。そしてそのロックの取得順序はFIFOになっていないため、Bによる２回めのDo()が先にロックを取得できてしまう可能性があるのです。

(PlantUML)