aioff.
中文
Product design
PRODUCT DESIGN·10 min

Supabase: try a schema change before bringing it to production

Supabase provides a Postgres-based application backend with APIs, authentication and file storage. Branches let teams try schema changes in a separate environment, test their application and review migrations before merging.

Break down the problem and try your own design and implementation first. Then explore the reasoning to check states, edge cases, trade-offs, and ways to test your approach. The guide offers a reasoning path, not a complete implementation.

01
CODE EXERCISEAdvanced

Which deployment steps are ready, waiting or blocked?

Scenario

Deploying a preview environment requires a health check before a schema migration, followed by loading test records. Design a pure in-memory dependency analyzer that tells the interface which pending steps are ready, waiting or blocked by failure. It executes no migrations, sends no network requests and performs no retries. This is an invented protocol, not Supabase’s internal scheduler.

Input and rules

  1. steps contains at most 100,000 entries. Each is a non-null object with a unique nonempty string id and state equal to pending, running, succeeded or failed. An empty array is valid. Inputs are read-only; validate only the listed fields. Let L be the total character length of all ID occurrences.
  2. dependencies contains at most 300,000 entries. Each is a non-null object with nonempty strings before and after: before must succeed before after can start. Both endpoints must exist. Ignore repeated directed edges rather than counting them twice. A self-loop or any directed cycle makes the entire input invalid.
  3. This is a fixed execution snapshot with no retries. A running, succeeded or failed step has already started, so all its direct prerequisites must be succeeded; otherwise the snapshot is invalid. States do not change during analysis.
  4. For every pending step, any failed ancestor makes it blocked. Otherwise it is ready if all direct prerequisites have succeeded, including the case of no prerequisites; all other cases are waiting. failed is an execution state of a step, while blocked describes a step that has not started because an upstream step failed.
  5. Output every pending step’s id and classification in steps input order. Omit already-started steps. Do not choose one failing ancestor or list all ancestors. Any structural, field or snapshot error returns a located error and no partial classification. You need not enumerate all errors, but must distinguish invalid input from valid waiting.

Small example

The step order is A health check succeeded; B migration failed; C test records pending; D function check pending; E configuration check pending; F independent check pending. Dependencies are A→B, B→C, B→D and A→E. Classify C, D, E and F.

Try these changes independently: (a) change B to running; (b) add C→A; (c) change C to succeeded; (d) deliver A→B a second time. Explain which still allow valid classifications and which must be rejected.

Deliverables

Describe validation, deduplication, cycle detection, failure propagation and original-order output. Avoid traversing all ancestors separately for every step, and avoid deep recursive calls that can overflow the call stack. Analyze time and space in terms of n steps, m input edges and L. Give at least four invariants. You may discuss JS Map or Rust collections, but provide no complete implementation or line-by-line pseudocode.

Explore the reasoning
  1. Establish identities and dependencies. Retain input positions in an ID index, validate fields and endpoints, then deduplicate edges with structured nested indexes rather than collision-prone string concatenation. An empty graph is valid; an invalid endpoint must not silently create a node.
  2. Detect cycles with iterative topological traversal. Count indegrees after deduplication and process zero-indegree nodes in a queue. Processing fewer than n nodes signals a cycle. Verify the whole graph before returning classifications, rather than treating a reachable fragment as a successful result.
  3. Check prerequisites of already-started steps. Every running, succeeded or failed step must have all direct prerequisites succeeded. This exercise excludes retries and in-snapshot changes, so a prerequisite failing later cannot explain inconsistent input.
  4. Propagate a single upstream-failure flag. Combine upstream failure with the node’s own failed state before passing the flag to successors. Do not store full ancestor sets. A pending step with an upstream failure is blocked; otherwise use direct-prerequisite success to distinguish ready and waiting. Collect results in original step order.
  5. Trace outcomes and cost. The main example gives C/D blocked and E/F ready. In (a), C/D wait and E/F remain ready. In (b), reject the cycle. In (c), C succeeded while B failed, so the snapshot is invalid. In (d), the repeated edge changes nothing. Input reordering changes output order only; duplicate edges preserve classifications; blocking propagates across multiple levels; errors yield no partial output. Average hashing gives O(n+m) collection/graph operations, with L character work accounted for separately. Indexes, deduplicated edges, queue and output fit O(n+m+L) space. Do not copy each node’s entire ancestor set.