Volver

Optimizando búsquedas geoespaciales en Cloudflare Workers: De Haversine a Geohash

Author: Cristian González /

Dev Backend Algorithm Cloudflare Workers Cloudflare D1

Cuando desarrollamos nuestra aplicación de búsqueda de espacios cercanos para desplegarla en Cloudflare Workers con Cloudflare D1 como base de datos, nos enfrentamos a un desafío crítico. La naturaleza serverless de Workers, con sus límites estrictos de tiempo de ejecución y recursos, combinada con las particularidades de D1 (la base de datos SQL de Cloudflare basada en SQLite), requería un enfoque especialmente eficiente para las búsquedas geoespaciales.

Este artículo detalla cómo evolucionamos desde un enfoque inicial basado en la fórmula de Haversine, que resultó problemático en el entorno de Cloudflare, hacia una solución optimizada utilizando el paquete ngeohash que nos permitió cumplir con los requisitos de rendimiento en esta infraestructura serverless.

El problema inicial: La fórmula de Haversine

Inicialmente, implementamos la solución más directa: calcular la distancia entre dos puntos en la superficie terrestre utilizando la fórmula de Haversine. Esta fórmula trigonométrica calcula la distancia entre dos puntos de la Tierra utilizando sus coordenadas (latitud y longitud).

function getDistanceInKm(lat1, lon1, lat2, lon2) {
  const R = 6371 // Radio de la Tierra en km
  const dLat = ((lat2 - lat1) * Math.PI) / 180
  const dLon = ((lon2 - lon1) * Math.PI) / 180

  const a =
    Math.sin(dLat / 2) * Math.sin(dLat / 2) +
    Math.cos((lat1 * Math.PI) / 180) *
      Math.cos((lat2 * Math.PI) / 180) *
      Math.sin(dLon / 2) *
      Math.sin(dLon / 2)

  const c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a))
  return R * c
}

El enfoque inicial era simple:

  1. Obtener todos los espacios de la base de datos D1
  2. Calcular la distancia de cada espacio a la ubicación del usuario
  3. Filtrar aquellos dentro del radio especificado
  4. Ordenar por distancia

Sin embargo, este enfoque presentaba problemas significativos en el entorno de Cloudflare:

Problemas de rendimiento en Cloudflare Workers

Al ejecutar este código en Cloudflare Workers con D1, nos encontramos con varias limitaciones críticas:

  1. Carga computacional excesiva: Calcular la distancia de Haversine para cada registro en D1 es costoso, especialmente cuando la base de datos crece.
  2. Tiempo de ejecución limitado: Cloudflare Workers tiene un límite estricto de tiempo de ejecución de 50ms en el plan gratuito y 30 segundos en el plan pagado, lo que hacía que nuestras consultas frecuentemente agotaran el tiempo disponible.
  3. Transferencia de datos innecesaria: Traer todos los registros de D1 para filtrarlos después es ineficiente, especialmente cuando solo unos pocos están realmente cerca.
  4. Limitaciones de SQLite: D1, al estar basado en SQLite, no ofrece funciones geoespaciales nativas como otros sistemas de bases de datos más especializados.

La solución: ngeohash

Para resolver estos problemas, implementamos un sistema basado en geohash utilizando el paquete ngeohash. Este paquete de Node.js proporciona una implementación eficiente del algoritmo geohash, que convierte coordenadas geográficas en cadenas de texto. Lo interesante es que ubicaciones cercanas comparten prefijos similares en sus geohashes.

Primero, instalamos el paquete:

npm install ngeohash

Implementación con ngeohash

Luego, importamos y utilizamos las funciones del paquete en nuestro código:

import * as ngeohash from 'ngeohash'

// Función para codificar coordenadas a geohash
function encodeGeohash(latitude: number, longitude: number, precision = 9) {
  return ngeohash.encode(latitude, longitude, precision)
}

// Función para obtener geohashes vecinos
function getNeighbors(geohash: string) {
  return ngeohash.neighbors(geohash)
}

Añadimos un campo geohash a nuestro modelo de datos:

// Generate geohash from latitude and longitude using ngeohash
const geohash = encodeGeohash(input.latitude, input.longitude)

// Add geohash to the input data
const spaceData = {
  ...input,
  geohash
} as typeof input & { geohash: string }

Luego, implementamos la función de búsqueda de espacios cercanos aprovechando las capacidades de ngeohash:

async findNearbySpaces(latitude: number, longitude: number, radiusKm = 5) {
  // Generate geohash for the target location (precision 7 is ~150m precision)
  const centerGeohash = encodeGeohash(latitude, longitude, 7);

  // Get neighboring geohashes to cover the search area using ngeohash
  const neighbors = getNeighbors(centerGeohash);
  // Add the center geohash to the list
  const neighboringHashes = [centerGeohash, ...neighbors];

  // Find spaces with matching geohash prefixes (at least first 5 characters - ~5km precision)
  const hashPrefixLength = 5;
  const neighborPrefixes = removeDuplicates(
    neighboringHashes.map((hash) => hash.substring(0, hashPrefixLength))
  );

  // Create queries for each prefix
  const whereConditions = neighborPrefixes.map(
    (prefix) => sql`${SpaceTable.geohash} LIKE ${prefix + '%'}`
  );

  // Combine the conditions with OR
  let whereClause;
  if (whereConditions.length === 1) {
    whereClause = whereConditions[0];
  } else {
    whereClause = sql`(${sql.join(whereConditions, sql` OR `)})`;
  }

  const potentialSpaces = await this.db.query.SpaceTable.findMany({
    limit: 10,
    offset: 0,
    where: () => whereClause
  });

  // Filter spaces by actual distance and sort by proximity
  const spacesWithDistance = potentialSpaces.map((space) => {
    const distance = getDistanceInKm(
      latitude,
      longitude,
      space.latitude,
      space.longitude
    );
    return { ...space, distance };
  });

  // Filter spaces within the requested radius
  const filteredSpaces = spacesWithDistance
    .filter((space) => space.distance <= radiusKm)
    .sort((a, b) => a.distance - b.distance);

  // Construct the results
  const data = filteredSpaces.map((space) => {
    const { distance, ...spaceData } = space;
    return spaceData;
  });

  return {
    data,
    distances: filteredSpaces.map((space) => ({
      id: space.id,
      distance: space.distance
    }))
  };
}

Ventajas del enfoque con ngeohash en Cloudflare

  1. Biblioteca probada y optimizada: ngeohash es una biblioteca madura y optimizada para JavaScript/TypeScript, lo que la hace ideal para Cloudflare Workers.
  2. Consultas más eficientes en D1: En lugar de recuperar todos los registros, solo obtenemos aquellos cuyo geohash coincide con los prefijos de la ubicación objetivo y sus vecinos.
  3. Reducción de cálculos: Solo calculamos la distancia exacta para un subconjunto mucho menor de espacios, lo que es crucial dado el tiempo limitado de ejecución de Workers.
  4. Mejor rendimiento en Cloudflare Workers: Al reducir tanto la carga computacional como la transferencia de datos, nos mantenemos dentro de los límites de tiempo de ejecución de 50ms en muchos casos.
  5. Compatibilidad con el entorno serverless: ngeohash es ligero y no tiene dependencias externas, lo que lo hace ideal para entornos serverless como Cloudflare Workers.

Detalles técnicos importantes

Precisión del geohash con ngeohash

Una de las ventajas de ngeohash es que permite especificar la precisión del geohash generado. La longitud del geohash determina su precisión:

  • 5 caracteres: ~5km de precisión
  • 6 caracteres: ~1.2km de precisión
  • 7 caracteres: ~150m de precisión

En nuestra implementación, generamos geohashes con alta precisión (7 caracteres) pero buscamos coincidencias con prefijos más cortos (5 caracteres) para cubrir el área deseada.

Manejo de bordes con ngeohash.neighbors()

Un desafío con los geohashes es el “efecto de borde” - dos ubicaciones pueden estar físicamente cercanas pero tener geohashes completamente diferentes si están en lados opuestos de un límite de celda. La función neighbors() de ngeohash resuelve elegantemente este problema proporcionando los 8 geohashes vecinos que rodean un geohash dado:

// Obtener los 8 geohashes vecinos que rodean el geohash central
const neighbors = ngeohash.neighbors(centerGeohash)

Esto nos permite cubrir eficientemente un área geográfica sin preocuparnos por los efectos de borde.

Verificación final con Haversine

Aunque usamos ngeohash para la preselección, seguimos utilizando la fórmula de Haversine para el cálculo final de distancias, garantizando resultados precisos:

const spacesWithDistance = potentialSpaces.map((space) => {
  const distance = getDistanceInKm(
    latitude,
    longitude,
    space.latitude,
    space.longitude
  )
  return { ...space, distance }
})

Resultados en Cloudflare

Después de implementar esta solución con ngeohash en nuestro entorno de Cloudflare Workers con D1, observamos mejoras significativas:

  • Tiempo de respuesta: Reducción del tiempo de respuesta de ~200ms a ~30ms en promedio, manteniéndonos cómodamente dentro del límite de 50ms del plan gratuito.
  • Uso de CPU: Disminución del uso de CPU en más del 80%, crucial para la facturación basada en recursos de Cloudflare.
  • Escalabilidad: La solución mantiene un rendimiento constante incluso cuando la base de datos D1 crece.
  • Costos operativos: Reducción significativa en los costos de computación en Cloudflare, ya que se procesan menos datos y se realizan menos cálculos.

Conclusión

La optimización de búsquedas geoespaciales en entornos con restricciones como Cloudflare Workers con D1 requiere pensar más allá de los algoritmos tradicionales. El uso de ngeohash como biblioteca para implementar la técnica de geohash, combinado con cálculos precisos de distancia para los resultados finales, nos permitió crear una solución eficiente y escalable que funciona dentro de las limitaciones de esta plataforma serverless.

Esta técnica no solo mejoró el rendimiento de nuestra aplicación, sino que también redujo los costos operativos al minimizar el uso de recursos computacionales, demostrando que a veces, la elección del algoritmo correcto y la biblioteca adecuada puede tener un impacto más significativo que la optimización del hardware, especialmente en entornos serverless como Cloudflare Workers.