Lock-free スナップショットの撮り方を説明してみる
マルチスレッドなどの環境下で時間経過によって勝手に変化する複数の変数を読みたい場面は多くあります。
しかしCPUは一度に一つしか値を読み書きできないので、簡単には出来ません。
何故なら読んでるそばから値が変動してでたらめな値を読むかも知れないからです。
変動してるものを読むのだから読む側が完璧じゃなくても仕方ないという妥協は有り得ますが
特定のある一瞬の時刻での状態を写真のようにパチリとフィルムに収められたら嬉しいですよね。
一番簡単なのはロックを取りながら読む事ですが、ロックは諸般の事情により使えない事とします。
前提
値が勝手に変動するという状況が分かりにくいと思うので、適当な例えとして卵の孵化を想像してみましょう。
「卵」→「ヒビ」→「ひよこ」 の順でランダムに勝手に進んで行きます。止めることは出来ませんし後戻りもしません。
こんな卵が複数ある孵化器の監視を任されたとします。卵の状態が今どんな感じかを訊かれるので適切に答えましょう。
ただし、一度に目視できるのは卵一つだけです。卵は今回は図の関係で3つだけとしますがこれ以上に増えても手順は同様です。
レベル1
「全部の卵が『ヒビ』状態なのか教えて」
一度には見れないので、一個ずつ卵を見てみましょう。A→B→Cの順に卵を確認します。
たまたま全部にヒビが入っていましたね、これで「全部が『ヒビ』でした」と教えて良いのでしょうか？ダメです。
何故なら確認中に卵の状態が変わったかも知れないからです。もし見てない所での卵の状態がこんな感じだったらどうでしょう？
もしこうなら、仮に卵の状態を常時同時に監視し続けれたとしても「全部が『ヒビ』」という瞬間は一瞬たりとも発生していないのです。発生していなかった状態を観測して報告してしまっては監視員失格です。ではどうすれば良いのでしょうか？
答えは二度見れば良いのです。
二度見て、全てで『ヒビ』状態だった場合、どんな状況を想定しても緑色の横線を引いた瞬間は必ず3つとも『ヒビ』状態だったと言わざるを得ません。もしそうでなかったら、二度目見た時に状態が変わっていないと説明が付かないからです。
つまり合計6回観測して、全部『ヒビ』だった場合に限り「そうだよ」と返すだけですね。とても簡単です。コードに書くならこんな感じ。
static const int TAMAGO=0, HIBI=1, HIYOKO=2; int eggs[3]; // 勝手に状態が変わる卵たち bool check_hibi(){ for(int i=0; i<2; ++i) // 二度見する for(int j=0; j<3; ++j) // 全部の卵を見る if(eggs[j] != HIBI) return false; return true; }
スナップショットの考え方は大まかにこの通りです。
補足「そんな答えで大丈夫か」
緑の線の時に全部が『ヒビ』だからって、2度目見終わった後で報告する前の間にどれかが『ひよこ』になる場合があるよね、嘘の状態を報告することになるよね。と気になる方も居ると思います。
確かにその通りです。報告を受け取った側はその報告を受けたからといってその時もずっと『ヒビ』の状態が維持されている保障は全くありません。
しかし考えてみてください、全知全能の神が光より速く全ての卵の状態を観測して超すごい手段で報告をよこしてくれたとしても、全く同じ問題は起きます。ここで出来る最良の事は「全てが『ヒビ』だった瞬間が一瞬でも観測された」事を報告する事なのです。
レベル2
「全部の卵の状態を教えて」
やっとスナップショットらしくなって来ました。
方法は全く同じく「二度見する」だけです。
この場合は緑色の線の所でA=『ひよこ』B=『卵』C=『ヒビ』であることを保障できます。
何故なら2回見た間で一致しているからです。では一致しなかったらどうするのでしょう？
赤いキザギザ線のうちどこかでC卵の状態が変わっているので、安易にスナップショットがとれたとは言えません。
その場合は「更にもう一度見る」だけです。
一致するまで何度でも観測すれば良いです。コードで書くならこんな感じ。
int* snapshot_eggs(){ int* const snapshot = static_cast<int*>malloc(3*sizeof(int)); for(int i=0; i<3; ++i) snapshot[i] = eggs[i]; // 初回の観測 while(true){ bool check = true; for(int i=0; i<3; ++i){ if(snapshot[i] != eggs[i]) check = false; // 前回のチェックと合わなかったら失敗 snapshot[i] = eggs[i]; // 次回チェックあるいは返答のために記憶 } if(check == true) return snapshot; // 二度観測した物が合ったらスナップショット成功 // 合わなかったらスナップショットやり直し } }
ロックを取っていないのでこのアルゴリズムはノンブロッキングに分類されます
また、値が書き変わり続けた場合にスナップショットがいつまでも成功しない状況(=starvation)が有りうるため、このスナップショットアルゴリズムはlock-freeです。値が書き変わり続ける場合、自分は失敗しますが他のスレッドの何らかの操作は進んでいるため進行保障は満たされます。
レベル3
さて、ここまでの状況はとても簡単でした。何故なら卵は孵化する方向にしか進まないから起こり得る状況の数が知れてるからです。もう少し難しい状況を考えてみましょう。
さて信号機は状態遷移が巡回してしまいます。地点の離れた複数の信号機をどうやって一人でスナップショットを取ったら良いのでしょうか？
結論から言うと無理です。2つの信号を例にあげます。
青信号を2回連続で観測したからと言って、その2回の青信号が同一の青信号とは限りません。2回目に見た青信号はぐるっと一周した物で、ひょっとしたら一瞬たりとも2つの信号が同一になった瞬間は存在しないかもしれません。
しかしプログラミングの世界ならもう少しがんばれます。
信号機に信号と一緒に変化するカウンタを付けるよう国土交通省あたりに掛け合えば良いのです。*1
こうすれば赤信号を二回観測してもそれが同一の赤信号なのかぐるっと一周してきた赤信号なのかはたまた何周かした後のものかを区別できます。そうすればもうこっちの物でヒヨコのスナップショットがそのまま適用できます。桁溢れが心配ならカウンタに64bit用意しておけばたぶんカウンタが巡回する前に宇宙が崩壊することでしょう*2。
こうすることで無事にスナップショットを撮れます。
memcachedはgetsコマンドを使う事でキーごとに取り付けられたユニーク値を獲得できます。この値は64bit有って、memcachedが起動してから加えた操作の論理クロックが書き込み時に一緒に書き込まれる物で、一言で言うとここで付けたカウンタと全く同じ使い方をして構わない物です。
つまりmemcachedはgetsコマンドで、ユニーク値を比較し複数の任意のキーバリューペアのスナップショットを取れます！*3
さて、信号機ですがカウンタ値を返されても困る、実際の信号の値を返してくれ、というのが普通だと思います。
信号とカウンタとを一瞬で読めれば完璧なんですが常にそれが可能とは限りませんし、カウンタと信号の変化が完璧に同時とも限りません。
困りましたね、しかしそこにもスナップショットが適用できます。
カウンタを読む→信号を読む→カウンタを読む(二度目)→信号を読む(二度目) という作法で可能です。コードで書くとこんな感じ。
struct lamp_t{ int lamp_; uint64_t cnt_; lamp_t(const lamp_t& org) :lamp_(org.lamp_),cnt_(org.cnt_){ // スナップショットコピーコンストラクタ while(true){ if(lamp_ == org.lamp_ && cnt_ == org.cnt_) return; // 一致したので成功 lamp_ = org.lamp_; cnt_ = org.cnt_; // 失敗したのでもう一回コピー } } bool operator==(const lamp_t& rhs)const{ // スナップショット比較 if(lamp_ != rhs.lamp_ || cnt_ != rhs.cnt_) return false; if(lamp_ != rhs.lamp_ || cnt_ != rhs.cnt_) return false; // 二度見する必要がある return true; } lamp_t& operator=(const lamp_t& rhs){ // スナップショット代入 lamp_ = rhs.lamp_; cnt_ = rhs.cnt_; while(true){ // 一致するまで繰り返す if(lamp_ == rhs.lamp_ && cnt_ == rhs.cnt_) return *this; lamp_ = rhs.lamp_; cnt_ = rhs.cnt_; // 一致しなかったら読みなおし } } };
信号の値を読むときはこれらのメンバ関数を使って、ヒヨコの時と同じ作法でスナップショットを取る事で達成できます。
まとめ
今回は複数の値をあたかも一瞬で全部確認したかのようにチェックするLock-freeスナップショットについて解説しました。
複数の値を読み出す操作を二回行なって、一致を見るだけで可能です。*4
次回はこれを使ってk-Compare Single Swap(k個の値が一定の値であることをチェックしてそのうち一つを書き換えるまでをアトミックに行う)を実現してみます。
