ということで、replicationを理解する前にconsistencyを理解する必要があると気が付きました。
Jepsenの各consistency modelの説明を読むにあたって第二層のlinearizabilityとserializabilityを初めに理解するのが良さそうというところまでは来た。
著者のPeter Bailisは第一層strict serializabilityの提唱者という認識。上記記事と元論文がすべてを言い尽くしているが、
- linearizabilityはCAPのC
- serializabilityはACIDのI
が最短の説明となる。また、
- linearizabilityの出自は分散システム
- serializabilityの出自はデータベース
である。出自の異なるこれらの特性を包括的に語るための生み出されたterminologyがstrict serializabilityであると理解した。自信はないが、システムパフォーマンスを語るときにresponse time/throughputをそれぞれ議論するようなものだと思った。本質的には出自の異なるこれらの特性を語るための理論がqueueing theoryであるという理解。
個人的にはlinearizabilityのほうが難しい。数学に疎いのでこれまた自信はないが、線形代数の線形と似た概念だと理解している。すなわちoperationが時間軸上で点として表現されるということだと理解している。しかし、これがCAPのCとどう関係するのかがわからない。
"This is the idea behind linearizability [6] (also known as atomic consistency [7], strong consistency, immediate consistency, or external consistency [8])."
via Check out this quote from Designing Data-Intensive Applications - https://learning.oreilly.com/library/view/designing-data-intensive-applications/9781491903063/ch09.html
linearizabilityの同義語多すぎでは…。
"the basic idea is to make a system appear as if there were only one copy of the data, and all operations on it are atomic."
via Check out this quote from Designing Data-Intensive Applications - https://learning.oreilly.com/library/view/designing-data-intensive-applications/9781491903063/ch09.html
あーなるほど。Figure 9-4がいままで読んだ説明で一番わかりやすかった。replicationの文脈ではlinearizabilityはwrite operationが時間軸上で点として表現されるゆえに全replicaに一瞬でデータがコピーされるようなconsistency modelということかな。すなわち全てのprocessからのread operationは必ず1つしかreplicaしか存在しないような振る舞いになる。ただし、invocation/completion timeについては何も言及していない。ACIDのIについても何も言及していない。
"In other words, linearizability is a recency guarantee."
via Check out this quote from Designing Data-Intensive Applications - https://learning.oreilly.com/library/view/designing-data-intensive-applications/9781491903063/ch09.html
ヤバいわかりやすすぎる。結局素直にDesigning Data-Intensive Applicationsを前から読むのが良いのでは…
"One way of electing a leader is to use a lock: every node that starts up tries to acquire the lock, and the one that succeeds becomes the leader [14]. No matter how this lock is implemented, it must be linearizable: all nodes must agree which node owns the lock; otherwise it is useless."
via Check out this quote from Designing Data-Intensive Applications - https://learning.oreilly.com/library/view/designing-data-intensive-applications/9781491903063/ch09.html
ここでlinearizabilityがleader electionに繋がってくるのか…感動がすごい。
"If you want to enforce this constraint as the data is written (such that if two people try to concurrently create a user or a file with the same name, one of them will be returned an error), you need linearizability."
via Check out this quote from Designing Data-Intensive Applications - https://learning.oreilly.com/library/view/designing-data-intensive-applications/9781491903063/ch09.html
linearizabilityはuniquenessにも使われている。
ビジネス要件やシステム要件によってはlinearizabilityより緩くconsistencyを管理して良いケースはあるだろうが、アプリケーションではなくDBMSで実装すべきだろうと思う。
"Similar issues arise if you want to ensure that a bank account balance never goes negative, or that you don’t sell more items than you have in stock in the warehouse, or that two people don’t concurrently book the same seat on a flight or in a theater."
via Check out this quote from Designing Data-Intensive Applications - https://learning.oreilly.com/library/view/designing-data-intensive-applications/9781491903063/ch09.html
在庫や予約の一貫性にもlinearizabilityが使われる。
なお、CAPとACIDについてはこれらの記事に詳しかった。自分は用語を耳にしたことがあるだけで、全然腹落ちできてなかったとことに気がついた。
私なりに理解をまとめると、
- consistency modelを正しく理解することと、システム要件を正しく理解することが非常に重要
- consistencyの問題はアプリケーションではなくDBMSで解決するのが良さそう
あたり前のことしか言えてない…。
