From 9adcefabee69d0c8a8f580c2512e35d2c54c8219 Mon Sep 17 00:00:00 2001 From: =?utf8?q?J=C3=A9r=C3=B4me=20Benoit?= Date: Fri, 9 Jun 2023 20:53:16 +0200 Subject: [PATCH] feat: add support for tasks ELU in fair share strategy MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Signed-off-by: Jérôme Benoit --- CHANGELOG.md | 1 + README.md | 8 +++-- src/index.ts | 9 ++++- src/pools/abstract-pool.ts | 6 ++-- .../abstract-worker-choice-strategy.ts | 4 +-- .../fair-share-worker-choice-strategy.ts | 21 +++++++----- .../selection-strategies-types.ts | 22 ++++++++++-- tests/pools/abstract/abstract-pool.test.js | 34 ++++++++++++------- .../selection-strategies.test.js | 32 ++++++++++------- 9 files changed, 91 insertions(+), 46 deletions(-) diff --git a/CHANGELOG.md b/CHANGELOG.md index e2bb9a87..56bb1c83 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -10,6 +10,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 ### Added - Add `LEAST_ELU` worker choice strategy (experimental). +- Add tasks ELU instead of runtime support to `FAIR_SHARE` worker choice strategy. ### Changed diff --git a/README.md b/README.md index e0f665fe..d3a4534f 100644 --- a/README.md +++ b/README.md @@ -166,7 +166,7 @@ An object with these properties: - `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 + - `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`, `WorkerChoiceStrategies.INTERLEAVED_WEIGHTED_ROUND_ROBIN` and `WorkerChoiceStrategies.FAIR_SHARE` strategies are targeted to heavy and long tasks. Default: `WorkerChoiceStrategies.ROUND_ROBIN` @@ -174,11 +174,13 @@ An object with these properties: - `workerChoiceStrategyOptions` (optional) - The worker choice strategy options object to use in this pool. 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. - - `weights` (optional) - The worker weights to use in the weighted round robin worker choice strategy: `{ 0: 200, 1: 300, ..., n: 100 }` + - `elu` (optional) - Use the tasks 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 } }` + Default: `{ runTime: { median: false }, waitTime: { median: false }, elu: { median: false } }` - `restartWorkerOnError` (optional) - Restart worker on uncaught error in this pool. Default: `true` diff --git a/src/index.ts b/src/index.ts index 55355d2e..8b827876 100644 --- a/src/index.ts +++ b/src/index.ts @@ -17,6 +17,7 @@ export type { } from './pools/pool' export type { ErrorHandler, + EventLoopUtilizationMeasurementStatistics, ExitHandler, IWorker, MeasurementStatistics, @@ -27,9 +28,15 @@ export type { WorkerNode, WorkerUsage } from './pools/worker' -export { WorkerChoiceStrategies } from './pools/selection-strategies/selection-strategies-types' +export { + Measurements, + WorkerChoiceStrategies +} from './pools/selection-strategies/selection-strategies-types' export type { IWorkerChoiceStrategy, + Measurement, + MeasurementOptions, + MeasurementStatisticsRequirements, TaskStatisticsRequirements, WorkerChoiceStrategy, WorkerChoiceStrategyOptions diff --git a/src/pools/abstract-pool.ts b/src/pools/abstract-pool.ts index f082b8d1..427678c4 100644 --- a/src/pools/abstract-pool.ts +++ b/src/pools/abstract-pool.ts @@ -563,10 +563,8 @@ export abstract class AbstractPool< .aggregate ) { if (workerUsage.elu != null && message.taskPerformance?.elu != null) { - workerUsage.elu.idle.aggregate = - workerUsage.elu.idle.aggregate + message.taskPerformance.elu.idle - workerUsage.elu.active.aggregate = - workerUsage.elu.active.aggregate + message.taskPerformance.elu.active + workerUsage.elu.idle.aggregate += message.taskPerformance.elu.idle + workerUsage.elu.active.aggregate += message.taskPerformance.elu.active workerUsage.elu.utilization = (workerUsage.elu.utilization + message.taskPerformance.elu.utilization) / diff --git a/src/pools/selection-strategies/abstract-worker-choice-strategy.ts b/src/pools/selection-strategies/abstract-worker-choice-strategy.ts index 8f71b502..d9a57341 100644 --- a/src/pools/selection-strategies/abstract-worker-choice-strategy.ts +++ b/src/pools/selection-strategies/abstract-worker-choice-strategy.ts @@ -170,8 +170,8 @@ export abstract class AbstractWorkerChoiceStrategy< /** * Gets the worker task ELU. - * If the task statistics require the ELU, the average ELU is returned. - * If the task statistics require the ELU, the median ELU is returned. + * If the task statistics require the average ELU, the average ELU is returned. + * If the task statistics require the median ELU, the median ELU is returned. * * @param workerNodeKey - The worker node key. * @returns The worker task ELU. diff --git a/src/pools/selection-strategies/fair-share-worker-choice-strategy.ts b/src/pools/selection-strategies/fair-share-worker-choice-strategy.ts index 52b25fb9..ff9eaf36 100644 --- a/src/pools/selection-strategies/fair-share-worker-choice-strategy.ts +++ b/src/pools/selection-strategies/fair-share-worker-choice-strategy.ts @@ -2,10 +2,11 @@ import { DEFAULT_WORKER_CHOICE_STRATEGY_OPTIONS } from '../../utils' import type { IPool } from '../pool' import type { IWorker } from '../worker' import { AbstractWorkerChoiceStrategy } from './abstract-worker-choice-strategy' -import type { - IWorkerChoiceStrategy, - TaskStatisticsRequirements, - WorkerChoiceStrategyOptions +import { + type IWorkerChoiceStrategy, + Measurements, + type TaskStatisticsRequirements, + type WorkerChoiceStrategyOptions } from './selection-strategies-types' /** @@ -36,8 +37,8 @@ export class FairShareWorkerChoiceStrategy< median: false }, elu: { - aggregate: false, - average: false, + aggregate: true, + average: true, median: false } } @@ -109,9 +110,11 @@ export class FairShareWorkerChoiceStrategy< workerNodeKey: number, workerVirtualTaskStartTimestamp: number ): number { - return ( - workerVirtualTaskStartTimestamp + this.getWorkerTaskRunTime(workerNodeKey) - ) + const workerTaskRunTime = + this.opts.measurement === Measurements.elu + ? this.getWorkerTaskElu(workerNodeKey) + : this.getWorkerTaskRunTime(workerNodeKey) + return workerVirtualTaskStartTimestamp + workerTaskRunTime } private getWorkerVirtualTaskStartTimestamp (workerNodeKey: number): number { diff --git a/src/pools/selection-strategies/selection-strategies-types.ts b/src/pools/selection-strategies/selection-strategies-types.ts index c578ddc3..b0b036ee 100644 --- a/src/pools/selection-strategies/selection-strategies-types.ts +++ b/src/pools/selection-strategies/selection-strategies-types.ts @@ -41,10 +41,24 @@ export const WorkerChoiceStrategies = Object.freeze({ */ export type WorkerChoiceStrategy = keyof typeof WorkerChoiceStrategies +/** + * Enumeration of measurements. + */ +export const Measurements = Object.freeze({ + runTime: 'runTime', + waitTime: 'waitTime', + elu: 'elu' +} as const) + +/** + * Measurement. + */ +export type Measurement = keyof typeof Measurements + /** * Measurement options. */ -interface MeasurementOptions { +export interface MeasurementOptions { /** * Set measurement median. */ @@ -55,6 +69,10 @@ interface MeasurementOptions { * Worker choice strategy options. */ export interface WorkerChoiceStrategyOptions { + /** + * Measurement to use for worker choice strategy. + */ + measurement?: Measurement /** * Runtime options. * @@ -87,7 +105,7 @@ export interface WorkerChoiceStrategyOptions { * * @internal */ -interface MeasurementStatisticsRequirements { +export interface MeasurementStatisticsRequirements { /** * Require measurement aggregate. */ diff --git a/tests/pools/abstract/abstract-pool.test.js b/tests/pools/abstract/abstract-pool.test.js index 25566a6a..4b6f46a6 100644 --- a/tests/pools/abstract/abstract-pool.test.js +++ b/tests/pools/abstract/abstract-pool.test.js @@ -210,19 +210,24 @@ describe('Abstract pool test suite', () => { median: false }, elu: { - aggregate: false, - average: false, + aggregate: true, + average: true, median: false } }) - pool.setWorkerChoiceStrategyOptions({ runTime: { median: true } }) + pool.setWorkerChoiceStrategyOptions({ + runTime: { median: true }, + elu: { median: true } + }) expect(pool.opts.workerChoiceStrategyOptions).toStrictEqual({ - runTime: { median: true } + runTime: { median: true }, + elu: { median: true } }) for (const [, workerChoiceStrategy] of pool.workerChoiceStrategyContext .workerChoiceStrategies) { expect(workerChoiceStrategy.opts).toStrictEqual({ - runTime: { median: true } + runTime: { median: true }, + elu: { median: true } }) } expect( @@ -239,19 +244,24 @@ describe('Abstract pool test suite', () => { median: false }, elu: { - aggregate: false, + aggregate: true, average: false, - median: false + median: true } }) - pool.setWorkerChoiceStrategyOptions({ runTime: { median: false } }) + pool.setWorkerChoiceStrategyOptions({ + runTime: { median: false }, + elu: { median: false } + }) expect(pool.opts.workerChoiceStrategyOptions).toStrictEqual({ - runTime: { median: false } + runTime: { median: false }, + elu: { median: false } }) for (const [, workerChoiceStrategy] of pool.workerChoiceStrategyContext .workerChoiceStrategies) { expect(workerChoiceStrategy.opts).toStrictEqual({ - runTime: { median: false } + runTime: { median: false }, + elu: { median: false } }) } expect( @@ -268,8 +278,8 @@ describe('Abstract pool test suite', () => { median: false }, elu: { - aggregate: false, - average: false, + aggregate: true, + average: true, median: false } }) diff --git a/tests/pools/selection-strategies/selection-strategies.test.js b/tests/pools/selection-strategies/selection-strategies.test.js index 9b581ff5..e9376281 100644 --- a/tests/pools/selection-strategies/selection-strategies.test.js +++ b/tests/pools/selection-strategies/selection-strategies.test.js @@ -898,8 +898,8 @@ describe('Selection strategies test suite', () => { median: false }, elu: { - aggregate: false, - average: false, + aggregate: true, + average: true, median: false } }) @@ -924,8 +924,8 @@ describe('Selection strategies test suite', () => { median: false }, elu: { - aggregate: false, - average: false, + aggregate: true, + average: true, median: false } }) @@ -974,16 +974,18 @@ describe('Selection strategies test suite', () => { history: expect.any(CircularArray) }, active: { - aggregate: 0, - average: 0, + aggregate: expect.any(Number), + average: expect.any(Number), median: 0, history: expect.any(CircularArray) }, - utilization: 0 + utilization: expect.any(Number) } }) expect(workerNode.workerUsage.runTime.aggregate).toBeGreaterThan(0) expect(workerNode.workerUsage.runTime.average).toBeGreaterThan(0) + expect(workerNode.workerUsage.elu.utilization).toBeGreaterThanOrEqual(0) + expect(workerNode.workerUsage.elu.utilization).toBeLessThanOrEqual(1) } expect( pool.workerChoiceStrategyContext.workerChoiceStrategies.get( @@ -1036,16 +1038,18 @@ describe('Selection strategies test suite', () => { history: expect.any(CircularArray) }, active: { - aggregate: 0, - average: 0, + aggregate: expect.any(Number), + average: expect.any(Number), median: 0, history: expect.any(CircularArray) }, - utilization: 0 + utilization: expect.any(Number) } }) expect(workerNode.workerUsage.runTime.aggregate).toBeGreaterThan(0) expect(workerNode.workerUsage.runTime.average).toBeGreaterThan(0) + expect(workerNode.workerUsage.elu.utilization).toBeGreaterThanOrEqual(0) + expect(workerNode.workerUsage.elu.utilization).toBeLessThanOrEqual(1) } expect( pool.workerChoiceStrategyContext.workerChoiceStrategies.get( @@ -1103,16 +1107,18 @@ describe('Selection strategies test suite', () => { history: expect.any(CircularArray) }, active: { - aggregate: 0, - average: 0, + aggregate: expect.any(Number), + average: expect.any(Number), median: 0, history: expect.any(CircularArray) }, - utilization: 0 + utilization: expect.any(Number) } }) expect(workerNode.workerUsage.runTime.aggregate).toBeGreaterThan(0) expect(workerNode.workerUsage.runTime.median).toBeGreaterThan(0) + expect(workerNode.workerUsage.elu.utilization).toBeGreaterThanOrEqual(0) + expect(workerNode.workerUsage.elu.utilization).toBeLessThanOrEqual(1) } expect( pool.workerChoiceStrategyContext.workerChoiceStrategies.get( -- 2.34.1