Design a Scheduling System (a la Autosys)
Abhishek Kalyankar
5748
System DesignInterview

Introduction:

We need a system used by other developers in team where they can schedule jobs. This will be a single system which will cover all teams in the company.
I had to use a Google Doc, which meant I was not supposed to draw an architecture diagram.

Requirements

Functional Requirements (Given by panel):

  1. Users can do below:
    • Create New Jobs
    • Edit Jobs
    • Delete Jobs
    • See Job History
    • Ability to run a job ad hoc without affecting its schedule

Non Functional Requirements (I came up with this):

  • System should be highly available
  • System should be fault tolerant
  • Minimal latency

My Approach:

  • I have used Autosys in my work. So I thought I will model my design based on my understanding of Autosys!
  • Since I was not allowed to draw diagram, I focussed more on API design and DB design.
  • We will have different APIs for each feature. For DB, I am using RDBMS just because I see clear relationships between different components (e.g. Job table will have job related details, audit table has history, etc). One is free to use NoSQL as well.

For the core scheduling, I decided to use cron expression format.

Workflow:

  1. User would go to a UI (out of scope for this), enter job name, payload (the script/api to be executed every time the job runs) and a cron format specifying the schedule.
  2. Cron validations, payload validations (see if api is in valid format, script files are valid paths, etc are out of scope)
  3. Once they submit, we will call API to save that schedule.
  4. Similar flow for edit, delete and audit/history features.

Logic Design:

Interviewer asked me to not write API, but instead write method names and return type.

  1. int submitJob(JobDetails)

    • the input will be a custom object of type Job (kinda like a Java POJO)
    • the function will return a unique jobId which will be UUID, if its a success.
    • In case of failure, an exception message saying operation failed
    • Make an entry in the audit table

  2. void editJob (jobId)

    • input will be jobId
    • method will check if job exists and is a valid job - if not - an exception message/IllegalArgumentException will be thrown
    • If it's a valid jobId - perform the edit
    • Make an entry in the audit table

  3. boolean deleteJob (jobId)

    • if input is invalid job - return false
    • if valid jobId, perform a soft delete and return true
    • Make an entry in the audit table

Database Schema:

image

Details on Schema:

JOB_DETAILS

  • This is the main table to save job data. Data gets inserted when we create or edit a job. If we create a job, the new row inserted will always have job_version as 1.
  • When we edit a job, we insert a new row, and here job_version will be current row's job_version + 1.
  • E.g. If I create a job first time, version will be 1, when I edit next time, new record will be inserted with version 2 (along with other modified details), the next time new record with version 3 and so on. To get the most recent job, take the job with max job_version for that particular job_id.
  • This design is optional but I choose this as it gives us detailed level data which we can use for audit/connect to a ML pipeline for job predictions.
  • This kinda DB design is inspired from Data Warehousing projects.
  • My design does not do a hard delete. If we get a request to delete a job, we simply mark the is_deleted column in JOB_DETAILS as true. This gives us the option to undelete jobs as well (out of scope for this interview)
  • job_payload is the actual thing to be exected when the job runs. It could be executing an API (field will have curl command), calling a bash file/python file (in this case this field will have fully qualified path to the .sh/.py files), etc.

JOB_SCHEDULE:

  • Whenever a job is created, data is inserted here and original cron expression will be saved in cron_expression. Along with this, we use cron expression to calculate next 3 job runs (if applicable) and save those details as well. These 3 future job run details will be available on the UI when user wants to review/edit a job
  • After interview I realized I could have had a different schema for this table and instead of having 3 columns for 3 future runs, I can have a separate table which can store jobId and next 'n' runs as desired.
  • In case a job is edited, we simply replace the cron_expression and corresponding 3 future jobs
  • Other tables are self explanatory
  • Did not talk about partitioning/sharding/indexes, etc as interviewer was not interested.

Architecture:

  • The database will be RDBMS and it will be load balanced and replicated. As a followup from interviewer I discussed all 3 replication strategies in details wiith tradeoffs - single leader, multi leader and quorum based replication
  • DB nodes configuration can be maintained by a central agency like Apache ZooKeeper. ZK will also track alive/dead nodes using heartbeats.
  • If one does not want to use ZK, then use gossip protocol where each node will ping other node every 5 seconds (heartbeat) to check for liveliness. In this case, and if using a single leader replication, if leader goes down, use Paxos for leader election.
  • Similar to DB nodes, our services/APIs will also be made redundant by having replicas.
  • A LB will be used to direct request to an appropriate service node. I discussed round robin, weighted round robin and consistent hashing mechanisms to route request to server nodes.
  • As our company grows and we have global offices, users will be in diff parts of world. Then we can cache data based on geography of the user - Did not go too deep here as he was not interested in cache
  • In case of multiple load/requests, we can use auto scaling to perform horizontal scaling. Even then if its still very slow, we can park all requests in an MQ and let them be processed at their own speed. We can display a message to user saying your request is being processed and let them know once its done. This way our system is not overwhelmed. This is done because for us Availability is of prime importance, even over consistency (CAP Theorem). No matter what, app should be accessible and should be servicing our requests, even if its slow due to high load.
  • We will have a MQ (Dead Letter Queue) like Apache Kafka - this will be responsible for collecting all errors. This will be fed to a separate 'Alerting and Repair' handling microservice and also it will be connected to Splunk/Kibana to view logs/debug
  • The purpose of this microservice will be to see if this is error can be self corrected - e.g. if the jar file dies, can we automatically restart it? If load increases on system, can we do auto scaling and so on.
  • If its not auto correcting error, then alert the PM team about this error via DataDog or simply check logs via Kibana.

Some other considerations:

  • When creating a job, we will have a UI warning, that if an infinite, always running job is created, (e.g. * * * * * * * ), then warn user about the consequences of their actions. If user is still ok, then proceed.
  • In an enhanced system, perhaps for such severe/abnormal requests, we can have a manual approval workflow, where one needs an approval from somebody to create a job which is infinitely running.
  • If an adhoc job is being run with an infinite time, reject that job request

This is all I could get done in 50 mins - lots of deep follow up questions were asked at every stage which I answered to my best knowledge.
Was a little bit shaky in the core scheduling logic (how to calculate current and next runs, etc) and interviewer gave a hint but overall it was pretty smooth according to me and I was happy with my overall performance.

Verdict - Rejected

How do you rate my design? How can you design it or improve my design? Any constructive feedback?

Comments (14)