Tla+ Specification Of The Bounded Staleness Together With Potent Consistency Guarantees
In my previous post, I had presented a TLA+ modeling of distributed information shop that provides the consistent prefix property. In this post, I extend this model slightly to construct bounded together with strong consistency. In fact the strong consistency specification is achieved when nosotros conduct hold the Delta on the bounded consistency every bit 1.
The TLA+ (well, PlusCal to last to a greater extent than accurate) code for this model is available at https://www.dropbox.com/s/qvmhhgjf9iycaca/boundedstrongP.tla?dl=0
WriteRegion == 1
ReadRegions == 2..NumRegions
chan = [n \in 1..NumRegions |-> <<>>];
We exercise D to announce the Delta on the bounded staleness consistency. Bounded staleness ensures that read results are non likewise stale. That is, the read functioning is guaranteed to run across at to the lowest degree all writes that precedes D disclose of updates earlier the read started. The read may potentially run across to a greater extent than or less to a greater extent than lately written values.
Strong consistency ensures that a read functioning returns the value that was in conclusion written for a given object. This is achieved past times using D=1.
The write percentage has three actions to perform: Commit the write inwards the write region, Multicast the write to the read regions, together with Receive/process an ack message from a read region.
These actions tin last performed inwards whatever arbitrary gild within the procedure loop, together with the model checker volition methodically explore all possible combinations of these actions interleaved alongside the read percentage actions to expose whatever flaws inwards the protocol.
The kickoff activity alternative is to commit a write inwards the write region. (We don't become into how that is implemented inwards the region; mayhap commit is done past times replicating the update to a write quorum inwards the region.) As a trial the CommittedLSN is incremented. Note that, inwards contrast to prefix consistency model, inwards the bounded staleness model the write is throttled to non advance to a greater extent than than D ahead of whatever of the read regions.
The mo activity alternative is to multicast a committed write to the read regions through the FIFO channels. together with this is an asynchronous replication. These may last sent whenever this activity is chosen, together with is non blocked on waiting whatever acknowledgements from the read regions.
This activity is precisely the same every bit inwards the prefix consistency model. The SentLSN variable denotes the in conclusion CommittedLSN write that is forwarded to the read regions together with is used for ensuring ordered replication.
The in conclusion activity alternative is to have an Ack message from the channel from a read region. The Progress variable keeps runway of the Ack messages, together with the CompletedLSN is updated to reverberate the highest write that is acknowledged past times all the read regions. Harking dorsum to activity 1, detect that the write percentage lazily disseminates this CompletedLSN information alongside the read regions past times piggybacking this to the commit-write messages. In this model the read-regions produce non utilize this CompletedLSN information, simply every bit I start to explore inwards the MAD questions, this tin last useful.
The read regions solely react to the replicated messages from the write region. The kickoff activity alternative is to have a message pending inwards the channel from the write region. The mo activity alternative is to ship dorsum an Ack message for whatever replication message that is non acknowledged yet. The actions are almost the same except for the line of piece of occupation updating the CompletedLSN at the read region.
CP == [][\A i \in ReadRegions:
CommittedLSN'[i] = CommittedLSN[i]
\/ CommittedLSN'[i] = CommittedLSN[i] + 1]_vars
The BoundedC invariant is to banking concern fit that the read regions are e'er maintained to last within the staleness saltation of the most recent CommittedLSN. (Since I used CommittedLSN variable for both read together with write regions, the TLA translator assigned CommittedLSN_ "with underscore" to the write region's version to distinguish it from that of the read regions.)
BoundedC == \A i \in ReadRegions :
CommittedLSN[i]=< CommittedLSN_[1]
/\ CommittedLSN[i]>= CommittedLSN_[1] -D
The SyncStep invariant is to banking concern fit the human relationship betwixt the CompletedLSN at the write percentage together with the copies maintained at the read regions.
SyncStep == \A i \in ReadRegions :
CompletedLSN[i] =< CompletedLSN_[1]
\/ CompletedLSN[i] > CompletedLSN_[1] -D
I kickoff wrote this predicate alongside "CompletedLSN[i] > CompletedLSN_[1] -1" simply the model checker was quick to tell me I was wrong. This is bounded past times D together with "not 1" every bit have operations at the read regions tin last asynchronous within the D staleness bound. Here the write percentage received Acks for its ii commits dorsum to dorsum together with hence the CompletedLSN at the write percentage was 2 versions ahead of those inwards the read regions.
No, it turns out, at that topographic point is yet surprisingly interesting together with useful tricks nosotros tin trace within this uncomplicated model.
As I mentioned in the review of the "Many Faces of Consistency" paper, at that topographic point is the "operational definitions of consistency" exposed to the customer together with at that topographic point is the "state based definitions consistency" used past times the developers, together with at that topographic point is a gap betwixt the ii where y'all tin play interesting tricks together with expose the customer operational consistency it cares virtually inwards an efficient way.
In our model nosotros approached things from the Earth consistency perspective together with made certain everything industrial plant safely. We tin yet add together a lot of efficiency together with functionality past times slightly changing how nosotros expose things to the customer from an operational consistency perspective. Azure Cosmos DB performs many interesting tricks nether the hood to implement many consistency models inwards concert. More on this later...
The TLA+ (well, PlusCal to last to a greater extent than accurate) code for this model is available at https://www.dropbox.com/s/qvmhhgjf9iycaca/boundedstrongP.tla?dl=0
The organisation model
As inwards the previous post, nosotros assume at that topographic point is a write percentage (with ID=1) together with read regions (with IDs 2 through NumRegions). The write percentage performs the write together with copies it to the read regions. There are FIFO communication channels betwixt the write together with read regions.WriteRegion == 1
ReadRegions == 2..NumRegions
chan = [n \in 1..NumRegions |-> <<>>];
We exercise D to announce the Delta on the bounded staleness consistency. Bounded staleness ensures that read results are non likewise stale. That is, the read functioning is guaranteed to run across at to the lowest degree all writes that precedes D disclose of updates earlier the read started. The read may potentially run across to a greater extent than or less to a greater extent than lately written values.
Strong consistency ensures that a read functioning returns the value that was in conclusion written for a given object. This is achieved past times using D=1.
The write percentage actions
The write percentage has three actions to perform: Commit the write inwards the write region, Multicast the write to the read regions, together with Receive/process an ack message from a read region.
These actions tin last performed inwards whatever arbitrary gild within the procedure loop, together with the model checker volition methodically explore all possible combinations of these actions interleaved alongside the read percentage actions to expose whatever flaws inwards the protocol.
The kickoff activity alternative is to commit a write inwards the write region. (We don't become into how that is implemented inwards the region; mayhap commit is done past times replicating the update to a write quorum inwards the region.) As a trial the CommittedLSN is incremented. Note that, inwards contrast to prefix consistency model, inwards the bounded staleness model the write is throttled to non advance to a greater extent than than D ahead of whatever of the read regions.
The mo activity alternative is to multicast a committed write to the read regions through the FIFO channels. together with this is an asynchronous replication. These may last sent whenever this activity is chosen, together with is non blocked on waiting whatever acknowledgements from the read regions.
This activity is precisely the same every bit inwards the prefix consistency model. The SentLSN variable denotes the in conclusion CommittedLSN write that is forwarded to the read regions together with is used for ensuring ordered replication.
The in conclusion activity alternative is to have an Ack message from the channel from a read region. The Progress variable keeps runway of the Ack messages, together with the CompletedLSN is updated to reverberate the highest write that is acknowledged past times all the read regions. Harking dorsum to activity 1, detect that the write percentage lazily disseminates this CompletedLSN information alongside the read regions past times piggybacking this to the commit-write messages. In this model the read-regions produce non utilize this CompletedLSN information, simply every bit I start to explore inwards the MAD questions, this tin last useful.
The read percentage actions
The read regions solely react to the replicated messages from the write region. The kickoff activity alternative is to have a message pending inwards the channel from the write region. The mo activity alternative is to ship dorsum an Ack message for whatever replication message that is non acknowledged yet. The actions are almost the same except for the line of piece of occupation updating the CompletedLSN at the read region.
Invariant checking together with testing
The consistent prefix invariant yet holds for this model every bit nosotros refined that model to obtain this one.CP == [][\A i \in ReadRegions:
CommittedLSN'[i] = CommittedLSN[i]
\/ CommittedLSN'[i] = CommittedLSN[i] + 1]_vars
The BoundedC invariant is to banking concern fit that the read regions are e'er maintained to last within the staleness saltation of the most recent CommittedLSN. (Since I used CommittedLSN variable for both read together with write regions, the TLA translator assigned CommittedLSN_ "with underscore" to the write region's version to distinguish it from that of the read regions.)
BoundedC == \A i \in ReadRegions :
CommittedLSN[i]=< CommittedLSN_[1]
/\ CommittedLSN[i]>= CommittedLSN_[1] -D
The SyncStep invariant is to banking concern fit the human relationship betwixt the CompletedLSN at the write percentage together with the copies maintained at the read regions.
SyncStep == \A i \in ReadRegions :
CompletedLSN[i] =< CompletedLSN_[1]
\/ CompletedLSN[i] > CompletedLSN_[1] -D
I kickoff wrote this predicate alongside "CompletedLSN[i] > CompletedLSN_[1] -1" simply the model checker was quick to tell me I was wrong. This is bounded past times D together with "not 1" every bit have operations at the read regions tin last asynchronous within the D staleness bound. Here the write percentage received Acks for its ii commits dorsum to dorsum together with hence the CompletedLSN at the write percentage was 2 versions ahead of those inwards the read regions.
MAD questions
1. Did nosotros explore the blueprint infinite thoroughly within this uncomplicated model?No, it turns out, at that topographic point is yet surprisingly interesting together with useful tricks nosotros tin trace within this uncomplicated model.
As I mentioned in the review of the "Many Faces of Consistency" paper, at that topographic point is the "operational definitions of consistency" exposed to the customer together with at that topographic point is the "state based definitions consistency" used past times the developers, together with at that topographic point is a gap betwixt the ii where y'all tin play interesting tricks together with expose the customer operational consistency it cares virtually inwards an efficient way.
In our model nosotros approached things from the Earth consistency perspective together with made certain everything industrial plant safely. We tin yet add together a lot of efficiency together with functionality past times slightly changing how nosotros expose things to the customer from an operational consistency perspective. Azure Cosmos DB performs many interesting tricks nether the hood to implement many consistency models inwards concert. More on this later...
0 Response to "Tla+ Specification Of The Bounded Staleness Together With Potent Consistency Guarantees"
Post a Comment