datastoreのmemo

業務中に書いてたdatastoreのmemo


# Datastoreの特徴
RDBとNoSQLの特徴を併せ持つカラム指向のNoSQL
DatastoreはNoSQLだが、Entity GroupでRDBの特徴を実現できる

RDBの特徴
- 利便性（conveniency）
- 一貫性（consistency）
- 可用性（availability）

NoSQLの特徴
- スケーラビリティ
- レイテンシー

# Overview
## マクロ
![image](https://qiita-image-store.s3.amazonaws.com/0/94686/49120e79-fdc1-fbbb-16e4-3dc1beb878e1.png)
## ミクロ
![image](https://qiita-image-store.s3.amazonaws.com/0/94686/7290aea2-0e04-1937-e286-8f176a2281af.png)

## Datastoreは内部構造
GAEでは、以下に示す、全部で7種類のBigtableが使われてている
Bigtableではクエリで検索はできないので、予めIndex tablesが用意されている

名前|役割
---|---
Entities Table| アプリケーション・プログラムからの書き込みデータ
EntitiesByKind Table| カインドで検索するIndex tables
EntitiesByProperty ASC Table | プロパティ項目で検索するためのIndex tables
EntitiesByProperty DESC Table |  プロパティ項目で検索するためのIndex tables
EntitiesByCompositeProperty Table|  複合インデックス検索で使用されるIndex tables
Custom indexes Table| カスタムインデックスの構成を保持している
Id sequences Table |  エンティティとにアサインされる数値のIDを生成・格納するもの

ここがわかりやすい
http://blog.sojiro.me/blog/2016/08/07/about-gae-datastore/

## Entities Table
* DatastoreのEntityを保存するBigtableのテーブル
* このテーブルのカラムはEntity keyとEntity Serializedの2つ
* Entity keyにはEntity Keyが入る
* Entity Serializedにはシリアラズされたバイトストリームが入る
* よってインデックスを作らない限りEntityのプロパティ内容に基づくクエリ、フィルタ、ソートなどは実行できない

## Entity Key
* A complete key is the combination of the entity "Kind" and the entity ID or the entity key name. 
* The entities complete key cannot be modified once the entity is saved.  If this is required, you should create a second entity using the new key, copy all of entity property values, and then delete the the original entity.
* Entity Keyは、「Entityが所属するEntity GroupのRoot Entityまでのパス」を含む
* 辞書順でソートされている

```
/Grandparent:Alice
/Grandparent:Alice/Parent:Sam
/Grandparent:Ethel
/Grandparent:Ethel/Parent:Jane
```

## EntitiesByKind Table
- This table serves simple queries against a specific "Kind" of entity. 
- AppIDとKindと

## Query
- Index tables map entity keys to kinds, property values, and ancestors. 
- When the AppEngine executes a query, it must convert the query into an equivalent BigTable scan against one of the index tables
- As a general rule, datastore scans never sort or filter in memory.  Because the datastore query planner does not have knowledge regarding the size of your data set, it will not pull your dataset into memory during a scan.
- GQL queries は prefix scan in BigTableに変換される

## Index tables
 * Entities Tableとは別に作成されるBigtableのテーブル
 * クエリを記述すると自動的に作成される。明示的な作成も可能
 * 4種類のIndex tables
   * カインドインデックス(EntitiesByKind Table)
   * シングルプロパティインデックス(EntitiesByProperty ASC/DESC Table)
   * コンポジットインデックス(EntitiesByCompositeProperty Table)

## Merge（SortMerge） join
 * Datastoreでは、コンポジットインデックスに頼らずに複数プロパティの条件検索を実現するために、マージジョインが実装されている
 * シングルプロパティインデックスの検索結果をマージする
 * "zig-zag"アルゴリズムにより、個々のインデックスを並行してスキャンする

![image](https://qiita-image-store.s3.amazonaws.com/0/94686/73a49380-30ff-ef9e-2a96-0e1d7287b21a.png)


# 用語の比較
Concept	Cloud| Datastore |Relational database | document-oriented databases 
---|---|---|---
オブジェクトが所属するカテゴリ|Kind|Table | Collection
オブジェクト|Entity|Row/Record | Document/Object
オブジェクトがもつデータ|Property|Column | Field
オブジェクトを特定する ID|Key(Entity Key)|Primary key | Object ID
外部キー | Parent Key | Foreign key | Object ID

※ただし、datastoreのKeyはdatastoreの全Kindの中で一意にする必要があり、
以下のような手順でEntities Tableのkeyを発行する

```go
// 自分のKind名とID or No(そのKindの中でのPrimary Key)で一意にするか
key := datastore.NewKey(c, "Employee", ID, 0, nil)
// 自分のKind名とID or No(そのKindの中でのPrimary Key)とParent Kind名一意にするか
key := datastore.NewKey(c, "Employee", "", No, "People")
key := datastore.NewKey(c, "Employee", "", No, "Animal")
// datastoreに自動で発行してもらう
key := datastore.NewIncompleteKey(c, "Employee", nil) // これは以下と同一
// datastore.NewKey(c, "Employee", "", 0, nil) // つまり、Primary Keyがわかない
 ```

# Entity Group
* 全てのエンティティはEntity Groupに所属している
* Parent Keyを持たないEntityはRoot Entity
* Entity Groupは、データセンター間のレプリケーションでもStrong Consistencyにデータが反映される。
* トランザクションによりACID特性を保障したいときに設定する
* 特徴
    * 強い整合性
    * トランザクション性(ACID特性)
    * ローカル性、エンティティはキーの辞書順で並べ替えられ、格納される
* 制約
    * 各エンティティ グループの書き込みは、1 秒間に 1 回の更新
    * エンティティの作成後にエンティティ グループの関係を変更できない


# クエリの種類
## グローバルクエリ
* Cloud Datastoreで祖先を指定しないクエリ
* 結果整合性がある

```go
// 下記のクエリはRead Entityにあたる
datastore.NewQuery("testkind").Filter("name =", uniqueName)
```

## 祖先クエリ
* 特定のEntityグループに属するEntityだけを取得するクエリ
* 強い整合性がある

```go
// 下記のクエリはRead Entityにあたる
datastore.NewQuery("testkind").Ancestor(ancestorKey).Filter("name =", uniqueName)
```

## キーのみのグローバルクエリ
キーのみのクエリは、特別なグローバル クエリで、エンティティのプロパティ値は返されず、キーのみが返される。

## キーによる検索
* 強い整合性がある

```go
// 下記のクエリはRead Entityにあたる
datastore.Get(ctx, k, &d)
```


## プロジェクションクエリ
* ようは必要なフィールドのみを指定して取得するクエリ, ```SELECT HOge```的に
* 検索クエリがCovering indexになっている（＝インデックスだけで結果を返せる）場合はクエリはプロジェクションクエリと呼ばれ、次のようなクエリで実現できる
* 制約
    * データストアインデックス付きプロパティのみ対象
    * 同じプロパティを複数回指定することはできない
    * (=, IN)のフィルタで参照されるプロパティは指定できない

```go
// 下記のクエリはRead Indexにあたる
q := datastore.NewQuery("post").Project("bbs_id", "updated_at").Order("-updated_at")
```
# 整合性
## クエリによる整合性
Cloud Datastore API |Read Entity | Read Index |
---|---|---|---
グローバルクエリ |結果整合性 | 結果整合性
キーのみによるグローバルクエリ |  なし | 結果整合性
祖先クエリ |強い整合性 | 強い整合性
キーによる検索（get()） |強い整合性 | なし

## 強い整合性(Strong Consistency)
* RDB的なアプローチ、最後に更新された値が返されることを保証する
* 更新直後から必ず最新の情報を取ってこれる。ただし、逆を言えば、最新の情報が反映されるまでは情報を取れない。
* Entityが少ないと有利で、スケールアウトが難易

## 結果整合性(Eventual Consistency)
* NoSQL的なアプローチ、即座にデータが反映されることを前提としていない
* 更新後十分な時間が経過しないと最新の情報を取れない。しかし、古い情報かもしれないが、いつでも情報を取れる。
* Entityが多いと有利で、スケールアウトが容易
* DNSとか

# トランザクション
* 単一のトランザクションで複数のエンティティに対して適用する場合、属するエンティティグループが最大で5つまで
* 複数のエンティティグループを組み合わせてトランザクションを実行するにはクロスグループ（XG）トランザクションが必要になる
* 楽観的ロックなので、RDBの用にDBをロックしないためスループットは高いが、競合時のリトライが必要であり(最大3回される)、その処理の中で冪等性をたもたなければならない(ポインタ型に注意)


# インデックス
## DataStore Index
 * 自動で付加される
 * noindexタグで追加させなくできる
 * シングルプロパティインデックスで使用する

## 複合インデックス
 * クエリによってindex.ymlに自動追加される
 * ~~Order句で2種類以上フィールドを指定したらmerge joinで対応できなるから生成される？~~
 * ~~ASC/DESCのEntitiesByProperty Tableがあるため、1種類は対応可能だから?~~


# References
http://www.cloudsultant.com/chapter2.htm
https://en.wikipedia.org/wiki/Eventual_consistency
https://cloud.google.com/datastore/docs/articles/balancing-strong-and-eventual-consistency-with-google-cloud-datastore/
http://www.apps-gcp.com/consistency-of-datastore/
https://ja.wikipedia.org/wiki/%E7%B5%90%E6%9E%9C%E6%95%B4%E5%90%88%E6%80%A7
http://shmachid.com/database/135/
http://pospome.hatenablog.com/entry/20161009/1475990332
http://knightso.hateblo.jp/entry/2014/06/02/102029
http://knightso.hateblo.jp/entry/2014/08/28/083545
http://qiita.com/hnw/items/52addaebe95bb9a16eac
http://qiita.com/hnw/items/7900cce018bb24f51b91
http://knightso.hateblo.jp/entry/2014/05/31/124422
https://thinkit.co.jp/story/2011/02/22/2009
https://www.slideshare.net/kazunori279/cba-google-app-engine-20101208
http://d.hatena.ne.jp/kazunori_279/20090617/1245223665
http://itpro.nikkeibp.co.jp/article/COLUMN/20060111/227102/?rt=nocnt
http://software.fujitsu.com/jp/manual/manualfiles/M100013/J2X17495/03Z200/J7495-h-02-02.html
https://ja.wikipedia.org/wiki/CAP%E5%AE%9A%E7%90%86
http://d.hatena.ne.jp/kazunori_279/20090617/1245219785