You are viewing a plain text version of this content. The canonical link for it is here.
Posted to notifications@couchdb.apache.org by GitBox <gi...@apache.org> on 2021/01/26 23:29:40 UTC
[GitHub] [couchdb-documentation] nickva opened a new pull request #617: [rfc] Fair Share Replication Scheduler
nickva opened a new pull request #617:
URL: https://github.com/apache/couchdb-documentation/pull/617
Discussed on the [ML](https://lists.apache.org/thread.html/rebba9a43bfdf9696f2ce974b0fc7550a631c7b835e4c14e51cd27a87%40%3Cdev.couchdb.apache.org%3E)
Based on the Fair Share Scheduler paper by [Judy Kay and Piers Lauder](https://proteusmaster.urcf.drexel.edu/urcfwiki/images/KayLauderFairShare.pdf)
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [couchdb-documentation] bessbd edited a comment on pull request #617: [rfc] Fair Share Replication Scheduler
Posted by GitBox <gi...@apache.org>.
bessbd edited a comment on pull request #617:
URL: https://github.com/apache/couchdb-documentation/pull/617#issuecomment-768902077
> Interesting idea. Would it be, say, any design document which has a "replicator_config" field in it and we'd merge those, or have a single (special) doc id like "_design/replicator_config"? That might work, but I am also thinking this is for a 3.x branch and I would be hesitant to add a whole new configuration mechanism.
I'm not sure yet how it would look like / work in `main`, but I thought some configuration is necessary / useful there as well.
> We do have precedent of configuring per-db settings in other application such as in [ken](https://github.com/apache/couchdb/blob/3.x/src/ken/src/ken_server.erl#L264) and [smoosh](https://github.com/apache/couchdb/blob/3.x/src/smoosh/src/smoosh_utils.erl#L54). Settings applied via HTTP should not get lost, if they do it's a bug. They get written to the config files on disk. Where you thinking about needing to set it on every node perhaps? Yeah we'd have call config on very node if the setting is set via HTTP, and that's not ideal but probably too late to change in 3.x at this point.
I did not know that any online configuration changes get persisted to disk. Looking at https://docs.couchdb.org/en/latest/api/server/configuration.html#put--_node-node-name-_config-section-key this isn't trivial to me. Do you mean [this](https://github.com/apache/couchdb/blob/fa0aff9332c7260a4d5e50b354386f39308cbf17/src/chttpd/src/chttpd_node.erl#L72)? Perhaps we should document that.
Considering that configuring this feature requires server admin rights, it is actually some `_config` that should probably handle this (as opposed to some design document-like thing).
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [couchdb-documentation] bessbd commented on pull request #617: [rfc] Fair Share Replication Scheduler
Posted by GitBox <gi...@apache.org>.
bessbd commented on pull request #617:
URL: https://github.com/apache/couchdb-documentation/pull/617#issuecomment-768159926
> @bessbd I'd prefer not going to fork this until we're ready to do a 4.0 release, since we are still regularly getting typos and documentation corrections for 3.x and maintaining 2 branches even in just the main CouchDB repo is a pain.
>
> Until we're ready to actually commit the 4.x doc changes that is - at which point we'll fork.
>
> Sound good to you? If you want to start an ML thread, go ahead...
Sounds good to me, thank you @wohali ! In that case I'm suggesting to just omit the `3.x` from this RFC as `main` here is for `couchdb`'s `3.x`. (Can you please confirm the last part, @wohali ?)
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [couchdb-documentation] nickva edited a comment on pull request #617: [rfc] Fair Share Replication Scheduler
Posted by GitBox <gi...@apache.org>.
nickva edited a comment on pull request #617:
URL: https://github.com/apache/couchdb-documentation/pull/617#issuecomment-768421797
> For the configuration: have you considered doing this perhaps via design docs (or something like that)? I think that would be closer in "online-ness" to the databases.
Interesting idea. Would it be, say, any design document which has a "replicator_config" field in it and we'd merge those, or have a single (special) doc id like "_design/replicator_config"? That might work, but I am also thinking this is for a 3.x branch and I would be hesitant to add a whole new configuration mechanism.
> Ie. I can create-update-delete replicator databases, but to configure shares for them, I'd have to edit config (files and/or via the HTTP API - which is then either lost or gets splatted on restart unless I do some double booking).
We do have precedent of configuring per-db settings in other application such as in [ken](https://github.com/apache/couchdb/blob/3.x/src/ken/src/ken_server.erl#L264) and [smoosh](https://github.com/apache/couchdb/blob/3.x/src/smoosh/src/smoosh_utils.erl#L54). Settings applied via HTTP should not get lost, if they do it's a bug. They get written to the config files on disk. Where you thinking about needing to set it on every node perhaps? Yeah we'd have call config on very node if the setting is set via HTTP, and that's not ideal but probably too late to change in 3.x at this point.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [couchdb-documentation] nickva commented on a change in pull request #617: [rfc] Fair Share Replication Scheduler
Posted by GitBox <gi...@apache.org>.
nickva commented on a change in pull request #617:
URL: https://github.com/apache/couchdb-documentation/pull/617#discussion_r565416777
##########
File path: rfcs/017-fair-share-scheduling.md
##########
@@ -0,0 +1,216 @@
+---
+name: Formal RFC
+about: Submit a formal Request For Comments for consideration by the team.
+title: 'Fair Share Job Scheduling for CouchDB 3.x Replicator'
+labels: rfc, discussion
+assignees: 'vatamane@apache.org'
+
+---
+
+# Introduction
+
+This document describes an improvement to the CouchDB 3.x replicator to
Review comment:
It's specifically targeted towards the 3.x scheduler which is architecturally different from the `main` one. The 3.x branch is actually easier to apply these changes to so it seemed like a good place to start. For the main replicator we might have a separate RFC or just update this one with a PR.
As discussed below we don't have a 3.x branch yet, if and when do we could move it there.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [couchdb-documentation] nickva commented on a change in pull request #617: [rfc] Fair Share Replication Scheduler
Posted by GitBox <gi...@apache.org>.
nickva commented on a change in pull request #617:
URL: https://github.com/apache/couchdb-documentation/pull/617#discussion_r565519411
##########
File path: rfcs/017-fair-share-scheduling.md
##########
@@ -0,0 +1,216 @@
+---
+name: Formal RFC
+about: Submit a formal Request For Comments for consideration by the team.
+title: 'Fair Share Job Scheduling for CouchDB 3.x Replicator'
+labels: rfc, discussion
+assignees: 'vatamane@apache.org'
+
+---
+
+# Introduction
+
+This document describes an improvement to the CouchDB 3.x replicator to
+introduce fair resource sharing between replication jobs in different
+_replicator databases.
+
+## Abstract
+
+Currently CouchDB replicator 3.x schedules jobs without any regard to what
+database they originated from. If there are multiple `_replicator` dbs then
+replication jobs from dbs with most jobs will consume most of the scheduler's
+resources. The proposal is to implement a fair sharing scheme as described in
+[A Fair Share Scheduler][2] paper by Judy Kay and Piers Lauder. It would allow
+sharing replication scheduler resources fairly amongst `_replicator` dbs.
+
+The idea was originally discussed on the [couchdb-dev][1] mailing list and the
+use of the Fair Share algorithm suggested by Joan Touzet.
+
+## Requirements Language
+
+The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD",
+"SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be
+interpreted as described in [RFC
+2119](https://www.rfc-editor.org/rfc/rfc2119.txt).
+
+## Terminology
+
+`_replicator` databases : A database that is either named `_replicator` or ends
+with the `/_replicator` suffix.
+
+`shares` : An abstract representation of entitlement to run on the replication
+scheduler.
+
+`usage` : A measure of resource usage by jobs from a particular `_replicator`
+db. For the scheduling replicator this will be the total time spent running.
+
+`continuous` replications : Replication jobs created with the `"continuous":
+true` parameter. These jobs will try to run continuously until the user removes
+them. They may be temporarily paused to allow other jobs to make progress.
+
+`one-shot` replications : Replication jobs which are not `continuous`. If the
+`"continuous":true` parameter is not specified, by default, replication jobs
+will be `one-shot`. These jobs will try to run until they reach the end of the
+changes feed, then stop.
+
+`job priority` : A job attribute which indicates the likelihood of the job
+being executed before other jobs. Following the convention in the "Fair Share"
+paper, jobs with a lower priority value are at the front of the pending queue,
+and get executed first.
+
+`max_jobs` : Configuration parameter which specifies up to how many replication
+jobs to run on each `replication` node.
+
+`max_churn` : Configuration parameter which specifies a limit of how many new
+jobs to spawn during each rescheduling interval.
+
+---
+
+# Detailed Description
+
+The general idea behind the algorithm is to continuously monitor
+per-`_replicator` jobs statistics and update each job's priorities in
+proportion to the usage from all the jobs in the same `_replicator` db. To make
+sure all jobs eventually get a chance to run and do not starve, all the
+priorities are continuously boosted, such that jobs which haven't run for a
+while, and maybe be starved, will eventually get a chance to run.
+
+The algorithm has 3 basic components that can run mostly independently from
+each other:
+
+1) Keep track of `usage` for each `_replicator` db . In the paper this part is
+called "user-level scheduling". As jobs run, they send reports to this
+component. Those reports are accumulated for one period, then rolled up when
+the period ends. There is also a decay coefficient applied to account for
+recent historical usage (this is called `K1` in the paper). This ensures in
+absence of jobs running from a particular `_replicator` db, the usage would
+drops to 0 and the whole entry is removed from the table table altogether.
+
+ Every `UsageUpdateInterval` seconds (called `t1` in the paper):
+ For each `Db`:
+ ```
+ DecayCoeff = get_usage_decay_coefficient(0.5)
+ AccumulatedUsage = get_accumulated_usage(Db),
+ update_usage(Db, usage(Db) * DecayCoeff + AccumulatedUsage)
+ reset_accumulated_usage(Db)
+ ```
+
+2) Uniformly decay all process priorities. Periodically lower the priority
+values, and thus boost the priority, of all the pending and running jobs in the
+system. The paper in this step applies a per-process "nice" value, which is
+skipped in the initial proposal. It could be added later if needed.
+
+ Every `UniformPriorityBoostInterval` seconds (called `t2` in the paper):
+ For each `Job`:
+ ```
+ DecayCoeff = get_uniform_decay_coefficient(0.75),
+ Job#job.priority = Job#job.priority * DecayCoeff
+ ```
+
+[note]: If jobs were scheduled to run at an absolute future time (a deadline) this step could be avoided. Then, the effect of all the jobs needing to periodically move to the front of the queue would be accomplished instead by the current time (i.e. `now()`) moving head along the time-line.
+
+3) Adjust running process priority in proportion to the shares used by all the
+jobs in the same db:
+
+ Every `RunningPriorityReduceInterval` seconds (called `t3` in the paper):
+ For each `Job`:
+ ```
+ Db = Job#job.db,
+ SharesSq = shares(Db) * shares(Db),
+ Job#job.priority = Job#job.priority + (usage(Db) * pending(Db)) / SharesSq
+ ```
+
+### How Jobs Start and Stop
+
+During each rescheduling cycle, `max_churn` running jobs from the back of the
+queue are stopped and `max_churn` jobs from the front of the pending queue are
+started. This part is not modified from the existing scheduling algorithm,
+except now, the jobs would be ordered by their `priority` value before being
+ordered by their last start time.
+
+In addition, `one-shot` replication jobs would still be skipped when stopping
+and we'd let them run in order to maintain traditional replication semantics
+just like before.
+
+When picking the jobs to run exclude jobs which have been exponentially backed
+off due to repeated errors. This part is unmodified and from the original
+scheduler.
+
+### Configuration
+
+The decay coefficients and interval times for each of the 3 parts of the algorithm would be configurable in the `[replicator]` config section.
+
+Per-`_replicator` db shares would be configurable in the `[replicator.shares]` section as:
+
+```
+[replicator.shares]
+$prefix/_replicator = $numshares
+```
+
+By default each db is assigned 100 shares. Then higher number of shares should
+then indicated a larger proportion of scheduler resources allocated to that db.
+A lower number would get proportionally less shares.
+
+For example:
+
+```
+[replicator.shares]
+
+; This is the default
+; _replicator = 100
+
+high/_replicator = 200
+low/_replicator = 50
+```
+
+# Advantages and Disadvantages
+
+Advantages:
+
+ * Allow a fair share of resources between multiple `_replicator` db instances
+
+ * Can boost or lower the priority of some replication jobs by adjusting the
+ shares assigned to that database instance.
+
+Disadvantages:
+
+ * Adds more complexity to the scheduler
+
+# Key Changes
+
+ * Modifies replication scheduler
+
+ each `_replicator` db in the system.
+
+ * A delay in `running` state as reflected in monitoring API responses
+
+ * `[replicator] update_docs = false` configuration option becomes hard-coded
+
+## Applications and Modules affected
+
+ * `couch_replicator` application
+
+## HTTP API additions
+
+N/A
Review comment:
Not a bad idea. There is a balance here with adding new HTTP API to 3.x, but I can see it being helpful since the algorithm here is dynamic and it may not be obvious what's happening. Am thinking maybe something like:
```json
"_scheduler/share_stats" : {
"_replicator": {
"shares": 100,
"utilization": 0.5,
"pending_jobs": 100,
"running_jobs": 3
},
"high/_replicator": {
"shares": 200,
"utilization": 0.8,
"pending_jobs": 48,
"running_jobs": 12
}
```
However a slight problem here that _scheduler/ API works at the cluster level but schedulers work independently on each node. We can aggregate stats which sum easily (for example, if we had `GET _scheduler` return a job total summary by state `{"running": 10, "pending": 90, ...}`) some of the share stats might not work well aggregated, say if they are normalized values like utilization. We could still sum them I suppose document the issue.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [couchdb-documentation] bessbd commented on a change in pull request #617: [rfc] Fair Share Replication Scheduler
Posted by GitBox <gi...@apache.org>.
bessbd commented on a change in pull request #617:
URL: https://github.com/apache/couchdb-documentation/pull/617#discussion_r565080926
##########
File path: rfcs/017-fair-share-scheduling.md
##########
@@ -0,0 +1,216 @@
+---
+name: Formal RFC
+about: Submit a formal Request For Comments for consideration by the team.
+title: 'Fair Share Job Scheduling for CouchDB 3.x Replicator'
+labels: rfc, discussion
+assignees: 'vatamane@apache.org'
+
+---
+
+# Introduction
+
+This document describes an improvement to the CouchDB 3.x replicator to
Review comment:
I think this PR should go to `3.x` and then the `3.x` reference should be omitted from the RFC.
##########
File path: rfcs/017-fair-share-scheduling.md
##########
@@ -0,0 +1,216 @@
+---
+name: Formal RFC
+about: Submit a formal Request For Comments for consideration by the team.
+title: 'Fair Share Job Scheduling for CouchDB 3.x Replicator'
+labels: rfc, discussion
+assignees: 'vatamane@apache.org'
+
+---
+
+# Introduction
+
+This document describes an improvement to the CouchDB 3.x replicator to
+introduce fair resource sharing between replication jobs in different
+_replicator databases.
+
+## Abstract
+
+Currently CouchDB replicator 3.x schedules jobs without any regard to what
+database they originated from. If there are multiple `_replicator` dbs then
+replication jobs from dbs with most jobs will consume most of the scheduler's
+resources. The proposal is to implement a fair sharing scheme as described in
+[A Fair Share Scheduler][2] paper by Judy Kay and Piers Lauder. It would allow
+sharing replication scheduler resources fairly amongst `_replicator` dbs.
+
+The idea was originally discussed on the [couchdb-dev][1] mailing list and the
+use of the Fair Share algorithm suggested by Joan Touzet.
+
+## Requirements Language
+
+The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD",
+"SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be
+interpreted as described in [RFC
+2119](https://www.rfc-editor.org/rfc/rfc2119.txt).
+
+## Terminology
+
+`_replicator` databases : A database that is either named `_replicator` or ends
+with the `/_replicator` suffix.
+
+`shares` : An abstract representation of entitlement to run on the replication
+scheduler.
+
+`usage` : A measure of resource usage by jobs from a particular `_replicator`
+db. For the scheduling replicator this will be the total time spent running.
+
+`continuous` replications : Replication jobs created with the `"continuous":
+true` parameter. These jobs will try to run continuously until the user removes
+them. They may be temporarily paused to allow other jobs to make progress.
+
+`one-shot` replications : Replication jobs which are not `continuous`. If the
+`"continuous":true` parameter is not specified, by default, replication jobs
+will be `one-shot`. These jobs will try to run until they reach the end of the
+changes feed, then stop.
+
+`job priority` : A job attribute which indicates the likelihood of the job
+being executed before other jobs. Following the convention in the "Fair Share"
+paper, jobs with a lower priority value are at the front of the pending queue,
+and get executed first.
+
+`max_jobs` : Configuration parameter which specifies up to how many replication
+jobs to run on each `replication` node.
+
+`max_churn` : Configuration parameter which specifies a limit of how many new
+jobs to spawn during each rescheduling interval.
+
+---
+
+# Detailed Description
+
+The general idea behind the algorithm is to continuously monitor
+per-`_replicator` jobs statistics and update each job's priorities in
+proportion to the usage from all the jobs in the same `_replicator` db. To make
+sure all jobs eventually get a chance to run and do not starve, all the
+priorities are continuously boosted, such that jobs which haven't run for a
+while, and maybe be starved, will eventually get a chance to run.
+
+The algorithm has 3 basic components that can run mostly independently from
+each other:
+
+1) Keep track of `usage` for each `_replicator` db . In the paper this part is
+called "user-level scheduling". As jobs run, they send reports to this
+component. Those reports are accumulated for one period, then rolled up when
+the period ends. There is also a decay coefficient applied to account for
+recent historical usage (this is called `K1` in the paper). This ensures in
+absence of jobs running from a particular `_replicator` db, the usage would
+drops to 0 and the whole entry is removed from the table table altogether.
+
+ Every `UsageUpdateInterval` seconds (called `t1` in the paper):
+ For each `Db`:
+ ```
+ DecayCoeff = get_usage_decay_coefficient(0.5)
+ AccumulatedUsage = get_accumulated_usage(Db),
+ update_usage(Db, usage(Db) * DecayCoeff + AccumulatedUsage)
+ reset_accumulated_usage(Db)
+ ```
+
+2) Uniformly decay all process priorities. Periodically lower the priority
+values, and thus boost the priority, of all the pending and running jobs in the
+system. The paper in this step applies a per-process "nice" value, which is
+skipped in the initial proposal. It could be added later if needed.
+
+ Every `UniformPriorityBoostInterval` seconds (called `t2` in the paper):
+ For each `Job`:
+ ```
+ DecayCoeff = get_uniform_decay_coefficient(0.75),
+ Job#job.priority = Job#job.priority * DecayCoeff
+ ```
+
+[note]: If jobs were scheduled to run at an absolute future time (a deadline) this step could be avoided. Then, the effect of all the jobs needing to periodically move to the front of the queue would be accomplished instead by the current time (i.e. `now()`) moving head along the time-line.
+
+3) Adjust running process priority in proportion to the shares used by all the
+jobs in the same db:
+
+ Every `RunningPriorityReduceInterval` seconds (called `t3` in the paper):
+ For each `Job`:
+ ```
+ Db = Job#job.db,
+ SharesSq = shares(Db) * shares(Db),
+ Job#job.priority = Job#job.priority + (usage(Db) * pending(Db)) / SharesSq
+ ```
+
+### How Jobs Start and Stop
+
+During each rescheduling cycle, `max_churn` running jobs from the back of the
+queue are stopped and `max_churn` jobs from the front of the pending queue are
+started. This part is not modified from the existing scheduling algorithm,
+except now, the jobs would be ordered by their `priority` value before being
+ordered by their last start time.
+
+In addition, `one-shot` replication jobs would still be skipped when stopping
+and we'd let them run in order to maintain traditional replication semantics
+just like before.
+
+When picking the jobs to run exclude jobs which have been exponentially backed
+off due to repeated errors. This part is unmodified and from the original
+scheduler.
+
+### Configuration
+
+The decay coefficients and interval times for each of the 3 parts of the algorithm would be configurable in the `[replicator]` config section.
+
+Per-`_replicator` db shares would be configurable in the `[replicator.shares]` section as:
+
+```
+[replicator.shares]
+$prefix/_replicator = $numshares
+```
+
+By default each db is assigned 100 shares. Then higher number of shares should
+then indicated a larger proportion of scheduler resources allocated to that db.
+A lower number would get proportionally less shares.
+
+For example:
+
+```
+[replicator.shares]
+
+; This is the default
+; _replicator = 100
+
+high/_replicator = 200
+low/_replicator = 50
+```
+
+# Advantages and Disadvantages
+
+Advantages:
+
+ * Allow a fair share of resources between multiple `_replicator` db instances
+
+ * Can boost or lower the priority of some replication jobs by adjusting the
+ shares assigned to that database instance.
+
+Disadvantages:
+
+ * Adds more complexity to the scheduler
+
+# Key Changes
+
+ * Modifies replication scheduler
+
+ each `_replicator` db in the system.
+
+ * A delay in `running` state as reflected in monitoring API responses
+
+ * `[replicator] update_docs = false` configuration option becomes hard-coded
+
+## Applications and Modules affected
+
+ * `couch_replicator` application
+
+## HTTP API additions
+
+N/A
Review comment:
Do you think some API changes would be useful so that people could get info about and monitor replications and compare that with the configuration? Such as: this is the target share distribution; this is how much of that is "utilized".
I'm thinking of basically any ops-aid.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [couchdb-documentation] nickva commented on pull request #617: [rfc] Fair Share Replication Scheduler
Posted by GitBox <gi...@apache.org>.
nickva commented on pull request #617:
URL: https://github.com/apache/couchdb-documentation/pull/617#issuecomment-768383001
> In that case I'm suggesting to just omit the `3.x` references from this RFC as `main` here is for `couchdb`'s `3.x`. (Can you please confirm the last part, @wohali ?)
This RFC specifically targets the 3.x version of the replicator removing it would just lead to confusion since we don't have the two separate docs branches. I expect we'd have another RFC for main and that would be explicitly labeled for as `fdb` like other RFCs or `4.x` depending when it gets created.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [couchdb-documentation] nickva commented on pull request #617: [rfc] Fair Share Replication Scheduler
Posted by GitBox <gi...@apache.org>.
nickva commented on pull request #617:
URL: https://github.com/apache/couchdb-documentation/pull/617#issuecomment-779482126
The PR for this feature is ready: https://github.com/apache/couchdb/pull/3364
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [couchdb-documentation] bessbd commented on pull request #617: [rfc] Fair Share Replication Scheduler
Posted by GitBox <gi...@apache.org>.
bessbd commented on pull request #617:
URL: https://github.com/apache/couchdb-documentation/pull/617#issuecomment-768902077
> Interesting idea. Would it be, say, any design document which has a "replicator_config" field in it and we'd merge those, or have a single (special) doc id like "_design/replicator_config"? That might work, but I am also thinking this is for a 3.x branch and I would be hesitant to add a whole new configuration mechanism.
I'm not sure yet how it would look like / work in `main`, but I thought some configuration is necessary / useful there as well.
> We do have precedent of configuring per-db settings in other application such as in [ken](https://github.com/apache/couchdb/blob/3.x/src/ken/src/ken_server.erl#L264) and [smoosh](https://github.com/apache/couchdb/blob/3.x/src/smoosh/src/smoosh_utils.erl#L54). Settings applied via HTTP should not get lost, if they do it's a bug. They get written to the config files on disk. Where you thinking about needing to set it on every node perhaps? Yeah we'd have call config on very node if the setting is set via HTTP, and that's not ideal but probably too late to change in 3.x at this point.
I did not know that any online configuration changes get persisted to disk. Looking at https://docs.couchdb.org/en/latest/api/server/configuration.html#put--_node-node-name-_config-section-key this isn't trivial to me. Do you mean [this](https://github.com/apache/couchdb/blob/fa0aff9332c7260a4d5e50b354386f39308cbf17/src/chttpd/src/chttpd_node.erl#L72)? Perhaps we should document that.
Considering that this feature requires server admin rights, it is actually some `_config` that should probably handle this (as opposed to some design document-like thing).
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [couchdb-documentation] nickva commented on a change in pull request #617: [rfc] Fair Share Replication Scheduler
Posted by GitBox <gi...@apache.org>.
nickva commented on a change in pull request #617:
URL: https://github.com/apache/couchdb-documentation/pull/617#discussion_r565416777
##########
File path: rfcs/017-fair-share-scheduling.md
##########
@@ -0,0 +1,216 @@
+---
+name: Formal RFC
+about: Submit a formal Request For Comments for consideration by the team.
+title: 'Fair Share Job Scheduling for CouchDB 3.x Replicator'
+labels: rfc, discussion
+assignees: 'vatamane@apache.org'
+
+---
+
+# Introduction
+
+This document describes an improvement to the CouchDB 3.x replicator to
Review comment:
It's specifically targeted towards the 3.x scheduler which is architecturally different from the `main` one. The 3.x branch is actually easier to apply these changes to so it seemed like a good place to start. For the main replicator we might have a separate RFC or just update this one with a PR.
As discussed below we don't have a 3.x branch yet, if and when we do, we could move it there.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [couchdb-documentation] nickva merged pull request #617: [rfc] Fair Share Replication Scheduler
Posted by GitBox <gi...@apache.org>.
nickva merged pull request #617:
URL: https://github.com/apache/couchdb-documentation/pull/617
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [couchdb-documentation] bessbd edited a comment on pull request #617: [rfc] Fair Share Replication Scheduler
Posted by GitBox <gi...@apache.org>.
bessbd edited a comment on pull request #617:
URL: https://github.com/apache/couchdb-documentation/pull/617#issuecomment-768159926
> @bessbd I'd prefer not going to fork this until we're ready to do a 4.0 release, since we are still regularly getting typos and documentation corrections for 3.x and maintaining 2 branches even in just the main CouchDB repo is a pain.
>
> Until we're ready to actually commit the 4.x doc changes that is - at which point we'll fork.
>
> Sound good to you? If you want to start an ML thread, go ahead...
Sounds good to me, thank you @wohali ! In that case I'm suggesting to just omit the `3.x` references from this RFC as `main` here is for `couchdb`'s `3.x`. (Can you please confirm the last part, @wohali ?)
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [couchdb-documentation] bessbd commented on a change in pull request #617: [rfc] Fair Share Replication Scheduler
Posted by GitBox <gi...@apache.org>.
bessbd commented on a change in pull request #617:
URL: https://github.com/apache/couchdb-documentation/pull/617#discussion_r565912647
##########
File path: rfcs/017-fair-share-scheduling.md
##########
@@ -0,0 +1,216 @@
+---
+name: Formal RFC
+about: Submit a formal Request For Comments for consideration by the team.
+title: 'Fair Share Job Scheduling for CouchDB 3.x Replicator'
+labels: rfc, discussion
+assignees: 'vatamane@apache.org'
+
+---
+
+# Introduction
+
+This document describes an improvement to the CouchDB 3.x replicator to
Review comment:
> It's specifically targeted towards the 3.x scheduler which is architecturally different from the main one.
Yeah, I got that part. I just thought as `HEAD` here refers to `3.x`-related content, `3.x` in the change would just be redundant / confusing. Do you expect this RFC to be included in the `main` branch as well? (A yes and a no answer would both be reasonable to me.)
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [couchdb-documentation] bessbd commented on a change in pull request #617: [rfc] Fair Share Replication Scheduler
Posted by GitBox <gi...@apache.org>.
bessbd commented on a change in pull request #617:
URL: https://github.com/apache/couchdb-documentation/pull/617#discussion_r568882084
##########
File path: rfcs/017-fair-share-scheduling.md
##########
@@ -0,0 +1,216 @@
+---
+name: Formal RFC
+about: Submit a formal Request For Comments for consideration by the team.
+title: 'Fair Share Job Scheduling for CouchDB 3.x Replicator'
+labels: rfc, discussion
+assignees: 'vatamane@apache.org'
+
+---
+
+# Introduction
+
+This document describes an improvement to the CouchDB 3.x replicator to
Review comment:
Yeah, I was hoping for the "we just update this one and highlight differences".
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [couchdb-documentation] bessbd commented on pull request #617: [rfc] Fair Share Replication Scheduler
Posted by GitBox <gi...@apache.org>.
bessbd commented on pull request #617:
URL: https://github.com/apache/couchdb-documentation/pull/617#issuecomment-768135102
Please semi-ignore my `3.x` comment. I've just noticed this is not the `couchdb` repo. On a different topic: we should probably have a `3.x` branch in here. I'll ask on the CouchDB Slack, then probably open a ML thread.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [couchdb-documentation] nickva commented on pull request #617: [rfc] Fair Share Replication Scheduler
Posted by GitBox <gi...@apache.org>.
nickva commented on pull request #617:
URL: https://github.com/apache/couchdb-documentation/pull/617#issuecomment-788391210
The submitted PR was reviewed https://github.com/apache/couchdb/pull/3364
There is a script referenced in the PR comments to help test and play with the new feature
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [couchdb-documentation] nickva commented on a change in pull request #617: [rfc] Fair Share Replication Scheduler
Posted by GitBox <gi...@apache.org>.
nickva commented on a change in pull request #617:
URL: https://github.com/apache/couchdb-documentation/pull/617#discussion_r565416777
##########
File path: rfcs/017-fair-share-scheduling.md
##########
@@ -0,0 +1,216 @@
+---
+name: Formal RFC
+about: Submit a formal Request For Comments for consideration by the team.
+title: 'Fair Share Job Scheduling for CouchDB 3.x Replicator'
+labels: rfc, discussion
+assignees: 'vatamane@apache.org'
+
+---
+
+# Introduction
+
+This document describes an improvement to the CouchDB 3.x replicator to
Review comment:
It's specifically targeted to towards the 3.x scheduler which is architecturally different from the `main` one. The 3.x branch is actually easier to apply these changes to so it seemed like a good place to start. For the main replicator we might have a separate RFC or just update this one with a PR.
As discussed below we don't have a 3.x branch yet, if and when do we could move it there.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [couchdb-documentation] nickva commented on pull request #617: [rfc] Fair Share Replication Scheduler
Posted by GitBox <gi...@apache.org>.
nickva commented on pull request #617:
URL: https://github.com/apache/couchdb-documentation/pull/617#issuecomment-768421797
> For the configuration: have you considered doing this perhaps via design docs (or something like that)? I think that would be closer in "online-ness" to the databases.
Interesting idea. Would it be say any design document which has a "replicator_config" field in it and we'd merge those, or have a single (special) doc id like "_design/replicator_config"? That might work, but I am also thinking this is for a 3.x branch and I would be hesitant to add a whole new configuration mechanism.
> Ie. I can create-update-delete replicator databases, but to configure shares for them, I'd have to edit config (files and/or via the HTTP API - which is then either lost or gets splatted on restart unless I do some double booking).
We do have precedent of configuring per-db settings in other application such as in [ken](https://github.com/apache/couchdb/blob/3.x/src/ken/src/ken_server.erl#L264) and [smoosh](https://github.com/apache/couchdb/blob/3.x/src/smoosh/src/smoosh_utils.erl#L54). Settings applied via HTTP should not get lost, if they do it's a bug. They get written to the config files on disk. Where you thinking about needing to set it on every node perhaps? Yeah we'd have call config on very node if the setting is set via HTTP, and that's not ideal but probably too late to change in 3.x at this point.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [couchdb-documentation] nickva commented on a change in pull request #617: [rfc] Fair Share Replication Scheduler
Posted by GitBox <gi...@apache.org>.
nickva commented on a change in pull request #617:
URL: https://github.com/apache/couchdb-documentation/pull/617#discussion_r566253842
##########
File path: rfcs/017-fair-share-scheduling.md
##########
@@ -0,0 +1,216 @@
+---
+name: Formal RFC
+about: Submit a formal Request For Comments for consideration by the team.
+title: 'Fair Share Job Scheduling for CouchDB 3.x Replicator'
+labels: rfc, discussion
+assignees: 'vatamane@apache.org'
+
+---
+
+# Introduction
+
+This document describes an improvement to the CouchDB 3.x replicator to
Review comment:
However most of the RFCs we have are actually for 4.x, so it's better to be explicit probably. Especially if for this case there will be another RFC targeting 4.x (unless we just update this one and highlight differences).
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [couchdb-documentation] nickva commented on a change in pull request #617: [rfc] Fair Share Replication Scheduler
Posted by GitBox <gi...@apache.org>.
nickva commented on a change in pull request #617:
URL: https://github.com/apache/couchdb-documentation/pull/617#discussion_r566253842
##########
File path: rfcs/017-fair-share-scheduling.md
##########
@@ -0,0 +1,216 @@
+---
+name: Formal RFC
+about: Submit a formal Request For Comments for consideration by the team.
+title: 'Fair Share Job Scheduling for CouchDB 3.x Replicator'
+labels: rfc, discussion
+assignees: 'vatamane@apache.org'
+
+---
+
+# Introduction
+
+This document describes an improvement to the CouchDB 3.x replicator to
Review comment:
However most of the RFCs we have are actually for 4.x, so it's better to be explicit. Especially if for this case there will be another RFC targeting 4.x (unless we just update this one and highlight differences).
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [couchdb-documentation] bessbd commented on a change in pull request #617: [rfc] Fair Share Replication Scheduler
Posted by GitBox <gi...@apache.org>.
bessbd commented on a change in pull request #617:
URL: https://github.com/apache/couchdb-documentation/pull/617#discussion_r568882084
##########
File path: rfcs/017-fair-share-scheduling.md
##########
@@ -0,0 +1,216 @@
+---
+name: Formal RFC
+about: Submit a formal Request For Comments for consideration by the team.
+title: 'Fair Share Job Scheduling for CouchDB 3.x Replicator'
+labels: rfc, discussion
+assignees: 'vatamane@apache.org'
+
+---
+
+# Introduction
+
+This document describes an improvement to the CouchDB 3.x replicator to
Review comment:
Yeah, I was hoping for the "we just update this one and highlight differences".
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [couchdb-documentation] wohali commented on pull request #617: [rfc] Fair Share Replication Scheduler
Posted by GitBox <gi...@apache.org>.
wohali commented on pull request #617:
URL: https://github.com/apache/couchdb-documentation/pull/617#issuecomment-768147274
@bessbd I'd prefer not going to fork this until we're ready to do a 4.0 release, since we are still regularly getting typos and documentation corrections for 3.x and maintaining 2 branches even in just the main CouchDB repo is a pain.
Until we're ready to actually commit the 4.x doc changes that is - at which point we'll fork.
Sound good to you? If you want to start an ML thread, go ahead...
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [couchdb-documentation] nickva commented on a change in pull request #617: [rfc] Fair Share Replication Scheduler
Posted by GitBox <gi...@apache.org>.
nickva commented on a change in pull request #617:
URL: https://github.com/apache/couchdb-documentation/pull/617#discussion_r565519411
##########
File path: rfcs/017-fair-share-scheduling.md
##########
@@ -0,0 +1,216 @@
+---
+name: Formal RFC
+about: Submit a formal Request For Comments for consideration by the team.
+title: 'Fair Share Job Scheduling for CouchDB 3.x Replicator'
+labels: rfc, discussion
+assignees: 'vatamane@apache.org'
+
+---
+
+# Introduction
+
+This document describes an improvement to the CouchDB 3.x replicator to
+introduce fair resource sharing between replication jobs in different
+_replicator databases.
+
+## Abstract
+
+Currently CouchDB replicator 3.x schedules jobs without any regard to what
+database they originated from. If there are multiple `_replicator` dbs then
+replication jobs from dbs with most jobs will consume most of the scheduler's
+resources. The proposal is to implement a fair sharing scheme as described in
+[A Fair Share Scheduler][2] paper by Judy Kay and Piers Lauder. It would allow
+sharing replication scheduler resources fairly amongst `_replicator` dbs.
+
+The idea was originally discussed on the [couchdb-dev][1] mailing list and the
+use of the Fair Share algorithm suggested by Joan Touzet.
+
+## Requirements Language
+
+The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD",
+"SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be
+interpreted as described in [RFC
+2119](https://www.rfc-editor.org/rfc/rfc2119.txt).
+
+## Terminology
+
+`_replicator` databases : A database that is either named `_replicator` or ends
+with the `/_replicator` suffix.
+
+`shares` : An abstract representation of entitlement to run on the replication
+scheduler.
+
+`usage` : A measure of resource usage by jobs from a particular `_replicator`
+db. For the scheduling replicator this will be the total time spent running.
+
+`continuous` replications : Replication jobs created with the `"continuous":
+true` parameter. These jobs will try to run continuously until the user removes
+them. They may be temporarily paused to allow other jobs to make progress.
+
+`one-shot` replications : Replication jobs which are not `continuous`. If the
+`"continuous":true` parameter is not specified, by default, replication jobs
+will be `one-shot`. These jobs will try to run until they reach the end of the
+changes feed, then stop.
+
+`job priority` : A job attribute which indicates the likelihood of the job
+being executed before other jobs. Following the convention in the "Fair Share"
+paper, jobs with a lower priority value are at the front of the pending queue,
+and get executed first.
+
+`max_jobs` : Configuration parameter which specifies up to how many replication
+jobs to run on each `replication` node.
+
+`max_churn` : Configuration parameter which specifies a limit of how many new
+jobs to spawn during each rescheduling interval.
+
+---
+
+# Detailed Description
+
+The general idea behind the algorithm is to continuously monitor
+per-`_replicator` jobs statistics and update each job's priorities in
+proportion to the usage from all the jobs in the same `_replicator` db. To make
+sure all jobs eventually get a chance to run and do not starve, all the
+priorities are continuously boosted, such that jobs which haven't run for a
+while, and maybe be starved, will eventually get a chance to run.
+
+The algorithm has 3 basic components that can run mostly independently from
+each other:
+
+1) Keep track of `usage` for each `_replicator` db . In the paper this part is
+called "user-level scheduling". As jobs run, they send reports to this
+component. Those reports are accumulated for one period, then rolled up when
+the period ends. There is also a decay coefficient applied to account for
+recent historical usage (this is called `K1` in the paper). This ensures in
+absence of jobs running from a particular `_replicator` db, the usage would
+drops to 0 and the whole entry is removed from the table table altogether.
+
+ Every `UsageUpdateInterval` seconds (called `t1` in the paper):
+ For each `Db`:
+ ```
+ DecayCoeff = get_usage_decay_coefficient(0.5)
+ AccumulatedUsage = get_accumulated_usage(Db),
+ update_usage(Db, usage(Db) * DecayCoeff + AccumulatedUsage)
+ reset_accumulated_usage(Db)
+ ```
+
+2) Uniformly decay all process priorities. Periodically lower the priority
+values, and thus boost the priority, of all the pending and running jobs in the
+system. The paper in this step applies a per-process "nice" value, which is
+skipped in the initial proposal. It could be added later if needed.
+
+ Every `UniformPriorityBoostInterval` seconds (called `t2` in the paper):
+ For each `Job`:
+ ```
+ DecayCoeff = get_uniform_decay_coefficient(0.75),
+ Job#job.priority = Job#job.priority * DecayCoeff
+ ```
+
+[note]: If jobs were scheduled to run at an absolute future time (a deadline) this step could be avoided. Then, the effect of all the jobs needing to periodically move to the front of the queue would be accomplished instead by the current time (i.e. `now()`) moving head along the time-line.
+
+3) Adjust running process priority in proportion to the shares used by all the
+jobs in the same db:
+
+ Every `RunningPriorityReduceInterval` seconds (called `t3` in the paper):
+ For each `Job`:
+ ```
+ Db = Job#job.db,
+ SharesSq = shares(Db) * shares(Db),
+ Job#job.priority = Job#job.priority + (usage(Db) * pending(Db)) / SharesSq
+ ```
+
+### How Jobs Start and Stop
+
+During each rescheduling cycle, `max_churn` running jobs from the back of the
+queue are stopped and `max_churn` jobs from the front of the pending queue are
+started. This part is not modified from the existing scheduling algorithm,
+except now, the jobs would be ordered by their `priority` value before being
+ordered by their last start time.
+
+In addition, `one-shot` replication jobs would still be skipped when stopping
+and we'd let them run in order to maintain traditional replication semantics
+just like before.
+
+When picking the jobs to run exclude jobs which have been exponentially backed
+off due to repeated errors. This part is unmodified and from the original
+scheduler.
+
+### Configuration
+
+The decay coefficients and interval times for each of the 3 parts of the algorithm would be configurable in the `[replicator]` config section.
+
+Per-`_replicator` db shares would be configurable in the `[replicator.shares]` section as:
+
+```
+[replicator.shares]
+$prefix/_replicator = $numshares
+```
+
+By default each db is assigned 100 shares. Then higher number of shares should
+then indicated a larger proportion of scheduler resources allocated to that db.
+A lower number would get proportionally less shares.
+
+For example:
+
+```
+[replicator.shares]
+
+; This is the default
+; _replicator = 100
+
+high/_replicator = 200
+low/_replicator = 50
+```
+
+# Advantages and Disadvantages
+
+Advantages:
+
+ * Allow a fair share of resources between multiple `_replicator` db instances
+
+ * Can boost or lower the priority of some replication jobs by adjusting the
+ shares assigned to that database instance.
+
+Disadvantages:
+
+ * Adds more complexity to the scheduler
+
+# Key Changes
+
+ * Modifies replication scheduler
+
+ each `_replicator` db in the system.
+
+ * A delay in `running` state as reflected in monitoring API responses
+
+ * `[replicator] update_docs = false` configuration option becomes hard-coded
+
+## Applications and Modules affected
+
+ * `couch_replicator` application
+
+## HTTP API additions
+
+N/A
Review comment:
Not a bad idea. There is a balance here with adding new HTTP API to 3.x, but I can see it being helpful since the algorithm here is dynamic and it may not be obvious what's happening. Am thinking maybe something like:
```json
"_scheduler/share_stats" : {
"_replicator": {
"shares": 100,
"utilization": 0.5,
"pending_jobs": 100,
"running_jobs": 3
},
"high/_replicator": {
"shares": 200,
"utilization": 0.8,
"pending_jobs": 48,
"running_jobs": 12
}
```
However a slight problem here that _scheduler/ API works at the cluster level but schedulers work independently on each node. We can aggregate stats which sum easily (for example, if we had `GET _scheduler` return a job total summary by state `{"running": 10, "pending": 90, ...}`) some of the share stats might not work well aggregated, say if they are normalized values like utilization. We could still sum them I suppose document the fact that they represent a sum. Another option is to return per-node stats here.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [couchdb-documentation] nickva commented on pull request #617: [rfc] Fair Share Replication Scheduler
Posted by GitBox <gi...@apache.org>.
nickva commented on pull request #617:
URL: https://github.com/apache/couchdb-documentation/pull/617#issuecomment-769219780
> I did not know that any online configuration changes get persisted to disk. Looking at https://docs.couchdb.org/en/latest/api/server/configuration.html#put--_node-node-name-_config-section-key this isn't trivial to me. Do you mean this? Perhaps we should document that.
Yeah, they should be written to .ini files and persisted. Good idea to explicitly mention that in the docs. `X-Couch-Persist: false` can probably be documented as well. It's used in tests mostly, as far as I've seen.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org