# Project 5a: 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.
1. 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.
1. 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**.