Karesansuiを試す

この記事はカーネルVM Advent Calendarの12/21日分の記事です。前日分はid:rti7743さんのなのは完売 とある関数の電脳戦 (じょうほうせん とある関数のバトルプログラム) - お前の血は何色だ!! 4です。

Karesansuiって?

ものすごく大雑把に言うとEC2のオープンソース実装です。

遊ぶ環境を作るのにAmazon EC2は便利ですけれど、自分の手元にもああやって気楽にVMをポンポン立てれる環境が欲しいですよね。
同様の目的の為にOpenStackとかEucalyptusもあるようですけれど、アイコンの好みからKaresansuiを試してみる事にします。
Dear users of Karesansui | Karesansui Project
具体的な特徴としては

  • WebUI
  • Pythonで動いてる
  • RHEL系のLinuxで走る(というかDebian系でインストール成功してる人見たこと無い
  • Xen/KVMを利用できる
  • アイコンが可愛い

などが挙げられると思います*1

インストールする

まず環境は

OS CentOS5.7 2.6.18-274.12.1.el5xen
CPU Core i5 660
Memory 8GB
仮想化 Xen

参考にしたページ http://netmark.jp/2009/07/centos53karesansui.html

前もって必要な設定

まずXenが動く環境にしないといけないです。

# yum groupinstall Virtualization yum install iscsi-initiator-utils cyrus-sasl-md5 qemu gnutls-utils PyXML mysql-server MySQL-python perl-HTML-Parser perl-URI
# echo "alias scsi_hostadapter xenblk" >>/etc/modprobe.conf
# grep -lr "DEFAULTKERNEL=kernel" /etc/sysconfig/kernel | xargs sed -i 's/DEFAULTKERNEL=kernel/DEFAULTKERNEL=kernel-xen/g'
# grep -lr "default=." /boot/grub/menu.lst | xargs sed -i 's/default=./default=0/g'
# reboot

ここまで打って

# uname -r
2.6.18-274.12.1.el5xen

的な感じになれば大丈夫です。xenですね。

Karesansuiのインストール

公式サイトから落としてきたtar.gzファイルを展開して./

# tar xvf karesansui-2.0.1-install-pack.tar.gz
# Karesansui/karesansui-install

と打つだけです。簡単ですね。と思いきや問題にブチ当たります。

エラー: このディストリビューションはサポートしていません。

CentOSに対応してるって言ってたじゃないかバーニィと言いたくなるのをぐっと堪えてインストーラを騙します。

$ emacs Karesansui/installer/const.py
SUPPORTED_DISTROS = [
("centos", "^5-[12345].*$"),
("redhat", "^5Server-5.[12345].*$"),
#("redhat", "^(5Server-5.[12345]|6-6\.).*$"),
]
↑のを↓のように書き換える
SUPPORTED_DISTROS = [
("centos", "^5-[1234567].*$"),
("redhat", "^5Server-5.[12345].*$"),
#("redhat", "^(5Server-5.[12345]|6-6\.).*$"),
]

手元のCentOSは5.7だったので対応外と怒られたんですね。
CentOS5.5で動いた物がわざわざ動かなくなることも無いだろうとそのまま書き変えました。
気をとりなおしてインストール再開します。

# Karesansui/karesansui-install

対話的インストールな感じで必要なフォームを埋めればすいすい進みます。
具体的にはhttp://karesansui-project.info/wiki/karesansui/Ja_tutorialに書いてある物とほとんど一緒です。

使ってみる

インストールが完了したら

# ./karesansui-checkenv

を打つ事で環境が正しく動いてるか確認できます。正しく動いていればその一番下で
http://(サーバ名)/karesansui/v2/
にアクセスしろと言われます。
アクセスすると認証ダイアログが出ます。

ユーザ名の欄にはインストール時に入力したメールアドレス、パスワードもインストール時に入力したものを入れれば入れます。

無事入れました。jQueryなどを駆使した近代的なインタフェースです。
ここに表示されているカエルアイコンはこのKaresansuiのインストールされた物理マシン(ホスト)を表しています。

ホストの追加もホスト名とユニークキーを教えてやることで簡単にできるようですが自由に使えるマシンが複数あるわけではないので今回は一台のみです。
EC2には(多分)無い特徴として、アイコンを自由に変えられます。

夢が広がりますね。、
ホストマシンのアイコンを2度クリックするとゲストOSの管理画面に入ります。

可愛いアイコンが見えなくなってちょっと残念ですね。
【+作成】ボタンからゲストOSをインストールできるようです。早速試してみましょう。

モーダルなダイアログが出てきました。リッチなUIです。

ブートイメージというのを指定する所に来てふと手が止まりました。
どうやらisoファイルを適当に指定して…というわけには行かないようです。

調べたところ、この2つはvmlinuzファイルとのinitrdファイルのフルパスかftpURIかで指定できるようです。
サーバ内部の物のフルパスを指定するのって何だか気持ち悪いのでftpでやります。で、手頃なftpサーバに出来るのがそのマシンそのものなのでそこをホストにします。

# yum install vsftpd
# /etc/init.d/vsftpd start

anonymous FTPで接続できる必要があるっぽいので適当に設定して接続します。

# ftp localhost
Connected to localhost.localdomain.
220 Welcome.
530 Please login with USER and PASS.
530 Please login with USER and PASS.
KERBEROS_V4 rejected as an authentication type
Name (localhost:hogehoge): ftp
331 Please specify the password.
Password:
230 Login successful.
Remote system type is UNIX.
Using binary mode to transfer files.
ftp>

こんな感じに動けば大丈夫そうです。
で、ゲストOSとしてgentooに挑戦しようとしたのですが、vmlinuzとinitrdがどこにあるか分からなかったのでCentOSを入れてみます。
isoファイルをftpで見えるところにマウントしてやるだけですね。

# cd /var/ftp/
# wget http://ftp.jaist.ac.jp/pub/Linux/CentOS/6.2/isos/i386/CentOS-6.2-i386-LiveCD.iso
# mount -t iso9660 CentOS-6.2-i386-LiveCD.iso -o loop pub

こんな感じで ftp://(サーバ名)/pub/isolinux/vmlinuz0 と ftp://(サーバ名)/pub/isolinux/initrd0.img がそれぞれアクセスできるようになります。
ブラウザに直接そのURLつっこめば導通チェックできます。
するとしばらくしてゲストOSが立ち上がってきます。

アイコン可愛いですね。これはKaresansui組み込みのアイコンの一部ですが、Twitterアイコンと組み合わせたりするサービスが現れないかなーとか夢が広がります。

立ち上げに失敗した場合は[ジョブ]タブの中でエラーの詳細を見ることができます。楽ですね。

これはFTPのURLを打ち損じてコケてる画面です。生のコマンドが表示されるので、何かでコケたらターミナル開いたりして再現できますね。

さて、無事にゲストOSの作成に成功したらこんな感じになるはずです。

立ち上げるにはアイコンを2度クリックして開始ボタンを押せば良いです。

と思ったら立ち上げに失敗したようです。

どうやらXenまわりのエラーのようですね…

/opt/hde/lib/python/sqlalchemy/orm/scoping.py:127: SADeprecationWarning: Use session.add()
return getattr(self.registry(), name)(*args, **kwargs)
libvir: error : Unknown failure
libvir: Xen Daemon error : POST operation failed: xend_post: error from xen daemon: (xend.err "Error creating domain: Boot loader didn't return any data!")
Failed to start guest. - dom=cen
POST operation failed: xend_post: error from xen daemon: (xend.err "Error creating domain: Boot loader didn't return any data!")

軽くググったところ、設定を間違ったようなのですがここでうっかりスナップショットのタブを押したらKaresansuiさんが機嫌を損ねたようで謎のエラーがポップアップされるようになってホストOSが表示できなくなりました…。

まだ僕には早すぎたのかも知れません。

表示できないホストマシンアイコンの図。

もう少し追跡したいのですが終電の時間が迫っているので今日はここまでで勘弁してください。

カーネルVM Advent Calendar明日は @cosmo__ さんです。

*1:詳しいこと知らないだけだろとも言う

DSIRNLP勉強会で発表しました

@overlastさんのお誘いにより招待講演という形でDSIRNLP勉強会で発表をしました。

IRともNLPとも関係のない話ですが、冬のLock-free祭りという題目でお腹いっぱい話せました。
発表資料はこちら

↑だとアニメーションが死んでてイミフになってるので↓がおすすめです。一番良いのはPowerPoint2007以降で再生することですが。
http://www.slideboom.com/presentations/460931/%E5%86%AC%E3%81%AELock-Free%E7%A5%AD%E3%82%8A_safe
アニメーション有りなら深く考えずめくっていくだけでおおよその雰囲気は掴めるんじゃないかと思います。
総ページ数190枚の大作です。

いろんな人にlock-freeなデータ構造の面白さを理解して頂けたようで大変満足です。
また、@hitoshi_niさんから「発表から情熱が伝わって来た」と好評をいただき、本を頂けました。

どちらも買おうか悩みつつ財布の都合で踏みとどまっていた本なので、超えてはいけない線を超えてしまいそうです。
ありがとうございます!

時間や自分の理解度の都合で話しそびれたこと

・Lock-free double ended queue
・Lock-free malloc
・Lock-free snapshot
・Lock-free STM
・OSTM, RSTM, NZTMという進化の系譜
・そもそもLock-freeとObstruction-freeの違い
・TransactionalLocking2
・STMのOpacity
まだ話せそうで話してない事が結構あるので次回は夏頃になるかと思いますが気長にお待ちください。

面白かった話

数学は得意でなく、機械学習も出てくる記号の意味からして理解できていないのですが簡潔ビットベクトルは僕の頭でも理解できるほど噛み砕いて頂き大変興味深かったです。
あとGraphDBとかSuffixArrayとか興味が尽きないです。

ノンブロッキングでマルチリーダーでserializableなSTM戦略

前回ノンブロッキングなSTMに付いて説明したのですが、トランザクション中での読み出しに関してはあまりに適当な説明しかしていなかったです。
そこをもう少しまともに説明しようと思います。

読み出しトランザクション?

複数の箇所の読み出しをatomicに行う必要があります。
一番簡単な方法は「その値そのもので上書きしてやる」事で値を変えずに所有権を自分に移す事です。

  transactional_object<int> *a,*b;
  const int *commited_a, *commited_b;
  status_t my_status = new status_t(ACTIVE);
retry:
  transactional_object<int> *old_a = a, *old_b = b;
  // aを読む
  if(*(old_a->owner_) == COMMITTED){
     commited_a = old_a->new_;
  } else if(*old_a->owner_) == ABORT){
     commited_a = old_a->old_;
  } else {
     assert(*(old_a->owner_) == ACTIVE);
     cas(&old_a->owner_, ACTIVE, ABORT); // 先行してるトランザクションを殺す
     goto retry; // 殺すのに成功しても失敗しても非ACTIVEだと思われるので初めから
  }
  // 同様にbを読む
  if(*(old_b->owner_) == COMMITTED){
     commited_b = old_b->new_;
  } else if(*old_b->owner_) == ABORT){
     commited_b = old_b->old_;
  } else {
     assert(*old_b->owner_) == ACTIVE);
     cas(&old_b->owner_, ACTIVE, ABORT);  // 先行してるトランザクションを殺す
     goto retry;
  }

 
  { // aにcommited_aを上書き(丸ごとCASして差し替えてるけど)
    bool result = cas(&a, old_a, new transactional_object<int>(commited_a, new int(*commited_a), my_status);
    if(result == false) { goto retry; }
  }
  { // 同様にbも上書き
    bool result = cas(&b, old_b, new transactional_object<int>(commited_b, new int(*commited_b), my_status);
    if(result == false) { goto retry; }
  }
  { // commit
    bool result = cas(my_status, ACTIVE, COMMITTED);
    if(result == true){
       // この瞬間、aとbを自分が所有しているのでcommited_aとcommited_bの値が一貫していると思って良い
       // 何故なら他のスレッドがaかbを割り込んで書き換えたのならその前に自分がABORTさせられここに至れないはずだから
    }else{
       // 他のスレッドにSATSUGAIされた
       my_status = new status_t(ACTIVE);
       goto retry;
    }
  }

正直超効率悪いです。
何より酷いのが、これだと複数のスレッドが同時に読み出しに来れないんです。
なぜかというと書き込みの時と同じ作法で所有権をぶん取っちゃってるからですね。

ナイーブな解決策としてもうひとつ挙がるのが「read committedな分離レベルでいいじゃないか」という諦めです。
スレッドがACTIVEな時はoldがcommitedな最新の値なのでそっちを読めばいいので大変楽です。
しかし一貫性については妥協しています

int commited_a = *(a->owner_) == COMMITTED ? *(a->new_) : *(a->old_);
int commited_b = *(b->owner_) == COMMITTED ? *(b->new_) : *(b->old_); // この瞬間既にaは別の値になってるかも知れない
commited_a; commited_b; // ←これら2つの値が一貫した値である保証はない

読みだした時に別の値になってるというのは悲しい話です。

Lock-basedなSTMなら書き込む対象しかlockせず読み出しはwait-freeなvalidation作業だけで一貫性を保証できるのでマルチリーダーは気楽なのですが*1Non-blockingなSTMで同様の事を成し遂げるのは簡単ではないです。

トランザクションとは何だったのか

ACIDを満たす操作を一瞬で行なったように見せかけるのがトランザクションだというのは学校で習うのですが、それが実際に意味するところを理解してる人はあんまり居ないんじゃないかと思います。トランザクションとは何なのか。

物理的に本当に一瞬で行う事が不可能な事は言うまでもありません。
ロックを取る事で外からみて一瞬で終わったように見せかけている?70点。
一瞬で終わったように見せかけれそうにないならやり直している?75点。

トランザクションのACIDのConsistencyが意味するところ、それはトランザクションの開始と終了までの間で「一瞬でもコミット完了時の瞬間のデータの状態が存在したことを約束する」事なのです。

なのでこのようにスナップショットを取ることが可能です。

a,b,cの値を2回読んで居ますが、ここで2回読み出す値が一致していれば少なくとも黄色い縦線のその一瞬だけは、a,b,cの値が同時に読みだした通りの値であったことを保証できます*2。ロックを取らずとも、値の一致だけでスナップショットを取得できるのです。これも立派な読み出しトランザクション!Kakkoii!!一致しなかったらもう一回やり直せばいいだけです、一致しなかったということは他の誰かが何か変更を加えたという事なので全体としてどこかで進行が起こっているはずです、つまり進行保証があるのでつまりlock-freeです。*3

それをノンブロッキングなSTM中でどう使うかというと、読みだした値全てをread-setとして保管しておき、コミット直前にもう一回read-setが一致している事を確認するだけです。拍子抜けするほど簡単ですね。

緑色がトランザクション中で読んだ値、赤線がトランザクション中で読み書きした値です。
緑色い線は前述の方法でlock-freeなスナップショットを取り、赤線は前回の日記Non-blocking STMについて頑張って説明してみる - くまメモトランザクションコミットの方法で、ステータスをCASすることで複数のオブジェクトの論理的な最新状態を書き換えています。万一どちらかが失敗した場合はトランザクションを初めからやり直すので、今回は成功する場合だけを考えましょう。

さて問題そうに見えるのが、黄色い縦線(読み出した物のスナップショット)と、オレンジ色い縦線(書き込んだ物のスナップショット)の間にタイムラグが有ることです。このタイムラグがセーフなのか?というのが本日の話題です。

結論から言うと、セーフです。先ほど話したように「一瞬でもコミット完了時の瞬間のデータの状態が存在したことを約束する」事ができれば良いのです。必ずしも物理的にその条件を満たしているべきとは誰も言っていません。黄色い横線の間、自分がabortされない限りは書き込み途中の値は他者から読まれなくて、どの瞬間でどこに何が書かれていても一緒なので、早い話がオレンジ色い縦線は自由に左方向にずらして良いのです。論理的に同じなのです。*4

この図中のオレンジの縦線は、外に対して言い訳する分にはどこにあったことにしてもいいのです。なので論理的に再読み出しによる確認と書き込みのコミットは全く同じ瞬間に行われたということにして外部に対して保証して良いのです。これによって晴れてロックせずに一貫性も一切妥協せず複数スレッドからの読み出しが同時に行なえる事になりました。*5
本当にトランザクションは最高だぜ*6

*1:たとえばTL2とか

*2:ABA問題についてはせせこましいので許してください。ここは適当な論理時計でも付いてると見做してください

*3:進行してないくせに値を書き換えてる場合はObstruction-freeに格下げですがね!

*4:もちろん黄色い線もずらして良いです

*5:そういえばinvisible readerの話しかしてなかったので別の実装も機会があったら話したいですね

*6:酔ってます

LevelDB雑感

LevelDBが公開されて少し経ちました。
全体ではLog Structured Merge Treeという物を実装しているようですが詳しいところは知りません。

実装を少し読んだのですが内部で使われているSkipListにいくつも思い切った設計がありました。

(参考)togetter「LevelDBを読む人たち」
http://togetter.com/li/136983

SkipListそのものはMulti Reader / Single Writerな実装なのですが
おもしろい事にReaderとWriterが同時に走っても大丈夫なように作られています。

Reader-Reader : 共存可能
Reader-Writer : 共存可能
Writer-Writer : 共存不可

Readerが常に走り続けている状況を想定した上で、Writerの足を止めたくないんでしょうね。
為される事の論理的構造が決まっているからこそ、書き込み途中のデータを読み出せる仕組みにしたんだと思います。

また、削除が行えない仕組みになっていました。SkipListクラスのデストラクタでまとめてメモリ開放を行えますがそれまでの間はメモリ領域も含めてSkipListからは一切開放できないように機能を限定することで、並行データ構造を設計する上で鬼門となる削除周りの複雑さを一気にスキップした感じです。

いくつか不可解な点もあります。
C++0xなのにstd::mt19937ではなく、簡易乱数生成器を自作している。速度のためだとしてもここをチューニングしても意味なさそう。
・「現時点での最大レベル」を保持する変数への保護がmemory_order_relaxedだけ。atomicにする意義がよく分からない
・「現時点での最大レベル」は実際のところわざわざ保持しなくても常に最大レベルから読み始めても速度落ちなさそう。というかそこのメモリを取り合うコストのほうが高そう
・insert処理がシングルスレッドでしか走らないことを利用してアリーナ型のアロケータを自作している。切り分ける個別のアドレスに削除用領域を残さない分メモリ効率は高そうだけれどこのアロケータ単体で速度を測ったらUbuntu標準のmallocより遅かった…
・アロケータの実装を見るに、freeの分のメモリを節約した事にはなっているが、切り詰めるなら残りサイズでstd::multisetを作って最後までページをしゃぶり尽くす実装などもあり得たがこの実装の判断はどこから?
僕の勘違いもあるとは思いますが、興味深いソースコードです。全体として品質が高く、googleの技術力を感じさせます。

SkipList

SkipListそのものは順序関係のあるデータを検索・挿入・削除がO(log n)となるデータ構造ですが
std::mapなどで実装されている平衡木と比べて

△利点
・乱数により常に負荷分散を行うので、入力データによる偏りを気にしなくて良い
・不変条件を満たす事が比較的容易
▼欠点
・挿入されるアイテム数のlog n程度の最大レベルになるよう調整する必要がある
・アイテム1つ毎に必要になるポインタの個数が最大レベル数に比例して大きくなり二分木より大きくなりがち

といった違いがあります。

木は平衡化のために回転が必須ですが、回転するとどうしても検索途中のスレッドの探索範囲を知らずに変えてしまいます。
SkipListの場合は平衡化の必要がないところがポイントですね。

何故これをLSM-Treeで使おうと思ったかが未だちょっと理解できていないのですが、どこかに解説はないでしょうか。

Non-blocking STMについて頑張って説明してみる

STMはソフトウェアトランザクショナルメモリの略です。
↓とりあえずwikipedia
http://ja.wikipedia.org/wiki/%E3%82%BD%E3%83%95%E3%83%88%E3%82%A6%E3%82%A7%E3%82%A2%E3%83%88%E3%83%A9%E3%83%B3%E3%82%B6%E3%82%AF%E3%82%B7%E3%83%A7%E3%83%8A%E3%83%AB%E3%83%A1%E3%83%A2%E3%83%AA

日本でSTMの話題を検索すると「楽観的ロックでしょ?」といった発言を見かける事が多く、確かに実用的な手法の多くはロックベースだったりしていますが、正直なところロックベースな手法のSTMはデータベースでのトランザクションと似ているフシがあったりしてデータベースに詳しい人からするとそれほど驚くような手法ではない事が多いのです。その一方でノンブロッキング(=非ロックベース)な物は工夫がいくつも凝らしてあり、眺めて良し愛でて良しの大変エキサイティングな物になっています(パフォーマンス以外)そのあたりを少し書きたいなと思います。

STMって何?

データベースの界隈で使われる「トランザクション」をメモリに適用して並行プログラムを書きやすくしようという研究です。
初めはMaurice Herlihy先生の1993年の論文のハードウェアトランザクショナルメモリ(HTM*1 )が元だったのですが、Nir Shavit先生がそれと同様のセマンティクスをソフトウェアレベルで可能であることを示してから一気に研究が加速しました。lock-freeな論文を出していた方々の最近の研究がソフトウェアトランザクショナルメモリに染まっていて、それほどまでに魅力的なのだなというのが伝わってくると思います。*2
HTMに比べてSTMはハードウェアを取り換えずとも環境に合わせた複数の実装を試すことができ、インタフェース仕様さえ共通なら同一のトランザクションを別のトランザクショナルメモリ実装で走らせることも可能です。またハードウェアに縛られない実装が可能なのでHTMと比べて大きなトランザクションにも向いています。*3
一般にデータベースでのトランザクションはACIDと呼ばれる特性を満たしている必要がありましたが、STMのトランザクションはACIしか満たさない事が普通です。これはD(Durability=永続性)は「いつ電源が落ちても復旧可能」という意味で、そもそも揮発性メモリしか相手にしていないSTMからすると永続化は蚊帳の外の問題だからです。

住み分けはあるの?

STMを分類するなら「ノンブロッキングか否か」「オブジェクトベースかワードベースか」が挙げられると思います。*4

ノンブロッキング

ロックを使うか否かは大事な問題です。ロックを抱えたスレッドがPageFaultなどして数万クロック返ってこないという事態になった際にも全体が停止せずに済みます。端的に言うなら外乱に強くなります。またロックをしない事で優先順位の逆転が起きないのです。火星探査機を実装している方必見ですね。
しかし何でもノンブロッキングにすれば良いかと言うと今度は間接化やメモリ動的確保のオーバーヘッドが大きく性能が出ないのでそこもまた面白い所です。

オブジェクトベースorワードベース

どんな単位でメモリを保護するかというのも重要な問題です。オブジェクトベースなSTMではオブジェクト(というデータの塊)にトランザクション用のメタデータを付加して管理する場合が多いです。C以外の近代のプログラム言語ではオブジェクトに暗黙のメタデータを取り付ける事は一般化しているため、設計側に大きな変更をしなくても実装に追加するだけで自然に対応できる事が見込まれています。またデータに触れる際に一緒にメタデータもキャッシュラインに載る可能性が高いため筋が良さそうに見えます。しかし大きなオブジェクトを一つのトランザクション単位にしてしまうと「オブジェクトの別の場所に触れているので実際に衝突していなかったのに衝突扱いにされた」などという事態に陥りパフォーマンスに無駄が出る場面もあります。またオブジェクトの生存管理もトランザクショナルメモリ側で行う事になるため実装が大きくなりやすいとか。代表例としてはDynamicSTM,OSTM,RSTM,NZTMなどが挙げられます。
ワードベースなトランザクションでは、メモリは普通のメモリとして管理しつつ、そのメモリとは別にメモリのワードごとのメタデータをハッシュテーブルなどに置いて管理します。この方法なら大きなオブジェクトや長い配列の一部に対するアクセスであっても適切に衝突を検知できます。しかしメモリアクセスのたびにハッシュテーブルから引くことになるためパフォーマンスは難しいですし、キャッシュミスも頻発します。WSTMなどがありますが、具体的にはまだ追ってないです…。
どちらを選ぶにも一長一短なので、オブジェクトによってその2種類を使い分けるハイブリッド型のトランザクショナルメモリも有るのですが詳しくは知らないです。これ*5とかこれ*6とか。

どんな所で使われてるの?

既にHaskellScalaClojureでは実用的なライブラリが出ているようです。その多くはロックベースな物で、ノンブロッキングな物はあまり第一線では見かけません。前述の通りノンブロッキング化のオーバーヘッドに起因するパフォーマンス低下のせいじゃないかと思います。

ノンブロッキングソフトウェアトランザクショナルメモリ

中でも僕の好きなノンブロッキングなSTMに付いての話をしようと思います。具体的には論文Nonblocking memory management support for dynamic-sized data structuresを。
「ノンブロッキング」が何を意味しているのかの詳細は僕の過去の日記non-blockingの意味するところ - くまメモを見てもらうとして、一言で言うと「obstruction-freeかlock-freeかwait-freeのどれか」という事です。これまでずっとlock-free以上の特性を持ったSTMは無いんじゃないかと思ってたのですがもっと探してみるとwait-freeもどうやら可能そうという事が分かりました。*7

大雑把に言って何を使って何を行うの?

コンピュータの世界の名言に「全ての問題は間接化によって解決する」という物が有ります。ノンブロッキングSTMもその一種でまさに間接参照を用いてブレイクスルーを果たしました。
1ワード幅のCAS命令(LL/SC命令でも可)さえ有ればそれ以上強力な同期命令を必要としないので、早い話が今あなたが使っているCPUで動きます。
それによってどんなプログラムが書けるようになるかというと

atomic {
  if(x == 0){
    y += 1; // この瞬間も x==0であることが保証される
  }
}

のような雰囲気で書けます。複数ヶ所の一括更新が上限なくデッドロックの心配もなく行えます。*8

composable

何よりすごいのはcomposable(組み立て可能)であるという事です。
ちょっとググった所このcomposableについて誤解しているケースもあるので説明します。

ソフトウェアの教科書を読んだことがあれば、LRUキャッシュは双方向リストとハッシュマップを用いて実装できる事は知っていると思います。
ここで、複数のスレッドから並行にアクセス出来るLRUキャッシュを実装する場合を考えましょう。

すぐに思いつくのは普通の教科書的なLRUキャッシュを実装して単一のロックで排他する事です。これでパフォーマンスが要求を満たすならそれで充分です。
しかしパフォーマンスを高めるためにメニーコアのプロセッサの性能を使い切ろうと思った際、細粒度並行LRUキャッシュをフルスクラッチ実装するのはかなりの力量が要求され、デバッグのコストまで考えると挑戦すべきではありません。*9
双方向リストやハッシュマップの細粒度ロックやLock-freeの信頼できる実装が既に有る場合、そちらを流用して実装する事で達成しようとするのはエンジニアとして自然な考えです。

しかし、できません。

シングルスレッドな物で良いなら例えばC++ならstd::listとboost::unordered_mapの組み合わせでLRUキャッシュの実装は可能です。

しかしマルチスレッドになったとたんにそれは不可能になります。並行双方向リストの操作と並行ハッシュマップの操作を同時に行えない以上、2つのデータ構造に対する操作の間にタイムラグが発生するからです。ハッシュマップ側でlistのノードを見つけ、リストにアクセスしようとした途端に他のスレッドによってそのノードがdeleteされるかも知れません。*10
それを回避するために外から2つの操作を別のロックで括ってしまうとそもそも単一のロックで行なう程度の並列性しか得られません。*11

一般に、並行データ構造は組み合わせて使う事ができないのです。これがcomposabilityの欠如と呼ばれる物です。ついでにいうとLock-freeでもできません。これは完璧にソフトウェア工学の敗北です。
しかしSTM実装のハッシュマップと双方向リストならば操作全体をアトミックブロックで囲ってやる事で簡単に組み合わせられます。部品を使いまわしてコードを書ける上にマルチコアの恩恵に与れるのですから革新的ですね。

いいから早く実装を教えてよ

まずソフトウェアトランザクショナルメモリで保護する対象を示します。ただのポインタです。

これを保護するとしてこのような構造を作ります。

C++で書くとこんな感じです。

typedef int status_t;
template<typename T>
struct transactional_object{
  const T* const old_;
  const T* const new_;
  status_t* const owner_;
  transactional_object(const T* o, const T* n, status_t* s)
    :old_(o),new_(n),owner_(s){}
};
transactional_object* obj;

全てconstでガッチガチに固めているところがポイントです。一度作ったらstatusの実体値以外どこも書き換えません。並行処理のコードでよくあるimmutableパターンという奴ですね。volatileにすべきか迷いましたが、簡潔さのため省きます。
このオブジェクトからどう読むかというと、status_tの状態によって切り分けます。オブジェクトとステータスを別に保管するというのはノンブロッキングなトランザクショナルメモリでの頻出パターンです。これからもよく出てきます。
status_tはcommitted, abort, activeの三つのうちどれかの状態を取るので、それぞれの場合をifで切り分ければ良いです。

赤く塗られてるのが最新のコミットされた値です。C++で書くならこんな感じ

static const int COMMITTED=0;
static const int ABORT=1;
static const int  ACTIVE=2;
const T* read_value(const transactional_object* const obj){
  const status owners_status = *(obj->owner);
  if(owners_status == COMMITTED){
    return obj->new_; // COMMITTEDならnew
  }else if(owners_status == ABORT){
    return obj->old_; // ABORTならold
  }else{
    assert(owners_status == ACTIVE);
    /* 戦略によって変わるのでとりあえず割愛 */
  }
}

ここに書き込む際にはtransactional_objectごと新しく作ってCAS*12ですげ替えます。

void write_value(const transactional_object** const target, const T* const old_value, const T* const new_value, status_t owner){
  while(1){
    const transactional_object* old_target = *target;
    const transactional_object* new_object = new transactional_object(old_value, new_value, owner);
    const int result = CAS(target, old_target , new_object);
    if(result){ break; } else { delete new_object; }
  }
}

丸ごと差し替えるわけなので、図に描くとこんな感じです。

古い最新の値をoldに残して最新の値を書き込んでいる所がポイントです。
ここまででルール説明は完了です。後はCASを用いて適切に処理をするだけです。

動き方

ここからこれらのルールを生かしてどのようにトランザクションを実現するのかを説明します。

トランザクションの例として以下のような事例を考えます。典型的な銀行口座の残高移しの例です。

口座AからBに10000移す。残高がマイナスになりそうだったら取引は行わない。

C++でナイーブな物を実装するとして、トランザクション本体はこんな手順で操作を行います。

std::vector<transactional_object<int>*> accouts; // あらかじめ配列の形で保存されているとする
/* 口座A→Bに10000円移す */
const int* const A_account = read_value(accounts[A]);
const int* const B_account = read_value(accounts[B]);

// 自身のステータスを作成
const status_t* my_status = new status_t(ACTIVE);

// Aの口座から10000円引く
const int* const old_A = read_value(old_A_account);
if(old_A < 10000){
  throw AccountException("残高がマイナスです");
}
write_value(&accounts[A], old_A, new int(*old_A - 10000);

// Bの口座に10000円足す
const int* const old_B = read_value(old_B_account);
write_value(&accounts[B], old_B, new int(*old_b + 10000));

// コミットする
const bool result = CAS(my_status, ACTIVE, COMMITTED);

簡単ですね。図に書くならこんな感じです。

実は簡潔に説明しようとして一部エンバグしてますが大筋で大丈夫です。*13
大事なのは、write_valueする際にownerの項が同一のmy_statusを指すように書き換えてやる事です。
これによってmy_statusの1byteの状態の変化によって、同時に何万箇所でも一斉に論理的に書き換わるのです。

my_statusがCommittedになるだけで

逆に、Abortになるだけで

と、遷移します。変えているのはmy_statusの1つだけなのに、赤く塗っている箇所が複数同時に移動しているのです。これがキモです。

もしステータスがActiveだった場合にどうするかというと、一番簡単な解決方法はCASでActiveAbortに持ち込んでやって、その後で作業することです。
これにより多分このアルゴリズムを見た人の9割ぐらいが思う「書き換えた値をコミットするまでの間で誰かに上書きされたりしたらどうするの?」という疑問が解決します。答えは「上書きしにくる誰かは、必ずこっちをAbortさせてから上書きするので自分のコミットが失敗するだけ」となるわけです。

で、多分これをC++で書こうと思うと、read_valueの代わりにoperator*とかoperator Tとか使いたいですし、書き込みの代わりにoperator=とかとかしたいですし、オペレータで実現するとなると引数としてステータス渡せないしスレッドローカルストレージにポインタを置くことになるのかなーとかとか考えているわけです。

発展話題

読み出し問題

読み出ししか行わないトランザクションの場合、読んでるそばから書き変わっていってしまうとトランザクションの意味が無いのでリードロックしたいのですが、ナイーブにやるなら「その値を複製してwrite_value()を呼ぶ」事で可能です。
そんな読み出し如きで所有権を移す真似をするとマルチリーダーできないのですが、実はちょっと工夫すると一貫性を妥協せずに実現可能です。要望が有ったら書きます。

ゾンビトランザクション問題

実は読みだすうちに他のトランザクションによってコミットされた値を時間差で読んでしまう問題があります。矛盾した値を読んだトランザクションは最後のcommit挑戦時にabortするので一貫性の問題は無いのですが、トランザクション最中にそれを検知する努力をしないと無限ループや除算を書かれた場合に思いもよらない事態を引き起こします*14。Dynamic STMの論文ではIncremental Validationが提案されていた気がします。1個新しく読み出すたびに、これまでに読み出した物全てが前回読んだ値と一致する事を確かめる物です。n個読みだすなら内部的にO(n^2)回の読み出し操作を行う事になり大変です。*15

高速化

ちょっと読みたいだけなのに3回(transactional_object, owner_, old_/new_)もポインタを辿らなきゃいけないの馬鹿らしいなというのはみんな考える事のようで場合によってそれが1回になるよう工夫したOSTMや、大体の場合で2回になるよう工夫したRSTMや、競合してない限り1回で行けるNZTMなどなどが出ています。こちらも要望があったら書きます。*16

言語機能

この例示した記法が現実で使い物になるはずもなく、実際にはもっとスマートな見た目になるよう様々な工夫が凝らされます。composabilityを実現するための入れ子トランザクションの実装策はいくつもあり、あまり言語機能に興味のなかった僕はあまり追ってないのですが、一番簡単なのはトランザクション内部でのトランザクションは全て外側のトランザクションの操作として片付けてしまう事です。それを言語機能に手を加えず実現するには僕のC++力ではどうやったらいいか想像付かないので誰かCoolな策を考えてください。*17

応用

僕の修士の研究はこの方法をキーバリューストア上で行うという大変シンプルな物です。シンプル過ぎて類似研究にgkbrする日々ですけれど最近はnewSQLのほうが凄すぎてあまり喜ばれない感ございます。*18

12/2/ 12:49 PG_kuraさんに指摘いただいたところを修正(x==1 → x==0)

*1:Transactional Memory: Architectural Support for Lock-Free Data Structures

*2:僕は若干寂しかったですけれど

*3:HTMのほうはキャッシュラインの反映をどうするかという細かいトランザクションの世界を相手にしています

*4:他にも有りますが調べながら書きます

*5:Making object-based STM practical in unmanaged environments

*6:Automatic data partitioning in software transactional memories

*7:wait-free STMの具体的な実装は知らないのですが、lock-freeなSTMならRingSTMがそれっぽく見える

*8:多分C++でやるとマクロとoperatorの嵐になるんじゃないかと思いますが

*9:多分僕は喜んでやりますが

*10:これ書きながら真剣に考えたら、索引する際にはmap参照→listのポインタ獲得→map参照の順で行い一致した場合のみアクセス可能とし、消す際には必ずmapからの参照を消してからlistから消すようにし、参照をweak_ptrにすればなんとかなるようなならないような…いずれにせよ自明ではないです

*11:外からストライプロックで保護してやるというのも可能ですが、無駄なロックを取ることは避けられません

*12:知らない人は居ないと思いますがcasは「比較→一致した場合に限り代入」を一気に行うCPU命令です。慣例に従いCAS(目的のアドレス, 想定する値, その値だった時に上書きする値)という使い方をします。

*13:write_valueする際にoldの値が最新のoldじゃないとダメなのでリトライするならread_valueからやり直すべきなんだけれど説明するにはせせこましくて

*14:SQL文は多分ファントムリードによる無限ループとか発生し得ないんじゃないかなと思います

*15:最近の論文だと「ヒューリスティックを用いて回避する」とだけ書いてあったりして一体どういうヒューリスティックなのかと問い詰めたい

*16:はてなスター100個ぐらい貰えたら

*17:どんどんスレッドローカルストレージに入れていけばいいのかな…コンパイル時じゃなくて実行時解決

*18:Xeround反則だろ…

Pythonで使えるLRUを比較する

高速化の為にローカルにキャッシュを設けたい、でもメモリを無駄遣いする気はない、といった場合にLRU(Least Recentry Used)キャッシュを使うのはよくあるパターンです。
pythonでLRUキャッシュをさがすといくつか選択肢が見つかります。

$ pip search lru
pylru - A least recently used (LRU) cache implementation
ciutils - Helpers to use in CI environments (e.g. use
xmlrunner together with `test` command)
repoze.lru - A tiny LRU cache implementation and decorator
darts.util.lru - Simple dictionary with LRU behaviour
velruse - Simplifying third-party authentication for web
applications.
lrucache - Least-recently-used (LRU) cache module
pyplugin - Python NPAPI plugin for XULRunner
lru - A simple LRU cache implementation

中でもpylru, repoze.lru, lruが使えたので入れて比べてみました(lrucacheはName or service not known> while getting http://bad.dynu.ca/%7eevan/lrucache/lrucache-0.2.tar.gz (from http://pypi.python.org/simple/lrucache/)とか出てインストールできませんでした。)

結論を先にネタバレするとpylru推奨です。

使い方

使い方はそれぞれこんな感じです
pylru

import pylru
# 追加
cache = pylru.lrucache(1000) # サイズを指定
cache[0] = 10 # []=で、代入
# 参照
assert cache[1] == 1 # []でアクセス
try:
  cache[1]
  assert False
except KeyError: # 見つからなければKeyErrorが投げられる
  pass

lru

import lru
cache = lru.LRUCache(1000)
# 追加
cache[0] = 10
# 参照
assert cache[1] == 1
try:
  cache[1]
  assert False
except KeyError:
  pass

repoze.lru

import repoze.lru
cache = repoze.lru.LRUCache(1000)
# 挿入はput
cache.put(0,10)
# 参照はget
assert cache.get(0) == None
assert cache.get(1) == 1

pylruとlruが[]によるアクセス、repoze.lruはset,getメソッドでアクセスするようです。
どれを使っても困らなさそうなので比較ベンチを取ってみます。

ベンチマーク

CPU AMD Phenom(tm) II X4 955
OS Linux2.6.35-30-generic-pae
Python 2.6.6

サイズ10000固定でn回操作するのにかかった時間のグラフです(縦軸が秒、横軸がn)
ベンチマークはそれぞれ10回ずつ行って平均を取りました*1
サイズを変動させた方のベンチマークのほうが興味深かったのですが後述する理由により固定です*2

各種目のベンチマークは長いのでこちらへ
https://gist.github.com/1319383


lruのput(紫)だけ致命的に遅くて他のグラフが下に潰れています。
lruのputが一体何やってるのか調べてないですがこれでは比較になりません。
なのでlruのputを省いてグラフを描いてみます。

lruはgetも他と比べて遅いようですが、何かオフセットのような物があるのは何なんでしょう…?
勾配はpylruに近いのですが最小のたかが100000要素のget操作に1.9秒もかかっています。
repoze.lruのput(紫)はpylruのput(緑)と比べて遅いようです。
その代わりrepoze.lruのget(水色)はpylruのget(赤)より僅かに速いようです。

この比較から、一番バランスが取れて性能が出せているのはpylru。repoze.lruはgetが僅かに速いですがput操作が遅いです。
また、lruは致命的にputが遅いので非推奨と感じました。というかlruの470万回のputで1600秒とか掛かってて時間かかり過ぎで当初の予定通りのベンチマークが取れなかったです…。

結論: pylru推奨。lruは地雷。

以下は取るだけとったフルの比較

*1:分散をgnuplotで同時にプロットさせる方法を誰か教えてください><

*2:今度取り直します

続きを読む

PythonでThriftを通してHibari

HibariというErlangによる分散KVSがあるようです
http://hibari.github.com/hibari-doc/hibari-app-developer-guide.ja.html
流行りのEventualConsistencyではなく、高い一貫性を守りつつスケールするという代物です。

インストールする

http://hibari.github.com/hibari-doc/hibari-app-developer-guide.ja.html
に従っていけばできます。Repoというソフトウェアに依存しています。
比較的新しいErlang環境を要求するところも注意が必要です。
逆に、repoさえあれば

$ repo init -u git://github.com/hibari/manifests.git -m hibari-default.xml
$ repo sync
$ make
$ make package

でほぼ完了します。

Repoの入手場所のサーバが落ちていて途方に暮れていたら[twitter:@tatsuya6502]さんが緊急回避的にgistを教えてくださいました。

Repoから参照しているandroid.git.kernel.orgが使えなくて途方に暮れていたらまたしても[twitter:@tatsuya6502]さんに助けて頂けました。至りつくせりです。本当にありがとうございます。

無事立ち上がりました

Thriftを使う

インストールしたHibariの内部に
hibari/lib/gdss_ubf_proto-0.1.7/priv/thrift/hibari.thrift
というファイルがあるので好きな場所に持ってきます。持ってきた場所で

$ thrift --gen py hibari.thrift

と打つとgen-pyディレクトリが作成され、中にimportできる物が一式揃います。便利ですね。

$ ls
hibari.thrift gen-py/
$ ls gen-py
__init__.py hibari/

早速使ってみます。

import thrift
from thrift.transport import TSocket
from thrift.transport import TTransport
from thrift.protocol import TBinaryProtocol

from sys import path
path.append('gen-py')
from hibari import Hibari # Clientを使う
from hibari import ttypes # 命令に使うオブジェクト群

# ソケットを作成
socket = TSocket.TSocket('localhost',7600)
socket.setTimeout(None)
transport = TTransport.TBufferedTransport(socket)
protocol = TBinaryProtocol.TBinaryProtocol(transport)
client = Hibari.Client(protocol)
socket.open()

# 使ってみる
request = ttypes.Add(b"tab1", b"fookey", b"Hello Hibari!")
response = client.Add(request) #=> None or Exception
print response
$ python hibari_thrift.py
HibariResponse(value=None, key=None, timestamp=135)
$ python hibari_thrift.py
Traceback (most recent call last):
  File "app_main.py", line 53, in run_toplevel
  File "samp.py", line 21, in 
    response = client.Add(request)
  File "gen-py/hibari/Hibari.py", line 200, in Add
    return self.recv_Add()
  File "gen-py/hibari/Hibari.py", line 223, in recv_Add
    raise result.ouch
HibariException: HibariException(timestamp=None, what=101, why='Key Exist')

Add命令は「キーが存在していない場合に限り成功する」ので二度目に失敗するのは仕様通りの挙動です。(何故boolでなく例外で返してるか分かりませんが)
確かに動いてるのですが、自分好みにラップしたのが以下です。
thrift依存っぽいところをクラス内に押し込んで、python-memcacheっぽいインタフェースを提供しつつ、boolで返せそうな所はboolを使うようにして、valueには好きなデータを使いたいのでpickleによりシリアライズするよう。

続きを読む