From d33be4309c69e39da5e81479e40b1a5ec7078bd5 Mon Sep 17 00:00:00 2001 From: =?utf8?q?J=C3=A9r=C3=B4me=20Benoit?= Date: Fri, 16 Jun 2023 21:27:58 +0200 Subject: [PATCH] perf: optimize worker choice strategies MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Signed-off-by: Jérôme Benoit --- CHANGELOG.md | 1 + .../abstract-worker-choice-strategy.ts | 5 ++ .../fair-share-worker-choice-strategy.ts | 15 +++--- ...hted-round-robin-worker-choice-strategy.ts | 48 ++++++++---------- .../least-busy-worker-choice-strategy.ts | 18 +++---- .../least-elu-worker-choice-strategy.ts | 18 +++---- .../least-used-worker-choice-strategy.ts | 22 ++++---- .../round-robin-worker-choice-strategy.ts | 5 -- ...hted-round-robin-worker-choice-strategy.ts | 22 ++++---- .../selection-strategies.test.js | 50 ++++++++++--------- ...round-robin-worker-choice-strategy.test.js | 2 +- 11 files changed, 97 insertions(+), 109 deletions(-) diff --git a/CHANGELOG.md b/CHANGELOG.md index 9058bed6..40a1eac2 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -14,6 +14,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 ### Changed - Optimize O(1) queue implementation. +- Optimize worker choice strategies: pre-choose the worker node key by executing the choice algorithm after tasks submission. ## [2.6.2] - 2023-06-12 diff --git a/src/pools/selection-strategies/abstract-worker-choice-strategy.ts b/src/pools/selection-strategies/abstract-worker-choice-strategy.ts index a060cea3..feb7d957 100644 --- a/src/pools/selection-strategies/abstract-worker-choice-strategy.ts +++ b/src/pools/selection-strategies/abstract-worker-choice-strategy.ts @@ -26,6 +26,11 @@ export abstract class AbstractWorkerChoiceStrategy< */ private toggleFindLastFreeWorkerNodeKey: boolean = false + /** + * Id of the next worker node. + */ + protected nextWorkerNodeId: number = 0 + /** @inheritDoc */ public readonly strategyPolicy: StrategyPolicy = { useDynamicWorker: false 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 ff9eaf36..39da59a0 100644 --- a/src/pools/selection-strategies/fair-share-worker-choice-strategy.ts +++ b/src/pools/selection-strategies/fair-share-worker-choice-strategy.ts @@ -66,13 +66,7 @@ export class FairShareWorkerChoiceStrategy< /** @inheritDoc */ public update (workerNodeKey: number): boolean { this.computeWorkerVirtualTaskEndTimestamp(workerNodeKey) - return true - } - - /** @inheritDoc */ - public choose (): number { let minWorkerVirtualTaskEndTimestamp = Infinity - let chosenWorkerNodeKey!: number for (const [workerNodeKey] of this.pool.workerNodes.entries()) { if (this.workersVirtualTaskEndTimestamp[workerNodeKey] == null) { this.computeWorkerVirtualTaskEndTimestamp(workerNodeKey) @@ -81,10 +75,15 @@ export class FairShareWorkerChoiceStrategy< this.workersVirtualTaskEndTimestamp[workerNodeKey] if (workerVirtualTaskEndTimestamp < minWorkerVirtualTaskEndTimestamp) { minWorkerVirtualTaskEndTimestamp = workerVirtualTaskEndTimestamp - chosenWorkerNodeKey = workerNodeKey + this.nextWorkerNodeId = workerNodeKey } } - return chosenWorkerNodeKey + return true + } + + /** @inheritDoc */ + public choose (): number { + return this.nextWorkerNodeId } /** @inheritDoc */ diff --git a/src/pools/selection-strategies/interleaved-weighted-round-robin-worker-choice-strategy.ts b/src/pools/selection-strategies/interleaved-weighted-round-robin-worker-choice-strategy.ts index deaa4881..85f31483 100644 --- a/src/pools/selection-strategies/interleaved-weighted-round-robin-worker-choice-strategy.ts +++ b/src/pools/selection-strategies/interleaved-weighted-round-robin-worker-choice-strategy.ts @@ -28,14 +28,10 @@ export class InterleavedWeightedRoundRobinWorkerChoiceStrategy< } /** - * Worker node id where the current task will be submitted. - */ - private currentWorkerNodeId: number = 0 - /** - * Current round id. + * Round id. * This is used to determine the current round weight. */ - private currentRoundId: number = 0 + private roundId: number = 0 /** * Round weights. */ @@ -58,8 +54,8 @@ export class InterleavedWeightedRoundRobinWorkerChoiceStrategy< /** @inheritDoc */ public reset (): boolean { - this.currentWorkerNodeId = 0 - this.currentRoundId = 0 + this.nextWorkerNodeId = 0 + this.roundId = 0 return true } @@ -73,12 +69,12 @@ export class InterleavedWeightedRoundRobinWorkerChoiceStrategy< let roundId: number | undefined let workerNodeId: number | undefined for ( - let roundIndex = this.currentRoundId; + let roundIndex = this.roundId; roundIndex < this.roundWeights.length; roundIndex++ ) { for ( - let workerNodeKey = this.currentWorkerNodeId; + let workerNodeKey = this.nextWorkerNodeId; workerNodeKey < this.pool.workerNodes.length; workerNodeKey++ ) { @@ -91,32 +87,28 @@ export class InterleavedWeightedRoundRobinWorkerChoiceStrategy< } } } - this.currentRoundId = roundId ?? 0 - this.currentWorkerNodeId = workerNodeId ?? 0 - const chosenWorkerNodeKey = this.currentWorkerNodeId - if (this.currentWorkerNodeId === this.pool.workerNodes.length - 1) { - this.currentWorkerNodeId = 0 - this.currentRoundId = - this.currentRoundId === this.roundWeights.length - 1 - ? 0 - : this.currentRoundId + 1 + this.roundId = roundId ?? 0 + this.nextWorkerNodeId = workerNodeId ?? 0 + const chosenWorkerNodeKey = this.nextWorkerNodeId + if (this.nextWorkerNodeId === this.pool.workerNodes.length - 1) { + this.nextWorkerNodeId = 0 + this.roundId = + this.roundId === this.roundWeights.length - 1 ? 0 : this.roundId + 1 } else { - this.currentWorkerNodeId = this.currentWorkerNodeId + 1 + this.nextWorkerNodeId = this.nextWorkerNodeId + 1 } return chosenWorkerNodeKey } /** @inheritDoc */ public remove (workerNodeKey: number): boolean { - if (this.currentWorkerNodeId === workerNodeKey) { + if (this.nextWorkerNodeId === workerNodeKey) { if (this.pool.workerNodes.length === 0) { - this.currentWorkerNodeId = 0 - } else if (this.currentWorkerNodeId > this.pool.workerNodes.length - 1) { - this.currentWorkerNodeId = this.pool.workerNodes.length - 1 - this.currentRoundId = - this.currentRoundId === this.roundWeights.length - 1 - ? 0 - : this.currentRoundId + 1 + this.nextWorkerNodeId = 0 + } else if (this.nextWorkerNodeId > this.pool.workerNodes.length - 1) { + this.nextWorkerNodeId = this.pool.workerNodes.length - 1 + this.roundId = + this.roundId === this.roundWeights.length - 1 ? 0 : this.roundId + 1 } } return true diff --git a/src/pools/selection-strategies/least-busy-worker-choice-strategy.ts b/src/pools/selection-strategies/least-busy-worker-choice-strategy.ts index 58fbb51e..dc304c89 100644 --- a/src/pools/selection-strategies/least-busy-worker-choice-strategy.ts +++ b/src/pools/selection-strategies/least-busy-worker-choice-strategy.ts @@ -57,25 +57,25 @@ export class LeastBusyWorkerChoiceStrategy< /** @inheritDoc */ public update (): boolean { - return true - } - - /** @inheritDoc */ - public choose (): number { let minTime = Infinity - let leastBusyWorkerNodeKey!: number for (const [workerNodeKey, workerNode] of this.pool.workerNodes.entries()) { const workerTime = workerNode.workerUsage.runTime.aggregate + workerNode.workerUsage.waitTime.aggregate if (workerTime === 0) { - return workerNodeKey + this.nextWorkerNodeId = workerNodeKey + return true } else if (workerTime < minTime) { minTime = workerTime - leastBusyWorkerNodeKey = workerNodeKey + this.nextWorkerNodeId = workerNodeKey } } - return leastBusyWorkerNodeKey + return true + } + + /** @inheritDoc */ + public choose (): number { + return this.nextWorkerNodeId } /** @inheritDoc */ diff --git a/src/pools/selection-strategies/least-elu-worker-choice-strategy.ts b/src/pools/selection-strategies/least-elu-worker-choice-strategy.ts index 35ab69d0..eca5a1cf 100644 --- a/src/pools/selection-strategies/least-elu-worker-choice-strategy.ts +++ b/src/pools/selection-strategies/least-elu-worker-choice-strategy.ts @@ -57,24 +57,24 @@ export class LeastEluWorkerChoiceStrategy< /** @inheritDoc */ public update (): boolean { - return true - } - - /** @inheritDoc */ - public choose (): number { let minWorkerElu = Infinity - let leastEluWorkerNodeKey!: number for (const [workerNodeKey, workerNode] of this.pool.workerNodes.entries()) { const workerUsage = workerNode.workerUsage const workerElu = workerUsage.elu?.active.aggregate ?? 0 if (workerElu === 0) { - return workerNodeKey + this.nextWorkerNodeId = workerNodeKey + return true } else if (workerElu < minWorkerElu) { minWorkerElu = workerElu - leastEluWorkerNodeKey = workerNodeKey + this.nextWorkerNodeId = workerNodeKey } } - return leastEluWorkerNodeKey + return true + } + + /** @inheritDoc */ + public choose (): number { + return this.nextWorkerNodeId } /** @inheritDoc */ diff --git a/src/pools/selection-strategies/least-used-worker-choice-strategy.ts b/src/pools/selection-strategies/least-used-worker-choice-strategy.ts index 4161a1d2..a505e627 100644 --- a/src/pools/selection-strategies/least-used-worker-choice-strategy.ts +++ b/src/pools/selection-strategies/least-used-worker-choice-strategy.ts @@ -37,17 +37,7 @@ export class LeastUsedWorkerChoiceStrategy< /** @inheritDoc */ public update (): boolean { - return true - } - - /** @inheritDoc */ - public choose (): number { - const freeWorkerNodeKey = this.findFreeWorkerNodeKey() - if (freeWorkerNodeKey !== -1) { - return freeWorkerNodeKey - } let minNumberOfTasks = Infinity - let leastUsedWorkerNodeKey!: number for (const [workerNodeKey, workerNode] of this.pool.workerNodes.entries()) { const workerTaskStatistics = workerNode.workerUsage.tasks const workerTasks = @@ -55,13 +45,19 @@ export class LeastUsedWorkerChoiceStrategy< workerTaskStatistics.executing + workerTaskStatistics.queued if (workerTasks === 0) { - return workerNodeKey + this.nextWorkerNodeId = workerNodeKey + return true } else if (workerTasks < minNumberOfTasks) { minNumberOfTasks = workerTasks - leastUsedWorkerNodeKey = workerNodeKey + this.nextWorkerNodeId = workerNodeKey } } - return leastUsedWorkerNodeKey + return true + } + + /** @inheritDoc */ + public choose (): number { + return this.nextWorkerNodeId } /** @inheritDoc */ diff --git a/src/pools/selection-strategies/round-robin-worker-choice-strategy.ts b/src/pools/selection-strategies/round-robin-worker-choice-strategy.ts index 93692531..0995b350 100644 --- a/src/pools/selection-strategies/round-robin-worker-choice-strategy.ts +++ b/src/pools/selection-strategies/round-robin-worker-choice-strategy.ts @@ -27,11 +27,6 @@ export class RoundRobinWorkerChoiceStrategy< useDynamicWorker: true } - /** - * Id of the next worker node. - */ - private nextWorkerNodeId: number = 0 - /** @inheritDoc */ public constructor ( pool: IPool, diff --git a/src/pools/selection-strategies/weighted-round-robin-worker-choice-strategy.ts b/src/pools/selection-strategies/weighted-round-robin-worker-choice-strategy.ts index 618b5065..fc6f48cf 100644 --- a/src/pools/selection-strategies/weighted-round-robin-worker-choice-strategy.ts +++ b/src/pools/selection-strategies/weighted-round-robin-worker-choice-strategy.ts @@ -48,10 +48,6 @@ export class WeightedRoundRobinWorkerChoiceStrategy< } } - /** - * Worker node id where the current task will be submitted. - */ - private currentWorkerNodeId: number = 0 /** * Default worker weight. */ @@ -73,7 +69,7 @@ export class WeightedRoundRobinWorkerChoiceStrategy< /** @inheritDoc */ public reset (): boolean { - this.currentWorkerNodeId = 0 + this.nextWorkerNodeId = 0 this.workerVirtualTaskRunTime = 0 return true } @@ -85,7 +81,7 @@ export class WeightedRoundRobinWorkerChoiceStrategy< /** @inheritDoc */ public choose (): number { - const chosenWorkerNodeKey = this.currentWorkerNodeId + const chosenWorkerNodeKey = this.nextWorkerNodeId const workerVirtualTaskRunTime = this.workerVirtualTaskRunTime const workerWeight = this.opts.weights?.[chosenWorkerNodeKey] ?? this.defaultWorkerWeight @@ -94,10 +90,10 @@ export class WeightedRoundRobinWorkerChoiceStrategy< workerVirtualTaskRunTime + this.getWorkerTaskRunTime(chosenWorkerNodeKey) } else { - this.currentWorkerNodeId = - this.currentWorkerNodeId === this.pool.workerNodes.length - 1 + this.nextWorkerNodeId = + this.nextWorkerNodeId === this.pool.workerNodes.length - 1 ? 0 - : this.currentWorkerNodeId + 1 + : this.nextWorkerNodeId + 1 this.workerVirtualTaskRunTime = 0 } return chosenWorkerNodeKey @@ -105,11 +101,11 @@ export class WeightedRoundRobinWorkerChoiceStrategy< /** @inheritDoc */ public remove (workerNodeKey: number): boolean { - if (this.currentWorkerNodeId === workerNodeKey) { + if (this.nextWorkerNodeId === workerNodeKey) { if (this.pool.workerNodes.length === 0) { - this.currentWorkerNodeId = 0 - } else if (this.currentWorkerNodeId > this.pool.workerNodes.length - 1) { - this.currentWorkerNodeId = this.pool.workerNodes.length - 1 + this.nextWorkerNodeId = 0 + } else if (this.nextWorkerNodeId > this.pool.workerNodes.length - 1) { + this.nextWorkerNodeId = this.pool.workerNodes.length - 1 } this.workerVirtualTaskRunTime = 0 } diff --git a/tests/pools/selection-strategies/selection-strategies.test.js b/tests/pools/selection-strategies/selection-strategies.test.js index 0df558de..d7567114 100644 --- a/tests/pools/selection-strategies/selection-strategies.test.js +++ b/tests/pools/selection-strategies/selection-strategies.test.js @@ -98,7 +98,7 @@ describe('Selection strategies test suite', () => { expect( pool.workerChoiceStrategyContext.workerChoiceStrategies.get( workerChoiceStrategy - ).currentWorkerNodeId + ).nextWorkerNodeId ).toBe(0) expect( pool.workerChoiceStrategyContext.workerChoiceStrategies.get( @@ -1069,7 +1069,7 @@ describe('Selection strategies test suite', () => { for (const workerNode of pool.workerNodes) { expect(workerNode.workerUsage).toStrictEqual({ tasks: { - executed: maxMultiplier, + executed: expect.any(Number), executing: 0, queued: 0, failed: 0 @@ -1102,6 +1102,10 @@ describe('Selection strategies test suite', () => { utilization: expect.any(Number) } }) + expect(workerNode.workerUsage.tasks.executed).toBeGreaterThanOrEqual(0) + expect(workerNode.workerUsage.tasks.executed).toBeLessThanOrEqual( + max * maxMultiplier + ) expect(workerNode.workerUsage.runTime.aggregate).toBeGreaterThan(0) expect(workerNode.workerUsage.runTime.average).toBeGreaterThan(0) expect(workerNode.workerUsage.elu.utilization).toBeGreaterThanOrEqual(0) @@ -1166,12 +1170,12 @@ describe('Selection strategies test suite', () => { utilization: expect.any(Number) } }) - expect(workerNode.workerUsage.tasks.executed).toBeGreaterThan(0) + expect(workerNode.workerUsage.tasks.executed).toBeGreaterThanOrEqual(0) expect(workerNode.workerUsage.tasks.executed).toBeLessThanOrEqual( max * maxMultiplier ) - expect(workerNode.workerUsage.runTime.aggregate).toBeGreaterThan(0) - expect(workerNode.workerUsage.runTime.average).toBeGreaterThan(0) + expect(workerNode.workerUsage.runTime.aggregate).toBeGreaterThanOrEqual(0) + expect(workerNode.workerUsage.runTime.average).toBeGreaterThanOrEqual(0) expect(workerNode.workerUsage.elu.utilization).toBeGreaterThanOrEqual(0) expect(workerNode.workerUsage.elu.utilization).toBeLessThanOrEqual(1) } @@ -1239,12 +1243,12 @@ describe('Selection strategies test suite', () => { utilization: expect.any(Number) } }) - expect(workerNode.workerUsage.tasks.executed).toBeGreaterThan(0) + expect(workerNode.workerUsage.tasks.executed).toBeGreaterThanOrEqual(0) expect(workerNode.workerUsage.tasks.executed).toBeLessThanOrEqual( max * maxMultiplier ) - expect(workerNode.workerUsage.runTime.aggregate).toBeGreaterThan(0) - expect(workerNode.workerUsage.runTime.median).toBeGreaterThan(0) + expect(workerNode.workerUsage.runTime.aggregate).toBeGreaterThanOrEqual(0) + expect(workerNode.workerUsage.runTime.median).toBeGreaterThanOrEqual(0) expect(workerNode.workerUsage.elu.utilization).toBeGreaterThanOrEqual(0) expect(workerNode.workerUsage.elu.utilization).toBeLessThanOrEqual(1) } @@ -1637,7 +1641,7 @@ describe('Selection strategies test suite', () => { expect( pool.workerChoiceStrategyContext.workerChoiceStrategies.get( workerChoiceStrategy - ).currentWorkerNodeId + ).nextWorkerNodeId ).toBeDefined() expect( pool.workerChoiceStrategyContext.workerChoiceStrategies.get( @@ -1653,7 +1657,7 @@ describe('Selection strategies test suite', () => { expect( pool.workerChoiceStrategyContext.workerChoiceStrategies.get( pool.workerChoiceStrategyContext.workerChoiceStrategy - ).currentWorkerNodeId + ).nextWorkerNodeId ).toBe(0) expect( pool.workerChoiceStrategyContext.workerChoiceStrategies.get( @@ -1674,7 +1678,7 @@ describe('Selection strategies test suite', () => { expect( pool.workerChoiceStrategyContext.workerChoiceStrategies.get( workerChoiceStrategy - ).currentWorkerNodeId + ).nextWorkerNodeId ).toBeDefined() expect( pool.workerChoiceStrategyContext.workerChoiceStrategies.get( @@ -1690,7 +1694,7 @@ describe('Selection strategies test suite', () => { expect( pool.workerChoiceStrategyContext.workerChoiceStrategies.get( pool.workerChoiceStrategyContext.workerChoiceStrategy - ).currentWorkerNodeId + ).nextWorkerNodeId ).toBe(0) expect( pool.workerChoiceStrategyContext.workerChoiceStrategies.get( @@ -1849,12 +1853,12 @@ describe('Selection strategies test suite', () => { expect( pool.workerChoiceStrategyContext.workerChoiceStrategies.get( pool.workerChoiceStrategyContext.workerChoiceStrategy - ).currentRoundId + ).roundId ).toBe(0) expect( pool.workerChoiceStrategyContext.workerChoiceStrategies.get( pool.workerChoiceStrategyContext.workerChoiceStrategy - ).currentWorkerNodeId + ).nextWorkerNodeId ).toBe(0) expect( pool.workerChoiceStrategyContext.workerChoiceStrategies.get( @@ -1931,12 +1935,12 @@ describe('Selection strategies test suite', () => { expect( pool.workerChoiceStrategyContext.workerChoiceStrategies.get( pool.workerChoiceStrategyContext.workerChoiceStrategy - ).currentRoundId + ).roundId ).toBe(0) expect( pool.workerChoiceStrategyContext.workerChoiceStrategies.get( pool.workerChoiceStrategyContext.workerChoiceStrategy - ).currentWorkerNodeId + ).nextWorkerNodeId ).toBe(0) expect( pool.workerChoiceStrategyContext.workerChoiceStrategies.get( @@ -1961,12 +1965,12 @@ describe('Selection strategies test suite', () => { expect( pool.workerChoiceStrategyContext.workerChoiceStrategies.get( workerChoiceStrategy - ).currentRoundId + ).roundId ).toBeDefined() expect( pool.workerChoiceStrategyContext.workerChoiceStrategies.get( workerChoiceStrategy - ).currentWorkerNodeId + ).nextWorkerNodeId ).toBeDefined() expect( pool.workerChoiceStrategyContext.workerChoiceStrategies.get( @@ -1982,12 +1986,12 @@ describe('Selection strategies test suite', () => { expect( pool.workerChoiceStrategyContext.workerChoiceStrategies.get( workerChoiceStrategy - ).currentRoundId + ).roundId ).toBe(0) expect( pool.workerChoiceStrategyContext.workerChoiceStrategies.get( pool.workerChoiceStrategyContext.workerChoiceStrategy - ).currentWorkerNodeId + ).nextWorkerNodeId ).toBe(0) expect( pool.workerChoiceStrategyContext.workerChoiceStrategies.get( @@ -2012,12 +2016,12 @@ describe('Selection strategies test suite', () => { expect( pool.workerChoiceStrategyContext.workerChoiceStrategies.get( workerChoiceStrategy - ).currentRoundId + ).roundId ).toBeDefined() expect( pool.workerChoiceStrategyContext.workerChoiceStrategies.get( workerChoiceStrategy - ).currentWorkerNodeId + ).nextWorkerNodeId ).toBeDefined() expect( pool.workerChoiceStrategyContext.workerChoiceStrategies.get( @@ -2033,7 +2037,7 @@ describe('Selection strategies test suite', () => { expect( pool.workerChoiceStrategyContext.workerChoiceStrategies.get( pool.workerChoiceStrategyContext.workerChoiceStrategy - ).currentWorkerNodeId + ).nextWorkerNodeId ).toBe(0) expect( pool.workerChoiceStrategyContext.workerChoiceStrategies.get( diff --git a/tests/pools/selection-strategies/weighted-round-robin-worker-choice-strategy.test.js b/tests/pools/selection-strategies/weighted-round-robin-worker-choice-strategy.test.js index 3f94411c..b21c41ff 100644 --- a/tests/pools/selection-strategies/weighted-round-robin-worker-choice-strategy.test.js +++ b/tests/pools/selection-strategies/weighted-round-robin-worker-choice-strategy.test.js @@ -35,7 +35,7 @@ describe('Weighted round robin strategy worker choice strategy test suite', () = ) const resetResult = strategy.reset() expect(resetResult).toBe(true) - expect(strategy.currentWorkerNodeId).toBe(0) + expect(strategy.nextWorkerNodeId).toBe(0) expect(strategy.workerVirtualTaskRunTime).toBe(0) }) }) -- 2.34.1