インフラエンジニアのためのkumofs情報 順序配列

kumofsで順番を持った集合を作る方法として、前回はリストを紹介しましたが
キー値に規則を作ることで、もうすこし簡単に順番を持つ配列を作ることができます。
まず、CASを使ってカウンターを準備します。

mem.atomic_set('counter') {|val|
  val = val.to_i + 1
  caunter_val = val
}

カウンターには予め、値として0を入れておきます。
そして、集合の各要素であるvalueを保存する場合に、並べたい順番にカウンターから
値をひとつづつ受け取りキーを作成し、キーと要素のペアを作っていきます。
キーを作るときは、集合の識別のためのラベルを付けておくと良いでしょう。

mem.set('label' << caunter_val.to_s, value, 0, true)

例）
「キー値」「要素」
「label0」「value1」
「label1」「value2」
「label2」「value3」
：
「label,100」「value101」
ちょうど、キー値が配列の要素番号の指定にあたり、配列要素の数がカウンターの値に
なるイメージです。
要素を順番に読み出したいときには、ラベルに番号を付けていくだけで出来ます。

counter = mem.get('counter',true).to_i
for i in 0 .. counter do
  value[i] = mem.get('label' << i.to_s,true)
end

リストとは違い、ラベルさえ知っていれば集合中のどの要素にも１回のアクセスで値が
取得できます。
またkumofs本来のアクセス速度をそのまま生かした高速なアクセスが実現できます。

辞書検索のような特定のキー値でのアクセスを維持したまま順番を付けたい場合は
前回紹介したようなリスト形式、キー値にはこだわらず、順番を持った要素に高速に
アクセスしたい場合は順序配列形式というように使い分けをすると良いでしょう。

インフラエンジニアのためのkumofs情報 リスト構造

kumofsはキーバリューストアの中でも、機能よりもスピード重視なので、それ自体では
キーとバリューペアだけのシンプルな構造しか扱えず、検索やレンジスキャン、キー一覧
の取得などは行えません。
そこで、前回紹介したCAS操作を応用して、kumofsにリスト構造を作ってみます。
プログラマにお馴染みのリスト構造は、「値」と「次の要素を示すポインタ」を持ち
「次の要素」を順番に辿っていくことで、順番を持った値集合を作ることができます。
kumofsを使ってこれを実現するためには、バリュー値に「値、次のキー値」を持たせることで
実現できそうです。
一つのバリュー内に、値と（次の）キーを入れるためには、カンマ区切りにするなどしてデータ
を登録しておきます。
また、操作と構造を簡単にするために循環リストとします。
循環リストは、最後の要素の「次のキー値」が先頭要素の「キー値」になっていて、次の要素を
辿っていくと、先頭に戻ります。ちょうどリングのようなイメージです。

しかしこのままではkumofsで実装するには、面倒なことがおきます。リストに新しい要素を
追加しようとするとき、最後の要素のバリュー内の「次のキー値」を新しい要素のキー値に
置き換える必要があります。ところがkumofsのようなデータストアは複数プロセスから追加
更新が発生することが前提になるので、追加時に「最後の要素」がどこにあるのかを、プロセス
間で共有する仕組みが必要になってきます。

そこで、矢印を逆にしてみます。つまり、「値、前のキー値」をバリューに持たせます。

こうすると、要素の追加の時に更新しなければいけないのは、先頭キーのバリューになり、要素
が増えても先頭キーは固定されているので、各プロセスは先頭キーだけ知っていれば要素の
追加ができます。

要素追加時の操作は、新しい要素に「値、前のキー値(先頭のキー値のバリュー内にある）」を
登録し、最初のキー値のバリューを「値、新しい要素のキー」に更新します。
複数プロセスから要素の追加が発生する場合を考慮すると、先頭のキー値のバリューを更新する
にはCAS操作が必要になります。そうしないと、他のプロセスで先頭のバリュー値を上書きされて
追加した要素がリングから外れてしまいます。

では、実際に実装してみましょう。
その前に、前回紹介したrubyでのCAS操作を見やすくするため、メソッドを置き換えておきます。

require 'memcache'

class MemCache2 < MemCache

  def atomic_set(key)
    begin
      ret = self.cas(key,0,true){|value| yield(value) }
    end until ret == "STORED\r\n"
  end
end

CAS操作は次のようになります。

mem = MemCache2.new 'localhost:11211'
mem.atomic_set('key') {|value|
  valueに関する操作
}

本題のリスト操作に戻って、要素の追加は

mem.atomic_set('first_key') {|value|
    prev_key = value.split(",")[1]
    mem.set(new_key, new_value + ',' + prev_key, 0, true) 
    value = value.split(",")[0] + ',' + new_key
  }

各要素を順に拾っていくには、先頭キーから後ろ向きに辿っていきます。

current_key = 'first_key'
while 1
  current_value = mem.get(current_key, true)
  print "key=#{current_key}, value=#{current_value.split(",")[0]}\n"
  current_key = current_value.split(",")[1]
  if current_key == 'first_key' then break end
end

このようにリスト操作を実装しておけば、先頭要素のキーを知るだけで、集合の要素を
順番に取得することができ、キーや値の一覧も得ることができます。

インフラエンジニアのためのkumofs情報 CASを試す

kumofsはCAS(Compare-And-Swap)をサポートしています。これは、ある値を更新したい
場合に、他のプロセスが同時に更新しようとして競合が発生してしまうのを防ぐしくみ
です。具体的には、ひとつのプロセスが値を更新しようとしたとき、内部でその値に関連
付けられたバージョン番号を同時に取得して、書き込み時にバージョン番号を比較、同じ
であれば値を更新します。そしてバージョン番号も変わります。
バージョン番号が一致しなければ、他のプロセスが値を更新していることになるので、値の
取得からやり直します。
実際に試してみます。
まず、CASを使わないで２つのプロセスから同時に一つの値を更新してみます。
以下のようなrubyサンプルを作ります。
一つのvalueを、引数に与えた数だけひたすらカウントアップするカウンターです。

for i in 1..ARGV[0].to_i do
  value = mem.get('counter',true)
  value = value.to_i + 1
  mem.set('counter',value,0, true)
end

実行前に、キー「counter」にvalueとして「0」を入れておきます。

$ telnet localhost 11211
Trying 127.0.0.1...
Connected to localhost.localdomain (127.0.0.1).
Escape character is '^]'.
set counter 0 0 1
0
STORED

２つのプロセスとして起動して、同時にvalueを更新してみます。

$ ./counter.rb 10000 &
$ ./counter.rb 10000 &

結果を見てみると、

$ telnet localhost 11211
Trying 127.0.0.1...
Connected to localhost.localdomain (127.0.0.1).
Escape character is ']'.
get counter
VALUE counter 0 5
11184
END

となり、合計20000にはなっていません。
更新が競合し、ひとつのプロセスが更新した結果を、他のプロセスが読み直しをせずに
自分の値で上書きしてしまったため、値が小さくなってしまってます。
次にCASを使って更新してみます。

for i in 1..ARGV[0].to_i do
  begin ret = mem.cas('counter',0,true) do |value|
      value.to_i + 1
    end
  end until ret == "STORED\r\n"
end

mem.cas()は、do～endまでのブロックで定義された操作を、あらかじめ取得しておいた
バージョン番号と現在のそれと比較し、一致すれば値(ここではvalue)を書き込みます。
書込みが正常に行われると、「STORED」を返します。「STORED」以外の値が返ってくる
場合は、valueの取得とブロック内の処理をやり直して、再度バージョン番号の比較を
して書き込みを試します。
実行してみましょう。

$ ./cascounter.rb 10000 &
$ ./cascounter.rb 10000 &

結果は、

$ telnet localhost 11211
Trying 127.0.0.1...
Connected to localhost.localdomain (127.0.0.1).
Escape character is ']'.
get counter
VALUE counter 0 5
20000
END

無事、合計が20000になりました。
テストに使用した、サンプルスクリプトは以下を参照。
http://github.com/so-net-developer/kumofs/blob/master/counter.rb
http://github.com/so-net-developer/kumofs/blob/master/cascounter.rb
実行には、ruby用のmemcacheライブラリmemcache-client(1.8.5)が必要です。

$ sudo gem install memcache-client

インフラエンジニアのためのkumofs情報 バックアップ

kumofsはkumoctlコマンドでバックアップを行えますが、このコマンドを投げただけだと
各ノードにハッシュ担当分のデータがコピーされて置かれるだけです。これだとノードの
構成が同じ状態のときしか、リストアには使えません。どんな状態でもリストアできる
ようにするためには、各ノードに作られたバックアップデータを１箇所に集めて、一つの
ファイルにマージしておく必要があります。
ノードの数が多くなると、手作業で実施するのは面倒です。簡単なスクリプトを作っておく
と良いでしょう。
社内で作ってみたPerlスクリプトを紹介しておきますので、参考にしてください。

http://github.com/so-net-developer/kumofs/blob/master/kumo-backup.pl

スクリプトでやっていることは、順番に以下のようになります。
kumofsの正常稼動の確認。（faultノードがあればバックアップは中止）
ノードリストの取得。
バックアップコマンド投入。
各ノードからバックアップファイルをFTPで取得する。
取得した全てのバックアップファイルをマージする。

スクリプトの実行には、以下のモジュールが必要なので、CPAN等からあらかじめ入れて
おきます。
Net::FTP
Memcached::Fast
内部から、kumoctlコマンドを呼び出しています。
設定は、スクリプト中の変数定義を書き換えて行います。
FTPはscpに置き換えても良いでしょう。

インフラエンジニアのためのkumofs情報 CentOS4 へのインストール その２

次に、MessagePack for C++をconfigureしようとすると・・・

$ tar xzvf msgpack-0.4.3.tar.gz
$ cd msgpack-0.4.3
$ CC=gcc4 CXX=g++4 ./configure
 :
Note that gcc < 4.1 is not supported.

If you are using gcc >= 4.1 and the default target CPU architecture is "i386", try to
add CFLAGS="--march=i686" and CXXFLAGS="-march=i668" options to ./configure as follows:

  $ ./configure CFLAGS="-march=i686" CXXFLAGS="-march=i686"

と言って止まってしまう。gcc41は間違いなくインストール済みなので、CPUアーキテクチャの
判定をミスっているもよう。言われたとおりのオプションを指定してやり直し。

$ CC=gcc4 CXX=g++4 ./configure CFLAGS="-march=i686" CXXFLAGS="-march=i686"
$ make
$ sudo /usr/local/sbin/checkinstall --exclude=/selinux
...
$ sudo rpm -ivh /usr/src/redhat/RPMS/i386/msgpack-0.4.3-1.i386.rpm

MessagePack for Ruby

$ sudo gem install msgpack

そして、kumofsのビルドに入るはずなのですが、configureすると・・・
まず、MessagePackの時と同様、CFLAGS指定を要求してくる。追加指定して、make
しようとすると・・・
なにやらincludeファイルのNot Foundが山のように出てくる。
ファイル名を頼りに調べると、boost(C++ライブラリ)が無いようです。これはCentOSの
あるバージョン以降からは標準で入っているようなのですが、CentOS4.8ではデフォルト
どころか、yumでも入らない。
仕方がないので、ソースを拾ってきて、指定どおりビルド。いちおうrpm化しましたが
ビルドの時しか使わないでしょう。

$ tar xzvf boost_1_44_0.tar.gz
$ cd boost_1_44_0
$ ./bootstrap.sh --prefix=/usr
$ sudo /usr/local/sbin/checkinstall ./bjam install
$ sudo rpm -ivh /usr/src/redhat/RPMS/i386/boost_1_44_0-20100921-1.i386.rpm

このライブラリ、とても大きく、ビルドだけで１時間近くかかる。
気を取り直してconfigureし直すも、まだだめ。ファイルだけじゃなく、そもそも存在
しないディレクトリを参照してる。
そこで、エラーの内容と、CentOS5の/usr/include以下のディレクトリ構成を参考にして
シンボリックリンクを張ってみる。

$ cd /usr/include/c++
$ ls
3.4.3
$ g++4 -v
cc バージョン 4.1.2 20080704 (Red Hat 4.1.2-44)
$ sudo ln -s 3.4.3 4.1.2
$ ls -la
drwxr-xr-x   7 root root 4096 9月 21日 18:32 3.4.3
lrwxrwxrwx   1 root root    5 9月 21日 18:34 4.1.2 -> 3.4.3
$ cd 4.1.2
$ sudo ln -s /usr/include/boost/tr1/tr1 tr1

(g++4のバージョンに合わせて適宜読み替えてください）
これで無事kumofsのconfigureが通る。

$ cd kumofs-0.4.5
$ CC=gcc4 CXX=g++4 ./configure CFLAGS="-march=i686" CXXFLAGS="-march=i686"
$ make
$ sudo /usr/local/sbin/checkinstall --exclude=/selinux
...
$ sudo rpm -ivh /usr/src/redhat/RPMS/i386/kumofs-0.4.5-1.i386.rpm

ほかのマシンにもインストールする場合は、これまでに作ったrpmパッケージを順番に
インストールすればOKです。（bootsは要らない)

インフラエンジニアのためのkumofs情報 CentOS4 へのインストール その1

kumofsは日本で生まれただけあって日本語の情報も豊富で、インストールや設定で苦労
することも無いようです。ここでは、事情により古いCentOS4.8で動かしてみた結果を
記しておきます。
作者のサイトhttp://github.com/etolabo/kumofs/blob/master/doc/doc.ja.md
を見ると、動作要件として「linux >= 2.6.18」と記されています。その他ライブラリに
ついてはなんとかなるとして、CentOS4.8(2.6.9)で動くのかどうか・・・
結論から言うと、問題なく動いてます。ただし、kumofsのパッケージのビルド環境として
あるていど新しいLinux環境（コンパイラ、ライブラリ、その他の配置等）を前提にして
いるので、それなりに工夫（というよりごまかし）が必要でした。
作業の方針として、rpmパッケージ化してインストールします。ただでさえ面倒なビルド作業
を、kumofsを動かしたい全ノードで実施しなければいかない手間を省くためです。
yumでインストールするコンパイラ類はなるべく最新のものを取得したいので、
http://wiki.centos.org/AdditionalResources/Repositories/RPMForge
を参考にして、rpmforgeをインストールしておきます。
それから、rpm化にはcheckinstallを使うことにします。これも
http://www.asic-linux.com.mx/~izto/checkinstall/
から拾って、インストールしておきます。CentOS4.xでも普通にmake,make installでいけます。
後から入れるMessagePack for C++がgcc4.1以上を要求してくるので、これをインストール。
本来ならgcc44あたりを入れないと、kumofsのconfigureがうまく動かないのですが、CentOS4.xにはgcc41しか用意されていないようです。

$ sudo yum -y install gcc4 gcc4-c++

必要なライブラリ類をインストール。（ソース元は省略）
zlib-devel

$ sudo yum -y install zlib-devel

bzip2

$ tar xzvf bzip2-1.0.5.tar.gz
$ cd bzip2-1.0.5
$ make
$ sudo /usr/local/sbin/checkinstall
...
$ sudo rpm -ivh /usr/src/redhat/RPMS/i386/bzip2-1.0.5-1.i386.rpm

openssl-devel

$ sudo yum -y install openssl-devel

ruby1.8.7

$ tar xzvf ruby-1.8.7-p249.tar.gz
$ cd ruby-1.8.7-p249
$ ./configure
$ make
$ sudo /usr/local/sbin/checkinstall --fstrans=no
...
$ sudo rpm -ivh /usr/src/redhat/RPMS/i386/ruby-1.8.7-p249-1.i386.rpm

RubyGems

$ tar xzvf rubygems-1.3.6.tgz
$ cd rubygems-1.3.6
$ sudo /usr/local/sbin/checkinstall -R "/usr/local/bin/ruby setup.rb"
...
$ sudo rpm -ivh /usr/src/redhat/RPMS/i386/rubygems-1.3.6-1.i386.rpm

TokyoCabinet

$ tar xzvf tokyocabinet-1.4.43.tar.gz tar.gz
$ cd tokyocabinet-1.4.43
$ ./configue
$ make
$ sudo /usr/local/sbin/checkinstall
$ sudo rpm -ivh /usr/src/redhat/RPMS/i386/tokyocabinet-1.4.43-1.i386.rpm

ここまでは、CentOS4.8であることは特に意識することなく定石どおり。