１週間前にCloud Datastoreのクエリでがんばるハナシという記事を書きましたが、そこで書いた各種テクニックをサポートするライブラリを作ったので紹介します。

注意: 現時点でまだβ版(v0.1.0)です。正式版の前に後方互換のない修正が入る可能性があります

モチベーション

Search APIあまり使いたくない

Datastoreクエリの不足する機能を補う為にSearch APIを併用するテクニックがあります。
Search APIはとても便利ですがいくつかの制限があり、何よりインデックスサイズに上限がある為スケーラビリティに難があります。

参照: GAEでハマったこと(´･ω･`)

Search APIに出来るだけ頼らないことが本ライブラリの第一の目的です。

LIKEやINを使いたい

Cloud DatastoreはLIKEやIN/OR条件のフィルタをサポートしません。¹
これは内部のインデックス構造上の理由によるものですが、本ライブラリを利用することで部分的にですが実現することができます。

カスタムインデックス定義を節約したい

複数の異なるプロパティを組み合わせて検索したい場合でかつソートまたはInequality Filter(>,>=,<,<=)を併用する場合、index.yaml(GAE/Javaの場合はdatastore-indexes.xml)にカスタムインデックスを定義する必要があります。

カスタムインデックスは必要なプロパティの組み合わせの数だけ定義しておく必要があります。よくある複数フィールドを持つ検索画面UIなどで「未入力・未選択の場合は検索条件に含めない」という仕様があったりすると、その条件を含めないパターンのインデックスも定義しなくてはならなくなり、すぐにインデックス定義数が膨らんでしまいます。

カスタムインデックス定義の数やエンティティあたりのインデックスサイズには上限がある為、できる限りカスタムインデックス定義は少なくしておきたいところです。

本ライブラリは単一のListプロパティに必要なインデックスを集約しますので、カスタムインデックスの定義を削減して節約することが出来ます。

アーキテクチャ

本記事では割愛します。下記スライドがちょっと参考になります

Datastoreで検索エンジンを作る

利用例

サンプルコード

GAE/Go 1.11 runtime上で、appengine標準ライブラリ(google.golang.org/appengine/datastore) を用いて記述しています。
https://github.com/knightso/sandbox/blob/master/extra-ds-query/gae_xian_books.go

XIAN自体は現状datastoreライブラリに依存していない為、Cloud Datastore Client Library(cloud.google.com/go/datastore)でも同様に動作するはずです。

各サンプルの仕組みについてはCloud Datastoreのクエリでがんばるハナシで解説していますのでそちらを参照ください。

準備

保存・検索時共通設定

保存・検索時に差異があると正しく検索されない為、グローバル変数に保持しておくとよいです。

var bookIndexesConfig = &xian.Config{
    IgnoreCase:         true, // 大文字小文字を区別しない
}

モデル（Datastore保存用構造体）

// BookStatus describes status of Book
type BookStatus int

// BookStatus constants
const (
    BookStatusUnpublished BookStatus = 1 << iota
    BookStatusPublished
    BookStatusDiscontinued
)

// Book is sample model.
type Book struct {
    Title         string
    Price         int
    Category      string
    Status        BookStatus
    Indexes       []string // for XIAN
}

// BookStatuses is the list of all BookStatuses
var BookStatuses = []BookStatus{
    BookStatusUnpublished,
    BookStatusPublished,
    BookStatusDiscontinued,
}

フィルター用ラベル定数

検索項目ごとにラベルを用意します。
定数は必須ではないですがラベルはできるだけ短くしておいた方が良い為、可読性を考えて定数化しておくことを推奨します。

const (
    // BookQueryLabelTitleIndex は書籍タイトル部分一致検索用ラベル
    BookQueryLabelTitleIndex = "ti"
    // BookQueryLabelTitlePrefix は書籍タイトル前方一致検索用ラベル
    BookQueryLabelTitlePrefix = "tp"
    // BookQueryLabelIsPublished は書籍ステータス"発行済"検索用ラベル
    BookQueryLabelIsPublished = "p"
    // BookQueryLabelIsHobby は書籍カテゴリー"趣味"検索用ラベル
    BookQueryLabelIsHobby = "h"
    // BookQueryLabelStatusIN は書籍ステータスIN検索用ラベル
    BookQueryLabelStatusIN = "s"
    // BookQueryLabelPriceRange は書籍料金範囲検索用ラベル
    BookQueryLabelPriceRange = "pr"
)

保存共通処理

    key := datastore.NewKey(ctx, "Book", bookID, 0, nil)

    book := &Book{
        Title:    "title",
        Price:    2000,
        Status:   BookStatusUnpublished,
        Category: "sports",
    }

    idxs := xian.NewIndexes(bookIndexesConfig)

    〜各インデックス保存（後述）〜

    built, err := idxs.Build()
    if err != nil {
        return err
    }

    book.Indexes = built

    if _, err := datastore.Put(ctx, key, book); err != nil {
        return err
    }

後続サンプルでは 〜各インデックス保存（後述）〜 の部分のみ記述します。

検索共通処理

    q := datastore.NewQuery("Book")

    filters := xian.NewFilters(bookIndexesConfig)

    〜各フィルタ追加（後述）〜

    built, err := filters.Build()
    if err != nil {
        http.Error(w, err.Error(), http.StatusInternalServerError)
    }

    for _, f := range built {
        q = q.Filter("Indexes =", f)
    }

    var books []Book
    if _, err := q.GetAll(ctx, &books); err != nil {
        http.Error(w, err.Error(), http.StatusInternalServerError)
        return
    }

後続サンプルでは 〜各フィルタ追加（後述）〜 の部分のみ記述します。

部分一致

保存

検索条件が1文字の場合はunigram、2文字以上の場合はbigramで検索します。

    idxs.AddBiunigrams(BookQueryLabelTitleIndex, book.Title)

検索

    filters.AddBiunigrams(BookQueryLabelTitleIndex, title)

長文だとインデックス数がかなり大きくなるのでご注意ください。

前方一致

プレフィックスで検索します。

保存

    idxs.AddPrefixes(BookQueryLabelTitlePrefix, book.Title)

検索

    filters.AddPrefix(BookQueryLabelTitlePrefix, title)

biunigram以上にインデックスを消費する為長文には向きません。

NOT EQUAL

以降は直接本ライブラリの提供機能という訳ではないですが、Cloud Datastoreのクエリでがんばるハナシで挙げたテクニックのサンプルを記します。

NOT EQUALは条件が固定ならばboolのEquality Filterに変換できます。

保存

    idxs.AddSomething(BookQueryLabelIsPublished, book.Status == BookStatusPublished)

検索

    filter.AddSomething(BookQueryLabelIsPublished, false)

IN(OR)

IN(OR)も条件が固定ならばEquality Filterに変換可能です。

保存

    idxs.AddSomething(BookQueryLabelIsHobby, book.Category == "sports" || book.Category == "cooking")

検索

    filters.AddSomething(BookQueryLabelIsHobby, true)

IN(OR)全組み合わせバージョン

力技ですが、IN(OR)の全組み合わせを登録しておくことで、条件不定のOR条件もEquality Filterで実装可能です。

保存

    for i := 1; i < 1<<uint(len(BookStatuses))+1; i++ {
        if i&int(book.Status) != 0 {
            idxs.AddSomething(BookQueryLabelStatusIN, i)
        }
    }

検索

OR検索はbit論理和で指定できます。

    filters.AddSomething(BookQueryLabelStatusIN, BookStatusUnpublished|BookStatusPublished)

大小比較

大小比較も仕様を調整して選択肢を固定にすればEquality Filterで検索できます。

保存

    switch {
    case book.Price < 3000:
        idxs.Add(BookQueryLabelPriceRange, "p<3000")
    case book.Price < 5000:
        idxs.Add(BookQueryLabelPriceRange, "3000<=p<5000")
    case book.Price < 10000:
        idxs.Add(BookQueryLabelPriceRange, "5000<=p<10000")
    default:
        idxs.Add(BookQueryLabelPriceRange, "10000<=p")
    }

検索

    filters := xian.NewFilters(bookIndexesConfig).Add(BookQueryLabelPriceRange, "5000<=p<10000")

ソートやInequality Filterの併用

クエリのソートやInequality Filterは従来通りに使用可能です。
ソートやInequlity Filter対象のプロパティと、本ライブラリインデックス保存用プロパティ（上記サンプルだとIndexes）とを組み合わせたカスタムインデックスが必要になります。

SaveNoFiltersIndex

ConfigでSaveNoFiltersIndexをtrueに設定しておくと、インデックス保存時に必ず拡張フィルタなし検索用のインデックスが保存されます。

var bookIndexesConfig = &xian.Config{
    IgnoreCase:         true,
    SaveNoFiltersIndex: true, // here
}

検索時にフィルタを設定しない場合、この拡張フィルタなし検索用インデックスのEquality Filterが自動で適用されます。

この設定がfalseで、拡張フィルタのあり・なしの両パターンの検索がある場合、カスタムインデックスを両パターン分用意しておく必要がありますが、trueにしておくことでカスタムインデックスを半分に節約することができます。

トレードオフ

マージジョイン

上述下通り本ライブラリは単一Listプロパティにインデックスを詰め込むことでカスタムインデックス定義を節約することを目的の一つとしていますが、内部的にはマージジョインという仕組みで検索が行われる為、データ件数や条件によってはカスタムインデックスを定義した場合に比べてパフォーマンスが極端に落ちることがあります。²

対策

カスタムインデックスの併用

フィルタ使用頻度の高いプロパティ（例えばユーザーIDなど）は本ライブラリ対象から外して通常プロパティとしてカスタムインデックスを組むことでマージジョインのパフォーマンス劣化を軽減することができます。

- kind: Book
  properties:
  - name: UserID
  - name: Indexes

CompositeIdxLabels

本ライブラリ自体にも複合インデックス機能を持っています。

よく使われるフィルタラベルの組み合わせを設定しておくと内部に複合インデックスが構築され、そのラベルに対するフィルタを複数適用するとマージジョイン劣化が軽減されます。

// ValidateConfig/MustValidateConfig関数を利用すると事前にCompositeIdxLabelsのバリデーションを行う
var bookIndexesConfig = xian.MustValidateConfig(&xian.Config{
    IgnoreCase:         true,
    SaveNoFiltersIndex: true,
    CompositeIdxLabels: []string{BookQueryLabelIsPublished, BookQueryLabelIsHobby, BookQueryLabelPriceRange}, // here
})

複合インデックス機能は指数関数的にインデックスが増えていくので用法用量にご注意ください。複数インデックスを持つラベル(biunigramなど)が含まれるとさらにインデックス数は爆発します。

インデックス爆発を防ぐ為に、現在下記の制限があります。

CompositeIdxLabelsに指定できるラベル数は最大8
Build後の合計拡張インデックス数は最大512

超過するとエラーになります。

マイグレーション

本ライブラリで作成したインデックスに影響のある修正や変更があった場合は保存済み既存エンティティに対して全てマイグレーション（インデックス再保存）を行う必要が生じます。 ³

PUT時レイテンシ

本ライブラリを使用すると、（使用方法にもよりますが）基本的にインデックス量は増大します。
現行Datastoreはインデックスが非同期で保存される為PUT時レイテンシへの影響は微小でしたが、バックエンドがFirestore in Datastore modeになった場合、レイテンシに大きく影響を与える可能性があります。（検証予定です）

TODO

README書く（これは一両日中に！）
テストもっと充実させる
INフィルタを簡易的に書けるユーティリティ関数
もっと簡易的に記述する為のラッパーユーティリティ
Firestore in Datastore modeでパフォーマンス検証
後方一致（優先度低）
形態素解析サンプル（優先度低）

さいごに

Datastoreの標準クエリだけでも工夫をすれば結構いろいろ検索できることを知ってもらえたら嬉しいです(^^)

Cloud Spannerなど超強力な新勢力におされて影が薄くなりがちなDatastoreですが、まだまだコスト的にはメリットもあります。
また今後DatastoreのバックエンドがFirestore(Spanner)に移行されていきますので、そちらの美味しいところを貰ってさらに強力なサービスになっていくことが期待されます。⁴⁵

自分はこれからも安くて美味しいDatastore、使い倒していく所存です！！q(^o^)p

あと・・・テスト手伝ってくれた石田さん、Thanks!!

JavaやPythonはSDKライブラリレベルでサポートしていますが、カーソルが使えないなどの制限があります。 ↩
経験的に数百万エンティティくらいではパフォーマンス劣化は落ちませんでした（検索条件にもよりますが）。 ↩
Datastore標準機能でもシングルプロパティインデックスの追加変更はマイグレーションが必要です。カスタムインデックスの追加変更は自動で更新されます。 ↩
主にトランザクション周りの制限が緩和されます。クエリも強整合になります ↩
値上げがないことを祈るばかり(^ω^; ↩

Cloud Datastoreのクエリでがんばるハナシ2 〜 ライブラリ作った 〜