Skip to content

Latest commit

 

History

History
44 lines (44 loc) · 12.1 KB

README.md

File metadata and controls

44 lines (44 loc) · 12.1 KB

We are going to implement chain replication! The paper makes it sound so simple, right? Specifically, you will implement a replica that will form part of a chain replication chain. You will need to deal with links (replicas) going away and new links arriving. Because your replica may be the head or the tail, you will need to talk with clients.

The service we are providing to clients will be an incrementable hashtable. It is a hashtable whose key is a string and value is an integer. We cannot directly set the integer for a given key, but we can increment it. (We decrement by incrementing with a negative number.) If a key does not exist in the table, we act as if the key has a value of zero. the Two operations we can do on the table are:

  • get(key) - returns the current integer for the key, or zero if the key does not exist.
  • increment(key, value) - increments the key by the given value.

Since our implementations must interoperate, we will use gRPC with the proto file specified in chain.proto . You will also need to implement chain_debug.proto for testing purposes. Please use this pom.xml to build your code.

ZooKeeper will be our oracle (master) to tell us what machines are available and who is the tail and who is the master. You can start ZooKeeper with this jar file zookeeper-dev-fatjar.jar :

java -jar zookeeper-dev-fatjar.jar server 2181 datadir

ZooKeeper will startup listening on port 2181 and storing data in the datadir. You can then access ZooKeeper with addr:2181 where addr is the address of the machine you started ZooKeeper on.

When your program is started, you will be passed two arguments (along with others below): zookeeper_host_port_list control_path.

zookeeper_host_port_list should match the address:port of the machines running ZooKeeper. The control_path will specify a node in ZooKeeper where sequential nodes will be created to determine the chain's ordering. When a replica starts, it will create a sequential znode of the form: replica-XXXXX, where XXXXX is the sequence number. The replica with the lowest sequence number is the head, and the highest is the tail. Replicas should watch their predecessor's and successor's znodes for changes so that they can rebuild the chain if necessary and potentially start acting as the head or tail.

The znode will contain two lines: the first line is host:port of the gRPC for the replica. The next line will be your name.

Some details that we need to make clear to interoperate properly:

  • a replica should only respond successfully to HeadChainReplica.increment if it is the head. A successful response is generated when a head receives the ACK for the xid that corresponds to the increment invocation. For example, if a client calls increment('A' by 5) on the head and 'A' is currently 2 and 57 was the last xid, The head will generate an update with key='A', newValue=7, and xid=58. The head will not respond back to the client until it receives an ACK for xid 58 from its successor.
  • the state maintained by each replica, the table of keys and values, will reflect the state of the system when all pending requests have been acked. In other words, the state will be updated when an UpdateRequest is received even if the xid has not yet been acked.
  • when a successor connects to a new predecessor, it will send its current state to it's predecessor. The predecessor will match the predecessor against what it has received from zookeeper. It will do a state transfer with all pending updates (called sent in the paper) and send its state if needed. Before it sends the sent list, the predecessor will acknowledge any UpdateRequests based on the lastAck received from the successor.
  • a replica will get the addresses for its successors and predecessors from ZooKeeper. It should watch for changes. They will happen.
  • when issuing gRPC calls, you should use a timeout of 3 seconds.

command line

your program should take the following command line:

java -jar chainreplication.jar your_name grpc_host_port zookeeper_host_port_list control_path

the control_path will specify a node in zookeeper where sequential nodes will be created to determine the ordering of the chain. when a replica starts, it will create a sequential znode of the form: replica-XXXXX, where XXXXX is the sequence number. the replica with the lowest sequence number is the head and the highest is the tail. replicas should watch their predecessor's for changes so that they can rebuild the chain if necessary and potentially start acting as the head or tail.

the znode will contain two lines: the first line is host:port of the grpc for the replica. the next line will be your name.

i encourage you to test against each other's implementation, but do not share code!

test plan

here is the test plan that we will use: https://github.com/prayuj/chain-replication/blob/main/chain%20replication%20test%20plan.txt