src/pools/selection-strategies/fair-share-worker-choice-strategy.ts

   1 import { DEFAULT_WORKER_CHOICE_STRATEGY_OPTIONS } from '../../utils'
   2 import type { IPool } from '../pool'
   3 import type { IWorker } from '../worker'
   4 import { AbstractWorkerChoiceStrategy } from './abstract-worker-choice-strategy'
   5 import type {
   6   IWorkerChoiceStrategy,
   7   RequiredStatistics,
   8   WorkerChoiceStrategyOptions
   9 } from './selection-strategies-types'
  10
  11 /**
  12  * Selects the next worker with a fair share scheduling algorithm.
  13  * Loosely modeled after the fair queueing algorithm: https://en.wikipedia.org/wiki/Fair_queuing.
  14  *
  15  * @typeParam Worker - Type of worker which manages the strategy.
  16  * @typeParam Data - Type of data sent to the worker. This can only be serializable data.
  17  * @typeParam Response - Type of execution response. This can only be serializable data.
  18  */
  19 export class FairShareWorkerChoiceStrategy<
  20     Worker extends IWorker,
  21     Data = unknown,
  22     Response = unknown
  23   >
  24   extends AbstractWorkerChoiceStrategy<Worker, Data, Response>
  25   implements IWorkerChoiceStrategy {
  26   /** @inheritDoc */
  27   public readonly requiredStatistics: RequiredStatistics = {
  28     runTime: true,
  29     avgRunTime: true,
  30     medRunTime: false,
  31     waitTime: false,
  32     avgWaitTime: false,
  33     medWaitTime: false,
  34     elu: false
  35   }
  36
  37   /**
  38    * Workers' virtual task end execution timestamp.
  39    */
  40   private workersVirtualTaskEndTimestamp: number[] = []
  41
  42   /** @inheritDoc */
  43   public constructor (
  44     pool: IPool<Worker, Data, Response>,
  45     opts: WorkerChoiceStrategyOptions = DEFAULT_WORKER_CHOICE_STRATEGY_OPTIONS
  46   ) {
  47     super(pool, opts)
  48     this.setRequiredStatistics(this.opts)
  49   }
  50
  51   /** @inheritDoc */
  52   public reset (): boolean {
  53     this.workersVirtualTaskEndTimestamp = []
  54     return true
  55   }
  56
  57   /** @inheritDoc */
  58   public update (workerNodeKey: number): boolean {
  59     this.computeWorkerVirtualTaskEndTimestamp(workerNodeKey)
  60     return true
  61   }
  62
  63   /** @inheritDoc */
  64   public choose (): number {
  65     let minWorkerVirtualTaskEndTimestamp = Infinity
  66     let chosenWorkerNodeKey!: number
  67     for (const [workerNodeKey] of this.pool.workerNodes.entries()) {
  68       if (this.workersVirtualTaskEndTimestamp[workerNodeKey] == null) {
  69         this.computeWorkerVirtualTaskEndTimestamp(workerNodeKey)
  70       }
  71       const workerVirtualTaskEndTimestamp =
  72         this.workersVirtualTaskEndTimestamp[workerNodeKey]
  73       if (workerVirtualTaskEndTimestamp < minWorkerVirtualTaskEndTimestamp) {
  74         minWorkerVirtualTaskEndTimestamp = workerVirtualTaskEndTimestamp
  75         chosenWorkerNodeKey = workerNodeKey
  76       }
  77     }
  78     return chosenWorkerNodeKey
  79   }
  80
  81   /** @inheritDoc */
  82   public remove (workerNodeKey: number): boolean {
  83     this.workersVirtualTaskEndTimestamp.splice(workerNodeKey, 1)
  84     return true
  85   }
  86
  87   /**
  88    * Computes the worker node key virtual task end timestamp.
  89    *
  90    * @param workerNodeKey - The worker node key.
  91    */
  92   private computeWorkerVirtualTaskEndTimestamp (workerNodeKey: number): void {
  93     this.workersVirtualTaskEndTimestamp[workerNodeKey] =
  94       this.getWorkerVirtualTaskEndTimestamp(
  95         workerNodeKey,
  96         this.getWorkerVirtualTaskStartTimestamp(workerNodeKey)
  97       )
  98   }
  99
 100   private getWorkerVirtualTaskEndTimestamp (
 101     workerNodeKey: number,
 102     workerVirtualTaskStartTimestamp: number
 103   ): number {
 104     return (
 105       workerVirtualTaskStartTimestamp + this.getWorkerTaskRunTime(workerNodeKey)
 106     )
 107   }
 108
 109   private getWorkerVirtualTaskStartTimestamp (workerNodeKey: number): number {
 110     return Math.max(
 111       performance.now(),
 112       this.workersVirtualTaskEndTimestamp[workerNodeKey] ?? -Infinity
 113     )
 114   }
 115 }