Modeling A Replicated Storage Organisation Inwards Tla+, Projection 1

Why a TLA+ project?

The offset projection assignment inwards my distributed systems cast this semester was modeling a replicated storage arrangement inwards TLA+. Assigning a TLA+ projection makes me a rarity with distributed systems professors. A mutual projection would move a MapReduce programming assignment or a projection to implement a unproblematic distributed service (such equally a key-value store) inwards Java.

I mean value that a MapReduce deployment projection does non learn much most distributed systems, because MapReduce is a real unsmooth abstraction together with hides all things distributed nether the hood. Using MapReduce for the distributed systems cast projection would move similar handing people a mechanics certification upon successful completion of a driving test.

Implementing a unproblematic distributed service, on the other hand, would learn students that indeed programming together with debugging distributed systems is real hard. However, I would suspect that much of the hardship inwards that projection would move due to accidental complexities of the implementation linguistic communication rather than the intrinsic complexity of reasoning most distributed systems inwards the presence of concurrent execution together with failures. In a distributed systems deployment, it would move difficult for the students to evidence exhaustively for race conditions, concurrency bugs, together with exercise many possible combinations of node failures together with message losses. That is notoriously difficult for fifty-fifty the professionals, as shown past times this survey of 104 distributed concurrency bugs from Cassandra, HBase, Hadoop MapReduce, together with ZooKeeper.

I am of course of educational activity non against assigning an implementation projection inwards a distributed systems class. I come across the utility together with necessity inwards giving students hands-on programming sense on distributed systems. I mean value an implementation projection would move suitable for an advanced distributed systems class. The cast I am teaching is the offset distributed systems cast for the students, thus  an implementation projection would move unnecessarily complicated together with burdensome for these students, who are likewise taking three other classes.

I learn the distributed systems cast with emphasis on reasoning most the correctness of distributed algorithms, thus a TLA+ is a practiced agree together with complement for my course. Integrating TLA+ to the cast gave students a means to larn a hands-on sense inwards algorithms design together with dealing with the intrinsic complexities of distributed systems: concurrent execution, asymmetry of information, concurrency bugs, together with a serial of untimely failures.

TLA+ has a lot to offering for practise together with implementation of distributed systems. At Amazon, the engineers used TLA+ for modeling S3, DynamoDB, together with another production systems that come across a lot of updates together with novel features. TLA+ helped the engineers discovery several critical bugs introduced past times updates/features inwards the blueprint stage, which if non institute would accept resulted inwards large amount of technology scientific discipline endeavour subsequently on. These are detailed inwards a twosome of articles from Amazon engineers. I accept been hearing other TLA+ adoption cases inwards the industry, together with promise to come across increasingly to a greater extent than adoption inwards the coming years.

Modeling Voldemort replicated storage arrangement with client-side routing inwards TLA+

I wanted to assign the TLA+ modeling projection on a practical useful application. So I chose modeling of a replicated storage system. I assigned the students to model Voldemort with client-side routing equally their offset project.

Here is the protocol. The customer reads the highest version release "hver" from the read quorum (ReadQ). The customer thus writes to the write quorum nodes (WriteQ) the shop the updated tape with "hver+1" version number. The storage nodes tin flaming crash or recover, provided that no to a greater extent than than FAILNUM release of nodes are crashed at whatsoever moment. Our WriteQ together with ReadQ pick volition consist of the lowest id storage nodes that are upward (currently non failed).

I asked the students to model cheque with unlike combinations of ReadQ, WriteQ, together with FAILNUM, together with figure out the relation that needs to move satisfied with these configuration parameters inwards lodge to ensure that the protocol satisfies the single-copy consistency property. I wanted my students to come across how consistency tin flaming move violated equally a effect of a serial of unfortunate events (such equally untimely node choke together with recoveries). The model checker is real practiced for producing counterexamples where consistency is violated.

Simplifying assumptions together with template to larn the students started

I tried to continue the offset projection easy. We simplified things past times modeling the storing (and updating) of only a unmarried information item, thus nosotros didn't accept to model the hashing part. We likewise used shared memory. The customer straight writes (say via an RPC) to the db of the storage nodes. (It is possible to model a message-box at each process, together with I assigned that for the 2nd project.)

I likewise gave the students the template for the model. This helps my TAs a lot inwards grading. Without whatsoever template the students tin flaming larn inwards wildly unlike directions with their modeling. Below is the template. In instance you lot desire to give this a essay together with come across how you lot do with it, I volition await a calendar week or thus earlier I part my solution for the project1.

Extending to the 2nd project

I accept assigned the 2nd projection i time to a greater extent than on the modeling of a replicated storage system. But this fourth dimension instead of a quorum, "chain replication" is used for ensuring persistence together with consistency of storage. In the 2nd project, the replication is done past times server-side routing, together with the modeling includes message passing.

Links

Using TLA+ for teaching distributed systems (Aug 2014)
My sense with using TLA+ inwards distributed systems cast (Jan 2015)

Modeling Paxos together with Flexible Paxos inwards Pluscal together with TLA+

Modeling the hygienic dining philosophers algorithm inwards TLA+

There is a vibrant Google Groups forum for TLA+ : https://groups.google.com/forum/#!forum/tlaplus
Clicking on label "tla" at the terminate of the transportation service you lot tin flaming attain all my posts most TLA+

Share this post