メタデータの末尾にスキップ
メタデータの先頭に移動

 

はじめに

Shared Disk 対 Shared Nothing

分散データシステムは二つの大きなデータストレージ構造に分類されます: (1) shared disk と (2) shared nothing です。

Shared Disk 構造Shared Nothing 構造

Shared disk approaches suffer from several architectural limitations inherent in coordinating access to a single central resource. そのようなシステムでは、クラスタ内のノードの数が増加すると、調整の負荷が増大します。While some workloads can scale well with shared disk (e.g. small working sets dominated by heavy reads), most workloads tend to scale very poorly -- especially workloads with significant write load.

それは大規模な分散システムでできる唯一のやり方として知られているため、ClustrixDBはshared nothing のやり方を使用します。

Shared Nothing のアプローチ

スケール可能なshared nothing データベースシステムを構築するためには、二つの基本的な問題を解決する必要があります:

  1. 大きなデータセットを多数の個別のノードに渡って分割する。
  2. 分散データ環境で有利になる評価モデルを作成する。 

This document explains how ClustrixDB distributes data sets across a large number of independent nodes, as well as provides reasoning behind some of our architectural decisions. 

Shared Nothing 分散戦略

shared nothing 構造では、ほとんどのデータベースが以下のカテゴリに分類されます:

  1. テーブルレベルの分散。最も基本的なやり方で、テーブル全体を一つのノードに割り当てます。データベースはテーブルを分割しません。そのようなシステムはとても大きなテーブルを扱うことができません。
  2. Single-key-per-table 分散 (別名 a.k.a index colocation、あるいは single-key sharding). 最も一般的なやり方。ほとんどの分散テーブル(例えば、MySQL クラスタ、MOngoDBなど)で好まれている方法。このやり方では、テーブルは一つのキー(例えば、ユーザid)を使って複数のチャンクに分割されます。チャンクに関連する全てのインデックスがプライマリーを使って維持されます(co-located)。
  3. 独立したインデックスの分散。ClustrixDBで使われている戦略です。このやり方では、それぞれのインデックスは固有の分散を行います。広範囲の分散クエリ評価プランのサポートが要求されます。 

ClustrixDBの基本

ClustrixDBはデータの分散に微粒子を用います。以下のテーブルは私たちのシステムで使われる基本的な概念と用語を要約します。多くの他のシステムと違って、ClistrixDBはインデックスあたりの分散戦略を利用します。

分散の概念の概要

ClustrixDBの分散の概念
Representation

それぞれのテーブルは一つ以上のインデックスを持ちます。内部的には、ClustrixDBはそれらのインデックスをテーブルのrepresentations として参照します。それぞれのrepresentation は独自の分散キー (別名 区分キーあるいは破片キー)を持ちます。ClustrixDBは一つのテーブルの中のデータを切り取るために複数の独立したキーを使用することを意味します。これは、一つのテーブルのデータを切り取るために一つのキーを利用する他のほとんどの分散データベースシステムと著しく異なります。

それぞれのテーブルはプライマリキーを持つ必要があります。ユーザがプライマリキーを定義しない場合は、ClustrixDBは隠れたプライマリキーを自動的に作成するでしょう。base representation はプライマリキーで整列されたテーブル内の全てのカラムを含んでいます。Non-base representations はテーブル内のカラムのサブセットを含んでいます。

スライス

ClustrixDBはconsistent hashingを使ってそれぞれのrepresentationを論理的なslices の集合に分解します。

consistent hashingを使って、ClustrixDBはrepresentation全体をrehashする必要なく個々のsliceに分割することができます。

レプリカ

ClustrixDBは複数のデータのコピーを耐障害性と可用性のために保持します。別個のノード格納された、少なくとも二つのそれぞれの論理スライスの物理的なreplicasがあります。

ClustrixDBはrepresentationあたりのreplicaの個数の設定をサポートしています。例えば、ユーザはテーブルの基本的なrepresentationの3つのreplicaを必要とし、テーブルのほかのrepresentationには2つだけreplicaを必要とするかも知れません。

概念の例

次の例を考えます:

テーブルに次のデータを入れます:

Table: example
idcol1col2col3
11636january
21735february
31834march
41933april
52032may

Representation

ClustrixDBは上のスキーマを3つのrepresentationsに組織化するでしょう。一つはメインテーブルのためのもの(base representation、プライマリキーによって組織化されています)、それぞれインデックスキーで組織化された更に二つのrepresentationが続きます。

下の図表の黄色はそれぞれのrepresentationのordering keyを示します。二つ目のインデックスのrepresentationはプライマリキーのカラムを含んでいることに注意してください。 

Table: example

base representation

k1 representationk2 representation

primary key

idcol1col2col3
11636january
21735february
31834march
41933april
52032may

index (col2)

col2id
325
334
343
352
361

index (col3, col1)

col3col1id
april194
february172
january161
march183
may205

スライス

ClustrixDBはそれぞれのrepresentationを一つ以上の論理的なslicesに分割するでしょう。ClustrixDBをsliceする時には以下のルールが使われます:

  • representationキーにconsistent hashingアルゴリズムを適用します。 
  • それぞれのrepresentationを他に関係なく分散します。この設計の背景にある論拠の精細な検証については、single key vs. independent distribution を参照してください。
  • sliceの数は同じテーブルのrepresentationとの間で変えることができます。
  • サイズに基づいてsliceを分割します。
  • ユーザはそれぞれのrepresentationの初期sliceの数を設定するかも知れません。デフォルトでは、それぞれのrepresentationは一つのノードあたり一つのsliceです。
base representation slices
スライス 1スライス 2スライス 3
idcol1col2col3
21735february
41933april
idcol1col2col3
11636january
52032may
idcol1col2col3
31834march
k1 representation
スライス 1スライス 2
col2id
325
343
352
col2id
334
361
k2 representation
スライス 1スライス 2スライス 3slice 4
col3col2id
april194
col3col2id
february172
col3col2id
january161
march183
col3col2id
may205

レプリカ

耐障害性と可用性を保証することはデータの複数のコピーを持つことを意味します。ClustrixDBはreplicas (sliceのコピー)をクラスタ内に配置するために以下の規則を使用します。

  • それぞれの論理的なsliceは二つ以上の物理的なreplicaによって実施されます。The default protection factor is configurable at a per-representation level. 
  • Replica placement is based on balance for size, reads, and writes.
  • 同じノード上に同じsliceの二つ以上のreplicaは存在できません。
  • ClustrixDBはsliceへのwriteのsuspendやblock無しでオンラインで新しいreplicaを作成することができます。
4つのノードのクラスタのデータ分散の例
node 1node 2node 3node 4
k2 slice 1 replica A
col3col2id
april194
k2 slice 2 replica B
col3col2id
february172
base rep slice 3 replica A
idcol1col2col3
31834march
base rep slice 2 replica B
idcol1col2col3
11636january
52032may
k2 slice 3 replica A
col3col2id
january161
march183
k2 slice 1 replica B
col3col2id
april194
base rep slice 1 replica A
idcol1col2col3
21735february
41933april
k2 slice 2 replica A
col3col2id
february172
k2 slice 4 replica B
col3col2id
may205
base rep slice 2 replica A
idcol1col2col3
11636january
52032may
base rep slice 3 replica B
idcol1col2col3
31834march
k2 slice 4 replica A
col3col2id
may205
k2 slice 3 replica B
col3col2id
january161
march183
base rep slice 1 replica B
idcol1col2col3
21735february
41933april

 

一貫性のあるハッシュ

ClustrixDBはデータ分散のためにconsistent hashingを使用します。Consistent hashingによりClustrixDBは動的にデータセット全体をrehashする必要なく、動的にデータを再分散することができます。

スライス

ClustrixDBはそれぞれの分散キーを64bitの数空間にハッシュ化します。次に空間を領域に分割します。それぞれの領域はその跡で特定のsliceに所有されます。以下の表では、consistent hashingがどのように特定のキーを特定のsliceに割り当てるかを示します。 

スライスHash RangeKey Values
1min-100H, Z, J
2101-200A, F
3201-maxX, K, R

そして、ClustrixDBはデータの容量とデータアクセスのバランスのためにsliceをクラスタ内の利用可能なノードに割り当てます。

成長のための再スライス

データセットが大きくなるにつれて、ClustrixDBは自動的かつ増加的にデータセットを一度に一つ以上のsliceに再スライスします。現在のところ、再スライスの閾値をデータセットのサイズに置いています。もしsliceが最大のサイズを超えると、システムは自動的にそれを二つ以上の小さなスライスに分割するでしょう。 

例えば、スライスが事前設定された閾値を超えて成長したとしましょう:

スライスHash RangeKey ValuesSize
1min-100H, Z, J768MB
2101-200A, F, U, O, S1354MB (too large)
3201-maxX, K, R, Y800MB

rebalancerプロセスは自動的に上記の状況を検知し、スライス分割の操作をスケジュールするでしょう。システムはハッシュの領域を二つの新しいスライスに分割するでしょう:

スライスHash RangeKey ValuesSize
1min-100H, Z, J768MB
2101-200A, F, U, O, S1354MB (too large)
4101-150A, F670MB
5151-200U, O, S684MB
3201-maxX, K, R, Y800MB

システムはスライス1とスライス3を修正してはならないことに注意してください。Our technique allows for very large data reorganizations to proceed in small chunks.

Single キー 対 独立したインデックスの分散

なぜテーブルレベルの分散がとても制限されたスケーラビリティしか提供しないのかを理解するのは容易です。一つ以上のとても大きなテーブル(数百万行)に占められたスキーマを想像してみてください。そのような場合には、一つのノードがテーブル全体を提供しなければならないため、システムにノードを追加することは役に立ちません。  

なぜClustrixDBは単一キーのやり方ではなく、独立したインデックス分散を使用するのか?The answer is two-fold:
  1. Independent index distribution allows for a much broader range of distributed query plans that scale with cluster node count.
  2. Independent index distribution requires strict support within the system to guarantee that indexes stay consistent with each other and the main table. 多くのシステムではインデックスの一貫性をサポートするために要求される厳密な保証を提供しません。

二つのやり方を比較および対照するために、特定の利用例を検証してみましょう。異なるトピックがスレッドでグループ化されていて、ユーザが異なるトピックに投稿できる掲示板を考えてみましょう。この掲示板サービスは人気になり、いまや数十億のスレッドの投稿、数十万のスレッド、数百万のユーザがいます。

また、初期の掲示板の負荷は以下の二つのアクセスパターンから成ると仮定します。

  1. 特定のスレッドの全ての投稿はpost id順に扱います。
  2. 特定のユーザについて、ユーザごとに最新の10の投稿を扱うとします。

アプリケーション内の全ての投稿から成る以下のような簡易化したスキーマの一つのとても大きなテーブルを想像できるかもしれません。

Single キーのアプローチ

単一キーのやり方では、どのキーを投稿テーブルを分散するために選択すればいいのかというジレンマに遭遇します。以下の表で分かるように、両方の場合において良いスケーラビリティになるような一つのキーを選択することができません。 

分散キー利用例1: スレッドに投稿する利用例2: ユーザによって投稿されたトップ10
thread_idthread_idを含むqueryが良く機能するでしょう。Requests for a specific thread get routed to a single node within the cluster. スレッドと投稿の数が増えた場合は、容量を増やすために単純にクラスタにノードを追加します。thread_idを含まないクエリ、例えば特定のユーザの最新10の投稿、はthread_postテーブルを含む全てのノードで評価しなければなりません。言い換えると、関係する投稿が全てのノードにありえるため、システムはクエリを broadcast しなければなりません。
user_iduser_idを含まないクエリはbroadcastになります。As with use case 2 w/ thread_id key, we lose system scalability when we have to broadcast.user_idを含むクエリは一つのノードへ向かいます。それぞれのノードはユーザの整列された投稿のセットを持っているでしょう。システムはbroadcastせずにスケールすることができます。

One possibility with such a system could be to maintain a separate table which includes a user_id and a posted_on columns. We can then have the application manually maintain this index table.

しかしこのことは、今度はアプリケーションが複数のwriteを発行し、二つのテーブル間のデータの整合性の責任を持つ必要があることを意味します。そして、もっとインデックスを追加する必要がある場合を想像してみてください。このやり方は単純にはスケールしません。データベースの利点の一つは自動的なインデックスの管理です。 

独立した依存インデックスキーのアプローチ

ClistrixDBは両方の利用方法を満たす独立した分配を自動的に作成するでしょう。DBAはthread_idによってbase representation(プライマリキー)、user_idによってセカンダリキーの分配を指定することができます。システムは完全なACIDを保証してテーブルとセカンダリインデックスの両方を自動的に管理するでしょう。 

更に詳しい説明はEvaluation Model の章を調べてください。 

キャッシュの効率

データの耐障害性のためにマスタースレイブのペアを利用する他のシステムとは異なり、ClustrixDBは前述したようにデータをより細やかな方法でデータを配布します。私たちの方法では、readをセカンダリのrreplicaに送信しないことによりClustrixDBのキャッシュ効率を上げることができます。

次の例を考えます:二つのノードと二つのスライス AとB、それらのセカンダリコピーのA'とB'があると仮定します。 

両方のコピーから読み込むプライマリコピーからのみ読み込む
ノード 1ノード 2
AB
B'A'
ノード 1ノード 2
AB
B'A'

プライマリとセカンダリのreplicaの両方からの読み込みを許可した場合、それぞれのノードはAとBの両方の内容をキャッシュしなければなりません。ノードあたりのキャッシュを32GBと仮定すると、システムの総有効キャッシュは32GBになります。.

プライマリのreplicaからの読み込みのみに制限することで、ノード1はAだけを担当し、ノード2はBだけを担当します。ノードあたりのキャッシュを32Gと仮定すると、総有効キャッシュfootprintは64GBあるいは反対のモデルの2倍になります。

分散キーの不均衡

いくつかのデータセットによって、ユニークではないセカンダリインデックスのキー分散がクラスタを不均衡にすることがありえます。そのような場合、ClustrixDBは自動的に分散の不均衡を検知し、オンラインの再分配アクションをスケジュールします。 

セカンダリキーの不均衡の例
ノード 1ノード 2ノード 3
スライス 1
col1id
Jan1
Jan5
Jan3
Jan8
Jan6
Feb9
スライス 2
col1id
Mar4
Apr2
スライス 3
col1id
Sep10
Dec11
Nov43

上の例では、一つの値(Jan)がインデックスの全ての値の50%を代表していると分かります。デフォルトでは、ClustrixDBはrepresentationのための分散キーとしてインデックスされたカラムから開始します。しかしながら、データセットが一つの値に偏っているため、スライス1は不均衡な数のエントリを取得します。 

The rebalancer process will notice that the difference between the minimum slice size per hash range is 10MB while the maximum size is 30MB. そのような状況はデータセットの間でデータの不均衡を示していて、それはクラスタ間で駄目なデータ分散を引き起こします。

スライスハッシュrangeスライスサイズスライスサイズ / ハッシュ range
1min-100100MB10MB
2101-200300MB30MB
3200-max150MB15MB

上の状況を直すために、リバランサはrepresentationのリディストビュート操作をスケジュールするでしょう。それはプライマリキーからrepresentation分散キーへのキーの追加で始まります。Since the primary key must be unique by definition, we know that a balanced distribution is possible for the dataset provided we consume enough of the primary key.

例では、リバランサはidカラムを分散キーに追加するでしょう。今度は (col1, id)をハッシュしたので、スライスに渡ってデータの分散がもっとよくなります。

セカンダリキーの不均衡の修正
ノード 1ノード 2ノード 3
スライス 1
col1id
Jan1
Jan5
Jan6
Feb9
スライス 2
col1id
Mar4
Apr2
Jan3
スライス 3
col1id
Sep10
Dec11
Jan8
Nov43
TOP
inserted by FC2 system