読者です 読者をやめる 読者になる 読者になる

mixi engineer blog

ミクシィ・グループで、実際に開発に携わっているエンジニア達が執筆している公式ブログです。様々なサービスの開発や運用を行っていく際に得た技術情報から採用情報まで、有益な情報を幅広く取り扱っています。

かんたん友人検索 その弐

mixi
朝のジョギング生活を絶賛継続中ですが、あまり体重が減らなくてショボンヌなmikioです。さて今回は、Tokyo Dystopiaを使った検索機能「かんたん友人検索」の設計と実装についてお話しします。

全体の戦略

Tokyo Dystopia(TD)は単なる全文検索用のインデックス管理ツールです。多数の文字列の中から特定のパターンを含んだ文字列を特定する処理を高速化することはできますが、逆に言えばそれしかできないのです。住所を市区町村単位で限定して結果を絞り込むとか、ログイン時間が近い順に並び替えるとかの高機能は備えていません。Hyper Estraierにはそういったアプリケーション寄りの機能を持たせていましたが、逆にコードベースが肥大化して保守や最適化がしにくくなってしまいました。その反省を踏まえて、今回は、「全文検索による対象の絞り込み」だけはTDにやらせて、その他の機能は全て専用に書き下ろすことにしました。 かんたん友人検索のシステムを構成する機能を大別すると、プロセス管理、ネットワークインターフェイス、全文検索、属性による絞り込み、適合度によるソート、クエリの分散と結果のマージなどがあります。この記事では、まずは全ての機能で中核的な役割を果たすTokyo Cabinet(TC)に行った改良について説明し、次に各種のインデックスの構造と構築方法について触れて、さらに検索処理の具体的な手順を示し、最後にアーキテクチャ全体と個々の実装を概観します。

■ 機能構成

friendsearchfunctions.png

TCの性能を大幅にアップ

TDはTCをストレージに用いる検索システムですが、そのTCの性能を向上させることでTDの性能も向上させました。従来(1.2系列)までのTCは、reader/writerロックで排他制御を行っていました。すなわち参照(read)は共有ロックを用いて参照スレッド同士は同時に処理を行わせ、一方で更新(write)は排他ロックを用いて他のスレッドをブロックして独占的に処理を行わせるというモデルです。1.3.1では参照も更新も共有ロックを用いるようになり、openやcloseなどのメタな操作以外は全て同時に行えるようにしました。 ところが、ベンチマークテストをしてみると、ユーザランドでのロックをあらかた取り払っても、スループットが以前とあまり変わらないことがわかりました。Web等でいろいろ調べたところ、ファイルの読み書きに用いているpreadやpwriteの並列処理性能が(少なくともLinuxにおいては)あまり高くないのではないかという説が浮上しました。そこで、同記事に倣ってmmapを使うようにしたところ、単一スレッドによるパフォーマンスも複数スレッドのスループットも劇的に改善しました。100万レコードの読み書きの性能(単位は秒)を以下に示すとおり、今やTCの性能はCDBに匹敵するところまで来ています。

■ 旧バージョンとの比較

dbmversioncomparison.png

■ DBMファミリーとの比較

dbmbrothercomparison.png

TCの数え上げモード

検索やデータマイニングのシステムを実装する際には、様々な事象の頻度を高速に数え上げる必要に迫られることが多くあります。例えば、各ユーザのログイン頻度を数えたり、各ページの被閲覧数を数えたり、各単語の出現頻度を数えたりする処理です。そこでは、事象の識別子(ユーザIDや日記IDや単語の文字列)をキーとして、それに該当する出現回数を値としたハッシュデータベースを作り、キーを指定して値を増加させる操作が繰り返されます。この操作を効率化するために、TCの各種データベースに、以下のようなメソッドを追加しました(もちろんCのAPIでは関数として提供されます)。すなわち、キーに対応づけたint型またはdouble型の数値をアトミックに加算し、戻り値として加算後の値を返します。
int DB::add_int(string key, int num);
double DB::add_double(string key, double num);
上記のメソッド群がない場合、getして値を取り出してからそれを加算した結果の値をputをすることになるのですが、その方法だと2回演算が必要であるのみならず、アトミック性を確保するためにアプリケーション側でロックをかけなければならないので、大変効率が悪くなってしまいます。地味な機能ではありますが、こういう改善が後でジワッと効いてくるのです。なお、Tokyo Tyrant(TT)のバイナリプロトコルでも数え上げができるようになったので、同じような悩みのある方はぜひチェックしてみてください。

全文検索用転置インデックス

検索を高速に行うには、その過程で参照するデータを効率的に取得できるように予めインデックスを作っておく必要があります。ユーザの名前や自己紹介文を対象とした全文検索を行うので、mixi本体のデータベースに問い合わせて、全ユーザのデータを取得し、それをTDのユーティリティで転置インデックスに変換します。mixi本体はMySQLのデータベースなので、PerlのプログラムでDBIを使って接続して、結果はTSV形式のファイルとしてインデクシング用のマシンに保存します。あとはTDの付属のコマンドにそれを流し込むだけです。現状では転置インデックスの更新は24時間に1回のペースで行っています。転置インデックスの構造については以前の記事を参照してください。

属性データベース

かんたんユーザ検索では「性別」「年齢」「現住所」「出身地」による絞り込みを行うことができますが、それらはいずれもカーディナリティ(ばらつき)が低い属性なので、インデックスによって絞り込みを高速化することは現実的ではありません。「年齢」はカーディナリティが比較的高いと思われるかもしれませんが、「18歳から90歳まで」のような条件を入力される可能性もあるので、やはりインデックスは期待どおりに機能しないのです。

となると、候補の全件に対して逐次的に属性の照合を行うしかありません。それを高速化するために、全属性データをメモリに載せて、ユーザIDを添字にした固定長領域の配列として参照できるようにしました。実装は簡単で、インデックス作成時に全ユーザの属性を格納した構造体配列をそのまま直列化してファイルに書き込み、検索時にはそれをmmapして参照するようにしています。TCに固定長データベースというAPIセットがありますが、それとほぼ同じ発想です。

■ 固定長配列のイメージ

friendfixlength.png

スコアデータベース

かんたん友人検索の最大の特徴である適合度順の算出処理においては、現住所や最終ログイン時刻やマイミクシィの数などをスコア情報として利用します。これらの情報は検索されるユーザごとに一定で、検索操作を行うユーザによって変わるわけではないので、静的なスコア情報と考えられます。後述するマイミクシィグラフを使った動的なスコア情報と好対照です。現住所などはMySQLのデータベースから取得し、TTによる最終ログイン時刻データベースから取得します。これらの取得はインデックスを作成する前後に行うのが原則ですが、最終ログインデータベースは結構な負荷がかかっているので、負荷がピークになる時間帯(22時〜26時くらい)は避けるように制御しています。

マイミクシィグラフ非正規化データベース

適合度順の精度をさらに高めるために、マイミクシィ関係のグラフ構造を3ホップまで追跡して、操作しているユーザと各ユーザとの関係の強さを反映させています。そのためには、「誰と誰がマイミクか」を調べる処理をものすごい回数、しかもオンデマンドで実行することになります。ところで、mixi本体においてマイミクシィ関係のデータベースはMySQLで管理されています。リレーショナルデータベースのテーブルとして、ユーザIDのペアを二重化して保持しています。例えば3番と5番がマイミクシィである場合、[3:5]というレコードと、[5:3] というレコードを記録し、左の列にインデックスを張って高速に参照できるようにしています。 しかし、もしMySQLにマイミク関係を3ホップまで問い合わせるとなると1回の検索で10000回くらいMySQLにクエリを投げることになってしまうので、インデックスを張っているとはいえ、現実的な時間で応答することはできません。そこで、ユーザIDをキーにしてそのユーザのマイミクシィのIDの配列を関連付けた構造に非正規化し、それをTCのハッシュデータベースに格納するようにしました。マイミクシィ関係はそんなに激しく更新されるわけではないので、MySQLからTCへのデータの流し込みは週に1回くらいの頻度で行います。こうしておくと、TCのハッシュデータベースならば1秒に200万クエリくらい検索処理を行えるので、10000クエリくらいならオンデマンドで参照されても屁の河童なのです。

■ 非正規化のイメージ

friendnormalization.png

検索処理の手順

転置インデックスと属性データベースがあれば、検索処理の実装は簡単です。ここでは処理の主体をアプリケーション層と検索サーバに分けて考えます。
  1. アプリケーションは、ユーザがブラウザ経由で入力した検索条件を検索サーバ群へのクエリとして組み立てて送信する。
  2. 検索サーバ群は、全文検索用のキーワードをTDに渡し、転置インデックスから条件に該当する候補のIDセットを受け取る。
  3. 検索サーバ群は、IDセットの各々のIDに対して属性データベースを参照し、属性条件に該当しないものを削る。
  4. 検索サーバ群は、IDセットの各々のIDに対してスコアデータベースを参照して静的スコアを算出する。
  5. 検索サーバ群は、マイミクシィグラフ非正規化データベースを用いて操作ユーザのIDを中心としたグラフ分析による動的スコアの算出を行う。
  6. 検索サーバ群は、静的スコアと動的スコアをマージした結果の降順でIDセットを並び替える。
  7. 検索サーバ群は、IDセットを直列化してアプリケーションに返信する。

アーキテクチャ

上記の手順を複数のマシンで分散して処理できるように、システム全体のアーキテクチャを考えなければなりません。なぜ分散が必要なのかといえば、データ量が多い(しかも増大し続ける)ので1台だとパフォーマンスが追いつかないという理由と、QPSが高いのでピーク時にスループットが追いつかないという理由からです。要するに負荷が半端ないからということです。 パフォーマンスやスループットを向上させるには、各種の演算の対象データを減らすことが必要です。といっても、処理しなければならないデータの総量は決まっているので、対象データを適当な単位で分割して複数のマシンに分配したものを同時に処理させることになります。今回は、全文検索用転置インデックスと属性データベースとスコアデータベースを分散して処理させることにしました。つまり、全文検索と属性絞り込みと静的スコアリングは分散処理で行います。それらの処理を行うサーバをサーチャと呼ぶことにします。また、分散処理の結果のマージと動的スコアリングは単一のサーバで行います。これをマージャと呼ぶことにします。

■ アーキテクチャ

friendsearchdetailarch.png

サーチャの実装

サーチャのマシンは10数台です。現状ではそこまで分散させる必要はないのですが、ユーザ数が増大していくことを考えて多めに見積もっています。全文検索はTDのIndexed Database API(文字N-gram API)で行い、属性による絞り込みと静的スコアリングはmmapしたファイルやTCのデータベースを直接参照して行います。クエリ毎にファイル群のopen/closeを行うと効率が悪いので、ファイル群との接続を維持したネットワークサーバのデーモンとして実装します。プロトコルにはHTTPを用います。ネットワーク層の部分はTT(libtokyotyrantのttutil.h)を再利用することで、epollやマルチスレッド等を用いた効率的な実装になっています。

マージャの実装

マージャのマシンは2台です。1台でもよかったのですが、フェイルオーバーのためにもう1台用意しています。マージャは、アプリケーションからクエリを受け取って、マルチスレッドでサーチャ群にクエリを分配し、結果が返されるまでの間にマイミクシィグラフの分析を行い、最後に結果をマージしてアプリケーションに返します。マージャはFastCGIプログラムとして実装し、アプリケーションともサーチャともHTTPで通信します。最初はPerlでお気楽に書きたかったのですが、スレッドが安心して使えないのでCで書かざるを得ませんでした。

マイミクシィグラフの分析は、動的に行います。すなわち、予め結果を計算して保存した結果を使うのではなく、クエリが来た時に計算するということです。設計当初は予め計算することを考えたのですが、1500万ユーザの分のデータを保持するとなるとデータベースが巨大になりすぎて、ファイルアクセスによるレイテンシが致命的になりかねないので、それよりもCPUに頑張らせた方が得だと考え直しました。

一般的に、検索機能を利用する際には1回だけ検索して終わりというのではなく、平均3回くらいは連続して検索を行うようです。グラフ分析を動的に行うといっても、連続されて投げられるクエリの分は分析結果を再利用した方が得なので、グラフ分析の結果はTTのオンメモリDBにキャッシュしています。

分析の具体的な手順は以下のようになります。
  1. 自分(操作しているユーザ)のIDを、スコア100を与えて、プール(TCのオンメモリメモリデータベース)に加える。(0ホップ目)
  2. プールの各々(今は自分のみ)のマイミクシィを取得し、「そいつのスコア / 取得したマイミク数 + α」をスコアとして与えて、プールに加える。(1ホップ目)
  3. プールの各々のユーザのマイミクシィを取得し、「そいつのスコア / 取得したマイミク数 + α」をスコアとして与えて、プールに加える。(2ホップ目)
  4. プールの各々をスコアの降順でソートし、上位1000人だけ残して他は捨てる。
  5. プールの各々のユーザのマイミクシィを取得し、「そいつのスコア / 取得したマイミク数 + α」をスコアとして与えて、プールに加える。(3ホップ目)
  6. プールの各々をスコアの降順でソートし、上位3000人だけ残して他は捨てる。
プールに加えていくところでは、そのIDが既にプールにある場合は、スコアを加算します。この処理で、前述したTCの数え上げモードが活躍します(そのために数え上げモードを作りました)。手順2の時点で、「自分」と「マイミクシィ」と「マイミクシィのマイミクシィ」が、自分からの経路の太さに応じたスコアの数直線に並べられていることになります。単なるホップ数を数えているわけではなく、マイミクシィ数が多い人よりもマイミクシィ数が少ない人と繋がっている方が経路が太いとみなすモデルです。裂けるチーズを裂いていく感じと言えばわかりやすいかもしれません。ここで重要なのは、2ホップ目の処理では2ホップ目同士や1ホップ目にもスコアを再分配しているということです。こうすることで、同じ1ホップ目の中でも序列をつけることができ、手順3や手順5によって計算量を減らす際に重要な経路を切ってしまうリスクが軽減されます。

アプリケーションの実装

アプリケーション層は通常のmixiのアプリケーション群と同居させています。マージャとHTTPで通信するためにLWPを用います。ユーザから検索条件が渡されると、ユーザIDや現住所等のプロフィール情報を補完して、マージャにクエリを投げます。マージャから結果が返されたら、その各々についてニックネームや紹介文などの表示情報をmixiデータベースから取得して、HTMLとして出力します。こうして「かんたん友人検索」の簡単でない処理は完了します。

■ ユーザインターフェイス

friendsearchui.png

まとめ

かんたん友人検索の仕組みについて説明しました。全文検索機能をベースとしていながらも、周辺の機能群をいかに効率化するかに注力していることが意外だったかもしれません。正直、全文検索のエンジンがTDである必然性はなく、LuceneやHyper EstraierやSennaやを代用しても目的は達成できたと思います。ぶっちゃけ、キーワードの絞り込みに使うだけなら検索エンジンなんて何でもよかったのです。最も大変な課題は、属性による絞り込みとソートです。それらは候補の各々を対象とした演算になるので、少しでも賢いことをやろうとすると途端に計算量が跳ね上がってしまうのです。この問題をなんとか乗り切るためには、ドメインに特化した簡便法によって計算量をギリギリまで削減する手法を考案したり、DBMのような効率的なストレージを開発したり、並列化や分散処理を行ってスループットを稼いだりといった工夫を重ねるしかありません。かんたん友人検索もまだまだ改善の余地がありますが、今回の開発で得た知見をもとに、また新たなサービスを構築し改良していけたらと思っています。