NoSQL のデータ モデル設計の特徴

導入

「その場に留まるためにはできるだけ早く走らなければなりません。
そしてどこかに行くには少なくともXNUMX倍の速さで走らなければなりません！」
(c) 不思議の国のアリス

少し前に講演を依頼されました アナリスト 当社は、データ モデルの設計をテーマにしています。なぜなら、長期間 (場合によっては数年間) プロジェクトに携わっていると、IT テクノロジーの世界で自分たちの周りで何が起こっているのかを見失ってしまうからです。 当社では (たまたまですが) 多くのプロジェクトが (少なくとも現時点では) NoSQL データベースを使用していないため、私の講義では、HBase の例を使用して NoSQL データベースに別途注意を払い、資料のプレゼンテーションをそれらのデータベースに向けるようにしました。使ったことのない人でも効果があります。 特に、数年前に読んだ例を使用して、データ モデル設計のいくつかの機能を説明しました。 Amandeep Khurana による記事「HB ase スキーマ設計の概要」。 例を分析するとき、主要なアイデアを聴衆によりよく伝えるために、同じ問題を解決するためのいくつかのオプションを比較しました。

最近、「何もすることがなくなったので」、理論上の計算はどれくらい実践に相当するだろうか、という質問を自分自身に問いかけました (XNUMX 月の長い週末が隔離生活であったことは特にこれに役立ちます)。 実は、この記事のアイデアはこうして生まれました。 数日間 NoSQL を使用してきた開発者は、そこから何も新しいことを学べない可能性があります (したがって、すぐに記事の半分を読み飛ばす可能性があります)。 しかし、 アナリストNoSQL をまだ詳しく扱ったことがない人にとっては、HBase のデータ モデル設計の機能についての基本的な理解を得るのに役立つと思います。

分析例

私の意見では、NoSQL データベースの使用を開始する前に、メリットとデメリットを慎重に検討し、比較検討する必要があります。 多くの場合、問題は従来のリレーショナル DBMS を使用して解決できる可能性が最も高くなります。 したがって、特別な理由がない限り NoSQL を使用しないほうがよいでしょう。 それでも NoSQL データベースを使用することに決めた場合は、ここでの設計アプローチが多少異なることを考慮する必要があります。 特に、これまでリレーショナル DBMS のみを扱ってきた人にとっては珍しいものがあるかもしれません (私の観察によれば)。 したがって、「リレーショナル」の世界では、通常、問題領域のモデル化から始めて、必要に応じてモデルを非正規化します。 NoSQL では、 データを扱うために予想されるシナリオを直ちに考慮する必要があります そして最初にデータを非正規化します。 さらに、他にも多くの違いがありますが、それについては以下で説明します。

次の「合成」問題を考えてみましょう。これについては引き続き取り組んでいきます。

何らかの抽象的なソーシャルネットワークのユーザーの友人リストのストレージ構造を設計する必要があります。 単純化するために、すべての接続が（Linkedin ではなく Instagram のように）直接行われていると仮定します。 この構造により、次のことが効果的に可能になります。

• ユーザー A がユーザー B を読むかどうかの質問に答えます (読み取りパターン)
• ユーザー B からユーザー A のサブスクリプション/サブスクリプション解除の場合に接続の追加/削除を許可する (データ変更テンプレート)

もちろん、問題を解決するには多くのオプションがあります。 通常のリレーショナル データベースでは、おそらく単純に関係のテーブルを作成し (たとえば、この「友人」を含む家族、職場などのユーザー グループを保存する必要がある場合に典型化される)、最適化することになるでしょう。アクセス速度を上げると、インデックス/パーティショニングが追加されます。 おそらく、最終的なテーブルは次のようになります。

USER_ID
友人ID

Vasya
ペチャ

Vasya
OLYA

以下、明確にし、よりよく理解するために、ID の代わりに名前を示します。

HBase の場合、次のことがわかっています。

• フルテーブルスキャンにならない効率的な検索が可能 キーによる排他的
  • 実際、多くの人にとって馴染みのある SQL クエリをそのようなデータベースに記述するのは悪い考えであるのはそのためです。 もちろん、技術的には、結合やその他のロジックを含む SQL クエリを同じ Impala から HBase に送信できますが、それがどれほど効果的になるか...

したがって、ユーザー ID をキーとして使用する必要があります。 そして、「友達の ID をどこに、どのように保存するか?」というテーマについて私が最初に考えたのは、 それらを列に格納するというアイデアかもしれません。 この最も明白で「単純な」オプションは次のようになります (これを次のように呼びます) オプション 1 (デフォルト)さらなる参照のため):

行キー
講演者

Vasya
1:ペティア
2：オーリヤ
3：ダーシャ

ペチャ
1：マーシャ
2:ヴァシャ

ここで、各行は 1 人のネットワーク ユーザーに対応します。 列には友人の数に応じて 2、1、... という名前が付けられ、列には友人の ID が格納されます。 各行の列数が異なることに注意することが重要です。 上図の例では、2 つの行には 3 つの列 (1、2、XNUMX) があり、XNUMX 番目の行には XNUMX つの列 (XNUMX と XNUMX) だけがあります。ここでは、リレーショナル データベースにはない XNUMX つの HBase プロパティを使用しました。

• 列の構成を動的に変更する機能 (友達の追加 -> 列の追加、友達の削除 -> 列の削除)
• 行が異なれば列構成も異なる場合があります

構造がタスクの要件に準拠しているかどうかを確認してみましょう。

• データの読み取り: Vasya が Olya に登録されているかどうかを理解するには、以下を引く必要があります。 行全体 RowKey = “Vasya” というキーを使用して、列の値を Olya が「見つかる」まで並べ替えます。 または、すべての列の値を反復処理して、Olya を「満たさない」と答え False を返します。
• データ編集：フレンド追加: 同様のタスクでは、減算する必要もあります 行全体 RowKey = "Vasya" キーを使用して友人の総数を数えます。 新しい友達の ID を書き留める必要がある列の番号を決定するには、この友達の合計数が必要です。
• データ変更：フレンド削除:
  • 引き算が必要 行全体 RowKey = “Vasya” キーを使用して列を並べ替えて、削除する友人が記録されている列を見つけます。
  • 次に、友人を削除した後、番号付けに「ギャップ」が生じないように、すべてのデータを XNUMX つの列に「シフト」する必要があります。

ここで、「条件付きアプリケーション」側で実装する必要があるこれらのアルゴリズムの生産性を評価してみましょう。 O-象徴主義。 仮説的なソーシャル ネットワークのサイズを n と表します。 この場合、1 人のユーザーが持つことができる友達の最大数は (n-1) です。 O シンボルの使用の枠組み内では重要ではないため、この目的ではこれ (-XNUMX) をさらに無視できます。

• データの読み取り: 行全体を減算し、制限内のすべての列を反復処理する必要があります。 これは、コストの上限推定値が約 O(n) になることを意味します。
• データ編集：フレンド追加: 友達の数を判断するには、行のすべての列を反復処理してから、新しい列を挿入する必要があります => O(n)
• データ変更：フレンド削除:
  • 追加と同様 - 制限内のすべての列を通過する必要があります => O(n)
  • 列を削除した後、列を「移動」する必要があります。 これを「正面から」実装すると、制限内で最大 (n-1) 個の操作が必要になります。 しかし、こことさらに実践的な部分では、固定数の操作に対して「擬似シフト」を実装する別のアプローチを使用します。つまり、n に関係なく、一定の時間がそれに費やされます。 この一定時間 (正確には O(2)) は、O(n) に比べて無視できます。 このアプローチを次の図に示します。「最後の」列からデータを削除する列にデータをコピーし、最後の列を削除するだけです。
    

合計すると、すべてのシナリオで O(n) の漸近的な計算複雑性が得られました。
おそらくすでにお気づきかと思いますが、ほとんどの場合、データベースから行全体を読み取る必要があり、XNUMX 件中 XNUMX 件の場合は、すべての列を調べて友人の総数を計算するだけです。 したがって、最適化の試みとして、各ネットワーク ユーザーの友人の合計数を格納する「カウント」列を追加できます。 この場合、行全体を読み取って友人の総数を計算することはできず、XNUMX つの「カウント」列だけを読み込むだけです。 重要なことは、データを操作するときに「カウント」を更新することを忘れないことです。 それ。 私たちは改善されます オプション 2 (カウント):

行キー
講演者

Vasya
1:ペティア
2：オーリヤ
3：ダーシャ
カウント：3

ペチャ
1：マーシャ
2:ヴァシャ

カウント：2

最初のオプションと比較すると、次のようになります。

• データの読み取り：「ヴァシャはオーリヤを読みますか？」という質問に対する答えを得るために。 何も変わっていない => O(n)
• データ編集：フレンド追加: 行全体を読み取ってその列を反復する必要がなくなり、「count」列などの値のみを取得できるため、新しい友人の挿入が簡素化されました。 新しい友人を挿入するための列番号をすぐに決定します。 これにより、計算量が O(1) に削減されます。
• データ変更：フレンド削除: 友人を削除する場合、この列を使用して、データを XNUMX セル左に「シフト」するときの I/O 操作の数を減らすこともできます。 ただし、削除する必要がある列を見つけるために列を反復処理する必要は依然として残るため、 => O(n)
• 一方、データを更新する場合、毎回「count」列を更新する必要がありますが、これには一定の時間がかかり、O シンボルの枠組み内では無視できます。

一般に、オプション 2 の方が若干最適であるように見えますが、どちらかというと「革命ではなく進化」に近いものです。 「革命」を起こすために必要なのは オプション 3 (列).
すべてを「ひっくり返して」みましょう：私たちが任命します 列名 ユーザーID！ 列自体に何を書くかは私たちにとってもはや重要ではありません。それを番号 1 にします (一般に、役立つものをそこに保存できます。たとえば、グループ「家族/友人/など」)。 このアプローチは、これまでに NoSQL データベースを使用した経験のない、準備ができていない「素人」を驚かせるかもしれませんが、このアプローチこそが、このタスクで HBase の可能性をより効果的に使用できるようにするものです。

行キー
講演者

Vasya
ペティア: 1
オリヤ: 1
ダーシャ: 1

ペチャ
マーシャ：1
ヴァシャ: 1

ここでは、いくつかの利点が一度に得られます。 これらを理解するために、新しい構造を分析し、計算の複雑さを見積もってみましょう。

• データの読み取り: Vasya が Olya に登録されているかどうかの質問に答えるには、「Olya」という 1 つの列を読むだけで十分です。そこにあれば、答えは True、そうでない場合は、False => O(XNUMX)
• データ編集：フレンド追加: 友達の追加: 新しい列「友達 ID」を追加するだけです => O(1)
• データ変更：フレンド削除: Friend ID 列を削除するだけです => O(1)

ご覧のとおり、このストレージ モデルの大きな利点は、必要なすべてのシナリオで XNUMX つの列のみを使用して操作し、データベースから行全体を読み取る必要がなく、さらにこの行のすべての列を列挙する必要がないことです。 そこで止めてもいいのですが...

戸惑いながらも、データベースにアクセスする際のパフォーマンスの最適化と I/O 操作の削減という道をもう少し進むこともできます。 完全な関係情報を行キー自体に直接保存したらどうなるでしょうか? つまり、userID.friendID? のような複合キーを作成します。 この場合、その行の列を読み取る必要すらありません (オプション 4(行)):

行キー
講演者

ヴァシャ・ペティア
ペティア: 1

ヴァシャ・オリャ
オリヤ: 1

ヴァシャ・ダシャ
ダーシャ: 1

ペティア・マーシャ
マーシャ：1

ペチャ・ヴァシャ
ヴァシャ: 1

明らかに、このような構造におけるすべてのデータ操作シナリオの評価は、以前のバージョンと同様に O(1) になります。 オプション 3 との違いは、データベースでの I/O 操作の効率のみです。

さて、最後の「お辞儀」。 オプション 4 では、行キーが可変長になり、パフォーマンスに影響を与える可能性があることが簡単にわかります (ここで、HBase はデータをバイトのセットとして格納し、テーブル内の行はキーによってソートされることを思い出してください)。 さらに、シナリオによっては処理が必要になる可能性があるセパレーターもあります。 この影響を排除するには、userID と friendsID のハッシュを使用できます。両方のハッシュの長さは一定であるため、区切り文字を使用せずに単純に連結できます。 すると、テーブル内のデータは次のようになります(オプション 5(ハッシュ)):

行キー
講演者

dc084ef00e94aef49be885f9b01f51c01918fa783851db0dc1f72f83d33a5994
ペティア: 1

dc084ef00e94aef49be885f9b01f51c0f06b7714b5ba522c3cf51328b66fe28a
オリヤ: 1

dc084ef00e94aef49be885f9b01f51c00d2c2e5d69df6b238754f650d56c896a
ダーシャ: 1

1918fa783851db0dc1f72f83d33a59949ee3309645bd2c0775899fca14f311e1
マーシャ：1

1918fa783851db0dc1f72f83d33a5994dc084ef00e94aef49be885f9b01f51c0
ヴァシャ: 1

明らかに、私たちが検討しているシナリオでこのような構造を扱うアルゴリズムの複雑さは、オプション 4、つまり O(1) の複雑さと同じになります。
計算の複雑さのすべての推定値を XNUMX つの表にまとめてみましょう。

友達を追加する
友人の安否を確認する
友達を削除する

オプション 1 (デフォルト)
O（N）
O（N）
O（N）

オプション 2 (カウント)
O（1）
O（N）
O（N）

オプション 3 (列)
O（1）
O（1）
O（1）

オプション 4 (行)
O（1）
O（1）
O（1）

オプション 5 (ハッシュ)
O（1）
O（1）
O（1）

ご覧のとおり、オプション 3 ～ 5 が最も望ましいと思われ、理論的には必要なすべてのデータ操作シナリオを一定時間で確実に実行できます。 私たちのタスクの条件では、ユーザーの友人全員のリストを取得するという明示的な要件はありませんが、実際のプロジェクト活動では、優れたアナリストとして、そのようなタスクが発生する可能性があることを「予測」し、 「ストローを広げてください。」 したがって、私の同情は選択肢 3 の側にあります。しかし、実際のプロジェクトでは、この要求は他の手段ですでに解決されている可能性が非常に高いため、問題全体の一般的なビジョンがなければ、この要求は行わない方が良いでしょう。最終的な結論。

実験の準備

上記の理論的議論を実際にテストしてみたいと思います。これが、長い週末の間に思いついたアイデアの目標でした。 これを行うには、データベースを使用するための説明されたすべてのシナリオにおける「条件付きアプリケーション」の動作速度と、ソーシャル ネットワーク (n) のサイズの増加に伴うこの時間の増加を評価する必要があります。 私たちが興味を持ち、実験中に測定するターゲットパラメータは、「条件付きアプリケーション」が XNUMX つの「ビジネス操作」を実行するのに費やした時間です。 「ビジネス取引」とは、次のいずれかを意味します。

• 新しい友達を XNUMX 人追加します
• ユーザー A がユーザー B の友達かどうかを確認する
• 友人を XNUMX 人削除する

したがって、最初の声明で概説した要件を考慮すると、検証シナリオは次のようになります。

• データ記録。 サイズ n の初期ネットワークをランダムに生成します。 「現実世界」に近づけるために、各ユーザーが持つ友達の数も確率変数になります。 「条件付きアプリケーション」が生成されたすべてのデータを HBase に書き込む時間を測定します。 次に、結果の時間を追加された友達の総数で割ります。これが、XNUMX つの「ビジネス操作」の平均時間を取得する方法です。
• データの読み取り。 ユーザーごとに、ユーザーが購読しているかどうかを回答する必要がある「パーソナリティ」のリストを作成します。 リストの長さ = ユーザーの友人のおよその数。チェックされた友人の半分については答えが「はい」、残りの半分については答えが「いいえ」である必要があります。 チェックは、「はい」と「いいえ」の回答が交互になる順序で実行されます (つまり、1 回ごとに、オプション 2 と XNUMX の行のすべての列を調べる必要があります)。 次に、合計スクリーニング時間をテストした友人の数で割って、被験者あたりの平均スクリーニング時間を求めます。
• データ削除。 ユーザーからすべての友達を削除します。 さらに、削除順序はランダムです (つまり、データの記録に使用された元のリストを「シャッフル」します)。 次に、合計チェック時間を削除した友人の数で割って、チェックあたりの平均時間を取得します。

成長に伴って時間がどのように変化するかを確認するには、5 つのデータ モデル オプションのそれぞれと、さまざまなサイズのソーシャル ネットワークに対してシナリオを実行する必要があります。 5 n 以内では、ネットワーク内の接続とチェックするユーザーのリストは、当然、XNUMX つのオプションすべてで同じである必要があります。
理解を深めるために、n= 5 で生成されたデータの例を以下に示します。書かれた「ジェネレーター」は、出力として XNUMX つの ID 辞書を生成します。

• 最初のものは挿入用です
• XNUMXつ目はチェック用です
• XNUMX番目 – 削除用

{0: [1], 1: [4, 5, 3, 2, 1], 2: [1, 2], 3: [2, 4, 1, 5, 3], 4: [2, 1]} # всего 15 друзей

{0: [1, 10800], 1: [5, 10800, 2, 10801, 4, 10802], 2: [1, 10800], 3: [3, 10800, 1, 10801, 5, 10802], 4: [2, 10800]} # всего 18 проверяемых субъектов

{0: [1], 1: [1, 3, 2, 5, 4], 2: [1, 2], 3: [4, 1, 2, 3, 5], 4: [1, 2]} # всего 15 друзей

ご覧のとおり、チェック対象の辞書にある 10 を超えるすべての ID は、まさに確実に False の答えが得られる ID です。 「友達」の挿入、確認、削除は、辞書に指定されている順序どおりに実行されます。

実験は Windows 10 を実行するラップトップで実行され、一方の Docker コンテナーでは HBase が実行され、もう一方のコンテナーでは Jupyter Notebook を備えた Python が実行されました。 Docker には 2 つの CPU コアと 2 GB の RAM が割り当てられました。 「条件付きアプリケーション」のエミュレーションと、テスト データを生成して時間を測定するための「パイプ」の両方のロジックはすべて Python で記述されました。 このライブラリは HBase と連携するために使用されました。 ハッピーベース、オプション 5 のハッシュ (MD5) を計算するには - hashlib

特定のラップトップの計算能力を考慮して、n = 10、30、... の起動が実験的に選択されました。 170 – 完全なテスト サイクル (すべての n のすべてのオプションのすべてのシナリオ) の合計操作時間は、多かれ少なかれ妥当であり、15 回のお茶会 (平均 XNUMX 分) に適合したとき。

ここで、この実験では主に絶対的なパフォーマンス数値を評価しているわけではないことに注意する必要があります。 異なる XNUMX つのオプションを相対的に比較しても、完全に正しいとは限りません。 ここで、n に応じた時間の変化の性質に興味があります。「テスト スタンド」の上記の構成を考慮すると、ランダムな要因やその他の要因の影響を「クリアした」時間推定値を取得するのは非常に困難であるためです (そのようなタスクは設定されていませんでした）。

実験の結果

最初のテストは、友達リストに記入するのに費やされる時間がどのように変化するかです。 その結果が下のグラフです。

オプション 3 ～ 5 では、予想どおり、ほぼ一定の「ビジネス トランザクション」時間が示されており、ネットワーク サイズの拡大やパフォーマンスの区別できない差には依存しません。
オプション 2 も一定ではありますが、パフォーマンスがわずかに悪く、オプション 2 ～ 3 と比較してほぼ正確に 5 倍です。 これは理論と相関しているため、喜ばざるを得ません。このバージョンでは、HBase との間の I/O 操作の数がちょうど 2 倍になっています。 これは、原則としてテストベンチが良好な精度を提供することを示す間接的な証拠として役立ちます。
また、オプション 1 は予想どおり、最も遅いことが判明し、ネットワークのサイズに合わせて追加するのにかかる時間が直線的に増加することがわかります。
次に、XNUMX 回目のテストの結果を見てみましょう。

オプション 3 ～ 5 も、ネットワークのサイズに関係なく、一定時間で期待どおりに動作します。 オプション 1 と 2 は、ネットワーク サイズが増加するにつれて時間が直線的に増加し、パフォーマンスも同様であることを示しています。 さらに、オプション 2 は少し遅くなることがわかりました。これは明らかに、追加の「カウント」列を校正して処理する必要があるためです。これは、n が大きくなるにつれて顕著になります。 ただし、この比較の精度は比較的低いため、結論を出すことは差し控えます。 さらに、これらの比率 (オプション 1 と 2 のどちらが速いか) は実行ごとに変化しました (依存性と「行きつ戻りつ」の性質を維持しながら)。

さて、最後のグラフは除去テストの結果です。

繰り返しますが、ここでも驚くべきことではありません。 オプション 3 ～ 5 は、一定時間で削除を実行します。
さらに、興味深いことに、オプション 4 と 5 は、前のシナリオとは異なり、オプション 3 よりもパフォーマンスが著しくわずかに劣っています。明らかに、行削除操作は、一般に論理的な列削除操作よりもコストが高くなります。

オプション 1 と 2 では、予想どおり、時間が直線的に増加します。 同時に、オプション 2 は、カウント列を「維持」するための追加の I/O 操作が原因で、オプション 1 よりも一貫して遅くなります。

実験の一般的な結論:

• オプション 3 ～ 5 では、HBase を利用するため、効率が向上します。 さらに、それらのパフォーマンスは相互に一定の割合で異なり、ネットワークのサイズには依存しません。
• オプション 4 と 5 の差は記録されませんでした。 しかし、これはオプション 5 を使用すべきではないという意味ではありません。 おそらく、テストベンチのパフォーマンス特性を考慮した、使用された実験シナリオでは検出できなかったと考えられます。
• データを使用して「ビジネス操作」を実行するために必要な時間の増加の性質は、すべてのオプションについて以前に得られた理論的計算をほぼ裏付けています。

フィナーレ

行われた大まかな実験は絶対的な真実とみなされるべきではありません。 考慮されておらず、結果を歪めている要因が多数あります (これらの変動は、ネットワーク サイズが小さいグラフで特に顕著です)。 たとえば、happybase で使用されている節約の速度、Python で作成したロジックの実装量と方法 (コードがすべてのコンポーネントの機能を最適かつ効果的に使用して作成されたとは言えません)、おそらくHBase キャッシュの機能、ラップトップ上の Windows 10 のバックグラウンド アクティビティなど。 一般に、すべての理論的計算はその妥当性が実験的に証明されていると考えることができます。 まあ、少なくとも、そのような「正面攻撃」で彼らに反論することは不可能でした。

結論として、HBase でデータ モデルの設計を始めたばかりのすべての人に対する推奨事項は、リレーショナル データベースを使用したこれまでの経験を要約し、「戒め」を覚えておくことです。

• 設計時には、ドメイン モデルではなく、データ操作のタスクとパターンから進めます。
• 効率的なアクセス (フルテーブルスキャンなし) – キーのみによる
• 非正規化
• 異なる行には異なる列を含めることができます
• スピーカーのダイナミックな構成

出所： habr.com