Возможен ли пространственный поиск в сети P2P?

Question

Я хочу создать социальную сеть на основе геолокации на основе Javascript / HTML5, и мне интересен лучший выбор из возможных архитектур. Клиент-сервер может быть простым в разработке, но недостатком является то, что ресурсы системы могут быть очень высокими, особенно потому, что приложение должно управлять перемещениями (наихудший случай: пользователь, находящийся в автомобиле, должен видеть других пользователей, находящихся рядом с ним в автомобилях).

По сути, в архитектуре клиент-сервер задачи сервера будут:

1. собирает и хранит широту и долготу пользователей (их может быть тысячи)
2. выполняет поиск географического расстояния для этого пользователя (чтобы получить список пользователей, находящихся вокруг него в радиусе)
3. создает и отправляет клиенту файл XML с позицией пользователей в списке

Эти 3 операции должны выполняться периодически, каждые 3 или 5 секунд, потому что я хочу "живую" карту, которая показывает пользователей в списке, перемещающихся в их окружении (город, город).

Все эти 3 пункта можно оптимизировать:

1. клиент отправляет свою позицию при перемещении на 10 метров, чтобы уменьшить объем данных для обработки
2. Поиск "сферического прямоугольника" в таблице MyISAM с пространственным индексом (использование MBRContains) для выгрузки базы данных MySQL.
3. общий выходной файл: отправляемый XML может быть одинаковым, если 2 пользователя находятся в радиусе х метров (2 пользователя находятся близко друг к другу).

На этом этапе сложно оценить нагрузку, но я думаю, что клиент-серверная архитектура не подходит для этого типа приложений, и peer2peer может быть хорошим ответом, если 2 клиента смогут общаться, когда они находятся рядом.

Моя точка зрения:

Существует ли какой-либо метод, позволяющий клиенту осуществлять слепой поиск других клиентов, находящихся в определенном радиусе, без помощи центрального сервера? (возможно с широковещательной рассылкой UDP: -)

редактировать: исправление. UDP Brodcast позволяет клиенту опрашивать компьютер, где бы он ни находился, в определенном диапазоне или по IP-адресу.

Спасибо за вашу помощь, Флоран

Answer 1

Ответ на самом деле зависит от многих вещей, поэтому я помогу с основной стратегией. Чтобы разобраться, вам нужно понять, как работает Kademlia (Kademlia - это сеть DHT P2P, которая хранит информацию).

В Kademlia при первом запуске каждый узел выбирает случайный идентификатор, представляющий собой 160-разрядное число, представляющее точку в пространстве всех возможных 160-разрядных идентификаторов.

Идентификатор информации, которая должна быть сохранена, получается с помощью функции SHA-1 (она принимает произвольную строку и выдает 160-битное число, которое обрабатывается как идентификатор информации, которая должна быть сохранена)

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

(иллюстрация взята из здесь )

Информация запрашивается через ее ID. Как поиск информации, так и поиск узлов требует O (log (N)) прыжков для получения необходимой информации. Метрика «XOR» используется в Kademlia (в вашем случае это может быть обычная евклидова метрика).

Каждый узел поддерживает массив сегментов, каждый блок содержит адреса узлов, которые соответствуют текущему сегменту. Соответствие - это мера того, насколько близки идентификаторы. рассмотрим пример:

           0                              160
Node 1 ID: 1101000101011111101110101001010...
Node 2 ID: 1101011101011111101110101001010...
Node 3 ID: 1101000101011001101110101001010...

После применения метрики XOR к узлам # 1,2, т. Е. (Вычисляя число, представляющее виртуальное расстояние между этими узлами), мы получаем:

index - 012345678901234
xor   - 000001100000000... (the difference is in 5-th msb bit)
order - msb         lsb

После применения метрики Xor к узлам # 1,3 мы получаем:

index - 012345678901234
xor   - 000000000000011... (the difference is in 13-th msb bit)
order - msb         lsb

Очевидно, что Узел 1 ближе к Узлу 3, так как он имеет разницу в менее значимых битах, чем расстояние от Узла 1 до Узла 2. И, следовательно, с точки зрения Узла 1 его соседний Узел 3 переходит на 13-й сегмент (более высокий индекс означает более близкие идентификаторы), и Узел 2 переходит к 5-му сегменту, который содержит группу узлов, которые находятся на расстоянии 5 мкс MSB от текущего идентификатора узла.

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

Возвращаясь к вашему примеру, чтобы обеспечить эффективные геопространственные запросы, вам необходимо заменить метрику XOR Kademlias обычной евклидовой метрикой. В этом случае вы будете иметь свои идентификаторы в виде трехмерных или двумерных векторов, и, к сожалению, из-за того, что евклидова метрика приводит к числам с плавающей запятой, которые не подходят непосредственно для этого типа алгоритма, поэтому вам нужно будет преобразовать их в дискретные двоичные числа как-то похоже на то, что делает функция XOR. После этого поиск соседних узлов является тривиальной задачей.

Надеюсь, это поможет. Кстати, посмотрите на HyperDex, новое распределенное хранилище данных с возможностью поиска, тесно связанное с евклидовой метрикой, может помочь ...

Answer 2

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

Я бы пошел на следующее:

1. Назначьте квадратные мили (или любой другой размер) конкретным серверам.

2. Пусть устройства отправят сообщение «Я здесь» со своими координатами какому-либо диспетчеру, который перенаправит их на правильный сервер квадратной мили для обработки.

3. Серверы должны регистрироваться, когда устройство входит в квадратную милю, которой они управляют. Это может быть центральная карта, чтобы убедиться, что устройство зарегистрировано в одном и только одном квадрате.

4. Переслать это сообщение всем другим устройствам в квадрате.

5. И / или убедитесь, что вы указали, для какого квадрата предназначено это сообщение, и убедитесь, что устройства проверяют его, прежде чем отобразить его пользователю.

Настройте размер квадрата и скорость сообщения «Я здесь». Вот и все.