From 9e2ab226b1bc8d1c234f73ac9300132b8f05b335 Mon Sep 17 00:00:00 2001 From: =?utf8?q?J=C3=A9r=C3=B4me=20Benoit?= Date: Sat, 10 Jun 2023 13:04:15 +0200 Subject: [PATCH] docs: initial worker choice strategies documentation MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Reference: #772 Signed-off-by: Jérôme Benoit --- README.md | 12 ++++++------ src/pools/selection-strategies/README.md | 18 ++++++++++++++++++ 2 files changed, 24 insertions(+), 6 deletions(-) create mode 100644 src/pools/selection-strategies/README.md diff --git a/README.md b/README.md index 6fdac382..cb45449c 100644 --- a/README.md +++ b/README.md @@ -164,9 +164,9 @@ An object with these properties: - `WorkerChoiceStrategies.LEAST_USED`: Submit tasks to the worker with the minimum number of executed, executing and queued tasks - `WorkerChoiceStrategies.LEAST_BUSY`: Submit tasks to the worker with the minimum tasks total execution and wait time - `WorkerChoiceStrategies.LEAST_ELU`: Submit tasks to the worker with the minimum event loop utilization (ELU) (experimental) - - `WorkerChoiceStrategies.WEIGHTED_ROUND_ROBIN`: Submit tasks to worker by using a weighted round robin scheduling algorithm based on tasks execution time - - `WorkerChoiceStrategies.INTERLEAVED_WEIGHTED_ROUND_ROBIN`: Submit tasks to worker by using an interleaved weighted round robin scheduling algorithm based on tasks execution time (experimental) - - `WorkerChoiceStrategies.FAIR_SHARE`: Submit tasks to worker by using a fair share tasks scheduling algorithm based on tasks execution time or ELU + - `WorkerChoiceStrategies.WEIGHTED_ROUND_ROBIN`: Submit tasks to worker by using a [weighted round robin scheduling algorithm](./src/pools/selection-strategies/README.md#weighted-round-robin) based on tasks execution time + - `WorkerChoiceStrategies.INTERLEAVED_WEIGHTED_ROUND_ROBIN`: Submit tasks to worker by using an [interleaved weighted round robin scheduling algorithm](./src/pools/selection-strategies/README.md#interleaved-weighted-round-robin) based on tasks execution time (experimental) + - `WorkerChoiceStrategies.FAIR_SHARE`: Submit tasks to worker by using a [fair share scheduling algorithm](./src/pools/selection-strategies/README.md#fair-share) based on tasks execution time or ELU active time `WorkerChoiceStrategies.WEIGHTED_ROUND_ROBIN`, `WorkerChoiceStrategies.INTERLEAVED_WEIGHTED_ROUND_ROBIN` and `WorkerChoiceStrategies.FAIR_SHARE` strategies are targeted to heavy and long tasks. Default: `WorkerChoiceStrategies.ROUND_ROBIN` @@ -175,9 +175,9 @@ An object with these properties: Properties: - `measurement` (optional) - The measurement to use in worker choice strategies: `runTime`, `waitTime` or `elu`. - - `runTime` (optional) - Use the tasks median runtime instead of the tasks average runtime in worker choice strategies. - - `waitTime` (optional) - Use the tasks median wait time instead of the tasks average wait time in worker choice strategies. - - `elu` (optional) - Use the tasks median ELU instead of the tasks average ELU in worker choice strategies. + - `runTime` (optional) - Use the tasks [median](./src/pools/selection-strategies/README.md#median) runtime instead of the tasks average runtime in worker choice strategies. + - `waitTime` (optional) - Use the tasks [median](./src/pools/selection-strategies/README.md#median) wait time instead of the tasks average wait time in worker choice strategies. + - `elu` (optional) - Use the tasks [median](./src/pools/selection-strategies/README.md#median) ELU instead of the tasks average ELU in worker choice strategies. - `weights` (optional) - The worker weights to use in the weighted round robin worker choice strategy: `{ 0: 200, 1: 300, ..., n: 100 }`. Default: `{ runTime: { median: false }, waitTime: { median: false }, elu: { median: false } }` diff --git a/src/pools/selection-strategies/README.md b/src/pools/selection-strategies/README.md new file mode 100644 index 00000000..9e409cdf --- /dev/null +++ b/src/pools/selection-strategies/README.md @@ -0,0 +1,18 @@ +# Worker choice strategies + +## Strategies + +### Fair share + +Its goal is to distribute the load evenly across all workers. To achieve this, the strategy keeps track of the average task execution time for each worker and assigns the next task to the worker with the lowest task end prediction time: `task_end_prediction = max(current_time, task_end_prediction) + average_task_execution_time`. +By default, the strategy uses the average task execution time for each worker but it can be configured to use the event loop utilization (ELU) active time instead. + +### Weighted round robin + +### Interleaved weighted round robin + +## Statistics + +### Median + +Strategies using the average task execution time for each worker can use the median instead. Median is more robust to outliers and can be used to avoid assigning tasks to workers that are currently overloaded. Median usage introduces a small overhead: measurement history must be kept for each worker and the median must be recomputed each time a new task has finished. -- 2.34.1