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

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

В принципе, в архитектуре клиент-сервер задачи сервера будут:

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

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

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

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

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

Я хочу сказать следующее:

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

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

Благодарим вас за помощь, Florent

2 ответа

Ответ на самом деле зависит от многих вещей, поэтому я буду помогать с базовой стратегией. Чтобы понять все, вам нужно понять, как работает 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-метрики к Nodes # 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 уровней расстояний.

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

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


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

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

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

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

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

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

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

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

licensed under cc by-sa 3.0 with attribution.