# Serialization, Persistence, and Immutability
**Due: Sept 26, 2021, 11:59:59 pm, v1**

This project builds on the previous to add persistence. You should end
with a project that saves files and can retrieve them the next time it
starts. Though your system won't yet have a way to retrieve old
versions of file (a la `Elephant`), all versions of all nodes
and directories are stored forever.

We'll reach persistence by dividing each written file into chunks,
and writing metadata referencing those chunks to a *log*. The high points of this
project include the following:
- Rabin-Karp fingerprints: use content-defined chunk
  boundaries to split large files, as in `lbfs`.
- (Meta-)data will be serialized using Google Protocol Buffers.
- The filesystem will be made permanent by writing the log, and all
  file data, to disk.
- Time travel.

## Setup

This repository
contains the following files:
- `main.go` - Scaffolding for P2, which you don't have to
  use. References files in `dfs` in same directory. 
  You run, for example, like `go run main.go -d -m dss2`.
- `exampleMetaLog` - a short log resulting from copying three files
  into the FS.
- `protoget.go` - parses the log. `go run protoget.go
  exampleMetaLog`. You might first have to run the two `go mod`
  commands, and also create the golang version of the prototype file.
- `rk.c` and `rktest.c` - C version of rabin-karp
  chunking. Compile ("gcc -o rk rk.c rktest.c") and run on
  `testfile`. Insert two spaces at
  the beginning of the first line
  and try again. The results should differ only in the length of the
  very first chunk.
  similar. Your `go` version of finger-printing should produce
  the same results.
- `testfile` - File to test chunking on.

Do not modify `main.go`, and make
the whole thing conform to [this video](https://sedna.cs.umd.edu/818/movies/p2testing.mp4).
Compile the protobuf definition in `pb/dfs.proto` as `protoc --go_out=. *.proto`
**Note:** the resulting file `dfs.pb.go` might have the incorrect
package name. If so, change it to `pb`.
You *may* create new files under `dfs/`, and
modify any of the files you see there. Please **do not** modify `main.go`.

Install the base protocol buffers with: `brew install protobuf`
(v3.60) or on Ubuntu: `sudo apt install -y protobuf-compiler`. 

The current protocol buffers main page is
[here](https://developers.google.com/protocol-buffers), and a 
Go tutorial [here](https://developers.google.com/protocol-buffers/docs/gotutorial).


As this project builds on the previous, you need to have a working
base. You can download my code from [here](https://gitlab.cs.umd.edu/keleher/cmsc818epublicf2021/-/blob/master/p1/dfsSolution.go).
This code is rough, but does fulfill the requirements of the
project. Bug-fixes and improvements are welcome. 

## Terminology
We name blocks of data through cryptographic hashes. In this
project, taking the "hash" of an object is using `SHA1` to create a
cryptographic hash of an item, and then
`base32` to create an ASCII representation of that hash value. Both
are easily created by calling packages in Go's standard 
library. Go objects are first serialized in `protobuf` representation, and
then hashed as above.

- A file's metadata is contained in a structure called a DNode.
- The *sig* of a DNode is a hash of that DNode.
- The *sig* of a data block is a hash of that data block.


## Overview

We are going to make our file system from P1 into a *persistent* file system,
meaning that it will save files to permanent storage (the disk), and read it
from permanent storage when starting up.

There are two key abstractions:
- A single, *monotonically-increasing log* for all DNode metadata. DNodes
  reference other DNodes and file blocks (the data).
- File blocks, which are saved off independently in the underlying
  file system.

The log must be defined and written to disk in such an order that *any prefix
is consistent*. In other words, the log will never have holes. Though the log
might not be *complete* (might not includes the most recent changes) it will
never have DNodes containing references to DNodes that are not
located earlier in the log.

## System Design
Our approach will be fairly simple, but incorporate some asynchrony in order
to aggregate writes and changes to the namespace hierarchy into smaller
numbers of changes.

Modified data is tracked using the `dirty` field of the DNode structure.
Dirty data needs to be saved to stable
storage and dirty metadata needs to be saved to the log.

### Asynchrony
Rather than immediately pushing changes directly to disk when a
`write()` call arrives from FUSE, we let a periodic asynchronous `flusher()`
coroutine write them instead. The advantage of this is that many small
modifications, potentially even to different files, can happen within
a short period of time. For this project we are using a period of five
(5) seconds, which can encompass quite a few changes if directories
are being copied or compiled.



## A File Creation End to End
Let's assume we are copying a small file `foo` into our an empty file
system. The following is roughly the sequence of operations that must
occur:

1. `create()` call:
    - `foo`'s metadata is created.
    - The root's metadata is modified to include `foo`.
	- `foo`'s and the root's metadata are both marked *dirty*.

1. A `write()` call to `foo`:
    - Copy the written data into the DNodes `.data` field.	
    - Update `foo`'s metadata to describe the new data, and mark all
      relevant metadata as dirty.
1. More `write()` calls:
    - Same as above.
1. `flush()` call:
    - "Finalize" the writes by dividing them into blocks via
	   Rabin-Karp, and de-allocate the data slice. 
   - Update `foo`'s `ChildSigs` to include the hashes of all the blocks.
   - Write each block as a separate file, named by sig, into the *chunkPath*
     directory (should be a **-c <chunkpath>** option, defaults to
     **chunks/** in the current directory.
1. `flusher()` coroutine wakes up and runs:
   - Traverses the entire namespace in postorder (on any branch marked dirty), and
     in push dirty DNodes to the in-memory log. In this case, the
     `DNodes` will consist of one for `foo`, and one for the root.
   - Writes the modified tail of the log to the end of the existing
     log. In this case, the log is intially empty.
   - Set all `dirty` flags to `false`.
1. File system killed.
1. On subsequent startup, the file system must be recreated by reading and applying
the log, as follows:
   - Read the entire log from start to finish, saving associations
     between sigs and DNodes.
   - Keep track of the last root DNode: this will be the root of the
     system you re-instantiate. Any changes after this last root are lost.


## Issues

- **Synchronization**: 
Fuse may call multiple handlers in parallel, and any such handlers are
potentially running in parallel with the flusher. These must be
synchronized, even if means using a single lock for the entire file system.

- **Log Structure**: 
Consists entirely of metadata (DNodes) marshalled into protobuf
format, each prefixed by a `uint32` that gives the following
protobuf's length.  You are *not* required to page the log to disk;
you can write the entire new portion of the log in a single system
call.

- **Log Ordering**: 
The log consists of DNodes, which must be ordered as with a post-order
traversal of the tree. In other words, all file and directory versions
referenced by a specific version of a parent directory must come
before that parent directory in the log. 

- **Versioning**:
We are keeping every saved DNode, all saved data blocks, and
therefore we have the ability to "go back in time". This can be done
on a file-by-file, directory-by-directory, or root version base. In
the latter case, you can take the entire file system back to an
earlier time by just re-instantiating the file system from an earlier
version of the root.

- **Signatures, and where to keep them**
In the log, all connections, whether between directories and contained
files, or between files and the blocks making up their current
version, are maintained by tracking sigs. This information must
persists across file system restarts.

- **File Data Representation**
A file's data may at any time be represented in one of two ways: as a
sequence of sigs in `.DataBlocks`, or in the `.data` field. If a file
is currently in the former state and is accessed, either for reading
or writing, the file must be instantiated by reading the datablocks,
in order, into `.data`.

- **Partial vs Full Namespaces in Memory**
The assumption in this document is that *the entire namespace always exists
in memory*. This does not mean that files are instantiated, however
and therefore does not necessarily make the system too inefficient.

- **Modules**
A directory is usually a package, packages are part of a module. You
must have `go.mod` and `go.sum` files in your top-level directory for
this to work. The good thing is that *all your local imports should be
local*. In other words:
  - Structure your directory as in the originally supplied files.
  - Create a `go.mod` in your top level (where `main.go` is):
    `go mod init p2`.
  - Import directories relative to the top level being "p2", e.g. the
  `dfs` package in the `dfs` subdir is imported as "p2/dfs". 
  - Before running you must execute `go mod tidy`, and this should be
  re-run when your imports (other than standard library imports) change.

- **Chunking**
  See [Wikipedia](http://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm)
  for a detailed explanation of Rabin-Karp chunking. 
  Your chunking approach should use 31 as your prime, 32 bytes as the length
  of the hash, and min/target/max chunk sizes of 2048/4096/8192 bytes.
  
  You can find a C version of the algorithm 
  in the starter files for this project. Translation to go is quite straightforward,
  though there are NO implicit type conversions between different types
  of integers: you need to use type conversions.

## `protobuf` serialization
DNodes must be serialized through
`proto.Marshal` and `proto.Unmarshal` from the standard
library.
There are two tricky aspects.
First, the package will only marshal *exported* fields of a
struct, i.e.
capitalized fields.
This can be convenient, as fields that need to be saved can be
capitalized and those that are ephemeral can start with a lowercase
letter.
For example, the
following is a possible definition for a DNode:

    type DNode struct {
       Name      string
       Attrs     fuse.Attr
       Version   int
       PrevSig   string // used for versioning
       ChildSigs map[string]int
       DataBlocks []string
    
       sig       string
       dirty     bool
       parent    *DNode
       kids      map[string]*DNode
       data       []byte
    }

The first six fields are included in the marshalled version; the
others are not.

Every distinct DNode (one per version of a file) is uniquely
identified by its signature, which is the `base32` version of
the hash of its `protobuf`-marshalled value.
Each time a DNode is modified and written to the object store, its
hash (signature) is different and it is therefore stored under a
different key.
The signature allows a saved directory, for example, to precisely
specify the appropriate snapshot of the DNode's state.

`.kids` is not capitalized and will not be saved.
This is appropriate, because it is not needed to persist a directory.
However, the saved version of a directory *does* need to be able
to name the files/versions it contains.
These are named by `.ChildSigs`.
`.kids` is used only during runtime, and `.ChildSigs` is used only
in the persistant representation of the node.

Likewise, the saved version of the node should not contain the file's
`.data`.
Instead, it should contain signatures naming or more blocks of data
that contain the file's data.


## Testing

I will be testing all projects on **lagoon**. If you do not have an
account and would like one, email me.

There are many moving parts here, and you will have to write a
bit of code. *Test parts separately* when possible. Go makes it
easy and fast to take small sections of code and run them by
themselves. For example, I used `marshal.go` (below) to help me
understand `protobuf` marshalling. You can do similar modular testing for
the key-value store, for the fingerprint chunking, etc.

Your code should support the following command-line arguments:
- **-d** - toggles printing of debugging output. Default: `false`,
  i.e. no debugging info is printed.
- **-c <chunkpath>** - directory to store and retrieve chunks.
- **-C <chunkpath>** - shows size and offset from beginning of file for every
  chunk created.
- **-f <seconds>** - Default: specifies the periodicity of the
  flusher, in seconds. Default: 5.
- **-m <mountdir>** - Default: `dss` in current directory.
- **-n** - "new file system": reset the file system to
  initial state.
- **-t <time string>** - Time travel: specifies that the file system
  should reflect a specific time, AND that the resulting file system
  is read-only. Example: `-t "2021-09-15T12:40:28"`

## Grading


I will assign grades vaguely as follow:
- 50 pts - persistence works. At a minimum:
  - untar `redis`
  - compile it
  - kill
  - restart, remove a single `.o` file and re-compile
- 15 pts - rabin-karp finger-print-defined blocks
   - I'll copy in a file, kill the filesystem, and use `protoget` to look at the
    signatures and lengths of the resulting data blocks. Running your
    program w/ `-C` should print created blocks (see video), and these
    should correspond to the output of `rk`.
    The resulting blocks should be of lengths: 7141, 6482, 7778, 8192, 7500, 8192, 2101, 7995, 4888, 8192, 8192, 8111.
- 20 pts - asynchronous writing of data via goroutine(s)
  - I'll verify by writing data and killing the file system before the flusher has a
    chance to run.	Note that **the flusher should print out a single
    dot after finishing each period**.
- 15 pts - time travel

[![Watch the video](https://sedna.cs.umd.edu/818/movies/p2small.png)](https://sedna.cs.umd.edu/818/movies/p2testing.mp4)



## Submit

Submit by pushing your file system back to your repository. Include in
 the top level of your P2 directory a README.md file describing what
 works, what doesn't, and how to run your code. Note that your code
 *should* be run exactly as above.




