Cron Controller: Schedules, Catch-up and Concurrency

Cron Controller: Schedules, Catch-up and Concurrency

You've joined the platform-runtime team that owns cronctl, the small controller that launches every team's scheduled jobs (think of a CronJob controller). It has had a rough quarter: jobs fire on the wrong days, a restart launched hundreds of runs at once, and two product requests are queued behind the fixes. Everything is UTC unless a Part says otherwise, and time is counted in whole minutes.

Codebase

How your code is run

run(operations: list[list]) -> list executes the operations in order against a fresh controller and returns one result per operation. Every operation is [name, *args]. Errors are returned as "error: <code>" strings, never raised.

• Time strings look like "2024-03-01T09:30": UTC, minute resolution, exactly that shape, a real calendar date, year 2000-2199. Anything else is invalid time. Results use the same format (a result may fall after 2199).
• An unknown operation name returns "error: unknown operation". A wrong number of arguments (or an empty or non-list operation) returns "error: invalid arguments". Arguments of the wrong type produce the specific error named in the tables below.
• Operations that carry a time (create_job, tick, finish, and later bulk_create) have it as their first argument. The rest of the operations are reads or pure calculations.

Cron expressions

An expression has five fields separated by whitespace (leading, trailing and repeated whitespace is ignored): minute hour day-of-month month day-of-week.

1. Ranges: minute 0-59, hour 0-23, day-of-month 1-31, month 1-12 or JAN-DEC, day-of-week 0-7 or SUN-SAT (both 0 and 7 mean Sunday). Names are case-insensitive and allowed only in the month and day-of-week fields.
2. A field is a comma-separated list of items. An item is *, a value v, or a range lo-hi (lo <= hi), optionally followed by /step (an integer >= 1) **only after * or a range** (5/15 is invalid). Numbers are plain decimal digits (leading zeros allowed). Anything else (empty items, signs, ?, L, #, values out of range) is invalid expression.
3. * means the field's whole range (day-of-week: 0-6). A step counts from the first value of its range: */15 in minutes is 0, 15, 30, 45; */10 in day-of-month is 1, 11, 21, 31; */2 in month is JAN, MAR, MAY, ...; 1-30/7 is 1, 8, 15, 22, 29; MON-FRI/2 is MON, WED, FRI.
4. A minute matches when its minute, hour and month are in their sets and its day matches:

• A day field (day-of-month or day-of-week) is restricted exactly when its text does **not begin with ***. So *, */1 and */2 are unrestricted; 5, 1-31 and MON are restricted.
• If both day fields are restricted, the day matches when day-of-month matches or day-of-week matches (Vixie cron).
• Otherwise the day matches only when both match. An unrestricted field still applies its own set: */2 in day-of-month means odd days.

1. Next fire. The *next fire* of an expression after minute a is the smallest matching minute strictly greater than a, provided its calendar year is at most 8 + the calendar year of a (8 years always reaches the next 29 February). If there is none, the expression *never fires* from a.

Part 1: Schedules fire on the wrong days (INC-4417, INC-4429)

Goal: make next_runs follow the cron rules above. Teams report nightly jobs running on the wrong days of the month and Sunday jobs that never run.

Rules

1. count must be an integer from 1 to 50 (true is not one), otherwise invalid count.
2. The first time is the next fire of expr after after; each following time is the next fire after the previous one.
3. If the first search finds nothing the result is error: never fires. If a later search finds nothing the list simply ends there (it may be shorter than count).

Example

[["next_runs", "*/20 9-10 * * MON-FRI", "2024-03-01T10:15", 4],
 ["next_runs", "0 12 13 * FRI", "2024-03-01T00:00", 4],
 ["next_runs", "0 12 */2 * FRI", "2024-03-01T00:00", 4]]

returns

[["2024-03-01T10:20", "2024-03-01T10:40", "2024-03-04T09:00", "2024-03-04T09:20"],
 ["2024-03-01T12:00", "2024-03-08T12:00", "2024-03-13T12:00", "2024-03-15T12:00"],
 ["2024-03-01T12:00", "2024-03-15T12:00", "2024-03-29T12:00", "2024-04-05T12:00"]]

The second expression is "the 13th or any Friday" (both fields restricted). The third has an unrestricted day-of-month (*/2), so it means odd days that are also Fridays.

Part 2: Restart storm and concurrency policies (INC-4466)

Goal: after Tuesday's deploy the controller was down for six hours; when it came back, tick launched every missed run of every job (360 copies of each every-minute job). Make tick behave like a Kubernetes CronJob controller: at most one catch-up run per job, a concurrency policy per job, an optional starting deadline, and a safety cap on missed schedules.

Rules

1. The clock. The controller's *clock* is the latest valid time presented so far by any time-carrying operation. An operation whose time is earlier than the clock returns clock went backwards and does nothing; equal times are fine. An operation whose time passes both time checks moves the clock to its time even if it then fails for another reason. Operations rejected as unknown operation or invalid arguments never reach the controller and do nothing at all.
2. create_job. name is 1-40 characters: lower-case letters and digits in groups separated by single hyphens (nightly-report), otherwise invalid name. policy is "allow", "forbid" or "replace". options is optional (absent or null means defaults); in Part 2 its only key is starting_deadline, a positive integer number of minutes or null (= no deadline). Any other key or value is invalid options. The job's schedule times are the fire times strictly after the creation time. A job whose expression never fires from the creation time is rejected with never fires.
3. tick(now) looks at every job in creation order and decides, independently for each:
4. Let L be the job's last_schedule (the schedule time of the newest run it launched) or, if it has launched nothing yet, its creation time. The job's *missed schedules* are its schedule times t with L < t <= now, and, if the job has a starting_deadline, also t >= now - starting_deadline (inclusive).
5. No missed schedules: nothing happens for this job.
6. More than 100 missed schedules (exactly 100 is fine): event overflow <job>, and nothing else changes for that job (no run, last_schedule unchanged).
7. Otherwise let T be the most recent missed schedule; at most one run is launched, for T:

• allow: launch.
• forbid: if the job has any running run, event skip <job> for <T> (forbid) and nothing else changes (last_schedule stays where it was, so that time is still "missed" at the next tick, together with any newer ones). Otherwise launch.
• replace: every running run of the job is deleted first, in launch order, each with event replace <run_id>; then launch. Deleted runs no longer exist (run not found).

1. Launching creates a run with id <job>-<n> (n = number of runs this job has launched so far + 1), state running, scheduled_for = T, launched_at = now; sets last_schedule = T; event launch <run_id> for <T>. The result is the list of events in the order they happened.
2. finish: outcome must be "succeeded" or "failed" (else invalid outcome, checked before the run is looked up). The run's state becomes the outcome and finished_at the operation's time. A run that is not running gives run not active.
3. job_status: last_schedule (time or null), next_fire (the job's next schedule time strictly after the current clock, or null if there is none), active (ids of running runs, oldest launch first) and launched (total runs launched). run: finished_at is null while running.

Example

[["create_job", "2024-03-01T00:00", "report", "30 9 * * *", "allow"],
 ["create_job", "2024-03-01T00:00", "sync", "*/10 * * * *", "forbid"],
 ["tick", "2024-03-01T00:45"],
 ["tick", "2024-03-01T01:05"],
 ["finish", "2024-03-01T01:06", "sync-1", "succeeded"],
 ["tick", "2024-03-01T01:06"],
 ["tick", "2024-03-01T09:30"],
 ["job_status", "sync"]]

returns true, true, then ["launch sync-1 for 2024-03-01T00:40"] (only the latest of four missed times runs), ["skip sync for 2024-03-01T01:00 (forbid)"], true, ["launch sync-2 for 2024-03-01T01:00"] (the skipped time is still missed once sync-1 is done), ["launch report-1 for 2024-03-01T09:30", "skip sync for 2024-03-01T09:30 (forbid)"], and finally {"last_schedule": "2024-03-01T01:00", "next_fire": "2024-03-01T09:40", "active": ["sync-2"], "launched": 2}.

Part 3: Hung runs and run history (INC-4502)

Goal: runs that hang block forbid jobs forever, and finished runs pile up on the cluster. Add run timeouts and bounded history. Part 2 behaviour must not change for jobs that use neither.

New options (keys of the create_job options object): timeout (positive integer minutes or null, default none), keep_succeeded and keep_failed (integers >= 0; defaults in cronctl/config.py: 3 and 1). Unknown keys or invalid values are invalid options. New run state: timed_out.

Rules

1. Timeouts. A running run with a job timeout times out as soon as launched_at + timeout <= clock. Its state becomes timed_out and its finished_at is launched_at + timeout (the moment it expired, not the moment anyone noticed). This is applied at the start of every time-carrying operation, right after its clock check passes (including operations that go on to fail), before the operation does anything else. So a finish on an already-expired run is run not active, and a forbid job's tick that is exactly at the expiry time sees no running run.
2. Retention. Finished runs fall into two classes per job: *succeeded* (succeeded) and *failed* (failed and timed_out). Whenever a run finishes, each class keeps only the newest keep_* runs of that job, newest meaning greater finished_at, ties broken by the higher launch number. Dropped runs are gone (run not found). Running runs and replaced runs never count; launch numbers keep counting up (ids are never reused) and launched is unaffected.
3. history lists the retained finished runs of both classes, oldest first by (finished_at, launch number).

Example

[["create_job", "2024-03-01T00:00", "etl", "0 * * * *", "allow", {"timeout": 45, "keep_succeeded": 1}],
 ["tick", "2024-03-01T01:00"],
 ["tick", "2024-03-01T02:00"],
 ["finish", "2024-03-01T02:10", "etl-2", "succeeded"],
 ["tick", "2024-03-01T03:00"],
 ["finish", "2024-03-01T03:20", "etl-3", "succeeded"],
 ["history", "etl"],
 ["run", "etl-2"],
 ["finish", "2024-03-01T03:21", "etl-1", "failed"]]

returns true, ["launch etl-1 for 2024-03-01T01:00"], ["launch etl-2 for 2024-03-01T02:00"] (etl-1 timed out at 01:45), true, ["launch etl-3 for 2024-03-01T03:00"], true (that drops etl-2), [["etl-1", "timed_out", "2024-03-01T01:45"], ["etl-3", "succeeded", "2024-03-01T03:20"]], "error: run not found", "error: run not active".

Part 4: Time zones and intervals (requirements change, PLAT-912)

Goal: finance wants "09:00 Berlin time" jobs, and the monitoring team wants @every interval jobs. Add both. All earlier behaviour (catch-up, the 100 cap, deadlines, policies, timeouts, retention) applies to the new kinds of schedule unchanged.

Rules

1. Time zones. The tz option of create_job and an optional fourth argument of next_runs is a fixed UTC offset "+HH:MM" / "-HH:MM": hours 00-14, minutes 00, 15, 30 or 45, magnitude at most 14:00 ("+14:00" is valid, "+14:15", "+5:30" and "UTC" are not). Invalid: invalid options for create_job and invalid timezone for next_runs (checked after invalid count, before never fires). The default is +00:00.
2. A cron expression is matched against local time = UTC + offset: the local minute, hour, day-of-month, month and weekday. There is no daylight-saving time. The 8-year rule of "next fire" uses the local calendar year of after. All times going in and out stay UTC.
3. Intervals. An expression of the form @every <N>m or @every <N>h (N a positive integer without sign or leading zeros; at most 525 600 minutes in total; one space; surrounding/repeated whitespace ignored) fires every N minutes (N * 60 for h) counted from an anchor: the schedule times are anchor + k * interval for k = 1, 2, ... (never the anchor itself). A job's anchor is its creation time (not the time of any launch); for next_runs the anchor is its after. Any other text starting with @ is invalid expression. Interval schedules never run out, so they never give never fires.
4. A tz together with an @every expression is invalid options (invalid timezone for next_runs).

Example

[["next_runs", "30 2 * * *", "2024-03-01T00:00", 2, "+05:30"],
 ["next_runs", "0 0 1 * *", "2024-03-01T00:00", 2, "-08:00"],
 ["next_runs", "@every 90m", "2024-03-01T10:07", 3]]

returns

[["2024-03-01T21:00", "2024-03-02T21:00"],
 ["2024-03-01T08:00", "2024-04-01T08:00"],
 ["2024-03-01T11:37", "2024-03-01T13:07", "2024-03-01T14:37"]]

(Local midnight at -08:00 is 08:00 UTC; the +05:30 job runs at 21:00 UTC on the previous UTC day of each local 02:30.)

Part 5: Fleet import and long outages (stretch)

Goal: the platform team wants to import whole fleets of jobs from Helm manifests and survive multi-year outages in staging. Add bulk creation and a compact tick summary, and make the controller fast enough.

Rules

1. bulk_create creates the jobs <prefix>-0 ... <prefix>-<count-1> (creation order = index order); job i uses exprs[i % len(exprs)]. Same policy and options for all. count is an integer 1-5000. prefix and every generated name must be a valid job name; exprs must be a non-empty list of valid expressions. Anything wrong anywhere means no job is created (all or nothing); job exists if any generated name is taken. All jobs get the same creation time now.
2. tick with "counts" performs exactly the same tick, but returns the number of launch, skip, replace and overflow events, plus digest: the sum over this tick's launches of minutes_since_1970(scheduled_for) * (job_creation_index + 1), modulo 1 000 000 007, where job_creation_index is the job's 0-based position in creation order.
3. Hidden tests include: a few hundred jobs with yearly, monthly and leap-day schedules ticked over a decade; a fleet that was "down" for ten years with every-minute jobs; and many schedules that can never fire. The whole suite has a few seconds, and decades of minutes are far too many to step through one by one.

Example

[["bulk_create", "2024-01-01T00:00", "probe", 3, ["*/30 * * * *", "@every 45m"], "allow"],
 ["tick", "2024-01-01T01:00", "counts"]]

returns 3 and {"launched": 3, "skipped": 0, "replaced": 0, "overflowed": 0, "digest": 170407050}. (probe-0 and probe-2 run for 01:00; probe-1 runs for 00:45.)

Notes

• clock.py, jobs.py and errors.py are known-good.
• You may use the AI assistant freely; you are expected to verify what it produces.
• Later Parts must not break earlier ones; hidden tests re-check earlier behaviour with the newer features switched on.
• Parts 1-4 are a strong result. Part 5 is a stretch.