OYO / Airbnb HLD: Find Places Near Me, Free for My Dates

"Design Airbnb." Two questions hide inside it, and they're both unusual. The first is "what's near me?" — find listings around a point on Earth, fast, out of tens of millions. A database can index a number or a string, but "close to these coordinates" is neither, and WHERE lat BETWEEN ... AND lng BETWEEN ... is a slow, wrong box. The second is "is it free for my dates?" — the same date-range, no-double-booking problem as a hotel, now a filter on the search. Solve geospatial search and date availability and you've solved Airbnb; the rest is profiles and photos.

The keystone is a single trick that turns "near me" from a geometry problem into a string-prefix lookup: the geohash.

Let's start nowhere near a computer

Picture a city directory organized by a grid of neighborhood squares. To find cafés near you, you don't read every entry in the country — you flip to your square (and the eight around it) and read only those. Each address is filed under a short square-label, and places in the same square share that label.

That label is a geohash: encode a latitude and longitude into a short string, and two points that are physically close get the same prefix. Suddenly "find listings near here" is WHERE geohash LIKE '9q8yy%' — a plain indexed prefix scan, the thing databases are fastest at. The grid square is the unit of search, and the whole location problem collapses into string matching.

Where this exact shape shows up

• Airbnb, OYO, Uber, Yelp, Zomato, Tinder — anything with "near me" runs on a geospatial index (geohash, quadtree, S2, or H3).
• "Stores within 5km", "drivers nearby", delivery radius — the same prefix/cell lookup.
• The date-availability half is the hotel-management and movie-booking reservation problem, now a search filter.

Step 1 — Functional requirements (sentences first)

• A guest searches listings near a location, filtered by dates (and price, guests, …), ranked.
• A guest books a listing for a date range; it must never be double-booked.
• A host lists a property (location, price, calendar) and manages bookings.
• Guests and hosts leave reviews.

The two hard verbs are "searches near a location, filtered by dates" and "books without double-booking." The rest is CRUD.

Step 2 — Non-functional requirements

• Fast geospatial search. "Listings near here" over tens of millions, in tens of milliseconds. The dominant query.
• No double-booking — ever. Two guests requesting overlapping dates: exactly one wins. Correctness, not best-effort.
• Availability correctness. A listing shown as free for your dates really is free; back-to-back stays don't falsely clash.
• Read-heavy. Far more searching and browsing than booking, so search must cache and scale independently of the booking path.
• Scalable + available. Sharded by geography/host; a search outage mustn't take down booking.

Listing them is the easy half; the design only earns them if it fulfills them:

Every trade-off below is chosen to keep one of these.

Step 3 — Location search: the geohash

Encode a point by repeatedly halving the world — is the longitude in the east or west half? the latitude north or south? — interleaving the bits and writing them out in base-32. Each character narrows the box; a shared prefix means a shared box.

package dev.fiveyear.rental;
 
/**
 * Geohash: encode (lat, lng) into a base-32 string by interleaving longitude and
 * latitude bits, narrowing the world in half at each step. The payoff is the
 * whole reason it exists: points that are physically near each other share a
 * long string prefix, so "find listings near here" becomes a prefix range scan.
 */
public final class GeoHash {
    private static final String BASE32 = "0123456789bcdefghjkmnpqrstuvwxyz";
 
    public static String encode(double lat, double lng, int precision) {
        double latLo = -90, latHi = 90, lngLo = -180, lngHi = 180;
        StringBuilder hash = new StringBuilder();
        boolean even = true;            // geohash starts with a longitude bit
        int bit = 0, ch = 0;
        while (hash.length() < precision) {
            if (even) {                 // bisect longitude
                double mid = (lngLo + lngHi) / 2;
                if (lng >= mid) { ch = (ch << 1) | 1; lngLo = mid; } else { ch <<= 1; lngHi = mid; }
            } else {                    // bisect latitude
                double mid = (latLo + latHi) / 2;
                if (lat >= mid) { ch = (ch << 1) | 1; latLo = mid; } else { ch <<= 1; latHi = mid; }
            }
            even = !even;
            if (++bit == 5) {           // 5 bits -> one base-32 char
                hash.append(BASE32.charAt(ch));
                bit = 0; ch = 0;
            }
        }
        return hash.toString();
    }
 
    private GeoHash() {}
}

More precision (a longer string) means a smaller box: 5 characters is roughly a few kilometres, 7 is a neighbourhood, 9 is a house. To search, encode the query point to the precision that matches your radius and prefix-match listings.

Step 4 — Availability: a date-range filter

The second filter is the hotel problem: a listing is free for your stay iff no existing booking overlaps it, with ranges kept half-open [checkin, checkout) so a guest leaving the 14th and another arriving the 14th don't collide.

package dev.fiveyear.rental;
 
import java.time.LocalDate;
import java.util.List;
 
/** A booking occupies a half-open date range [start, end) — checkout day is free. */
record DateRange(LocalDate start, LocalDate end) {
    boolean overlaps(DateRange other) {
        return start.isBefore(other.end) && other.start.isBefore(end);
    }
}
 
/** A listing carries its geohash (for location search) and its booked ranges. */
record Listing(String id, double lat, double lng, String geohash, List<DateRange> bookings) {
    boolean availableFor(DateRange req) {
        return bookings.stream().noneMatch(b -> b.overlaps(req));
    }
}

That overlaps one-liner is the entire availability rule, and the half-open comparison (isBefore, not !isAfter) is what makes back-to-back stays legal — the single most common bug in reservation code.

Step 5 — Marrying the two filters

Search is the intersection: a geohash prefix narrows to a place, then availability drops anything booked for the dates, then you rank what's left.

package dev.fiveyear.rental;
 
import java.util.ArrayList;
import java.util.List;
 
/**
 * Search marries the two filters: a geohash prefix narrows to a place, and the
 * availability check drops anything booked for the requested dates. (Real geohash
 * search also queries the 8 neighbor cells to catch listings just across a cell
 * boundary — the one gotcha to mention out loud.)
 */
public class SearchIndex {
    private final List<Listing> listings = new ArrayList<>();
 
    public void add(String id, double lat, double lng, List<DateRange> bookings) {
        listings.add(new Listing(id, lat, lng, GeoHash.encode(lat, lng, 9), bookings));
    }
 
    public List<String> search(double lat, double lng, int precision, DateRange req) {
        String cell = GeoHash.encode(lat, lng, precision);
        List<String> out = new ArrayList<>();
        for (Listing l : listings) {
            if (l.geohash().startsWith(cell) && l.availableFor(req)) out.add(l.id());
        }
        return out;
    }
}

The order matters for speed: the geohash prefix is an indexed narrowing that cuts the candidate set from millions to a handful; only then do you run the cheaper availability check on that handful. Coarse-but-indexed first, fine-but-scanned second.

Step 6 — The data model, and which datastore

Which datastore — and why it isn't a default. Listings and bookings want a relational database, and earn it: booking is a transaction that must enforce no overlapping range per listing, and Postgres does this natively with an EXCLUDE constraint over a daterange (a GiST index that rejects any insert overlapping an existing booking — double-booking made impossible at the storage layer). The geohash is just an indexed column for the prefix scan; at large scale you graduate to a purpose-built geo index (PostGIS, S2/H3, or Elasticsearch geo). And hot searches sit behind a cache, because the same "places in Goa next weekend" query repeats endlessly. Relational for the money-and-correctness data, a geo index for location, a cache for the read storm.

Step 7 — Booking without double-booking

Search is read-heavy and forgiving; booking is the opposite — it must be exactly once. Two guests hitting "Reserve" on the same listing for overlapping dates is the race, and the fix is the same atomic check-then-write as every reservation system: do the overlap check and the insert in one transaction, with the database as the referee.

The elegant version pushes the rule into the schema — the EXCLUDE constraint above means the second overlapping INSERT simply fails, no application locking needed. The portable version takes a row lock on the listing, re-checks for overlap, then inserts. Either way the guarantee is the same one the movie-booking and hotel designs make: the winner is decided by the database, not by hope. Search may show a listing as free a second before someone books it — that's fine; the booking transaction is the source of truth, and the loser gets a clean "just taken, try another."

Step 8 — Trade-offs (each one keeping an NFR)

The complete implementation

The pieces above are the engine. Here's the driver that proves them — the geohash validated against well-known cities, neighbours sharing a prefix, half-open overlap, and search marrying location with availability:

package dev.fiveyear.rental;
 
import java.time.LocalDate;
import java.util.List;
 
public class Main {
    public static void main(String[] args) {
        // geohash validates against well-known values: SF -> "9q", NYC -> "dr"
        String sf  = GeoHash.encode(37.7749, -122.4194, 7);
        String nyc = GeoHash.encode(40.7128, -74.0060, 7);
        assertTrue(sf.startsWith("9q"), "San Francisco geohash starts 9q (got " + sf + ")");
        assertTrue(nyc.startsWith("dr"), "New York geohash starts dr (got " + nyc + ")");
 
        // nearby points share a long prefix; a far one shares nothing
        String a = GeoHash.encode(37.7749, -122.4194, 7);
        String b = GeoHash.encode(37.7751, -122.4192, 7);   // ~30m away
        assertTrue(a.substring(0, 5).equals(b.substring(0, 5)), "neighbours share a 5-char cell");
        assertTrue(nyc.charAt(0) != sf.charAt(0), "SF and NYC differ in the first char");
 
        // date overlap: half-open, so checkout day frees the room
        DateRange stay = new DateRange(LocalDate.of(2026, 7, 10), LocalDate.of(2026, 7, 14));
        DateRange backToBack = new DateRange(LocalDate.of(2026, 7, 14), LocalDate.of(2026, 7, 16));
        DateRange clash = new DateRange(LocalDate.of(2026, 7, 12), LocalDate.of(2026, 7, 13));
        assertTrue(!stay.overlaps(backToBack), "back-to-back stays don't overlap");
        assertTrue(stay.overlaps(clash), "an enclosed stay overlaps");
 
        // search marries location + availability
        SearchIndex idx = new SearchIndex();
        idx.add("sf-free", 37.7749, -122.4194, List.of());
        idx.add("sf-booked", 37.7751, -122.4192, List.of(stay));     // booked over the requested dates
        idx.add("nyc", 40.7128, -74.0060, List.of());
 
        DateRange req = new DateRange(LocalDate.of(2026, 7, 11), LocalDate.of(2026, 7, 13));
        List<String> hits = idx.search(37.7749, -122.4194, 5, req);
        assertTrue(hits.contains("sf-free"), "free SF listing is returned");
        assertTrue(!hits.contains("sf-booked"), "booked SF listing filtered out by dates");
        assertTrue(!hits.contains("nyc"), "NYC listing filtered out by location");
 
        System.out.println("ALL RENTAL ASSERTIONS PASSED");
    }
 
    static void assertTrue(boolean c, String m) { if (!c) throw new AssertionError(m); }
}

Step 9 — Only now, the boxes

The split to notice: a search service (geohash + dates, cache in front, reading a geo index) and a booking service (the transactional no-double-book write) are separate. Searching is read-heavy and cacheable; booking is write-correct and rare. Keeping them apart lets each scale — and fail — on its own.

Step 10 — Scaling the design, one bottleneck at a time

• Search dominates → put a cache in front (the same "Goa next weekend" query repeats), then read replicas of the geo index.
• The geo index grows → move from a geohash column to a dedicated geo store (Elasticsearch / S2 / H3), sharded by region so a city's listings live together.
• Bookings need strong consistency → keep them on a relational primary, sharded by listing/host; a booking only ever touches one listing's rows, so no cross-shard transaction.
• Hot destinations → a popular city is a read hotspot; cache and replicate its search results, and rate-limit the rare write contention per listing.

The headline: search scales by caching and a sharded geo index; booking scales by sharding per listing — two planes, two strategies.

Step 11 — When a piece fails: designing for failure

• The search cache or geo index degrades → it's an optimization; fall back to the slower geo query on the primary, or a wider geohash scan. Browsing slows; it doesn't stop.
• The booking DB is the source of truth → it must stay correct, so it gets a replica + failover; during a blip, writes pause rather than risk a double-book. Correctness over availability, on the write path only.
• Search says "free" but it's just been booked → the booking transaction is the referee: the second guest's insert is rejected by the EXCLUDE constraint and gets a clean "just taken." Stale search is acceptable; a double-booking is not.
• A payment or notification lags → async and retryable; the reservation holds the room while they catch up. The optimization degrades; the truth (the booking) stands.

The interview corner

• "How do you search by location?" A geohash: encode lat/lng so nearby points share a prefix, then prefix-match — and query the 8 neighbour cells too, for boundaries.
• "Why not lat/lng BETWEEN?" A bounding box scans and ranks poorly; a geohash prefix is a single indexed range scan and groups truly-near points.
• "How do you stop double-booking?" An atomic, per-listing no-overlap check — ideally a Postgres EXCLUDE constraint over a daterange, so the overlapping insert simply fails.
• "Search showed it as free, then it got booked." Fine — search is best-effort and cached; the booking transaction is the source of truth and rejects the loser cleanly.
• "How does it scale?" Two planes: search via cache + a sharded geo index; booking via a relational primary sharded per listing.

Where to go from here

• The date-availability core in one class is the hotel-management LLD; the atomic reservation at scale is the movie-booking HLD.
• New to system design? The rookie's guide to HLD walks the method this article follows.