Redisで簡単Inverted Index

WebPayはRailsを利用して構築しています。 今回はRailsアプリケーションでちょっと手間取る検索の高速化のTipsを紹介します。

最近のRailsアプリケーションでは、整合性が要求される基本的なデータにRDBMSを、揮発性の高いデータに高速なNoSQLを利用するパターンが一般的です。 WebPayではMySQLとRedisでこのような構成をとっています。 Redisは使い勝手がよく、高速で、データをディスクに保持することができるので、KVS系のNoSQL製品のなかでは一番汎用的に利用できる印象があります。

さて、Railsではserializeを指定して変化しがちなデータ形式をJSON等のシリアライズ形式でRDBにストアすることがあります。 メタデータなど、雑多な入力が予期されるデータには非常に便利ですが、シリアライズされたフィールドを検索しにくいという欠点があります。 PostgreSQLなど、JSONデータ型をデータベースシステムレベルでサポートしている製品もあります MySQLでも5.7からuser defined functionsの仕組みが追加され、JSON UDFを利用することでデータベースシステム上でJSON演算を行うことができるようになるそうです。 しかし、いまアプリケーションを構築している環境で動作するとはかぎりません。 たとえばWebPayではリリース前のMySQL 5.7を利用することはできません。

このような場合の正攻法は、検索用の別ソリューションを投入することです。 よく知られているのはelasticsearchなど全文検索エンジンを導入し、シリアライズされたデータのなかの、検索対象にしたいフィールドを全文検索エンジンにインデクシングする方法です。 書籍『SQLアンチパターン』(Bill Karwin著)でもRDBMSを検索目的で利用する「プアマンズ・サーチエンジン」アンチパターンに対する解決策として挙げられていました。 しかし、すでに稼動している環境に新たなミドルウェアを持ち込むのが憚られる場合は多々あります。 全文検索エンジンは非常にパワフルですが、名前の一部をキーワード検索したいような場合には少々オーバースペックに感じます。

そこで、KVSを使ってシンプルな転置インデックスを構築する方法を検討します。 大抵すでにキャッシュ目的などでKVSを導入しているでしょうし、KVSは仕組みが簡単なので、コーディングもわずかで済みます。 今回はRedisを例にしますが、他のKVS製品でもすこし工夫することで実現可能だと思います。

問題設定

上述のように、名前の一部をキーワード検索するような問題を考えます。 説明で具体的な単語が使えるように、次のような例をつくりました。

  • 写真を管理するサービスで、写真には複数のタグをつけられる
  • タグは自由入力(候補から選択する方法ではない)
  • タグが部分一致する写真を検索する機能を提供したい

次のようなデータを例に説明していきます。

1
2
3
4
5
6
photo id:1
      tag: クリスマスパーティー, 七面鳥
photo id:2
      tag: クリスマスツリー, 原宿
photo id:3
      tag: 初詣, 明治神宮, 原宿

ここで「クリスマス」で検索すると写真1,2が表示されるようにしたいです。

データ構造を考える

まず転置インデックスについて理解しましょう。 転置インデックスとは、あるワードがどのドキュメントのどの場所に出現するかを判別するデータ構造です。 今回の場合はタグ名から写真idへの対応づけになります。

1
2
3
4
5
6
7
クリスマスパーティ → 1
七面鳥 → 1
クリスマスツリー → 2
原宿 → 2
初詣 → 3
明治神宮 → 3
原宿 → 3

Redisで転置インデックスを実現するために、今回はhashを使います。 Redisは単なるKVSではなく、組み込みでvalueとしてHash, Array, Setなど典型的なデータ構造を持てるようになっています。 Hashもkey-value構造ですが、RedisではRedisのkeyをkeyと呼ぶので、hashのkeyのことはfieldと呼びます。

Redisのfieldは単一の値しか持てないので、上の例では「原宿」が2回でてきており、そのまま格納することはできません。 そこでvalueはidの一覧をカンマ区切りで持つことにします。

次のコマンドでRedisにデータを投入します。 HMSETは複数のfield-value pairをhashに格納するコマンドです。 説明が長くならないよう改行をいれていますが、redis-cliには行継続はありません。一行になおして入力してください。

1
2
3
4
5
6
7
HMSET photo_tag_inverted_index
    "クリスマスパーティ" "1"
    "七面鳥" "1"
    "クリスマスツリー" "2"
    "原宿" "2,3"
    "初詣" "3"
    "明治神宮" "3"

KVSによってはアトミックな文字列の追加をサポートしており、純粋なカンマ区切りより1,2,3,のように最後に余計な,をつけるスタイルのほうが扱いやすいかもしれません。

さて、ここから「クリスマス」を含むものを探索するにはどうすればいいでしょうか。 完全一致ではないので、HGETだけではいけません。 「クリスマス」タグのついた写真はないので、結果が0件になります。

そこでHSCANを利用します。fieldを走査し、パターンに当てはまるエントリを返します。

1
2
3
4
5
6
127.0.0.1:6379> HSCAN photo_tag_inverted_index 0 MATCH *クリスマス*
1) "0"
2) 1) "クリスマスパーティー"
   2) "1"
   3) "クリスマスツリー"
   4) "2"

redis-cliから実行すると文字がエンコーディングされて表示されているかもしれません。 この結果は次のような構造になっています。

1
2
3
4
5
6
7
[
  次のカーソル,
  [
    ヒットしたfield1, field1のvalue,
    ヒットしたfield2, field2のvalue, ...
  ]
]

次に、Rubyで検索処理を実装します。

別解として、はじめにタグをn-gramに分解し、それぞれをストアする方法があります。 検索や自然言語処理に慣れ親しんだ方はこちらの方法のほうがスマートに感じるでしょう。 より高度な検索条件が指定できますし、検索ワードの揺れにも多少ロバストになります。 処理のうえでも、HSCANではなくHMGETを利用できるので、検索語の含まれるn-gram数に線形な時間になります。

しかし、今回の記事のもとになったケースでは、SQLのLIKEで十分でした。 n-gramが適切な検索結果を出すために必要な場面ではありませんでした。

Redis自体の動作が高速なのでタグエントリ数が少ないうちは速度の差はそれほどありません。 むしろRubyでのn-gram処理のほうがオーバーヘッドになる可能性もあります。 ためしに20,000件のハッシュを作成して手元のマシンでテストしましたが、Rubyでの処理をふくめて数十msで終了します。 20,000件を十分な数とみるか全然たりないとみるかはアプリケーションによりますが、今回のケースでは十分でした。

今回はできるだけ簡単にシンプルな検索がしたかったので、名前をそのままfieldにする安直な方法をとりました。

Rubyによる実装

実装は3つの部分に分けられます。

  • インデックスを管理し、追加、検索するクラス
  • RDBMS上のデータに応じてインデックスを更新する処理
  • 検索処理

Redisとの通信はredis gemを使います。 まず最初のクラスをつくります。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
require 'redis'

class PhotoTagInvertedIndex
  # データ構造を変更する場合に備えて、バージョン番号をつける
  REDIS_KEY = photo_tag_inverted_index_v1'

  def initialize
    # 必要なら接続先を設定
    @redis = Redis.new()
  end

  # Find photos that include query in the tags
  # http://redis.io/commands/scan
  #
  # @param query [String] search query, a part of tag
  # @return [Array<Integer>] photo ids
  def search(query)
    found = []
    # cursor を利用して一回のパケットが大きくなりすぎないようにする
    # count は大きめにとり、通常1回でおわるようにしてある
    # サーバが 0 を返したら全件見たことになる
    # cursor の返り値は string であることに注意
    next_cursor = 0
    begin
      next_cursor_resp, resp = @redis.hscan(REDIS_KEY, next_cursor, 'MATCH', '*%s*' % query, 'COUNT', 10_000)
      next_cursor = next_cursor_resp.to_i
      resp.each_slice(2) { |pair| found += decode(pair[1]) }
    end while next_cursor > 0
    found.uniq
  end

  # Add indices
  #
  # @param photo_id [Integer]
  # @param tags [String]
  def add(photo_id, *tags)
    tags.select { |n| n != nil && n != '' }.each do |tag|
      # WARNING: not atomic
      # 複数のインスタンスが同時に操作するとデータがこわれる
      ids = decode(@redis.hget(REDIS_KEY, tag))
      ids << photo_id
      @redis.hset(REDIS_KEY, tag, ids.uniq.join(','))
    end
  end

  private
  def decode(value)
    (value || '').split(',').map(&:to_i)
  end

  def encode(ids)
    ids.join(',')
  end
end

redis-cliからやっていたことを単純にRubyのコードに変換しただけです。 いくつか注意点にコメントを入れました。

つぎに、タグを保存したときにインデックスを更新します。 タグは"photo has many tags"という形でTagモデルが管理しているものとします。

1
2
3
4
5
6
7
8
9
class Tag < ActiveRecord::Base
  belongs_to :photo
  after_save :update_index

  private
  def update_index
    PhotoTagInvertedIndex.new.add(photo.id, self.name)
  end
end

最後に検索です。おそらくcontrollerのactionの中に実装することになるでしょう。 Railsを普段使っている方なら説明の必要はないでしょうが、コードも添えておきます。

1
2
# params[:query]に検索語(クリスマス)が入っている
@photos = Photo.find(PhotoTagInvertedIndex.new.search(params[:query]))

ほとんどPhotoTagInvertedIndexクラスだけで完結しており、その実装も簡単です。 全文検索エンジンの新たなコマンドを覚えたり、サーバをセットアップする必要はありません。

おわりに

ここではRedis, Ruby, Railsの例を紹介しましたが、他のプロダクトを利用してもまったく同じ考え方で簡単な転置インデックスを作れます。 この記事のコードは自由に利用できますが、説明に利用する場合は出典を記載していただけると嬉しいです。

最後に、この記事でやりきれなかった項目をいくつかとりあげ、読者の方への課題としてみます。 ぜひTwitterなどでフィードバックをください。

  • PhotoTagInvertedIndexのテストを書いてください
  • PhotoTagInvertedIndex#addは並行性に関する問題があります。別のマシンで同時に実行してもデータが壊れないように修正してください
  • n-gramを利用するように変更してください
  • この記事の実装とn-gramを利用する実装で、処理速度や検索品質を比べてください
  • Redisではなくmemcached(あるいは、あなたの好きなKVS)をバックエンドにしてください