Fix a TODO and slightly optimize backfill strategy. (#4621)
Closes https://github.com/flutter/flutter/issues/165683.
A few changes:
- Release candidates are now kDefault, so that reruns still take priority
- Reruns check for tree-redness cause, not just last kBatchSize tasks
- Tip-of-tree runs at kDefaultPriority
diff --git a/app_dart/lib/src/request_handlers/scheduler/backfill_strategy.dart b/app_dart/lib/src/request_handlers/scheduler/backfill_strategy.dart
index 4961b4e..47cd8e3 100644
--- a/app_dart/lib/src/request_handlers/scheduler/backfill_strategy.dart
+++ b/app_dart/lib/src/request_handlers/scheduler/backfill_strategy.dart
@@ -72,8 +72,12 @@
return false;
});
- // Now, create two lists: high priority (recent failure or RC) and regular.
+ // Now, create three lists
+ // 1. Rerun existing failure
final higherPriorityReruns = <TaskRef>[];
+ // 2. Tip of tree
+ final mediumPriorityReruns = <TaskRef>[];
+ // 3. Everything else
final lowerPriorityReruns = <TaskRef>[];
for (final (_, column) in grid.eligibleTasks) {
@@ -83,13 +87,27 @@
continue;
}
- // Determine whether it is high priority or regular priority.
- if (isReleaseCandidateBranch(branchName: grid.getCommit(row).branch) ||
- column
- .getRange(i, min(i + BatchPolicy.kBatchSize + 1, column.length))
- .any((t) => fs.Task.taskFailStatusSet.contains(t.status))) {
+ // Determine relative priority.
+ if (_indexOfTreeRedCause(column) case final index? when index > i) {
+ // ⬜ i
+ // 🟥 index
+ // ^^ Use high priority, this is turning the tree red.
+ //
+ // ⬜ i
+ // 🟩
+ // 🟥 index will return as `null`
+ // ^^ Uses default (or backfill) priority, next commit passed.
higherPriorityReruns.add(row);
+ } else if (isReleaseCandidateBranch(
+ branchName: grid.getCommit(row).branch,
+ )) {
+ // Release candidates should take priority over normal backfill.
+ mediumPriorityReruns.add(row);
+ } else if (row.commitSha == grid.getCommit(column[0]).sha) {
+ // Tip of tree should take priority over normal backfill.
+ mediumPriorityReruns.add(row);
} else {
+ // Everything else.
lowerPriorityReruns.add(row);
}
@@ -98,12 +116,16 @@
}
}
- // Shuffle both sublists.
- higherPriorityReruns.shuffle(_random);
- lowerPriorityReruns.shuffle(_random);
+ // Shuffle each sublist.
+ for (final list in [
+ higherPriorityReruns,
+ mediumPriorityReruns,
+ lowerPriorityReruns,
+ ]) {
+ list.shuffle(_random);
+ }
- // Return both of these lists, concatted.
- // TODO(matanlurey): ToT tasks should be run with kDefaultPriority.
+ // Return each list concatted in order.
return [
...higherPriorityReruns.map(
(t) => grid.createBackfillTask(
@@ -111,6 +133,12 @@
priority: LuciBuildService.kRerunPriority,
),
),
+ ...mediumPriorityReruns.map(
+ (t) => grid.createBackfillTask(
+ t,
+ priority: LuciBuildService.kDefaultPriority,
+ ),
+ ),
...lowerPriorityReruns.map(
(t) => grid.createBackfillTask(
t,
@@ -119,4 +147,21 @@
),
];
}
+
+ static int? _indexOfTreeRedCause(Iterable<TaskRef> tasks) {
+ for (final (i, task) in tasks.indexed) {
+ // Only evaluate completed tasks.
+ if (!fs.Task.finishedStatusValues.contains(task.status)) {
+ continue;
+ }
+
+ // Returns true for failed tasks, and false for successful.
+ if (fs.Task.taskFailStatusSet.contains(task.status)) {
+ return i;
+ } else {
+ return null;
+ }
+ }
+ return null;
+ }
}
diff --git a/app_dart/test/request_handlers/scheduler/backfill_strategy_test.dart b/app_dart/test/request_handlers/scheduler/backfill_strategy_test.dart
index 1f56346..c387105 100644
--- a/app_dart/test/request_handlers/scheduler/backfill_strategy_test.dart
+++ b/app_dart/test/request_handlers/scheduler/backfill_strategy_test.dart
@@ -10,6 +10,7 @@
import 'package:cocoon_service/src/request_handlers/scheduler/backfill_strategy.dart';
import 'package:cocoon_service/src/service/luci_build_service.dart';
import 'package:cocoon_service/src/service/luci_build_service/commit_task_ref.dart';
+import 'package:test/fake.dart';
import 'package:test/test.dart';
import '../../src/utilities/entity_generators.dart';
@@ -20,8 +21,7 @@
group('DefaultBackfillStrategy', () {
// Pick a deterministic seed, because shuffling is involved.
- final random = Random(0);
- final strategy = DefaultBackfillStrategy(random);
+ final strategy = DefaultBackfillStrategy(_FakeRandom());
final commits = [
for (var i = 0; i < 10; i++)
@@ -127,14 +127,54 @@
]);
// dart format on
+ expect(
+ strategy.determineBackfill(grid),
+ unorderedEquals([
+ isBackfillTask
+ .hasCommit(commits[0])
+ .hasTarget(targets[0])
+ .hasPriority(LuciBuildService.kDefaultPriority),
+ isBackfillTask
+ .hasCommit(commits[0])
+ .hasTarget(targets[1])
+ .hasPriority(LuciBuildService.kDefaultPriority),
+ ]),
+ );
+ });
+
+ // INPUT:
+ // 🧑💼 ⬜ 🟩
+ // 🧑💼 ⬜ ⬜
+ //
+ // OUTPUT:
+ // 🧑💼 🟨 🟩
+ // 🧑💼 ⬜ 🟨
+ test('gives lowest priority to non-ToT commits', () {
+ // dart format off
+ grid = BackfillGrid.from([
+ // Linux TASK_0 Linux TASK_1
+ (commits[0], [taskNew (0, 0), taskSucceeded (0, 1)]),
+ (commits[1], [taskNew (1, 0), taskNew (1, 1)]),
+ ], tipOfTreeTargets: [
+ targets[0],
+ targets[1],
+ ]);
+ // dart format on
+
expect(strategy.determineBackfill(grid), [
- isBackfillTask.hasCommit(commits[0]).hasTarget(targets[0]),
- isBackfillTask.hasCommit(commits[0]).hasTarget(targets[1]),
+ isBackfillTask
+ .hasCommit(commits[0])
+ .hasTarget(targets[0])
+ .hasPriority(LuciBuildService.kDefaultPriority),
+ isBackfillTask
+ .hasCommit(commits[1])
+ .hasTarget(targets[1])
+ .hasPriority(LuciBuildService.kBackfillPriority),
]);
});
// INPUT:
- // 🧑💼 ⬜ ⬜ ⬜ kBatchSize = 6
+ // 🧑💼 ⬜ ⬜ ⬜ < 0
// 🧑💼 ⬜ ⬜ ⬜ < 1
// 🧑💼 ⬜ ⬜ ⬜ < 2
// 🧑💼 ⬜ ⬜ ⬜ < 3
@@ -144,7 +184,7 @@
// 🧑💼 🟥 ⬜ ⬜ < 7
//
// OUTPUT:
- // 🧑💼 3️⃣ 1️⃣ 2️⃣ kBatchSize = 6
+ // 🧑💼 3️⃣ 2️⃣ 1️⃣ < 0
// 🧑💼 ⬜ ⬜ ⬜ < 1
// 🧑💼 ⬜ ⬜ ⬜ < 2
// 🧑💼 ⬜ ⬜ ⬜ < 3
@@ -152,7 +192,7 @@
// 🧑💼 ⬜ ⬜ 🟥 < 5
// 🧑💼 ⬜ 🟥 ⬜ < 6
// 🧑💼 🟥 ⬜ ⬜ < 7
- test('places previously failing within kBatchSize as high priority', () {
+ test('places previously failing as high priority ignoring kBatchSize', () {
// dart format off
grid = BackfillGrid.from([
// Linux TASK_0 Linux TASK_1 Linux TASK_2
@@ -171,20 +211,28 @@
]);
// dart format on
- expect(strategy.determineBackfill(grid), [
- isBackfillTask.hasCommit(commits[0]).hasTarget(targets[1]), // 1️⃣
- isBackfillTask.hasCommit(commits[0]).hasTarget(targets[2]), // 2️⃣
- isBackfillTask.hasCommit(commits[0]).hasTarget(targets[0]), // 3️⃣
- ]);
+ expect(
+ strategy.determineBackfill(grid),
+ unorderedEquals([
+ isBackfillTask // 1️⃣
+ .hasCommit(commits[0])
+ .hasTarget(targets[2])
+ .hasPriority(LuciBuildService.kRerunPriority),
+ isBackfillTask // 2️⃣
+ .hasCommit(commits[0])
+ .hasTarget(targets[1])
+ .hasPriority(LuciBuildService.kRerunPriority),
+ isBackfillTask // 3️⃣
+ .hasCommit(commits[0])
+ .hasTarget(targets[0])
+ .hasPriority(LuciBuildService.kRerunPriority),
+ ]),
+ );
});
- test('any commit to a release candidate branch has high priority', () {
+ test('any commit to tip-of-tree has medium priority', () {
final commit = CommitRef.fromFirestore(
- generateFirestoreCommit(
- 1,
- branch: 'flutter-3.32-candidate.0',
- sha: '123',
- ),
+ generateFirestoreCommit(1, sha: '123'),
);
// dart format off
grid = BackfillGrid.from([
@@ -200,8 +248,15 @@
isBackfillTask
.hasCommit(commit)
.hasTarget(targets[0])
- .hasPriority(LuciBuildService.kRerunPriority),
+ .hasPriority(LuciBuildService.kDefaultPriority),
]);
});
});
}
+
+final class _FakeRandom extends Fake implements Random {
+ @override
+ int nextInt(_) {
+ return 0;
+ }
+}
