Add diff command.

## Problem

Between two backup's of S3 bucket, there is no need to sync keys that have not changed. We only want to sync keys that have changed or that are new.

When doing a PutCopy with S3, S3 will take care of not doing useless work (using etag + modtime). However, simply doing the PutCopy call takes about 1s.  For 44 million keys, it takes a long time.

## Solution

Doing a list of a large bucket takes less than an hour. It's thus practical to:

* Keep a listing of last backup's bucket.
* Do a listing of the current bucket state.
* Preprocess the keys that will result in nop syncs with S3.
* Create a new listing file that only contains keys needing to be sync'd.

The diff commands takes two readers containing s3.Key objects in JSON:

* The __old__ reader contains a listing of the previously sync'd keys.
* The __new__ reader contains a listing representing the current state of the bucket to sync.

Then, for each key in __old__, it will record the etag of that key. Then, for each key in __new__, it will check if the etag is already known of __old__.

* If the etag is already known; it means the content of the key hasn't changed. There's nothing to sync.
* If the etag is not known: it means the content has changed _or_ the key is a new entry since __old__.  Either way, it should be sync'd.

If a key was in __old__ but is not in __new__:

* The key was deleted: nothing will be done and it will remain in the backup bucket.
* The key content was changed: the key path will be overwritten by the new version, as the new key will appear with a new etag in the __new__ reader.

To sum up, the output is list of S3 keys, in JSON, representing only the keys that should be sync'd, where _keys that should be sync'd_ means _keys that have changed or a new_.

## Implementation:

The coverage is:

```bash
$ go test ./... -cover
ok  	github.com/Shopify/brigade/cmd/diff	0.020s	coverage: 93.8% of statements
```

In action, it looks like this:

![diff-demo](https://cloud.githubusercontent.com/assets/1189716/3334326/202b540c-f7fe-11e3-94b9-e3e05c7212e7.gif)


r: @boourns, @bouk , @camilo 
cc: @benbjohnson, @snormore,  @fbogsany
Ugh, I just wish Go had a proper set type

Bouke


On Mon, Jun 23, 2014 at 4:11 PM, Antoine Grondin <notifications@github.com>
wrote:

> In cmd/diff/types.go:
>
> > @@ -0,0 +1,15 @@
> > +package diff
> > +
> > +type keySet interface {
> > +	Contains(string) bool
> > +	Add(string)
> > +	Len() int
> > +}
> > +
> > +func newKeyMap() keySet { return make(keymap) }
> > +
> > +type keymap map[string]struct{}
> > +
> > +func (k keymap) Contains(key string) bool { _, ok := k[key]; return ok }
> > +func (k keymap) Add(key string)           { k[key] = struct{}{} }
> > +func (k keymap) Len() int                 { return len(k) }
>
> Two reasons:
> 1. map[string]struct{} takes less memory than map[string]bool
> 1. I'm wrapping the set in an interface so it's easier to replace the
> implementation by another one without changing the code everywhere.
>
> The map based set consumes a lot of memory and I've been working on
> different set implementations. Having this interface makes it easier to
> plug them in and see how they compare.
>
> —
> Reply to this email directly or view it on GitHub
> <https://github.com/Shopify/brigade/pull/4/files#r14097139>.
>