関口宏司のLuceneブログ

OSS検索ライブラリのLuceneおよびそのサブプロジェクト(Solr/Tika/Mahoutなど)について
スポンサーサイト

一定期間更新がないため広告を表示しています

| スポンサードリンク | - | | - | - |
Baileyのアーキテクチャ - 今後の超大規模検索インフラの指針
会社を創業した2年半前頃はLuceneを使って数百万件オーダーの文書の全文検索機能を企業システムなどに導入するコンサルティングを行っていた(もちろん、今でも)。

ところが現在は、数千万件やそれを超える1億件、さらには十億件オーダーの文書を検索したいという依頼がある。検索側ではSolr 1.3(出る出るといっていまだ出ていないので、客先にいくたびに肩身が狭い?)がDistributed Searchをサポートするが、大量の文書のインデックスをなるべく短い時間で作成するための並列化や、多数のハードウェアの故障をあらかじめ織り込んだ運用を行うために、だんだんとHadoopが無視できなくなりつつある今日この頃だ。

SolrのMLで紹介されていたBaileyというプロジェクトは、LuceneやHadoopのコミッターのDoug Cutting氏のチェックポイント的な、今後の大規模検索のインフラのあるべき姿を彼なりに示したものであると見た。以下はその「デザイン」を解説したページの翻訳である。

例によって翻訳はいい加減なところがあるので、正確なところは原文をあたっていただきたい。

http://bailey.wiki.sourceforge.net/Architecture



デザイン

1 システム構成と機能

システムはひとつの「マスター」と複数の「ノード」、複数の「クライアント」からなります。

docidハッシュ値空間は「リング」とみなします。各「ノード」はリング上のドキュメントの「レンジ」の「インデックス」をメンテナンスします。「マスター」は各ノードとそれらがインデックスしているレンジのマッピングを管理します。

「ノード」は仮想/論理ノードを参照します。物理「ホスト」は複数のノードをホストします。

システムは以下の操作をサポートします:

  • addDoc(doc), deleteDoc(doc), updateDoc(doc)

  • search(query)



「アプリケーション」はこれらの操作を「クライアント」を通じて行います。クライアントはノードとレンジのマッピング情報を取得するためにマスターと通信します。そしてノードに対し直接addDoc(doc), deleteDoc(doc), updateDoc(doc)したりsearch(query)したりします。

2 パーティショニング

ロードバランシングのために一貫したハッシングを使うこととします。ノードXはリング上の「ポジション」にアサインされます。リング上の「次」のノード/ポジションはX+1です。ノードXのレンジは[X, X+1)です。

これはレンジパーティショニングに似ています。

3 レプリケーション

耐障害性対策のためにレプリケーションを行います。N-wayレプリケーションとはデータをN個のノードに保存/インデクシングすることを意味します。N=3の場合、ノードXのレンジは[X, X+3)です。レンジ[X, X+1)はノードXに加えてノードX-2とノードX-1をサービスします。

4 search(query)

ノードとレンジのマッピングに基づき、クライアントは検索リクエストを複数のノードに送ります。クライアントはリクエストを送る各ノードに検索レンジを指定することで次を行います:
(1)ノードのための検索レンジはそのノードがカバーしているレンジ
(2)検索レンジは統合的にリングをただ一度だけカバーします
(3)リクエストを送るノード数をなるべく少なくします

たとえば、7個のノードで3-wayレプリケーションの場合、検索リクエストはノードXに検索レンジ[X, X+3)で、ノードX+3に検索レンジ[X+3, X+6)で送られます。またノードX+6では検索レンジは[X+6, X+7)ですが、X+7 == Xです。

再検索の待ち時間を避けるための代替案はリングをR回(たとえばR=2)カバーすることです。

5 addDoc(doc)/deleteDoc(doc)/updateDoc(doc)

ドキュメントの追加、削除、更新はアプリケーションが指定したドキュメントのリビジョン番号が付加されるものとします。そうしないとベクタークロックなどのより複雑なオペレーションを行わなければなりません。

各ノードは定期的に(定期的にのみ)ディスクにフラッシュされる軽量なログをメンテナンスします。ログはログエントリのシーケンスです。各ログエントリは<{ADD|DEL}, docid, revision>です。

更新リクエストは複数のノードに送られ、送られた全レンジはドキュメントを含んでいなければなりません。

ノードがリビジョンRのドキュメントの更新リクエストを受け取った場合、リビジョンRがノードに保存/インデクシングされているリボジョンと比較して新しいことを確認します。そしてノードはその新しいリビジョンをメモリに保存およびインデクシングしてログにログエントリを書き込みます。

W-way更新ではその更新が「完了」したとみなせるためには、少なくともW個のノードが更新リクエストを成功させる必要があります。ここでWは1 < W <= Nです。W > 1とは更新オペレーションに耐障害性を持たせることを意味します。

6 一貫性

各ノードはログ伝播ともいわれるレンジのオーバラッピングにおけるノード間でシンクします。しかしほとんどのケースでW+R <= Nなので、システムは結果として一貫性を具備します。

ノードは、更新リクエストのためのリビジョンが現在ノード上に保存/インデクシングされているリビジョンよりも新しいことをチェックしますので、単調な更新一貫性をサポートします。

クライアントの実装はセッションの一貫性をサポートしなければなりません。またread-your-writesと単調なリード一貫性をサポートするといい感じです。

ログ伝播について。ノードXはレンジ[X, X+3)をサービスし、以下の定期シンクを行います:
range [X, X+1) with node X-2
range [X, X+2) with node X-1
range [X+1, X+3) with node X+1
range [X+2, X+3) with node X+2

以下はノードX上のレンジ[X, X+1)の更新がどのようにノードX-2に伝播されるかを説明しています。最後のシンクの間、ノードX上のログエントリEの更新はノードX-2に伝播され、ノードX上の現在のログエントリはFであるとします。

  • ログエントリ(E, F]がシーケンシャルにスキャンされ、レンジ[X, X+1)にあるものがノードX-2に送られます。

  • ノードX-2はノードXから受信したログエントリをチェックします。ログエントリ<{ADD|DEL}, docid, revision>において、もしノードX-2の現在のリビジョンが古い場合は、ノードX-2は当該docidをリクエストリストにプットします。そしてノードX-2はdocidのリクエストリストをノードXに送信します。

  • ノードXはリクエストリスト上のドキュメントの保存コピーをノードX-2に出荷します。

  • ノードXからドキュメントを受信すると、ノードX-2はそれを通常の更新リクエストとして処理します。つまりノードX-2は単調な更新一貫性を確認するためにリビジョンを再度チェックしてログします。



7 ノードの追加/ノードの削除

新しいノードが追加されると、新しいポジションがアサインされます。新しいX'がXとX+1の間のポジションX'にアサインされると仮定しましょう。

隣接ノードが影響を受け以下から:
node X-2 serves range [X-2, X+1)
node X-1 serves range [X-1, X+2)
node X serves range [X, X+3)
以下のようにスイッチします:
node X-2 serves range [X-2, X')
node X-1 serves range [X-1, X+1)
node X serves range [X, X+2)
node X' serves range [X', X+3)

ノードX'は1つ以上の隣接ノードからインデックスファイルをコピーすることによりレンジ[X', X+3)を用意します。そしてノードX'はレンジオーバラッピングにおけるノードのシンクを開始します。

実行中のノー・ライトあるいは更新伝播の喪失を保証するために、2-フェーズコミット風なことが行われます。
| 関口宏司 | 超大規模検索 | 15:00 | comments(0) | trackbacks(0) |
IndexReaderを読み込み専用で開く(2.4)
今やIndexWriterを使ってドキュメントの削除ができるようになった。以前はドキュメントの削除はIndexReaderを使ってやる仕事であった(関連記事)。

もしIndexReaderを使っての削除やNormの設定(IndexReader.setNorm())を行わないことがわかっている場合は、Lucene 2.4(現trunk)から追加された新しいopen()メソッドにreadOnly=trueを設定してIndexReaderを取得すると良いだろう。こうすることでマルチスレッドの検索プログラムにおいて、検索スピードをこれまでよりも向上させられる。

open()メソッドにreadOnly=trueを設定してIndexReaderを取得するとIndexReaderのサブクラスであるSegmentReaderの代わりにReadOnlySegmentReaderが使われるようになり、(SegmentReaderではついている)synchronizedがisDeleted(docId)メソッドからはずれるようになる。isDeleted(docId)はdocIdで示されたドキュメントが削除済みか否かを検査するもので検索のあらゆる場面(特にFunctionQueryとMatchAllDocsQuery)で呼び出されるメソッドである。マルチスレッドでIndexReaderを使用している環境では、ドキュメントの削除フラグを管理しているテーブルをsynchronizedブロックの中で検査する必要があるが、IndexReaderがreadOnly=trueであることがわかっていれば、その管理テーブルは変更されることはありえないのでsynchronizedは不要となるのだ。

2.4ではreadOnly=falseがデフォルトである。もしIndexReaderを読み込み専用で使うことがわかっている場合は、readOnly=trueを明示してopen()するとisDeleted()がsynchronizedされなくなり、マルチスレッドの検索性能が向上するのでぜひ覚えておくといいだろう。
| 関口宏司 | Luceneクラス解説 | 23:59 | comments(0) | trackbacks(0) |
Lucene in Action (2nd EDITION)
ManningのWebサイトによると、"Lucene in Action, SECOND EDITION"(LIA2)は来年3月出版予定らしい:

Lucene in Action, SECOND EDITION
http://www.manning.com/hatcher3/


そういえば先日、共著者のひとりであるOtisがLIA2に掲載するLucene事例をメーリングリストで募集していた:

Case studies for Lucene in Action 2nd edition

出版予定までまだまだ半年以上なので執筆真っ最中だと思われるが、早くもその第1章がManningのサイトで公開されている(参照するには、上記最初のURLに飛び、「Table of Contents」のChapter-1「Meet Lucene」をクリック)。
| 関口宏司 | Luceneとは? | 02:20 | comments(0) | trackbacks(0) |
フィールド名の一覧を得る(初心者向き)
Luceneのインデックスには、さまざまなFieldを持った多様なDocumentを登録することができる。そのFieldもいろいろな属性を持たせることができる。たとえば、次のプログラムはひとつのインデックスにperson、book、shopといったそれぞれ異なるFieldを持つDocumentを登録している:



static void makeIndex() throws IOException {
IndexWriter writer = new IndexWriter( dir, analyzer, MaxFieldLength.LIMITED );
writer.addDocument( person() );
writer.addDocument( book() );
writer.addDocument( shop() );
writer.close();
}

static Document person(){
Document doc = new Document();
doc.add( new Field( "id", "ABC456", Store.YES, Index.UN_TOKENIZED ) );
doc.add( new Field( "name", "John Smith", Store.YES, Index.TOKENIZED ) );
doc.add( new Field( "age", "45", Store.YES, Index.NO ) );
return doc;
}

static Document book(){
Document doc = new Document();
doc.add( new Field( "id", "BK-6", Store.YES, Index.NO ) );
doc.add( new Field( "title", "Lucene in Action", Store.YES, Index.TOKENIZED ) );
doc.add( new Field( "author", "Erik Hatcher", Store.YES, Index.TOKENIZED ) );
doc.add( new Field( "author", "Otis Gospondnetic", Store.YES, Index.TOKENIZED ) );
return doc;
}

static Document shop(){
Document doc = new Document();
doc.add( new Field( "shopid", "FLWR51", Store.YES, Index.UN_TOKENIZED ) );
doc.add( new Field( "name", "Uncle Peter Flower Shop", Store.YES, Index.TOKENIZED ) );
doc.add( new Field( "phone", "455-9811", Store.YES, Index.NO ) );
return doc;
}



Fieldにはフィールド名がつけられているが、面白いのは、同じフィールド名のFieldでも異なるFieldの属性がつけられることだ。たとえば上の例で言えばpersonのidフィールドは索引付けする(INDEX.UN_TOKENIZED)のに対し、bookのidフィールドは索引付けしない(INDEX.NO)と定義されている。

ところで、このように自由に定義・登録されたフィールド名の一覧はどのように取得できるのだろう。このような目的にIndexReaderのgetFieldNames()が使用できる。このメソッドの引数にはFieldOptionを渡し、取得したいFieldの属性を指定する:



static void printFieldNames() throws IOException {
IndexReader reader = IndexReader.open( dir );
System.out.println( "===== FieldOption.ALL =====" );
printFieldNames( reader.getFieldNames( FieldOption.ALL ) );
System.out.println( "===== FieldOption.INDEXED =====" );
printFieldNames( reader.getFieldNames( FieldOption.INDEXED ) );
System.out.println( "===== FieldOption.UNINDEXED =====" );
printFieldNames( reader.getFieldNames( FieldOption.UNINDEXED ) );
reader.close();
}

static void printFieldNames( Collection fields ){
for( Iterator i = fields.iterator(); i.hasNext(); ){
String field = (String)i.next();
System.out.println( field );
}
}



この実行結果は、次のようになる:



===== FieldOption.ALL =====
id
author
phone
shopid
title
age
name
===== FieldOption.INDEXED =====
id
author
shopid
title
name
===== FieldOption.UNINDEXED =====
phone
age


| 関口宏司 | Luceneクラス解説 | 13:31 | comments(0) | trackbacks(0) |
(小ネタ) EnglishNumberFilter
数字の"1"を"one"に、"11"を"eleven"に変換出力するEnglishNumberFilterが提案された(Solrで)。日本語なら"1"を「一」、"11"を「十一」とするようなものか:

https://issues.apache.org/jira/browse/SOLR-690

するとすかさず、"1st"、"2nd"を"first"、"second"とできるといいね、とコメントがついた。日本語なら「ひい」「ふう」「みい」?

| 関口宏司 | Luceneクラス解説 | 01:48 | comments(0) | trackbacks(0) |
Solrロゴ・・・
すったもんだの挙句、Solrロゴへの投票はお流れになり、ロゴデザインを再募集しようか、ということになった。なお、Solr 1.3のリリース時には新しいロゴは必要ない、という確認がメーリングリストでとられており、Solr 1.3リリース準備は粛々とすすめられる模様。

Solrロゴコンテスト
http://wiki.apache.org/solr/LogoContest
| 関口宏司 | その他(分類不能) | 10:16 | comments(0) | trackbacks(0) |
「特徴語検索」(MoreLikeThis)の応用例
以前説明した「特徴語検索」(MoreLikeThis)を使用したEコマースサイトがSolrメーリングリストで紹介されていたので、ここでも紹介しよう:

http://www.vanns.com/

このサイトで商品を選ぶと、「その他のおすすめ商品」が右側に表示される。これはユーザが選択した商品と特徴が似ている他の商品を検索・表示するもので、MoreLikeThisを使用している。次のような感じである:



おすすめ商品一覧 = searcher.search( MoreLikeThis.like( ユーザが選んだ商品 ) );



検索エンジンはこのように、結構いろいろなところ(機能)で使われていたりするので、面白い。
| 関口宏司 | Luceneデモ | 13:17 | comments(0) | trackbacks(0) |
祝!2008年8月8日
は100年に一度のロンウイットの日、と書こうと思いつき、念のため(何が念のためだ?)「丸八 8月8日」で検索したらやはり「丸八」が社名につく会社が同じことを言っていた。

・・・なので恥ずかしいからやめようと思ったが、せっかく100年に一度だから書いてしまった。
| 関口宏司 | その他(分類不能) | 17:34 | comments(0) | trackbacks(0) |
(警告)Lucene 2.4でFieldableインタフェース変更の可能性
前回紹介したTFを省略できるようにする改善などに絡み、FieldableインタフェースがLucene 2.4以降で変わる可能性が出てきた。Fieldableが具体的にLucene 2.4から変わるのか不明だが、少なくともLucene 2.4で「Fieldableインタフェースは将来的にメソッド追加などの変更可能性がある」旨注意喚起されることはほぼ決まりのようだ:

https://issues.apache.org/jira/browse/LUCENE-1349

Fieldableは抽象クラスではなくインタフェースであるため、メソッドなどを追加してしまうと後方互換性が損なわれる。そのためこれに先立ってはメーリングリストで投票が行われた。私もこのブログで書こうかと思ったが、忙しいのとまさかFieldableをimplementsしている人はいなかろう、と思ったので書かなかった。

案の定、メーリングリストでも賛成票以外の票はなく、Fieldableに関しては例外的に後方互換性の契約を破って、その代わりJavadocやCHANGES.txtで注意喚起しよう、ということになった次第である。
| 関口宏司 | Luceneクラス解説 | 13:00 | comments(0) | trackbacks(0) |
+ Solrによるブログ内検索
+ PROFILE
     12
3456789
10111213141516
17181920212223
24252627282930
31      
<< August 2008 >>
+ LINKS
検索エンジン製品 - 比較のポイント
商用検索エンジンを購入した企業担当者は読まないでください。ショックを受けますから・・・
>>製品比較 10のポイント
+ Lucene&Solrデモ
+ ThinkIT記事
+ RECOMMEND
Apache Solr入門 ―オープンソース全文検索エンジン
Apache Solr入門 ―オープンソース全文検索エンジン (JUGEMレビュー »)
関口 宏司,三部 靖夫,武田 光平,中野 猛,大谷 純
+ RECOMMEND
Lucene in Action
Lucene in Action (JUGEMレビュー »)
Erik Hatcher,Otis Gospodnetic,Mike McCandless
FastVectorHighlighterについて解説記事を寄稿しました。
+ RECOMMEND
+ SELECTED ENTRIES
+ RECENT COMMENTS
+ RECENT TRACKBACK
+ CATEGORIES
+ ARCHIVES
+ MOBILE
qrcode
+ SPONSORED LINKS