Skip to content

Wide Fan-Outs Kept in Check, Inputs Every Database Stores, Shards That Fail Alone

Latest

Choose a tag to compare

@bw19 bw19 released this 19 Nov 22:29

A wide forEach no longer stalls at its fan-in or takes the replica's workers with it: arrivals at one fan-in land
together, a fan-out's claims are paced to what its fan-in absorbs so the rest of the shard keeps its workers, a branch
waiting there holds no payload, and on PostgreSQL the branches are created in far fewer statements. On SQL Server,
MySQL and MariaDB, terminating or cancelling a wide fan-out and archiving a large tree no longer lock the shard's
other flows. Crash recovery runs on each shard's own clock, and new flows go around a shard the replica cannot read.
Inputs are held to what every database can store: text PostgreSQL refuses is refused everywhere, graph names, task
names and URLs are 1 to 512 printable ASCII characters, and a fairness weight is a whole number. On PostgreSQL, keys,
names and URLs take the "C" collation, and the engine reads no environment variables. Upgrading an existing
database needs schema changes by hand
(Breaking), the carrier's subgraphError is a JSON object, and
dwarf_operation_seconds is renamed.

Fixed

  • An API call made as Startup finished could read the engine's metrics half-built. Startup now builds them
    before it marks the engine started.

  • A call in flight when Shutdown ran could run on past it. An operation already admitted - a Create waiting on
    the host's LoadGraph, a Run, a list - went on against shards being closed, where a flow reads as not found, and
    one still running across a restart read the state the next Startup replaces. Shutdown now cancels every call it
    admitted before it stops anything else and waits for each to return; such a call returns a 503, Poll and
    ShardInfo included. A call cancelled while writing may still have taken effect, as one whose caller gives up may: a
    Create can have made its flow. A host's LoadGraph that ignores its context delays Shutdown until it returns,
    and a Shutdown called from inside a call the engine made to the host waits for that call, forever.

  • Startup and Shutdown called at once could overlap. Each now waits for the one under way: a Shutdown called
    during a Startup stops the engine that Startup brings up, a Startup called during a Shutdown starts once the
    engine has stopped, and a second Shutdown returns once the engine has stopped.

  • A wide forEach no longer stalls at its fan-in. When many branches of one fan-out finished together, their
    arrivals at the fan-in were recorded one transaction at a time, so a fan-out of hundreds of thousands of branches
    queued its arrivals for minutes after its branches were done, and a branch waiting its turn renewed its lease every
    15 seconds whatever time it had left - writes to the very database the queue was waiting for. Arrivals queued at
    one fan-in are now recorded together, up to 256 in a transaction of a few statements on every database, and a
    waiting branch renews its lease only when 15 seconds are left, then every 45 seconds, so one that joins within its
    time budget renews nothing.

  • Crash recovery on one shard no longer waits for another. A replica ran the recovery of all the shards it
    dispatches in one loop, each pass waiting for its slowest shard and the next pass waiting for the last, so one slow
    pass - a scan of a large shard's open flows - delayed every shard's reset of the steps whose worker's lease ran out,
    and with it the time a crashed worker's steps take to run again. Recovery now runs as three background jobs of each
    shard, on every replica that dispatches it, each on its own clock: lease_recovery and orphan_repair (replaying a
    step whose transition was lost to a crash) every minute, and wedge_sweep (the subgraph hand-offs counted by
    dwarf_steps_unwedged and the stranded flows counted by dwarf_flows_orphaned) every five minutes, each pass
    starting an interval after the last one ended. dwarf_janitor_progress_age_seconds reports them under those job
    names. A pass that runs to its end is progress, so a healthy job's age stays under its interval plus the length of a
    pass; one growing past that is blocked or failing, and the logs say why.

  • A failed, cancelled or terminated fan-out keeps what its lost branch stored. A fan-out whose branches never all
    converged folded into its final state only the branches that completed, so what a lost branch had stored vanished:
    the writes of an attempt before a Retry, of a run a Cancel let finish, or of the run that interrupted. Every
    branch's stored changes are now folded, whatever its status, as a lost step outside a fan-out already kept them. A
    run that fails stores none of its writes, as before, and a fan-out that converges is unchanged.

  • SQLite: a prompt asked again after a Resume reaches Snapshot. After a Resume, a step that retried and
    interrupted again, or a caller whose subgraph child interrupted a second time, had its new prompt dropped, so the
    root's Snapshot showed an empty interrupt payload.

  • SQL Server, MySQL and MariaDB: archiving a large tree no longer holds up the shard's other flows. A closed tree
    larger than a batch (4,000 rows) and smaller than the staging threshold (262,144 rows) was moved to the archive in one
    transaction, and on these databases that transaction locked the live tables: SQL Server escalated its row locks to a
    lock on each whole table, and MySQL and MariaDB, when the tree was a large share of the table, read and locked all of
    it. Every Create and every step on the shard waited until the move committed. On these three databases a tree
    larger than a batch is now archived in stages, a batch at a time, as a tree past the staging threshold already was;
    PostgreSQL and SQLite move it whole as before.

  • SQL Server, MySQL and MariaDB: terminating or cancelling a wide fan-out no longer holds up the shard's other
    flows.
    A forEach keeps its branches in one flow, and Terminate, a flow's expiration and Cancel updated all
    of a flow's open steps in one statement. On SQL Server, past about 5,000 open steps, that statement locked the
    whole steps table: every step on the shard waited until the Terminate committed, or until the Cancel finished.
    On MySQL and MariaDB at the default REPEATABLE READ, with the flow a large share of the shard's steps, the statements
    locked other flows' steps as well, and every step completing on the shard waited for the Terminate. SQL Server
    now updates the steps 2,000 at a time, Terminate still in one transaction, and MySQL and MariaDB reach them
    through the index on their flow. At REPEATABLE READ the index still locks the gap after the flow's last step until the
    Terminate commits, so while it is the shard's newest flow, a new flow's first step waits; READ-COMMITTED, the
    recommended level, avoids it.

  • SQL Server: replaying a wide fan-out's arrivals, and retrying a call to a wide subgraph, no longer lock the
    steps table.
    The repair that replays the steps a dead replica left queued at a fan-in, and a flow.Retry of a
    subgraph caller, which deletes the child it called, wrote all of one flow's steps in one statement, so past about
    5,000 steps the whole steps table was locked until the transaction committed. They now write the steps 2,000 at a
    time, as Terminate does; on MySQL and MariaDB the repair reaches them through their flow's index. A retry whose
    delete of the old child fails is now written again, rather than leaving the child behind.

  • SQL Server: a write no longer waits on other flows' rows, and two replicas' janitors no longer deadlock. While
    the live tables were small, SQL Server read them by scanning for an update or delete that named its rows by a list
    of ids or by their flow, and such a scan waits on every row another transaction holds, the ones it does not change
    included, READ_COMMITTED_SNAPSHOT or not. A fan-in arrival, Terminate, Cancel, Resume, an interrupt, lease
    recovery or Purge then waited on unrelated flows' work in flight. When two replicas dispatched a shard, their
    janitors' archive and delete batches each held their own trees and scanned past the other's, deadlocked, and lost
    every retry, so a batch failed and its trees waited in the live tables for a later sweep. These statements now
    reach their rows through an index on SQL Server, and lock only the rows they name.

  • MySQL and MariaDB: a statement still running after 8 seconds no longer fails. sequel set a read and a write
    timeout of 8 seconds, and a connect timeout of 4, on every MySQL and MariaDB connection, whatever the data source
    name said, so a statement whose reply took longer - a migration on a busy server, a wait for a row lock - failed with
    invalid connection. Connections now keep the driver's own timeouts, none by default, and whatever the data source
    name sets: give it timeout, readTimeout or writeTimeout to bound them.

  • Background readings ignore a step of the wall clock. dwarf_janitor_progress_age_seconds,
    dwarf_peer_blind_seconds and the dispatch cycle's work time are measured on the monotonic clock, so a host whose
    clock is set back or forward no longer reports a false age or a stalled job.

  • A graph can no longer send one task to another task's URL. Two task names that differed only in invalid
    UTF-8 passed Validate but became one name when the graph was stored, so a flow could dispatch a task to the URL
    bound to the other. Such a graph is now refused, under the name rule in Breaking.

  • WithLinks can no longer add a link to a rendered diagram. The parameter name given to
    GraphRenderer.WithLinks or FlowRenderer.WithLinks went into each click directive as it was, so a name holding
    a quote and a line break added a click line of its own, pointing anywhere: a risk for a page that takes the name
    from a request. The name is now held to the rule in Breaking, and FlowRenderer query-escapes the step key in
    each link.

  • An error that cannot be stored as it is still reaches its onError handler. An error whose message or
    properties held a NUL made the handler's onErr impossible to store on PostgreSQL, and one too large for a column
    did the same on every database, so the step failed once its write was refused and the handler never ran. When the
    error as a whole cannot be stored, onErr now keeps its message and status code and drops its properties, as
    flow.Subgraph already did with a child's error. The message is the one a failed flow reports: control characters
    other than a newline or a tab are replaced with U+FFFD, and a message over 16 KiB is cut.

Changed

  • A migration file of two or more statements applies whole on PostgreSQL, SQL Server and SQLite (sequel
    v1.20.0): in one transaction with its completion record, so a failure leaves nothing applied and the next start
    runs the file again. A file of one statement, and every file on MySQL and MariaDB, still runs statement by
    statement, and the repair for one whose statement applied without its completion being recorded is unchanged. See
    When a Migration Fails.

  • The engine reads no environment variables. It read DWARF_ARCHIVE_DAY, DWARF_ARCHIVE_GRACE,
    DWARF_STAGE_ROWS and DWARF_STAGE_BYTES at every Startup, production included; they were settings for tests
    and benchmarks, and set in a production environment they changed the archive's day length, its grace or the
    staging thresholds. They now have no effect. The variables the test suites and the benchmark read are renamed
    DWARF_TESTING_*, beside sequel's SEQUEL_TESTING_DSN: DWARF_TEST_LOG_LEVEL is DWARF_TESTING_LOG_LEVEL.

  • The engine registers a sequel virtual function, SEEK_FROM. sequel's virtual functions are shared by
    everything in the process, so a host that uses sequel must not register one of its own under that name: it would
    replace the engine's.

  • New flows go around a shard the replica cannot read. A Create placed on a shard whose database was down or
    not answering failed or waited out its caller's deadline, so with one of two shards down about half of all Create
    calls failed. A replica now leaves a shard out of new-flow placement once it has gone over half a second without
    reading that shard's peer registry, until the shard answers again, so only the calls placed on it in that first
    half-second fail; a replica that can read no shard places over all of them. The new counter
    dwarf_placement_skipped{shard} counts the flows placed elsewhere. A shard slow enough that a replica's reads of it
    run late is left out for the moments they do, which shows as short, frequent bursts in the counter. See
    One Shard Is Slow or Unreachable.

  • Large trees are archived two at a time on each replica. A shard's janitor runs two large-tree archiving jobs,
    large_archiving_1 and large_archiving_2 (one on SQLite), as it does two of each fast job; each copies the trees of
    its share, so a single replica copies two at once and keeps a shard's archiving going alone.
    dwarf_archive_oldest_attempt_seconds gains a job label: each job reports the oldest unpublished copy of its
    share, so aggregate with max. dwarf_archive_failing_seconds and dwarf_janitor_progress_age_seconds report the
    jobs under their new names.

  • dwarf_ingress_operations{op, status_code} (new) counts each API call once, by how it ended: 200, else the
    status code of the error the caller got, with 499 for a caller that cancelled and 408 for one whose deadline
    passed. A call that fails before reaching the database, such as a bad request or a failed graph load, counts too.
    Await and Run return a 408 when their wait runs out, so split by op before alerting on errors.

  • A wide fan-out's claims are paced to its fan-in. While half of a replica's candidate cache worth of its
    workers wait at one cohort's fan-in, the cache holds back that cohort's other steps, so the rest of the shard's
    work keeps its workers. idx_dwarf_steps_selection, and on MySQL, MariaDB and SQLite idx_dwarf_steps_due,
    carry lineage_id for it, so dispatch's fetch stays index-only; a database made by v0.15.0 needs the indexes
    rebuilt (below).

  • A step holds less memory while its task runs and while it waits at a fan-in. A dispatch held its step's input
    twice while the task ran - the stored columns beside their decoded copy - and kept its input and output after
    nothing read them. It now keeps the decoded copy alone during the task, lets go of the input once its successors'
    states are made, and holds no payload while it waits at a fan-in, so the workers queued behind a wide fan-out's
    fan-in hold little more than their stacks.

  • PostgreSQL: a wide fan-out is created in far fewer statements. A transition's successors - the branches of a
    forEach or a static fan-out - went in 64 to a statement; on PostgreSQL they now go in up to 4,096 to a statement,
    as arrays, so creating a wide fan-out takes a fraction of the round trips and holds its flow's lock for less time.
    A single successor is inserted as before, and the other databases keep their statements.

  • PostgreSQL: keys, names, URLs and statuses are stored in the "C" collation. They took the database's
    collation, on most servers a locale of the operating system's C library such as en_US.UTF-8, whose order of -,
    _, . and / can change when that library is updated; an index on such a column built before the update is then
    out of order until it is rebuilt. "C" orders by bytes, never changes, and matches the binary collations the other
    databases already use. Error messages, cancel reasons and final states keep the database's collation, so
    Query.Search stays case-insensitive beyond ASCII. A database made by v0.15.0 gets it from the schema change below.

Breaking

  • dwarf_operation_seconds is renamed dwarf_shard_operation_seconds, beside the new per-call counter.
    Dashboards and alerts on the old name stop matching; rename them.

  • Text PostgreSQL cannot store is refused on every database. A NUL in a string, and invalid UTF-8 or a \u
    escape of an unpaired surrogate in JSON passed through as given (a json.RawMessage, or a remote host's changes),
    are now refused before they are written, the error naming the field that holds them. Create and Run (the
    initial state or the baggage), Resume, Continue and Fork return a 400, and a task whose changes or interrupt
    payload hold such text fails its step at once, without taking its onError transition. A list or Purge text
    filter holding invalid UTF-8 or a NUL is a 400 too. PostgreSQL always refused this text, but only at the write:
    a step failed after its write retries ran out, counted in dwarf_steps_write_failed, and an operation returned
    the database's error. SQLite, MySQL, MariaDB and SQL Server stored some or all of it, so a flow that ran on one of
    them could fail on PostgreSQL. Carry binary data base64-encoded.

    • A flow already running on SQLite, MySQL, MariaDB or SQL Server whose state holds such text can fail at a
      later step
      , when the engine next writes that text.
  • Graph names, task names and URLs are 1 to 512 printable ASCII characters, neither beginning nor ending with a
    space.
    workflow.IsValidName and workflow.IsValidURL state the rule. Validate, and so Create, Run and a
    subgraph spawn, refuses a graph whose name, or any of whose task names or task URLs, breaks it: a character
    outside printable ASCII (a space through ~) - a control character, invalid UTF-8, an accented letter or an
    emoji -, a task URL with a leading or trailing space, or a name or URL longer than 512 characters, the width of
    the columns that store it. Two such names could look alike and differ, two that differed in invalid UTF-8 became
    one when the graph was stored, and a longer one failed its write, for a task after the entry point in the middle
    of the flow. Create, Run and flow.Subgraph refuse a workflow URL outside the rule with a 400, and a
    flow.Goto to a target outside it fails the step, as a target with no goto transition does. A URL
    percent-encodes any other character. A when expression may hold any text but invalid UTF-8 or a NUL.

    • A flow created from such a graph before the upgrade keeps running, and so do its forks and continuations,
      but a Goto to one of its task names outside the rule fails the step. A subgraph spawn of such a graph fails,
      and flow.Subgraph returns the 400.
  • WithLinks takes a plain parameter name. GraphRenderer.WithLinks and FlowRenderer.WithLinks take a name
    of at most 32 characters: an ASCII letter or underscore, then ASCII letters, digits, underscores or hyphens. Any
    other name renders the diagram without links.

  • A fairness weight is a whole number from 1 to 1,000,000. FlowOptions.FairnessWeight is an int, and
    Create and Run refuse a negative weight or one above 1,000,000 with a 400. 0 still means the default of 1. A
    weight sets a key's share by its ratio to the other keys' weights, so a share smaller than the default's is set by
    raising the other keys' weights. In JSON, fairnessWeight is an integer: a fraction no longer decodes, and neither
    does a whole number written with a decimal point or an exponent (4.0, 1e3), which some encoders write for a
    float-typed value.

  • The carrier's subgraphError is a JSON object. A carrier that delivers a subgraph's error to its caller held
    it as a string containing the error's JSON; it now holds that object itself: error (the message), statusCode,
    trace when there is one, and the error's properties as further keys, without a stack. The carrier's v stays 1.
    A task server that encodes and decodes the carrier with the workflow package needs no change, but one on an
    earlier dwarf than its engine, or a later one, fails to decode such a carrier: roll task servers and the engine out
    together, as for every carrier change. A task server in another language that reads subgraphError reads an
    object. RawFlow.SetSubgraphResolution takes the child's error as an error rather than its JSON text.

  • An existing database needs a schema change by hand. Migrations are edited in place before v1.0, so a database
    made by v0.15.0 does not pick this up, and Startup does not check for it; a new database gets it. The
    fairness_weight column of dwarf_flows, dwarf_steps and every archive day's dwarf_flows_archive_<n> and
    dwarf_steps_archive_<n> becomes an integer. Apply it with every replica stopped, before starting v0.16.0.
    Without it, a stored weight that is fractional, or 1,000,000 or more, cannot be read: the band scan of its shard
    fails, so that shard dispatches nothing while the step is due; and dispatching its flow's steps, spawning its
    subgraphs, forking it and continuing it fail, live or archived. A v0.16.0 flow created at weight 1,000,000 is such
    a weight. The same window rebuilds idx_dwarf_steps_selection with lineage_id, and on MySQL and MariaDB
    idx_dwarf_steps_due too; without them the engine runs, but dispatch reads the table for each candidate. On PostgreSQL it also gives the identity text columns (keys, names,
    URLs, statuses) the "C" collation; without it the engine runs as before (Changed).

    • Fractional weights are rounded to the nearest whole number, and any below 1 become 1. A deployment that used
      fractions for a smaller share should first scale every stored weight by one factor (for example
      UPDATE dwarf_flows SET fairness_weight = fairness_weight * 10, and the same on dwarf_steps), or the rounding
      gives those keys the default share. Scale the weights its callers pass the same way.
    • Every statement below rewrites its table. Plan the window by the size of dwarf_steps.
    • PostgreSQL. One statement a table changes the weight and the collations, so each table and its indexes are
      rebuilt once.
      -- the selection index, rebuilt with lineage_id at the end:
      DROP INDEX idx_dwarf_steps_selection;
      ALTER TABLE dwarf_flows ALTER COLUMN fairness_weight TYPE INT USING GREATEST(1, ROUND(fairness_weight))::INT,
          ALTER COLUMN flow_token TYPE VARCHAR(16) COLLATE "C", ALTER COLUMN workflow_url TYPE VARCHAR(512) COLLATE "C",
          ALTER COLUMN workflow_name TYPE VARCHAR(512) COLLATE "C", ALTER COLUMN graph_hash TYPE VARCHAR(64) COLLATE "C",
          ALTER COLUMN status TYPE VARCHAR(16) COLLATE "C", ALTER COLUMN trace_parent TYPE VARCHAR(128) COLLATE "C",
          ALTER COLUMN fairness_key TYPE VARCHAR(256) COLLATE "C";
      ALTER TABLE dwarf_steps ALTER COLUMN fairness_weight TYPE INT USING GREATEST(1, ROUND(fairness_weight))::INT,
          ALTER COLUMN step_token TYPE VARCHAR(16) COLLATE "C", ALTER COLUMN task_name TYPE VARCHAR(512) COLLATE "C",
          ALTER COLUMN task_url TYPE VARCHAR(512) COLLATE "C", ALTER COLUMN status TYPE VARCHAR(16) COLLATE "C",
          ALTER COLUMN fairness_key TYPE VARCHAR(256) COLLATE "C", ALTER COLUMN advance_goto TYPE VARCHAR(512) COLLATE "C";
      -- every archive day <n>: the dwarf_flows statement on dwarf_flows_archive_<n>, the dwarf_steps one on dwarf_steps_archive_<n>
      CREATE INDEX idx_dwarf_steps_selection ON dwarf_steps (status, parked, priority, fairness_key, created_at, step_id) INCLUDE (not_before, lease_expires, fairness_weight, lineage_id) WHERE status IN ('pending', 'running');
    • MySQL and MariaDB. The indexes that carry the column are rebuilt with it.
      UPDATE dwarf_flows SET fairness_weight = GREATEST(1, ROUND(fairness_weight));
      ALTER TABLE dwarf_flows MODIFY fairness_weight INT NOT NULL DEFAULT 1;
      UPDATE dwarf_steps SET fairness_weight = GREATEST(1, ROUND(fairness_weight));
      ALTER TABLE dwarf_steps MODIFY fairness_weight INT NOT NULL DEFAULT 1;
      -- every archive day <n>, the same two statements for each of dwarf_flows_archive_<n> and dwarf_steps_archive_<n>
      -- the selection and due indexes, with lineage_id:
      ALTER TABLE dwarf_steps DROP INDEX idx_dwarf_steps_selection,
          ADD INDEX idx_dwarf_steps_selection (status, parked, priority, fairness_key, created_at, step_id, not_before, lease_expires, fairness_weight, lineage_id),
          DROP INDEX idx_dwarf_steps_due,
          ADD INDEX idx_dwarf_steps_due (status, parked, priority, not_before, fairness_key, created_at, step_id, lease_expires, fairness_weight, lineage_id);
    • SQL Server. A column's type cannot change while an index or its default refers to it, so the default is
      dropped and re-added around the change, and on dwarf_steps the two indexes that carry it as well; the selection index comes back with lineage_id. For each of
      dwarf_flows, dwarf_steps, dwarf_flows_archive_<n> and dwarf_steps_archive_<n>, as a batch of its own
      (shown for dwarf_steps):
      UPDATE dwarf_steps SET fairness_weight = CASE WHEN ROUND(fairness_weight, 0) < 1 THEN 1 ELSE ROUND(fairness_weight, 0) END;
      DECLARE @df sysname = (SELECT name FROM sys.default_constraints
          WHERE parent_object_id = OBJECT_ID(N'dwarf_steps') AND COL_NAME(parent_object_id, parent_column_id) = N'fairness_weight');
      EXEC(N'ALTER TABLE dwarf_steps DROP CONSTRAINT ' + QUOTENAME(@df));
      -- dwarf_steps only:
      DROP INDEX idx_dwarf_steps_selection ON dwarf_steps;
      DROP INDEX idx_dwarf_steps_due ON dwarf_steps;
      ALTER TABLE dwarf_steps ALTER COLUMN fairness_weight INT NOT NULL;
      ALTER TABLE dwarf_steps ADD DEFAULT 1 FOR fairness_weight;
      -- dwarf_steps only:
      CREATE INDEX idx_dwarf_steps_selection ON dwarf_steps (status, parked, priority, fairness_key, created_at, step_id) INCLUDE (not_before, lease_expires, fairness_weight, lineage_id) WHERE status IN ('pending', 'running');
      CREATE INDEX idx_dwarf_steps_due ON dwarf_steps (status, parked, priority, not_before) INCLUDE (fairness_key, created_at, step_id, lease_expires, fairness_weight) WHERE status = 'pending' AND step_id <> 0;
    • SQLite. SQLite cannot change a column's type, so each of the four tables is rebuilt by
      SQLite's own procedure. First round the weights
      (UPDATE dwarf_steps SET fairness_weight = MAX(1, ROUND(fairness_weight))), then, in one transaction, create the
      table under a new name from v0.16.0's definition (the SQLite section of internal/migrations/live/1.sql for
      dwarf_flows, live/2.sql for dwarf_steps, archive/1.sql and archive/2.sql for a day, with the day's
      table name), copy the rows (INSERT INTO dwarf_steps_new SELECT * FROM dwarf_steps), drop the old table, rename
      the new one, and create the table's indexes from the same file, named as the old ones were. Only rebuilding
      changes how a value is stored: a rounded weight left in the old REAL column is still read back as a real
      number, and 1,000,000 or more then cannot be read.

Dependencies

  • sequel v1.20.2, seamster v0.4.1, pgx v5.13.0 and golang.org/x/sync v0.25.0. Through sequel, the MySQL driver v1.10.2 and
    go-mssqldb v1.12.0.