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

# はじめに

前回、[データのバージョン管理が可能な分散データベースNomsをさわってみる](http://qiita.com/ykshr/items/ac470aa828703e7578e8)という記事を書きました。

特に問題なく、サクッとインストールからサンプルスクリプトを動かすことができました。…が、正直、Nomsについてはよく分かりませんでした(´・ω・`)
そのため、イントロを読みましたので、自分の理解を記載しておきます。
ただ、残念ながら英語能力が無いため、誤っている内容も多々あると思います。。。
※ もし、誤りがありましたら編集リクエスト頂けると嬉しいです。

元：[Git - attic-labs/noms/blob/master/doc/intro.md](https://github.com/attic-labs/noms/blob/master/doc/intro.md)


# Introduction to Noms

これまでの多くのデータベースシステムは、次の2つの特性を持っていました。

* ある一時点のデータのみを保持していた（リカバリ目的のデータは別として）  
* 分散データベースであっても、正しいデータは1つであった  

Nomsは、上記のようなこれまでのデータベースの特性に加えて、Gitなどの分散型システムの特性を取り入れたものです。

## Basics

Nomsは、データを[有向非巡回グラフ](https://ja.wikipedia.org/wiki/%E6%9C%89%E5%90%91%E9%9D%9E%E5%B7%A1%E5%9B%9E%E3%82%B0%E3%83%A9%E3%83%95)（DAG）のノードとしてモデル化しています。これは、Git、[Bitcoin](https://bitcoin.org/en/)、[Ethereum](https://www.ethereum.org/)、[IPFS](https://ipfs.io/)、[Camlistore](https://camlistore.org/)、[bup](https://bup.github.io/)などのシステムと同様の構成です。

また、すべてのノードにはハッシュが定義されています。ハッシュは、そのノードの値と、そのノードに到達可能なすべてのノードの値から生成されたものです。
そのため、もし、2つのノードが同じハッシュをもった場合は、そのノードに到達するまでの履歴とそのノードの値の両方が同じということです。逆に、もし、2つのノードが異なるハッシュをもった場合は、履歴もしくは値のどちらか（もしくは両方）が異なるということになります。

[前回のブログ](http://qiita.com/ykshr/items/ac470aa828703e7578e8#%E3%82%B3%E3%83%9F%E3%83%83%E3%83%88%E3%83%AD%E3%82%B0%E3%81%AE%E8%A1%A8%E7%A4%BA)と[公式Git]((https://github.com/attic-labs/noms/blob/master/doc/go-tour.md#dataset))のハッシュを比較してみます。
すると、1つ目のハッシュ`hshltip9kss28uu910qadq04mhk9kuko`は同じなのですが、最終的なハッシュ`b6953vj5tq7h0ckkv8gmfb86d8n089ab`は異なっていることが分かります。最終的なデータは同じはずなので、履歴が異なるため違う値になっているということですね。

ちなみに、Nomsを言い換えると、一つの大きな[Merkle DAG](https://github.com/jbenet/random-ideas/issues/20)とも言えるみたいです。

## Databases and Datasets

[前回のブログ](http://qiita.com/ykshr/items/ac470aa828703e7578e8#noms%E3%81%A8%E3%81%AF)で書きましたが、Nomsのデータベースとデータセットは、Gitのリポジトリとブランチみたいな位置付けになるみたいです。このイメージをもっておくと、多少分かりやすいかと思います。

| Noms | Git |
|:-----|----:|
| Database | Repository |
| Dataset | Branch |


Nomsでは、データベースはもっとも大きい概念であり、2つ役割があります。

* データを保存する（[Content-addressable storage](https://en.wikipedia.org/wiki/Content-addressable_storage)）
* データセットの履歴を保持する

また、Nomsのデータベースは、キーバリューストレージに実装することができます。ただし、データセットの保存には、[楽観的並行性制御](https://ja.wikipedia.org/wiki/%E6%A5%BD%E8%A6%B3%E7%9A%84%E4%B8%A6%E8%A1%8C%E6%80%A7%E5%88%B6%E5%BE%A1)のみが用いられます。
主に、Nomsのデータベースは、次の通り実装されるみたいです。

* ローカルDB　：[LevelDB](https://github.com/google/leveldb)
* リモートDB　：[HTTP protocol](https://github.com/attic-labs/noms/blob/master/go/datas/database_server.go)
* クラウドDB　：[Amazon DynamoDB](https://aws.amazon.com/dynamodb/)
* テスト用DB　：[memory](https://github.com/attic-labs/noms/blob/master/js/src/memory-store.js)

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つ前のコミット）をもち、マージ処理をした際は複数の親をもつことになるみたいです。

これは、[前回のブログ](http://qiita.com/ykshr/items/ac470aa828703e7578e8#%E3%82%B3%E3%83%9F%E3%83%83%E3%83%88%E3%83%AD%E3%82%B0%E3%81%AE%E8%A1%A8%E7%A4%BA)でも、`Parent`として、1つ前のコミットのハッシュが表示されていましたね。

## Chunks

Nomsでは、データはチャンクとして、特定の単位に分割して保存されます。

この時のチャンクの単位は、暗黙的に大きなデータにも効率的に対応可能な単位に決められるみたいです。（詳細はProlly Treesに記載）
また、チャンクの単位を明示的に指定したい場合は、`Ref`タイプを用いることで、指定することができます。（`Ref`タイプはTypeに記載）

Nomsでは、ハッシュを基に保存したチャンクを特定しています。このチャンクの特定に、[Content-addressable storage](https://en.wikipedia.org/wiki/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](#prolly-trees-probabilistic-b-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](https://github.com/attic-labs/noms/blob/master/go/hash/hash.go#L7)を用いています。
※ ハッシュの計算は、システムのバージョンに依存しているため、将来的には変更される可能性があります。

一方、`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>`であることを意味しています。
    <pre>
    struct Commit {
        Value: Set&lt;Number&gt;
        Parents: Set&lt;Ref&lt;Cycle&lt;0&gt;&gt;&gt;
    }
    </pre>

2. データセットに`Set<String>`をコミット
下記は、現在のコミットがデータタイプ`Set<String>`であり、以前のコミットがデータタイプ`Set<Number>`であったことを意味しています。
    <pre>
    struct Commit {
        Value: Set<String>
        Parents: Set<Ref<Cycle<0>> |
            Ref<struct Commit {
            Value: Set<Number>
                Parents: Cycle<0>
            }>>
        }
    }
    </pre>

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

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

## Prolly Trees: Probabilistic B-Trees

Nomsでは、データ構造として_Prolly Trees_というものを使っています。
_Prolly Trees_は、B-Treeと似た木構造らしいのですが、木構造内で保持しているデータを基にして各ノードに格納する値の数を確率的に決定する[Search Tree](https://en.wikipedia.org/wiki/Search_tree)みたいです。


### Indexing and Searching with Prolly Trees

_Prolly Trees_は、下記の基準でソートされています。

* データタイプ（Boolean, Number, String）　：格納された値でソート
* 上記以外のデータタイプ　： ハッシュ値でソート

Nomsでは、_Prolly Trees_をソートしておくことでインデックス、および集合演算に用いられています。

インデックスでは、従来のデータベースと同様に、データを探索する際の計算量を削減することができます。例えば、年齢で人を検索することを想定して、データタイプ`Map<Number, Set<Person>>`を定義したとします。この時の計算量はO(log<sub>k</sub>(n))となります。
※ kは_Prolly Trees_の平均幅であり一般的に64くらい（？）とのことです。

集合演算では、Unionおよび[Intersect](https://github.com/attic-labs/noms/blob/d6537c74c58fecebb8c4605c07b0670ed9737e1f/js/src/set.js#L157)が効率的に実装されています。例えば、年齢および髪の色で人を検索することを想定して、データタイプ`Map<Number, Set<Person>>`および`Map<String, Set<Person>>`を定義したとします。Nomsでは、それぞれでデータを抽出した後に、Intersectすることが可能です。

# おわり

おわりです。