tecnogram888 / Project4Skeleton

http://inst.eecs.berkeley.edu/~cs162/sp12/phase4.html
1 stars 0 forks source link

Phase 4: Build a Distributed Key-Value Store

In Phase 4 of your class, you will implement a distributed Key-Value Store that runs on multiple nodes on Amazon EC2 and uses Two-Phase Commit for atomic operations, replication for performance and fault-tolerance, and encryption for security. As in previous phases, you will submit an initial design document and a final design document apart from the code itself.

Architecture Diagram

Figure: A distributed Key-Value Store with replication factor of two.

Architecture Diagram

Figure: Functional digram of a distributed key-value store. Components in colors other than black are the key ones you will be developing for this project. Blue depicts GET execution path, while green depicts PUT and DEL; purple ones are shard between operations. Components in black might also require minor modifications to suite your purposes.

Skeleton Code:

The project skeleton you should build on top of is posted at https://github.com/CS162Berkeley/Project4Skeleton. If you have git installed on your system, you can run git clone https://github.com/CS162Berkeley/Project4Skeleton.git, or else you can download the tarball from here. Phase 4 builds on top of the Single Server Key-Value Store developed in Phase 3; however, several interfaces have been extended to support the required functionalities for Phase 4. You can reuse the code developed for Phase 3 and define additional classes and methods as you deem fit.

EC2 instructions:

Read the instructions carefully from this document regarding instantiation, operation, and termination of EC2 instances. As always, let us know in Piazza if anything is unclear.

Requirements:

Tasks (weight / approximate lines of code):

  1. (40% / 250 loc) Implement the 2PCMaster class that implements 2PC coordination logic in the Coordinator server. 2PCMaster must select replica locations using consistent hashing.
  2. (35% / 220 loc) Implement the 2PCMasterHandler class that implements logic for 2PC participants in Key-Value servers.
  3. (10% / 75 loc) Implement registration logic in SlaveServer (aka Key-Value Server) and RegistrationHandler in 2PCMaster. Each SlaveServer has a unique ID that it uses to register with the 2PCMaster in the coordinator.
  4. (10% / 75 loc) Implement the 2PCLog class that Key-Value servers will use to log their states during 2PC operations and for rebuilding during recovery.
  5. (5% / 40 loc) Implement encryption/decryption of stored values. The first message to be exchanged between client and server has to be an encryption key. Add a new message type "getEnKey" to the existing message types. The server has a single encryption key generated when it starts and shares this key with clients when requested using "getEnKey".You can store the values in encrypted format at server end.

Consistent Hashing

As mentioned earlier, Key-Value servers will have unique 64-bit IDs. The coordinator will hash the Keys to 64-bit address space. Then each Key-Value server will store the first copies of Keys with hash values greater than the ID of its immediate predecessor up to its own ID. Note that, each Key-Value server will also store the Keys whose first copies are stored in its predecessor.

Consistent Hashing

Figure: Consistent Hashing. Four Key-Value servers and three hashed Keys along with where they are placed in the 64-bit address space.

Sequence of Operations During Concurrent GET and PUT (DELETE) Requests

Sequence Diagram of Concurrent R/W Operations in Phase
4

Figure: Sequence diagram of concurrent Read/Write operations in Phase 4. "Phase 3" blocks in the digram refer to the sequence diagram of activities when clients write to a single-node Key-Value server, where the Coordinator is the client to individual Key-Value servers. GET request from Client 1 is hitting the cache in the above diagram; if it had not, the GET request would have been forwarded to each of the SlaveServers until it is found.

Sequence Diagram of Concurrent R/W Operations in Phase
3

Figure: Sequence diagram of concurrent Read/Write operations in Phase 3.

Your Key-Value server should support the GET/PUT/DELETE interface using the same format as Phase 3 with the following change(s):

Your Coordinator Server should perform Two-Phase Commit using the following extended KVMessage format (2PCMessage piggybacked on KVMessage):

Registration Messages

Encryption Messages

Error messages in addition to the ones in Phase 3:

Concepts you are expected to learn