Fix two bugs in the global balancing phase

* Nodes with 0 shards were being ignored because wrong datatype.
* The limit was being ignored because max not min.

BugzID: 24680

Allow skip straight to global phase

When rebalancing a DB-per-user cluster with small Q values its typical
that

a) the local phase takes a loooong time, and
b) the local phase doesn't suggest any moves

While the local phase should still run at least once, we'll expose a
flag to skip straight to the global phase since we'll need to run the
plan generator many many times and we can't afford to wait.

BugzID: 24680

Refuse to place shards on decom:true nodes

BugzID: 24420

Rely on decom:true attribute to filter decom nodes

BugzID: 24420

Ensure that the owner of a doc is also a host

BugzID: 24395

Rewrite rebalancing plan generator

This patch splits the functionality of the module out into three
classes or work:

* Fixing zoning and replica level violations
* Contracting a cluster
* Rebalancing shards across a cluster

The implementations of the first two features are pretty similar - find
the shards that need to be moved, then choose an optimal home for each
of them.  By default the contraction code will remove shards from nodes
in the "decom" zone, and the rebalancing code will ignore that zone
entirrely. An optimal home is a node that

a) is in the correct zone, and
b) has the fewest # of shards for the DB among nodes in the zone, and
c) has the fewest total # of shards among nodes satisfying a) and b)

The implementation of rebalancing is a bit more complicated.  The
rebalancing algorithm looks roughly like this

For DB in all_dbs:
    Ensure all nodes have at least (N*Q) div length(Nodes) shards
    Ensure no node has more than (N*Q) div length(Nodes) + 1 shards
For node in nodes:
    If node has more than TotalShards div length(Nodes) + 1 shards:
        Donate shard to another node

The net result is that each database is balanced across the cluster and
the cluster as a whole is globally balanced.

The current version of the module prints out shard move and copy
operations in a clou-friendly format via io:format.  It also returns a
list of {Op, #shard{}, node()} tuples representing the operations.

The rebalancer will stop after generating 1000 operations by default.
The limit can be customized by using the 1-arity versions of expand,
contract and fix_zoning, but note that the performance of the rebalancer
degrades as the number of pending operations increases.

BugzID: 23690
BugzID: 20770

Fix latent single-shard range hack

We had an off-by-one error when we fake #shard{} records for node local
databases. This fixes the issue. The bug was noticeable when attempting
to pass these shards to `fabric_view:is_progress_possible/1`.

BugzId: 22809

Use a consistent commenting syntax

Address comments from PR

Ensure all shards are moved off non-target nodes

BugzID: 20742

Stabilize mem3_util:owner/2

BugzID: 21413

Move rotate_list to mem3_util

Support balancing across a subset of nodes

mem3_balance implicitly assumed the set of nodes over which the DB is
hosted is expanding.  We need to make a couple of small changes in the
case of cluster contraction.

BugzID: 20742

Fix load_shards_from_disk/2

load_shards_from_disk/2 did not expect #ordered_shards to be returned
from load_shards_from_disk/1. Since it uses a list comprehension the
mistake is silently squashed, resulting in an empty list.

In production this manifests are the occasional failure, where 'n' is
calculated as 0, causing quorum reads to fail. The very next call
succeeds as it reads the cached versions and correctly downcasts.

BugzID: 20629

Preserve key and incorporate range into rotation key

we're not rotating by DbName any more

refactor choose_ushards

Zero out shard caches on upgrade

The mix of #shard and #ordered_shard records breaks ushards.  Different
nodes can start returning different results.

Add function to assist with rebalancing

This function takes either a database name or a list of shards and a
list of target nodes to balance the shards across. Every node with
less than a fair share of shards will steal shards from the node with
the most shards as long as both shards are in the same zone.

BugzID: 18638

Use a private record for event listener state

Fix trivial typo

Balance replication ownership across nodes

The previous algorithm was biased towards low-numbered nodes, and in the
case of a 3 node cluster would declare db1 to be the owner of all
replications.  We can do better just by leveraging the existing
ushards code.

There's a possibility to refactor this as a new ushards/2 function if
that's perceived as useful.

BugzID: 19870

Update to use the new couch_event application

Choose ushards according to persistent record

The order of nodes in the by_range section of "dbs" documents is now
promoted to the principal order for ushards. Ushards still accounts
for Liveness, selecting the first live replica and still supports
Spread by rotating this list using the CRC32 of the database name
(since many databases will have the same layout).

If by_range and by_node are not symmetrical then by_node is used and
order is undefined to match existing behavior.

If two shards differ we need to sync

There's no security if two shards return different answers but it gives
us enough of a signal to know that we need to trigger a full on
synchronization.

BugzId: 18955

Moving shard maps _membership endpoint to _shards db handler

Add doc shard info endpoint

Fix _membership/$DBNAME api endpoint

This switches the JSON key to be a binary, as required by jiffy.

Also, remove extraneous <<"parts">> path from the url.

Show full shard range.

Update to use new multi rexi_server protocol

Handle the #doc_info case in changes_enumerator

This is to handle the special case where the user migrates a CouchDB
database to BigCouch and they have not yet compacted the
database. Once the database has been compacted, this #doc_info clause
should never be encountered.

Don't log when ensuring dbs exist

Add function to determine shard membership locally

mem3:belongs/2 allows you to determine if a given doc id belongs to a
given shard (whether a #shard{} record or just the filename of a
shard) without looking up the shard map or making any remote
calls.

Change API to function per level

Switch to couch_log

Add license headers

Add ejson_body to all mem3 open_doc attempts that need it

Remove references to margaret

Build with rebar

Fix up copyright headers

New build system for mem3

Remove Cloudant build system remnants

Merge pull request #43 from cloudant/guard-against-empty-list

Guard against empty list

Guard against empty list

Rotating an empty list gives badarith so add a guard clause, since the
result of rotating an empty list is well known.

BugzID: 17801

Merge pull request #42 from cloudant/17801-spread-the-pain

BugzID: 17801

Spread ushards load to more nodes

In some cases, notably q=1 databases, the current ushards algorithm
will always choose the same replica (because of the lists:sort and
order-preserving orddict). This causes a severely skewed load profile
if you have lots of these cases.

This patch rotates each group of nodes using the crc32 of the database
name, spreading out the load pretty evenly.

The patch is a little obscure because ushards still has remnants of
previous work (breaking nodes into the local, same zone, different
zone, but then deliberately merging local and same zone back together
because that was a silly idea).

BugzID: 17801

Ignore other config changes

Merge pull request #40 from cloudant/13179-refactor-config-registration

Use config app instead of couch_config

Updated the tests too

Use config app instead of couch_config

BugzID: 13179

Merge pull request #38 from cloudant/17185-reduce-log-spam

Replace cache miss log with metrics

BugzID: 17185

Merge pull request #39 from cloudant/15754-mem3-sync-backlog

Add an API for mem3_sync queue lengths

BugzID: 15754

Add an API for mem3_sync queue lengths

Replace cache miss log with metrics

This also adds metrics for cache hits and evictions as well as the miss.

Merge pull request #36 from cloudant/13605-fix-shards-badmatch

Protect against cache_hits on non-existant entries

BugzID: 13605

Protect against cache_hits on non-existant entries

This can happen if we load a shard set from the cache and then eject the
shards before processing the cache_hit '$gen_cast' message. Instead of
trying to be fancy and reinserting the shards into the cache directly we
just rely on the fact that they'll be reinserted normally on the next
request.

Merge pull request #35 from cloudant/15924-dont-resurrect-on-delete

Don't resurrect shards on deletion

Don't resurrect shards on deletion

In bigcouch and bigcouchplus (at least) the deleted property is a
binary, <<"deleted">>, and not an atom, deleted, as it used to
be. This causes mem3_shards to recreate a shard immediately after it
is deleted, leading to profound silliness.

BugzID: 15924

Merge pull request #33 from cloudant/11602-sync-security

BugzID: 11602

Merge pull request #34 from cloudant/explicit_zone_placement

Explicit zone placement

BugzID: 14920

Placement is always specified as a string

Remove cruft

Explicit zone placement

Check security objects during internal replication

If we detect that two shards have different values for a security object
during internal replication we automatically trigger a security object
synchronization.

BugzId: 11602

Relax the mem3_sync_security fix constraint

Instead of requiring that we only have an empty security object and a
single non-empty version that out numbers empties, we relax the fixable
constraint to be a single simple majority of (N/2)+1 objects of a single
value.

BugzId: 11602

Wait for rexi_server before adding a node

The race condition between a nodeup event and rexi_server starting was
causing some superfluous errors. This just waits for rexi_server to boot
before notifying mem3_sync_nodes.

Merge pull request #32 from cloudant/14654-mem3-sync-stuck-replications

Fix stuck internal replications after node down

BugzID: 14654

Fix stuck internal replications after node down

We weren't removing entries from the dict tracking what was in the job
queue. This looks like a bug after the switch from tuples to the #job{}
record which means its probably been around for quite awhile. Simple fix
is simply to use the correct dict key.

BugzId: 14654

Merge pull request #31 from cloudant/14348-node-redirects

Configurable redirect of mem3 push jobs

BugzID: 14348

Configurable redirect of mem3 push jobs

In order to faciliate smoother node replacements, mem3 can be
configured to redirect push jobs intended for one node (the failed
one) to another (its replacement). e.g,

[mem3.redirects]
dbcore@db1.foo.cloudant.com = dbcore@db2.foo.cloudant.com

BugzID: 14348

Remove obsolete appup

Merge 'origin/replicator', closes #16

Conflicts:
src/mem3_rep_manager.erl
src/mem3_sup.erl
src/mem3_util.erl

Case 13884

Add upgrade instructions

Export live_shards/2

Remove unused include_lib

Eventually we should insert the validation function automatically.

BugzID: 13780

Avoid #changes_args.db_open_options for compatibility

We'll add it once we deploy the new version of the #changes_args record.

BugzID: 13780

Look for 'deleted' and <<"deleted">> for compatibility

BugzID: 13780

Fix error causing crash on add_node

Merge branch '1.3.x'

Conflicts:
src/mem3.erl
src/mem3_cache.erl
src/mem3_nodes.erl
src/mem3_rep.erl
src/mem3_sup.erl
src/mem3_sync.erl
src/mem3_sync_event.erl

BugzID: 13780

Merge pull request #30 from cloudant/13606-node-info-ets

Publish node metadata in a protected ets table

BugzID: 13606

Remove remaining references to #state.nodes

Publish node metadata in a protected ets table

This allows for far cheaper access to the zone information.  The
fallback to gen_server:calls is only for the initial hot upgrade and can
be removed afterwards along with the code_change.

BugzID: 13606

Fix edge condition when loading shards from disk

BugzId: 13386

Remove custom appup

Don't include deleted dbs in mem3:fold_shards/2

The `delete` option was passed to couch_db:open_doc/2 which ended up
causing deleted databases to be included in mem3:fold_shards/2. This is
counterintuitive so is being removed.

Merge pull request #29 from cloudant/13511-1.3.x-improve-internal-replicator

Improve internal replicator configuration

BugzID: 13511

Improve internal replicator configuration

This work is needed to support the internal replication requirements for
cluster elasticity. This adds three new options:

  * batch_size - The number of revisions to replicate in a single batch
  * batch_count - The number of batches to replicate. The special value
    `all` means to replicate until finished.
  * filter - A 1-arity function that takes a #full_doc_info{} record and
    returns `keep` or `discard` that determines if that doc should be
    included in the replication.

Put mem3_sync replication exit messages on one line

Merge pull request #28 from cloudant/13529-reconfigure-ring-on-nodeup

Reconfigure ring on nodeup events

BugzID: 13529

Deduplicate lookup of special local databases

Reconfigure ring replications on nodeup

BugzID: 13529

Reply immediately if we already enqeueued the job

Really remove the Job from the Q

Reorder supervision tree to start mem3_nodes earlier

mem3_sync requires mem3_nodes to be running during init.

Merge pull request #20 from cloudant/13470-make-ushards-zone-aware_master

Reimplement mem3:ushards to honor all 5 properties

BugzID: 13470

Add upgrade instructions for .4,.6 -> .7

Merge pull request #27 from cloudant/fix-initial-sync

Add a manager for node syncrhonization

Add a manager for node synchronization

Don't be dumb about response formats

Guard code_change to prevent future surprises

Remove obsolete appup