Design a Proximity Service (Nearby Friends)

[Mobile App] 
    |
    v
[Load Balancer]
    |
    v
[API Gateway] --> [Auth Service]
    |
    v
[Location Service] --> [User Service]
    |                      |
    v                      v
[Geospatial DB]     [Friend Graph DB]
    |                      |
    v                      v
[Notification Service] <---+
    |
    v
[WebSocket/Push Notifications]

CREATE TABLE user_locations (
    user_id BIGINT PRIMARY KEY,
    latitude DECIMAL(10,8) NOT NULL,
    longitude DECIMAL(11,8) NOT NULL,
    geohash VARCHAR(12) NOT NULL,    -- For spatial indexing
    last_updated TIMESTAMP NOT NULL,
    location_sharing_enabled BOOLEAN DEFAULT false,
    INDEX idx_geohash (geohash),
    INDEX idx_last_updated (last_updated)
);

CREATE TABLE friendships (
    user_id BIGINT,
    friend_id BIGINT,
    status ENUM('pending', 'accepted', 'blocked'),
    location_sharing_level ENUM('none', 'approximate', 'precise'),
    created_at TIMESTAMP,
    PRIMARY KEY (user_id, friend_id),
    INDEX idx_user_friends (user_id, status)
);

-- This scans every user record!
SELECT user_id, latitude, longitude 
FROM user_locations 
WHERE SQRT(POW(latitude - 37.7749, 2) + POW(longitude - (-122.4194), 2)) < 0.1;

San Francisco: 9q8yywe (precision 7 ≈ 153m x 153m)
Nearby location: 9q8yywd (shares 6-char prefix)
Distant location: 9q9p5bc (different prefix)

public class GeohashService {
    private static final String BASE32 = "0123456789bcdefghjkmnpqrstuvwxyz";
    
    public String encode(double lat, double lon, int precision) {
        double[] latRange = {-90.0, 90.0};
        double[] lonRange = {-180.0, 180.0};
        StringBuilder geohash = new StringBuilder();
        boolean isEven = true;
        
        while (geohash.length() < precision) {
            int bit = 0;
            for (int i = 0; i < 5; i++) {
                if (isEven) { // longitude
                    double mid = (lonRange[0] + lonRange[1]) / 2;
                    if (lon >= mid) {
                        bit = (bit << 1) | 1;
                        lonRange[0] = mid;
                    } else {
                        bit = bit << 1;
                        lonRange[1] = mid;
                    }
                } else { // latitude
                    double mid = (latRange[0] + latRange[1]) / 2;
                    if (lat >= mid) {
                        bit = (bit << 1) | 1;
                        latRange[0] = mid;
                    } else {
                        bit = bit << 1;
                        latRange[1] = mid;
                    }
                }
                isEven = !isEven;
            }
            geohash.append(BASE32.charAt(bit));
        }
        return geohash.toString();
    }
}

-- Find users within ~2.4km (geohash precision 6)
SELECT u.user_id, u.latitude, u.longitude 
FROM user_locations u
WHERE u.geohash LIKE '9q8yyw%' 
  AND u.location_sharing_enabled = true
  AND u.last_updated > NOW() - INTERVAL 1 HOUR;

public class QuadTree {
    private static final int MAX_USERS_PER_NODE = 100;
    
    static class QuadNode {
        double minLat, maxLat, minLon, maxLon;
        List<User> users = new ArrayList<>();
        QuadNode[] children = new QuadNode[4]; // NW, NE, SW, SE
        
        boolean isLeaf() { return children[0] == null; }
        
        void insert(User user) {
            if (isLeaf() && users.size() < MAX_USERS_PER_NODE) {
                users.add(user);
            } else {
                if (isLeaf()) split();
                getQuadrant(user).insert(user);
            }
        }
    }
}

public class LocationUpdatePolicy {
    private static final double MIN_DISTANCE_METERS = 50;
    private static final long MIN_TIME_MS = 30_000;
    private static final double SPEED_THRESHOLD_MPS = 5; // ~11 mph
    
    public boolean shouldUpdate(Location current, Location last) {
        if (last == null) return true;
        
        double distance = haversineDistance(current, last);
        long timeDiff = current.timestamp - last.timestamp;
        
        // Always update if time threshold passed
        if (timeDiff > MIN_TIME_MS) return true;
        
        // Update if moved significant distance
        if (distance > MIN_DISTANCE_METERS) return true;
        
        // Update more frequently if moving fast (driving/transit)
        double speed = distance / (timeDiff / 1000.0);
        if (speed > SPEED_THRESHOLD_MPS && distance > 25) return true;
        
        return false;
    }
}

@Component
public class ProximityNotificationService {
    private final Map<Long, WebSocketSession> userSessions = new ConcurrentHashMap<>();
    
    @EventListener
    public void handleLocationUpdate(LocationUpdateEvent event) {
        Long userId = event.getUserId();
        Location newLocation = event.getLocation();
        
        // Find friends within notification radius
        List<Long> nearbyFriends = findNearbyFriends(userId, newLocation, NOTIFICATION_RADIUS_METERS);
        
        for (Long friendId : nearbyFriends) {
            // Check if this friend wasn't nearby before
            if (!wasPreviouslyNearby(userId, friendId)) {
                sendProximityNotification(friendId, userId, newLocation);
            }
        }
    }
    
    private void sendProximityNotification(Long recipientId, Long friendId, Location location) {
        WebSocketSession session = userSessions.get(recipientId);
        if (session != null && session.isOpen()) {
            ProximityNotification notification = ProximityNotification.builder()
                .friendId(friendId)
                .approximateDistance(Math.round(calculateDistance(recipientId, location)))
                .area(getApproximateArea(location)) // "Downtown SF", not exact coordinates
                .build();
                
            session.sendMessage(new TextMessage(JsonUtils.toJson(notification)));
        }
    }
}

public class GeoShardingStrategy {
    private static final List<String> SHARD_REGIONS = Arrays.asList(
        "us-west", "us-east", "eu-west", "asia-pacific"
    );
    
    public String getShardForLocation(double lat, double lon) {
        if (lat >= 24.0 && lat <= 49.0 && lon >= -125.0 && lon <= -66.0) {
            return lon < -95.0 ? "us-west" : "us-east";
        }
        if (lat >= 35.0 && lat <= 71.0 && lon >= -10.0 && lon <= 40.0) {
            return "eu-west";
        }
        return "asia-pacific";
    }
}

public List<NearbyFriend> findNearbyFriends(Long userId, Location location, int radiusMeters) {
    String primaryShard = getShardForLocation(location.latitude, location.longitude);
    List<String> shardsToQuery = Arrays.asList(primaryShard);
    
    // If near shard boundary, query adjacent shards too
    if (isNearShardBoundary(location, radiusMeters)) {
        shardsToQuery = getAdjacentShards(primaryShard);
    }
    
    return shardsToQuery.stream()
        .flatMap(shard -> queryShardForNearbyFriends(shard, userId, location, radiusMeters).stream())
        .collect(Collectors.toList());
}

public enum LocationSharingLevel {
    NONE(0),           // Not visible to anyone
    APPROXIMATE(1),    // Visible within ~500m accuracy  
    PRECISE(2);        // Exact coordinates
    
    public static class LocationPrivacySettings {
        LocationSharingLevel defaultLevel = NONE;
        Map<Long, LocationSharingLevel> friendOverrides = new HashMap<>();
        boolean shareWithAllFriends = false;
        boolean temporarySharing = false; // 24-hour expiry
        Set<String> blockedAreas = new HashSet<>(); // "home", "work"
    }
}

public class LocationPrivacy {
    private static final double APPROXIMATE_RADIUS_METERS = 500;
    
    public Location approximateLocation(Location exact) {
        // Add random offset within 500m radius
        double radiusInDegrees = APPROXIMATE_RADIUS_METERS / 111320.0; // approx meters per degree
        double angle = Math.random() * 2 * Math.PI;
        double distance = Math.random() * radiusInDegrees;
        
        return Location.builder()
            .latitude(exact.latitude + distance * Math.cos(angle))
            .longitude(exact.longitude + distance * Math.sin(angle))
            .accuracy(APPROXIMATE_RADIUS_METERS)
            .build();
    }
}

-- Automatically delete old location data
CREATE EVENT delete_old_locations
ON SCHEDULE EVERY 1 DAY
DO
DELETE FROM user_locations 
WHERE last_updated < DATE_SUB(NOW(), INTERVAL 30 DAY);

-- User deletion (GDPR Article 17)
CREATE PROCEDURE delete_user_location_data(IN user_id BIGINT)
BEGIN
    DELETE FROM user_locations WHERE user_id = user_id;
    DELETE FROM location_sharing_history WHERE user_id = user_id OR shared_with_user_id = user_id;
    INSERT INTO user_deletion_log (user_id, deleted_at) VALUES (user_id, NOW());
END;