NoSQL のデータモデリングのテクニック

NoSQL の設計に関することを体系的に知りたかったため、NoSQL Data Modeling Techniques（NoSQL のデータモデリング技術）を読み、まとめてみました。（図もそのまま引用しています）

原文がそのまま日本語訳されたものはここにありました。

※おかしなところがあったらご指摘いただきたいです。

---

• NoSQL は非機能の基準（スケーラビリティ、パフォーマンス、整合性）においてよく比較される
• NoSQL は実践と理論の両面からよく研究されている。（CAP 定理 は NoSQL のシステムにも当てはまる）
• 一方で、NoSQL のデータモデリングはあまり研究されていない（リレーショナルデータベースに見られるような体系的な理論が不足している）

データモデルの観点から NoSQL のシステムを比較し、一般的なモデリングのテクニックを紹介する。

主要な NoSQL システムの「進化」についての想像:

• SQL・リレーショナルモデルは、（ずっと昔に）エンドユーザと対話をするために設計された
  • ユーザは、個別のデータ項目よりも集計されたレポート情報を知りたがった
  • ユーザが、同時実行性、整合性、データ型の妥当性を明確にコントロールできるということは期待できないため、トランザクションの保証、スキーマ、参照整合性が重視されていた
• 一方で、データベース内で集約してもらう必要がないことがある。多くの場合、整合性とデータの妥当性をアプリケーション側で制御できる。
  • さらに、データベースからこれらの機能を排除すると、パフォーマンスやスケーラビリティに極めて重要な影響を与えることがわかった。

ここからデータモデルが進化していった:

• キーバリューストア:
  • とてもシンプルでパワフル（以下のテクニックの多くがこのモデルに適用できる）
  • キーの範囲を処理する必要があるケースにあまり適用できないことが欠点
• 順序付きキーバリューモデル:
  • 上の制限を克服し、集約の性能を大幅に向上させた
  • 値のモデル化はしない（一般的にモデル化はアプリケーションがおこなう）
• ビッグテーブル型のデータベース:
  • 値を、列ファミリ、列、タイムスタンプつきのバージョン（map-of-maps-of-maps）でモデル化する
• ドキュメントデータベース:
  • ビックテーブルを改良したもので、2 つの大きな改善点がある
    • 値を任意の複雑なスキームで表現できる
    • データベースで管理されたインデックスがある（そのように実装された例がいくつかある）
• 全文検索エンジン:
  • ドキュメントデータベースに関連した（柔軟なスキーマや自動インデックスがある）種類のもの
    • おもな違い:
      • ドキュメントデータベースは、フィールドの名前でインデックスをグループ化する
      • 全文検索エンジンは、フィールドの値でインデックスをグループ化する
• グラフデータモデル:
  • 順序付きキーバリューモデルから派生したものと考えることができる
  • 依存関係を素直に表現できる
  • 階層的にモデル化する技術についても優れている
  • ドキュメントデータベースと関連がある（あるモデルを map として実装することもあれば、ドキュメントとして実装することもあるため）

NoSQL のデータモデリングについての一般的な注意点

• NoSQL のデータモデリングは、アプリケーションに特化したクエリをもとに始めることが多い
  • リレーショナルモデルは、よく利用できるデータの構造をもとに設計される（設計のテーマは 「どのような答えがあるか」）
  • NoSQL のデータモデルは、よくアプリケーション固有のアクセスパターンから設計される（設計のテーマは 「どのような質問があるか」）
• NoSQL のデータモデリングには、データ構造やアルゴリズムの深い知識が求められることが多い
• データの複製と非正規化は一般的におこなわれる
• 階層的であったりグラフのようであったりするデータのモデリング、処理について、
  • リレーショナルデータベースはこの分野には向いていない
  • グラフデータベースはこの分野を完璧に扱うことができる
  • NoSQL のほとんどがこの分野に強い

概念的なテクニック

1. 非正規化（Denormalization）

• 同じデータを複数の箇所にコピーしてクエリを簡単化・最適化すること
• 非正規化するときのトレードオフ:
  • クエリのデータ量・クエリごとの IO VS データの総量
  • 処理の複雑さ VS データの総量

適用できる対象: キーバリューストア、ドキュメントデータベース、ビッグテーブルスタイルデータベース

2. 集約（Aggregates）

• 主要なジャンルの NoSQL は何らかの形でソフトスキーマを提供している
  • キーバリューストア、グラフデータベース:
    • 値に制約がなく任意のフォーマットで構成できる
    • 複合キーを利用すると 1 つのビジネスエンティティに対して複数のレコードを変化させることができる（ユーザアカウントの場合、UserID_name、UserID_email、UserID_messages など）
  • ビッグテーブルモデル:
    • 1 つの列ファミリの中に複数の可変のカラムを持つ
    • 1 つのセルに複数のバージョンを持つ
  • ドキュメントデータベース:
    • 本質的にはスキーマレス
    • ユーザが定義したスキーマを使って入力されたデータを検証できるものがある

ソフトスキーマを使うと以下のようなことができる。

• ネストされたエンティティを使って一対多の関係を最小で表せる
• 異なるビジネスエンティティをモデル化して 1 つのドキュメントやテーブルにできる

例: 商品について表したとき

非正規化をするとアップデートにパフォーマンスと整合性の面で大きな影響を与えるため、アップデートのフローに注意する必要がある。

適用できる対象: キーバリューストア、ドキュメントデータベース、ビッグテーブルスタイルデータベース

3. アプリケーション側での結合（Application Side Joins）

• NoSQL で JOIN がサポートされることはほとんどない（設計時に JOIN しておく）
• リレーショナルデータベースではクエリの実行時に JOIN する

NoSQL でも、以下のようなときに JOIN を避けられないことがある（アプリケーション側で処理する）

• 多対多の関係（リンクでモデル化される）
• 頻繁に更新されるテーブル（問い合わせ時にアプリケーション側で JOIN するほうがよいことがある。履歴を残しておいて問い合わせ時に結合するなど）

適用できる対象: キーバリューストア、ドキュメントデータベース、ビッグテーブルスタイルデータベース、グラフデータベース

一般的なモデリング手法

4. アトミックに集約する（Atomic Aggregate）

• 多くの NoSQL でトランザクションのサポートが限定的なことがある
• 正規化せず 1 つのビジネスエンティティを 1 箇所に保存しておくことで、アトミックに更新できる

データモデリング技術としてアトミックに集約することはトランザクションの完璧なソリューションではないが、ストアが原子性やロック、テスト・アンド・セット命令をサポートする場合に適用できる。

適用できる対象: キーバリューストア、ドキュメントデータベース、ビッグテーブルスタイルデータベース

5. 列挙的できるキー（Enumerable Keys）

• 順序づけされていないキーバリューのデータモデルの最も大きな利点は、ハッシュキーによって複数のサーバーにまたがってパーティションできること
• ストレージが順序づけられたキーのサポートをしていなくても、アプリケーション側でその機能を実現できることがある

例: メールのメッセージ

• アトミックカウンタ（いくつかの NoSQL ストレージにある、シーケンシャルな ID を発行できるカウンタ）があれば、userID_messageID を複合キーとして保存しておき、最新のメッセージ ID をもとに遡ることができる。
• メッセージはバケットにまとめることができる。これによって指定した日付からメールボックスを遡ったり進んだりすることができる。

適用できる対象: キーバリューストア

6. 次元数の削減（Dimensionality Reduction）

• 多次元データをキーバリューや他の非多次元モデルにマッピングするためのテクニック
• 従来の地理情報システム: 四分木や R 木のような空間インデックスが利用されていた
  • 指定の場所を更新する必要があり、データ量が大きいと操作にコストがかかる
• もう一つの方法: 2 次元構造をトラバースし平坦化してリストにする
  • 例: Geohash（ジオハッシュ）
    • 2 次元空間を Z 字型に操作して 0、1 に符号化する
    • ビットの符号の近さを利用して地域間の距離を推定できる
    • 空間的な関係を保持したまま、順序付きキーバリューのようなプレーンなデータモデルに地理情報を保存できる

適用できる対象: キーバリューストア、ドキュメントデータベース、ビッグテーブルスタイルデータベース

7. インデックステーブル（Index Table）

• インデックスをサポートしていないストアでインデックスを利用するためのテクニック
  • BigTable スタイルのデータベースで特に重要
• アイデア: アクセスパターンに沿ったキーを持つ特別なテーブルを作成すること

例: 指定された都市からすべてのユーザーを検索するクエリは、都市をキーとするテーブルによってサポートされる

• インデックステーブルはマスターテーブルの更新ごとに、もしくはバッチモードで更新される
  • いずれにしてもパフォーマンスが悪化し、整合性の問題が起こる

適用できる対象: ビッグテーブルスタイルデータベース

8. 複合キーインデックス（Composite Key Index）

• 順序付きのキーを持つストアで非常に有効
• 複合キーと二次ソートを組み合わせると多次元インデックスを構築することができる

例: 各レコードがユーザーの統計情報であるレコードの集合

キーの部分マッチによるキーの範囲の選択をサポートしているストア（ビッグテーブルなど）であれば、特定の州や都市のレコードを反復処理する形式（州：都市：ユーザ ID）のキーを利用できる。

SELECT Values WHERE city="CA:*"
SELECT Values WHERE city="CA:San Francisco*"

適用できる対象: ビッグテーブルスタイルデータベース

9. 複合キーによる集計（Aggregation with Composite Keys）

• 複合キーはインデックス作成だけでなくグループ化にも利用できる

例: ウェブサイトを訪れたユニークユーザ数をカウントするとき（以下のクエリに似ている）

SELECT count(distinct(user_id)) FROM clicks GROUP BY site

• アイデア: ユーザごとにレコードを連ねておくことでデータをメモリに展開して（一人ひとりのイベント数は多くない）ハッシュテーブルで重複除去できる
  • 1 人のユーザに対して 1 つのエントリを用意してエントリにサイトを追加していく方法もあるが、更新は挿入よりも効率が悪い

適用できる対象: 順序付きのキーバリューストア、ビッグテーブルスタイルデータベース

10. 転置して検索して直接的に集約する（Inverted Search – Direct Aggregation）

アイデア: インデックスを使って条件を満たすデータを見つけて、オリジナルの表現やフルスキャンをしてデータを集約する

例: ユーザがサイトへ訪問したログ（ユーザ ID、ユーザのカテゴリ、アクセスされた都市、訪問したサイトが含まれる）のレコードがたくさんあり、ある基準（サイト、都市など）を満たすユーザをカテゴリごとにユニークユーザで集計したいとき

• 基準を満たすユーザの検索は、{Category -> [user IDs]}、{Site -> [user IDs]}などの転置インデックスで効率よくおこなうことができる（このようなインデックスを使って差や和をとってユーザ ID を取得できる）
• 一方で、カテゴリがたくさんあるときに、以下のような集計をするクエリは転置インデックスで効率よく処理できない

SELECT count(distinct(user_id)) ... GROUP BY category

• これに対応するには、{UserID -> [Categories]} の形の直接的なインデックスを作成し、1 つずつ順番に処理していく。

• 注意点:
  • ユーザ ID ごとにランダムにレコードを検索するのは効率が悪い
  • バッチクエリを活用するとよい
    • ユーザの集合を（異なる基準で）事前に計算しておき、フルスキャンでまとめてまとめて計算する

適用できる対象: キーバリューストア、ドキュメントデータベース、ビッグテーブルスタイルデータベース

階層的なモデリング技法

11. 木構造の集約（Tree Aggregation）

木や任意のグラフも単一のレコードやドキュメントにモデル化できる。

• 木に一度にアクセスされる場合に有効（投稿とコメント一覧を取得する場合など）
• 検索、任意のエントリへのアクセスには問題があるかもしれない
• たいていの NoSQL 実装において、更新は効率が悪い（独立したノードと比較したとき）

適用できる対象: キーバリューストア、ドキュメントデータベース

12. 隣接リスト（Adjacency Lists）

• グラフのモデリングに適した方法
• 各ノードが直接的な祖先と子孫の配列を持つ独立のレコードとしてモデル化される
• 親や子の ID でノードを検索したり、クエリごとに 1 ステップずつグラフを走査したりすることができる
• 与えられたノードの部分木全体を取得したり、深く、もしくは広く走査することには向いていない

適用できる対象: キーバリューストア、ドキュメントデータベース

13. マテリアライズド・パス（Materialized Paths）

• 木構造の再帰的な走査を避けるためのテクニック
• アイデア: 各ノードを親もしくは子の ID で h 属性化し、ノードの前に来るものと後ろにくるものを走査せずに決定する

• 階層構造をフラットなドキュメントに変換できるため、特に全文検索エンジンに役立つ
  • 上の例では、Men's shoes カテゴリが含まれるすべての製品やサブカテゴリを、単にカテゴリ名を指定した短いクエリで検索できる
• 以下のようにして保存できる:
  • ID の集合
  • ID を連結した文字列（この場合は、正規表現を利用して検索できる、以下が例）

適用できる対象: キーバリューストア、ドキュメントデータベース、検索エンジン

14. 入れ子集合（Nested Sets）

• 木構造を表現するためのモデル化するための標準的な手法
• リレーショナルデータベースで広く使われている。キーバリューストアやドキュメントデータベースにも適用できる。
• アイデア: 葉を配列に格納する。葉でないノードは最初と最後のインデックスを使って葉の範囲にマッピングする。

• 不変のデータに対してとても効率的:
  • メモリ使用量が少ない
  • 走査せずにすべての葉を取得できる
• 葉を 1 つ追加するとインデックスの更新が必要になるため、挿入と更新にかなりのコストがかかる

適用できる対象: キーバリューストア、ドキュメントデータベース

15. ネストしたドキュメントの平坦化: フィールド名に番号を振る（Nested Documents Flattening: Numbered Field Names）

• 検索エンジンは通常、フラットなドキュメント（フィールドと値の平坦なリスト）に対して利用する
• データモデリングをして、ビジネスエンティティをフラットなドキュメントにマッピングしたい
  • エンティティが複雑な内部構造（階層構造を持つ文書など）を持っているときには難しい

• この例でのビジネスエンティティは履歴書のようなもの（名前、スキル、スキルのレベルが含まれる）
• 単に Skill、Level のフィールドを持たせてモデル化してしまうと、両方のフィールドを組み合わせたクエリが間違ったマッチングになってしまうことがある（上の図）
• この問題を解決するアイデア: 各スキルと対応するレベルを専用のフィールド Skill_i、Level_i でインデックス化して同時に検索する

• この方法は入れ子の数が増えるごとにクエリが急速に複雑になるため、本当の意味でのスケーラブルとは言えない

適用できる対象: 検索エンジン

16. ネストしたドキュメントの平坦化: 近接クエリ（Nested Documents Flattening: Proximity Queries）

• 文書が入れ子になっていることによる問題は別のテクニックでも解決できる
• アイデア: 単語間の距離を制限する近接クエリを利用する
• 以下の図では、スキルとレベルが SkillAndLevet として 1 つのフィールドになっている（このクエリは Excellent と Poetry という単語が続くことを示している）

適用できる対象: 検索エンジン

17. バッチグラフ処理（Batch Graph Processing）

• neo4j のようなグラフデータベースはノードの近傍を探索したり、2、3 個のノードの関係を探索するのに優れている
• 汎用のグラフデータベースはスケールしないため、大規模のグラフを効率よくグローバルに処理できない
• グラフの分散処理は MapReduce やメッセージパッシングパターン（例）でおこなうことができる
• このアプローチにより、キーバリューストア、ドキュメントデータベース、ビッグテーブルスタイルのデータベースが大規模グラフの処理に適している

適用できる対象: キーバリューストア、ドキュメントデータベース、ビッグテーブルスタイルデータベース