MongoDBで再帰的(階層的)データ構造を実現する方法
MongoDBでhierarchical(階層的)なデータ構造を実現することが出来るか気になったので調べてみた
公式にちょうどMongoDBで木構造のデータモデルを実現する方法のドキュメントがあり、何パターンか方法があるようだったのでそれぞれ試してみる
評価ポイント
メンテナンス性
ツリーの子要素を変更した場合他にも変更が発生するか
変更が発生する場合変更コストはどれくらいか, またコストは定量的に評価出来るか
要素の追加は簡単か
またツリーの一部の要素を削除することは可能か
子要素を全て一階層上の親要素に書き換える
階級自体は消えないが別の名前に変える
子要素の一部を同階級の新しい要素の子要素として移動するなどで対応可能か
また子要素を再帰的に変更する必要があるか等
パフォーマンス
期待したパフォーマンスは出るか
想定データ件数、同時接続数で性能劣化しないか
他システムとの相互運用性はどうか
RDBMSとの相互運用性
RDBMSのデータと関連付けられるか
親参照パターン
各ドキュメントに親要素への参照を設定し再帰的に取得するパターン
ツリーの再帰的な取得は $graphLookup を使う
code:bash
db.categories.insert( { _id: 1, name: "Books", parent: null } )
WriteResult({ "nInserted" : 1 })
db.categories.insert( { _id: 2, name: "Programming", parent_id: 1 } )
WriteResult({ "nInserted" : 1 })
db.categories.insert( { _id: 3, name: "Languages", parent_id: 1 } )
WriteResult({ "nInserted" : 1 })
db.categories.insert( { _id: 4, name: "Databases", parent_id: 2 } )
WriteResult({ "nInserted" : 1 })
db.categories.insert( { _id: 5, name: "dbm", parent_id: 4 } )
WriteResult({ "nInserted" : 1 })
db.categories.insert( { _id: 6, name: "MongoDB", parent_id: 4 } )
WriteResult({ "nInserted" : 1 })
db.categories.aggregate([
{
$graphLookup: {
from: "categories",
startWith: "$parent_id",
connectFromField: "parent_id",
connectToField: "_id",
as: "hierarchy"
}
}
])
{ "_id" : 0, "name" : "MongoDB", "parent_id" : 2, "hierarychy" : { "_id" : 4, "name" : "Programming", "parent_id" : 5 }, { "_id" : 5, "name" : "Books", "parent" : null }, { "_id" : 2, "name" : "Databases", "parent_id" : 4 } } { "_id" : 1, "name" : "dbm", "parent_id" : 2, "hierarychy" : { "_id" : 4, "name" : "Programming", "parent_id" : 5 }, { "_id" : 5, "name" : "Books", "parent" : null }, { "_id" : 2, "name" : "Databases", "parent_id" : 4 } } { "_id" : 5, "name" : "Books", "parent" : null, "hierarychy" : }
このようにgraphLookupで再帰的にドキュメントを取得することが出来る
from コレクション名
startWith ツリーの検索を開始するフィールドのexpression
connectFromField 再帰的に親と子関係を結ぶ際の繋ぎ元になるフィールド
connectToField 再帰的に親と子関係を結ぶ際の繋ぎ先になるフィールド
デフォルトでは全件取得になるのでレコードを絞る場合は$matchを使う
code:bash
db.categories.aggregate([
{ $match: { "name": "MongoDB" } },
{ $graphLookup: {
from: "categories",
startWith: "$parent_id",
connectFromField: "parent_id",
connectToField: "_id",
as: "hierarchy",
maxDepth: 3,
depthField:
"numConnections"
}
}
])
{
"_id" : 6.0,
"name" : "MongoDB",
"parent_id" : 4.0,
"hierarychy" : [
{
"_id" : 1.0,
"name" : "Books",
"parent" : null,
"numConnections" : NumberLong(2)
},
{
"_id" : 2.0,
"name" : "Programming",
"parent_id" : 1.0,
"numConnections" : NumberLong(1)
},
{
"_id" : 4.0,
"name" : "Databases",
"parent_id" : 2.0,
"numConnections" : NumberLong(0)
}
]
}
nameで指定されたレコードを1件取得し、そのレコードを元に再帰的に親のドキュメントを取得していることが分かる
Mongo 3.4からgraphLookupクエリが出来るようになったので要素に直接の親要素と子要素のIDを持っていればどちらの方向からもgraphLookupで辿ることが出来る
要は3.4からドキュメント型DBでありながらグラフDB的な用途にも使えるようになった。同時にグラフ型DBの弱点であったメンテナンスのしづらさやクエリの複雑もMongoDB上で構築されることで使いやすくなっているとのこと。
子要素を再帰的に取得する場合は以下のようにconnectFromFieldとconnectToFieldを先程と逆にする
code:bash
db.categories.aggregate([
{
$graphLookup: {
from: "categories",
startWith: "$parent_id",
connectFromField: "_id",
connectToField: "parent_id",
as: "hierarchy"
}
}
])
/* 1 */
{
"_id" : 1.0,
"name" : "Books",
"parent" : null,
"hierarchy" : []
}
/* 2 */
{
"_id" : 2.0,
"name" : "Programming",
"parent_id" : 1.0,
"hierarchy" : [
{
"_id" : 6.0,
"name" : "MongoDB",
"parent_id" : 4.0
},
{
"_id" : 2.0,
"name" : "Programming",
"parent_id" : 1.0
},
{
"_id" : 5.0,
"name" : "dbm",
"parent_id" : 4.0
},
{
"_id" : 3.0,
"name" : "Languages",
"parent_id" : 1.0
},
{
"_id" : 4.0,
"name" : "Databases",
"parent_id" : 2.0
}
]
}
/* 3 */
{
"_id" : 3.0,
"name" : "Languages",
"parent_id" : 1.0,
"hierarchy" : [
{
"_id" : 5.0,
"name" : "dbm",
"parent_id" : 4.0
},
{
"_id" : 6.0,
"name" : "MongoDB",
"parent_id" : 4.0
},
{
"_id" : 4.0,
"name" : "Databases",
"parent_id" : 2.0
},
{
"_id" : 2.0,
"name" : "Programming",
"parent_id" : 1.0
},
{
"_id" : 3.0,
"name" : "Languages",
"parent_id" : 1.0
}
]
}
/* 4 */
{
"_id" : 4.0,
"name" : "Databases",
"parent_id" : 2.0,
"hierarchy" : [
{
"_id" : 5.0,
"name" : "dbm",
"parent_id" : 4.0
},
{
"_id" : 6.0,
"name" : "MongoDB",
"parent_id" : 4.0
},
{
"_id" : 4.0,
"name" : "Databases",
"parent_id" : 2.0
}
]
}
/* 5 */
{
"_id" : 5.0,
"name" : "dbm",
"parent_id" : 4.0,
"hierarchy" : [
{
"_id" : 5.0,
"name" : "dbm",
"parent_id" : 4.0
},
{
"_id" : 6.0,
"name" : "MongoDB",
"parent_id" : 4.0
}
]
}
/* 6 */
{
"_id" : 6.0,
"name" : "MongoDB",
"parent_id" : 4.0,
"hierarchy" : [
{
"_id" : 5.0,
"name" : "dbm",
"parent_id" : 4.0
},
{
"_id" : 6.0,
"name" : "MongoDB",
"parent_id" : 4.0
}
]
}
ただこの状態だとフラットに階層が表現されているので見辛い
以下の要領でViewを作りネストする
code:bash
db.createView('viewCategoryDepth1', 'categories', [
{ $graphLookup: {
from: "categories",
startWith: "$_id",
connectFromField: "_id",
connectToField: "parent_id",
maxDepth: 0,
as: "Children"
}
}
]);
# Programming以下をネストして取得
db.categories.aggregate([
{$match: {"name": "Programming"}},
{
$graphLookup: {
from: "viewCategoryDepth1",
startWith: "$_id",
connectFromField: "_id",
connectToField: "parent_id",
as: "Children",
maxDepth: 0
}
}
])
# 結果 viewで入れ子にしたので2レベルまでネストされた結果が表示される
/* 1 */
{
"_id" : 2.0,
"name" : "Programming",
"parent_id" : 1.0,
"Children" : [
{
"_id" : 4.0,
"name" : "Databases",
"parent_id" : 2.0,
"Children" : [
{
"_id" : 6.0,
"name" : "MongoDB",
"parent_id" : 4.0
},
{
"_id" : 5.0,
"name" : "dbm",
"parent_id" : 4.0
}
]
}
]
}
# さらにviewを作って入れ子にすれば深い階層の要素もネストして取得出来る
db.categories.insert(
{
"_id" : 7,
"name" : "Mastering MongoDB",
"parent_id" : 6
})
db.categories.insert(
{
"_id" : 8,
"name" : "Head First Mongo",
"parent_id" : 6
})
db.createView('viewCategoryDepth2', 'categories', [
{ $graphLookup: {
from: "viewCategoryDepth1",
startWith: "$_id",
connectFromField: "_id",
connectToField: "parent_id",
maxDepth: 0,
as: "Children"
}
}
]);
db.categories.aggregate([
{$match: {"name": "Programming"}},
{
$graphLookup: {
from: "viewCategoryDepth2",
startWith: "$parent_id",
connectFromField: "_id",
connectToField: "parent_id",
as: "Children",
maxDepth: 0
}
}
])
# この場合は3階層の入れ子なので3レベルまでネストされて取得出来る
/* 1 */
{
"_id" : 2.0,
"name" : "Programming",
"parent_id" : 1.0,
"Children" : [
{
"_id" : 4.0,
"name" : "Databases",
"parent_id" : 2.0,
"Children" : [
{
"_id" : 6.0,
"name" : "MongoDB",
"parent_id" : 4.0,
"Children" : [
{
"_id" : 8.0,
"name" : "Head First Mongo",
"parent_id" : 6.0
},
{
"_id" : 7.0,
"name" : "Mastering MongoDB",
"parent_id" : 6.0
}
]
},
{
"_id" : 5.0,
"name" : "dbm",
"parent_id" : 4.0,
"Children" : []
}
]
}
]
}
親要素を再帰的にネストして取得する場合同様にViewをネストが必要なレベル分作成する
code:bash
# 同様に
db.createView('viewCategoryParent1', 'categories', [
{ $graphLookup: {
from: "categories",
startWith: "$parent_id",
connectFromField: "parent_id",
connectToField: "_id",
maxDepth: 0,
as: "Parent"
}
}
]);
db.createView('viewCategoryParent2', 'categories', [
{ $graphLookup: {
from: "viewCategoryParent1",
startWith: "$parent_id",
connectFromField: "parent_id",
connectToField: "_id",
maxDepth: 0,
as: "Parent"
}
}
]);
# name: MongoDBから再帰的に取得
db.categories.aggregate([
{$match: {"name": "MongoDB"}},
{
$graphLookup: {
from: "viewCategoryParent2",
startWith: "$parent_id",
connectFromField: "parent_id",
connectToField: "_id",
as: "Parent",
maxDepth: 0
}
}
])
# 結果
/* 1 */
{
"_id" : 6.0,
"name" : "MongoDB",
"parent_id" : 4.0,
"Parent" : [
{
"_id" : 4.0,
"name" : "Databases",
"parent_id" : 2.0,
"Parent" : [
{
"_id" : 2.0,
"name" : "Programming",
"parent_id" : 1.0,
"Parent" : [
{
"_id" : 1.0,
"name" : "Books",
"parent" : null
}
]
}
]
}
]
}
またグラフ構造なので親を複数持つ事も可能
code:bash
# ドキュメント作成
db.employees.insertMany([
{"_id": 1, "name": "Aisha", "manager_ids": null},
{"_id": 2, "name": "Josh", "manager_ids": 1}, {"_id": 3, "name": "Andrew", "manager_ids": 1}, {"_id": 4, "name": "Emery", "manager_ids": 2, 3}, ])
# ネスト用View作成
db.createView('viewEmployeeParent1', 'employees', [
{ $graphLookup: {
from: "employees",
startWith: "$manager_ids",
connectFromField: "manager_ids",
connectToField: "_id",
maxDepth: 0,
as: "managers"
}
}
]);
# クエリ
db.employees.aggregate([
{$match: {"name": "Emery"}},
{
$graphLookup: {
from: "viewEmployeeParent1",
startWith: "$manager_ids",
connectFromField: "manager_ids",
connectToField: "_id",
as: "managers",
maxDepth: 0
}
}
])
# 結果
/* 1 */
{
"_id" : 4.0,
"name" : "Emery",
"manager_ids" : [
2.0,
3.0
],
"managers" : [
{
"_id" : 3.0,
"name" : "Andrew",
"manager_ids" : [
1.0
],
"managers" : [
{
"_id" : 1.0,
"name" : "Aisha",
"manager_ids" : null
}
]
},
{
"_id" : 2.0,
"name" : "Josh",
"manager_ids" : [
1.0
],
"managers" : [
{
"_id" : 1.0,
"name" : "Aisha",
"manager_ids" : null
}
]
}
]
}
子参照パターン
親要素が子要素のIDを保持するパターン。サブツリーで変更が発生しないような場合に向いている
またノードが複数の親を持つような場合にも向いている
code:bash
db.categories.insert( { _id: "MongoDB", children: [] } )
db.categories.insert( { _id: "dbm", children: [] } )
db.categories.insert( { _id: "Languages", children: [] } )
db.categories.insert( { _id: "Books", children: "Programming" } ) # ある要素の直接の子要素を取得する
db.categories.findOne( { _id: "Databases" } ).children
# ある要素の全ての子要素を再帰的に取得
db.categories.aggregate([
{ $match: {"_id": "Databases"}},
{ $graphLookup: {
from: "categories",
startWith: "$children",
connectFromField: "children",
connectToField: "_id",
as: "childrens"
}
}
])
/* 1 */
{
"_id" : "Programming",
"children" : [
"Databases",
"Languages"
],
"childrens" : [
{
"_id" : "dbm",
"children" : []
},
{
"_id" : "MongoDB",
"children" : []
},
{
"_id" : "Languages",
"children" : []
},
{
"_id" : "Databases",
"children" : [
"MongoDB",
"dbm"
]
}
]
}
基本的には親要素を参照するパターンと同じだがどちらから参照するかという違い
Pros
親参照と同じようにどちらの方向へも遡れる
Cons
子要素の参照を親が持つので子を作成した後にそのIDで親を更新する必要がある
祖先要素の配列を持つパターン
Ancestor(祖先要素)をドキュメントで持つパターン. 最上位までの親要素のIDを各ドキュメントが持つ
Ancestorにインデックスを張れば親要素を遡るのと子孫要素を辿るのを効率的に行える
似たものでMaterialized Pathパターンというのもある
code:bash
db.categories.insert( { _id: "Programming", ancestors: "Books" , parent: "Books" } ) db.categories.insert( { _id: "Books", ancestors: , parent: null } )
# Programmingの子要素を全件取得
db.categories.find( { ancestors: "Programming"} )
# Programmingの直接の子要素(1階層)のみ取得
db.categories.find( { ancestors: "Programming", parent: "Programming" } )
Materialized Pathsパターンよりは若干パフォーマンスでは劣るが直観的に分かりやすい
Pros
直観的に理解しやすい
クエリが簡単
Cons
親要素での変更が生じると子孫要素全てに影響する
例: 親要素を別のIDに変更→子孫要素のancestorのIDも全て変更
Materialized Pathsパターン
ドキュメントに直接文字列でドキュメントまでのパスを保持するパターン
code:bash
db.categories.insert( { _id: "Books", path: null } )
db.categories.insert( { _id: "Programming", path: ",Books," } )
db.categories.insert( { _id: "Databases", path: ",Books,Programming," } )
db.categories.insert( { _id: "Languages", path: ",Books,Programming," } )
db.categories.insert( { _id: "MongoDB", path: ",Books,Programming,Databases," } )
db.categories.insert( { _id: "dbm", path: ",Books,Programming,Databases," } )
# 全件取得
db.categories.find().sort( { path: 1 } )
# Programmingの子要素を全件取得
db.categories.find( { path: /,Programming,/ } )
# Programmingの親要素を全件取得
# => Programmingのpathをカンマで分割
文字列の正規表現での一致なのでインデックスを使用しつつ部分的な子要素から末尾の子要素まで効率的に取得出来る
Pros
文字列自体に対する検索なのでRDBMSでも実現可能
子要素の取得も効率的に行える
Cons
Pathの維持コスト
整合性を維持しつつ親要素からの順序を保証するにはソート出来る必要がある
親要素の更新が発生した際その子孫要素全てが影響を受ける
Nested Setsパターン
https://gyazo.com/4d857e6ffff3a963c1dcdb4a6c5828ac
このように順繰りにツリーを辿っていきleftとrightを設定する
code:bash
db.categories.insert( { _id: "Books", parent: 0, left: 1, right: 12 } )
db.categories.insert( { _id: "Programming", parent: "Books", left: 2, right: 11 } )
db.categories.insert( { _id: "Languages", parent: "Programming", left: 3, right: 4 } )
db.categories.insert( { _id: "Databases", parent: "Programming", left: 5, right: 10 } )
db.categories.insert( { _id: "MongoDB", parent: "Databases", left: 6, right: 7 } )
db.categories.insert( { _id: "dbm", parent: "Databases", left: 8, right: 9 } )
# Databases以下の子要素を全て取得
var databaseCategory = db.categories.findOne( { _id: "Databases" } );
db.categories.find( { left: { $gt: databaseCategory.left }, right: { $lt: databaseCategory.right } } );
サブツリーを辿っていくのに適しているデータ構造
ただツリーの要素を変更すると全てに対して変更が発生するので変更コストが高い
なのでツリー構造が変化しない静的なツリーの場合は向いている
のビデオで紹介されている通りMongoDBはRDSMSとKVSの中間あたりの機能性とパフォーマンス/スケーラビリティという位置づけ
RDBMSほどの汎用性と機能性はないがスケールし十分高速に動作する
MongoDB 3.4でグラフ関連の機能が追加されたことにより従来の親要素や子要素、祖先IDを配列で持つ、Nested Sets, Materialized Pathを使わなくてもグラフ表現でメンテナビリティを維持しつつ, またMongoDBであることで運用性も維持しつつ現実的に再帰的構造を表現出来るようになった
パフォーマンス調査
graphLookup のパフォーマンスがネストされた状態でどれくらいスループットが出るか調査
データ追加
ツリー構造でInsertするデータ構造
レベル→9レベル程度
件数→200万件程度
割合
レベル1: 6個
レベル2: レベル1にそれぞれ6個程度ずつぶらさがる
レベル3: レベル2にそれぞれ6個程度ずつぶらさがる
以下同でレベル9まで
6^9 = 約200万件
Elixirでベンチマーク
200万件程度のツリー構造を持つデータセットに対してリクエストする
以下のスクリプトでseedデータ生成
code:python
from pymongo import MongoClient
from faker import Faker
client = MongoClient('mongodb://root:root@localhost:27017/')
fake = Faker()
db = client.test
data = []
id = 0
leafs = 6
max_level = None
def generate_tree(parent_id, levels):
global id
global max_level
if levels == 1:
return
if max_level == None:
max_level = levels
for i in range(leafs):
id = id + 1
if levels == max_level:
data.append({'_id': id, 'name': fake.name(), 'parent_id': None})
else:
data.append({'_id': id, 'name': fake.name(),
'parent_id': parent_id})
generate_tree(id, levels - 1)
if __name__ == "__main__":
generate_tree(None, 9)
db.trees.insert_many(data)
python seed.py
Elixirでiexからベンチマークする
code:elixir:mix.exs
defp deps do
[
{:mongodb, ">= 0.0.0"},
{:poolboy, ">= 0.0.0"},
{:benchee, "~> 1.0"}
# {:dep_from_hexpm, "~> 0.3.0"},
]
end
code:bash
$ mix deps.get
code:elixir
iex> {:ok, conn} = Mongo.start_link(url: "mongodb://localhost:27017/test", username: "root", password: "root", auth_source: "admin")
iex> > Benchee.run(%{"mongo" => func}) |> Benchee.Formatters.Console.format Operating System: Linux CPU Information: AMD Ryzen 7 1700X Eight-Core Processor
Number of Available Cores: 16
Available memory: 31.37 GB
Elixir 1.7.4
Erlang 22.0.2
Benchmark suite executing with the following configuration:
warmup: 2 s
time: 5 s
memory time: 0 ns
parallel: 1
inputs: none specified
Estimated total run time: 7 s
Benchmarking mongo...
Name ips average deviation median 99th %
mongo 1.14 K 878.12 μs ±14.50% 853.04 μs 1343.78 μs
[
["",
"\nName ips average deviation median 99th %\n",
"mongo 1.14 K 878.12 μs ±14.50% 853.04 μs 1343.78 μs\n"]
8階層200万件のデータセットで最下層から最上位まで遡って取得する場合にも1140 IPS, 中央値が1ms以下と高速にLookup出来ることが分かった
ツリー型データ構造を表現する手段としてMongoDBを採用するPros/Cons
Pros
運用性
各所で既に実績のあるMongoDB
クエリ形式がJSONライクで専用のグラフDBを使い複雑なクエリを書くよりは分かりやすい
相互運用性
各種システムに少なくともMongoDBのライブラリは必ずある
ただRDBMSとのハイブリッド構成はライブラリ側/もしくは自力での対応になる
パフォーマンス
200万件程度のデータセットで1ms以下で8階層レベルのネストも割と安定してLookup出来た
RDBMSで非正規型データ構造を持ちトリガーを駆使してデータを更新したり正規化データでJOINするよりは、運用コストとパフォーマンスというトレードオフでのバランスはそこそこ取れているように思える
Cons
AWSで運用する場合はAWS Documnet DBが候補に上がるが, AWS Document DBでは2019-07-30現在$graphLookup がサポートされていない
Mongo DB公式がサービスを提供しているMongo DB Atlasなら3.6に対応しているので出来る
そこまでDocument DBと料金的な違いはないがMongo DBのAPIをフルに使えるのでgraphLookupも出来る
ただAWS外のサービスをAWSに入れる形になるので多少構築や料金支払いなど運用性は劣る
Terraform のカスタムプロバイダでMongo DB Atlasに対応したものがあるので多少マシか
GUI管理ツールで使いやすい物がRDBMS程はない
MongoDB専用のものは有料というものも多い (MongoDB Compass, MongoDB plugin for DBEaver EE, Studio 3Tなど)
基本的にはMongoDB公式のMongoDB Compassがよい
ただElectronだからか重い
クエリを直接打てるコンソールがないのでクエリを直接コピペなどして試しづらい
Robo 3TもOSSだがそこそこ使いやすい
MongoDB Compassよりは軽い
クエリを直接打てるコンソールがある
ほとんどの場合において全てのデータをMongoDBに置くというようなことはせず、ログや非構造型データをメインに置くためRDBMSとのハイブリッド構成になる
RDBMSのレコードとドキュメントとのリレーションを抽象化されたORM側で設定出来ると実装しやすい(laravel-mongoなどは出来る)
弱い一貫性モデルのためトランザクショナルな処理は実装に気をつける必要がある
ロック
どうしてもトランザクショナルに扱いたい場合はcompensational pattern(補償処理パターン)などを検討する必要がある, 例: Sagaパターンなど
そもそもそのようなデータはMongoDBで扱わずにRDBMSで処理するなど