<commit_before># uncorded - embedded distributed store for small immutable data

**Status: Experimental**

Uncorded is a use-case specific database for applications needing to add, remove and expire small immutable documents of data across a cluster of nodes. Uncorded is not a general purpose database and it assumes the size and number of active documents is extremely small.

A few uncorded characteristics:

  + intended for very small, short-lived, immutable data
  + expires data at a given point in time
  + prefers availability over cluster consistency
  + handles add/remove centric workloads where master-slave replication doesn't help

# Architecture Overview

Uncorded exposes three operations: add, remove and get. Add and remove operations need to be replicated across the cluster. Uncorded takes advantage of the remove-wins semantics of a [2P-set CRDT](https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type#State-based_2P-set) (conflict-free replicated data type) to achieve strong eventual consistency -- that is, all nodes should eventually arrive at the same state regardless of replication message ordering.

## Master-Master Replication Strategy

A state-based CRDT was chosen over an operation-based CRDT so we could forego the requirement of a reliable network ensuring idempotent message delivery. The downside of a state-based CRDT is that we always replicate a node's entire state. Uncorded's small and short-lived state is a great fit here so long as we don't hold remove-set values indefinitely.

Nodes publish changes to listeners via newline delimited JSON representations of their state. Listeners apply the state changes according to the [2P-set](https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type#State-based_2P-set) merge algorithm.

## Fault Model

### Adding a document

In order to make adding a document highly-available and fast, uncorded does not wait for any nodes, let alone a quorum, to acknowledge writes. This has two major repercussions:

  + No read-after-write consistency: it is the onus of consumers to implement adequate retries to compensate for replication lag.
  + It is possible to loose a document if the node that accepted the write fails before replicating to other nodes in the cluster.

### Removing a document

In order to make document removal highly available and fast, uncorded does not wait for any nodes, let alone a quorum, to acknowledge the removal. It is possible to remove the same document twice while a previous removal is replicated across nodes. Due to the eventually consistent nature of adding a document, it is possible to try and remove a token before it has been replicated to an uncorded node. It is important for consumers to retry token consumption for at least 1 second before declaring a token invalid.

### Replicating a document addition/removal

?

# Usage

Using uncorded requires firing up the API server and creating sets for use within your application.

```
const uncorded = require('uncorded');
const server = uncorded.createServer({
  discovery: uncorded.discovery.elb({
    region: 'us-east-1',
    elbName: 'uncorded-test-elb'
  })
});
const tokens = server.createSet('tokens');

// ... now start using your replicated set
const token = tokens.add({ user: 'bob' });
const found = tokens.get(token.id);
console.log(found.doc);
tokens.remove(token.id);
```

## Options

#### `log`

An instance of a [`bunyan`](https://github.com/trentm/node-bunyan) logger or an API compatible alternative.

#### `discovery`

An implementation of the [cluster discovery](#cluster-discovery) interface like the ELB cluster discovery module. If the `discovery` options is not specified, uncorded will warn and disable cluster discovery.

## Cluster Discovery

Uncorded supports pluggable cluster discovery. Discovery modules must be EventEmitters that appropriately produce `peer-added` and `peer-removed` events containing peer URLs.

### Cluster Discovery: ELB

Uncorded comes built-in with a module for discovering peers based on healthy instances registered with an AWS Elastic Load Balancer. Cluster discovery is accomplished by periodically querying AWS ELBs for healthy nodes. We'll start with polling every 5 seconds and see where we go from there. Option fields include:

  + `region`: the AWS region where the ELB and EC2 instances reside. (i.e. `us-east-1`)
  + `elbName`: the name of the Elastic Load Balancers the instances are registered with. (i.e. `uncorded-elb`)
  + `interval`: the period of time to delay between polling for healthy nodes.<commit_msg>README: include links to relevant AWS docs.<commit_after># uncorded - embedded distributed store for small immutable data

**Status: Experimental**

Uncorded is a use-case specific database for applications needing to add, remove and expire small immutable documents of data across a cluster of nodes. Uncorded is not a general purpose database and it assumes the size and number of active documents is extremely small.

A few uncorded characteristics:

  + intended for very small, short-lived, immutable data
  + expires data at a given point in time
  + prefers availability over cluster consistency
  + handles add/remove centric workloads where master-slave replication doesn't help

# Architecture Overview

Uncorded exposes three operations: add, remove and get. Add and remove operations need to be replicated across the cluster. Uncorded takes advantage of the remove-wins semantics of a [2P-set CRDT](https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type#State-based_2P-set) (conflict-free replicated data type) to achieve strong eventual consistency -- that is, all nodes should eventually arrive at the same state regardless of replication message ordering.

## Master-Master Replication Strategy

A state-based CRDT was chosen over an operation-based CRDT so we could forego the requirement of a reliable network ensuring idempotent message delivery. The downside of a state-based CRDT is that we always replicate a node's entire state. Uncorded's small and short-lived state is a great fit here so long as we don't hold remove-set values indefinitely.

Nodes publish changes to listeners via newline delimited JSON representations of their state. Listeners apply the state changes according to the [2P-set](https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type#State-based_2P-set) merge algorithm.

## Fault Model

### Adding a document

In order to make adding a document highly-available and fast, uncorded does not wait for any nodes, let alone a quorum, to acknowledge writes. This has two major repercussions:

  + No read-after-write consistency: it is the onus of consumers to implement adequate retries to compensate for replication lag.
  + It is possible to loose a document if the node that accepted the write fails before replicating to other nodes in the cluster.

### Removing a document

In order to make document removal highly available and fast, uncorded does not wait for any nodes, let alone a quorum, to acknowledge the removal. It is possible to remove the same document twice while a previous removal is replicated across nodes. Due to the eventually consistent nature of adding a document, it is possible to try and remove a token before it has been replicated to an uncorded node. It is important for consumers to retry token consumption for at least 1 second before declaring a token invalid.

### Replicating a document addition/removal

?

# Usage

Using uncorded requires firing up the API server and creating sets for use within your application.

```
const uncorded = require('uncorded');
const server = uncorded.createServer({
  discovery: uncorded.discovery.elb({
    region: 'us-east-1',
    elbName: 'uncorded-test-elb'
  })
});
const tokens = server.createSet('tokens');

// ... now start using your replicated set
const token = tokens.add({ user: 'bob' });
const found = tokens.get(token.id);
console.log(found.doc);
tokens.remove(token.id);
```

## Options

#### `log`

An instance of a [`bunyan`](https://github.com/trentm/node-bunyan) logger or an API compatible alternative.

#### `discovery`

An implementation of the [cluster discovery](#cluster-discovery) interface like the ELB cluster discovery module. If the `discovery` options is not specified, uncorded will warn and disable cluster discovery.

## Cluster Discovery

Uncorded supports pluggable cluster discovery. Discovery modules must be EventEmitters that appropriately produce `peer-added` and `peer-removed` events containing peer URLs.

### Cluster Discovery: ELB

Uncorded comes built-in with a module for discovering peers based on healthy instances registered with an AWS Elastic Load Balancer. Cluster discovery is accomplished by periodically [querying AWS ELBs for healthy nodes](http://docs.aws.amazon.com/ElasticLoadBalancing/latest/APIReference/API_DescribeInstanceHealth.html) and [resolving their IP addresses](http://docs.aws.amazon.com/AWSEC2/latest/APIReference/API_DescribeInstances.html). We'll start with polling every 5 seconds and see where we go from there. Option fields include:

  + `region`: the AWS region where the ELB and EC2 instances reside. (i.e. `us-east-1`)
  + `elbName`: the name of the Elastic Load Balancers the instances are registered with. (i.e. `uncorded-elb`)
  + `interval`: the period of time to delay between polling for healthy nodes.
{'fraction_non_alphanumeric': 0.06431005110732538, 'fraction_numerical': 0.002022998296422487, 'mean_word_length': 4.723948811700183, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 6, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3446337', 'n_tokens_mistral': 2446, 'n_tokens_neox': 2310, 'n_words': 1216}