SALT: Efficient Shard Balancing for Playwright

Table of contents

The problem

Say we have a test suite with known (predicted) test durations, and $N$ CI machines — shards. We want to split the tests across shards so that the whole run finishes as early as possible.

The finish time is determined by the slowest shard. Scheduling theory calls it the makespan: if $\textsf{shard}_i$ is the set of tests assigned to the $i$-th shard, and $\textsf{duration}(t)$ is the predicted duration of a test $t$, then

Minimizing the makespan is the classic multiway number partitioning problem, and it is NP-hard. However, there are heuristics that get close enough for real-world suites.

Naïve approach and its challenges

The typical heuristic is longest-processing-time-first scheduling, or LPT:

1. Sort tests by predicted duration, longest first.
2. Assign each test to the currently least-loaded shard.

The algorithm costs $O(n \log n)$, and it was proved that the makespan it produces is never worse than $\frac{4}{3} - \frac{1}{3N}$ times the optimal makespan. For example, on two shards it equals $\frac{7}{6}$, meaning LPT produces a makespan at most 17% above the best possible split, no matter how adversarial the test durations are.

This is a good starting point, but applying this algorithm to Playwright sharding has a few challenges.

Challenge 1: test groups

Playwright’s native --shard algorithm allocates work per file by default. A file’s tests run in order, and sometimes unintentionally share state: a signed-in session or a file on disk.

When designing a custom balancer, we should follow Playwright balancing rules as closely as possible, since test authors end up relying on them without knowing. Breaking these rules might result in confusing failures caused by test interference.

So instead of balancing tests, we balance test groups — the smallest sets of tests that must stay together on one shard.

Here’s how Playwright defines them:

• with fullyParallel: true, every test is its own test group;
• without it, a whole spec file is one test group;
• a test.describe.serial (or .configure({ mode: 'serial' })) suite is always one atomic group, even inside a fully-parallel project;
• a test.describe.parallel block is shardable per-test, even in a non-parallel project.

Challenge 2: project dependencies

Another important factor is Playwright’s project graph. Projects can declare dependencies — often used for setup work such as preparing a database or a signed-in session — and teardown projects. Both can take significant time. When allocating a test to a shard, its price depends on the tests previously allocated to that shard: a shared dependency only needs to run once there.

Definitions

Before describing the algorithm that can deal with Playwright tests, here’s the required vocabulary (source):

• A test group is an indivisible unit of work, as defined above. Each group knows its work (summed predicted durations of every test) and its dependency closure — every dependency and teardown project it transitively requires.
• A family is the set of all test groups with the same dependency closure.
• For each family $F$, we define $\textsf{setup}(F)$ — the combined price of every project in $F$‘s dependency closure — and $\textsf{work}(F)$ — the combined price of all of $F$‘s test groups.
• For each shard $i$, we’ll write $\textsf{load}_i$ for the work already allocated to that shard.
• $\textsf{missing}_i(F)$ is the part of family $F$‘s setup that has not already run on shard $i$. A fresh shard has $\textsf{missing}_i(F) = \textsf{setup}(F)$; a shard that already runs the whole dependency closure has $\textsf{missing}_i(F) = 0$.
• For any set of shards $A$, $\textsf{extraSetup}(A,F) = \sum_{i \in A} \textsf{missing}_i(F)$ is their combined missing setup for family $F$.
• At any point in the algorithm, $\textsf{total}$ is the sum of all current shard loads, all not-yet-allocated family work, and one copy of every required dependency that has not run on any shard yet.
• $\textsf{unseenSetup}(F)$ is the combined price of the dependencies in family $F$‘s closure that have not run on any current shard.

Algorithm

We call the algorithm SALT — Setup-Aware LPT. It is a heuristic built around one strategic idea: allocate families with the heaviest setup first, while there is still freedom to place them well, and let the light, zero-setup families pad the remainders at the end.

So we sort the families descending by their setup price, and then place each family in three steps:

1. decide $K$ — how many shards the family should span;
2. select $K$ host shards one at a time;
3. run plain LPT to spread the family’s test groups across those $K$ shards.

All three steps make their choices in the same way: estimate the makespan each option would lead to, and pick the option with the lowest estimate.

Step 1: how many shards?

We have a family $F$ and want to choose a promising number $K$ of shards to spread it across. Spanning more shards divides the family’s work but multiplies its setup cost. The candidates range from $1$ to $\min(N, |F|)$, where $|F|$ is the number of test groups in the family: a family cannot occupy more shards than it has indivisible groups.

For every candidate value of $K$, we will estimate a makespan lower bound and then pick the $K$ that minimizes it.

For a given family $F$ and candidate $K$, consider the following two different makespan lower bounds:

1. A local lower bound. Some shard will carry at least a $1/K$ slice of this family plus its setup — the makespan can’t beat that:

2. A global lower bound. The makespan can’t beat perfect balancing of everything. Dividing $\textsf{total}$ perfectly across $N$ shards gives us this bound — but first we have to account for the extra setup that spreading $F$ across $K$ hosts may require.

   The price is shard-dependent. Sort $\textsf{missing}_i(F)$ from lowest to highest:

   $$\textsf{missing}_{(1)}(F) \le \textsf{missing}_{(2)}(F) \le \cdots \le \textsf{missing}_{(N)}(F)$$

   If $F$ must span $K$ shards, the cheapest possible hosts are the first $K$ in that ordering. Call this optimistic host set $M_K$. Its combined missing setup is $\textsf{extraSetup}(M_K,F)$.

   $\textsf{total}$ already reserves one copy of $\textsf{unseenSetup}(F)$. Those dependencies also appear in every $\textsf{missing}_i(F)$, so the first reserved copy would be counted twice unless we subtract it:

   $$\textsf{makespan} \ge \frac{\textsf{total} + \textsf{extraSetup}(M_K,F) - \textsf{unseenSetup}(F)}{N}$$

Putting the two estimates together, side by side:

Notice that the local bound falls as $K$ grows, while the global one rises. The best estimate is somewhere in-between: we try every admissible $K$ and keep the one with the lowest estimate.

Step 2: which shards?

At this point, family $F$ and its span $K$ are fixed. What remains is to select the exact $K$ host shards.

We maintain a running set $S$ of already-selected shards. It starts empty. While $|S| < K$, we score every shard $i$ outside $S$, add the lowest-scoring candidate to $S$, and repeat.

In every scoring round, the family $F$, the span $K$, and the already-selected set $S$ are fixed; what varies is the candidate shard $i$. We will estimate a makespan projection and then pick the $i$ that minimizes it.

For a given candidate shard $i$, consider the following two makespan estimates:

1. A load-aware local projection. The family’s work will be spread across $K$ selected hosts, so $\textsf{work}(F)/K$ is the average share. We provisionally give that share to candidate $i$ and project its finishing load:

   $$\widehat{\textsf{makespan}}^{\,\textsf{local}}_i(F) = \textsf{load}_i + \textsf{missing}_i(F) + \frac{\textsf{work}(F)}{K}$$
   Important

   The hat over $\textsf{makespan}$ marks this as an estimate, not a genuine bound. Some selected host must receive at least the average share, but there is no guarantee it is candidate $i$ — it may receive less. We still use the average because it scales the backpressure with the family’s size: a large family should be more reluctant than a small one to choose an already-loaded shard.

2. A global lower bound. If we add candidate $i$ to $S$, we still need

   $$K - |S| - 1$$

   more hosts. Consider all shards outside $S$ other than $i$, order them by $\textsf{missing}_j(F)$, and take as many as we still need. Call this set $M$: the optimistic co-hosts for candidate $i$. It is optimistic because it ignores their current loads and picks only the cheapest possible missing setup.

   The global lower bound now has a direct interpretation: the already-selected hosts, candidate $i$, and its optimistic co-hosts together form the complete hypothetical host set $S \cup \{i\} \cup M$. Start with $\textsf{total}$, add its combined missing setup, and — as in Step 1 — subtract $\textsf{unseenSetup}(F)$ because $\textsf{total}$ already contains the first unseen copy:

   $$\textsf{makespan} \ge \frac{ \textsf{total} + \textsf{extraSetup}(S \cup \{i\} \cup M,\ F) - \textsf{unseenSetup}(F) }{N}$$

Putting the two estimates together, candidate $i$‘s score is the larger of the two:

After every candidate outside $S$ is scored, the one with the lowest estimated makespan joins $S$. We then score the remaining candidates again with the new $S$, and repeat until $|S| = K$.

Step 3: LPT, at last

Within the selected shards, the family’s test groups are placed with plain LPT: heaviest test group first, least-loaded shard wins. The only refinement is what “load” means when the shards are compared.

For every test group $g$, each candidate shard bids the price of accepting it:

and $g$ goes to the lowest bidder.

Every other shard’s load stays fixed during this choice, so minimizing the winning bid also minimizes the immediate makespan.

The $\textsf{missing}_i(F)$ term matters only for a shard’s first test group of this family: such a shard has to bring the family’s setup along, so its bid is higher. Once that first test group lands, the setup price folds into the shard’s load and the shard’s dependency set covers $F$‘s closure, so $\textsf{missing}_i(F)$ drops to zero: every following test group of this family is charged its own work only.

Implementation and runtime complexity

SALT is implemented in @flakiness/playwright:

• The source code is a few hundred well-commented lines.
• We have a thorough test suite that pins down every behavior described in this post, and doubles as a catalog of examples.

Let’s discuss the runtime of the three balancing steps in this implementation, after tests have been grouped into families. Let $T$ be the number of tests, $P$ the number of projects, and $N$ the number of shards.

• Steps 1 and 2 are independent of $T$. They operate only on families, dependency closures, and shards. In this implementation they cost $O(P^3 + NP^2 + PN^2 \log N)$: cubic terms in the two small inputs, plus the logarithmic cost of sorting shard candidates.
• Step 3 is the only test-bound step. Sorting the test groups and placing each one costs $O(T \log T + TN(P + \log N))$ in the current straightforward implementation.

For the input sizes this implementation targets, $N$ and $P$ are very small compared with $T$. The terms from Steps 1 and 2 do not include $T$ and are negligible at that scale, so the practical runtime estimate is governed by the Step 3 terms:

Example

Let’s make this concrete with a tiny test suite. Each test declares its (predicted) duration right in the title:

import { defineConfig } from "@playwright/test";

export default defineConfig({
  fullyParallel: true,
  projects: [
    { name: "setup", testMatch: "setup.spec.ts" },
    { name: "e2e", testMatch: "e2e.spec.ts", dependencies: ["setup"] },
    { name: "unit", testMatch: "unit.spec.ts" },
  ],
});

import { test } from "@playwright/test";

test("seed the database (30s)", async () => {});

import { test } from "@playwright/test";

test.describe.serial("checkout", () => {
  test("add to cart (15s)", async () => {});
  test("pay (5s)", async () => {});
});

test("search (10s)", async () => {});
test("profile (10s)", async () => {});

import { test } from "@playwright/test";

for (let i = 1; i <= 6; ++i) test(`unit ${i} (5s)`, async () => {});

First, the test groups. The serial checkout suite is indivisible and moves as one 20-second unit; every other test is free to travel on its own:

Now, the families: bucketing the test groups by their dependency closure yields two of them.

Time to run the algorithm — let’s balance this suite onto $N = 2$ shards.

$F_1$ goes first: it has the heaviest setup. At this point both shards are fresh, so $\textsf{missing}_{(1)}(F_1) = \textsf{missing}_{(2)}(F_1) = 30$ and $\textsf{unseenSetup}(F_1) = 30$. Step 1 tries both candidate spans, with $\textsf{total} = 100$ (all the work, $40 + 30$, plus the setup project counted once):

• $K = 1$: $\textsf{extraSetup}(M_1,F_1) = 30$, so $\operatorname{\textsf{max}}(30 + 40,\ (100 + 30 - 30) / 2) = 70$;
• $K = 2$: $\textsf{extraSetup}(M_2,F_1) = 60$, so $\operatorname{\textsf{max}}(30 + 20,\ (100 + 60 - 30) / 2) = 65$.

$K = 2$ wins: the estimates claim that paying the 30-second setup on both shards is worth it. Step 2 is trivial here — with $K = N = 2$ both are selected anyway. Step 3 places the test groups with LPT: checkout (20s) lands on shard 1, which now also owes the setup — 50s total; search and profile (10s each) fill shard 2 to the same $30 + 20 = 50\text{s}$.

$F_2$ goes next, and its Step 1 is a perfect tie: both $K = 1$ and $K = 2$ estimate a 65-second makespan. Ties resolve toward the wider span, so the six unit tests pad both shards evenly, 15 seconds each.

The final plan: 65 seconds on each shard.

The algorithm chose to run the setup twice, because splitting $F_1$‘s work still won. And this is actually optimal: any plan that keeps $F_1$ on a single shard loads it with $30 + 40 = 70\text{s}$, while any plan that splits $F_1$ pays for the second setup — $130\text{s}$ of total work, or 65s per shard at the very best.

Wrapping up

SALT has already proved itself: it is used in the real world by WordPress’s Gutenberg project to cut its test run from 35 to 23 minutes.

However, SALT is a heuristic, and its makespan estimates should be taken with a grain of salt :) Heuristics are best judged by their counterexamples, so if your suite balances worse than you’d expect — we’d love to see it: file an issue.

Happy sharding!

Flakiness.io Team