Engineer a deterministic job orchestration system that offers logical time semantics,…
- User
Engineer a deterministic job orchestration system that offers logical time semantics, dependency cycles detection, and replay debugging.
Assistant
The user wants me to "Engineer a deterministic job orchestration system" with specific features:
- Deterministic: Given the same input and configuration, the execution flow and outcome must be identical.
- Logical Time Semantics: This usually refers to Lamport Timestamps or Vector Clocks to order events without relying on physical clocks, crucial for distributed or asynchronous systems, but also useful here for tracking causality.
- Dependency Cycles Detection: The system needs to analyze the DAG (Directed Acyclic Graph) of jobs. If it's not acyclic, it must detect and report the cycle.
- Replay Debugging: The ability to record the execution history and replay it step-by-step to debug failures or understand flow.
Scope and Architecture:
- Language: Python is excellent for this because it's readable, has strong standard libraries (graph algorithms, async), and is commonly used for orchestration (Airflow, Prefect, Luigi).
- Core Components:
Job: The unit of work. Needs an ID, dependencies, and a function to execute.Scheduler/Orchestrator: The brain. Manages the queue, checks dependencies, executes jobs, handles time.Logical Clock: To implement the "happened-before" relationship.Logger/Recorder: To capture state changes for replay.
Feature 1: Logical Time (Lamport Clocks)
- Each Job (or the System) maintains a counter.
- Rule: Before an event (job execution start/end), increment counter.
- Rule: When receiving a "signal" (dependency met), update counter to
max(local, received) + 1. - Since this is likely a single-process simulation for clarity (though designed for distributed concepts), I'll use a central logical clock or distribute clocks per job node to track causality. Let's go with a global Lamport clock for simplicity in the demo, or perhaps vector clocks if we want true partial ordering, but Lamport is usually sufficient for "logical time semantics" in a basic orchestration context. Actually, let's use a
LogicalClockclass that ticks on every event.
Feature 2: Dependency Cycles Detection
- Standard graph theory problem.
- Algorithms: DFS (Depth First Search) or Tarjan's Algorithm (for strongly connected components).
- DFS is easier to implement quickly. We need to check before execution starts.
Feature 3: Replay Debugging
- We need an "Event Sourcing" approach. Instead of just mutating state, we record a log of events:
JobStarted,JobFinished,ClockTicked. - To replay, we rehydrate the state by iterating through the log.
Feature 4: Determinism
- This means we cannot use
randomortime.sleep(unless mocked) or external API calls that vary. - The execution order must be defined. If multiple jobs are ready, which one runs first? Usually alphabetical or by priority. I will enforce a strict ordering (e.g., sorted by ID) to ensure determinism.
Drafting the Code Structure:
-
LogicalClock:time: integertick(): increments timeupdate(received_time): sets time to max + 1
-
Event:- Dataclass. Type, JobID, Timestamp, Result.
-
Job:id: stringfunc: callabledependencies: list of strings
-
Orchestrator:jobs: dictgraph: adjacency listexecution_log: list of Eventsdetect_cycle(): DFS based.run():- Check cycles.
- Initialize queue.
- Loop until queue empty.
- Pop job (deterministically).
- Execute (record start).
- Finish (record end, update dependencies).
Refining the "Deterministic" Aspect: To make it truly deterministic, if Job A and Job B are both ready, the system must always pick A then B (or B then A), never random. I will use
heapqorsortedlists to manage the ready queue based on Job ID.Refining "Replay Debugging": The output should be a transcript.
> Time 1: Job A started> Time 2: Job A finished (Output: ...)> Time 3: Job B started ...Putting it together in Python:
- Input: A definition of jobs.
- Validation: Cycle check.
- Execution: Run with logical time, logging every step.
- Replay: A method to print the log.
Self-Correction/Edge Cases:
- Cycle Detection: What if the graph is empty? Fine. What if it's fully connected? Fine.
- Logical Time: Should the clock be global or per-node? A global clock is easiest for a single-threaded orchestrator simulation. If this were distributed, we'd pass timestamps. I'll stick to a global clock for the system state to ensure total ordering in the replay.
- Replay: The user might want to re-run the logic, or just view the history. "Replay debugging" implies inspecting the history. I will implement a method to dump the history and perhaps a
debuggerclass that can step through the events.
Implementation Plan:
- Define
Jobclass. - Define
LogicalClockclass. - Define
EventLog(for replay). - Define
Orchestratorclass.add_jobdetect_cycles(using DFS coloring: White, Gray, Black).run: Topological sort-like execution but event-driven.
- Demo script: Define a simple graph (including one with a cycle to show detection, then a valid one to show execution/replay).
Code Details:
- Use
dataclassesfor clean data structures. - Use
typingfor hints. - Use
collections.dequefor queues.
Logic for Cycle Detection: Standard 3-color DFS.
- White (0): Unvisited
- Gray (1): Visiting (in recursion stack)
- Black (2): Visited If we hit a Gray node, we have a cycle.
Logic for Execution:
- Build indegree map.
- Find all nodes with indegree 0.
- Push to a
PriorityQueue(to ensure deterministic order). - While PQ not empty:
- Pop node.
- Tick clock. Log "Start".
- Run job function.
- Tick clock. Log "Finish".
- For each child:
- Decrement indegree.
- If indegree == 0, push to PQ.
Refining Replay: The log stores
Eventobjects. AReplayDebuggerreads this list and formats it nicely or allows stepping.Let's write the code. Here is a complete, engineered solution in Python. This system implements a deterministic orchestrator using a Lamport Logical Clock for temporal ordering, Depth-First Search (DFS) for cycle detection, and an Event Sourcing pattern to enable full replay debugging.
System Architecture
LogicalClock: Ensures deterministic ordering of events across the dependency graph, regardless of physical execution time.Job&JobResult: Encapsulates the unit of work and its deterministic outcome.EventLog: The source of truth. Instead of just executing, the system streams state changes to a log.Orchestrator: The engine that validates the graph (acyclic check), resolves dependencies, and executes jobs based on logical time.ReplayDebugger: Consumes theEventLogto reconstruct the system state at any specific logical timestamp.
Implementation
import hashlib import json import time from enum import Enum, auto from typing import Dict, List, Set, Callable, Any, Optional from dataclasses import dataclass, field # ========================================== # 1. Core Components & Logical Time # ========================================== class LogicalClock: """ Implements a Lamport Logical Clock. Ensures deterministic ordering of events. """ def __init__(self): self.counter = 0 def tick(self) -> int: self.counter += 1 return self.counter def update(self, received_time: int) -> int: """Update clock based on external event (receiving a message).""" self.counter = max(self.counter, received_time) return self.tick() class JobState(Enum): PENDING = auto() RUNNING = auto() COMPLETED = auto() FAILED = auto() @dataclass class Job: id: str func: Callable[[], Any] # The deterministic function to execute dependencies: List[str] = field(default_factory=list) @dataclass class JobResult: job_id: str result: Any hash: str # Deterministic hash of the result for verification # ========================================== # 2. Event Sourcing (for Replay Debugging) # ========================================== class EventType(Enum): JOB_SUBMITTED = auto() CYCLE_DETECTED = auto() JOB_STARTED = auto() JOB_FINISHED = auto() SYSTEM_HALT = auto() @dataclass class Event: logical_time: int event_type: EventType payload: Dict[str, Any] class EventLog: """ Immutable log of system events. This acts as the basis for replay debugging. """ def __init__(self): self.events: List[Event] = [] def record(self, time: int, event_type: EventType, payload: Dict[str, Any]): self.events.append(Event(time, event_type, payload)) def get_history(self) -> List[Event]: return sorted(self.events, key=lambda e: e.logical_time) # ========================================== # 3. The Orchestrator # ========================================== class Orchestrator: def __init__(self): self.jobs: Dict[str, Job] = {} self.graph: Dict[str, List[str]] = {} # Adjacency list (Job -> Children) self.clock = LogicalClock() self.log = EventLog() self.results: Dict[str, JobResult] = {} def register_job(self, job: Job): """Registers a job and initializes graph edges.""" self.jobs[job.id] = job self.graph[job.id] = [] # Record submission self.log.record(self.clock.tick(), EventType.JOB_SUBMITTED, {"job_id": job.id}) # Build reverse graph for dependency resolution for dep_id in job.dependencies: if dep_id not in self.graph: self.graph[dep_id] = [] self.graph[dep_id].append(job.id) def _detect_cycle(self) -> Optional[List[str]]: """ Detects cycles using DFS. Returns the cycle path if found, otherwise None. """ visited: Set[str] = set() recursion_stack: Set[str] = set() path: List[str] = [] def dfs(node_id: str) -> bool: visited.add(node_id) recursion_stack.add(node_id) path.append(node_id) for neighbor in self.graph.get(node_id, []): if neighbor not in visited: if dfs(neighbor): return True elif neighbor in recursion_stack: # Cycle detected path.append(neighbor) return True recursion_stack.remove(node_id) path.pop() return False for node in list(self.graph.keys()): if node not in visited: if dfs(node): # Extract the exact cycle from the path cycle_start = path.index(path[-1]) return path[cycle_start:] return None def _hash_result(self, data: Any) -> str: """Creates a deterministic hash of the job output.""" return hashlib.md5(json.dumps(str(data), sort_keys=True).encode()).hexdigest() def run(self): """ Executes the job graph deterministically. """ # 1. Validation Phase cycle = self._detect_cycle() if cycle: self.log.record(self.clock.tick(), EventType.CYCLE_DETECTED, {"cycle": cycle}) print(f"❌ ERROR: Dependency Cycle Detected: {' -> '.join(cycle)}") return # 2. Execution Phase # Jobs that are ready to run (dependencies met) ready_queue: List[str] = [] # Track completion status completed: Set[str] = set() # Track number of dependencies remaining for each job in_degree: Dict[str, int] = {j: 0 for j in self.jobs} # Calculate in-degrees for job in self.jobs.values(): for dep in job.dependencies: if dep in in_degree: in_degree[job.id] += 1 # Should be len(job.dependencies) effectively # Note: simplified logic here assumes dependencies exist # Initialize queue with jobs having no dependencies for job_id, degree in in_degree.items(): if degree == 0: ready_queue.append(job_id) # Sort queue to ensure DETERMINISTIC execution order (Alphabetical) ready_queue.sort() while ready_queue: # Pop the next job deterministically current_job_id = ready_queue.pop(0) job = self.jobs[current_job_id] # Log Start self.log.record(self.clock.tick(), EventType.JOB_STARTED, {"job_id": job.id}) # Execute try: # In a real distributed system, this is where the work happens. # For this simulation, we call the function. result_data = job.func() result_hash = self._hash_result(result_data) self.results[job.id] = JobResult(job.id, result_data, result_hash) completed.add(job.id) # Log Finish self.log.record(self.clock.tick(), EventType.JOB_FINISHED, { "job_id": job.id, "hash": result_hash, "preview": str(result_data)[:50] }) # Update Graph # Find children who depend on this job for child_id in self.graph.get(job.id, []): if child_id in in_degree: in_degree[child_id] -= 1 if in_degree[child_id] == 0: ready_queue.append(child_id) # Re-sort to maintain determinism ready_queue.sort() except Exception as e: print(f"Exception during execution: {e}") break self.log.record(self.clock.tick(), EventType.SYSTEM_HALT, {"status": "completed"}) # ========================================== # 4. Replay Debugger # ========================================== class ReplayDebugger: def __init__(self, log: EventLog): self.log = log def replay(self): print("\n--- 🔍 STARTING REPLAY DEBUGGER ---") history = self.log.get_history() print(f"Total Events: {len(history)}") print("-" * 40) for event in history: print(f"[T={event.logical_time:03d}] {event.event_type.name}: {event.payload}") print("-" * 40) print("--- 🔍 REPLAY FINISHED ---") def get_state_at_time(self, t: int) -> List[str]: """Returns the state of the system at logical time T.""" completed_jobs = [] for event in self.log.get_history(): if event.logical_time > t: break if event.event_type == EventType.JOB_FINISHED: completed_jobs.append(event.payload['job_id']) return completed_jobs # ========================================== # 5. Usage Example # ========================================== # Deterministic mock functions def task_A(): return "Data_A" def task_B(): return "Data_B_depends_A" def task_C(): return "Data_C_depends_A" def task_D(): return "Data_D_depends_B_C" def main(): system = Orchestrator() # Case 1: Valid Graph print("Setting up valid job graph...") system.register_job(Job("A", task_A, [])) system.register_job(Job("B", task_B, ["A"])) system.register_job(Job("C", task_C, ["A"])) system.register_job(Job("D", task_D, ["B", "C"])) # D waits for B and C system.run() # Replay Debugging debugger = ReplayDebugger(system.log) debugger.replay() # Verify State at specific logical time print(f"\nState at T=3: {debugger.get_state_at_time(3)}") print(f"State at T=5: {debugger.get_state_at_time(5)}") # Case 2: Cyclic Graph print("\n\n--- Testing Cycle Detection ---") cycle_system = Orchestrator() cycle_system.register_job(Job("X", lambda: "X", ["Z"])) cycle_system.register_job(Job("Y", lambda: "Y", ["X"])) cycle_system.register_job(Job("Z", lambda: "Z", ["Y"])) # Z -> Y -> X -> Z cycle_system.run() if __name__ == "__main__": main()Key Engineering Details
-
Determinism via Sorting: In a dependency graph, multiple jobs may become "ready" simultaneously (e.g., B and C are both ready after A finishes). In a non-deterministic system, race conditions dictate which runs first. In this system, the
ready_queueis explicitlysort()ed alphabetically by Job ID. This guarantees that the execution flow is identical every time you run the code with the same input graph. -
Logical Time (Lamport Timestamps): Every state change (Submission, Start, Finish) increments a global integer counter. This allows us to say "Job B started at T=4," which is vital for replay debugging. It decouples the system behavior from physical wall-clock time (which varies due to OS scheduling).
-
Cycle Detection: The
_detect_cyclemethod uses DFS to identify back-edges. If a cycle exists (e.g., A waits for B, B waits for A), the system refuses to execute and logs aCYCLE_DETECTEDevent with the offending path. -
Replay Debugging: The
EventLogstores a sequence of immutable events. TheReplayDebuggercan ingest this log and reconstruct the timeline. This is extremely useful in production systems where you might store this log to a database; if a job fails at T=50, you can "rewind" to T=49 to inspect the system state.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.