Elastic

Для GeoService мы будем использовать Elasticsearch. Ниже мы подробно будем разбирать все детали, как настроить и оптимизировать.

❓ Прежде чем читать все обязательно посмотри про KD-Tree. Ниже будет лучшее объяснение, которое я находил: https://youtu.be/Glp7THUpGow?si=JumYZnDKDDhJWRqo

✅Крутой разбор QuadTree vs KDTree: https://github.com/amay12/SpatialSearch

✅А здесь elastic презентует BKD Tree: https://www.elastic.co/blog/bkd-backed-geo-shapes-in-elasticsearch-precision-efficiency-speed

Elastic из-под капота умеет:

1. Балансировать нагрузку на master-slave, а также выбирать наименее загруженные кластера. Собирать результаты от нескольких шардов. Следить за connections
   1. ✅В этом Elastic помогают coordinator nodes: https://opster.com/guides/elasticsearch/best-practices/elasticsearch-coordinating-nodes-when-to-use/
2. Шардировать и производить перебалансировку шардов, если какой-то добавляется или убирается
3. Производить failover
   1. ✅Здесь можно почитать про failover в целом и в Elastic: https://severalnines.com/blog/the-what-why-and-how-of-elasticsearch-failover/
4. Пагинация в Elastic
   1. https://www.luigisbox.com/blog/elasticsearch-pagination/

→ по geohash префиксам

Выше мы уже познакомились с geohashing. Тут мы будем использовать GeoHash как ключ шардирования

// При создании места
POST /places/_doc/123?routing=dr5r
{
  "name": "Starbucks",
  "location": {"lat": 55.7558, "lon": 37.6173},
  "geohash_5": "dr5r"
}

Как результат:

• Близкие географически места попадают в одни шарды
• При поиске запрос идет только к нужным шардам, а не ко всем

Если потребуется увеличить точность и кол-во шардов, то это делается через удлиннение string для GeoHash. Elastic сам перекалибрует данные под капотом

Например, наша точка будет находиться как ниже:

Для GeoHash это решается через поиск соседних полей:

Точка A: geohash "dqcjqz" (граница ячейки)
Точка B: geohash "dqcjr0" (соседняя ячейка)
Расстояние: 50 метров
Общий префикс: только "dqcj" (4 символа)

def get_neighbors_search(lat, lon, precision):
    center_geohash = geohash.encode(lat, lon, precision)
    
    # 8 соседних ячеек: N, NE, E, SE, S, SW, W, NW
    neighbors = [
        geohash.neighbors(center_geohash, 'north'),
        geohash.neighbors(center_geohash, 'northeast'),
        geohash.neighbors(center_geohash, 'east'),
        # ... остальные направления
    ]
    
    # Поиск в центральной + 8 соседних ячейках
    all_search_keys = [center_geohash] + neighbors
    return search_in_multiple_geohashes(all_search_keys)

BKD-Tree: решает эту проблему автоматически