【Google App Engine】 頑張って全文検索

TaskQueueを使った全文検索


　非同期処理、並列処理はPDF生成に限った話ではない。これを応用して全文検索も考えることができる。例えば、下図のように、データを分割して複数のTaskで並行処理することで、検索にかかる時間を短縮することができる。これまで説明してきたように、Datastoreでは、前方一致検索はできるが全文検索はできない。もしこれで全文検索が可能になるのであれば嬉しいことである。Indexを使わずに全件検索するなんて無謀のように思えるかもしれない。でもこれこそがクラウドの醍醐味なのだ。



　実装は下図のような感じになる。商品マスタ※検索では、商品名、基本説明、詳細説明を全件検索して、部分的にでもヒットしたら結果を返すようにした。（※ 今ECを作っているので、このBlogでは唐突に商品マスタなどの単語が現れる）　
　

• 検索項目
  
  • 商品名
    
  • 基本説明
    
  • 詳細説明
    
• URLパラメータ
  
  • fulltext : 全文検索する正規表現
  • 例えば「コーヒー」という文字列を検索条件とする場合、以下のように指定する必要あり
    .*コーヒー.*
  • pagesize : １レスポンスで返される最大件数（デフォルト100）
    
  • next : 次の行番号。先頭から何番目かを指定する。
    
    • 数値を指定すると、その値からpagesize件数を返す。
      
    • 「101-200」のように、範囲指定も可能。これが指定されているとpagesizeは無視
      
    • nextパラメータが指定されている場合、検索を行わずMemcacheをチェックする。要するに2回目以降（場合によってTaskQueueへの追加登録を行う。）
      
  • taskunit : １タスクで処理される件数（デフォルト500）
    
  • queueadd : １度に登録されるタスクの数（デフォルト4）
    
    • tasknoをmemcacheで管理しているので各taskは、（taskno-1)*taskunit+1 ～ taskunit分を処理することになる

実行結果

• データを10000件登録してテスト。
  
  • 2000件だと、重すぎてエラーになる場合が多い。
    以下のメッセージが返される。サーバ側にログは出力されていない。
    

    ---

    Error: Server Error
    The server encountered an error and could not complete your request.
    　
    If the problem persists, please report your problem and mention this error message and the query that caused it.
    

    ---

  • TaskQueueに4件処理が登録されるが、以下のWarningログが大量に出力され、いつまでたっても処理が終わらない。
    

    ---

    Request was aborted after waiting too long to attempt to service your request. Most likely, this indicates that you have reached your simultaneous active request limit. This is almost always due to excessively high latency in your app. Please see http://code.google.com/appengine/docs/quotas.html for more details.
    

    ---

  • 1000件でも同様。
    
  • 1タスク500件、一度に4タスク登録。（合計20タスク）
    
    • 全データ検索まで : 1分25秒
      
    • 1タスクの処理時間 : 5～7秒
      
    • 最初に1回タスクが最初に実行される前に"Request was aborted after waiting too long ..."のWarningログが1件出力された。
      その後は順調に処理された。
      
  • 一度に2タスク登録。
    
    • 全データ検索まで : 1分34秒
      
    • "Request was aborted after waiting too long ..."のWarningログは出力されなかった。
      
  • 一度に6タスク登録。
    
    • 全データ検索まで : 1分30秒
      
    • 最初に1回タスクが最初に実行される前に"Request was aborted after waiting too long ..."のWarningログが3件出力された。
      その後は順調に処理された。
      
  • 一度に8タスク登録。
    
    • 全データ検索まで : 1分47秒
      
    • 1タスクの処理時間 : 6～7秒
      
    • 1回目と2回目に登録したタスクが最初に実行される前に"Request was aborted after waiting too long ..."のWarningログが3件出力された。
      （最後の3回目はタスクの登録件数が3件なので出力されなかったと推測される。）
      
  • タスク登録なし
    -> 本来レスポンスを受けたインスタンスが全文検索を行うのは最初の1回のみなので、とりあえずテスト用に、最初に件数取得リクエスト。それからデータストアから500件検索してインメモリでPattern-Matcherチェック。これを開始データを500件ずらして20回行う。
    
    • 全データ検索まで : 6分4秒
      
    • 1リクエストの処理時間 : 6～7秒
      
    • レスポンスを1回+20回投げたうち、5回以下のエラー発生。
      サーバにログは出力されていない。リクエストをはじかれている感じ。
      

      ---

      java.io.IOException: Server returned HTTP response code: 500 for URL:
      

      ---

      
      
• 1タスク1000件時のエラーについて
  
  • 最初のリクエストから10分経過した時点で、登録された4件のタスクは残ったまま。
    
  • それぞれのタスクはリトライを12回しているようである。（TaskQueueのRetries = 12）
    
  • ログには"Request was aborted after waiting too long ..."のWarningログが大量に出力されているが、タスクのServletに記述した開始ログが出力されていない。
    -> "Request was aborted ..."の場合、処理がロールバックされてログも出力されない？？

　ちなみに、1回目の実行時（Coldstart時）はすぐに完了するようにすることで、"Request was aborted after waiting too long ..."のWarningログが出ないようにすることができる。そうすることで約30秒実行時間を短縮できるが、それでも同時実行インスタンスは４つ以上にならないようである。その様子は、前記事に書いたとおり。

Relation Indexによる全文検索


　TaskQueueを使った全文検索では、1万件のデータで1分40秒かかるため、とても実用的とはいえない。それから、商品名で検索して安い順で表示させたいことはよくあるが、「安い順」という新たな条件が追加されることで、もうお手上げになる。「安い順」であれば、価格に対してaddSort条件を追加してやればいいのだが、そうすると、ID順の時のように、件数で区切ってTaskQueueに登録することができなくなってしまうのだ。ムリクリやるなら、最初のページの最後のレコードを、次ページの開始点（greater than）とすればよいが、いずれにしても最初ページを検索しないと次ページも検索できないことになってしまう。これでは並列処理はできない。

Like＋「安い順」検索　データを10000件登録してテスト
1タスク500件、一度に4タスク登録。（合計20タスク）

• 全データ検索まで : 1分36秒
  
• 1タスクの処理時間 : 6～11秒
  
• "Request was aborted after waiting too long ..."のWarningログは出力されなかった。
  
• ほかに待っているタスクが無いせいか、タスクを登録したらすぐに実行されているように見える。
  
  • (登録元タスクの終了前に、登録先タスクが開始されているので)
    
• インスタンスの起動状況が安定してくると、４タスクがほぼ同時に実行される箇所も出てきた。
  taskno=10～13、14～17)
  
  • データストアの検索には短くて0.06秒くらいしかかかっていない。その後のPattern-Matcherに時間がかかっているよう。

　そもそも、無尽蔵にTaskを起動して並行処理させようなんて発想自体が無謀である。クラウドにはCPU資源が潤沢にあるとはいえ、今はエコが当然とされる時代なのである。ということで、Brett Slatkinさんがいっている、関連Index（Relation Index 資料のP23-P25)を実装することで解決しようと思う。

• Relation Index Solution
  
  • Do a key-only query to fetch the MessageIndexes
    
    • MessageIndexをKey（word）で検索する
      
  • Transform returned keys to retrieve parent entity
    
    • 検索結果のKeysを取得
      
  • Fetch Message entities in batch
    
    • Keysからまとめてメッセージを取得
      
• 具体的な設計
  
  • ProductのRelation IndexをProductIndexとする。
    
  • 1つのwordにつき、すべてのSuffix ArrayをProductIndexに登録する（下図の例だと11個）
    
  • 文をスペースで区切ったTokenをWordとする
    
  • 登録するもの
    
    • Key（wordのSuffix Array）、Value（位置情報のList）
      
  • 位置情報のList
    
    • ProductのKey(shop_code+product_code+revision)#項目名
      

      ---

      （property name）,位置（offset）
      例） key#product_name,5
      コーヒー,「アメリカンコーヒー」
      

      ---

　また、これは、Brett Slatkinさんのものと異なり、EntityGroupを構成しない。その理由はパフォーマンスに大きく影響するからである。若干の時間差があったとしても、以下のように非同期にIndexを作成する方がよい気がしている。スケーラビリティを確保するためには、あまり神経質にならない方がいいことは、この記事でも述べたとおり。



考慮点

• IndexはKey検索である（直接Wordを指定しての検索） 前方一致検索である。このため、Entityの方にも、Suffix Arrayの値もつことにする。（重複を避けるため、KeyにSuffix Arrayの文字列を代入することはする）
  
• 商品削除時はIndexも削除する
  
• Suffix Arrayが可能な最大文字数
  
  • 1000文字未満とする（なぜなら1000行は一度にPUT（KEYS）できる限界だから）
    
  • Productの商品名（Product＿name）および、基本説明（Summary１）について、全文検索できるようにする。
    
  • １WORDは20文字程度が望ましいかも
    
    • 20文字＊50個の登録で1000行

＜追記＞
Suffix Arrayから任意の文字を検索するには、前方一致検索をしないとダメ。

• 例えば、「アメリカンコーヒー」という商品のSuffix Arrayは
  
  1. アメリカンコーヒー
     
  2. メリカンコーヒー
     
  3. リカンコーヒー
     
  4. カンコーヒー
     
  5. ンコーヒー
     
  6. コーヒー
     
  7. ーヒー
     
  8. ヒー
     
  9. ー
     
• となる。
  ここで「コーヒー」という単語で検索すると、6番目の値と合致するが、もし「アメリカン」という単語で検索すると、key検索では一致しない。前方一致検索をすれば、1番目の値と合致する。