[!IMPORTANT] In this lesson, you will master:

  1. 1. What is a Scheduling System?: Building intuition behind 1. what is a scheduling system?.
  2. 2. Requirements & Goals: Building intuition behind 2. requirements & goals.
  3. 3. Capacity Estimation: Building intuition behind 3. capacity estimation.

1. What is a Scheduling System?

Imagine trying to organize a dinner party with five friends. Alice works late on Tuesdays, Bob has soccer on Wednesdays, Charlie is free only after 8 PM, and Dave is traveling every other weekend. Finding a common time can be a logistical nightmare. Now, scale that problem up to a global workforce of 100,000 employees trying to book thousands of meeting rooms, virtual calls, and collaborative sessions every single day. That is the monumental challenge solved by a Scheduling System.

A Scheduling System allows users to book time slots, invite others, and manage recurring events. It is the invisible engine powering the modern professional world, sitting at the core of productivity tools like Google Calendar, Outlook, and Calendly.

[!TIP] The Hard Part: It’s not just storing static dates in a database. It’s about efficiently answering dynamic, cross-user queries like: “When are all 5 participants free next Tuesday?” This is fundamentally an intersection problem that requires specialized algorithms and data structures far beyond a simple SELECT query.

Real-World Examples

  • Google Calendar: Personal and Enterprise scheduling at massive scale.
  • Calendly: External booking system optimizing for availability intersection.
  • Airbnb: Booking property availability, blending scheduling with e-commerce constraints.

2. Requirements & Goals

Functional Requirements

  1. Create Event: Book a time range ([Start, End]).
  2. Conflict Detection: Prevent double-booking for the same resource (User or Room).
  3. Recurring Events: “Daily Standup at 10 AM”.
  4. Availability Search: Find common free slots for multiple users.

Non-Functional Requirements

  1. Read Heavy: Users view calendars much more often than they create events.
  2. Latency: Loading a month view should be < 200ms.
  3. Consistency: Critical. You cannot double-book a meeting room.

3. Capacity Estimation

  • Users: 1 Billion.
  • Events: 5 events/user/day.
  • Storage:
  • Events are small text.
  • 1B users * 5 events * 100 bytes = 500GB/day.
  • High Volume: We need Sharding.

4. System APIs & Anatomy of a Request

Anatomy of an Event Model

A calendar event isn’t just a string. It is a structured payload that must capture recurrence, timezone context, and attendee relationships.

{
  "event_id": "evt_998877",
  "calendar_id": "user_123", // Key for sharding
  "title": "Quarterly Planning",
  "time": {
    "start_utc": "2023-10-27T10:00:00Z",
    "end_utc": "2023-10-27T11:00:00Z",
    "timezone": "America/New_York" // Critical for UI display
  },
  "recurrence": "FREQ=MONTHLY;BYMONTHDAY=1", // RFC 5545
  "attendees": [
    { "user_id": "user_456", "status": "accepted" },
    { "user_id": "user_789", "status": "pending" }
  ]
}

Create Event

POST /v1/events

Body is the event model above.

Find Availability

POST /v1/free-slots
{
  "users": ["user_123", "user_456"],
  "range_start": "2023-10-27T09:00:00Z",
  "range_end": "2023-10-27T17:00:00Z",
  "duration_minutes": 60
}

5. Database Design & Storage

Handling Time Zones

Always store time in UTC. Never store local time strings like “10:00 AM EST” because Daylight Saving Time (DST) changes, geopolitical boundaries shift, and users travel. Convert to the User’s Local Time exclusively on the Client (Frontend) right before rendering.

Schema (Relational)

We need ACID compliance for strict conflict checks. You cannot afford to have two executives double-book the only boardroom because of eventual consistency.

CREATE TABLE events (
  event_id UUID PRIMARY KEY,
  calendar_id UUID, -- Shard Key
  start_time TIMESTAMP,
  end_time TIMESTAMP,
  rrule VARCHAR(255), -- Recurrence Rule
  INDEX idx_time (calendar_id, start_time, end_time)
);

Recurring Events (The “Infinite Row” Problem)

Consider a daily standup meeting. Do NOT create 365 rows for a year’s worth of meetings, and definitely don’t create infinite rows for a meeting with no end date.

  1. Store One Row with an RRULE (e.g., FREQ=DAILY;BYDAY=MO,TU,WE,TH,FR).
  2. Read Time: The application logic “expands” this rule to generate virtual event instances for the specific viewport the user is looking at (e.g., “This Week”).
  3. Expansion Limit: Usually we limit recurring event expansion to a set window (like 2-5 years in the future) to save processing power.
  4. Exceptions: If you move one instance of a recurring meeting (e.g., moving this Tuesday’s standup to 11 AM), store a separate “Exception Event” row that links to the parent recurrence and overrides that specific instance.

6. High-Level Design

High-Level Architecture: Scalable Scheduling & Availability Pipeline.

System Architecture: Google Calendar Engine
Interval Tree Search | Sharded SQL Storage | RRULE Expansion Cache
Booking Write Path
Availability Read Path
Consistency Guard
Clients
Application Services
Metadata / Cache
Sharded Persistence
Calendar Svc
CRUD Events
RRULE Expander
Free/Busy Svc
Interval Tree
O(log N + K)
Redis
Expanded View Cache
(1-Year Window)
SQL Shards
Shard 1
User IDs 0-99k
Shard 2
User IDs 100k-199k
...
Kafka Queue
Async Notifications
Create Event
/find-free-slots
Write (Critical Transaction)
Cache Read
  1. Calendar Service: The main orchestrator for event lifecycle (CRUD). It contains the RRULE Expander logic to turn a single “Weekly” rule into actual dates for the viewer.
  2. Free/Busy Service (Availability Engine): A specialized high-performance service that uses Interval Trees to find common free slots across multiple users without heavy DB scans.
  3. Expanded View Cache (Redis): Stores the already-expanded recurring events for a 1-year window, ensuring the month-view loads instantly for popular users.
  4. SQL Shards: The horizontal state layer where individual user calendars are persisted, sharded by user_id to ensure linear scalability.
  5. Kafka Queue: Handles asynchronous side effects like sending invitation emails or push notifications.

7. Deep Dive: Conflict Detection

How do we check if [NewStart, NewEnd] overlaps with any existing event?

The Mathematical Logic

Two intervals (S1, E1) and (S2, E2) overlap if and only if:

MAX(S1, S2) < MIN(E1, E2)
  • Logic: The latest start time must be earlier than the earliest end time.
  • Example:
  • Event A: 10:00 - 11:00. Event B: 10:30 - 11:30.
  • Max(10, 10.5) = 10.5. Min(11, 11.5) = 11.
  • 10.5 < 11. Overlap.

SQL Approach

SELECT count(*) FROM events
WHERE calendar_id = 'user_123'
AND start_time < 'NewEnd'
AND end_time > 'NewStart';

If count > 0, reject.

Interval Tree (In-Memory Optimization)

For complex queries (e.g., “Find all free slots for 10 users”), querying the DB is too slow. This logic is offloaded to the Free/Busy Svc shown in our architecture.

[!NOTE] Analogy: The Library Index vs. Scanning Every Shelf Asking the database for overlaps is like walking through a library, taking every single book off the shelf, and checking if it’s a biography published in 1999. It’s an O(N) linear scan. An Interval Tree is like the library’s index card system (or modern search terminal). You can instantly jump to “Biographies -> 1999” without checking the fiction section.

We can cache user schedules in an Interval Tree in memory (Redis with custom modules or application cache).

  • Interval Tree: Designed specifically for overlap queries. O(log N + K) complexity (where N is the number of intervals and K is the number of overlaps).
  • Segment Tree: Stores endpoints. Better for “min/max/sum in range” queries, but can also handle intervals. Interval Trees are generally simpler for pure overlap detection.

Interactive: Finding Common Free Time

When scheduling a meeting for 3 people, we must find the intersection of their free slots.

  • User A: Busy 10-11, 13-14.
  • User B: Busy 09-10, 13-15.
  • Result: 11-13 and 15-17 are potentially free.

[!TIP] Try it yourself: Click “Calculate Intersection” to watch the algorithm scan across all schedules and identify the green free zones.

Multi-User Availability

Click "Calculate" to find common free time.

User A
User B
User C
Common Free Slots

8. Data Partitioning (Sharding)

  • Shard Key: user_id (or calendar_id).
  • As shown in the SQL Shards diagram, Alice’s data lives independent of Bob’s.
  • Pro: Efficient local queries (“Show Alice’s week”).
  • Con: “Find common time for Alice (Shard A) and Bob (Shard B)” requires Scatter-Gather. The App server queries both shards and merges results.
  • For more on Sharding strategies, see Module 07: Data Scaling.

9. Reliability, Caching, & Load Balancing

[!NOTE] War Story: The “Thundering Herd” of Monday 9 AM At a major tech company, a new caching strategy caused the Free/Busy Service to collapse every Monday morning. Why? Because thousands of employees all logged in at 9:00 AM to check their calendars for the week. Since cache keys were generated lazily, the sudden spike of cache misses triggered thousands of simultaneous database queries, overwhelming the SQL shards. The solution was “Cache Pre-warming”: running an offline batch job every Sunday night to populate the Expanded View Cache for the upcoming week for all active employees.

Caching Strategy (Read-Through)

Since calendars are read-heavy, we cache the “expanded” view—computed by the RRULE Expander—in the Expanded View Cache (Redis).

  • Key: user:123:month:2023-10
  • Invalidation: When a user creates/updates an event, we delete the cached key (Write-Through or Cache-Aside).
  • For more on caching patterns, see Module 06: Caching.

Replica Lag & Consistency

If Alice books a room, and Bob tries to book it 100ms later:

  • Bob might read from a stale Replica that doesn’t have Alice’s booking yet.
  • Solution: Critical checks (Conflict Detection) must happen on the Primary Database or use a distributed lock (Redlock).
  • Trade-off: Lower Availability for booking (CP), but high availability for reading (AP).

10. Interactive Decision Visualizer: Conflict Detector

This demo visualizes how a system detects overlaps.

  • Timeline: Represents a day (09:00 - 17:00).
  • Blue Blocks: Existing meetings.
  • Ghost Block: The meeting you are trying to book.

[!TIP] Try it yourself: Drag the slider to move the “New” event. Notice how it turns RED when colliding with an existing blue block.

Booking Availability Check

Drag the slider. Formula: Max(S1, S2) < Min(E1, E2)

09:00
11:00
13:00
15:00
17:00
New

11. System Walkthrough: The Life of a Booking

Let’s trace what happens when Alice books a meeting room.

Step 1: User Action

  • Alice attempts to book Room A for 14:00 - 15:00.
  • POST /events: 
      {
"calendar_id": "room_a",
"start": "14:00",
"end": "15:00"
  }

Step 2: Validation (Application Layer)

  • Calendar Svc converts times to UTC.
  • Validates constraints (Start < End, Duration < 24h).

Step 3: Conflict Check (DB Layer)

  • The Service executes a transactional check against the SQL Shard responsible for room_a. ```sql BEGIN; – Lock room row or index range to prevent concurrent bookings SELECT 1 FROM events WHERE calendar_id = ‘room_a’ AND start_time < ‘15:00’ AND end_time > ‘14:00’ FOR UPDATE;

– If result is empty, proceed. INSERT INTO events …; COMMIT; ```

Step 4: Cache Update

  • Invalidate the Redis cache for room_a’s view. 
      DEL cache:room_a:month:2023-10

Step 5: Notification

  • Publish EventCreated to Kafka.
  • Notification Service sends emails to attendees.

12. Requirements Traceability Matrix

Requirement Architectural Solution
Availability Search Interval Tree (In-Memory) for fast O(log N) intersection.
Consistency SQL Transaction with Overlap Logic (Max(S)<Min(E)).
Recurring Events RRULE storage (compact) + Read-time expansion.
Scalability Sharding by User/Calendar ID.
Low Latency Redis Cache for pre-expanded monthly views.

13. Follow-Up Questions: The Interview Gauntlet

I. Data Structures & Algorithms

  • Why Interval Tree over Segment Tree? Interval Trees are optimized specifically for finding all overlapping intervals. Segment trees are better for aggregate queries (e.g., “How many meetings at 1pm?”).
  • RRULE Complexity: How do you handle “Every 3rd Tuesday of the month”? Use an RFC 5545 parser library. Do NOT re-implement this logic.

II. Database

  • Why not NoSQL (DynamoDB)? Conflict detection requires conditional writes based on other rows (range query). DynamoDB transaction support is limited for range overlaps without complex indexing. SQL is cleaner for this constraint.
  • Archival: Move events older than 1 year to Cold Storage (S3/Parquet).

III. System Design

  • Hot Spot: What if a public calendar (e.g., “Company Holidays”) has 1M subscribers?
  • Solution: Cache heavily. Use CDN for static calendars. Do not query DB for every user.
  • Timezones: Always store UTC. Store the User’s Timezone Preference separately to display correctly (e.g., handling Daylight Savings Time transitions).

14. Summary: The Whiteboard Strategy

If asked to design Google Calendar, draw this 4-Quadrant Layout:

1. Requirements

  • Func: Create, View, Search (Free/Busy).
  • Non-Func: Consistency (No Overlap), Read Heavy.
  • Scale: 1B Users.

2. Architecture

[Client] → [LB] → [Calendar Svc]
↙ ↘
[Redis Cache] [Free/Busy Svc]
(Month View) (Interval Tree)
↓
[SQL Shards]

* Sharding: By User ID.
* Cache: Expanded RRULE views.

3. Data & API

Events: (id, cal_id, start, end, rrule)
API: POST /events, GET /free-slots
Storage: UTC Timestamps.

4. Algorithms

  • Overlap: Max(S1, S2) < Min(E1, E2).
  • Interval Tree: For fast memory lookups.
  • RRULE: Store rule, expand on read.

Return to Specialized Systems