Designing a Proximity Service (Yelp, Google Places)

📌 1️⃣ Introduction

Proximity Service is a key component in many modern applications:

• Yelp: Find nearby restaurants and shops

• Google Places: Return nearby location data for developers

In this lesson, we will design a high-availability, high-performance, scalable proximity service.

🎯 2️⃣ Requirements Analysis

✅ Functional Requirements

1️⃣ Given a user’s location (latitude, longitude) and a search radius, return nearby businesses

2️⃣ Business owners can create, update, delete businesses (updates can appear next day — no real-time requirement)

3️⃣ Users can view detailed business information

🚀 Non-Functional Requirements

• Low latency: Users should get quick responses

• High availability: Handle traffic spikes

• System scale:

  • 100 million DAU

  • 200 million businesses

  • Average QPS ≈ 5,000

🧩 3️⃣ High-Level System Architecture

The system consists of two main services:

1️⃣ Location-Based Service

• Handles proximity queries

• Read-heavy, write-free

• Horizontally scalable (Stateless)

2️⃣ Business Service

• Handles CRUD operations on business data

• Write traffic is low; reads can be optimized with caching

API Design

• GET /nearby

  • Input: latitude, longitude, radius

  • Output: List of nearby businesses

  • Note: Pagination omitted for simplicity; should be included in production

• CRUD API

  • For managing business objects

  • Business detail requires a separate API call

🗃️ 4️⃣ Database Design

Business Table

• Stores detailed business information

• Estimated size ≈ 1~2 TB

Geospatial Index Table

• Columns: geohash + business_id (optional: latitude/longitude)

• Estimated size ≈ 6 GB

• Can fit in memory; use Read Replicas for read scalability

🌍 5️⃣ Geohash — How It Works

Principle:

1️⃣ Alternate binary partitioning of latitude and longitude

2️⃣ Generate a 01 sequence based on whether each value falls into lower/upper half of its range

3️⃣ Every 5 bits → encode to base32 character → Geohash string

4️⃣ Use prefix matching + 8 neighboring grids to query nearby businesses

Benefits:

✅ Fast lookup with simple DB indexing

✅ Works with common relational databases

✅ Naturally supports different search radii through variable Geohash precision

Cautions:

• Must query 8 neighboring grids to avoid missing edge cases

• Grid distortion at high latitudes

🚦 6️⃣ Sample Query Flow

User searches for restaurants within a 500m radius:

1️⃣ Determine appropriate Geohash precision (length 6 ≈ 500m)

2️⃣ Query the current Geohash grid and its 8 neighbors

3️⃣ Retrieve business IDs and coordinates

4️⃣ Calculate actual distance → rank → return results

🧑‍💻 7️⃣ Geohash Encoding Pseudocode (Java Style)

public class GeohashEncoder {

    private static final String BASE32 = "0123456789bcdefghjkmnpqrstuvwxyz";

    public static String encode(double latitude, double longitude, int precision) {
        double[] latRange = { -90.0, 90.0 };
        double[] lngRange = { -180.0, 180.0 };

        boolean isEven = true;
        int bit = 0;
        int ch = 0;
        StringBuilder geohash = new StringBuilder();

        int[] bits = { 16, 8, 4, 2, 1 };

        while (geohash.length() < precision) {
            double mid;
            if (isEven) {
                mid = (lngRange[0] + lngRange[1]) / 2;
                if (longitude > mid) {
                    ch |= bits[bit];
                    lngRange[0] = mid;
                } else {
                    lngRange[1] = mid;
                }
            } else {
                mid = (latRange[0] + latRange[1]) / 2;
                if (latitude > mid) {
                    ch |= bits[bit];
                    latRange[0] = mid;
                } else {
                    latRange[1] = mid;
                }
            }

            isEven = !isEven;

            if (bit < 4) {
                bit++;
            } else {
                geohash.append(BASE32.charAt(ch));
                bit = 0;
                ch = 0;
            }
        }

        return geohash.toString();
    }

    // Example usage
    public static void main(String[] args) {
        String geohash = GeohashEncoder.encode(37.4219999, -122.0840575, 6);
        System.out.println("Geohash: " + geohash);
    }
}

🏁 8️⃣ Summary

This lesson walks through the core design of a Proximity Service:

• Service decomposition (Location vs Business)

• Geohash-based spatial indexing

• Storage optimization

• Scalability considerations (read replicas, caching)

These design patterns are applicable to many real-world applications like Yelp, Google Places, Uber, DoorDash, and other location-based services 🚗📍.