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

   1 import type { IPoolWorker } from '../pool-worker'
   2 import { AbstractWorkerChoiceStrategy } from './abstract-worker-choice-strategy'
   3 import type { RequiredStatistics } from './selection-strategies-types'
   4
   5 /**
   6  * Worker virtual task timestamp.
   7  */
   8 type WorkerVirtualTaskTimestamp = {
   9   start: number
  10   end: number
  11 }
  12
  13 /**
  14  * Selects the next worker with a fair share scheduling algorithm.
  15  * Loosely modeled after the fair queueing algorithm: https://en.wikipedia.org/wiki/Fair_queuing.
  16  *
  17  * @template Worker Type of worker which manages the strategy.
  18  * @template Data Type of data sent to the worker. This can only be serializable data.
  19  * @template Response Type of response of execution. This can only be serializable data.
  20  */
  21 export class FairShareWorkerChoiceStrategy<
  22   Worker extends IPoolWorker,
  23   Data,
  24   Response
  25 > extends AbstractWorkerChoiceStrategy<Worker, Data, Response> {
  26   /** @inheritDoc */
  27   public readonly requiredStatistics: RequiredStatistics = {
  28     runTime: true
  29   }
  30
  31   /**
  32    *  Worker last virtual task execution timestamp.
  33    */
  34   private readonly workerLastVirtualTaskTimestamp: Map<
  35     Worker,
  36     WorkerVirtualTaskTimestamp
  37   > = new Map<Worker, WorkerVirtualTaskTimestamp>()
  38
  39   /** @inheritDoc */
  40   public resetStatistics (): boolean {
  41     this.workerLastVirtualTaskTimestamp.clear()
  42     return true
  43   }
  44
  45   /** @inheritDoc */
  46   public choose (): Worker {
  47     this.computeWorkerLastVirtualTaskTimestamp()
  48     let minWorkerVirtualTaskEndTimestamp = Infinity
  49     let chosenWorker!: Worker
  50     for (const worker of this.pool.workers) {
  51       const workerLastVirtualTaskEndTimestamp =
  52         this.workerLastVirtualTaskTimestamp.get(worker)?.end ?? 0
  53       if (
  54         workerLastVirtualTaskEndTimestamp < minWorkerVirtualTaskEndTimestamp
  55       ) {
  56         minWorkerVirtualTaskEndTimestamp = workerLastVirtualTaskEndTimestamp
  57         chosenWorker = worker
  58       }
  59     }
  60     return chosenWorker
  61   }
  62
  63   /**
  64    * Computes workers last virtual task timestamp.
  65    */
  66   private computeWorkerLastVirtualTaskTimestamp () {
  67     for (const worker of this.pool.workers) {
  68       const workerVirtualTaskStartTimestamp = Math.max(
  69         Date.now(),
  70         this.workerLastVirtualTaskTimestamp.get(worker)?.end ?? -Infinity
  71       )
  72       const workerVirtualTaskEndTimestamp =
  73         workerVirtualTaskStartTimestamp +
  74         (this.pool.getWorkerAverageTasksRunTime(worker) ?? 0)
  75       this.workerLastVirtualTaskTimestamp.set(worker, {
  76         start: workerVirtualTaskStartTimestamp,
  77         end: workerVirtualTaskEndTimestamp
  78       })
  79     }
  80   }
  81 }