CSE Roadmap

Common tier · about 4 hours · 8 parts

Part 4 of 8 · 2 min read

Design

A leader, followers and a replicated log.

Parts.

  • Scheduler replicas: an odd number (for example 3 or 5), in different failure zones such as different power units.
  • Leader: the only replica that launches jobs and changes shared state.
  • Followers: keep a copy of all state, and are ready to take over.
  • Consensus log: the replicas agree on the state using a consensus algorithm (Paxos in the book, Raft in other systems, Level 5). The log records each change in order, and a change counts only when a majority has it.
  • Cluster scheduler (or the job runner): the system that actually starts processes on machines. The scheduler sends it requests, and does not run jobs itself.
  • Job store: the definitions, kept in the replicated state, not in an outside database. The book prefers a small store inside the service over a large distributed file system, because small writes to a file system are slow, and because a service that others depend on should have few dependencies.

The leader's loop.

  1. Keep the jobs sorted by next launch time.
  2. Wait until the next launch time.
  3. Announce the launch start to the followers through the log, and wait until a majority has recorded it. Compute the next launch time for the job.
  4. Send the request(s) to the cluster scheduler.
  5. Announce the launch end through the log, again waiting for a majority.

The two announcements are the sync points. They are synchronous on purpose: if the leader launched without telling anyone and crashed, the new leader could launch the same job again.

Launch identity. A launch is identified by the job name and its scheduled time, not just the name. A job that runs every minute has many launches, and a short name would make them ambiguous.

Follower behaviour. Each follower records the start and end announcements and updates its copy of the next launch time. When the leader fails (the health check notices in seconds), a follower is elected leader. It must finish the open launches, those that have a start record and no end record.

Common mistake

Starting the job first and telling the followers afterward. A crash in between makes a double launch, because the new leader cannot know whether the first launch happened.

Check yourself: 1. What are the two sync points? 2. Why is a launch identified by name and time? 3. Which replica talks to the cluster scheduler?