Project 5: Logs and Replicated Objects

Overall Project Description

This project is about exploring the use of logs as a basis for shared objects.

More specifically, your tasks will be the following:

1. Create the tango library that defines the tango helper functions, and implements their connection with both the remote log server, and the application to which it is linked. Your library and protobuf definitions should allow register.go and stringSet.go to run, unaltered.
2. Define another object to implement a simple shared tree. This tree object should run with the same library and server defined for the other shared types.
3. Implement a "reader" mode for the tree app that will read all tree operations from the log, creating and linking up tree nodes as needed for consumers other than the tree creator. The reader should then print out all tree nodes, as shown below.

Part I: Details

This project is all about using the log, i.e. one of the possible outputs of a consensus algorithm like epaxos. However, epaxos is a bit unwieldy for this purpose, as we really want a totally-ordered log, not one that's just partially ordered. We could kludge this up w/ epaxos by just sending all requests to a single replica.

However, for ease of debugging we are going to use a toy log server in this project. We are also going to use some toy shared abstractions!

The files I'm giving you are in the following layout:

                    p4
            /     /    \       \
	   /     /       \       \
        pb   clients   library    server

• pb has a fully defined gRPC client/server protocol, though you can modify it. It also has a file for defining wire formats for the shared object types (mostly the tree creation).
• library defines some Interfaces and utility functions.
• server contains a fully-implemented log server.
• clients contains files implementing the register, stringset, and tree shared abstractions.

Log Server

The server is a simple gRPC server that responds to reads and writes. A write adds an Entry the log. A read fetches all log entries not already seen by the reader. Since the log is totally ordered, each read just returns a log suffix.

Note that a "reader" is just a single client of the log. The log might talk to multiple clients. Each client might manage multiple distinct objects ("one OID == one object"). For example, the tree consists of multiple objects, each with a distinct OID.

Shared Abstractions

Consider the register abstraction:

type Register struct {
	oid   uint64
	state uint64
}

func (r *Register) Apply(data []byte) {
	val := &SetUint64Value{}
	proto.Unmarshal(data, val)
	r.state = val.Value
}

func (r *Register) writeRegister(newstate uint64) {
	val := &SetUint64Value{}
	val.Value = newstate
	bytes, _ := proto.Marshal(val)
	UpdateHelper(bytes, r.oid)
}

func (r *Register) readRegister() uint64 {
	QueryHelper(r.oid, r)
	return r.state
}

The register's data is just the oid and the state. Three functions are defined, mirroring Figure 3 in the Tango paper. Your library will implement UpdateHelper and QueryHelper

Library functions

UpdateHelper

UpdateHelper defines a log entry and sends it to the server using protobufs. Log entries have two fields: Oid and Data. The first is just the object ID, the second is an opaque array of bytes that should be used to hold the operation's data. For the register, I just used a simple binary encoding to hold a 64-bit int. I converted the strings directly to data.

For the tree, however, you should define structure(s) in client.proto for create, setleft, and setright operations. Marshal this operation into the data buffer using proto.Marshal.

QueryHelper takes an oid and an ob object pointer as arguments. It should do two things:

1. Query the server to get any entries that are not yet local.
2. Apply all entries in the local version of the log matching Oid to the object ob. This object implements the TangoObject interface, and therefore has an Apply() method.

Note that even if there are no new objects coming from the server, there may be log entries that need to be applied to ob, as QueryHelper retrieves all entries, but only applies those with the requested Oid.

Testing

I will inspect your shared object implementation and run each. You should not be modifying the register and stringSet implementations.

> go run register.go
0
44
45
>

> go run stringSet.go
read strings: [one two three]
> 

Your tree-creating thread should make local calls that roughly mirror:

		one := createTreeNode(uint64(rand.Intn(1000)), "one")
		two := createTreeNode(uint64(rand.Intn(1000)), "two")
		three := createTreeNode(uint64(rand.Intn(1000)), "three")
		four := createTreeNode(uint64(rand.Intn(1000)), "four")
		SetLeft(one.oid, two.oid)
		SetRight(one.oid, three.oid)
		SetLeft(two.oid, four.oid)
		// print.....

The tree mutation events should be added to the log and the tree should be created locally. It doesn't matter if you create nodes locally first or just do the actual creation when they come through the log. Your code should then print a representation of the tree structure, such as:

> go run tree.go
"one": "two", "three"
"two": "four", ""
"three": "", ""
"four": "", ""
>

Likewise, another reader process running at the same time should see the same tree-node creation and mutation events, construct an exact copy of the tree, and print out the same representation:

> go run tree.go -r
"one": "two", "three"
"two": "four", ""
"three": "", ""
"four": "", ""

You will need to define your own implementation for the tree from scratch. Your tree nodes should conform to TreeNodeInterface. Operations consist of creating, setting the left child, and setting the right child.

Grading

• 45 pts : building the tango library to make the register and stringSet implementations work
• 40 pts : tree implementation
• 15 pts : reader

Notes

• All three of the shared object types might be running and adding operations to the log at the same time.
• You may add an enumeration for object types to the log entries. You might need to modify the calling parameters of QueryHelper.