Say Goodbye to Memory Overloads: The Low Level Design of On-The-Fly Recurring Events in Google Calendar

I recently encountered an interesting problem while coding Google Calendar: How do you manage recurring events?

You know, events which need to occur daily, weekly, or monthly. Here is an example use case:

1. You join a team standup every day at 9 AM.
2. To keep track of this, you set up a recurring Google Calendar Event (i).
3. On a particularly busy day, the standup is delayed to 10 AM (ii).
4. After a few late standups, your team decides to hold standups at 10 AM every day(iii).

Here are the corresponding diagrams:

(i) A simple recurrence relation in Google Calendar

(ii) A singular update in Google Calendar

(ii) A recurring update in Google Calendar

If you had to write the software to allow recurring events, as shown above, how would you go about it?

The most straightforward algorithm is creating N events for a single recurring event. You could tie a thread through the events using a linked list data structure.

This has the following disadvantages.

1. You now have limited memory to represent an infinitely recurring event. Sure, you could limit the event count. You could even try storing part of it in memory and the rest on disk. But at the end of the day, that is a LOT of memory.
2. A recurring event creation (i) brings your system down.
3. A recurring update (iii) also brings your system down.

We must support an infinite number of events with finite resources. That sounds impossible! To find a solution, we must dig into the behaviors of our system.

1. Recurring events are very similar to each other. Their only varying property is their date of occurrence.
2. These events have a predictable difference in their date of occurrence.
   Ex: The first Monday of every month.
3. They may be updated singularly(ii) or entirely(iii).
4. We must return a set of recurring events for a selected date range sent to our Calendar API.

And then it hits you: How about generating events on the fly?!

Core Idea: Generating calendar events for a selected date range

All we need to generate events is a blueprint of the recurring event. As long as we know the start time of the recurrence, we can generate events in any date range.

This is very similar to how an object is an instance of a class. Here, an event is an instance of a recurrence.

For singular and recurring updates, we use the following two operations:

A. When performing a singular update, we break the existing thread into three new threads, with a single node for the singular update.

A. Singular update creates three separate recurrence threads

B. In case of a recurring update, we break the existing thread into just two threads.

B. Recurring update creates two separate recurrence threads

Algorithm completum! Time to CODE!

---

Catch us next week for part two of this problem, where we describe how to code Google Calendar with all its design challenges!