Commit | Line | Data |
---|---|---|
d35e5717 | 1 | import type { IPool } from '../pool.js' |
67f3f2d6 | 2 | import type { IWorker } from '../worker.js' |
d35e5717 | 3 | import { AbstractWorkerChoiceStrategy } from './abstract-worker-choice-strategy.js' |
9adcefab JB |
4 | import { |
5 | type IWorkerChoiceStrategy, | |
6 | Measurements, | |
39618ede JB |
7 | type TaskStatisticsRequirements, |
8 | type WorkerChoiceStrategyOptions | |
d35e5717 | 9 | } from './selection-strategies-types.js' |
23ff945a | 10 | |
23ff945a JB |
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 | * | |
38e795c1 | 15 | * @typeParam Worker - Type of worker which manages the strategy. |
e102732c JB |
16 | * @typeParam Data - Type of data sent to the worker. This can only be structured-cloneable data. |
17 | * @typeParam Response - Type of execution response. This can only be structured-cloneable data. | |
23ff945a JB |
18 | */ |
19 | export class FairShareWorkerChoiceStrategy< | |
f06e48d8 | 20 | Worker extends IWorker, |
b2b1d84e JB |
21 | Data = unknown, |
22 | Response = unknown | |
bf90656c JB |
23 | > |
24 | extends AbstractWorkerChoiceStrategy<Worker, Data, Response> | |
17393ac8 | 25 | implements IWorkerChoiceStrategy { |
afc003b2 | 26 | /** @inheritDoc */ |
87de9ff5 | 27 | public readonly taskStatisticsRequirements: TaskStatisticsRequirements = { |
932fc8be JB |
28 | runTime: { |
29 | aggregate: true, | |
30 | average: true, | |
31 | median: false | |
32 | }, | |
e0843544 JB |
33 | waitTime: { |
34 | aggregate: true, | |
35 | average: true, | |
36 | median: false | |
37 | }, | |
5df69fab | 38 | elu: { |
9adcefab JB |
39 | aggregate: true, |
40 | average: true, | |
5df69fab JB |
41 | median: false |
42 | } | |
10fcfaf4 JB |
43 | } |
44 | ||
2fc5cae3 JB |
45 | /** @inheritDoc */ |
46 | public constructor ( | |
47 | pool: IPool<Worker, Data, Response>, | |
39618ede | 48 | opts?: WorkerChoiceStrategyOptions |
2fc5cae3 JB |
49 | ) { |
50 | super(pool, opts) | |
932fc8be | 51 | this.setTaskStatisticsRequirements(this.opts) |
2fc5cae3 JB |
52 | } |
53 | ||
afc003b2 | 54 | /** @inheritDoc */ |
a6f7f1b4 | 55 | public reset (): boolean { |
f3a91bac JB |
56 | for (const workerNode of this.pool.workerNodes) { |
57 | delete workerNode.strategyData?.virtualTaskEndTimestamp | |
58 | } | |
ea7a90d3 JB |
59 | return true |
60 | } | |
61 | ||
138d29a8 | 62 | /** @inheritDoc */ |
a4958de2 | 63 | public update (workerNodeKey: number): boolean { |
f3a91bac JB |
64 | this.pool.workerNodes[workerNodeKey].strategyData = { |
65 | virtualTaskEndTimestamp: | |
66 | this.computeWorkerNodeVirtualTaskEndTimestamp(workerNodeKey) | |
67 | } | |
db703c75 JB |
68 | return true |
69 | } | |
70 | ||
71 | /** @inheritDoc */ | |
b1aae695 | 72 | public choose (): number | undefined { |
baca80f7 | 73 | this.setPreviousWorkerNodeKey(this.nextWorkerNodeKey) |
fce028d6 | 74 | this.nextWorkerNodeKey = this.fairShareNextWorkerNodeKey() |
b1aae695 | 75 | return this.nextWorkerNodeKey |
9b106837 JB |
76 | } |
77 | ||
78 | /** @inheritDoc */ | |
f3a91bac | 79 | public remove (): boolean { |
9b106837 JB |
80 | return true |
81 | } | |
82 | ||
b1aae695 | 83 | private fairShareNextWorkerNodeKey (): number | undefined { |
e44639e9 JB |
84 | if (this.pool.workerNodes.length === 0) { |
85 | return undefined | |
86 | } | |
f3a91bac JB |
87 | return this.pool.workerNodes.reduce( |
88 | (minWorkerNodeKey, workerNode, workerNodeKey, workerNodes) => { | |
89 | if (workerNode.strategyData?.virtualTaskEndTimestamp == null) { | |
90 | workerNode.strategyData = { | |
91 | virtualTaskEndTimestamp: | |
92 | this.computeWorkerNodeVirtualTaskEndTimestamp(workerNodeKey) | |
93 | } | |
94 | } | |
ae3ab61d | 95 | return this.isWorkerNodeReady(workerNodeKey) && |
67f3f2d6 JB |
96 | // eslint-disable-next-line @typescript-eslint/no-non-null-assertion |
97 | workerNode.strategyData.virtualTaskEndTimestamp! < | |
98 | // eslint-disable-next-line @typescript-eslint/no-non-null-assertion | |
99 | workerNodes[minWorkerNodeKey].strategyData!.virtualTaskEndTimestamp! | |
f3a91bac JB |
100 | ? workerNodeKey |
101 | : minWorkerNodeKey | |
102 | }, | |
103 | 0 | |
104 | ) | |
97a2abc3 JB |
105 | } |
106 | ||
23ff945a | 107 | /** |
b0d6ed8f | 108 | * Computes the worker node key virtual task end timestamp. |
11df3590 | 109 | * |
f06e48d8 | 110 | * @param workerNodeKey - The worker node key. |
f3a91bac | 111 | * @returns The worker node key virtual task end timestamp. |
23ff945a | 112 | */ |
f3a91bac JB |
113 | private computeWorkerNodeVirtualTaskEndTimestamp ( |
114 | workerNodeKey: number | |
115 | ): number { | |
116 | return this.getWorkerNodeVirtualTaskEndTimestamp( | |
117 | workerNodeKey, | |
118 | this.getWorkerNodeVirtualTaskStartTimestamp(workerNodeKey) | |
119 | ) | |
b0d6ed8f JB |
120 | } |
121 | ||
f3a91bac | 122 | private getWorkerNodeVirtualTaskEndTimestamp ( |
b0d6ed8f | 123 | workerNodeKey: number, |
f3a91bac | 124 | workerNodeVirtualTaskStartTimestamp: number |
b0d6ed8f | 125 | ): number { |
e0843544 JB |
126 | const workerNodeTaskExecutionTime = |
127 | this.getWorkerNodeTaskWaitTime(workerNodeKey) + | |
39618ede | 128 | // eslint-disable-next-line @typescript-eslint/no-non-null-assertion |
e0843544 | 129 | (this.opts!.measurement === Measurements.elu |
f3a91bac | 130 | ? this.getWorkerNodeTaskElu(workerNodeKey) |
e0843544 JB |
131 | : this.getWorkerNodeTaskRunTime(workerNodeKey)) |
132 | return workerNodeVirtualTaskStartTimestamp + workerNodeTaskExecutionTime | |
b0d6ed8f JB |
133 | } |
134 | ||
f3a91bac JB |
135 | private getWorkerNodeVirtualTaskStartTimestamp ( |
136 | workerNodeKey: number | |
137 | ): number { | |
f201a0cd JB |
138 | const virtualTaskEndTimestamp = |
139 | this.pool.workerNodes[workerNodeKey]?.strategyData | |
140 | ?.virtualTaskEndTimestamp | |
f3a91bac | 141 | const now = performance.now() |
f201a0cd | 142 | return now < (virtualTaskEndTimestamp ?? -Infinity) |
67f3f2d6 JB |
143 | ? // eslint-disable-next-line @typescript-eslint/no-non-null-assertion |
144 | virtualTaskEndTimestamp! | |
f3a91bac | 145 | : now |
23ff945a JB |
146 | } |
147 | } |