Dynamo: Amazon’s Highly Available Key-value Store

はじめに

AmazonがDynamodbを紹介した論文を読んだ。
2007年のもので、NoSQLブームの走りとなったものだったと思う。
コンピュータ・サイエンス関係の「おすすめの論文」のようなもので、よくおすすめされるので読んでみたが、意外と面白かったので、面白かった場所に焦点を当てて書く。
ただし、現在は、AWSのサービスとして提供されていて機能追加も多いのでこの論文とは大きく異なると思われるので注意が必要。

Dynamodbとは

Amazonが開発したNoSQLで、高可用性KVS。
論文上では99.9995%のリクエスト返答成功率と、データロス無しという、数字を出している。

https://aws.amazon.com/jp/dynamodb/
を読むと、概要がわかりやすいだろう。

Dynamo で使われている技術 (4章)

４章では、主要技術を5つ挙げている。

1. Consistent hasing
   データ分割のアルゴリズムとして、Consistent hashingを採用している。
   また、キーが偏らないように Virtual node を使い単一ホストに対する複数キーの設定を設定している。
   ただ、単純には行かなかったようで、後半で試行錯誤を書いている。

2. Versioning
   Vector clockを採用し、順序が確定する場合には最新の情報を返す。
   更新要求が成功したからと言って、dynamoが更新された情報を返すわけではなく、古いデータを取得することが有りえる。
   そのため、同一データに対して同時に更新する可能性があり、不整合が発生しうる。その場合は復元を行う(後半に詳細が有る)
   さらに、vectorが大きくなるのを抑えるために、古い情報は捨てている。

3. Sloppy quorum and hinted handoff
   (W: Writeが成功する時の最低ノード数) + (R: Read時のデータ取得対象ノード数) > (N: レプリケーションノード数)
   になるようにして、Quorumのようになっている。
   書き込み対象が落ちている場合は、別ノードにデータが書き込まれる。復旧したら、データを戻した後にデータを消す(hinted hand off)。
   ちなみに、W, Rのノード数を変えることで、個々のサービスの要求を満たすことが出来るようになっている。
   例えば6章に、商品情報や宣伝のサービスではW=N,R=1にして高速で動作するようにしているとしている。(更新が圧倒的に少ないのでこういう設定が可能)

4. Anti-entropy using merkle tree
   Merkle tree を使うことによって差分を高速に発見し、そこだけデータ同期を行う

5. Gossip based membership protocol and failure detection
   GossipでノードやConsistent hashのリング情報などを共有している
   Seedsというリング上の全てのノードを知っているノードがいて、全ノードがそれらに合わせるので、分断は起きない。

バージョン差異が見つかった場合の修復方法 (6章冒頭)

Versioningでバージョンの不整合があるので、それをどのように治すかという問題を解説している。
不整合に対する対応では、サービスの性質に応じて３種類の方法を用いている。

1. クライアント(アプリ側)が独自のビジネスロジックで治す (例: カート情報)
2. 最新の更新日付を持つバージョンを使用する (例: セッション情報)
3. R=1,W=Nにして、そもそもバージョン差異に気づかないようにする。(例: 商品情報や宣伝のサービス)

ちなみに、全リクエスト中に複数バージョンが見つかった割合は

• 0.00057%で2つのバージョン
• 0.00047%で3つ
• 0.00009%で4つ

と、少ない(6.3章)

Consistent hasingのキーの割当に用いた戦略について (6.2章)

Consistent hashは工夫が合ったようで、３種類の戦略を取ったらしい。
下に論文にある図を置く

戦略1. ノードに対してランダムなtokenを割り当てて、token間のデータを各ノードが持つデータとする

Consistent hasingを素直に実装した初期の戦略。
ただ、この戦略には、以下の問題があった

1. ノードが増えたときには必ずデータ移動が発生し、移動対象データの全スキャンが走るので重い
   それに対応するために、データ移動を優先度最低のバックグラウンドタスクとして、移動完了後にノードを追加するようにした。そのために、ノード追加の時間が長かった
2. Merkle tree の再計算が必要
3. データの存在するノードが変動する可能性が有るので、全体バックアップを取るのに苦労した

これら問題の本質は、

1. データの分割箇所(partition)(上図の網掛け部分)の決定
2. データを配置する配置ノード(上図のA,B,C)の決定

という選択を同時に変更してるところから発生している。
例えば、「リクエストが多いからノードを追加しよう」と思ってもデータの分割箇所の変更が発生していた。

戦略2. 事前にpartionを均等なQ個に分割し、partitionを配置するノードは後から割り当てる

バックアップやMerkle treeの問題は、ノードが保持するデータが変わるために発生する問題だったので、保持データが変わらないようにしている。
partition内のデータを保持するノードを決定する際には、リングの位置を表すtokenを各ノードに割り当てて、partitionに最も近いtokenを持つN個のノードへpartitionのデータが配置される。
これによって、

• (戦略1で問題だった)partitionと配置ノードが同時に変わる問題を解決
• partitionを動的に変えられる

という利点が有る。

戦略3. Q個の均等なpartionに分割し、各ノードに割り当てるpartitionも確定する

２番めの戦略を進めて、割り当てるpartitionのノードを固定している。
そのために、

• ノードが無くなる場合には、消えたノードのpartitionを別のノードへ割り当てる
• ノードを追加する場合には、既存のノードに割り当てられたpartitionを新規ノードに移動させる

となり、２で発生していた、ノードが保持するpartitionが変わる問題が解消された。
ちなみに、3つの戦略における負荷の偏りを測ると、3が最良で２が最悪となった。(2が遅い理由はみつからなかった)

3番目の戦略の良いところはデプロイが簡単になったところ。
簡単になった理由は、

• partitionの範囲が固定されていてノードが保持するpartitionも固定されるおかげで、ノードのbootstrapや復元が早くなる (partitionの範囲が動的だとランダムアクセスになる)
• アーカイブが簡単 (partitionの範囲が固定されるので)

ただし、ノード管理の手間は増えるという欠点が有る。

まとめ

以上、Dynamoの古い論文を読んだ。

BeyondCorp - A New Approach to Enterprise Security -

GitHubのを眺めていたら、ORYのoathkeeperを見つた。
これがGoogleが社内で使用している「BeyondCorp」を参考にしているということが書いてあったので、その論文を読んだ。

BeyondCorpとは

GoogleがVPNの代わりに使用している、認証・認可のシステム。
人・デバイス・ネットワークなどを基に社内システムへのアクセス制御を行い、ホテルやカフェなどから、Google社内システムへのアクセスができるようになっている。
論文は何個か出されているが、読んだのは、BeyondCorp: A New Approach to Enterprise Security
また、GCPのサービスにもなっていて、Cloud Identity-Aware proxyという名前になっている

BeyondCorpの仕組み

図にすると、↓のような構成らしい

認証

HRのシステムと結びついてシングルサインオンをやっていると書いているが、具体的にはあまり書いていない。
Cloud Identity-Aware proxyでは、セキュリティキーというデバイスを使って二要素認証をしているので、同じようなものがあるはず。 (https://login.corp.google.com/?gnubby=0 を見ても、SecurityKeyの記載がある)

認可

権限制御のシステムは、AccessControlEngineという名前がついていて、

• ユーザー
• ユーザーの所属する組織
• デバイス
• 場所

を基に権限を与えている。
例えば、バグトラッカーを使えるのは、フルタイム開発者が開発マシンから見ている時だけ。財務システムはファイナンスグループのフルタイムかパートタイムだけ。など、分けられている。
権限制御はサービス単位だけでなく、サービスの要素に対しても割り当てられる。バグトラッカーのバグ詳細のページを見る権限と、検索、更新する権限は別にすることが出来るらしい。
また、Googleのビル内からのアクセスかどうかとか、新しい場所からのアクセスかで認証レベルを変えているし、OSのパッチがあたっているかどうかでも変えているらしい。

他

VPNから、BeyondCorpへ移行するのは大変だったようで、後半はそれについて書いてある。
あと、各社内サービスへの入り口へのFQDNはDNSで公開していると書いてある。これは、社外ネットワークを使っている以上、必要だろうという感じ。サービス本体の情報は社内DNSから引けるのかもしれない。

gh-ostの動き

gh-ostとは

gh-ostは、binlogを利用したmysql用のデータベースマイグレーションツールです。
大抵のマイグレーションツールがtriggerを使いつつ移行するのに対して、gh-ostはbinlogを使うことで、負荷制御やテスト可能性を実現しています。

githubはここ。
github.com

マイグレーション方法

goroutineを使って並行に動かしているので、図が正しいわけではないですが、おおよそ下図のような動きをします。

要約すると、
1. ゴーストテーブルを作成してテーブルを変更する
2. binlogを監視ししつつ、既存テーブルを順にコピーし始める。
3. binlogの中に、元テーブルの変更をするものがあれば、ゴーストテーブルにも反映する
4. 既存テーブルのコピーが終わったら、テーブル名を変更

という動きです。

テーブルコピー vs binlog反映

テーブルコピーとbinlogの反映は並行処理をしているので面倒そうですが、gh-ostでは下のように対処しています。

コピーしていない行がbinlogで反映された場合

binlogを基にクエリ実行
insertなら追加され、それ以外は無視される。

コピーした行がbinlogで反映された場合

ただ、実行する。binlogの変更が有るべき姿なので、問題なし

コピー中の行に対して、binlogが反映される場合

もし、取得と挿入の間にbinlogの変更が反映されると、binlogの反映がなかったことになる可能性が有るので、注意が必要です。
gh-ostは、既存行のコピー中にはbinlogの変更を停止することで、この問題を回避しています。 (INSERT INTO SELECTを使っています) ちなみに、既存行のコピーはデフォルトで1000行づつ行われ、１回のコピーが終わった後に、溜まっているbinlogの変更を反映するようになっています。
こうすることで、未反映のbinlogが溜まり過ぎないようになっています。

参考

gh-ostには資料が多く有ります。たとえば、

• テーブル名変更時の動き
• トリガー無しでの実装の工夫
• 負荷制御