Fair Share Replication Scheduler Implementation (3.x)

[nickva]

Fair share replication scheduler allows configuring job priorities
per-replicator db.

Previously jobs from all the replication dbs would be added to the scheduler
and run in a round-robin order. This update makes it possible to specify the
relative priority of jobs from different databases. For example, there could be
low, high and default priority _replicator dbs.

The original algorithm comes from the A Fair Share
Scheduler paper by Judy Kay and Piers Lauder. A summary of how
the algorithm works is included in the top level comment in the
couch_replicator_share module.

There is minimal modification to the main scheduler logic. Besides the
share accounting logic each cycle, the other changes are:

• Running and stopping candidates are now picked based on the priority first,
  and then on their last_started timestamp.

• When jobs finish executing mid-cycle, their charges are accounted for. That
  holds for jobs which terminate normally, are removed by the user, or crash.

Other interesting aspects are the interaction with the error back-off mechanism
and how one-shot replications are treated:

• The exponential error back-off mechanism is unaltered and takes precedence
  over the priority values. That means unhealthy jobs are rejected and
  "penalized" before the priority value is even looked at.

• One-shot replications, once started, are not stopped during each scheduling
  cycle unless the operator manually adjusts the max_jobs parameter. That
  behavior is necessary to preserve the "snapshot" semantics and is retained in
  this update.

[nickva]

To help test the PR I created a silly script which runs with a local ./dev/run -n1 cluster. It configures replication jobs and shares for three _replicator dbs and then continuously samples the proportion of running jobs in each db:

https://gist.github.com/nickva/7e86b3df19537a60372217e0f68b693a

So for the default parameters it might output something like:

 ** run stats num dbs: 3, total jobs: 100
rdb1/_replicator 66 66%
rdb2/_replicator 23 23%
rdb3/_replicator 11 11%

 ** run stats num dbs: 3, total jobs: 100
rdb1/_replicator 61 61%
rdb2/_replicator 31 31%
rdb3/_replicator 8 8%

With a configuration where the shares are all even (100) but the dbs have an uneven number of jobs, after 5-10 minutes there should be a roughly even share of running jobs from each db, even though one db has 500 jobs and others have less.

INTERVAL = 20000
CONFIG = {
    "replicator": {
        "max_jobs": "100",
        "max_churn": "20",
        "interval" : str(INTERVAL),
    },
    "replicator.shares": {
        RDB1 : "100",
        RDB2 : "100",
        RDB3 : "100",
    }
}
REPS = {
    RDB1 : 200,
    RDB2 : 300,
    RDB3 : 500,
}

 ** run stats num dbs: 3, total jobs: 100
rdb1/_replicator 30 30%
rdb2/_replicator 34 34%
rdb3/_replicator 36 36%

 ** run stats num dbs: 3, total jobs: 100
rdb1/_replicator 29 29%
rdb2/_replicator 33 33%
rdb3/_replicator 38 38%

[davisp]

My initial review of this PR didn't find anything major in terms of the implementation. Though I do think we're missing a high level overview comment in the couch_replicator_share module that provides a high level mental model for how this works. I know there's a paper I can go read for more detail but a quick two or three paragraphs that explain how shares and charges work and their relation I think would be a pretty good starting point. Along with maybe a couple scenarios that would describe how the priority calculations work out.

Other than that most of my comments were style nits.

[davisp]

+1. Awesome work as per usual.

[nickva]

Will merge the PR and noting that I still owe a documentation update for it.