はじめに
前回、データのバージョン管理が可能な分散データベースNomsをさわってみるという記事を書きました。
特に問題なく、サクッとインストールからサンプルスクリプトを動かすことができました。…が、正直、Nomsについてはよく分かりませんでした(´・ω・`)
そのため、イントロを読みましたので、自分の理解を記載しておきます。
ただ、残念ながら英語能力が無いため、誤っている内容も多々あると思います。。。
※ もし、誤りがありましたら編集リクエスト頂けると嬉しいです。
元:Git - attic-labs/noms/blob/master/doc/intro.md
Introduction to Noms
これまでの多くのデータベースシステムは、次の2つの特性を持っていました。
- ある一時点のデータのみを保持していた(リカバリ目的のデータは別として)
- 分散データベースであっても、正しいデータは1つであった
Nomsは、上記のようなこれまでのデータベースの特性に加えて、Gitなどの分散型システムの特性を取り入れたものです。
Basics
Nomsは、データを有向非巡回グラフ(DAG)のノードとしてモデル化しています。これは、Git、Bitcoin、Ethereum、IPFS、Camlistore、bupなどのシステムと同様の構成です。
また、すべてのノードにはハッシュが定義されています。ハッシュは、そのノードの値と、そのノードに到達可能なすべてのノードの値から生成されたものです。
そのため、もし、2つのノードが同じハッシュをもった場合は、そのノードに到達するまでの履歴とそのノードの値の両方が同じということです。逆に、もし、2つのノードが異なるハッシュをもった場合は、履歴もしくは値のどちらか(もしくは両方)が異なるということになります。
前回のブログと公式Gitのハッシュを比較してみます。
すると、1つ目のハッシュhshltip9kss28uu910qadq04mhk9kuko
は同じなのですが、最終的なハッシュb6953vj5tq7h0ckkv8gmfb86d8n089ab
は異なっていることが分かります。最終的なデータは同じはずなので、履歴が異なるため違う値になっているということですね。
ちなみに、Nomsを言い換えると、一つの大きなMerkle DAGとも言えるみたいです。
Databases and Datasets
前回のブログで書きましたが、Nomsのデータベースとデータセットは、Gitのリポジトリとブランチみたいな位置付けになるみたいです。このイメージをもっておくと、多少分かりやすいかと思います。
Noms | Git |
---|---|
Database | Repository |
Dataset | Branch |
Nomsでは、データベースはもっとも大きい概念であり、2つ役割があります。
- データを保存する(Content-addressable storage)
- データセットの履歴を保持する
また、Nomsのデータベースは、キーバリューストレージに実装することができます。ただし、データセットの保存には、楽観的並行性制御のみが用いられます。
主に、Nomsのデータベースは、次の通り実装されるみたいです。
- ローカルDB :LevelDB
- リモートDB :HTTP protocol
- クラウドDB :Amazon DynamoDB
- テスト用DB :memory
DAGでは、ポインタでデータセットを特定することになります。例えば、データセットfoo
をデータセットbar
にコピーするには、下記の通り指定します。
noms sync http://localhost:8000::foo http://localhost:8000::bar
Nomsでは、ポインタでデータセットを特定しているため、効率的な同期・コピーを実現しています。処理の流れとしては次の通りです。
- コピー元データベース
http://localhost:8000
から、データセットfoo
のハッシュを取得する - コピー先データベース
http://localhost:8000
で、データセットfoo
のハッシュが存在するかチェックする - 存在しないことが確認できれば、データセット
bar
としてポインタを追加する
上のコピーでは、データセットbar
は、データセットfoo
と同じデータのチャンクを参照するポインタとなります。そのため、コピー時にIOが発生しないらしいです。これは、コピー元とコピー先のデータベースが異なる場合でも同様です。既にコピー先に必要なチャンクが存在した場合は、そのデータセットのチャンクはコピーしないみたいです。
Time
Nomsでは、一度保存されたデータは、コミット処理なしに変更されることはありません。
また、Nomsのコミットは、基本的には1つの親(1つ前のコミット)をもち、マージ処理をした際は複数の親をもつことになるみたいです。
これは、前回のブログでも、Parent
として、1つ前のコミットのハッシュが表示されていましたね。
Chunks
Nomsでは、データはチャンクとして、特定の単位に分割して保存されます。
この時のチャンクの単位は、暗黙的に大きなデータにも効率的に対応可能な単位に決められるみたいです。(詳細はProlly Treesに記載)
また、チャンクの単位を明示的に指定したい場合は、Ref
タイプを用いることで、指定することができます。(Ref
タイプはTypeに記載)
Nomsでは、ハッシュを基に保存したチャンクを特定しています。このチャンクの特定に、Content-addressable storageを用いているとのことです。
Types
Nomsで定義されているデータタイプは次の通りです。
Boolean
-
Number
(arbitrary precision decimal) -
String
(utf8-encoded) -
Blob
(raw binary data) - User-defined structs
Set<T>
List<T>
Map<K,V>
- Unions:
T|U|V|...
-
Cycle<int>
(allows the creation of cyclic types) -
Ref<T>
(explicit out-of-line references)
Blobs, Sets, Lists, Maps型については、Nomsで適当なサイズに分割してチャンクを作ることが出来るため、巨大なデータを扱うことが出来るみたいです。
(詳細はProlly Trees)
一方、Strings, Numbers, Unions, Structs型については、Nomsで適当なサイズに分割してチャンクを作ることが出来ないため、適度なサイズで使うべきとのことです。
また、Ref型については、明示的にチャンクのサイズを指定することが出来ます。
Nomsでは、データタイプは主に次の目的で使われています。
- データの説明
当然ですが、データタイプを定義することで、保持しているデータの説明になります。Nomsでは、チャンクがヘッダー情報を保持しているのですが、そのヘッダー情報の中にデータタイプの定義も含まれています。 - データ構造の定義
Nomsでは、ユーザーが構造体を定義することができます。これにより、同じようなデータを用いているコミュニティー内での、データタイプのアドホックな標準化が可能です。 - データのチェック
データタイプをベースにしたデータチェックが可能になります。 - スキーマ検証(未実装)
データセットに対してコミット可能なデータタイプの制限を実装する予定です。これは、従来のデータベースにおけるスキーマ検証に類似した機能とのことです。
Refs vs Hashes
Nomsで似たような概念として、Hash
とRef
があります。
Hash
とRef
は、どちらもデータを特定するものです。
Hash
は、一般的なハッシュの使い方と同様に、データセットにコミットしたデータを特定するために使用しています。ハッシュの計算にはsha2-512を用いています。
※ ハッシュの計算は、システムのバージョンに依存しているため、将来的には変更される可能性があります。
一方、Ref
はデータタイプです。そのため、データセットに対しては、データタイプRef<T>
をコミットすることはできますが、ハッシュ値をコミットすることはできません。
んー… Ref
は、データの場所(Hash
) + データタイプみたいな感じなんですかね。
Type Accretion
Type Accretionとは、Nomsにおいて、データタイプの変更を、データセットでログとしてバージョン管理するための方法です。
Nomsでは、データタイプを変更した場合、Union
して保持するようです。
例えば、Number型で定義した項目に対して、String型のデータを投入した場合、データタイプはSet<Number|String>
となります。
1. Number型で定義 : Set<Number>
2. String型のデータを投入 : Set<Number|String>
Type Accretionでは、このデータタイプの変更と同様の操作をデータセットに対しても行う方法になります。具体的には次の通りです。
-
データセットに
Set<Number>
をコミット
下記は、すべて(過去~現在)のコミットがデータタイプSet<Number>
であることを意味しています。
struct Commit { Value: Set<Number> Parents: Set<Ref<Cycle<0>>> }
-
データセットに
Set<String>
をコミット
下記は、現在のコミットがデータタイプSet<String>
であり、以前のコミットがデータタイプSet<Number>
であったことを意味しています。
struct Commit { Value: Set Parents: Set> | Ref Value: Set Parents: Cycle<0> }>> } }
Type Accretionは、コンテナ型(データタイプ:list, set, map)に適用可能です。
また、下記の特徴があります。
- 既存データに変更を加える必要がない
- 他のデータベース製品では困難な、可逆のスキーマ変更が可能
Prolly Trees: Probabilistic B-Trees
Nomsでは、データ構造としてProlly Treesというものを使っています。
Prolly Treesは、B-Treeと似た木構造らしいのですが、木構造内で保持しているデータを基にして各ノードに格納する値の数を確率的に決定するSearch Treeみたいです。
Indexing and Searching with Prolly Trees
Prolly Treesは、下記の基準でソートされています。
- データタイプ(Boolean, Number, String) :格納された値でソート
- 上記以外のデータタイプ : ハッシュ値でソート
Nomsでは、Prolly Treesをソートしておくことでインデックス、および集合演算に用いられています。
インデックスでは、従来のデータベースと同様に、データを探索する際の計算量を削減することができます。例えば、年齢で人を検索することを想定して、データタイプMap<Number, Set<Person>>
を定義したとします。この時の計算量はO(logk(n))となります。
※ kはProlly Treesの平均幅であり一般的に64くらい(?)とのことです。
集合演算では、UnionおよびIntersectが効率的に実装されています。例えば、年齢および髪の色で人を検索することを想定して、データタイプMap<Number, Set<Person>>
およびMap<String, Set<Person>>
を定義したとします。Nomsでは、それぞれでデータを抽出した後に、Intersectすることが可能です。
おわり
おわりです。