Skip to content

Commit 8b79055

Browse files
metcoder95huntiezzcursoragent
authored
feat: add stricterFIFO option for queue fairness (#1100) (#1113)
Co-authored-by: huntiez <[email protected]> Co-authored-by: Cursor <[email protected]> Signed-off-by: huntiez <[email protected]>
1 parent f8fbb5f commit 8b79055

8 files changed

Lines changed: 145 additions & 4 deletions

File tree

‎README.md‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -463,6 +463,10 @@ This class extends [`EventEmitter`][] from Node.js.
463463
complete all in-flight tasks when `close()` is called. The default is `30000`
464464
- `recordTiming`: (`boolean`) By default, run and wait time will be recorded
465465
for the pool. To disable, set to `false`.
466+
- `stricterFIFO`: (`boolean`) When `true`, tasks that cannot be dispatched
467+
immediately are returned to the front of the queue instead of the back.
468+
This avoids head-of-line blocking under sustained load (especially with a
469+
single worker). Defaults to `false`.
466470

467471
Use caution when setting resource limits. Setting limits that are too low may
468472
result in the `Piscina` worker threads being unusable.

‎src/index.ts‎

Lines changed: 26 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -76,6 +76,7 @@ interface Options {
7676
trackUnmanagedFds? : boolean,
7777
closeTimeout?: number,
7878
recordTiming?: boolean,
79+
stricterFIFO?: boolean,
7980
loadBalancer?: PiscinaLoadBalancer,
8081
workerHistogram?: boolean,
8182
}
@@ -93,6 +94,7 @@ interface FilledOptions extends Options {
9394
niceIncrement : number,
9495
closeTimeout : number,
9596
recordTiming : boolean,
97+
stricterFIFO : boolean,
9698
workerHistogram: boolean,
9799
}
98100

@@ -128,6 +130,7 @@ const kDefaultOptions : FilledOptions = {
128130
trackUnmanagedFds: true,
129131
closeTimeout: 30000,
130132
recordTiming: true,
133+
stricterFIFO: false,
131134
workerHistogram: false
132135
};
133136

@@ -422,7 +425,9 @@ class ThreadPool {
422425
if (distributed) {
423426
// If task was distributed, we should continue to distribute more tasks
424427
continue;
425-
} else if (this.workers.size < this.options.maxThreads) {
428+
}
429+
430+
if (this.workers.size < this.options.maxThreads) {
426431
// We spawn if possible
427432
// TODO: scheduler will intercept this.
428433
this._addNewWorker();
@@ -473,13 +478,27 @@ class ThreadPool {
473478
return true;
474479
}
475480

481+
this._returnUndistributedTask(task, !this.options.stricterFIFO);
482+
return false;
483+
}
484+
485+
_returnUndistributedTask (task: TaskInfo, toTail = false) : void {
476486
if (task.abortSignal != null) {
477-
this.skipQueue.push(task);
487+
if (toTail) {
488+
this.skipQueue.push(task);
489+
} else {
490+
this.skipQueue.unshift(task);
491+
}
492+
return;
493+
}
494+
495+
if (toTail) {
496+
this.taskQueue.push(task);
497+
} else if (this.taskQueue.unshift != null) {
498+
this.taskQueue.unshift(task);
478499
} else {
479500
this.taskQueue.push(task);
480501
}
481-
482-
return false;
483502
}
484503

485504
runTask (
@@ -795,6 +814,9 @@ export default class Piscina<T = any, R = any> extends EventEmitterAsyncResource
795814
if (opts.workerHistogram !== undefined && (typeof opts.workerHistogram !== 'boolean')) {
796815
throw new TypeError('options.workerHistogram must be a boolean');
797816
}
817+
if (opts.stricterFIFO !== undefined && (typeof opts.stricterFIFO !== 'boolean')) {
818+
throw new TypeError('options.stricterFIFO must be a boolean');
819+
}
798820

799821
this.#pool = new ThreadPool(this, opts);
800822
}

‎src/task_queue/array_queue.ts‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -17,6 +17,10 @@ export class ArrayTaskQueue implements TaskQueue {
1717
this.tasks.push(task);
1818
}
1919

20+
unshift (task: Task): void {
21+
this.tasks.unshift(task);
22+
}
23+
2024
remove (task: Task): void {
2125
const index = this.tasks.indexOf(task);
2226
assert.notStrictEqual(index, -1);

‎src/task_queue/common.ts‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -5,6 +5,7 @@ export interface TaskQueue {
55
shift(): Task | null;
66
remove(task: Task): void;
77
push(task: Task): void;
8+
unshift?(task: Task): void;
89
}
910

1011
// Public Interface

‎src/task_queue/fixed_queue.ts‎

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -77,6 +77,11 @@ class FixedCircularBuffer {
7777
this.top = (this.top + 1) & kMask;
7878
}
7979

80+
unshift (data:Task) {
81+
this.bottom = (this.bottom - 1) & kMask;
82+
this.list[this.bottom] = data;
83+
}
84+
8085
shift () {
8186
const nextItem = this.list[this.bottom];
8287
if (nextItem === undefined) { return null; }
@@ -129,6 +134,16 @@ export class FixedQueue implements TaskQueue {
129134
this.#size++;
130135
}
131136

137+
unshift (data:Task) {
138+
if (this.tail.isFull()) {
139+
const newTail = new FixedCircularBuffer();
140+
newTail.next = this.tail;
141+
this.tail = newTail;
142+
}
143+
this.tail.unshift(data);
144+
this.#size++;
145+
}
146+
132147
shift (): Task | null {
133148
const tail = this.tail;
134149
const next = tail.shift();

‎test/fixtures/task-logger.js‎

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,8 @@
1+
const tasks = [];
2+
3+
module.exports = {
4+
run: task => {
5+
tasks.push(task);
6+
},
7+
getLog: () => tasks
8+
};

‎test/queues.test.ts‎

Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
import * as assert from 'node:assert/strict';
2+
import { test } from 'node:test';
3+
import { kQueueOptions } from '../dist/symbols';
4+
import { FixedQueue, ArrayTaskQueue, PiscinaTask as Task } from '..';
5+
6+
// @ts-expect-error - it misses several properties, but it's enough for the test
7+
class NumberedTask implements Task {
8+
constructor(readonly index: number) {}
9+
get [kQueueOptions] () {
10+
return null;
11+
}
12+
}
13+
14+
for (const QueueClass of [FixedQueue, ArrayTaskQueue]) {
15+
test(`${QueueClass.name} - unshift`, () => {
16+
const bufferSize = 2048;
17+
let queue = new QueueClass();
18+
19+
queue.unshift(new NumberedTask(1));
20+
assert.equal(queue.size, 1);
21+
22+
for (let i = 2; i <= bufferSize + 10; ++i) {
23+
queue.unshift(new NumberedTask(i));
24+
}
25+
assert.equal(queue.size, bufferSize + 10);
26+
27+
for (let i = 0; i < 5; ++i) {
28+
assert.equal((queue.shift() as NumberedTask).index, bufferSize + 10 - i);
29+
}
30+
assert.equal(queue.size, bufferSize + 5);
31+
32+
for (let i = 0; i < bufferSize + 5; ++i) {
33+
assert.equal((queue.shift() as NumberedTask).index, bufferSize + 5 - i);
34+
}
35+
assert.equal(queue.size, 0);
36+
37+
queue = new QueueClass();
38+
queue.push(new NumberedTask(1));
39+
queue.push(new NumberedTask(2));
40+
queue.push(new NumberedTask(3));
41+
queue.push(new NumberedTask(4));
42+
queue.push(new NumberedTask(5));
43+
assert.equal((queue.shift() as NumberedTask).index, 1);
44+
assert.equal((queue.shift() as NumberedTask).index, 2);
45+
assert.equal((queue.shift() as NumberedTask).index, 3);
46+
assert.equal(queue.size, 2);
47+
queue.unshift(new NumberedTask(6));
48+
queue.unshift(new NumberedTask(7));
49+
queue.unshift(new NumberedTask(8));
50+
queue.unshift(new NumberedTask(9));
51+
assert.equal((queue.shift() as NumberedTask).index, 9);
52+
assert.equal((queue.shift() as NumberedTask).index, 8);
53+
assert.equal((queue.shift() as NumberedTask).index, 7);
54+
assert.equal((queue.shift() as NumberedTask).index, 6);
55+
assert.equal((queue.shift() as NumberedTask).index, 4);
56+
assert.equal((queue.shift() as NumberedTask).index, 5);
57+
});
58+
}

‎test/stricter-fifo.test.ts‎

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
import * as assert from 'node:assert/strict';
2+
import { resolve } from 'node:path';
3+
import { test } from 'node:test';
4+
import Piscina from '..';
5+
6+
test('stricterFIFO keeps queued tasks in submission order', async () => {
7+
const pool = new Piscina({
8+
filename: resolve(__dirname, 'fixtures/task-logger.js'),
9+
minThreads: 1,
10+
maxThreads: 1,
11+
stricterFIFO: true
12+
});
13+
14+
const tasks = new Array(20).fill(0).map((_, i) => ({ i }));
15+
const pending = tasks.map((task) => pool.run(task, { name: 'run' }));
16+
await Promise.all(pending);
17+
18+
const log = await pool.run({}, { name: 'getLog' });
19+
assert.deepEqual(log, tasks);
20+
21+
await pool.destroy();
22+
});
23+
24+
test('stricterFIFO must be a boolean', () => {
25+
assert.throws(
26+
() => new Piscina({ stricterFIFO: 1 } as any),
27+
/options.stricterFIFO must be a boolean/
28+
);
29+
});

0 commit comments

Comments
 (0)