Main | July 2009 »

June 2009

June 29, 2009

MySQL のトリガーの実用性を確認するために InnoDB の SELECT COUNT(*) を高速化してみる

 最近 RDBMS のトリガーを色々書いているのですが、知らない人にトリガーが何かいちいち説明するのに簡単な例はないかな、というのと、MySQL の処理速度はトリガーによってどの程度変化するか、ということを確認するために、以下のような実験を行ってみました。

 InnoDB はしばしば、「SELECT COUNT(*) が遅い!」と批判されます。では、トリガーを使って行数を別のテーブルにキャッシュすればいいのではないでしょうか? 以下のように、極めて小さなテーブル t1 を作り、その行数を t1_cnt にキャッシュしてみることにします。

mysql> create table t1 (
    ->   id int unsigned not null primary key auto_increment,
    ->   v int unsigned not null
    -> ) engine=innodb;
Query OK, 0 rows affected (0.01 sec)

mysql> create table t1_cnt (
    ->   cnt int unsigned not null
    -> ) engine=innodb;
Query OK, 0 rows affected (0.01 sec)

mysql> insert into t1_cnt values (0);
Query OK, 1 row affected (0.00 sec)

 テーブルを定義し、t1_cnt に行数の初期値 (0) をセットしたら、次にトリガーを登録します。

mysql> delimiter |
mysql> create trigger t1_insert after insert on t1 for each row begin       
    ->   update t1_cnt set cnt=cnt+1;
    -> end|
Query OK, 0 rows affected (0.01 sec)

mysql> create trigger t1_delete after delete on t1 for each row begin
    ->   update t1_cnt set cnt=cnt-1;
    -> end|
Query OK, 0 rows affected (0.01 sec)

mysql> delimiter ;

 試しに t1 テーブルに値を出し入れして、t1_cnt の行数が変化することを確認します。

mysql> insert into t1 (v) values (1),(2),(3);
Query OK, 3 rows affected (0.00 sec)
Records: 3  Duplicates: 0  Warnings: 0

mysql> select * from t1_cnt;
+-----+
| cnt |
+-----+
|   3 |
+-----+
1 row in set (0.00 sec)

mysql> delete from t1;   
Query OK, 3 rows affected (0.00 sec)

mysql> select * from t1_cnt;
+-----+
| cnt |
+-----+
|   0 |
+-----+
1 row in set (0.01 sec)

 では、トリガーをセットしたことで、パフォーマンスはどれほど劣化するのでしょう。mysqlslap を使って測定してみます。

# トリガーが有効な場合
$ time /usr/local/mysql51/bin/mysqlslap -u root -S tmp/mysql.sock -c 20 -i 1000 -q 'insert into test.t1 (v) values (1)'
Benchmark
Average number of seconds to run all queries: 0.008 seconds
Minimum number of seconds to run all queries: 0.003 seconds
Maximum number of seconds to run all queries: 0.016 seconds
Number of clients running queries: 20
Average number of queries per client: 1


real 0m9.893s
user 0m0.590s
sys 0m1.975s

# トリガーが無効な場合
$ time /usr/local/mysql51/bin/mysqlslap -u root -S tmp/mysql.sock -c 20 -i 1000 -q 'insert into test.t1 (v) values (1)'
Benchmark
Average number of seconds to run all queries: 0.003 seconds
Minimum number of seconds to run all queries: 0.002 seconds
Maximum number of seconds to run all queries: 0.014 seconds
Number of clients running queries: 20
Average number of queries per client: 1


real 0m4.851s
user 0m0.612s
sys 0m1.911s

 トリガーを使うことで、書き込みパフォーマンスが約半分になっていることが確認できます。トリガーを使うことで、1回の INSERT で更新する行数は2倍になっているのですから、この結果は妥当だと考えられます。逆に言うと、トリガーという機能特有のオーバーヘッドは、少なくともこの場合はない (クライアントサイドでがんばってチューニングしなくても、トリガーに頼ってよい) ということになります。

 実際の運用では、テーブルの1行のサイズは、このテストで使った t1 テーブルよりもずっと大きいでしょうし、また、INSERT や DELETE 以外の SELECT や UPDATE 実行時には、今回セットしたトリガーはそもそも実行されないので、行数をカウントすることによるオーバーヘッドは、もっと小さいでしょう。一方で、MySQL のトリガーは行ベース (1行毎に処理を行うタイプ) なので、多数の行を一度に更新するようなクエリを実行する場合は、注意が必要になってきます。

 というわけで、以上、トリガーの紹介と簡単なベンチマークでした。MySQL とトリガーについて詳しく知りたい方は、MySQL :: MySQL 5.1 リファレンスマニュアル :: 18 トリガ等をご参照ください。

 なお、上記ベンチマークは、MySQL 5.1.35 で innodb_flush_log_at_trx_commit=0 に設定して実行しました。

June 25, 2009

Q4M の mutex まわりを整理

 Q4M (Queue for MySQL) の mutex と rwlock のうち主要な部分を、「スレッド間で共有する変数のアクセス権制御を C++ コンパイラで強制する方法」で紹介させていただいたロック手法 (以下 CAC) を使うようリファクタリングしました。変更の過程でバグらしきものは見つかりませんでしたが、なにか未発見のバグが直っていたりする可能性、あるいは品質維持を考えて、今後は CAC ベースのリリースにしていこうと思っています。

 というわけで、非 CAC ベースの最終版 (0.8.6)、および CAC リリース (0.8.7) の最新版のプレリリース (バイナリ版は linux x86_64 のみ) が q4m.31tools.com/dist/pre においてあります。興味のある方はお試しください。しばらく様子を見て問題がなければ、0.8.7 を正式リリースにしたいと思います。

 また、(特に新しいバージョンの) Q4M が一度でも落ちたことがある、という方がいらっしゃいましたら、ぜひ詳細な情報をお寄せいただければと思います。よろしくお願いいたします。

注. 一点、--with-delete=msync の場合に、mysqld 起動後初回の Q4M 書き込み時に1回だけ、ロックが逆転する可能性があったことを確認しました

June 23, 2009

スレッド間で共有する変数のアクセス権制御を C++ コンパイラで強制する方法

 マルチスレッドなプログラムを書いていると、スレッド間で共有する変数へのアクセスを正しく直列化できているか、という点が常に問題になります。どうせなら、正しく書けているかコンパイル時に確認したいよね、ということで、以下のような C++ テンプレートを書いてみました。

template <typename T> class cac_mutex_t {
public:
 
  class lockref {
  protected:
    cac_mutex_t<T>* m_;
  public:
    lockref(cac_mutex_t<T>& m) : m_(&m) {
      pthread_mutex_lock(&m_->mutex_);
    }
    ~lockref() {
      pthread_mutex_unlock(&m_->mutex_);
    }
    T& operator*() { return m_->t_; }
    T* operator->() { return &operator*(); }
  private:
    lockref(const lockref&);
    lockref& operator=(const lockref&);
  };

protected:
  friend class cac_mutex_t<T>::lockref;
  T t_;
  pthread_mutex_t mutex_;
public:
  cac_mutex_t(pthread_mutexattr_t* attr) : t_() {
    pthread_mutex_init(&mutex_, attr);
  }
  ~cac_mutex_t() {
    pthread_mutex_destroy(&mutex_);
  }
  const T* unsafe_ref() const { return &t_; }
  T* unsafe_ref() { return &t_; }
private:
  cac_mutex_t(const cac_mutex_t&);
  cac_mutex_t& operator=(const cac_mutex_t&);
};

 使用例は以下のとおり。

// mutex lock が必須な Foo 型の変数を宣言
cac_mutex_t<Foo> foo_serialized(NULL);

{ // RAII で mutex lock してアクセス
  cac_mutex_t<Foo>::lockref foo(foo_serialized);
  foo->x = ...
  ...
}

 要は、RAII かつスマートポインタなクラスを使って、ロックをコントロールしつつ、アクセスの直列化を保証できるよ、ということです。

 テクニックとしては既存だと思いますが、ちょっとググった範囲では見つからなかったので、紹介させていただきました。

6月24日追記: 設計を整理、rwlock を追加して Q4M の svn に追加しました。(link)

June 15, 2009

Pacific のクライアントAPI (仮) について

 先週、概要を紹介させていただいた Pacific について。まだ API をフリーズしていないつもりなのですが、だいぶ整ってきた気がするので、ざっくりまとめておきたいと思います。


インストール手順

  1. Thrift をインストール注1
  2. Pacific の svn レポジトリからチェックアウト
  3. Perl ドライバを make (cd driver-perl && perl Makefile.PL && make all test install)
  4. リゾルバを make (cd resolver && make)

テーブルのセットアップ手順

 テーブルのセットアップは、pschema コマンドを使って行います。

# リゾルバの裏側の MySQL は 127.0.0.1:33060 で動作
#
# プライマリテーブル「user」を作成
#   ・ 分散キーの名前は「username」
#      (型は varchar(255) not null charset utf8 collate utf8-bin 固定)
#   ・ カラムとして realname varchar(255) not null,last_tweet_at int unsigned not null
#   ・ ノード内で、セカンダリテーブルとのリレーションを表現するカラム _iid
#      も生成される
#
pschema create-primary --manager=127.0.0.1:33060 --primary=user --hostport=127.0.0.1:33061 --primary-key-name=username 'realname varchar(255) not null,last_tweet_at int unsigned not null'

# セカンダリテーブル「tweet」を作成
#   ・ カラムとして mtime と body (と 上記 _iid)
#
pschema create-secondary --manager=$MANAGER --primary=user --secondary=tweet --primary-key=mtime 'mtime int unsigned not null,body varchar(255) not null'

 この結果、MySQL ノードには、以下のようなスキーマのプライマリテーブルが作成されます注2。ER図で書くと、こんな感じになります。

CREATE TABLE `user` (
  `_iid` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `username` varchar(255) CHARACTER SET utf8 COLLATE utf8_bin DEFAULT NULL,
  `realname` varchar(255) NOT NULL,
  PRIMARY KEY (`_iid`),
  UNIQUE KEY `_pac_key` (`username`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

CREATE TABLE `tweet` (
  `_iid` int(10) unsigned NOT NULL,
  `mtime` int(10) unsigned NOT NULL,
  `body` varchar(255) NOT NULL,
  PRIMARY KEY (`_iid`,`mtime`),
  CONSTRAINT `tweet_ibfk_1` FOREIGN KEY (`_iid`) REFERENCES `user` (`_iid`) ON DELETE CASCADE
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

リゾルバを起動

 先に make した pacific_resolver を起動します。TCP ポート番号は現在のところ 9306 に固定です。リゾルバが使用するデータベースの情報は、環境変数を用いて渡すことができます注3

$ PACIFIC_MGR_MYSQL_HOST=127.0.01 PACIFIC_MGR_MYSQL_PORT=33060 ./pacific_resolver

Perl クライアントからのアクセス方法

 まず、Pacific のドライバオブジェクトを生成します。

use Pacific::Driver::Direct;
use Pacific::Driver::Direct::DBI::DBD::mysql;
use Pacific::Driver::Direct::Resolver;

my $pac = Pacific::Driver::Direct->new({
    dbi => Pacific::Driver::Direct::DBI::DBD::mysql->new({
        user     => 'root',
        pass     => undef,
        database => 'pacific',
    }),
    resolver => Pacific::Driver::Direct::Resolver->new({
        host => '127.0.0.1',
        port => 9306,
    }),
});

 キーによるテーブルのルックアップは、イテレータを使って行います。Pacific は、渡されたキーがどの RDBMS ノードに属するかリゾルバに問い合わせを行い、そのキーに属するデータにリードロックをかけ、順次イテレータに値を渡してきます。

my @rows;
for (my $iter = $pac->query_iter('user', [ qw/Alice Bob Eve/ ]);
     $iter->next;
     undef) {
    my $r = $iter->dbh->selectall_arrayref(
        'SELECT username,realname FROM user WHERE ' . $iter->key_expr,
        {},
        $iter->key_values,
    ) or die $iter->dbh->errstr;
    push @rows, @$r;
}

 レンジクエリ(範囲を指定した検索)も同様に記述することができます。範囲指定の演算子は、< <= > >= を組み合わせて使うことができます。

# Bob 以降10人を取得
my @rows;
for (my $iter = $pac->query_iter('user', { '>=' => 'Bob' });
     $iter->next;
     undef) {
    my $r = $iter->dbh->selectall_arrayref(
        'SELECT username,realname FROM user WHERE ' . $iter->key_expr
            . 'LIMIT ?',
        {},
        $iter->key_values,
        10 - @rows,
    ) or die $iter->dbh->errstr;
    push @rows, @$r;
    last if @rows >= 10;
}

 書き込みにあたっては、query_iter の代わりに modify_iter を使用します注4

for (my $iter = $pac->modify_iter('user', qw[ /Alice Bob/ ]);
     $iter->next;
     undef) {
    $iter->dbh->do(
        'UPDATE user SET hitpoint=hitpoint+10 WHERE ' . $iter->key_expr,
        {},
        $iter->key_values,
    ) or die $iter->dbh->errstr;
}

 ノード内でトランザクションを組むこともできます (下の例のように、単一のキーにアクセスする場合も、イテレータを使います)。

# tweet テーブルに発言を追加し、user テーブルの最終発言時刻を更新
for (my $iter = $pac->modify_iter(
         'user', [ qw/Alice/ ], { transactional => 1 },
     );
     $iter->next;
     undef) {
    $iter->dbh->do(
        'INSERT INTO tweet (_iid,mtime,body) VALUES'
            . ' ((SELECT _iid FROM user WHERE username=?),?,G)',
        {},
        'Alice', $tweet_at, $tweet,
    ) or die $iter->dbh->errstr;
    $iter->dbh->do(
        'UPDATE user SET last_tweet_at=? WHERE user=?',
        {},
        $tweet_at, 'Alice',
    ) or die $iter->dbh->errstr;
}

 また、より高レベルな ORM っぽいインターフェイスを提供する Pacific::Driver::Direct::Accessor モジュールもありますが、自分は元来 ORM 不要派で経験値が低いので、あまり深入りしたくない (深入りしたところでいいものができないと思ってる) 気持ちです。

 それではひとまずこのあたりで。ノードの分割/再配置に使う prelocate コマンドについても、また書きたいと思います。

注1. Pacific の開発は、Thrift の同ページにある Archived release (r760184) を使って行っています。でも、インストールが面倒なわりに Thrift の Perl クライアントはおそいので、何か別のトランスポートに換えようとと考えています。
注2. ノード内部でリレーションを表現するために _iid という値を別途使用するのは、空間効率を高める一方で、データの分断につながります。ですので、今後、_iid を使わず、セカンダリテーブルにも直接分散キーを書き込むモデルをサポートすることも考えています
注3. 使用可能な環境変数については、MySQLDriver.cpp を参考にしてください
注4. 範囲を指定した更新については、現時点で未対応です

June 10, 2009

Pacific という名前の分散ストレージを作り始めた件

 大規模なウェブアプリケーションのボトルネックがデータベースであるという点については、多くの同意が得られるところだと思います。解決策としては、同じ種類のデータを複数の RDBMS に保存する「sharding」 (別名:アプリケーションレベルパーティショニング/レベル2分散注1) が一般的ですが、最近では、分散キーバリューストア (分散 KVS) を使おうとする試みもみられるようになってきています。

 分散 KVS が RDBMS sharding に対して優れている要素としては、事前の分割設計が不要で、動的なノード追加(とそれにともなう負荷の再分散)が容易、といった点が挙げられると思います。一方で、KaiKumofs のような最近の実装では eventually consistent でこそ無くなってきているものの、ハッシュベースの分散 KVS は、レンジクエリができなかったり (例: 最新5件の日記を表示)、トランザクションがないためアプリケーションプログラムが複雑になったりするという問題を抱えています。

 では、どうすればいいのか? MySQL や PostgreSQL を使った RDBMS sharding でも、動的なノード追加(と無停止での負荷の再分散)を実現したい。というのが、今回コードを書き始めた動機でした。それが Pacific です。

 技術的には、大して複雑ではありません。Pacific は、パーティショニング情報とロックを管理する中央サーバ(リゾルバと呼んでいます)と、実際のデータを保存する RDBMS のノード群によって構成されます。

 Pacific では、レンジクエリを実行するために、ユニークキーを利用したレンジパーティショニングを行います。レンジパーティショニングは、ハッシュベースのパーティショニングよりもデータの局所性が向上するので、パフォーマンスや障害の局所性が高まるという効果も期待できます。

 また、トランザクションを可能にするためには、関連するデータが常に同一のノード上に配置される必要があるため注2、全てのデータがパーティショニング用のキーに関連づけられるようなテーブル設計を強制することになります。このデータモデルは、(Pacific が RDBMS 上の分散ストレージであるという点を除けば) Google App Engine の Data Store注3 と同様です。Pacific では、パーティショニング用のキーを含むテーブルをプライマリテーブル、プライマリテーブルと 1:1 または 1:n のリレーションをもつテーブルをセカンダリテーブルと呼んでいます。

 データの再配置は、単一の (あるいは数個の) ユニークキー単位で、1) そのキーに属する全データに排他的書き込みロックをかけ、2) データを別ノードにコピー、3) パーティショニング情報を更新して書き込みロック解除、 4) 旧ノードから読んでいるクライアントがいなくなった時点で旧ノード上のデータ削除、という操作を繰り返すことで行います。再配置中に読み込みがブロックされることはありませんし、書き込みがブロックされる時間も、エンドユーザーが意識しなくていい程度に抑えることができる、と考えています注4

 一番アクセスが集中するのはリゾルバということになりますが、パーティショニング情報の変更は少ないことが予測できますから、ストレージへのアクセス数が 10万 QPS 程度になるまでは問題は発生しないと思います注5。また、パーティショニング情報は RDBMS に保存されるため、リゾルバが不正終了しても、データの不整合が発生することはありません。

 Pacific については、コードは公開の svn レポジトリ注6上においてありますが、現状、テストコードとラフなサンプルが動いている程度で、ドキュメントが全く未整備です。進捗や具体的な使い方等については、今後このブログで書いて行きたいと思います。

17:12追記: 高可用性については、ウェブアプリケーションが使う分散ストレージの場合、ネットワーク分断が発生しない(冗長化によって防止できる)ので、ノードをまたがるような冗長化は必要なく、各ノード毎にクラスタを組めばいいという考えです。

注1. ミクシィのCTOが語る「mixiはいかにして増え続けるトラフィックに対処してきたか」:ITpro
注2. 多くのトランザクションは、関連する数個のテーブルに対する局所的な操作であるという仮定の下、同一のキーに属するデータ内でのみトランザクショナルな操作を可能としています
注3. The Python Datastore API - Google App Engine - Google Code
注4. 書き込みがブロックされる時間は、特定のキーに属するデータサイズ (Google App Engine で言うところのエンティティグループの大きさ) をコピーする時間に依存しますが、一番遅いのはHDDにシーケンシャル書き込みになるでしょうから、数MB/s 程度は目指したいところです
注5. より高いパフォーマンスが必要なら、リゾルバをレプリケーション対応化すればいいという話です。同時に、各ノードへの直接接続をやめて、中継サーバを用意するといった作業も必要になるでしょう
注6. http://kazuho.31tools.com/svn/pacific/

June 01, 2009

My weblog URL changed (ブログ移転のおしらせ)

My weblog has moved from labs.cybozu.co.jp/blog/kazuho (in Japanese), labs.cybozu.co.jp/blog/kazuhoatwork (in English) to this new location.  The latter has been merged as in English category of the new weblog.

RSS and Atom feeds have been redirected permanently to that of the new weblog. Old weblogs will be kept open as static pages.