Scheduling Bitmaps Redis Cache

How Google Calendar Finds Common Free Slots Instantly

One "Find a time" click. Behind it: precomputed availability bitmaps, bitwise AND across attendees, timezone normalization, and a scheduling engine that returns results in milliseconds — for millions of users with billions of events.

10 min read Bitmaps · Interval Merging · Redis · Timezones Episode 03
01 · Hook

One button. A surprisingly hard scheduling problem.

You're setting up a meeting with five colleagues across three time zones. You click "Find a time." In under a second, Google Calendar shows you three open slots — everyone's free, the duration fits, and it respects working hours.

At first glance this sounds easy: just check everyone's calendar and find empty time. But at scale, the backend may need to process thousands of events per attendee, handle recurring meetings that expand into hundreds of instances, support real-time edits, normalize time zones, and return results in milliseconds.

The core challenge: A naive approach scans every event for every attendee on every query. With hundreds of millions of users, each with thousands of events — including recurring series — recomputing from raw data every time becomes prohibitively expensive. The system needs a smarter representation of availability.

02 · Problem Statement

Why "Find a Time" is harder than it looks

Scheduling across multiple people is a set intersection problem on time intervals. Finding where N people are simultaneously free requires intersecting N sets of busy intervals. That's straightforward for 2 people with 5 events each. It becomes expensive when:

Scale factors working against you simultaneously

Event volume per user: A power user might have 5,000+ events per year, including recurring series. A weekly all-hands alone expands to 52 instances. A daily standup creates 260. Querying raw events and expanding recurrences on every scheduling request is O(events × attendees) — expensive.

Concurrency: "Find a Time" is triggered whenever anyone edits attendees on a meeting. At Google's scale, that's millions of scheduling computations per minute across all Calendar users worldwide.

Timezone complexity: DST transitions mean that "9:00 AM Monday" is a different UTC timestamp depending on the timezone — and it shifts twice a year. Cross-timezone scheduling must normalize correctly or produce ghost conflicts.

Realtime edits: If User B accepts a meeting invite while User A is in the "Find Time" flow, the suggestions must reflect the updated state. Stale availability is worse than no availability.

At scale: Google Calendar serves hundreds of millions of users. Each "Find Time" query must intersect availability across N attendees without querying hundreds of events per person from the database. The answer: precompute and cache availability as bitmaps.

03 · Architecture

The scheduling engine that makes it instant

The system runs on a precomputed bitmap cache backed by an event store. Instead of querying raw events on every request, availability is precomputed per user per day and stored as a compact bitstring. Finding common free slots becomes a bitwise AND operation — O(bits/64) per attendee. Click any node to inspect it.

scheduling-engine.flow
Click any node to inspect · Packets show a "Find Time" request flowing through the system
04 · Engineering Breakdown

How each component works

Bitmap-based availability tracking

The core insight: instead of storing events as time ranges, precompute a bitstring per user per day. Each bit represents a time slot (e.g., 15 minutes). A 1 means busy; 0 means free. A full day at 15-minute granularity is 96 bits — just 12 bytes per user per day.

Finding common free slots across N attendees becomes: combined = bitmap_A AND bitmap_B AND bitmap_C… Any 0 in the combined bitmap is a shared free window. This is a single CPU instruction per 64 bits — blindingly fast regardless of how many events each person has.

Timezone normalization

All bitmaps are stored in UTC. When a user in New York checks availability for a meeting with someone in London, both bitmaps are fetched in UTC, ANDed together, then the resulting free windows are converted back to each user's local time for display. This means a single cached bitmap works correctly regardless of which timezone the requester is in.

DST transitions are handled at the conversion layer — the UTC bitmap never changes when clocks spring forward. Only the display offset changes.

Recurring event expansion

Recurring events (RRULE in the iCalendar spec) are stored as a single rule, not as individual instances. When computing a bitmap, the Recurring Event Expander generates only the instances that fall within the requested date window. This is far cheaper than storing and querying every instance individually, especially for daily or weekly recurrences over multi-year periods.

Cache invalidation

Bitmaps are cached in Redis with a 15-minute TTL. Any calendar event mutation (create, update, delete, RSVP change) triggers an invalidation of the affected user's bitmap for affected dates. The next "Find Time" query for that user rebuilds the bitmap from the event store and re-caches it.

This "invalidate on write, rebuild on read" strategy ensures correctness: a bitmap is never stale by more than 15 minutes even without explicit invalidation, and it's updated immediately when the system knows a change occurred.

Working hours and preferences

After the raw bitmap intersection, the scheduling engine applies a working hours mask per attendee. Slots outside 9–5 (per user's configured hours) are filtered out of suggestions. This is another bitmap AND: free_slots AND working_hours_mask. The mask is precomputed once and stored alongside the availability bitmap.

05 · Interactive Demo

See the bitmap algorithm in action

Each bit represents a 30-minute slot (8:00 AM – 4:00 PM). Click any bit in User A or User B's row to toggle busy/free. The AND result updates instantly — amber bits are shared free windows where a meeting could be scheduled.

User A
User B
A AND B
1 = Busy  ·  0 = Free  ·  Amber = shared free window  ·  Click to toggle

Why this is fast: At 15-minute granularity, a full work-week (5 days × 13 hours) is 260 bits — just 5 × 64-bit integers. Finding common availability across 10 attendees is 10 × 5 AND operations = 50 CPU instructions. Compare that to iterating and comparing hundreds of event time ranges in a nested loop.

06 · Scale Simulator

How the architecture evolves with user count

Drag the slider to see which components are introduced as the scheduling system scales:

1K users100K10M100MGoogle scale
Availability strategy
DB query
Cache layer
None
Find Time latency
~800ms
At 1K users, direct DB queries work fine. Query each attendee's events, compute overlaps in-memory. Latency is dominated by DB round trips — acceptable at this scale.
07 · Alternative Designs

Why bitmaps instead of interval trees?

Approach Query time Memory Update cost Arbitrary precision?
Naive event scan O(events × attendees) Low Zero Yes
Interval tree (sorted) O(log n + k) Medium O(log n) Yes
Segment tree O(log n) High O(log n) Granularity-limited
Bitmap + cache ✓ O(bits/64) — constant 12 bytes/user/day Invalidate + rebuild Granularity-limited

Interval trees are more precise — they don't lose resolution at 15-minute boundaries. But for "Find a Time," precision below 15 minutes is irrelevant: no one schedules a meeting at 10:07 AM. The bitmap's fixed granularity is a feature, not a bug — it makes the representation compact, cache-friendly, and trivially intersectable.

The real advantage is cacheability: a bitmap for "User A on 2025-06-01" is a stable cache key. It's valid until User A's events on that date change. An interval tree must be rebuilt from raw events on every query — there's no natural cache key for the partial computation.

08 · Interview Questions

How to ace this in a system design interview

09 · Data Model

What gets stored — and in what form

The data model separates durable event storage (Postgres/Spanner) from ephemeral availability caches (Redis). Only the event store is source of truth — the bitmaps are derived data that can always be recomputed. Click any table to explore its design rationale.

← Click a table to inspect its schema

Redis key structure

-- Availability bitmap for a user on a given day (UTC)
SET avail:{userId}:{date_utc} <96-bit string, 15min slots> EX 900

-- Working hours mask (9am–5pm in user's timezone, expressed as UTC bits)
SET workhours:{userId}:{date_utc}:{tz_offset} <96-bit string> EX 86400

-- Bitwise AND of two users' bitmaps (Redis native command)
BITOP AND result_key avail:{userA}:{date} avail:{userB}:{date}

-- Count free slots (BITCOUNT on inverted bitmap)
BITCOUNT avail:{userId}:{date_utc}

-- Invalidate on event mutation (delete + let next read rebuild)
DEL avail:{userId}:{affected_date_utc}

Redis BITOP: Redis has a native BITOP AND command that performs bitwise AND across multiple bitstrings in a single command. This means the intersection of N attendees' bitmaps can happen server-side in Redis without fetching all bitmaps to the application layer — reducing both network overhead and application CPU.

10 · High-Level Design

The full system at a glance

The HLD shows every major service tier and data flow. Toggle layers to focus on a specific part of the system.

Client layer API / Auth Scheduling Engine Storage layer Async / cache miss path
11 · Low-Level Design

Inside a "Find Time" request — step by step

From clicking "Find a time" to receiving suggestions: walk through every method call, cache check, and computation in sequence.

1 / 7
12 · Tradeoffs

Every design decision has a cost

The bitmap approach isn't universally correct — it's optimised for Google Calendar's specific constraints. Use the radar to compare approaches, then explore each decision.

Bitmap + cache Interval merging Naive DB scan
← Previous deep dive
How Slack/Teams Tracks Your Active Status
←