この記事は
第二のドワンゴ Advent Calendar 2020の最終日25日目の記事となります。
suzuki0keiichiと申します。ドワンゴではニコニコの開発の責任者という立場で仕事をしております。真ん中の0はメールアドレスが取れなかった時に仕方なく間に入れた0のため、読みません。
第二のドワンゴ Advent Calendarの方は元ドワンゴの方も多数参加していただきました。
ありがとうございました。
概要
静的なウェブアプリに対して全文検索の機能を提供する仕組みとしてtinysearchが存在します。
しかし、動的ウェブアプリでも"サーバー側でやるにはきつい"、"それぞれのユーザーに特化した"わがままな検索は需要あるんじゃないか、ということで色々試行錯誤してみました。
本当はありものを弄ってあっさりしたオチを書いておしまいにするつもりでしたが行く先々で詰まったため無駄に紆余曲折があったのでそちらも覚えている限り記載します。
動機
世はサブスクサービス全盛の時代。
各自のプレイリストやマイリスト等呼ばれていくものが大量に増えていく。
サブスクサービスでは、そうでないものと比べロングテールなコンテンツの視聴傾向になることも多く、年月を重ねるにつれ各自のリストも増えていく。
数が増えていくと自然と検索需要が高まる。プレイリスト内の全文検索、最後に視聴した順など。
サーバー側でとても強い仕組みを持ってきて解決することも勿論出来るだろうが、今回は業務では無く、業務でない時くらい意識低く行きたいため、"とりあえず気になったからやってみる"方式を採用する！！
ここに書いた動機もアドベントカレンダーネタを探すための後付である。
(本当の動機はアドベントカレンダーのネタを用意すること、その過程自体を意識低く楽しむことです)
そのため、ここに書かれていることはドワンゴのサービスとは将来に渡って一切関係が無い事をご了承ください。
やったこと
tinysearchの調査
まず調査。
検索してみると、今はtinysearchを使ってみるのが手っ取り早そうに見える。
tinysearchは静的サイトで外部検索エンジンに頼らず全文検索機能を提供する事が動機であるように読めたので、全然違う使い方なのだろうと思いつつも、検索エンジン部分を軽量で新規に実装する事を考えるととりあえず今回のものに使えないか調査をした方が良かろうという事で調査を進める。
記事を読み進めていくと、工夫の工程(パフォーマンスよりもサイズ)やデータを加工している場所(生データも含めてインデックスにパッケージ)が今回の要件にマッチしていないように見える。
さらに、プレフィックス検索を入れるとサイズが爆発するなど嫌な予感のする表現が、、
コードを追ってみると、title、url、bodyという固定の名前指定が、、、
これはもう特化して作ってあるんですね、分かりました。
後はもう事前にインデックス生成をしているプログラムをwasm側に持ってこれるかどうか、持ってきてパフォーマンスやサイズ的に意味のあるものかどうかという所が焦点になりそう。
一応tinysearchが使っているbloomフィルタ(内部を読む感じCuckooフィルタか？)はメモリ効率の高いものということで、engine側のコードだけでも価値は高いものと考え進めてみる。
bin/src/main.rsを追う感じ、mainの中でpostsを読み込んで、(bloom)filterとstorageを作成して、関係するwasmと一緒にパッケージにするといった事がされているようだ。
切り替えるとしたら、下記のような事が必要になるだろう
- filterとstorageを作成する部分をwasm側に
- 依存関係的に可能なのか、サイズやパフォーマンス的にそのまま持ってこれるのかが怪しい
- postsも外から受け取れる形式にする必要がある
- 既存エンジンもstorageを外から受け取れるようにする
Rustも(特にcargoやビルド周辺)あまり経験薄い状態でこれ間に合うのか！？
経験が薄いときは動いているものを参考にする派なので、既存のコードをもっと読んでみる。
tinysearchの構成は主にbin、engine、sharedという3つの部品で構成されているようだ。
- bin -- サーバー上でインデックス生成及びwasmパッケージを行う実行ファイル
- engine -- wasm化されてブラウザ側で検索を行うライブラリ
- shared -- bin/engineどちらからも利用されるライブラリ
- 記事、フィルタ、ストレージなど共通のインターフェースのためのもの
今回はサーバー側でインデックスを生成できるものではないため(してもいいが若干目的のメリットを失う)、binとsharedにあるものをすべてengineに移すのが手っ取り早いように思えた。
フィルタとストレージはbin/src/storage.rsに綺麗に分離されていたため、そのままengine/srcに持っていく。
engine/src/lib.rsは大量に改変することになるため念の為バックアップを取っておく。
全部engine側に移ることで、バイナリにしたり戻したりという概念が要らないだろうという事で除外しようかとも思ったが、local storageに置くことも考えまだコードは消さずにコメント化しておく。
lazy_staticはそのままwasmでも使えるんだな、、等の細かい学びがありつつ、
案外あっさりクライアントだけで動くところまでは行った。
tinysearchの頑張りポイントはコードより成果物とメモリのサイズ削減の部分のため、コードはボリュームもそこまで無くシンプルだったため助かった。
あれ、、ここまで書いていて気づいたけど、1コンテンツ1フィルタだと、
コンテンツが増えれば増えるほど検索のループでかくなるんじゃないか？？これはやばいという事で明日へ、、
転置インデックスを組み合わせるための調査
似たようなものがたくさん出てきて、全部を舐めずに対象のものにアクセスする仕組みとして転置インデックスというものがある。
大変雑な説明ですみません。
bloom filterを使いつつ転置インデックスって？という所で頭がこんがらがってしまったのでネット上を色々探す。
bloom filterは大変雑に言うとこんな感じである。
- 特定のワードを何種類かのハッシュ関数で何種類かの数字に変換し、その数字のbitを立てたbitmapを用意する
- 検索時は検索キーワードを同様の処理をしてbitmapを作り、同じところのbitが全て立っていれば含まれる可能性がある
というものである。
可能性があると書いているように、含まれていない可能性もある。
しかし、bitが立っていない場合は絶対に含まれることはないという、偽陽性のものである。
何個かの記事を見た所、このbitの単位で転置インデックスを作ってしまえばいいということのようだ。(bit-sliced～と書かれている事が多い)
今考えてみるとそりゃそうだという感じなんだけど、、
そこでtinysearchの内部を改めて覗いてみる。
よく見ると、bloomfilterじゃなくてcuckoofilterと書いてある。
ん？？違うのか？と思って記事を見たりコードを読んだりすると、結構違うものであることがわかった。
cuckoofilterは後から要素の削除も出来つつ、誤検知も減らせるような仕組みで、単純なbitmapではないことがわかった。これでは転置インデックスをどう作れば良いんだ、、となってしまったのでtinysearchの事は一旦全て忘れる事とする。
(ちなみに、bloomfilterでも削除ができるcounting bloomfilterというものもあるようだ。
他の方法を探す
まずはcuckoofilterではなくbloomfilerをRustのcrateから探してみる。
bloom、bloomfilterの2件ほど見つかったが、bitmapに外からアクセスできるのはbloomfilterの方だけなようなので、まずこれを使ってみることとした。
今までのtinysearchを少しいじらせてもらおう的な方式から完全に新規のプロジェクトに変えたので、Rust→wasmの辺りでどのくらい簡単な仕組みが整っているか不安だったが、軽く調べた所、IntelliJで新規Rustプロジェクトを作成する際にwasm-packもすんなり使えるようになっていた。便利！すごい！
ソースコードはここに置きました。
bloomfilterからbitmapを取ること、(ngramで区切った)単語が含まれているか正しく判定できるかの軽いテストコードを書いた結果、正しく動くことがわかったため今回はこれで行くことに決めた。
作ったもの
試行錯誤の後、実際に残ったコードは小さいものになった。
wasm用Rustプロジェクトは下記のような処理のみ。ソースはここ
- ngramで単語を分割する
- bloomfilterを生成する
- 転置インデックスを作成する
- 検索キーワードで検索する
デモ用のJavaScriptは下記のような処理のみ。ソースは主にここ
- 上記のRustプロジェクトで生成されたwasm、js、d.ts
- 試験データの加工
- 最低限のdom操作(検索UIのため)
- wasm側のフィルタ生成や検索処理を呼び出す
今回のデモでは情報学研究データリポジトリのニコニコデータセットの動画メタデータ(.jsonl)を加工して配列にしたものを検索対象とした。
計測結果など
すみません。しっかりした計測が間に合わなかったため、感覚的な事だけ記載します。
筆者の環境はSurface Laptop3 Core-i7版とGoogle Chrome 87.0.4280.88です。
フィルタ生成の部分はかなり重くなってしまい、1000件近く追加したら5秒近くかかる事がわかった。ビルドオプションを--releaseから--devにすると更に倍くらいになる。
流石に生成中固まるのは厳しいので、setTimeoutに逃した。(Worker的なもので解決するのが正しいと思いつつ、手を抜きます！)
10000件以上のコンテンツを追加し、適当なキーワードから"アイマス"等のたくさんヒットしそうなキーワードで検索しても、80ms以内には返ってくる。
体感としては特にストレスは感じないレベル。
単語次第ではわざわざ転置インデックスを用意したのに、大半のフィルタが検索対象になっているので、これがただのバグの場合もう少し改善が可能かもしれません。
とはいえ、爆速というほどの数字でもないため、bloomfilterじゃないもので検索した際に似たような結果で終わってしまう可能性もあります、、、
(時間があれば雑なcontainsとかで全文検索するものと比べてみたかったです)
まとめ
Bloom filterは結構わかりやすい仕組みでした。久しぶりの頭の体操としては丁度いいレベルでした。
また、Rustのwasm化はwasm-packは思った以上にあっさり動き、ストレスがないレベルまで来ているなと感じました。
Bloom filterのシンプルさも合わせると、筆者の夜中の時間1週間分くらいを使うだけでも、それなりの動きをする全文検索エンジンが作れる事も非常に好印象でした。
ただ、利用crateがOS依存の処理が含まれていることがあるため、wasmにする際にfeatureの指定をしないとビルドできない事があり、まだToml力が非常に低い筆者は無駄な時間を沢山消費しました。Rustに限らずsbtとかでもあるものなので、新環境あるあるだとは思います。
最後に実サービスの利用を考えてみると、下記のような理由でまだまだ現実感は薄いなと感じました。
- サーバー側とのマスターデータの同期が厳しい
- 生成したフィルタやインデックスの保存が大変
- 今回は手を出さなかったですが保存するとしたらlocalStorage辺りで、localStorageは容量や削除タイミングなどなかなか辛いことが多そう
- 全文検索 + ソート等、プラスアルファの部分が無いと実用的ではない、がその部分を自前で作るコストはとても大きい
終わりに
久しぶりに試行錯誤、各環境やライブラリに翻弄されましたが、ストレスフルな部分はありつつもゴールに近づいていく過程はとても楽しいものでした。
普段の業務での"失敗しないやり方"は今回一切使わず、ノープラン旅行のような開発の進め方をしたのも、気軽さが増して楽しさに貢献していたと思います。
今年はコロナ禍で年末年始はご自宅の方も多いと思いますので、時間を贅沢に使う意識の低い気楽な趣味プログラムをしてみるのはいかがでしょうか？
それでは皆さん良いお年を。
参考
たくさん参考にさせて頂きました。ありがとうございました。
tinysearch(github)
RustとWasmで静的ウェブページに日本語検索機能を追加する
Bing検索の裏側―BitFunnelのアルゴリズム
情報学研究データリポジトリ ニコニコデータセット
cuckoofilter(Rust crate)
bloomfilter(Rust crate)