Homework 2: Single server Concurrency Control

Homework 2: Single-server concurrency control

In this assignment, we'll apply what we learned in lecture about concurrency control in general, and strict two-phase locking in particular, to the problem of implementing a "strongly consistent," transactional key-value store.

The assignment has two phases. In Phase 1, you'll implement a "lock manager" service that follows a Strict 2PL discipline, handling shared and exclusive lock requests for a set of abstract resources. In Phase 2, you'll use this lock manager to extend the key-value store BasicKVS into a transactional KVS. The transactional KVS will enforce serializable reads and writes to multiple keys.

Phase 1: the lock manager

Following a modular design philosophy, we'll keep the lock manager completely separate from the data store (or stores) that use it. Later in the class, we may be able to use the lock manager to protect resources other than keys in the KVS. As is common practice in Bud, we'll take the modular design a step further, separating the abstract "protocol" from its concrete implementation.

Strict 2PL Protocol

module LockMgrProtocol
  state do
    interface input, :request_lock, [:xid, :resource] => [:mode]
    interface input, :end_xact, [:xid]
    interface output, :lock_status, [:xid, :resource] => [:status]
  end
end

The unit of locking is the "resource." In a database setting, the resources could be data objects at various levels of granularity (e.g., the database, a table, a row, a cell). In our setting, the resources will be keys in the KVS.

The unit of scope and atomicity is an "xid" or transaction ID. A series of reads or writes with the same transaction ID are expected to run in apparent "isolation": that is, each transaction should perceive that it has exclusive access to the set of resources it reads or modifies, even if other transactions are concurrently accessing them. As we learned, the Strict 2PL protocol conservatively ensures isolation by making some transactions wait.

When we request a lock for a resource, we also specify a mode: either shared (:S) or exclusive (:X). At any time, a resource may have any number of shared locks associated with it, or one exclusive lock (which can only be granted if there are no shared locks). Because we are following the strict 2PL discipline, we never need to explicitly release locks: all locks are released at the end of the transaction.

The protocol should work as follows: when transaction T wishes to obtain a lock for resource R in mode M, it inserts a row [T, R, M] into request_lock. This request may succeed immediately, or it may be blocked by another lock. When a row [T, R, :OK] appears in lock_status, it signifies that the lock has been granted and T may proceed to read or write R (if the lock mode was :S or :X, respectively). Naturally, Bud does not explicitly block: the calling process implicitly blocks by "waiting" for the lock_status message to appear. Finally, when T reaches end-of-transaction, it inserts a row [T] into end_xact.

Phase 2: transactional KVS

Having a working lock manager will greatly simplify the job of supporting concurrent, multi-key updates to a KVS. Of course, our KVSProtocol will need to be extended to support transaction ids:

module XactKVSProtocol
  state do
    interface input, :xput, [:xid, :key, :reqid] => [:data]
    interface input, :xget, [:xid, :key, :reqid]
    interface output, :xget_response, [:xid, :key, :reqid] => [:data]
    interface output, :xput_response, [:xid, :key, :reqid]
  end
end

You can still use the BasicKVS as the storage "backend" for your transactional KVS -- and we recommend that you do so, to avoid code duplication. To support serializable transactions that span multiple keys, we'll use strict two-phase locking to guard the order in which transactions read and write keys, allowing only serializable interleavings:

1. xputs should not succeed (be translated into a kvput) until the transaction holds an exclusive (:X) lock on the key. Success is indicated by the appearance of a xput_response item with a corresponding xid and key.
2. xgets should not succeed (kvget) until the transaction holds a shared lock (:S).
3. The end_xact table defined by LockMgrProtocol should be accessible to the caller as well as the tables defined in XactKVSProtocol, so that a client can end its transaction and release locks.

Submission

Please work on this assignment in groups of two: if you can't find a partner, let us know.
Use this form to record partners. Only one person from each pair (the 'captain') will submit the assignment via email as you did with HW1. The subject of the email should be "Homework 2".

We'll test the functionality of the lock manager and the transactional kvs separately. This means partial credit for the lock manager is possible, but since the kvs depends on the lock manager, partial credit for the kvs unfortunately isn't possible. To keep things simple for our test scripts, please submit a file called lckmgr.rb that contains a module called TwoPhaseLockMgr (which itself includes LockMgrProtocol), and a file called xact_kvs.rb that contains a module called TwoPLTransactionalKVS (and includes XactKVSProtocol).