Nine million homes, a whole year, under half a gigabyte

transcript

Nine million homes. Every night of the year. Free or taken. All of it fits in under half a gigabyte. Here's the trick.

Rohan searches Goa for three nights. Is each home free? Ask the calendar service? A big search has tens of thousands of candidates. 14,000 searches a second. That's hundreds of millions of calls a second. So keep a copy instead.

Most homes are one unit. A night is free or taken. One bit. A year is 365 bits. Times more than 9 million listings. About zero point four gigabytes. Small enough to keep in memory.

Order matters. Where first. The map becomes a few geo cells. 9 million become about 2,500. Then when. Three nights is a three-bit mask. One AND, one compare per home. Then the host's rules. Minimum nights, check-in days, guest count. Only the survivors get a total price.

But here's the catch. A copy can be a little stale. Events keep it within about a minute. So two guests could see the same free night. Who decides?

Reserve reads the truth. Each night is inserted with a unique key: listing and night. The first insert succeeds. Booked. The second fails, and that guest sees just booked. No locks needed.

Search fast, on a copy. Decide exactly, on the source. Search reads a copy. Reserve reads the truth.

Full breakdown in the lecture.