概要
マルチプロセス環境配下における、同一レコードへの書き込みが大量に発生するwrite heabyな環境でmemcachedの更新をどうやってatomicに行うかを考えた時に出てきたスピンロック的なことやってみた記事。
memcachedとは書いたもののCAS操作を提供しているミドルウェアなら当てはまるしロック機構をクライアントで頑張ってるアプリケーションでも似たような話になると思う。
想定シナリオ
ユーザアクセスなり何かしらの動作が発生するたびに何かをインクリメントしたいケースがあったとしてcasを用いてある程度の原子性を持たせて実装しようとすると以下のようになる。
$ret = $mem->gets('test'); ($cas, $val) = @$ret; $val++; $mem->cas('test', $cas, $val));
ここで問題となるのは以下が失敗する可能性のある命令であるということ。例えばこのコードを同時に並列で動かしている場合にcas値を使った更新では一番先に更新を行ったプロセス以外は全て失敗となって何もしないということになる
$mem->cas('test', $cas, $val));
さくらインターネットさんのサンプル含めこの操作自体について調べていると以下のようにリトライすれば問題ないと言った記事があった。ざっくりいうと更新が成功するまでredoでループを繰り返していくというもの。マルチプロセスで動いている場合でも更新が成功するまでcas値の取得->更新を繰り返すのでインクリメントは必ず行われるよねと言った話。
foreach (1 .. $num) { $ret = $mem->gets('test'); ($cas, $val) = @$ret; $val++; unless ($mem->cas('test', $cas, $val)) { warn "$val update failed. retrying.\n"; redo; } }
ここで面白いなと思ったのがこの「更新が成功するまでredoを行う」という部分。(memcachedのCAS値の確認をロックと見立てれば) これはLinuxカーネルなんかでもよく使われるスピンロックに似ている！と思った。
ちなみにここではincrを例にしてますがmemcahced自体に備わっているincr命令はatomicでこっちが使えるケースなら今回取り上げる話は正直不要な話になります。
スピンロックとは
スピンロックとは共有リソースが2つ以上のプロセスによって同時に変更されるのを防ぐ方法です。複数プロセスが同時に同じリソースに更新を行おうとした際に最初のプロセスがロックを取得しレコードに関する更新権を得た状態になった際に、以降のプロセスはロックを取得できない状態となります。
この時に2つ目以降のプロセスはロックを獲得するために以下の動作をとることができます。
- ループしてロック獲得の処理
- sleepしてロック獲得の処理
- イベント発生をOS側に通知してもらうために依頼
ここで取り上げるのが「ループしてロック獲得の処理」これが一般的にいうスピンロックとなる。ループで何もしないという動作でロック獲得を待ち獲得できたら処理を行うという流れです。Linuxだとハードウェア関連の操作を行う際にこの辺はよく出てきたりします。
ちなみにこれ自体はLinux以外のOSでも利用されている，一般的な排他制御機構となります。実装例とかは基本linux以外で使ってるケースをあまり見ないので使う機会があまり無いのかもしれません。(ここはよくわからない)
スピンロックのメリット/デメリットは
スレッドが休止状態にならない。と言うのがメリットです。memcachedの上記のサンプルで言うならこのコード自体はLinuxのスケジューラが意図的に実行を取り上げない限りは実行可能状態で継続します。この場合CPUリソースはプロセスが放さないのでコンテキストスイッチが発生しない分高速にロックを獲得することができます。
デメリットはそのままでスレッドが休止状態にならないのでCPUリソースを食い続けます。また、スピンロックを保持したスレッドがCPU待ち状態になると、このスレッドが再度スケジューリングされるまで、スピンロックが解放されません。このため、スピンロック待ちの頻度が高くなりアプリケーション性能は劣化したりします。
そしてここで挙げたメリットであるコンテキストスイッチが発生しないのはスケジューラのプリエンプトが指定できるカーネル空間での話でユーザ空間として実装しようとしている今回のアプリケーションでは効果がだいぶ薄まります。
preempt_disableをカーネルはどこでやってるのか
カーネルスペースで実行されている場合、スピンロックを取得すると、実際にプリエンプションが無効になりますみたいな話を上で書いたけど結局どうやってんねんって思ったので調べた。
ざっくり言うとcurrent_thread_info()->preempt_disable_countをインクリメントしてプリエンプションを抑止
void preempt_disable(void) { BUG_ON(preempt_disable_count < 0 || preempt_disable_count == INT_MAX); if (preempt_disable_count++) return; thread_cpu_id = nondet_int(); assume(thread_cpu_id >= 0); assume(thread_cpu_id < NR_CPUS); lock_impl_lock(&cpu_preemption_locks[thread_cpu_id]); }
スピンロックの実装自体はこんな感じで書かれています。ロックを取得するまでループすると言った流れを取っているのがわかります。(プリエンプションの無効化なんかはここではなく呼び出し元でやってるのでしょうか。この辺はよくわからなかった。)。なんとなくでおった際のコメント入れてみました。
static __always_inline void arch_spin_lock(arch_spinlock_t *lock) { register struct __raw_tickets inc = { .tail = TICKET_LOCK_INC }; inc = xadd(&lock->tickets, inc); if (likely(inc.head == inc.tail)) goto out; for (;;) { unsigned count = SPIN_THRESHOLD; // inc.tail(元々)とinc.head(最新)を比較(__tickets_equal) do { // 一致するまでSPIN_THRESHOLD回繰り返す inc.head = READ_ONCE(lock->tickets.head); if (__tickets_equal(inc.head, inc.tail)) goto clear_slowpath; // 一致したら(goto clear_slowpath)で後処理 cpu_relax(); } while (--count); __ticket_lock_spinning(lock, inc.tail); } clear_slowpath: __ticket_check_and_clear_slowpath(lock, inc.head); // tailに1を加算し前の値を記録してロック操作を完了する out: barrier(); /* make sure nothing creeps before the lock is taken */ }
感想
スピンロックはユーザ空間で実装するのはメリットが少なそうなので素直にblockingなりで実装しよう。ロック期間が十分に小さい場合でも結局スケジューリング次第では期間が短いかの測定も難しそうだし。
ただユーザ空間で動くpthreadにspinlockなるものを見つけたのでいつかこれは試してみたい。(Cで今後がっつり開発する機会はないはずだけど。。)
int pthread_spin_destroy(pthread_spinlock_t *lock); #include <pthread.h> pthread_spinlock_t lock; int ret; ret = pthread_spin_destroy(&lock); /* spinlock is destroyed */ ### int pthread_spin_trylock(pthread_spinlock_t *lock); #include <pthread.h> pthread_spinlock_t lock; int ret; ret = pthread_spin_trylock(&lock); /* try to lock the spin lock */
ざっとみた感じpthreadでspinlockをやるにはCで書く必要がありそうな感じだしpythonやらから呼ぶのも大変そうなのでロック獲得をユーザ空間でやる場合にスピンロック使おうってケースはまあほぼなさそう。ポスグレの参考記事なんかも出てきたけどあれはあれでどうやって実装してるんだろう。
