ユーザー検索処理(あるいは配列マージ性能の言語比較)

ユーザー検索処理(あるいは配列マージ性能の言語比較)


MIIDAS COMPANY 磯崎です。

MIIDASではユーザーの登録時にたくさんの質問をしています。(年齢、学歴、経験企業、経験業務、英語ができるかどうか、転職回数、マネジメント経験、資格など)これらをたくさんの属性を条件に検索するのですが、「どれを検索条件にするかって? 全部だよ、全部。」という仕様があります。

たとえば、

  • 現職中の正社員で、25-35歳、営業の経験が2年以上あり、大学卒、英語が出来て、自動車免許をもっていて、転職経験は2回以下、
  • 現職中か離職3ヶ月以内で、金融業界の経験があり、PHPかJavaを2年以上、なんらかWebフレームワークの使用経験のある、直近の年収が700万円以下のエンジニアを若い順で

簡単なようで結構面倒で、またスケールするのが難しいですよね。

現在は、Mysqlの正規化されたデータを、入力された検索条件でSQL組み立てて実行しています。ですが、その実行計画をみてみると、ユーザーテーブルのキーを1つ2つ使ったあとはフルスキャンとなっています。ユーザ数が10万人に満たない現状でも、検索SQLは平均0.3秒程度かかっています。

このような処理はBI界隈では結構フツーにあり、分散クエリで解決できるとは思うのですが、OLTPでの処理について調べました。

  • スケールするようになるべくDBサーバの負荷をかけない
  • ユーザ数 100万人、100属性/ユーザ
  • 一番負荷がかかるパターンとして、想定検索結果 80%のユーザが該当する条件を20 個ANDでつなげる(検索結果:100万人 × 0.8^20≒1万人)
  • レスポンス 0.5秒以内
  • マシン:2013rate imac 2.7Ghz Corei5 メモリ8G

上記ができるかどうか調べてみました。

今回の課題のようなユーザ検索は、以下の2つの処理に分解できます。

A.検索条件の一つを満たすユーザのリストを取得する(80万ユーザのリスト × 20個)
B.上記のリストをマージして、すべてに存在するIDを取得する

A については、キーを使った検索なので、SQL自体は0.01秒で返ってきますし、
並列実行すれば、0.2秒はクリア出来そうですので、こちらは割愛。

Bが、0.3秒程度で実行できればよさそうです。

配列のマージ

配列のマージ処理は、PHPでは

for($arrays as $a){$result = array_intersect($result,$a)}

です。ユーザーIDを見立てた数値の配列を作成し上記を実行してみます。ソースはこちら。(git clone git@github.com:sei-isozaki/test-user-search.git)

php 02_array/01_php_test.php
PHP Fatal error: Allowed memory size of 134217728 bytes exhausted (tried to allocate 32 bytes)

おっと、100万人分のリストといっても1M×8Byte ×20 なので、最低200MBは必要ですので、メモリリミットを上げます。
→ini_set(‘memory_limit’, ‘2500M’);(ちょっとずつ上げましたが、1500Mでもエラーになったので。。。)

php 02_array/01_php_test.php
7.5560331344604sec in GET USER LIST
98.847007036209sec in array_intersect)
result user_count:11374

めちゃ遅いです(PHPは5.6)。PHP7.0と、MIIDASで使っているHHVMで同じソースを実行してみました。

/usr/local/opt/php70/bin/php 01_php_test.php
25.767143964767sec in array_intersect)

hhvm 01_php_test.php
1.3095819950104sec in array_intersect)

HHVMすごいですね。ただ、まだ速度が十分でないので、試しにJavaでも同じことをやってみることにします。適当ですが、ソースはこちら

javac Hoge.java
java Hoge
get list:5472msec
merge:234msec

Listを作るのが、遅いのと、メモリをギガ単位で消費しているのが気になりますが、マージ速度については、目標達成です。

この結果をHHVMのソースにも反映します。JavaのHashSetのretainAllの実装を参考に、Hashを使ってくれるMapにしてみます(ちょっとメモリは無駄につかいますが。 ソースはこちら

hhvm 04_hack_map/03_hack_test2.php
3.3389778137207sec in GET USER LIST
0.24764108657837sec in array_intersect)
result user_count:11374

使用メモリは500MB程度だし(アクティブモニタで適当にみただけですが)、処理速度も目標をクリアしました。