2月
04

PHP と MySQL でカジュアルに MapReduce する

yuya MySQL, PHP Add you comment

副題: ビッグデータ時代の非ビッグデータ集計戦略

PHP と MySQL を使ってカジュアルに MapReduce する MyMR というものを作ってみました.
とても安直な名前ですね.

yuya-takeyama/mymr – GitHub

とりあえず試してみる

MyMR には, MapReduce のマナー (?) に従って, WordCount するためのサンプルコードとサンプルデータを同梱してみました.

map/reduce 関数は PHP で書かれています.
WordCount.php

MySQL のユーザ名・パスワード等は適宜置き換えて下さい.

見事, 入力テーブル内の単語の出現回数を集計することができました.

MyMR の特徴

  • データの入出力はいずれも MySQL のテーブル
  • 入力と出力のデータベースは同じでもいいし別でもいい
    (入力はプロダクションサービスの Slave サーバで, 出力はデータ集計用の別サーバ, とかいうこともできる)
  • map/reduce 関数を PHP で書く
  • MySQL を意識することは無く, PHP 標準の array にほげほげするだけ
  • 分散/冗長性/耐障害性などについては特に考えていないし, 考える予定も無い
    (エラー処理はちゃんとしたい)
  • 並列処理でなく直列処理
    (並列処理は出来た方がいいと思っている)

まだ「とりあえず動く」程度の状態なので, 色々足りてない状態ではありますが, ギガ/テラバイト級のデータを相手にするのであれば Hadoop とかを使うべきだと思いますし, MyMR はそのような問題を解決しようとはしていません.

モチベーション

  • MySQL に直接 MapReduce 処理を行いたい
  • GROUP BY よりはもっと複雑な処理がやりたい
  • map/reduce を LL で書きたい
  • プログラミングモデルとしての MapReduce を活用したい

DBMS 上で MapReduce をやりたいのであれば MongoDB や CouchDB という選択肢がありますし, map/reduce を LL で書きたいというのであれば Hadoop Streaming という選択肢があるでしょう.
そうなると, やはり一番のモチベーションは MySQL で MapReduce する ということに尽きるように思います.

MongoDB による MapReduce も JavaScript でカジュアルにできてとても便利です.
ですが, 自分の場合, 普段の仕事だと, そもそものデータはほとんど MySQL に入っているので,

  1. mysqldump で csv ファイルを作成
  2. mongoimport で MongoDB にインポート
  3. MongoDB 上で MapReduce

みたいな手順を踏む必要があり, 非常に面倒です.
場合によっては mongoexport で csv に出力してさらに MySQL 上にインポート, なんてことをやることもあって, 正直疲れました.

MySQL で ということの次に重要だと思うのが, プログラミングモデルとしての MapReduce です.
これについては書くと長くなりそうなのでやめておきますが, Haskell のような関数型言語をつまみ食いすることで, この辺りの魅力がわかってきたように思います.
(関数型言語における map 関数と Hadoop/MongoDB/MyMR における Map はちょっと違いますが)
伊藤直也さんの MapReduce::Lite なんかも, その辺りにモチベーションがあって作られたのではないか, と想像しています.

何故 PHP か

特に大した理由はありません.
強いていえば仕事で使いたいと思っていて, 周囲で使われているのが PHP である, というだけの話です.

ついでに挙げるなら, PHP では MySQL ドライバが標準で備わっている, というのもあります.
MyMR では PDO を使っており, 普通に構築された LAMP 環境であれば, まず問題無く使えると思います.

とはいえ, 例えば Bundler の使える環境であればそういった依存関係に悩まされることもありませんし, 正直 Ruby で書き直したい.

MyMR の仕組み

仕組みといえるほど複雑なことはやっていませんが…

1: 入力データの取得

これはとても単純で, mymr コマンドの -i (–input) オプションに渡したテーブルを全件 SELECT するのみです.

今の所全データをガバっとメモリ内に取り込むようになっているので, テーブルサイズに比例してメモリを食います.
非ビッグデータ向けのフレームワークとはいえ, これはさすがにあんまりなので, 何とかするつもりです.

あと, 未実装ですが, WHERE 条件なども指定できれば入力の段階でフィルタできて便利そうなので, やろうと思っています.

2: Map

SELECT で取得した全ての行に対して Map 処理を行います.

MyMR の map 関数では, その中で emit メソッドを実行することで, テンポラリテーブルにデータを INSERT していきます.
関数のプロトタイプは void map(array $record) というシンプルなもので, 1 レコードを表すハッシュ (PHP なので array) を受け取るだけです.

入力テーブルの定義についての制約は特にありません.
通常どんなテーブルでも入力として扱うことができます.

emit にはキーとそれに対応する値を渡すことで, 中間データがテンポラリテーブルに 1 行ずつ挿入されます.
本来は MySQL セッションが終了した時点でテーブルは消えるのですが, 先の WordCount の例でいうと以下のようなテーブルが作成されています.

emit に渡された値は自動的に JSON に変換されています.

JSON 化してるのは構造化データを扱えるようにするためで, この辺りは MongoDB の MapReduce にインスパイアされてます.

3: Shuffle/Sort (?)

Hadoop なんかで言うところの Shuffle/Sort 付近に該当する, と思っているのですが, あんまり自信ないです.
ぶっちゃけると Hadoop 自体を使ったことは無くて, ブログ記事や書籍でつまみ食いした程度の知識しかありません.
(り, りろんはしってる (知らない))

とにかく, ここでは Reduce フェーズの前の下準備として, キーが同一のものをグループ化しています.

MyMR ではカジュアルに GROUP BY と GROUP_CONCAT を使っています.

実際は GROUP_CONCAT の SEPARATOR には改行コードの LF を指定しており, 複数の JSON が改行区切りで連結されたものになります.
要するに複雑なパース無しで複数の JSON を分割できるデリミタであれば何でもよくて, 無難に LF を使っているというだけの話です.

ところで, ここで JSON の代わりに MessagePack を使えれば, それだけである程度高速化できると思うんですが, そのときのデリミタは何にすればいいんでしょう?

4: Reduce

前の Shuffle フェーズで実行したクエリの結果全行に対して, 1 行 1 行 Reduce 処理を行います.

Map と同様, reduce 関数に 1 行 1 行の値を渡していきます.
関数のプロトタイプは array reduce(string $key, array $values) となっています.
$values では GROUP_CONCAT で改行区切りとなっていた JSON を予めパースし, 値の配列として渡されます.

そして返り値のハッシュがそのまま 1 行として -o (–output) に指定されたテーブルに 1 行 1 行挿入されていきます.

また, map と違って単純な入出力モデルになっているので, テストが書きやすいという利点があります.

そしてこれも map と違って, 挿入するデータは JSON ではなく, ハッシュのキーをカラム名としてレコードにマッピングされます.
そのため, 出力テーブルの定義は reduce 処理に合わせておく必要があります.

これまた map と違って, 出力テーブルでは key という名前のカラムが, キーを格納するために予約されており, reduce 返すキーとしては避ける必要があります.
それ以外は自由ですが, key カラムにはユニークインデックスを設定しておくのが良いでしょう.

まとめ

MyMR について長々と書いてきましたが, この記事で一番主張したいのは「MySQL から直接 MapReduce できたら便利じゃないか」ということに尽きます.
そういう需要があってもよさそうなものですが, ググってみても意外とそれらしい記事は見つからず, じゃあ作ってみようということでできたのが MyMR です.

ほとんどプロトタイプみたいなもので, 作り込みはまだまだこれからですが, 「MySQL で MapReduce する」というアイディアを発表したくて, この記事を書いています.

また, 今回はたまたま MySQL でしたが, 入出力を抽象化して MapReduce をするための何かがあれば, いろいろ捗るんじゃないかなぁという妄想もあります.

ビッグデータは無くとも, ビッグデータ時代に生まれた知見を活かすことはできるんじゃないか, というお話でした.

See also

,
11月
07

MySQL と N-gram による高速な日本語全文検索の実装

yuya MySQL, PHP 1 comment

2010-11-08 10:45 追記
以下の記事中のベンチマークですが、 N-gram 検索時にクエリキャッシュが効いている疑惑が持ち上がりました。
よって、表の数値は、必ずしも検索それ自体の性能を示すものではないかもしれない、という点にご注意ください。
詳細についてはただいま調査中 & MyNA ML にて質問中です。

本編
先日も書きましたが、 Openpear に Text_Ngram というライブラリを公開しました。 GitHub にも公開しています。
PHP で N-gram を生成する

せっかくなので、これを利用したプログラムのサンプルを公開してみます。

Zip Code Search with N-gram
Text_Ngram を用いて N-gram インデックスを作成し、高速に全文検索を行う実験。

普通の LIKE 演算を用いた検索と比べて、実際にどれぐらいの差がでるのか計測してみましょう。「恵比寿ガーデンプレイス」という単語を検索した際のスピードは以下のようになりました。

LIKE N-gram
1 119.127 msec 34.683 msec
2 132.0829 msec 30.2732 msec
3 129.246 msec 31.822 msec
4 92.5341 msec 18.944 msec
5 114.574 msec 9.2828 msec
6 107.5969 msec 6.393 msec
7 101.4121 msec 8.9741 msec
8 140.8319 msec 7.3969 msec
9 145.6361 msec 8.6441 msec
10 127.3508 msec 9.9769 msec
Avg. 121.0392 msec 16.6390 msec

この通り、 7 倍近い性能を出すことに成功しています !

以下では、実装のために実際に行った手順と、実装の一部を紹介します。

動作環境

私の手元では以下のような環境で、動作を確認しております。基本的に、 Ubuntu 10.04 上でパッケージマネージャを用いただけの、簡単な LAMP (Linux / Apache / MySQL / PHP) 構成です。

# Linux
$ cat /etc/lsb-release
DISTRIB_ID=Ubuntu
DISTRIB_RELEASE=10.04
DISTRIB_CODENAME=lucid
DISTRIB_DESCRIPTION="Ubuntu 10.04.1 LTS"

# Apache
$ apache2 -v
Server version: Apache/2.2.14 (Ubuntu)
Server built:   Sep 28 2010 12:52:38

# MySQL
$ mysqld -V
mysqld  Ver 5.1.41-3ubuntu12.6 for debian-linux-gnu on i486 ((Ubuntu))

# PHP
$ php -v
PHP 5.3.2-1ubuntu4.5 with Suhosin-Patch (cli) (built: Sep 17 2010 13:41:55)
Copyright (c) 1997-2009 The PHP Group
Zend Engine v2.3.0, Copyright (c) 1998-2010 Zend Technologies
    with Xdebug v2.0.5, Copyright (c) 2002-2008, by Derick Rethans

my.cnf の設定

[mysqld] セクションに、以下のような行を追加します。

[mysqld]
ft_min_word_len=1

これは、 MyISAM の FULLTEXT インデックスを作成する際の、単語の長さの最小値です。デフォルトでは 4 になっているので、ここを設定しないと、 2-gram を作成しても無視されることになります。

住所データの入手

日本郵政のサイトから CSV でダウンロードできます。
郵便番号データダウンロード

「読み仮名データの促音・拗音を小書きで表記するもの」→「全国一括」を選択して、ダウンロードします。

MySQL にテーブルを作成

以下のような定義でテーブルを作成します。 FULLTEXT インデックスによる検索が前提なので、 MyISAM であることが必須となります。
ただし、より高速にデータ投入を行えるよう、インデックスの作成は後回しにしています。

CREATE TABLE `addresses` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `zip` int(7) unsigned zerofill NOT NULL,
  `name` varchar(255) COLLATE utf8_unicode_ci DEFAULT NULL,
  `name_bigram` varchar(255) COLLATE utf8_unicode_ci DEFAULT NULL,
  PRIMARY KEY (`id`),
) ENGINE=MyISAM DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci

郵便番号、住所の他に、 N-gram (今回は 2-gram) のデータを入れるカラムを作っています。

住所データを MySQL に投入

以下のスクリプトを使用します。 Text_Ngram に依存しています。

以下のように実行して使います。

$ php make_bigram_addresses.php [住所データ CSV へのパス]

私の手元の環境では、 約 12 万行の INSERT が 3 分ほどで完了します。

テーブルに FULLTEXT インデックスを作成する

先ほど作ったテーブルに以下のような ALTER 文を流しましょう。 name_bigram カラムに FULLTEXT インデックスを追加します。

ALTER TABLE `addresses`
ADD FULLTEXT INDEX `name_bigram` (`name_bigram` ASC)

最終的に、テーブルの DDL は以下のようになると思います。

CREATE TABLE `addresses` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `zip` int(7) unsigned zerofill NOT NULL,
  `name` varchar(255) COLLATE utf8_unicode_ci DEFAULT NULL,
  `name_bigram` varchar(255) COLLATE utf8_unicode_ci DEFAULT NULL,
  PRIMARY KEY (`id`),
  FULLTEXT KEY `name_bigram` (`name_bigram`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci

以上で、高速な検索を行うための準備は完了です。

検索してみる

検索の際は、以下のような SQL を使用します。

SELECT SQL_NO_CACHE SQL_CALC_FOUND_ROWS *
FROM addresses
WHERE MATCH (name_bigram) AGAINST ('+恵比 +比寿 +寿ガ +ガー +ーデ +デン +ンプ +プレ +レイ +イス' IN BOOLEAN MODE)
LIMIT 3

このように、検索ワードも N-gram 形式にして検索する必要があります。

また、今回は計測が目的のため、 SQL_NO_CACHE オプションを用い、クエリキャッシュを無効化しています。

まとめ

今回は LAMP というシンプルな構成で、日本語対応の全文検索を実装してみました。

日本語での高速な全文検索を実現するソフトウェアには Tritonn や groonga, Hyper Estraier といった便利なソフトウェアも数多く存在するので、実際はそれらを使った方が簡単に実現できると思います。
しかし、実際にプロダクションとして運用するとなると、それらのソフトウェアについてのノウハウが必要となるため、なかなかそういった選択を採り辛いこともあるでしょう。

しかし、今回の方法であれば、 LAMP 以外のノウハウを特に必要としないので、比較的簡単に導入できるのではないでしょうか。

というわけで、皆さんも是非 Text_Ngram を使ってみてください !

参考文献

11月
04

サーバーをさくら VPS へ移転しました

yuya Announcement, Apache, Linux, MySQL 2 comments

これまでは XREA の有料ホスティングを利用していましたが、さくら VPS に移行しました。

この移転にあたって、大体以下のような作業を行っています。

  • さくら VPS 契約
  • OS は Ubuntu 10.04 (32bit) をインストール
  • ログインを公開鍵方式に限定して sshd を起動
  • ufw でファイアウォールの構築
  • aptitude や tasksel などで LAMP 環境の構築
  • WordPress 最新版をインストールし、テスト環境に
  • Git をインストール
  • テスト環境を Git リポジトリにチェックイン
  • RVM をインストール
  • WordPress 用とは別に Redmine 用ユーザーを作成し
  • Redmine 用ユーザーに RVM で Ruby 1.8.7 をインストール
  • Redmine 用ユーザーに Redmine をインストール
  • Redmine にブログ用のプロジェクトを作成
  • Redmine に、ブログ移転のために必要なタスクをチケットとして登録
  • Git リポジトリを Redmine と連携
  • Postfix をインストール
  • Redmine の更新が、Postfix を通じてメール通知されるように変更
  • 必要そうな WordPress プラグインをインストール
  • Apache を mod_proxy でリバースプロキシ化
  • munin をインストール
  • Mysql にスロークエリログが出力されるよう設定
  • 旧サーバーから WordPress の記事をエクスポート
  • 新サーバーに WordPress の記事をインポート
  • 本番環境用の VirtualHost を作成
  • テスト環境から git pull し、本番環境の構築
  • /etc/hosts を書き換え、擬似本番テスト
  • DNS の A レコードをさくら VPS のものに切り替え

大体こんな感じです。順番は必ずしもこの通りではありませんが。

さくら VPS では root 権限がもらえるので、いろいろインストールできるし、 Apache や MySQL についても細かく設定・監視ができるので楽しいです。 XREA のときにはできなかったような、より実践的なサーバー運用を学んで、このブログにも残していければと思います。

« Previous Entries