はじめまして。開発・インフラ部、福田です。
分散処理環境、ミドルウェアの整備と運用、ELT/ETL、R&D、雑用を担当しています。
舞台裏から眺めるAstamuse.com
Astamuse.comは、イノベーションを起こすあなたの為のサイトです。そこでは国内約1,100万件の特許文書を誰もが見やすい形で見ることもできます。また、約480万のキーワードを収録し、キーワード経由の訪問は全体の約4割を占めています。
技術ページにはキーワードのリンクがちりばめられ、綺羅星のごとく旅人をやさしく見守っています。
アスタミューゼでは、Hadoopクラスタを運用しており、HBaseをはじめ、YARN上でのMapReduceやSparkなどを使い、語彙の抽出、XML文書の解析・変換、ドキュメントのインデクシング、画像の変換などを行っています。
これらのデータ処理において、私たちはスループットを重視しています。ここでは、1千万件を超える文書と数百万件規模のキーワード辞書マッチングの工夫についてお話します。
基本となる技術要素
トライ木、XBW、辞書マッチング
Hadoop、HBase、Java、Python、Scala、Spark、YARN
要件
まず、実現したいことを整理すると以下の2点になります。
- １千万件の特許文書のテキストの辞書マッチングが合理的な時間内に終えられること
- 辞書マッチングにおいて、キーワード毎に付与したIDが解決できること
1つめは、特許文書のテキスト中の辞書キーワードを抽出する問題です。
一般的には、辞書式マッチングなどと呼ばれ、Trieというデータ構造を使用した方法が知られています。Trieとそれを利用したアルゴリズムについては、ウェブや書籍に詳しいためここでは説明を省きます。
2つめは、アプリケーションの要求で、マッチング結果にキーワード毎に付与された一意の識別子が必要になります。
背景と文脈
初期のアプローチ
当初、われわれのボキャブラリーは25万に満たない程の小さなものでした。コンテンツのリリースに向け、単純なトライ木を実装しました。デプロイされたコードは正しく動き、データは滞りなく更新されていきました。そう、あの日までは。
インシデント発生
ある午後、データ解析処理のジョブがメモリ不足に陥ることがわかりました。コンテンツ拡充のための段階的なキーワード追加の影響です。
当初のナイーブな実装ではメモリ消費量が大きすぎ、並列分散処理に支障をきたすようになりました。
本来、より早い段階で気づける問題でした。チームメンバーとのコミュニケーションミスにより、確実なテストがされないままキーワードの増加を迎えました。このことを深く反省しています。そして、反省そのものは問題を解決しません。
解決に向かって
まず、解決すべき問題を整理し、ゴールを設定しました。
ゴール定義
可能な限り早く障害を取り除き、更新を再開させること。(1週間以内に解決することが望ましい。)
課題ブレイクダウン
何をどうすればよいかを整理した結果、以下の3つを戦術目標としました。
- メモリの消費はMapタスクあたり2G以内で収まること(フルに使えるわけではない)
- 現実的な時間内にワークロードを終えられる実行速度が確保できること
- 既存のプログラムのインターフェースを変えないこと
調査検討の末、コンパクトかつ高速であることが期待できるXBWというアルゴリズムによるTrie木の実装を試みました。
数日間のハッキングの末、目標を達成できるコードが完成したため、回帰テストを行い、本番環境にデプロイし、更新を再開することができました。
成果の検証
ここで、当時起きたことを再現するコードとテストデータ作成し、2つの実装を比較してみます。
実験手順
全量データからサンプル抽出した25万、50万、100万、250万件と全量(約480万)の5通りのテストデータセットを用意し、それぞれデータをロードします。
平均キーワード長は7.34文字
性能の比較のため、トライ木を巡回し全キーワードのリストを出力するコードを用意し実行し
ます。
今回の実験では、ディスク書き込みの影響を無視するため標準出力に出力された結果を/dev/nullにリダイレクトしています。
XBWの方は、データを前処理し、ロード済みのオブジェクトをシリアライズし永続化したものをロード
ロード時間と、ツリー巡回の実行時間を測定 (各5回実行し、平均値を使用)
メモリの使用量についてはJava8の Native Memory Trackingを有効化し、出力のJava Heap Sizeを記録
実行環境
CPUとメモリ
4.6.3-gentoo x86_64 Intel(R) Core(TM) i7-2600K CPU @ 3.40GHz GenuineIntel GNU/Linux
16GB
Java 1.8.0_92
結果
計算のオーバーヘッドのためか、巡回の速度面では単純な実装に及ばないものの、メモリ消費量が低く抑えられており、ロード時間の短縮にも貢献しています。
これにより、限られたリソースで、合理的な時間内にワークロードを終えることができるようになりました。
まとめ
大規模テキスト集合と大きなキーワード辞書のマッチングを、XBWアルゴリズムによる省メモリ且つ高速なトライ木の実装を行い、単純な実装との比較を行い、XBW実装の空間効率が良いことを示しました。
学び
- コミュニケーションは密に。確認は入念に。
- 自分たちの使うものは自分たちでつくる。ないものは作る。
- 最小限のリソースを最大限利用するための工夫を怠らない。
参考文献
- 高速文字列解析の世界―データ圧縮・全文検索・テキストマイニング 岡野原 大輔 (著)
- Faster compressed dictionary matching Wing-Kai Hon, Tsung-Han Ku, Rahul Shah, Sharma V. Thankachan, Jeffrey Scott Vitter
本記事の内容は、2014年2月頃の出来事を振り返り、記事作成にあたり新たに比較データを取得しまとめたものです。
