概要
既存のアプローチの中でのHermesの位置づけ
- Chain Replicationでは、ヘッドにWriteし、末尾でReadする
- ヘッドでシリアライズ(順序付け)されている
- 末尾に来た時点ですべてのノードに値が書き込まれていることが保証されている
- Chain Replicationの進化系であるCRAQでは、Local readを達成しているが、依然としてWriteは遅い
システムモデル
仕組み
- Coordinator replicaとFollower replicaがいる
- あくまで各命令に、ということで、同時に異なる命令に異なるCoordinatorがいる
Write
- Coordinator replicaは、Timestamp(Lamport Clock)をつけたInvalidation messageを送る
- Invalidationはロックに近いように思えるが、同じキーへの同時書き込みは失敗しない
- タイムスタンプでTotal Orderが付けられる
- Invalid状態の値は、Readerに更新される値が来るから待っててねーというメッセージになる
- Ackが得られたらコミットし、そのあとValidationを送る
- ここでFollowerのタイムスタンプも来るので、Coordinatorのタイムスタンプが更新される(Lamport Clockなので)
Read
- 読んだときに、Validだったら、値が返される
- Invalidateなどその他の状態だったら、暫く待つ
- 書き込みを開始するときに既存の値を無効化することで、Valid状態のキーが最新の値を保持することが保証される
Safety replayable writes
- キーに値を書いている途中にネットワークの障害が起きたら、あるノードでは値が永遠にInvalidになってしまう?
- それを防ぐために、Linearizabilityを犠牲にすること無く書き込みをreplayする仕組みを備えている
- キの新しい値がまたInvでやってくるので、いつかは最新の値を知れる。Livenessの保証かな。
- Logical clockにより各書き込みの正確なグローバル順序がわかる
- 長い間Invalidだなーと思ったら、自分がCoordinatorになって、Invメッセージを他のノードに送る
- そうするとValidになるかもしれない(し、みんなもっと新しい値を知ってるかもしれない)
参考
