Calendar System

Shared Calendars and Scheduling

Design a shared calendar: events that repeat by rule, times that stay right across time zones and daylight saving changes, invitations, free/busy lookups and reminders.

Overview

A calendar stores events: a start, an end, a title, some people. That part is easy. Three things make the problem interesting.

Repeating events. 'Every Tuesday and Thursday at 10:00 until December' is one rule that produces many occurrences, some of which are later moved or canceled. The internet standard for this is iCalendar (RFC 5545) and its recurrence rule, the RRULE. Time. A meeting at 15:00 in New York must stay at 15:00 in New York when the clocks change, which means its time in UTC and in London moves. Many people. An event is shared by its attendees, and 'find 30 minutes when these five people and a room are free' has to read many calendars at once.

This topic designs a generic calendar service. The numbers are interview assumptions.

Questions to ask first

How many users? — 100 million, 50 million a day
Which recurrence patterns? — Daily, weekly, monthly, yearly with the RFC 5545 rule parts; weekly is the most common
Can one occurrence be changed? — Yes: one occurrence, this and following, or the whole series
Time zones? — Every event has an IANA zone such as America/New_York; all-day events have none
Do other apps sync with us? — Yes, over a CalDAV-style interface (RFC 4791)
Reminders? — Push and email, minutes to days before an occurrence

What you will be able to do

Store event times so they survive daylight saving and time zone rule changes.
Store a recurring event as an RRULE and expand it for a window, with runnable code.
Model edits to one occurrence, to this and following, and to the whole series.
Answer free/busy and find-a-time across time zones with an interval merge.
Schedule reminders and keep many devices in sync without losing edits.

Key concepts

RRULE
IANA time zones
Local time plus zone
Daylight saving gaps
Recurrence exceptions
Series split
Free/busy
Interval merge
ETags and sync tokens
Reminder scheduling

Functional requirements

Create, edit and delete events, including all-day events
Repeat events by rule, and edit one occurrence, this and following, or all
Invite attendees; they accept, decline or reply tentatively
Show day, week and month views in the viewer's own time zone
Answer free/busy for a set of people and rooms, and suggest meeting times
Send reminders before each occurrence

Non-functional requirements

A week view loads in under 200 ms at p95 (a target we chose)
An occurrence never moves in its own time zone because of a clock change elsewhere
Edits from two devices never silently overwrite each other
Reminders fire within a minute of their time, even at the top of the hour
Events are durable; the service is available 99.95% of the time (a target we chose)

Interview questions

How do you store recurring events?
Why not store everything in UTC?
How do "this", "this and following" and "all" edits work?
How does find-a-time work across time zones?
How do you query a week view quickly?
How do you stop two devices from overwriting each other's edits?
How do you send reminders for series that never end?
How would other calendar apps sync with this service?