Rust初心者がRustで全文検索サーバを作ってみた

情報検索・検索エンジン Advent Calendar 2019 の5日目の記事です。このAdvent Calendarを作った@takuya_aさんより、お誘いいただきました。

@minoru_osuka もし余裕あれば12/5の記事お願いします！ https://t.co/YIA9tIB4Gj

— takuya-a (@takuya_b) December 1, 2019

ということで、仕事とは別で個人的に始めたプロジェクトについて紹介できたらと思います。

私自身はApache Solrを好んで利用しています。
ただ、最近のサーバサイドの技術の移り変わりや、新しい開発言語の登場など、取り巻く環境が変化してきています。それらの習得も踏まえ、使ったことのない開発言語を用いて軽量な全文検索サーバを作り始めるという内容です。

開発した経緯

インフラの変化

ここ数年でインフラは大きく変化しました。
Solrが生まれた頃は、全文検索サーバ用にハードウェアを調達し、そのハードウェア上にSolrをインストールして実行していました。CPUやメモリ、ストレージをすぐに準備することができず苦労していたことを思い出します。リソースが用意できないのでSolrのマルチコアの機能を使い1つのSolrに異なるスキーマのインデックスを載せてサービスを相乗りさせることも当たり前でした。

それがOpenStackやVMwareなどのVMによる仮想化技術、Amazon Web ServicesやGoogle Cloudなどのクラウド環境の普及により、検索エンジンのスケールも比較的容易に行えるようになります。この頃からSolrもSolrCloudという従来のReplicationに代わるモダンなよりクラウドらしいクラスタ構成がとれるようになます。

そして今度は、コンテナによる仮想化技術の普及です。Dockerの登場でVMでの仮想化からコンテナによる仮想化に一気に移り変わろうとしています。その普及を後押ししているのが、コンテナ化されたアプリケーションの展開やスケーリング、管理を自動化するための基盤であるKubernetesなどのコンテナオーケストレーションシステムです。

前職、現職でもSolrやElasticsearchをKubernetes上にデプロイして運用する(運用してみようとチャレンジしてみる)ということを行っていますが、「全文検索サーバのように複雑なクラスタ機能を独自に持っているステートフルなミドルウェアをKubernetes上でうまく扱うのは難しいのでは？」とよく聞きます。実際にKubernetesの上にSolrCloudをデプロイして運用するのは大変でした。Kubernetesの恩恵を十分に享受しながらSolrCloudの機能を発揮するのはとても大変です。あるところではKubernetes上でSolrCloudを動かすことを諦めたという話を耳にすることもあります。なかなか一筋縄ではいきません。
効果的にデプロイするために試行錯誤しているうちに、それならば、最初からコンテナオーケストレーションシステム上で動かすことを前提として全文検索サーバを作ってみるのはどうだろうと漠然と考え始めました。

Rustの習得

漠然と考え始めた全文検索サーバの開発ですが、どの言語で開発しようかとなります。使い慣れたJavaがすぐに頭に浮かびます。全文検索ライブラリまで作るとなると大変なので、既存のライブラリを利用したいところです。JavaであればApache Lucene一択となりますが、Luceneを使ってまた検索サーバを作るならSolrとかElasticsearchで良いのでは?と自分の中で堂々巡りとなってしまったので、いっそJavaは忘れることにしました。
この機会に新しい開発言語の習得も兼ねてみたいと考えていたところ、Rustが目に止まりました。Rustにはガーベッジコレクション(GC)が無く、高いパフォーマンスを求められるシステムに適していると聞き興味を持ちました。話を聞くに検索エンジンのようなものの開発にうってつけな気がします。
ちょっとRust触ってみようかなと思ったのが、家に住みついたサワガニを捕まえた8月のことです。

数週間前から家にサワガニが住みついている。
Rustやれってお告げだろうか？#rustlang pic.twitter.com/cwMpZMjHwS

— Minoru Osuka (@minoru_osuka) August 11, 2019

Bayard

ということで9月からRustの本を買い、Bayardという全文検索サーバのPoC(Proof of Concept)をBorrow checkerに怒られながら開始します。
Bayardの開発は次のポリシーで進めています。

シンプル

検索サーバなので、全文検索機能は当たり前ですが、入力されたクエリーに対してマッチするドキュメントを高速に返せること、まずこれだけです。Learning to Rank(LTR)のような高度な機能は一旦横において、採用する全文検索ライブラリの機能を十分に使えることにします。

SolrやElasticsearchは1プロセス中に複数のインデックスを持つことができますがそれはしません。1プロセス1インデックスのみとします。コンテナオーケストレーションシステムによってリソースの割当が柔軟に行えるようになるので、昔のように1ノードに複数のインデックスを載せて相乗りさせる必要がないと考えたためです。

インデックスのスキーマは起動時にプロセスに渡され決定します。起動中にスキーマの変更は行いません。イミュータブルです。スキーマに変更がある場合は変更したスキーマで新たに起動しなおしてインデックスを作成しなおします。
SolrやElasticsearchでもスキーマ変更がある場合は別のクラスタを作成して再インデックス後に切り替えを行うことが多いのでミュータブルである必要もないと考えています。

The Twelve-Factor Appの手法になるべく沿った形で開発していこうと思います。

クラウドネイティブ

Cloud Native Computing Foundationにクラウドネイティブの定義としてCNCF Cloud Native Definitionという文書を公開しています。ここに書かれている定義に沿ったアプリケーションを開発するようにします。とはいえ、私自身がクラウドネイティブではないので具体的にどうして良いかはよくわからないです。さしあたってその最高峰ともいえるKubernetes上にデプロイをすることを前提に開発を進めようと思いっています。

コンテナ化してコンテナオーケストレーションシステム上にデプロイすることを前提とし、その上で水平スケールが可能になるようにします。SolrやElasticsearchのような高度なクラスタ機能は実装しません。多くの部分をコンテナオーケストレーションシステムに任せます。そのための監視が行えるようにログ出力とメトリクスの公開を行います。

採用した技術

せっかく新しく作るのだから、新しい技術を積極的に取り入れていこうと思い、次のものを取り入れました。

Tantivy

全文検索ライブラリとしてはLuceneが現在もっとも利用されているかと思いますが、他の言語で実装されたものもいくつかあります。

• Whoosh - Pure Pythonの全文検索ライブラリ。現在メンテナンスされていない？
• Bleve - Couchbaseが開発するGo製の全文検索ライブラリ。Kagomeが利用可能。
• Tantivy - Google Search SWEのPaul Masurel氏が開発するRust製の全文検索ライブラリ。

これらは、どれもLuceneの影響を多分に受けたいわゆるLucene alternativesです。いろいろな言語で実装されている全文検索ライブラリがありますが、実際どれが速いのかというのも気になります。
そこで、Bleve、Lucene、Tantivyの3つのベンチマークを比較してみました。約500万件のWikipedia(英語)の記事をインデックスして各キーワードの検索に要した時間を計測したものです。
このベンチマークのとり方ではTantivyが最速という結果になりました。(Tokenizerの設定はなるべく似せるようにはしてみました)
Search Benchmark, the Game
ベンチマークの結果からも高速に動くTantivyはなかなか良さそうです。
Meetupへの参加がきっかけでTantivyの開発者であるPaulさんと個人的な交流もあり、いろいろ質問もできそうなのでTantivyを採用します。そもそもRustを勉強しようとしているのでTantivy一択です。

Tantivy - Deep dive into Indexing

• Video
• 資料

gRPC

サーバ実装なので、クライントとの通信も高速に行えるようにしたいと考えました。従来のREST APIで行くか、それとも別の新しい技術を採用してみるか検討した結果、Googleによって開発されているgRPCというRPCフレームワークを採用することにしました。
gRPCはHTTP/2とProtocol Buffersを利用して高速なRPCによる通信を実現するというものです。最近ではマイクロサービスアーキテクチャを採用たシステムを構築する際に各コンポーネント間の通信に従来のREST APIに代わって採用される事例が増えてきているようです。

ライブラリはPingCAPから提供されているgrpc-rsを利用します。
このgrpc-rsはPingCAPが開発するTiKVというRust製のKey-Value database向けに開発されているライブラリなので実績は十分あります。

Futures and gRPC in Rust

• Video
• 資料

Raft Consensus Algorithm

サーバがスタンドアロンでしか動かないとなると耐障害性に問題があります。最近の全文検索サーバはクラスタが組めて当然な風潮です。Solrがどのようにクラスタを組んでいるかおさらいします。
SolrCloudではApache ZooKeeperがクラスタの状態を管理しています。
ZooKeeper自身もアンサンブル(ensemble)と呼ばれるクラスタを構成する機能をもち、複数ノードでデータをレプリケーションし、耐障害性の向上を図っています。
Solr自体はクラスタリングの機能は持っておらず、各SolrノードはそのZooKeeperに問い合わせてデータのレプリケーション先や分散検索をする先を知ることになります。SolrCloudにおいてZooKeeperが分散インデックス・検索、レプリケーションの中核の機能を提供しています。
ZooKeeperはいわゆるレプリケーション機能を持つKey-Value storeです。Key-Valueのデータの同期以外にもZooKeeperアンサンブル自体のクラスタ情報の同期も行っています。

ZooKeeper以外にもetcdやConsulといった同様のミドルウェアがあります。各ノード間でのデータの同期は、ZooKeeperはZooKeeper Atomic Broadcast(ZAB)、etcd、ConsulはRaft Consensus Algorithmという分散合意アルゴリズムを使用して実現されています。

BayardもSolrのように、こういったミドルウェアに頼ることを考えましたが、分散合意アルゴリズムを検索サーバ自体に組み込んでしまおうと考えました。
RaftのライブラリもPingCAPからraft-rsが提供されているのでこちらを利用します。
実際に組み込み作業を始めますが、このライブラリの使いか方がとても難しかったです。Paulさんも一度チャレンジしたようですが、「使い方がよくわからなかった。完全に失敗したよ」と言っていました。PingCAPの人も「元々TiKVのために作っているから扱いは大変かもしれない。わからないことがあったらなんでも聞いてね」とのことでした。Raftの組み込みが最も時間がかかった作業でした。

RustConf 2018 - Using Raft in Rust by Siddon Tang

• Video

アーキテクチャ

上記で紹介したRaftをBayard自体に組み込んでクラスタ構成をサポートしているため、SolrCloudやElasticsearchとはアーキテクチャは少し異なります。その構成はどちらかというとZooKeeperやetcdに近いものになります。大雑把書くと次のようになります。

クラスタは最低3ノード以上の奇数個の(3,5,7...)ノードで構成します。これはいわゆるSplit-brainを避けるためです。もちろんスタンドアローンで起動できますが、内部的にはシングルノードのクラスタという扱いです。

Bayardの中も大雑把に書くと次のような構造になっています。

全文検索を行えるZooKeeperとかetcdといった感じのサーバになります。
gRPC Serverが受け取ったデータが、State Machineに渡され、他のノードとコンセンサスをとり、Indexerによってインデックスの更新が行われます。

ノード間のデータの更新は下記のような流れで行われます。
ここで言うデータとは、クラスタの状態遷移を記録するエントリ(クラスタにノードが追加・削除されたなど)とインデックスに対して行われる処理のエントリ(ドキュメントの追加・削除・コミット・ロールバックなど)を含みます。

1. すべての更新リクエストは必ずリーダーが受け取ります。(Bayardの場合はフォロワーが受け付けた場合はリーダーへ転送するようにしています)
2. リーダーは自身のRaftログにエントリを追加します。
3. リーダーは追加されたエントリをフォロワーに同じエントリをブロードキャストします。
4. リーダーは自身も含めて過半数からエントリを保存したとの応答があるまで待機し、応答があればログのエントリをコミットします。
5. リーダーはコミットが完了したらクライアントへ応答を返します。

実行

ビルドから試してみたいという方は、こちらのドキュメントを参照してください。
Building Bayard
Getting started

Dockerの環境がある方はビルドせずに次のように実行できます。もし興味があれば試してみてください。
次のコマンドでDockerでBayardを起動できます。

$ docker run --rm --name bayard_server -p 5000:5000 bayardsearch/bayard:0.2.0 serve

起動したBayardはデフォルトのスキーマで起動しています。スキーマの確認は次のコマンドで行えます。

$ docker exec bayard_server bayard schema

適用されているスキーマに合わせてドキュメントを登録します。次のように幾つか登録して、最後にコミットします。

$ docker exec bayard_server bayard put 1 '{"text":"Bayard is a full text search and indexing server, written in Rust, built on top of Tantivy."}'
$ docker exec bayard_server bayard put 2 '{"text":"Solr is highly reliable, scalable and fault tolerant, providing distributed indexing, replication and load-balanced querying, automated failover and recovery, centralized configuration and more."}'
$ docker exec bayard_server bayard put 3 '{"text":"Elasticsearch is a distributed, open source search and analytics engine for all types of data, including textual, numerical, geospatial, structured, and unstructured."}'
$ docker exec bayard_server bayard put 4 '{"text":"Blast is a full text search and indexing server, written in Go, built on top of Bleve."}'
$ docker exec bayard_server bayard put 5 '{"text":"Riot is Go Open Source, Distributed, Simple and efficient full text search engine."}'
$ docker exec bayard_server bayard put 6 '{"text":"Toshi is meant to be a full-text search engine similar to Elasticsearch. Toshi strives to be to Elasticsearch what Tantivy is to Lucene."}'
$ docker exec bayard_server bayard put 7 '{"text":"Sonic is a fast, lightweight and schema-less search backend."}'
$ docker exec bayard_server bayard put 8 '{"text":"Tantivy is a full-text search engine library inspired by Apache Lucene and written in Rust."}'
$ docker exec bayard_server bayard put 9 '{"text":"Apache Lucene is a high-performance, full-featured text search engine library written entirely in Java."}'
$ docker exec bayard_server bayard put 10 '{"text":"Bleve is a modern text indexing library for go."}'
$ docker exec bayard_server bayard put 11 '{"text":"Whoosh is a fast, pure Python search engine library."}'
$ docker exec bayard_server bayard commit

ドキュメントIDを指定してインデックスからドキュメントを取得するには次のコマンドで行えます。

$ docker exec bayard_server bayard get 1

キーワードで検索するには次のコマンドで行えます。textフィールドにrustを含むドキュメントを検索する例です。

$ docker exec bayard_server bayard search text:"rust"

上記はスタンドアローンのサンプルですが、クラスタを構築する例はこちらに記載しています。
現在は依然PoCステージなので、機能もドキュメントも十分ではありませんが、こちらも見ていただけたらと思います。

• Source code repository
• Docker container repository
• Documents

公開後の反響

2019/11/01にGiHubで公開して1日でStarが500以上、1週間で1000を超えるなど想定外こ反響があり驚きました。
これもPingCAPのCommunity Relationshipsの人がBayardを気に入ってくれて、Hacker Newsに投稿してくれたおかげです。多くの開発者やユーザが集うコミュニティに対して積極的に情報発信、関係構築を行う事がOSSの世界でどれだけ大事なことか、改めてこういったロールの人の存在の大きさから実感しました。多くの人の目にとまるとそれだけ大きな反響も得られました。

Submitted to Hacker News and now it’s being discussed on the front page: https://t.co/9HdzZICLVW

— Queeny (@Que8eny) November 1, 2019

最初のリリースでは接続はgRPCのみだったのですぐにREST APIを用意してほしい旨の問い合わせがきました。まだgRPCで接続するにはハードルが高いようです。私もRust以外の言語向けに準備できていないのもあり、ひとまずREST APIの用意をすることにしました。

ElasticsearchとKibanaは本当に人気があります。ElasticsearchのREST APIとの互換性を望む問い合わせもきました。Kibanaで繋ぎたいと言うことでしたが、ElasticsearchのAPIをサポートするのは難しいのでお断りしました。アプリケーションログをインデックスしてKibanaで可視化するために軽量なElasticsearchの代替が欲しいようでした。KibanaとほどでなくてもGUIでインデックスの中身を可視化できると、もうワンチャンスありそうです。
OSSプロダクトに中立的なポジションのGrafanaでDatasourceプラグインを作ればデータの可視化ができそうなので作ってみてもいいかもしれないと思いました。

ちゃんと数えた訳ではないですが、Starをつけてくれた人たちは中国、フランスの人たちが多いような気がしました。PingCAPが中国のテック企業なのでなんとなくそうなのかな？と思いましたが、フランスも多いのはTantivyの開発者がフランス人だからでしょうか?

Rust製の全文検索サーバということでプロモーションをHacker Newsにポストされているので、Starを付けてくれた人たちのGitHubのプロフィールを見るとほとんどがRustのエンジニアです。でも、それと同じくらいGoのエンジニアも多いように見えます。それに対してJavaのエンジニアが極端に少ない印象です。Rust、Go、C/C++エンジニアには刺さっても、Javaエンジニアには刺さらなかったようです。
Javaを使わないエンジニアはLucene/Solr、Elasticsearch以外の選択肢を求めているのかと勘ぐってしまうくらいです。ニッチなところを狙えそうです。

Redditにも誰かがポストしてくれていて、その中でRust製の同じTantivyを使った全文検索サーバToshiの開発者からもコメントが付きました。先行するプロダクトの先輩開発者から、驚きとお褒めの言葉をもらい嬉しく思います。

I'm surprised this just comes out of nowhere, it would have been really awesome to collaborate with people on a project, but this also looks like it's professional. Either way, it no doubt it's consensus and distribution is much more complete than Toshi's, but the general threading and web features of this server seem much simpler, it basically uses that comes with grpc. Either way it's a super cool project, it gives me a lot of insight about how to adapt this type of raft consensus to Toshi and shares the same MIT license too.

なにか一緒にできたらといいなと思います。

おわりに

個人的なプロジェクトの紹介となって大変恐縮です。
SolrやElasticsearchといったOSSの検索サーバを利用されている方がたくさんいらっしゃるとは思いますが、LuceneやLucene alternativesもたくさん存在しています。自分の用途に合わせたシンプルなサーバを自分のお気に入りの開発言語で書いてみるのもなかなか楽しいものです。またTantivyのようなLucene alternativeを作ってみるというのもまた楽しいと思います。こんな楽しみ方もあるということを本日の記事でお伝えできたらと思いました。

このような記事を書く機会を作ってくれた@takuya_aさんと、Bayardのリリースにあたり協力してくれたPaulさん、PingCAPのエンジニア達、プロモーションに協力してくれたQueenyさんに感謝します。

ちなみに、開発している検索サーバにBayardと名付けたのは愛着を持って開発を続けられるようにと思ったからです。
採用したTantivyのロゴが馬で、「馬を速く走らせる」という意味を持っていた事から、自分も馬にちなんだ名前を付けようと探したところ、Bayardという、乗り手の数によって体の大きさを変化させることができるという伝説の馬がいるということで、その名前をつけました。

Bayard (French: Bayard; Italian: Baiardo; Dutch: (Ros) Beiaard) is a magic bay horse in the legends derived from the chansons de geste. He is renowned for his spirit, and possesses the supernatural ability to adjust his size to his riders.

Tantivyリスペクトのスケーラブルな馬です。

最後までお読みいただきありがとうございました。