Как использовать Redis и поиск геопоследовательности, чтобы найти двух пользователей в одном месте?

Я хочу реализовать сервис, который, учитывая геокоманды пользователей, может определить, находятся ли два пользователя в одном и том же месте в реальном времени.

Чтобы сделать это в режиме реального времени и масштабировать, мне кажется, я должен пойти с распределенным хранилищем данных в памяти, например, с Redis. Я исследовал использование geohashing, но проблема в том, что точки, близкие друг к другу, могут не всегда делиться одним и тем же префиксом хеширования. И geohash может быть излишним, так как мне интересно узнать, достаточно ли близки два пользователя, где они стоят рядом друг с другом.

Простым решением, конечно, является просто проверка того, попадают ли пары геокоординат на небольшое расстояние друг от друга. Но AFAIK, Redis и другое хранилище данных in-memory не имеют геопространственного индексации для поддержки такого рода поиска.

Каков наилучший способ реализации этого?

Ответы

Ответ 1

Эта функция запечена в Redis 3.2+.

Но для старых версий проблема все еще существует. Я принял ответ Yin Qiwen и создал модуль для Node, и вы можете увидеть, как он использует Redis, изучая код. Его наставления прекрасны, и я смог следовать за ними, чтобы добиться отличных результатов. https://github.com/arjunmehta/node-georedis

Тот же алгоритм, по сути, используется для собственных команд.

Это очень быстро и позволяет избежать любых операций типа пересечений /haversine. Самая крутая вещь (я думаю) о методе Yin Qiwen заключается в том, что наиболее вычислительно интенсивные части алгоритма могут быть распределены клиентам (вместо того, чтобы все происходит в БД или на сервере).

Он не на 100% точнее и использует предварительно сконфигурированные дистанционные шаги, но для большинства приложений вам не нужна точная точность, я бы себе подумал.

Я также перефразировал статью Yin Qiwen в разделе обмена файлами .

Извините за все ссылки.: P

Ответ 2

Как правило, это можно сделать с помощью отсортированного набора GeoHash и Redis. Существует проект, который я написал, прежде чем говорить о том, как реализовать службу пространственного индекса на redis.

https://github.com/yinqiwen/ardb/blob/master/doc/spatial-index.md

Ответ 3

Возможно, вы можете попробовать следующее:

Redis Geography Edition

Вы действительно хотите попробовать, он работает потрясающе. :)

Ответ 5

Я понимаю, что это не отвечает на ваш вопрос... но я не думаю, что это правильный инструмент.

PostgreSQL + PostGIS может выполнять действительно, очень хорошо. Вы можете настроить PostgreSQL, чтобы в значительной степени запустить как можно больше базы данных, поскольку она может поместиться в память.

PostGIS использует (я думаю) индексы rtree, поэтому он невероятно быстро выполняет вид поиска, который вас интересует.

Использование бэкэнд, который запускает запросы на веб-рассылку, позволит вам выполнять довольно много времени в реальном времени. Каждый раз, когда ваш бэкэнд получает координаты людей GPS; выполнять пространственный поиск; и уведомлять применимых клиентов через websockets.

Ответ 6

База данных Tarantool хранит данные в памяти, выталкивает их на диск в виде журналов транзакций, имеет пространственный индекс типа RTree (не только двумерный) и ряд хороших операций с таким индексом (сдерживание, перекрытие, расстояние).

Я использую его в коммерческом проекте для хранения и запросов записей, описывающих объекты в трехмерном пространстве.

http://tarantool.org/doc/book/box/box_index.html

https://github.com/tarantool/tarantool/wiki/R-tree-index-quick-start-and-usage

Стандартный клиент и примеры находятся в Lua, но есть несколько других клиентов, разработанных авторами баз данных. Я успешно использую Java-клиент в приложении Scala.

База данных также очень быстра - здесь научное сравнение с другими базами данных (отбрасывание аспекта пространственного db): http://airccse.org/journal/ijdms/papers/6314ijdms01.pdf

Ответ 7

Я хотел бы поделиться примером Java-кода для издания Redis Geography.

public void geoadd(String objectId, BigDecimal latitude, BigDecimal longitude) {
    log.info("geoadd(): {} {} {}", objectId, latitude, longitude);
    try (Jedis jedis = jedisPool.getResource()) {
        if (geoaddSha == null) {
            String script = "return redis.call('geoadd','" + GEOSET + "', ARGV[1], ARGV[2], KEYS[1])";
            geoaddSha = jedis.scriptLoad(script);
        }
        log.info("geoaddSha: {}", geoaddSha);
        log.info(jedis.evalsha(geoaddSha, 1, objectId, latitude.toString(), longitude.toString()).toString());
    }
}

@SuppressWarnings("unchecked")
public List<String> georadius(BigDecimal latitude, BigDecimal longitude, int radius, Unit unit) {
    log.info("georadius(): {} {} {} {}", latitude, longitude, radius, unit);
    try (Jedis jedis = jedisPool.getResource()) {
        if (georadiusSha == null) {
            String script = "return redis.call('georadius','" + GEOSET + "', ARGV[1], ARGV[2], ARGV[3], ARGV[4])";
            georadiusSha = jedis.scriptLoad(script);
        }
        log.info("georadiusSha: {}", georadiusSha);
        List<String> objectIdList = (List<String>) jedis.evalsha(georadiusSha, 0, latitude.toString(), longitude.toString(), String.valueOf(radius), unit.toString());
        log.info("objectIdList: {}", objectIdList);
        return objectIdList;
    }
}

public void remove(String objectId) {
    log.info("remove(): {}", objectId);
    try (Jedis jedis = jedisPool.getResource()) {
        jedis.zrem(GEOSET, objectId);
    }
}