皆さんこんにちは！WESEEK ソフトウェアエンジニアの増山です。

今回は、MongoDB (mongoose) で木構造のモデルの作成と、そのドキュメントの取得戦略について考えます。

JavaScript の AsyncGenerator を使った方法と、MongoDB の $graphLookup (aggregation) を使った方法の2つを紹介します。

前提知識

以下の前提知識があるとより楽に読み進められると思いますので参考にしてください。

JavaScript の AsyncIterator, AsyncGenerator
- https://javascript.info/async-iterators-generators
MongoDB
- https://www.mongodb.com/
mongoose
- https://mongoosejs.com/

今回扱う木構造のモデル

今回は以下のような木構造データモデルを扱います。

ドキュメントが他のドキュメントの ObjectId を親ドキュメントの参照として持つ構造になっています。

const nodeSchema = new Schema({
  parent: { type: mongoose.Schema.Types.ObjectId, ref: 'Node' },
  name: { type: String, default: '' },
});

MongoDB のドキュメントでは他にもいくつかの木構造データモデルの例が挙げられていますので興味があればこちらをご覧ください。

ゴール

ある Node を指定した時にその子孫の Node を全て取得するというシチュエーションを考えて見ます。

方法1

方法1では、順序関係なしに、特定の Node の全ての子孫 Node を Iterable として取得すること」を目指します。

実装

コード上のコメントで実装の解説しています。

最終的に generateIterable を呼ぶことで使用できます。

// 空配列であるかどうかを確かめるユーティリティ
const isEmptyArray = (val: any): val is never[] => {
    return 'length' in val && val.length === 0
}

class IterableTreeDocsFactory {

  async generateIterable(initialNode: NodeDocument): Promise<AsyncGenerator<NodeDocument> | never[]> {
    // ルートとなる initialNode から Cursor を作成
    const initialCursor = await this.getCursor(initialNode)

    return this.generateDescendantNodes(initialCursor)
  }

  private async* generateDescendantNodes(cursor: Cursor<NodeDocument>): AsyncGenerator<NodeDocument> {
    // 1. cursor に含まれる node をイテレートしてさらに cursor を生成
    // 2. 新たな cursor で再帰的に generateDescendantNodes を呼び出す
    // 3. node 自体は yield する
    for await (const node of cursor) {
      const nextCursor = await this.getCursor(node)

      if (!isEmptyArray(nextCursor)) {
        yield* this.generateDescendantNodes(nextCursor) // 再帰的に yield する
      }

      yield node
    }
  }

  private async getCursor(node: NodeDocument): Promise<Cursor<NodeDocument>> {
    const Node = mongoose.model('Node')

    const cursor = Node
        .find({ parent: node })
        .lean()
        .cursor({ batchSize: 10 })

    return cursor
  }
}

5.0.x 系までの GROWI でも似たような実装がされていました。

ソースコードはこちら

使い方

使い方の例を紹介します。
ここではより実践向けになるように、 Writable stream に pipe してその中で node を使った処理をする例を紹介します。

ルートとなる NodeDocument を取得
Node.findOne() に条件を渡すことで、特定の NodeDocument を取得できます。

const Node = mongoose.model('Node');

const initialNode = await Node.findOne();

IterableTreeDocsFactory を初期化して generateIterable メソッドを呼ぶ
これによって AsyncGenerator iterableTree が取得できます。

const factory = new IterableTreeDocsFactory();
const iterableTree = await factory.generateIterable(initialNode);

Readable に変換
4 の Writable に pipe するために Readable に変換します。

const readableStream = Readable.from(iterableTree);

Writable で node を受け取って目的の操作をする

const writeStream = new Writable({
  objectMode: true,
  async write(node, encoding, callback) {
    // node を使った処理

    callback();
  },
  async final(callback) {
    callback();
  },
});

Stream を pipe する
最後に readableStream と writeStream を pipe で繋げることでデータが流れます。

readStream.pipe(writeStream);

妥協点

今回実装した AsyncGenerator を使った木構造ドキュメント取得処理は大きく2つの課題が残っています。

順番を制御できない

方法1では、取得する順番を Node の名前順にしたり Node の作成された順にしたりすることができません。なので、もしソートしたい場合はアプリケーション側で行う必要があります。

クエリ数 = 取得するドキュメントの数になってしまう

方法1では、generateDescendantNodes ジェネレータメソッド内で再帰的にリクエストを送っています。1 Node 取得するために 1リクエストを発行する必要があるので、MongoDB にリクエストを送ることによるリソース的・時間的なオーバーヘッドが発生してしまいます。

少数のドキュメントを取得してくる場合は問題にはなりませんが、これが大きくなってくると取り回しづらくなってしまうでしょう。

そこで次の方法2ではこれらの妥協点を克服していきます。

方法2

方法2では、$graphLookup (aggregation) を使って方法1の妥協点を改善します。

実装と解説

Aggregation ではパイプラインを組み合わせることでデータを変形してから取得できます。
それぞれのパイプラインの詳しい説明は MongoDB Aggregation pipeline をご覧ください。

$match
- $parentID を _id にもつドキュメントを次のステージに流す
- ここでマッチした全てのドキュメントに対して $graphLookup が走る
$graphLookup
- _id を起点に、_id = parent なドキュメントを探す
- このとき深さは ∞ まで
- その結果を descendants として次のステージに流す
$unwind
- descendants を展開
$replaceRoot
- 各ドキュメントの descendants の配列に変換
$project
- 必要なプロパティのみにプロジェクション
- nameLength フィールドに name の長さを格納
- $addFields でも同様の操作が可能
$sort
- nameLength (降順) のあとに name (昇順) でソート

結果として 1. のページの子孫全てが name の降順になって取得できます。

const Node = mongoose.model('Node');
const descendantNodes = await Node.aggregate([
        {
          $match: {
            _id: $parentID, // $parentID はルートとなるページの ObjectID
          },
        },
        {
          $graphLookup: {
            from: 'nodes',
            startWith: '$_id',
            connectFromField: '_id',
            connectToField: 'parent',
            as: 'descendants',
          },
        },
        {
          $unwind: '$descendants',
        },
        {
          $replaceRoot: {
            newRoot: '$descendants',
          },
        },
        {
          $project: {
            _id: 1,
            parent: 1,
            name: 1,
            nameLength: { $strLenCP: '$name' },
          },
        },
        {
          $sort: {
            nameLength: -1,
            name: 1,
          },
        },
      ]);

結果

[
   {
      "_id":"62dba2d15322d2c95410eead",
      "parent":"62dba2d15322d2c95410eeab",
      "name":"/$parent/child1/grandChild1",
      "nameLength":27
   },
   {
      "_id":"62dba2d15322d2c95410eeae",
      "parent":"62dba2d15322d2c95410eeab",
      "name":"/$parent/child1/grandChild2",
      "nameLength":27
   },
   {
      "_id":"62dba2d15322d2c95410eeab",
      "parent":"62dba2d15322d2c95410eeaa",
      "name":"/$parent/child1",
      "nameLength":15
   },
   {
      "_id":"62dba2d15322d2c95410eeac",
      "parent":"62dba2d15322d2c95410eeaa",
      "name":"/$parent/child2",
      "nameLength":15
   }
]

これで1クエリのみで目的のドキュメントを取得できました。
この方法は近々 5.1.x 系の GROWI にも反映される予定です。

テストコードはこちら

方法2のデメリット

方法2 では木構造データの探索やソートなどの計算を全て MongoDB に肩代わりしてもらいます。なので、方法1よりは MongoDB への負荷が大きくなるというデメリットがあります。

一般的に、RDBMS の stored procedures に代表されるように集計系の処理は DB 側に寄せたほうが高パフォーマンスを生むと言われているので、GROWI の最新系では方法2を採用しています。(5.1.x 系を予定)

まとめ

今回は2つの方法を使って MongoDB の木構造モデルのデータを取得してみました。ぜひ参考にしてみてください。また、より良い方法がありましたら増山の Twitter に DM で教えてください。

【MongoDB】木構造モデルの作成とドキュメント取得

目次