👽
Software Engineer Interview Handbook
  • README
  • Behavioral
    • Useful Links
    • Dongze Li
  • Algorithm
    • Segment Tree
    • Array
      • Product Of Array Except Self
      • Merge Strings Alternately
      • Increasing Triplet Subsequence
      • String Compression
      • Greatest Common Divisor Strings
      • Max Product Of Three
      • Find Duplicate Num
      • Valid Palindrome Ii
      • Next Permutation
      • Rearrange Array By Sign
      • Removing Min Max Elements
      • Find Original Array From Doubled
      • Reverse Words Ii
    • Backtracking
      • Letter Combination Phone Number
      • Combination Sum Iii
      • N Queens
      • Permutations
      • Combination Sum
    • Binary Search
      • Koko Eating Bananas
      • Find Peak Element
      • Successful Pairs Of Spells Potions
    • Binary Search Tree
      • Delete Node In BST
      • Validate Bst
      • Range Sum Bst
    • Binary Tree
      • Maximum Depth
      • Leaf Similar Trees
      • Maximum Level Sum
      • Binary Tree Right Side
      • Lowest Common Ancestor
      • Longest Zigzag Path
      • Count Good Nodes
      • Path Sum III
      • Maximum Path Sum
      • Move Zero
      • Diameter Binary Tree
      • Sum Root Leaf Number
      • Traversal
      • Binary Tree Vertical Order
      • Height Tree Removal Queries
      • Count Nodes Avg Subtree
      • Distribute Coins
      • Binary Tree Max Path Sum
    • Bit
      • Min Flips
      • Single Number
      • Pow
      • Find Unique Binary Str
    • BFS
      • Rotten Oranges
      • Nearest Exist From Entrance
      • Minimum Knight Moves
      • Network Delay Time
      • Minimum Height Tree
      • Knight Probability In Board
    • Design
      • LRU Cache
      • Get Random
      • LFU Cache
      • Moving Average
      • Rle Iterator
      • Design Hashmap
    • DFS
      • Reorder Routes Lead City
      • Evaluate Division
      • Keys And Rooms
      • Number Of Provinces
      • Disconnected Path With One Flip
      • Course Schedule Ii
      • Robot Room Cleaner
      • Word Break Ii
      • Number Coins In Tree Nodes
      • Maximum Increasing Cells
      • Number Coins In Tree Nodes
      • Detonate Maximum Bombs
      • Find All Possible Recipes
      • Min Fuel Report Capital
      • Similar String Groups
    • DP
      • Domino And Tromino Tiling
      • House Robber
      • Longest Common Subsequence
      • Trade Stock With Transaction Fee
      • Buy And Sell Stock
      • Longest Non Decreasing Subarray
      • Number Of Good Binary Strings
      • Delete And Earn
      • Minimum Costs Using Train Line
      • Decode Ways
      • Trapping Rain Water
      • Count Fertile Pyramids
      • Minimum Time Finish Race
      • Knapsack
      • Count Unique Char Substrs
      • Count All Valid Pickup
    • Greedy
      • Dota2 Senate
      • Smallest Range Ii
      • Can Place Flowers
      • Meeting Rooms II
      • Guess the word
      • Minimum Replacement
      • Longest Palindrome Two Letter Words
      • Parentheses String Valid
      • Largest Palindromic Num
      • Find Missing Observations
      • Most Profit Assigning Work
    • Hashmap
      • Equal Row Column Pairs
      • Two Strings Close
      • Group Anagrams
      • Detect Squares
    • Heap
      • Maximum Subsequence Score
      • Smallest Number Infinite Set
      • Total Cost Hire Workers
      • Kth Largest Element
      • Meeting Rooms III
      • K Closest Points Origin
      • Merge K Sorted List
      • Top K Frequent Elements
      • Meeting Room III
      • Num Flowers Bloom
      • Find Median From Stream
    • Intervals
      • Non Overlapping Intervals
      • Min Arrows Burst Ballons
    • Linkedlist
      • Reverse Linked List
      • Delete Middle Node
      • Odd Even Linkedlist
      • Palindrome Linkedlist
    • Monotonic Stack
      • Daily Temperatures
      • Online Stock Span
    • Random
      • Random Pick With Weight
      • Random Pick Index
      • Shuffle An Array
    • Recursion
      • Difference Between Two Objs
    • Segment Fenwick
      • Longest Increasing Subsequence II
    • Stack
      • Removing Stars From String
      • Asteroid Collision
      • Evaluate Reverse Polish Notation
      • Building With Ocean View
      • Min Remove Parentheses
      • Basic Calculator Ii
      • Simplify Path
      • Min Add Parentheses
    • Prefix Sum
      • Find The Highest Altitude
      • Find Pivot Index
      • Subarray Sum K
      • Range Addition
    • Sliding Window
      • Max Vowels Substring
      • Max Consecutive Ones III
      • Longest Subarray Deleting Element
      • Minimum Window Substring
      • K Radius Subarray Averages
    • String
      • Valid Word Abbreviations
    • Two Pointers
      • Container With Most Water
      • Max Number K Sum Pairs
      • Is Subsequence
      • Num Substrings Contains Three Char
    • Trie
      • Prefix Tree
      • Search Suggestions System
      • Design File System
    • Union Find
      • Accounts Merge
    • Multithreading
      • Basics
      • Web Crawler
  • System Design
    • Operating System
    • Mocks
      • Design ChatGPT
      • Design Web Crawler
      • Distributed Search
      • News Feed Search
      • Top K / Ad Click Aggregation
      • Design Job Scheduler
      • Distributed Message Queue
      • Google Maps
      • Nearby Friends
      • Proximity Service
      • Metrics monitoring and alert system
      • Design Email
      • Design Gaming Leaderboard
      • Facebook New Feed Live Comments
      • Dog Sitting App
      • Design Chat App (WhatsApp)
      • Design Youtube/Netflix
      • Design Google Doc
      • Design Webhook
      • Validate Instacart Shopper Checkout
      • Design Inventory
      • Design donation app
      • Design Twitter
    • Deep-Dive
      • Back of Envelope
      • Message Queue
      • Redis Sorted Set
      • FAQ
      • Geohash
      • Quadtree
      • Redis Pub/Sub
      • Cassandra DB
      • Collaborative Concurrency Control
      • Websocket / Long Polling / SSE
    • DDIA
      • Chapter 2: Data Models and Query Languages
      • Chapter 5: Replication
      • Chapter 9: Consistency and Consensus
  • OOD
    • Overview
    • Design Parking
  • Company Tags
    • Meta
    • Citadel
      • C++ Fundamentals
      • 面经1
      • Fibonacci
      • Pi
      • Probability
    • DoorDash
      • Similar String Groups
      • Door And Gates
      • Max Job Profit
      • Design File System
      • Count All Valid Pickup
      • Most Profit Assigning Work
      • Swap
      • Binary Tree Max Path Sum
      • Nearest Cities
      • Exployee Free Time
      • Tree Add Removal
    • Lyft
      • Autocomplete
      • Job Scheduler
      • Read4
      • Kvstore
    • Amazon
      • Min Binary Str Val
    • AppLovin
      • TODO
      • Java Basic Questions
    • Google
      • Huffman Tree
      • Unique Elements
    • Instacart
      • Meeting Rooms II
      • Pw
      • Pw2
      • Pw3
      • Expression1
      • Expression2
      • Expression3
      • PW All
      • Expression All
      • Wildcard
      • Free forum tech discussion
    • OpenAI
      • Spreadsheet
      • Iterator
      • Kv Store
    • Rabbit
      • Scheduler
      • SchedulerC++
    • [Microsoft]
      • Min Moves Spread Stones
      • Inorder Successor
      • Largest Palindromic Num
      • Count Unique Char Substrs
      • Reverse Words Ii
      • Find Missing Observations
      • Min Fuel Report Capital
      • Design Hashmap
      • Find Original Array From Doubled
      • Num Flowers Bloom
      • Distribute Coins
      • Find Median From Stream
Powered by GitBook
On this page
  • Topics:
  • Functional Requirements
  • Non-functional Requirement
  • High Level Diagram
  • E2E
  • Data Schema
  • Deep Dive
  • Job Scheduling Flow
  • Fault-tolerance
  • Job Executor Flow
  1. System Design
  2. Mocks

Design Job Scheduler

Design a job scheduler that runs jobs at a scheduled interval.

PreviousTop K / Ad Click AggregationNextDistributed Message Queue

Last updated 1 year ago

Topics:

  1. RDBMS vs NoSQL?

  2. SQS vs Kafka?

  3. How to handle at-least once?

  4. How to make sure no concurrent worker working on same job? Task idempotency?

  5. Execution Cap?

  6. How to do prioritization? Using different queue?

Functional Requirements

  1. Submit task: allow the user to submit their tasks for execution.

  2. Allocate resources: allocate require resources to each task.

  3. Remove tasks: should allow cancel submitted tasks.

  4. Monitor task execution: should be adequately monitored and rescheduled if the task fails to execute.

  5. Show task status: User can view the status of a executed job.

  6. User can schedule a cron job with a schedule.

  7. For scheduled jobs, user can limit its max concurrency.

  8. Support different languages.

Non-functional Requirement

  1. Submitted job cannot be lost. Durability.

  2. Availability.

  3. Scalability: should be able to schedule and execute an ever-increasing number of tasks per day.

  4. Reliability - retry

  5. Efficient resource utilization.

  6. Release resources: after executing a task, the system should take back resources assigned to the task.

High Level Diagram

E2E

  1. User submit/get job connecting to API Gateway.

  2. Request get persisted in DB, acknowledgement get sent back to user.

  3. Job executor service will continuously poll the due jobs from DB and insert entries into the queue.

  4. Job executor service execute the business logic and update final result onto file system and update the status as COMPLETED.

Data Schema

Job Execution Table (for quickly fetching jobs that needs to be executed)
next_execution
job_id
(job_id+next_execution_bucket) partiton key
created_at (sort key)

Job Table (for updating status and job details)
job_id (partition_key)
created_at (sort_key)
user_id
execution_cap
scheduling_type
total_attempts
script_path
resource_req {Basic, Regular, Premium}
status: {CLAIMED, PROCESSING, FAILED, SUCCEED}

Job History Table (for quickly lookup jobs history user executed)
user_id (partition_key)
created_at (sort_key)
job_id
retry_cnt
created
interval: 3hr, -1
Column
Datatype
Description

TaskID

String

Uniquely identifies each task

UserID

String

UUID of user

SchedulingType

String

{once, daily, weekly, monthly, anually}

TotalAttempts

Integer

maximum number of retries in case a task execution fails.

ResourceRequirements

String

{Basic, Regular, Premium}

ExecutionCap

Time

maximum time allowed for task execution.

DelayTolerance

Time

indicates how much delay we can sustain before starting a task.

ScriptPath

String

The path of the script needs to be executed. The script is a file placed in a file system.

Deep Dive

Job Scheduling Flow

  1. Every X minute, the master node creates an authoritative UNIX timestamp and assigns a shard_id and schedule_job_execution_time to each worker.

  2. Worker node will execute DB query and push jobs inside the Kafka queue for execution.

SELECT * FROM ScheduledJob WHERE scheduled_job_execution_time == now() -X and shard_id = 1

SELECT * FROM ScheduledJob WHERE scheduled_job_execution_time == now() - X and shard_id = 2

Fault-tolerance

  • Master monitors health of workers and knows which worker is dead and how to re-assign the query to new worker

  • If master dies, we can allocate other worker node as master. (Automatic fail-over)

  • Introduce a local DB to track the status if worker has queries the DB and put the entry inside queue.

Job Executor Flow

  1. When a job is picked up from the queue, consumer's master updates JOB db attribution execution_status = CLAIMED.

  2. When worker process picks up the work, it updates execution_status = PROCESSING and continuously send health check to local DB.

  3. Upon completion of a job, worker process will push the result inside S3, update JOB db execution_status = COMPLETED and local db with the status.

  4. Both worker processes and master will update the health check inside local database.

Link
Medium Link2
Drawing
Drawing