コンペア・アンド・スワップ

当たり前だろうと思う事でも、世の中当たり前じゃなかったり、当たり前という基準は各々の判断でしかない。
コンペア・アンド・スワップもそんな当たり前なことの一つです。

お題

預金口座で残高を更新するシステムを作る。
預金口座は複数のATMから同時に振込や引落が行われる可能性がある。

方法

口座の更新は複数のATMから同時に行われる可能性があり、残高を正しく保つには、次のいずれかの方法をとる事になる。

預入要求、払出要求という操作をキューで管理し、残高の更新は１つのスレッドが行う。
コンペアアンドスワップを使う。

1の方法はシステムが大きくなりますが、考え方としてはシンプルです。
2のコンペア・アンド・スワップが今回説明したい内容で、覚えておくと色々なところで応用がきくかもしれません。

アルゴリズム

コンペア・アンド・スワップを使った更新アルゴリズムは次の通り。

値を読み出す。
加算、減算等の計算の処理を行う
コンペアアンドスワップ(もう一度値を読み出し古い値のままであれば2で更新した新しい値に置き換え)を行う。
3の処理が失敗した場合は、1に戻ってやり直す。

ある意味当たり前の話ですが、古い値と同じときに、新しい値に置き換えるというのが重要です。
古い値と同じということは、他から更新されていないということを示しているからです。

コンペア・アンド・スワップは、アトミックに(＝分解できない一つの操作として)行う必要があり、また成功したかどうかの結果を返すことが出来る必要があります。

なぜアトミックに操作できないと不味いかというと、例えば古い値と比較して置き換えれると判断した後に、別のスレッドが値を置き換えたりすると比較の結果が無意味となった上、置き換えられた値を更に上書きすることになり一貫性が保証できないからです。
その為、比較と交換の操作は分解できない１命令として操作する必要があります。

ちなみにコンペア・アンド・スワップをアトミックに操作する命令ですが、マシン語レベルですとx86系の場合、i486以降でcmpxchgという便利な命令があったりします。
SQLならばUPDATEで更新を行う際に、WHERE句でプライマリーキーと古い値で比較して更新を行い、更新された行数が1であれば成功、更新された行数が0であれば失敗と見なすのが良いでしょう。