Homework 3: Quorum KVS

Homework 3: Quorum Consensus in a Distributed KVS

In this assignment you will implement a distributed key-value store (KVS). Your implementation will do replication to provide single-copy consistency using classic R/W/N quorum consensus; R and W will be set via parameters. When the usual constraints are not met (i.e. R+W <= N, or W <= N/2), all bets are off: you are not expected to provide one-copy consistency under these circumstances.

Here's the protocol your KVS needs to support. Note that it's a minor extension of KVSProtocol in the bud sandbox:

    module QuorumKVSProtocol
      state do
        interface input, :quorum_config, [] => [:r_fraction, :w_fraction]
        interface input, :kvput, [:client, :key] => [:reqid, :value]
        # 2013-03-18: we're dropping the kvdel requirement
        # interface input, :kvdel, [:key] => [:reqid]
        interface input, :kvget, [:reqid] => [:key]
        interface output, :kvget_response, [:reqid] => [:key, :value]
        interface output, :kv_acks, [:reqid]
      end
    end

Some notes on quorum_config:

• Based on its (empty) key, the quorum_config input can only have one item at a time. You should also guarantee something stronger: after the first item is placed into that input, subsequent items should be "ignored". Allow exactly one configuration of R/W/N during the lifetime of a service.
• To simplify matters, you can ignore any inputs that arrive on the kv* inputs before quorum_config has received its first input.
• Rather than setting R and W directly, you will specify them as percentages of the N nodes in the system. The two fields of quorum_config should be set to values between 0 and 1.0, representing a percentage of the N nodes in the system. When calculating the values of R and W, be sure to round up the product of the corresponding fraction and N
• The input value 0 in quorum_config is special, and should be interpreted as setting R (resp W) to 1 (not 0!) regardless of N.
• The kv_acks output interface should be populated when kvput and kvdel requests have succeeded.

Getting Started

As a starting point, we are providing a "hard-wired" implementation of read-one-write-one ("ROWO") in the ptcrepo to illustrate the APIs. Don't reuse this code. You will want to design your solution as a set of reusable modules that will come in handy in later assignments.

Structuring Your Code

When you think about writing your code, here are some modules to keep in mind. You don't have to factor your code this way—the discussion here is just a suggestion. However, if you follow these guidelines then (a) it may be easier for you to write unit tests on individual modules and get your right, and (b) your code is more likely to live on in an open-source release :-)

• Local KVS: Please export the QuorumKVSProtocol from the ptcrepo. On each node you should use the BasicKVS implementation provided in ptcrepo.
• Membership: In this assignment let's avoid the complexities of maintaining quorum membership. Instead, please use the static membership scheme provided by the StaticMembership module from the ptcrepo. You can decide how you'd like to "deploy" this module and its state across nodes in your network; our ROWO example provides one reasonable scheme. (NB: Dynamic quorum membership is a tricky business! We may look at it later in the semester. Even if you have clever ideas on this front, keep them out of your homework solution for now.) Please include StaticMembership in your KVS so that we can insert tuples into add_member to configure each replica.
• Vote Counting: For R > 1 or W > 1, you will need to collect a sufficient number of acks before responding to a request. As you implement your solution to this assignment, think about writing standalone vote-counting protocols and implementations, and including or importing them into your quorum replication code.
• Versioning: As discussed in class, for 1 < W < N you may need to maintain version numbers or timestamps or the like on data items. This idea gets reused a lot as well (recall T/O concurrency control, not to mention revision control, multi-version databases, journaling filesystems, etc.) So try to write a reusable module for this.

Requirements

You are required to provide an implementation that satisfies the protocol above on any number N > 0 nodes, with any setting for quorum_config between 0 and 1.0. When the usual constraints on quorum consistency are met by the input to quorum_config, your implementation must provide single-copy consistency.

We have provided a simple "functional" test (tc_rowo.rb) for the protocol; our grading tests will work along similar lines but will be more extensive.

Submission

Please work on this assignment in groups of two. If you worked with a partner for Homework 2, please work with the same partner for this assignment. If you did not have a partner for the last assignment, please find a partner and email programthecloud@gmail.com to let us know who you're working with. If you can't find a partner, let us know.

Only one person from each pair (the "captain") will submit the assignment via email as you did with HW2. The subject of this email should be "Homework 3" and the first line of the body should contain the captain's student ID.

Attach a single file, quorum_kvs.rb, which should contain a module called QuorumKVS (which itself includes QuorumKVSProtocol and StaticMembership and uses BasicKVS):

module QuorumKVS
  include StaticMembership
  include QuorumKVSProtocol
  import BasicKVS => :kvs
end