Snap Map Design

# Snap Map Design\n\n---\n\n## 0) Problem Restatement\nDesign a real-time location sharing and discovery platform like Snap Map. The system should allow millions of users to broadcast their live location to friends and discover trending geographic hotspots on a global map. Core challenges include handling 300K+ location writes/sec, efficient geospatial clustering for hotspots, battery-efficient client updates, and strong privacy controls (Ghost Mode, custom visibility).\n\n---\n\n## 1) Requirements\n\n### 1.1 Functional\n- Live Location Sharing: Users share GPS coordinates with friends in real-time.\n- Friend Map View: See friend pins on a map, tap for details.\n- Hotspot Clusters: Aggregated, anonymous clusters of user activity on the map.\n- Ghost Mode: Hide your location from all friends temporarily.\n- Custom Visibility: Share with specific friend lists, not everyone.\n- Time-Limited Sharing: Auto-expire location shares after 15m, 1h, or 8h.\n- Story Heatmap: Public snaps visible on the map at landmark locations.\n\n### 1.2 Non-Functional\n- Low Latency: Location updates visible to friends within 2 seconds.\n- High Scalability: 300M DAU, 100M concurrent location sharers.\n- Battery Efficiency: Adaptive polling, not constant GPS drain.\n- Privacy: Granular controls, no location stored after session ends.\n- Availability: 99.99% uptime for location services.\n\n### 1.3 Scale Estimates\n- DAU: 300 million.\n- Concurrent sharers: 100 million.\n- Update frequency: Every 5 seconds per sharer.\n- Write throughput: 100M / 5s = 20M writes/sec (peak: 300K/sec per region).\n- Friend list reads: 500M reads/sec (users panning the map).\n- Hotspot clusters: 10M cluster computations/sec at zoom levels.\n\n### 1.4 API Design\n- Start Share: POST /v1/location/share — Begin broadcasting location.\n- Update Location: POST /v1/location/update — Push GPS coordinates (every 5s).\n- Get Friends: GET /v1/friends/locations — Fetch current friend locations in viewport.\n- Stop Share: DELETE /v1/location/share — End broadcast immediately.\n- Set Visibility: PUT /v1/location/visibility — Ghost Mode or custom lists.\n- Get Hotspots: GET /v1/hotspots?zoom=5&bbox=... — Clustered activity for viewport.\n\n---\n\n## 2) High-Level Architecture\n\n### 2.1 Components\n- Location Service: Ingests GPS updates, validates, stores in Redis.\n- Geospatial Index: Grid-based indexing (H3 or S2) for spatial queries.\n- Cluster Service: Computes hotspot clusters from raw locations at each zoom level.\n- Presence Service: Tracks who is sharing and their active sessions.\n- Friend Service: Resolves friend lists for visibility filtering.\n- WebSocket Gateway: Pushes real-time location updates to connected clients.\n- Map Tile Service: Renders map tiles with overlaid friend pins and clusters.\n\n### 2.2 Flow Diagram\n``mermaid\nflowchart LR\n U[Client App] -->|GPS fix every 5s| LS[Location Service]\n LS -->|write| Redis[(Redis\nlat/lon + H3)]\n LS -->|notify| WS[WebSocket Gateway]\n WS -->|push update| F[Friend Clients]\n LS -->|trigger| CS[Cluster Service]\n CS -->|read H3 cells| Redis\n CS -->|write clusters| Cache[(Cluster Cache)]\n`\n\n### 2.3 Location Update Flow\n1. Client captures GPS fix, sends POST /v1/location/update with lat/lon.\n2. Location Service validates coordinates, writes to Redis (key: loc:{userId}, TTL: session duration).\n3. Location Service writes to geospatial index (H3 cell at resolution 9).\n4. WebSocket Gateway pushes update to all friends who have this user visible.\n5. Cluster Service reads from geospatial index, recomputes clusters for affected zoom levels.\n\n---\n\n## 3) Detailed Component Design\n\n### 3.1 Location Storage (Redis)\n\nKey Design: Two Redis structures per user:\n- loc:{userId} — Hash with lat, lon, h3, ts, session_id\n- h3:{resolution}:{h3_cell} — Sorted Set of userIds (for spatial queries)\n\nWhy Redis: Sub-millisecond reads, built-in TTL for auto-expiry, Sorted Sets for range queries.\n\nWrite Path:\n1. Client sends location update.\n2. Location Service computes H3 cell (resolution 9 = ~250m hexagon).\n3. Write to loc:{userId} hash (overwrites previous).\n4. Add userId to h3:{res}:{cell} Sorted Set (score = timestamp).\n5. If H3 cell changed, remove from old cell, add to new cell.\n\nRead Path (friend locations):\n1. Get friend list from Friend Service.\n2. Pipeline loc:{friendId} for each friend.\n3. Return only friends with active sessions (TTL > 0).\n\n### 3.2 Geospatial Index (H3)\n\nWhy H3 over Quadtree/Geohash:\n- Fixed hexagon sizes at each resolution (no edge effects like geohash).\n- Hierarchical: parent cell contains all children (natural clustering).\n- Uber open-source, battle-tested at scale.\n\nResolution Strategy:\n- Resolution 7 (~5km): For zoomed-out hotspot view.\n- Resolution 9 (~250m): For friend-level precision.\n- Resolution 12 (~30m): For pinpoint friend location.\n\n### 3.3 Cluster Service\n\nAlgorithm: Grid-based clustering at each zoom level:\n1. For zoom level Z, group all H3 cells at resolution Z into grid buckets.\n2. Count users per bucket.\n3. If count > threshold (e.g., 10 users), render as cluster circle with count.\n4. If count < threshold, render individual pins.\n\nPrecomputation: Maintain cluster counts in Redis clusters:{zoom} hash. Update incrementally when locations change, not full recomputation.\n\n### 3.4 Privacy Controls\n\nGhost Mode:\n- Sets ghost:true in Redis loc:{userId}.\n- Location Service skips WebSocket push for ghost users.\n- Friend Service returns empty location for ghost users.\n\nCustom Visibility:\n- Stored in visibility:{userId} — Set of allowed friend IDs.\n- Friend Service filters friend list against visibility set.\n- Supports: All Friends, Close Friends, Custom List, Nobody.\n\n### 3.5 Battery Optimization\n\nAdaptive Polling:\n- Stationary detection: If GPS delta < 10m over 30s, reduce to 30s intervals.\n- Moving detection: If GPS delta > 50m, use 5s intervals.\n- Background mode: Switch to 30s intervals when app is backgrounded.\n\nCell Tower Fallback: Use cell tower location when GPS is unavailable (saves battery indoors).\n\n---\n\n## 4) Database Schema\n\n### 4.1 PostgreSQL (Persistent)\n\nsessions (active sharing sessions):\n`sql\nCREATE TABLE sessions (\n id UUID PRIMARY KEY,\n user_id UUID NOT NULL REFERENCES users(id),\n duration_minutes INT NOT NULL DEFAULT 60,\n visibility VARCHAR(20) NOT NULL DEFAULT 'all_friends',\n created_at TIMESTAMPTZ NOT NULL DEFAULT NOW(),\n expires_at TIMESTAMPTZ NOT NULL,\n stopped_at TIMESTAMPTZ\n);\n`\n\nvisibility_lists (custom friend lists):\n`sql\nCREATE TABLE visibility_lists (\n session_id UUID NOT NULL REFERENCES sessions(id),\n friend_id UUID NOT NULL REFERENCES users(id),\n PRIMARY KEY (session_id, friend_id)\n);\n``\n\n### 4.2 Redis (Real-time)\n\n| Key | Type | TTL | Purpose |\n|-----|------|-----|---------|\n| loc:{userId} | Hash | Session duration | Current lat/lon/h3/timestamp |\n| h3:{res}:{cell} | Sorted Set | 1 hour | Users in H3 cell (score = timestamp) |\n| clusters:{zoom} | Hash | 5 minutes | Precomputed cluster counts |\n| session:{id} | Hash | Session duration | Session metadata |\n| vis:{userId} | Set | Session duration | Allowed friend IDs |\n\n---\n\n## 5) Scaling Considerations\n\n### 5.1 Horizontal Scaling\n- Location Service: Stateless, scale behind load balancer. Each instance handles a region.\n- H3 Index: Shard by H3 cell prefix. Same cell always routes to same shard.\n- Redis Cluster: Shard by key hash. loc:* and h3:* keys distribute evenly.\n\n### 5.2 Regional Deployment\n- US-East: Handles Americas.\n- EU-West: Handles Europe.\n- APAC: Handles Asia-Pacific.\n- Cross-region: Friend visibility is eventually consistent (500ms lag acceptable).\n\n### 5.3 Hotspot Handling\n- Event hotspots (concerts, sports): Pre-allocate cluster cache slots.\n- Viral sharing: Rate limit location updates per user (max 1/sec).\n- Dense urban areas: Use higher H3 resolution (12 vs 9) to avoid over-clustering.\n\n---\n\n## 6) Trade-offs and Alternatives\n\n### 6.1 WebSocket vs SSE vs Long-Polling\n- WebSocket (chosen): Full-duplex, low latency, server-push capable.\n- SSE: Simpler but one-directional. Cannot receive location updates efficiently.\n- Long-polling: High overhead, not suitable for 5s update frequency.\n\n### 6.2 H3 vs Quadtree vs Geohash\n- H3 (chosen): Hexagonal cells, hierarchical, no edge effects.\n- Quadtree: Good for 2D spatial indexing but square cells create uneven distances.\n- Geohash: Simple but border effects — adjacent geohashes can be far apart.\n\n### 6.3 Redis vs Cassandra vs ScyllaDB\n- Redis (chosen): Sub-ms latency, built-in TTL, Sorted Sets for range queries.\n- Cassandra: Better for write-heavy workloads but higher latency (5-10ms).\n- ScyllaDB: Redis-compatible with better throughput but operational complexity.