データ指向アプリケーションデザインメモ2

このページについて

データ指向アプリケーションデザイン読書の記録をつらつらと書いておく

6章 パーティション

ローカルインデックス パーティショニングされた空間内でのセカンダリインデックス
パーティショニングまたいだクエリが打たれると結果を結合しないといけないので負荷が高まりがち
上記アプローチはスキャッタ/ギャザーと呼ばれる

グローバルインデックス パーティション関係なしにインデックスを保持する
ただし、この空間もパーティショニングは可能で、例えば色でいうと先頭 a ~ s, t ~ z のように分けられる
しかし、書き込み時に複数のインデックスが指定されている場合は完了までに時間がかかりうる (基本的にこれは非同期で行われるらしい。なので、書き込み直後はインデックス検索のデータが反映されてないかもしれない)

HBaseやMongoDBは動的にパーティションを生成するアルゴリズムが組み込まれている
例えば、あるパーティションが10GBに達したら、5GB - 5GB のパーティションに分割される

@Todo gossipプロトコル

7章 トランザクション

大まかな発想は40年変わっていない

• read committed
• スナップショット分離
• 直列化可能性

トランザクションが提供する安全性の保証は総じてACIDと呼ばれる。復習がてら追記してく。

Atomic コミットさえしなければデータが変更されない。何か不慮のことが起きても途中の書き込み(状態?)をすべてリセットできる

Consistency 一貫性はアプリケーションでハンドリングするのでここでは深くふれない ビジネス要件にもよって変わる。あくまでトランザクションを使ってどうこうなので。

Isolation 並行して発行されたトランザクションが、お互い副作用を起こさないこと。独立性を保証する。

Persistant 永続性は、トランザクションのコミットが行われたらデータが消失することがないと保証する ただし、コミット後にハードがすっ飛んだり物理的な異常はしょうがなし。

使う側からしたdbがエラーハンドリングに関するtips

• 過負荷で応答ができないときはそのままリトライしても悪化させるだけなので指数的にリクエストのwaitを入れる

  • そもそも過負荷によるエラーなのかアプリケーションが把握できるとよい
• リトライすべきは一時的と判断できるエラーのみ。恒久的なエラーについては行わないようにしたい
• リトライ中にアプリが落ちたらデータは失われるのでファイルorメモリにデータはもつようにすべき

分離性レベル

Read Committed

• DBからの読み取りを行った際に見えるデータはコミットされたもののみであること

  • ダーティリードは生じない

• DBへ書き込みを行うとき、上書きするのはコミットされたデータのみであること

  • ダーティライトは生じない
• ただし連続したアップデート

スナップショット分離

常にコミット済みのものを新しく作り、バージョニングしていく 読み取りと書き込みがバッティングしないメリットがある

@Todo Redisの優先順位つきキュー

同時に読み込まれるかつ、書き込みがある可能性のあるものはfor updateで
他からブロックするべき。でないと読み込み->書き込みで意図しない状況になることがある for update はcommit or rollback で解放される

FOR UPDATE	自分が更新する目的で行をロックしておく
FOR SHARE	他からの更新がかからないように行をロックをしておく
FOR UPDATE NOWAIT	ロックが重なった場合は、後からロックを取ろうとしたトランザクションが即エラー

衝突の実体化 -> ファントムリードが起きないよう、ロックをかけられるように必要な概念をテーブルに起こすこと 難しさと、アプリケーションレベルで並行性の制御は間違えやすいので最後の手段

VoltDBはパーティショニングしたものにCPU割り当ててトランザクションができる ただし、パーティションをまたぐトランザクションはコストが高い(1000回/秒)し、スケールできない模様

2PL 2フェーズロックは、書き込みをしようとするトランザクションがない限り、並行に読み込みを行える
しかし、トランザクション(書き込み)がある場合はそのトランザクションが終了するまで読み書きができない これは、一つのトランザクションの時間によって他の処理に影響を与えるので並行性のパフォーマンスはとれない

直列化可能スナップショット分離 seriarizable snapshot isolation(SSI) 楽観的ロックのアプローチをとる
トランザクションはコミットの時点でチェックされ、その実行が直列化可能になっていなければ中断になる。
要は、実行途中に他のトランザクションによって整合性がとれなくなったら。 まだ新しい(2008~)研究成果。foundationDBが採用している。よさそうだけど流行ってない?
書き込み(更新含む)のトランザクションがバッティングした場合、後のトランザクション要求は失敗するようになっている
読み書きのトランザクションを短く使えれば、安全にパフォーマンス良く使うことができる。
読み込み同士はバッティングしてもDBが続行させてくれるので、読み込みが長期にわたるトランザクションでも大丈夫

8章 分散システムの問題

分散システムを構築するのであれば、部分障害の可能性を必ず考慮する。
システムのいくつかがおかしくなることは必ずやってくる

@Todo AkkaやCassandraに搭載されている Phi Accrual failure detector レスポンスタイムの変動(ジッター)を考慮したタイムアウトアルゴリズム?

@Todo 仮想マシンを使うメリット

マシンのクロック管理の仕組みも取り入れるべき

@Todo Spannerの論文 クロックを利用したトランザクションID生成をどう解決しているか、また分散トランザクションについて

分散システムは、共有メモリがなく、完全に信頼できないネットワーク上でメッセージを送り合うので 限られた状況下でのシステムの振る舞いを定義していく必要がある。
そのためには自分たちが構築するインフラがどんな特徴をもっていて、どんな障害が考えられるのか把握しておかないとならない どこでメッセージが失われるか、その場合アプリケーションで担保するのか、その下のレイヤで担保できるのかなど

9章 一貫性と合意

線形化可能性

仮にレプリカを組んでいても、あるデータが複数のバーションを持たないようになっている仕様 そのため、ノードに対する書き込みが成功したら、どのノードへ読み込みリクエストをかけても
一意なデータが返ってくる

線形化可能性 ≒ 最新性の保証

線形化可能なシステムの仕様

• データのコピーは一つしかないように振る舞う
• データに対するすべての操作はアトミック

線形化可能なシングルリーダーレプリケーションはマルチデータセンタ運用ではデータセンタ間で障害が発生したときに整合性がとれなくなる。なぜならネットワークが途切れてしまった場合、片方へ同期処理ができなくなってしまうから。クライアントがリーダー側へリクエストを投げるよう切り替えられるのであれば問題ない。問題は、同期ができなくなっている側のデータセンタにリクエストが投げられてしまうことなので。また、そのときにリーダーから切り離されているレプリカはエラーを返すべき。 かといって、マルチリーダーレプリケーションがいいかというとそうではなくて、5章で書かれているように設計上の落とし穴(主に並行性の書き込みによるもの)があったりするので安易に選択するべきではない(むしろしないようにする)

ランポートタイムスタンプ タイムスタンプをノードIDとセットで保持し、分散システムで利用されるカウンタをユニークにする仕組みを提供する。基本的にノードIDの大きいものが優先される。(カウンタの値が同じならノードIDの大きいほうが大きいタイムスタンプとされる)

全順序ブロードキャスト 書き込み順序の配信を決定的なものにする。例えばユニーク制約を課すためには、書き込み前にレジスタに問い合わせ、nullであればIDをセットする。次からの書き込みは、ID名のレジスタに値が入っているので重複書き込みはできなくなる。(@Todo レジスタから値がすっとぶことあるのかな。。? レジスタから値が吹っ飛ぶ条件とは)

2相コミット(ツーフェーズコミット)

トランザクション対象が複数あるときに、それらと確実にコミットができるか確認してから個々のトランザクションを実行する方法。Javaではトランザクションマネージャがライブラリがあるぽい。コミット実行が確定したら、その処理はかならず実行されなければならない。すなわち、失敗した場合は永遠とリトライを続ける。2相コミットが原子性を維持するためにはこのような約束を必ず守る必要がある。 ただし、クライアントがクラッシュした場合は上記約束を守れるようにリカバリ対策をしてないと意味がない。(ムズカシイ。。)なので、クライアントもトランザクションログを保持する必要がある。 書籍では、クライアントはコーディネータと呼ばれていた。参加者との間をとりもつ役目をするので。 デメリットとしては、どこかのデータベースとのやり取りがコケたら処理を巻き戻さないといけないので耐障害性は下がる可能性がある。また、コーディネータ自体がトランザクションの状態をもつのでコーディネータが冗長化されてない場合は単一障害点になり得る

XA(eXtended Architecture)トランザクション

ヘテロジニアスな技術間での2相コミットの標準。(ヘテロジニアスは異なる技術領域のことをさす)
多くのRDB(MySQL, Postgres…)やメッセージブローカでサポートされている。 そのサポートされているXA APIを実装したものがコーディネータ。@Todo goでもある? @Todo 詳しい連携の方法は調べないと。例えばpostgresではどういう仕様なのかとか

合意アルゴリズム

• Viewstamped Replication
• Paxos
• Raft
• Zab

自分で実装するのはしんどいらしいので上辺くらいは理解しておくとよい
どれも、値の並びに対して決定を行うことで全順序ブロードキャストを提供するアルゴリズム、らしい
(全順序ブロードキャストではメッセージが厳密に一度だけ同じ順序ですべてのノードに送信される)

@Todo ZooKeeper, etcd ちょっと調べとく。ZookeeperはKafkaやHBaseの裏で使われているので間接的に関わることになりそう