#7 Concurrency/Scheduling
Google Calendar
Store events and recurring meetings for millions of users, find free time across many calendars, and never double-book a room.
What is being asked
Design a calendar: users create one-off and recurring events, invite others, see busy times, book rooms and get reminders, across time zones.
Requirements
Functional
- Create, update and delete events; recurrence such as "every Tuesday until June", with exceptions.
- Invitations with accept and decline; a free/busy view across people.
- Reminders by notification or email.
Non-functional
- Reads far outnumber writes: people open their week view constantly.
- A room must not be booked twice for overlapping times.
- Correct through daylight-saving changes.
Design
- An event row stores the organiser, start and end in UTC, the original time zone, and for a series a recurrence rule. A series is one row, not one row per occurrence; exceptions ("this week only, move to 3 pm") are stored separately.
- To show a week, the service loads the user's one-off events in range plus their recurring rules, and expands the rules for that range only.
- An invitation creates a per-attendee record pointing at the organiser's event, so a change by the organiser is seen by everyone.
- Free/busy is served from a per-user cache of busy intervals, rebuilt when that user's events change.
- A scheduler places upcoming reminders on a time-ordered queue and a worker sends them when due.
Key decisions and trade-offs
- Expand on read, not on write. Storing every occurrence of "every day forever" is impossible; expanding rules for the viewed range is cheap.
- Rooms need strong consistency. Booking a room is a transaction with an overlap check, or an exclusion constraint in the database, so two simultaneous bookings cannot both succeed.
- Time zones. Store the zone name with a recurring event: "9 am every Monday" must stay at 9 am local time after a clock change, which changes its UTC time.
- Shard by user, since nearly every query is "my events in this range".
Follow-up questions
- How do you find the first slot when eight people and a room are all free?
- What happens to attendees when the organiser's account is deleted?
- How would you sync with an external calendar that only supports polling?
- How do you send a reminder exactly once if a worker crashes mid-send?