Sedue - Distributed Full Text Search System

夏休みの前半は某携帯用アプリ、夏休みの後半はSedueという全文検索システムを作っていました。このエントリではSedueの分散機構について書ける範囲で書いてみたいと思います。

Sedueの概要についてはnvacaさんのエントリを見て頂く事にして、ここではSedueの分散機構について書きます。図を見ながら呼んで頂けると分かり易いかと思います。
まず、Sedueではマシン一台ごとにAdminDaemonというサーバーが立っています。AdminDaemonはそのマシン内で立っているサービス(SearchServer, QueryServer)を常時監視する役割を持っています。具体的には一定間隔毎にpingを打ち、閾値以上の間pingが帰ってこなかったらサービスをkillして新しいサービスを立てるという事をします。この仕組みによってサービスのAvailabilityを上げています。
次にこのAdminDaemonもAdminServerという別のサーバーによって常に監視されています。こちらも同じようにServerがDaemonにpingを打ち、Daemonの生存を常に確認しています。
ではAdminServerはどうやって冗長化しているかというと、2つのAdminServerを立てて常に通信を行い、お互いを監視しあいます。これによりもし片方のServerが死んだとしても、もう片方のサーバーがMasterとなって処理を行う事が出来ます。
基本的に全てのサーバーはマルチスレッド化されています。サーバーの設定時等はリクエストを受け付けないようにCounting Semaphoreを使用して特権モードに入らせたりしています。また、高負荷時にもpingを返せるように、Starvation Free Semaphoreの仕組みを併用しています。
さらにAdminServer, AdminDaemonはforwardingも行います。つまり、AdminServerに送ったコマンドをAdminDaemonに伝え、さらに各サービスにコマンドを送る事が出来ます。これによりAdminサーバーと通信をする事だけで各サービスの設定・開始・終了等を行うことが出来ます。この機構を利用してSedueシステム全体を自動設定するツールも有ります。
基本的にSedueのインデックスはメモリに載せるのですが、複数台のサーチサーバーがある場合(特にメモリ容量が個々に違う場合)にはどのようにこのインデックスを割り振るかというのは面白い問題になります。この自動設定ツールではその辺りの問題も2部グラフのマッチングを用いて適切にインデックスを割り当てています。ICPCのメンバーが多いのでこの辺りは凄く勉強になります。まさか実用アプリでグラフがどうとかやるとは…。ここまでが冗長化の仕組みです。

次はScalabilityを上げる仕組みです。これは構成そのものなのですが、とにかく今はSearchServerを並べてScalabilityを確保するという方式を取っています。クエリを発行されたQueryServerはSearchServerの台数分だけスレッドを作り、それぞれのSearchServerに分散してクエリーを投げます。そしてその結果を上手くマージし、ユーザーに返します。
これは大体～数十台ぐらいのシステムでは上手く動くのですが、もっと増えるとスレッド生成のコストがばかにならない可能性があります。そこまでのクラスタを持っていないのでちょっと実験できないのですが、Google並のスケールにするにはQueryServerもツリー構造に構成してスレッド生成数を減らす等の対策を取る必要が有ると思います。まぁただメモリ8G積んで十台並べれば80Gのインデックスを置ける(Wikipedia * 10個分ぐらい)訳なので、中規模サイトのバックエンドなどでは十分だと思います。ただweb規模にスケールするには全てをメモリに載せる訳にも行かないので、diskも併用するような技術を開発中です。
この仕組みがかなり上手く行って高速に検索する事が可能なった結果、今度はなんとRubyで書いたCGIがボトルネックになってしまいました。そこで出てきたのがC / C++でCGIを書く技術です。そちらはoxyたんに任せます。
さらにロードバランシングの仕組みも有るのですが、疲れたので今度書く事にします。単体でのベンチマークも有るのですが、こういう分散的な面でもかなり頑張ってますよというエントリでした。近い内にデモサイトを設置する予定です。
しかし僕らにはプログラミング技術しかないので、ちょっと営業の技術も学んで行かないとなぁ…というのが最近の悩みだったり。後はなんか単に検索するだけじゃ面白くないので、もっと色々やれないかなとか日夜議論しています。

Similar Posts:

• cloudkickでAmazon EC2のインスタンスを手軽に監視
• Baidu.comの検索サーバーはSSD
• GenomeSedue