memcachedプロトコルCAS操作について

当ブログをご覧の皆様こんにちは。さくらインターネット研究所の大久保です。

ご存知の方も多いと思いますが、先日、分散KVSの一つであるkumofsが、バージョン0.4.0にてCAS操作をサポートされたそうです。以下は開発者である古橋さんの日記のURLです。

▽ kumofs-0.4.0リリース -CAS操作をサポート
http://d.hatena.ne.jp/viver/20100514/p1

今回は突然ですが、番外編としてCAS操作について取り上げたいと思います。

CAS操作とは?

CASは”Check and Set”の略で、KVS上でトランザクション処理を行うために必要なものです。それ自体少々複雑ですので、以前当ブログにてmemcachedプロトコルの紹介をした際には、CAS操作のコマンド説明は省いておりました。なお、これまでとりあげてきたFlareでは、CAS操作は既にサポートされております。

ここでは分かりやすい例として、ホームページのアクセスカウンタをKVSに保存し、更新するシチュエーションを考えてみます。カウンタを更新する場合、以下のような手順を踏むことになります。

1. KVSから現在のカウンタの値を取得する(例:取得した値は10であった)。
2. カウンタの値を1増やす(例:カウンタは11となった)。
3. KVSにカウンタの値を保存する(例:11という値をKVSに保存した)。

これでうまくいきそうですが、Webサーバのように複数プロセスが並行して動作しているとどうでしょうか?

1. [プロセス1] KVSから現在のカウンタの値を取得する(例:取得した値は10であった)。
2. [プロセス1] カウンタの値を1増やす(例:カウンタは11となった)。
3. [プロセス2] KVSから現在のカウンタの値を取得する(例:取得した値は10であった)。
4. [プロセス1] KVSにカウンタの値を保存する(例:11という値をKVSに保存した)。
5. [プロセス2] カウンタの値を1増やす(例:カウンタは11となった)。
6. [プロセス2] KVSにカウンタの値を保存する(例:11という値をKVSに保存した)。

結果的に、カウンタの値が2増えるはずのところが1しか増えないことになります。このようにあるプロセスが値を取得してから保存するまでに、別のプロセスが同じデータを取得して処理を行うと、不整合が発生します。

ここでCAS操作を用いると、KVSからデータを取得し処理を行い、KVSにデータを保存するまでに、別のプロセスがデータの更新を行った場合、それを検出することができます。上記の例だと(6)の操作が失敗することで更新の衝突を検出できます。

※ カウンターの操作であればCAS操作を使わなくてもincrコマンドで実現可能ですが、あえて使わない場合で説明します。

CAS操作を試す

通常のgetコマンドとsetコマンドをCAS操作に変更するには、それぞれgetsコマンドとcasコマンドに置き換えます。

getsとcasコマンドの文法は以下の通りです。

gets <key>
VALUE <key><flags><bytes><cas unique>
<data block>
cas <key><flags><exptime><bytes><cas unqiue>
<data block>

getsコマンドを発行すると、”cas unique”という値が返されます。このcas unique値を、データを保存する際にcasコマンドの引数として渡すことで更新の衝突を検出することができます。

実際に試してみます。

更新が衝突しない場合

! 初期値としてtestというキーにabcという値をセットする。
set test 0 0 3
abc
STORED
! getsコマンドでデータを取得する。cas unique値は7となった。
gets test
VALUE test 0 3 7
abc
END
! casコマンドで値をdefに変更する。
cas test 0 0 3 7
def
STORED
! getコマンドで確認すると正しく更新されている。
get test
VALUE test 0 3
def
END

更新が衝突する場合

以下のように、クライアントAが値を取得して更新するまでに、クライアントBが値を更新するシチュエーションを再現します。

• クライアントAにて
  

  ! getsコマンドでデータを取得する。cas unique値は8となった。
  gets test
  VALUE test 0 3 8
  def
  END

• クライアントBにて
  

  ! 値をabcdeに変更する。
  set test 0 0 5
  abcde
  STORED
  ! 更新を確認
  get test
  VALUE test 0 5
  abcde
  END

• クライアントAにて
  

  ! casコマンドでデータを保存する。
  cas test 0 0 3 8
  123
  EXISTS

EXISTSと表示され更新に失敗することが確認できます。

perlから使う

ここではプログラミング言語からの利用例としてperlのクライアントライブラリを一例として説明します。

getsおよびcasコマンドに対応しているモジュールはCache::Memcached::Fastがあります。このモジュールは以下のような形で簡単にインストールできます。

Cache::Memcached::Fastモジュールのインストール

% tar xvfz Cache-Memcached-Fast-0.19.tar.gz
% cd Cache-Memcached-Fast-0.19
% perl Makefile.PL
% make
% sudo make install

単純な例として、CAS操作を用いてカウンタを更新するプログラムと、CAS操作を用いずにカウンタを更新するプログラムを動作させ、実行結果を比較してみます。

CAS操作を用いない場合

• ソースコード
  

  #!/usr/bin/env perl
  use Cache::Memcached::Fast;
  $num = shift;
  $mem = Cache::Memcached::Fast->new({'servers' =>["127.0.0.1:11211"]});
  foreach (1 .. $num){
  $val = $mem->get('test');
  $val++;
  $mem->set('test',$val);
  }

• 実行結果
  

  ! まず初期値としてtestに0をセットしておく。
  % telnet localhost 11211
  set test 0 0 1
  0
  STORED
  ! 2本のプロセスを同時に実行する。
  % ./nocas-test.pl 10000 &
  % ./nocas-test.pl 10000 &
  % telnet localhost 11211
  get test
  VALUE test 0 5
  10218
  END

本来カウンタの値は20,000になるはずですが、更新が衝突し、正常にカウントされていないことがわかります。

CAS操作を用いる場合

• ソースコード
  

  #!/usr/bin/env perl
  use Cache::Memcached::Fast;
  $num = shift;
  $mem = Cache::Memcached::Fast->new({'servers' =>["127.0.0.1:11211"]});
  foreach (1 .. $num){
  $ret = $mem->gets('test');
  ($cas,$val) = @$ret;
  $val++;
  unless ($mem->cas('test',$cas,$val)){
  warn "$val update failed. retrying.\n";
  redo;
  }
  }

• 実行結果
  

  ! まず初期値としてtestに0をセットしておく。
  % telnet localhost 11211
  set test 0 0 1
  0
  STORED
  ! 2本のプロセスを同時に実行する。
  % ./cas-test.pl 10000 &
  % ./cas-test.pl 10000 &
  % telnet localhost 11211
  get test
  VALUE test 0 5
  20000
  END

カウンタの値は20,000になり、正常にカウントされていることがわかります。

まとめ

上記の通り、CAS操作は複数のクライアントからKVSにアクセスするような環境においてアトミックなデータ更新を行うために必須のメソッドとなります。本記事で例を挙げたように、CAS操作がサポートされていないKVS単体では、ホームページのカウンタすら実装できません。それゆえ、今回kumofsでCAS操作がサポートされたことは、kumofsの利用の幅を大きく広げるものであると思います。

CAS操作はシンプルですが様々な応用が考えられますので、今後応用例についても触れていきたいと思います。