DynamoDBとRiak KVを組み合わせて、使いやすさと可用性を両立できないか考えてみた

WebアプリなどDynamoDBを使うことが多いと思います。ここではRiak KVと組み合わせて、使いやすさそのままにデータストアの可用性を（さらに）あげられないか考えてみました。具体的にはあつかうデータがCRDTかどうかに応じてRiak KVとDynamoDBを使い分けたらどうなるかというものです。

※ただDynamoDBの可用性は十分高い＆安定してそうなので自前でKVSのクラスタを管理する手間を考えると現実的ではない気はします。

## 背景

[AWS DynamoDBとDynamoの違いを調べてみた - Qiita](https://qiita.com/araiichiro/items/d7bf52dcdcfd6225db55) でまとめた利点・欠点を相互補完できないか考えました。

### DynamoDBの可用性（欠点）

DynamoDBではパーティションキーごとのリーダーノード経由でデータを書き込みます。DynamoDBでは1.5秒ごとにハートビートを実施＋リーダーノードがダウンしていたらPaxosによるリーダー選出をします[^1]。

もしリーダーノードがダウンしていたらアプリから書き込みができない（はず）です。つまり可用性は完璧ではなく、前述のフェイルオーバーの（わずかな）ダウンタイムがありえます。そこでRiak KVなどと組み合わせてダウンタイムを減らせないでしょうか？

### RiakなどのKVSの可用性（利点）

Riak KVなどリーダーレスKVSの可用性・耐障害性は高いです: そもそもリーダーノード（単一障害点）が存在しないし、いくつかのノードがダウンしていても利用できるノードから読み書きできればOKのため。

Riak KVはDynamoの論文がもとになっていて、その論文では（特に書き込みの）可用性のアピールをしています：

- always-on, always writable
- writes are never rejected
- high availability where updates are not rejected even in the wake of network partitions or server failures
- no updates are rejected due to failures or concurrent writes

### Riakなどの使いにくさ（欠点）

Riak KVなどのリーダーレス系のKVSでは下記の欠点がありました：

- リーダーレスなので書き込みが衝突するケースがある[^2]
	- → 書き込みの衝突をアプリ側で読み込み時に解決する必要がある (常にスプリットブレインしているのをアプリでなんとかするイメージ...)

### DynamoDBの使いやすさ（利点）

DynamoDBではアプリで特に何か注意する必要はなく使いやすいです（衝突などない）。

## 可用性向上のためにDynamoDBにRiak KVを組み合わせられないか

上記のようにDynamoDBとRiak KVには利点・欠点がありました：

| | 可用性 | アプリからの使いやすさ |
|---|---|---|
| DynamoDB | ○ | ◎ |
| Riak KV | ◎ | △？ |

DynamoDBにRiak KVを組み合わせて可用性の向上ができないか考えてみたいと思います。

### CRDT

Riak KVには Set や Counter などの Riak Distributed Data Types [^3]というCRDT [^4]のようなデータタイプがあります。

CRDTは書き込みの衝突がなく、アプリで何か必要がないデータ型です。これを使える場合にはアプリから使いやすいままデータストアの可用性を向上させることができそうです。

## 想定ワークロードその1: ホワイトリスト・ブラックリスト

オンライン広告のワークロードを考えます。例えばスマホのゲームアプリに広告を出すか/出さないかを判定します。出す/出さないの判定は、事前に設定したホワイトリスト・ブラックリストにもとづくとします。

今回、DynamoDBの通常のテーブルにアプリリストのマスターデータを作成し、グローバルセカンダリインデックスとして 「スマホアプリ → ホワイト・ブラックリスト」 で引けるインデックスを作成するものとします。

このグローバルセカンダリインデックスを使ってアプリ名（やアプリID）からホワイトリスト/ブラックリストを特定して、リストに含まれている or いないをチェックして広告配信に使用します。

#### リストのマスターデータ（人が管理）

| Partition Key | Sort Key | Value |
| --- | --- | --- |
| ホワイトリスト:1 | その1 | name:Final Quest |
|  | その2 | name:Super Hario  |
| ブラックリスト:1 | その1 | name:Final Quest |
|  | その2 | name:Rocket Monsters |


#### インデックス（システムから参照）

| Index Key            | Entries                                                 |
| -------------------- | ------------------------------------------------------- |
| name:Final Quest     | [ { PK=(ホワイトリスト:1,その1) }, { PK=(ブラックリスト:1,その1) } ] |
| name:Super Hario     | [ { PK=(ホワイトリスト:1,その2) } ]                            |
| name:Rocket Monsters | [ { PK=(ブラックリスト:1,その2) } ]                            |

※ PK = Partition Key + Sort Key


### インデックスをCRDTの `Set` で表現する

前述のアプリリストに対するインデックスは、CRDTの Set で表現できます。リストのマスターデータはDynamoDBの通常のテーブルに格納して管理（CRUD）しやすくしつつ、インデックスをRiak KVに格納して利用します。DynamoDBにはDynamoDB Streamsという機能があり、更新・削除を検知して何らかのアクション（例えばRiak KV上のデータの更新・削除）を実行できます。

#### 補足：
DynamoDBでのリストの更新の通りにインデックスの更新も行われます（パーティションキーごとのストリームなので順序が同じになる）。登録・削除が入れ替わることはない＝つまり登録したのに消えてる/削除したのに復活している、みたいなことがなく安心です。

#### 補足：

この例ではRiak KVを組み合わせても可用性向上はしないかもしれません。DynamoDBの読み込みではリーダーノード(WCU？)がダウンしていても読み込めるはずだからです。

他のメリットとしては地理的に各ノードが離れていてもデータの管理ができるのでCDN的な使い方ができそうです（例えば [^5] のような）。アプリから近いノードにアクセスすればレイテンシー改善や障害と重なる確率を減らせるかもしれません（要検証）。

## 想定ワークロードその2: フリクエンシーキャップ（広告表示頻度の制限）

広告IDなどからオーディエンス（スマホアプリのユーザー）を識別できた場合は、オーディエンス単位で広告を出すか/出さないかを判定するケースがあります。一日あたりの広告表示の頻度などを使用して実現します。

### フリークエンシーキャップや支出キャップをCRDTの `Counter` で表現する

フリークエンシー（頻度）の情報をCRDTの Counter で実装することでRiak KVで管理できます。これにより可用性を高められそうです。DynamoDBではリーダーノードがダウンしていると書き込みできませんが、Riak KVならいくつかのノードがダウンしていても書き込みできて可用性が上がりそうです。

## 最後に

CRDTで表せるデータはRiak KVで管理してそれ以外はDynamoDBで管理することで、使いやすさを維持したまま可用性を向上できるケースはありそうです。ただ、この構成にしても別に可用性が上がるとは言えないケース（インデックスの例）もあります。IoTなど他のワークロードも考えると今回の構成で意味が出てくるかもしれません。


[^DynamoDB]: [Amazon DynamoDB - Wikipedia](https://en.wikipedia.org/wiki/Amazon_DynamoDB)
[^Dynamo]: [Amazon's Dynamo - All Things Distributed](https://www.allthingsdistributed.com/2007/10/amazons_dynamo.html) [Dynamo: Amazon’s Highly Available Key-value Store](https://docs.riak.com/riak/kv/2.2.3/learn/dynamo/) 
[^Dynamo_wiki]: https://en.wikipedia.org/wiki/Dynamo_(storage_system)
[^1]: [AWS re:Invent 2018: Amazon DynamoDB Under the Hood: How We Built a Hyper-Scale Database (DAT321) - YouTube](https://www.youtube.com/watch?v=yvBR71D0nAQ)
[^VectorClock]: [Vector Clocks Revisited – Riak](https://riak.com/posts/technical/vector-clocks-revisited/index.html)
[^4]: [CRDT (Conflict-free Replicated Data Type)を15分で説明してみる - Qiita](https://qiita.com/everpeace/items/bb73ec64d3e682279d26)
[^3]: [Riak Distributed Data Types – Riak](https://riak.com/products/riak-kv/riak-distributed-data-types/index.html)
[^Option]: [読み込み整合性 - Amazon DynamoDB](https://docs.aws.amazon.com/ja_jp/amazondynamodb/latest/developerguide/HowItWorks.ReadConsistency.html)
[^5]: [Birth of the NearCloud: Serverless + CRDTs @ Edge is the New Next Thing - High Scalability -](http://highscalability.com/blog/2017/11/6/birth-of-the-nearcloud-serverless-crdts-edge-is-the-new-next.html)
[^2]: https://qiita.com/raiich/items/d7bf52dcdcfd6225db55#%E8%A3%9C%E8%B6%B3-%E3%82%A2%E3%83%97%E3%83%AA%E3%81%8C%E8%AA%AD%E3%81%BF%E8%BE%BC%E3%81%BF%E6%99%82%E3%81%AB%E6%9B%B8%E3%81%8D%E8%BE%BC%E3%81%BF%E3%81%AE%E8%A1%9D%E7%AA%81%E3%82%92%E8%A7%A3%E6%B1%BA%E3%81%99%E3%82%8B-%E3%81%A8%E3%81%AF