Design a Proximity Service: Geo-Hashing, Quadtrees, and Production Pitfalls

// io.thecodeforge — System Design tutorial

// DON'T DO THIS — naive O(n) query
function findNearbyNaive(userLat, userLng, radiusKm, allPois) {
    let results = [];
    for (let poi of allPois) {
        let dist = haversine(userLat, userLng, poi.lat, poi.lng);
        if (dist <= radiusKm) {
            results.push(poi);
        }
    }
    return results;
}
// For 10M POIs, this takes ~500ms per query on a single core.
// At 1000 QPS, you need 500 cores. Not happening.

// io.thecodeforge — System Design tutorial

// Geohash-based proximity query (pseudo-SQL)
// Assume table 'pois' has columns: id, lat, lng, geohash (varchar, indexed)

-- Step 1: Compute user's geohash at precision 6 (~1.2km cells)
-- Step 2: Query POIs with matching prefix
SELECT id, lat, lng, name
FROM pois
WHERE geohash LIKE 'u4pruy%'  -- prefix for user's cell
   OR geohash LIKE 'u4pruz%'  -- neighbor cells (8 neighbors)
   OR geohash LIKE 'u4prv0%'
   -- ... include all 9 cells

-- Step 3: Filter by exact distance (Haversine on small set)
-- This step is optional if cell size is small enough.

-- Index: CREATE INDEX idx_geohash ON pois(geohash);
-- This is a B-tree index, so prefix match is O(log n).

// io.thecodeforge — System Design tutorial

class Quadtree {
    constructor(boundary, capacity) {
        this.boundary = boundary; // {x, y, w, h}
        this.capacity = capacity; // max POIs per node before split
        this.points = [];
        this.children = null;
    }

    insert(point) {
        if (!this.boundary.contains(point)) return false;
        if (this.children === null && this.points.length < this.capacity) {
            this.points.push(point);
            return true;
        }
        if (this.children === null) this.subdivide();
        for (let child of this.children) {
            if (child.insert(point)) return true;
        }
        return false; // shouldn't happen
    }

    query(range, found) {
        if (!this.boundary.intersects(range)) return;
        for (let p of this.points) {
            if (range.contains(p)) found.push(p);
        }
        if (this.children !== null) {
            for (let child of this.children) child.query(range, found);
        }
    }

    subdivide() {
        let {x, y, w, h} = this.boundary;
        let halfW = w / 2, halfH = h / 2;
        this.children = [
            new Quadtree({x, y, w: halfW, h: halfH}, this.capacity),
            new Quadtree({x: x+halfW, y, w: halfW, h: halfH}, this.capacity),
            new Quadtree({x, y: y+halfH, w: halfW, h: halfH}, this.capacity),
            new Quadtree({x: x+halfW, y: y+halfH, w: halfW, h: halfH}, this.capacity)
        ];
        // Redistribute points to children
        for (let p of this.points) {
            for (let child of this.children) child.insert(p);
        }
        this.points = []; // clear parent
    }
}

// Usage:
let tree = new Quadtree({x: -180, y: -90, w: 360, h: 180}, 10);
// Insert 10M POIs...
// Query: find points within 1km of (lat, lng)
let range = {x: userLng-0.01, y: userLat-0.01, w: 0.02, h: 0.02}; // approx 1km
let nearby = [];
tree.query(range, nearby);

// io.thecodeforge — System Design tutorial

// Java ExecutorService example
ExecutorService readPool = Executors.newFixedThreadPool(20); // read queries
ExecutorService writePool = Executors.newFixedThreadPool(5);  // POI inserts

// Submit read tasks to readPool, write tasks to writePool
// This prevents bulk writes from starving reads.

// Also set a timeout on read tasks:
Future<List<POI>> future = readPool.submit(queryTask);
try {
    List<POI> results = future.get(100, TimeUnit.MILLISECONDS);
} catch (TimeoutException e) {
    // Return empty or fallback
    future.cancel(true);
}