Entrevista de diseño de sistemas: Diseñar un servicio de proximidad para lugares cercanos

Problema y alcance

Diseña un servicio global de búsqueda de lugares cercanos. El catálogo contiene 50 millones de restaurantes, tiendas e instalaciones públicas. Un usuario proporciona una posición actual, un radio de 500 metros a 50 kilómetros, una categoría y un filtro de horario de apertura, y luego recibe los 20 resultados más cercanos. El tráfico de búsqueda alcanza un pico de 200.000 solicitudes por segundo. La creación, reubicación y cierre de lugares alcanzan un pico de 100 actualizaciones por segundo. La latencia de lectura debe mantenerse por debajo de 150 milisegundos en p99.

Este problema trata a los lugares como entidades estáticas que cambian lentamente. Las ubicaciones de conductores, repartidores o amigos segundo a segundo, el emparejamiento (matching) y la asignación exclusiva pertenecen a un sistema diferente de ubicación dinámica. La distancia se refiere a la distancia geográfica sobre la superficie de la Tierra. El tiempo de ruta, la personalización y las subastas de publicidad quedan fuera del alcance central. Todos los recuentos y SLO son suposiciones de entrevista.

El problema central es una consulta de radio bidimensional. Un árbol B normal sobre latitud y longitud no puede saltar directamente a cada fila dentro de un círculo de consulta. El patrón recomendado utiliza primero un índice espacial o una cuadrícula discreta para crear un superconjunto de candidatos, y luego calcula la distancia exacta, filtra, ordena y trunca. Una coincidencia de celda es solo un filtro grueso; compartir una celda o una celda vecina no prueba que un lugar esté dentro del radio.

Qué evalúan los entrevistadores

La primera señal es definir la corrección antes que los componentes. Cada resultado debe estar dentro del radio, pasar los filtros y aparecer en un orden determinista de más cercano a más lejano. El conjunto de candidatos debe cubrir lugares a través de los límites de las celdas, y la distancia exacta debe verificar el resultado grueso. Consultar solo el geohash del usuario pasa por alto un negocio a decenas de metros de distancia al otro lado de un borde de celda arbitrario.

La segunda señal es elegir un índice a partir del patrón de actualización. Los negocios estáticos pueden comenzar con PostGIS GiST, un R-tree o el índice de distancia nativo de una base de datos. Cuando el tráfico de lectura y el enrutamiento global lo justifiquen, los lugares se pueden mapear en celdas H3, S2 o geohash. Simplemente decir “usar Redis GEO” no explica la cobertura del círculo, la resolución, los puntos calientes (hot spots) ni la distancia exacta.

La tercera señal es reconocer el sesgo espacial. Los océanos y las celdas rurales están casi vacíos, mientras que una sola celda del centro de una ciudad puede ser extremadamente caliente. Los rangos uniformes de latitud-longitud no producen shards uniformes. Un diseño útil enruta mediante un prefijo espacial grueso, divide las celdas densas y añade réplicas para las celdas con alta lectura. Las consultas de gran radio cruzan shards, por lo que no siempre se puede asumir que una búsqueda impactará en un solo nodo.

Por último, la paginación, la consistencia y las fallas deben coincidir. Para la paginación por distancia, las coordenadas del usuario, los filtros, la versión del catálogo, la última distancia y el ID del lugar son parte del contrato del cursor. Las actualizaciones o el tiempo de espera de un shard pueden cambiar el conjunto de resultados. Una respuesta sólida declara semántica de instantánea (snapshot) o de mejor esfuerzo (best-effort) y hace que los resultados parciales sean reconocibles.

Preguntas para aclarar antes de responder

¿Las ubicaciones son estáticas o se mueven continuamente? El pico de 100 actualizaciones por segundo admite almacenamiento en caché e indexación asíncrona. Las entidades en movimiento necesitan mayor frescura, un índice optimizado para escritura y consistencia de emparejamiento.
¿“Más cercano” significa distancia geográfica o tiempo de viaje? Este diseño utiliza distancia geográfica. El tiempo de viaje necesita un grafo de carreteras y un servicio de ETA separado, normalmente aplicado a un pequeño conjunto grueso de candidatos.
¿Los resultados deben ser completos o son aceptables 20 candidatos aproximados? Este problema requiere un filtrado de radio correcto y los 20 más cercanos de forma determinista entre los lugares indexados. Las celdas solo deben generar candidatos.
¿Qué tan fresco debe estar el estado de apertura? La ubicación y la categoría pueden tolerar una propagación a escala de minutos. Si el cierre temporal necesita segundos, manténlo en una capa superpuesta separada de TTL corto en lugar de dar al catálogo estático una única promesa mixta.
¿Se requiere paginación profunda? La búsqueda cercana generalmente solo necesita unas pocas páginas. Este diseño limita una sesión de resultados a 100 lugares. Exportar todos los resultados dentro de 50 kilómetros necesita una API asíncrona o de navegación regional.
¿Puede una falla entre shards devolver datos parciales? La API de exploración puede devolver partial=true con regiones faltantes. Un cliente estricto puede fallar y reintentar. Los datos parciales no deben presentarse como el conjunto más cercano completo.

Respuesta en 30 segundos

“Separaría la ruta de escritura del catálogo de la ruta de búsqueda. Los registros de lugares con versiones ingresan al catálogo como fuente de la verdad y actualizan de forma asíncrona un índice espacial. Cada lugar almacena coordenadas exactas, una celda de enrutamiento gruesa y una celda de resolución de búsqueda. Una consulta valida su radio y filtros, luego usa una cobertura H3, S2, geohash o un índice de distancia de PostGIS para obtener un superconjunto de candidatos. Calcula la distancia esférica exacta, filtra y ordena por (distance, place_id) antes de tomar 20.

El prefijo grueso enruta a los shards. Las celdas densas se pueden dividir y una consulta entre celdas visita un número acotado de shards en paralelo antes de una fusión global de top-k. Las claves de caché incluyen las celdas, el segmento de radio, los filtros y la versión del catálogo; un movimiento con versión invalida tanto la celda antigua como la nueva. Un cursor vincula la consulta original y la instantánea del catálogo. Verificaría los límites, la línea de cambio de fecha, los polos, las ciudades calientes, la reubicación, los tiempos de espera de shard y las cachés obsoletas mientras mido la corrección y el p99”.

Análisis detallado paso a paso

Paso 1: Fijar la API, el modelo y los invariantes

La API acepta radios acotados, coordenadas válidas, filtros aprobados y un tamaño de página pequeño. La respuesta incluye la distancia calculada, la versión del catálogo, la completitud y un cursor de continuación.

text

GET /v1/places/nearby?lat=&lng=&radius_m=&category=&open_at=&limit=&cursor=

Place {
  place_id, lat, lng, search_cell, routing_cell,
  category, status, hours_version, location_version, updated_at
}

Cursor {
  query_hash, catalog_version, last_distance_m, last_place_id
}

Mantén cuatro invariantes: cada resultado satisface el radio y los filtros; la generación de candidatos no puede omitir un punto dentro del círculo; el orden final es (distance_m, place_id); y una versión de ubicación antigua no puede sobrescribir una nueva. Las coordenadas usan un sistema de referencia declarado, rechazan rangos inválidos y usan metros internamente.

Paso 2: Elegir el índice espacial más simple que cumpla el objetivo

Una primera versión puede usar una base de datos relacional con un índice espacial. Una consulta de radio utiliza una forma delimitadora indexable para reducir el conjunto, luego una función de distancia exacta para filtrarlo. La documentación oficial de earthdistance dice explícitamente que la caja indexable contiene algunos puntos fuera de la distancia de gran círculo solicitada, por lo que se requiere una segunda verificación de distancia. Esta regla de superconjunto de candidatos es independiente de un proveedor específico.

Cuando una topología de base de datos no puede manejar el tráfico de lectura global o se necesita un enrutamiento espacial explícito, codifica cada lugar en celdas H3, S2 o geohash de resolución fija. Convierte el círculo de consulta en un conjunto de cobertura de celdas, lee la lista invertida de cada celda, desduplica y refina. La jerarquía de H3 cambia de resolución de manera eficiente, pero la contención geográfica entre celdas padre e hijo tiene consideraciones de aproximación. La verificación exacta de punto a punto aún decide la inclusión.

Una sola resolución fija crea problemas opuestos: las celdas grandes amplifican los candidatos, mientras que las celdas diminutas hacen que una consulta de 50 kilómetros enumere demasiadas celdas. Selecciona de un pequeño conjunto de resoluciones predefinidas según el radio y precalcula esos niveles para cada lugar, o enruta radios grandes a través de un índice más grueso. La amplificación de candidatos, el fanout y las pruebas de carga p99 eligen los niveles.

Paso 3: Ejecutar la búsqueda de candidatos y el top-k global

El servicio de consultas convierte el círculo en celdas candidatas, cubriendo cada celda que se intersecta en lugar de solo el centro. Lee los IDs de lugares y coordenadas filtrados de forma gruesa de cada celda en paralelo bajo un plazo límite general y un presupuesto por shard. Desduplica por place_id, calcula la distancia geográfica exacta, elimina los puntos fuera del círculo y aplica filtros de autorización, estado y categoría.

Cada shard puede devolver su top k local, pero el truncamiento necesita una prueba. Si cada shard ordena por la misma distancia final y devuelve al menos el k global, el elemento k+1 de un shard no puede ingresar al top k global. El agregador fusiona con un max heap de tamaño k. El trabajo es lineal en los candidatos devueltos, con memoria de fusión O(k).

Un radio grande o un centro urbano denso pueden producir demasiados candidatos. El servicio establece un presupuesto de candidatos pero no puede truncar silenciosamente y afirmar exactitud. Puede elegir una cuadrícula más fina, empujar hacia abajo el filtrado de categorías, expandirse en anillos hasta que existan 20 resultados y la distancia mínima posible desde cada región no buscada supere el vigésimo resultado actual, o devolver un error explícito de límite de recursos.

Paso 4: Presupuestar sharding, puntos calientes y capacidad

Mapea los directorios de celdas a shards con un routing_cell grueso, en lugar de particionar aleatoriamente por place_id, lo que transmitiría (broadcast) cada consulta espacial. Un servicio de directorio mantiene la tabla de enrutamiento y la época (epoch). Una consulta usa una época y reintenta ante un cambio de enrutamiento para que una división de celda no pueda crear una brecha.

Si se estima que un registro de índice de búsqueda que incluye ID, coordenadas, campos de filtro y sobrecarga ocupa de 128 a 256 bytes, 50 millones de registros requieren aproximadamente de 6 a 12 GiB antes de la replicación, múltiples resoluciones y sobrecarga de la base de datos. Esta magnitud se puede particionar y servir mediante nodos optimizados para lectura, pero no prueba que ninguna base de datos en particular cumplirá el objetivo.

A 200.000 QPS y un fanout promedio ilustrativo de seis lecturas de celdas, el backend ve alrededor de 1,2 millones de lecturas de celdas por segundo. El almacenamiento en caché y las lecturas por lotes deben reducir las operaciones. Añade réplicas según el calor de lectura y divide las celdas densas en hijas. Fusionar celdas dispersas solo cambia el almacenamiento y el enrutamiento; la cobertura geométrica aún controla la corrección.

Paso 5: Hacer converger escrituras, cachés y consistencia

Después de la validación de propiedad, el servicio de lugares actualiza el registro fuente e incrementa location_version. Un evento de cambio contiene la celda antigua, la celda nueva y la versión. El consumidor del índice escribe la nueva versión en la nueva celda antes de eliminar la celda antigua. Las lecturas desduplican por versión, lo que hace que la reproducción sea segura y evita que una eliminación retrasada permita que prevalezcan datos obsoletos. Un movimiento entre shards expone un retraso de índice acotado y converge por versión en lugar de requerir una transacción distribuida instantánea.

Utiliza dos capas de caché: IDs de candidatos por celda y objetos de lugares completos. Una clave de candidato incluye la versión del índice, la celda, la categoría y el segmento de estado. Una caché de respuesta final también debe incluir un segmento de coordenadas, un segmento de radio, filtros y la versión del catálogo, por lo que generalmente tiene una tasa de aciertos más baja. Las actualizaciones invalidan tanto las celdas antiguas como las nuevas, mientras que un TTL corto acota un evento de invalidación perdido.

Si open_at cambia cada minuto, no purgues todas las cachés espaciales cada minuto. Almacena en caché los candidatos estáticos y las reglas de apertura, luego evalúa las reglas en el momento de la consulta. Los cierres temporales residen en una pequeña capa superpuesta fresca. Por lo tanto, el flujo constante del estado de apertura no reconstruye el índice geográfico.

Paso 6: Definir la semántica de paginación y fallas

El cursor aplica hash a las coordenadas, el radio, los filtros y catalog_version, luego almacena el último (distance_m, place_id). Una llamada a la página siguiente rechaza parámetros de consulta diferentes. Si se admiten instantáneas de corta duración, lee la misma versión del catálogo. Una API de mejor esfuerzo, en cambio, documenta que las actualizaciones concurrentes pueden crear duplicados u omisiones y permite que el cliente desduplique los IDs.

Cada shard recibe un tiempo límite más corto que el objetivo de extremo a extremo de 150 milisegundos. Después de que un shard agota el tiempo de espera, la respuesta no puede llamarse los 20 más cercanos globales porque el shard faltante puede contener lugares más cercanos. Una API de exploración puede devolver partial=true, las celdas faltantes y un cursor de reintento. Un cliente estricto recibe un resultado de no disponible claro. El cortocircuito (circuit breaking) aísla el shard fallido, no todo el índice global.

El despliegue regional debe preferir una réplica de lectura local completa o una partición geográfica. Las políticas transfronterizas rigen los metadatos y la auditoría de los lugares, mientras que incluso las coordenadas comerciales públicas requieren un aprovisionamiento autorizado. La conmutación por error (failover) solo puede usar una región con un índice suficientemente fresco y debe devolver as_of; no puede recurrir a un escaneo de tabla de catálogo durante un incidente.

Paso 7: Verificar con contraejemplos geométricos y fallas

Para datos de prueba pequeños, usa la distancia exacta por fuerza bruta como oráculo. Genera puntos y círculos aleatorios y compara los conjuntos de resultados. Apunta a los bordes y esquinas de las celdas, longitud de 180 grados positiva y negativa, regiones polares, un punto exactamente en el radio, coordenadas duplicadas, cero resultados, posiciones 20 y 21 empatadas, y una reubicación entre celdas. Asegura que no haya falsos negativos, ni puntos fuera del radio, y un desempate estable.

Las pruebas de carga cubren por separado regiones vacías, ciudades normales y un punto caliente extremadamente denso. Mide el fanout de celdas, la amplificación de candidatos, los cálculos de distancia exacta, la tasa de aciertos de caché, p95/p99 de shards, el tiempo de fusión y el p99 de extremo a extremo. Las fallas incluyen una réplica de celda lenta, un cambio de época de enrutamiento, una invalidación perdida, la reproducción del consumidor, un movimiento entre shards interrumpido y la conmutación por error regional.

Realiza el despliegue con consultas en sombra (shadow queries). Envía una pequeña muestra de tráfico tanto al nuevo índice como a una implementación antigua de confianza, luego compara el conjunto de los 20 mejores, el orden, la distancia y la tasa de omisiones. Una mejora de latencia no puede justificar falsos negativos; omitir un lugar cercano correcto es un fallo de corrección del índice.

Respuesta de ejemplo sólida

“Primero delimito esto a la recuperación de lugares estáticos, no al emparejamiento de conductores en movimiento. Un catálogo de lugares almacena coordenadas exactas y una versión de ubicación monotónica, luego emite eventos a un índice espacial. Las lecturas no ordenan toda la tabla mediante una expresión de latitud-longitud. Convierten el círculo en celdas que lo cubren por completo. Puedo comenzar con un índice espacial de PostGIS e introducir H3, S2 o geohash cuando el tráfico global requiera un enrutamiento espacial explícito. Las celdas solo realizan un filtrado grueso; la distancia geográfica exacta decide la inclusión, seguida de una ordenación estable por distancia e ID de lugar.

Una celda gruesa enruta a un shard. Las celdas densas se dividen y las celdas con alta lectura obtienen réplicas. Una consulta lee shards acotados en paralelo, cada uno devuelve un top-k local y el agregador produce el top-k global. El exceso de candidatos desencadena un filtrado más selectivo o una expansión en anillos, nunca un truncamiento silencioso. Los candidatos de celda y los objetos de lugar se almacenan en caché con versiones de índice. Un movimiento invalida ambas celdas y las versiones de ubicación hacen que la reproducción converja.

El cursor vincula coordenadas, radio, filtros, versión del catálogo y la última distancia/ID de lugar. Un tiempo de espera de shard significa que los resultados más cercanos globales no son demostrables, por lo que una API de exploración marca la respuesta como parcial y nombra las celdas faltantes, mientras que una API estricta falla. Para la verificación, la distancia por fuerza bruta es el oráculo. Las comparaciones aleatorias y los casos específicos de bordes de celdas, línea de fecha, polos, empates, movimientos y cambios de enrutamiento prueban la corrección antes de que las pruebas de carga y fallas en ciudades calientes demuestren el p99 de 150 milisegundos”.

Errores comunes

Consultar solo el geohash central → un círculo que cruza el borde de la celda pierde vecinos cercanos → lee cada celda intersectada y verifica la distancia exacta.
Tratar las celdas vecinas como dentro del radio → una esquina lejana de la celda puede exceder el radio → usa la cuadrícula para candidatos y la distancia esférica para la inclusión.
Particionar aleatoriamente por ID de lugar → cada consulta cercana se transmite globalmente → enruta por prefijo espacial grueso, luego divide o replica celdas calientes.
Usar una sola resolución más fina → la precisión de radio pequeño produce un fanout explosivo para radios grandes → usa unos pocos niveles controlados elegidos a partir de mediciones.
Almacenar en caché solo por coordenadas → el radio, la categoría o las versiones de catálogo se contaminan entre sí → coloca el contrato de consulta completo y la versión en la clave.
Eliminar antes de agregar durante un movimiento → una falla del consumidor elimina temporalmente el lugar → escribe la nueva versión primero, elimina la celda antigua después y desduplica por versión.
Llamar a una respuesta “20 más cercanos” después de un tiempo de espera de shard → el shard faltante puede contener resultados más cercanos → marca los datos parciales o haz fallar las solicitudes estrictas.
Probar solo datos de centros urbanos densos → los errores de límites, polares y de regiones dispersas permanecen ocultos → usa un oráculo de fuerza bruta, pruebas basadas en propiedades y contraejemplos geométricos específicos.

Preguntas de seguimiento y respuestas

Pregunta de seguimiento 1: ¿Por qué no usar PostGIS para todo el sistema?

Es una buena primera opción. Una base de datos espacial ya proporciona candidatos de índice correctos y funciones de distancia, por lo que el equipo puede lanzar un sistema confiable con menos componentes. Introduce una cuadrícula discreta y un nivel de búsqueda separado solo después de que el tráfico, el enrutamiento global, el aislamiento de puntos calientes o las mediciones de costos demuestren que la topología de la base de datos no cumple el objetivo. La migración en sombra debe comparar conjuntos de resultados completos, no solo la latencia.

Pregunta de seguimiento 2: ¿Cómo demuestras que la cobertura de celdas no puede perder un lugar dentro del círculo?

Usa la operación de cobertura de círculos o polígonos de la biblioteca en lugar de adivinar un recuento de vecinos. La cobertura puede incluir celdas adicionales, pero debe incluir cada celda que intersecte el círculo. La distancia exacta elimina los falsos positivos posteriormente. Compara con un oráculo de escaneo completo sobre círculos aleatorios, esquinas de celdas, la línea de cambio de fecha y áreas polares. Cualquier falso negativo bloquea el lanzamiento.

Pregunta de seguimiento 3: ¿Qué pasa si una consulta de 50 kilómetros cubre miles de celdas finas?

Cambia a un nivel más grueso precalculado para que el recuento de celdas se mantenga acotado, luego confía en los filtros aplicados en el origen y el refinamiento exacto. La expansión en anillos puede detenerse una vez que existan 20 resultados y la distancia mínima posible de cada región no visitada supere el vigésimo resultado actual. Si una solicitud de radio grande aún excede su presupuesto de recursos, recházala o hazla asíncrona en lugar de buscar silenciosamente en menos datos.

Pregunta de seguimiento 4: ¿Cómo se convertiría esto en un emparejamiento de conductores cercanos?

El problema cambia materialmente. Las ubicaciones de los conductores necesitan escrituras y expiraciones en escala de segundos, un índice particionado por ciudad o celda, y protección contra actualizaciones desordenadas y conductores fantasma. Después de recuperar los candidatos, la clasificación necesita ETA, estado y equidad. La asignación final requiere una actualización condicional con versión o un propietario único para evitar el doble despacho; un índice espacial eventualmente consistente no puede reservar al conductor.

Pregunta de seguimiento 5: ¿El estado de apertura minuto a minuto creará una tormenta de invalidación?

Separa los candidatos espaciales estáticos del estado dinámico. Las cachés de celda contienen IDs, ubicaciones y categorías. Los nodos de consulta evalúan las reglas de apertura para open_at, mientras que los cierres temporales provienen de una pequeña capa superpuesta fresca. Solo los cambios de ubicación o categoría invalidan la caché de candidatos espaciales. Monitorea la frescura de la capa superpuesta y devuelve un estado desconocido o una degradación aprobada por el negocio cuando no esté disponible.