LoginSignup
14
10

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@ykshr

データのバージョン管理が可能な分散データベースNomsのイントロダクション

Last updated at Posted at 2016-08-21

はじめに

前回、データのバージョン管理が可能な分散データベース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つ役割があります。

また、Nomsのデータベースは、キーバリューストレージに実装することができます。ただし、データセットの保存には、楽観的並行性制御のみが用いられます。
主に、Nomsのデータベースは、次の通り実装されるみたいです。

DAGでは、ポインタでデータセットを特定することになります。例えば、データセットfooをデータセットbarにコピーするには、下記の通り指定します。

noms sync http://localhost:8000::foo http://localhost:8000::bar

Nomsでは、ポインタでデータセットを特定しているため、効率的な同期・コピーを実現しています。処理の流れとしては次の通りです。

  1. コピー元データベースhttp://localhost:8000から、データセットfooのハッシュを取得する
  2. コピー先データベースhttp://localhost:8000で、データセットfooのハッシュが存在するかチェックする
  3. 存在しないことが確認できれば、データセット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では、データタイプは主に次の目的で使われています。

  1. データの説明
    当然ですが、データタイプを定義することで、保持しているデータの説明になります。Nomsでは、チャンクがヘッダー情報を保持しているのですが、そのヘッダー情報の中にデータタイプの定義も含まれています。
  2. データ構造の定義
    Nomsでは、ユーザーが構造体を定義することができます。これにより、同じようなデータを用いているコミュニティー内での、データタイプのアドホックな標準化が可能です。
  3. データのチェック
    データタイプをベースにしたデータチェックが可能になります。
  4. スキーマ検証（未実装）
    データセットに対してコミット可能なデータタイプの制限を実装する予定です。これは、従来のデータベースにおけるスキーマ検証に類似した機能とのことです。

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_では、このデータタイプの変更と同様の操作をデータセットに対しても行う方法になります。具体的には次の通りです。

  1. データセットにSet<Number>をコミット
    下記は、すべて（過去~現在）のコミットがデータタイプSet<Number>であることを意味しています。

    
 struct Commit {
     Value: Set<Number>
     Parents: Set<Ref<Cycle<0>>>
 }

  2. データセットにSet<String>をコミット
    下記は、現在のコミットがデータタイプSet<String>であり、以前のコミットがデータタイプSet<Number>であったことを意味しています。

    
 struct Commit {
     Value: Set
     Parents: Set> |
         Ref
             Parents: Cycle<0>
         }>>
     }
 }

_Type Accretion_は、コンテナ型（データタイプ：list, set, map）に適用可能です。
また、下記の特徴があります。

  1. 既存データに変更を加える必要がない
  2. 他のデータベース製品では困難な、可逆のスキーマ変更が可能

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することが可能です。

おわり

おわりです。

14
10
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
14
10

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?