全文検索は、ほとんどのアプリケーションで欲しくなる機能である一方、とてもお金がかかります 
この記事では、Amazon DynamoDB で全文検索を実装することで、コストを大幅に抑える方法をご紹介します。
前提知識
全文検索 とは
大量の文章の中から、特定の文字列を検索する仕組みです。
例えば、この Qiita でも 「記事、質問を検索」 から何かを検索するとき、全文検索の仕組みが使われています。
全文検索にかかるお金
全文検索を実装する方法別に、コストをざっくり見てみます。
コスト概算は2023/12/04 現在公開されているものに基づいてざっくりと行っています。
料金の概算では、以下のようなユースケースを前提にします
- 月間のPV数は、約300,000PV の中規模なサイト
- 1日に1,000人が検索を行う
...
- 文字を入力するごとに検索結果を表示する仕組みで、1人は平均20文字を入力するので、1日に約20,000回検索APIが叩かれる
- サイトには、「タイトル」「著者」「本文」から構成されるコンテンツが10,000件登録されている
- 各コンテンツの本文は、平均 1,000 文字ほど
- タイトル、著者は長くても30文字
- 毎日、約100件のコンテンツが登録される
Algolia
今回のユースケースでは、月の検索回数は20,000*30=600,000回。
プラン
10,000リクエストを超えるので、無料のBuildプランではなく、Growプラン。レコード数課金
今回のユースケースでは、レコード数は合計10,000件。
100,000 レコードまで無料枠なので、無料。検索回数課金
10,000 リクエストまでは無料なので、課金対象は 590,000 回分。
￥75($0.50)/1,000リクエスト なので、75*590 = 44,250円
| サービス名 | 概要 | 月にかかる料金の概算 |
|---|---|---|
| Algolia | 高速な全文検索SaaS | 44,250円 |
| Elastic Cloud | Elasticsearch のクラウド | 2,970円〜 |
この記事で紹介する方法で実装した場合、（概算が難しいので正確な数字を出すのは難しそうですが） 数百円/月 に収まるはずです。
Amazon DynamoDB とは
1 桁ミリ秒単位で規模に応じたパフォーマンスを実現する高速で柔軟な NoSQL データベースサービス
https://aws.amazon.com/jp/dynamodb/
です。
NoSQL なので RDS に比べて機能は少ないですが、とても高速でスケーラブルです。
どうやって全文検索を実現するか
例えば、こんなデータがあったときに ↓
| ごとうひとり |
| ごとうふたり |
| いじちにじか |
| やまだりょう |
| きたいくよ |
ごとう で検索したら、
| ごとうひとり |
| ごとうふたり |
が取得できてほしい
STEP 1
まず、あらかじめ検索対象のデータを、bigram で分解して保存しておきます。
| 名前 | |||||
|---|---|---|---|---|---|
| ごとうひとり | ごと | とう | うひ | ひと | とり |
| ごとうふたり | ごと | とう | うふ | ふた | たり |
| いじちにじか | いじ | じち | ちに | にじ | じか |
| やまだりょう | やま | まだ | だり | りょ | ょう |
| きたいくよ | きた | たい | いく | くよ |
STEP 2
つぎに、検索するキーワードも bigram で分解します。
今回だと ごとう なので、 「ごと」 と 「とう」 です。
STEP 3
STEP 3-1
名前の中から、「ごと」 が分割文字列に含まれる名前を探します。すると、次の２つの名前が該当します。
| 名前 | |||||
|---|---|---|---|---|---|
| ごとうひとり | ごと | とう | うひ | ひと | とり |
| ごとうふたり | ごと | とう | うふ | ふた | たり |
STEP 3-2
名前の中から、「とう」 が分割文字列に含まれる名前を探します。すると、次の２つの名前が該当します。
| 名前 | |||||
|---|---|---|---|---|---|
| ごとうひとり | ごと | とう | うひ | ひと | とり |
| ごとうふたり | ごと | とう | うふ | ふた | たり |
STEP 4
STEP 3 で、検索キーワードの分割文字列全てを含むデータは次の２つなので、この２つのデータを検索結果として表示します。
| 名前 | |||||
|---|---|---|---|---|---|
| ごとうひとり | ごと | とう | うひ | ひと | とり |
| ごとうふたり | ごと | とう | うふ | ふた | たり |
bigram を用いた実装は、全文検索の実装方法のうちの一つでしかありません。
DynamoDB のテーブル設計
上のような形式をどのような構造のテーブルに格納すればいいかを考えます。
Twitterのように、投稿本文と投稿者が存在するようなデータで考えてみましょう。
| 本文 | 投稿者 |
|---|---|
| こんにちは | みちのすけ |
| こんばんは | みちたろう |
以下のような要件を満たすテーブル構造を考えます。
- データは「投稿本文」と「投稿者」で、どちらを検索対象にするか選択できる
- 投稿を作成した場合、その投稿に対してインデックスを作成する
- 投稿を更新した場合、その投稿に対する全てのインデックスを削除したのち、生成し直す
- 投稿を削除した場合、その投稿に対する全てのインデックスを削除できる
- 投稿を分割文字列で検索する場合、その分割文字列を含む全ての投稿を返す。
今回は、次のようなテーブルにしてみました。
用語
PK: パーティションキー
SK: ソートキー
GSI: グローバルセカンダリインデックス
| Key(PK) | Body | User | PostId(SK/GSI) |
|---|---|---|---|
| POST-001 | こんにちは | みちのすけ | 001 |
| POST-002 | こんばんは | みちたろう | 001 |
| BODY-_こ | 001 | ||
| BODY-_こ | 002 | ||
| BODY-こん | 001 | ||
| BODY_こん | 002 | ||
| BODY-にち | 001 | ||
| BODY-ちは | 001 | ||
| BODY-ばん | 002 | ||
| BODY-んに | 001 | ||
| BODY-んば | 002 | ||
| BODY-んは | 002 | ||
| USER-_み | 001 | ||
| USER-_み | 002 | ||
| USER-みち | 001 | ||
| USER-みち | 002 | ||
| USER-ちの | 001 | ||
| USER-ちた | 002 | ||
| USER-のす | 001 | ||
| USER-すけ | 001 | ||
| USER-たろ | 002 | ||
| USER-ろう | 002 |
もっと効率のいい設計もあるかと思いますが、今回はシンプルにこれでいきます。
DynamoDB に馴染みがない方にとってはとても奇妙に見えると思いますが、DynamoDB ではテーブルの正規化は行わず、１テーブルで全てのデータを管理することがベストプラクティスとされています。
"Amazon DynamoDB の一般的な設計原則では、使用するテーブルの数を最小限に抑えることをお勧めします。大部分のケースで、1 つのテーブルを使用することをお勧めします。"
https://docs.aws.amazon.com/ja_jp/amazondynamodb/latest/developerguide/bp-table-design.html
とんでもない行数になりますが、DynamoDB にはテーブルあたりの項目数制限はないため、どうにかなるはずです....
実際に、この機能が投稿の「作成」「更新」「削除」「検索」時にどのように動作するのかをみていきましょう。
作成
何もない状態から次のデータをテーブルに挿入することを考えます。
| PostId | 本文 | 投稿者 |
|---|---|---|
| 001 | こんにちは | みちのすけ |
テーブルに格納する前に、本文と投稿者名それぞれを bigram バラバラにします。
| 本文 | こんにちは | _こ | こん | んに | にち | ちは |
| 投稿者 | こんばんは | _こ | こん | んば | ばん | んは |
このとき、１文字でも先頭を検索できるように、「 _こ 」のような分割文字列も作成しておきます。
文字列の分割が終わったら、DynamoDB のテーブルに項目を追加します。
| Key(PK) | Body | User | PostId(SK/GSI) |
|---|---|---|---|
| POST-001 | こんにちは | みちのすけ | 001 |
| BODY-_こ | 001 | ||
| BODY-こん | 001 | ||
| BODY-にち | 001 | ||
| BODY-ちは | 001 | ||
| BODY-んに | 001 | ||
| USER-_み | 001 | ||
| USER-みち | 001 | ||
| USER-ちの | 001 | ||
| USER-のす | 001 | ||
| USER-すけ | 001 |
Key(PK) を見ると、項目は ３ 種類に分かれているのがわかります。
-
POST-から始まるキーを持つ項目は、検索で取得したい実データです。 -
BODY-から始まるキーを持つ項目は、本文を bigram で分割したものです。本文で検索するときに使用します。 -
USER-から始まるキーを持つ項目は、投稿者を bigram で分割したものです。投稿者で検索するときに使用します。
このように、文書に含まれる文字列と、その文字列が含まれる文書をマッピングしたデータ構造を「転置インデックス」や「逆引き索引」といったりします。
更新
ユーザが本文を更新する場合を考えます。この場合、POST- から始まる項目が更新されることになります。
| Key(PK) | Body | User | PostId(SK/GSI) |
|---|---|---|---|
| POST-001 | おはよう | みちのすけ | 001 |
POST- から始まる項目だけを更新した状況だと、本文は 「おはよう」 であるのにも関わらず、本文を 「こん」 で検索したときにこの項目がヒットしてしまいます。なぜなら、以下の項目がまだ存在しているからです。
| Key(PK) | Body | User | PostId(SK/GSI) |
|---|---|---|---|
| BODY-こん | 001 |
なので、POST- から始まる項目を更新した場合には、 (POST- を PostId にもつ) BODY- から始まる項目を一旦削除する必要があります。
| Key(PK) | Body | User | PostId(SK/GSI) |
|---|---|---|---|
| POST-001 | おはよう | みちのすけ | 001 |
| USER-_み | 001 | ||
| USER-みち | 001 | ||
| USER-ちの | 001 | ||
| USER-のす | 001 | ||
| USER-すけ | 001 |
このとき、削除する項目の指定は PostId に貼られている GSI で行います。
それから、「おはよう」 を bigram でバラバラにして、 BODY- を追加し直します。
| Key(PK) | Body | User | PostId(SK/GSI) |
|---|---|---|---|
| POST-001 | おはよう | みちのすけ | 001 |
| BODY-_お | 001 | ||
| BODY-おは | 001 | ||
| BODY-はよ | 001 | ||
| BODY-よう | 001 | ||
| USER-_み | 001 | ||
| USER-みち | 001 | ||
| USER-ちの | 001 | ||
| USER-のす | 001 | ||
| USER-すけ | 001 |
削除
ユーザが本文を削除する場合を考えます。この場合、POST- から始まる項目が削除されることになります。
検索でヒットしないようにする必要があるため、BODY- と USER- から始まる項目も全て削除・再作成する必要があります。
検索
ユーザが本文に対して文字列 「にちは」 を検索する場合を考えます。
まずは、 にちは を bigram で分割して、 にち と ちは という 2 つの文字列を得ます。
それから、 Key(PK) に対して、 BODY-にち と BODY-ちは に完全一致する項目をそれぞれ取得します。
次の 2つの行がヒットするはずです。
| Key(PK) | PostId(SK/GSI) |
|---|---|
| BODY-にち | 001 |
| BODY-ちは | 001 |
ヒットした行を見て、検索対象の全ての Key(PK) に含まれる PostId があるかを検証します。この場合、PostId は全ての Key(PK) に対して含まれるので、Id が 001 の投稿が検索結果として表示されるべき項目だということになります。
あとは、 POST-001 でクエリをかけると、検索結果としてふさわしい投稿データを取得できます。
| Key | 本文 | 投稿者 |
|---|---|---|
| POST-001 | こんにちは | みちのすけ |
実装してみる
実装編に続きます！