Design Google Calendar (Scheduling)

1. What is a Scheduling System?

A Scheduling System allows users to book time slots, invite others, and manage recurring events. It is the core of productivity tools like Google Calendar, Outlook, and Calendly.

[!TIP] The Hard Part: It’s not just storing dates. It’s about efficiently answering: “When are all 5 participants free next Tuesday?” This is an intersection problem that requires specialized algorithms.

Real-World Examples

  • Google Calendar: Personal and Enterprise scheduling.
  • Calendly: External booking system.
  • Airbnb: Booking property availability.

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

Create Event

POST /v1/events
{
  "calendar_id": "user_123",
  "start_time": "2023-10-27T10:00:00Z",
  "end_time": "2023-10-27T11:00:00Z",
  "attendees": ["user_456"],
  "recurrence": "FREQ=DAILY;COUNT=10" // RFC 5545
}

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 in UTC. Convert to User’s Local Time on the Client (Frontend).

Schema (Relational)

We need ACID for conflict checks.

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)

Do NOT create 365 rows for a daily meeting.

  1. Store One Row with an RRULE (e.g., FREQ=DAILY).
  2. Read Time: The application logic “expands” this rule to generate virtual events for the viewport.
  3. Expansion Limit: Usually we limit recurring events to 2-5 years in the future to save processing.
  4. Exceptions: If you move one instance of a recurring meeting, store a separate “Exception Event” row that links to the parent.

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: \(\text{MAX}(S1, S2) < \text{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. 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.
  • 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

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(StartA, StartB) < Min(EndA, EndB)

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. 
    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