Задача связана с геолокацией. Проект - умный gps трекер. Необходимо подготовить примерное описание архитектуры проекта.
Текст задания: SPECIFICATION.md
Достаточно детально описал свое видение архитектуры проекта.
Есть некоторые моменты, которые стоит обсудить более детально, прежде чем начинать реализацию проекта. Можно обсудить их на техническом собеседовании. Далее описана архитектура MVP. Конечная архитектура и алгоритмы могут быть улучшены.
1 . В качестве основного хранилища данных используется БД PostgreSQL.
Возможно, при большом количестве пользователей/большой нагрузке потребуется оптимизация производительности или использование специализированного решения.
2 . При постоянном добавлении пакетов треков/активности возможно сильное увеличение размеров БД. Как вариант решения - обрабатывать данные пакетов и преобразовывать к более удобному виду.
Например старые пакеты активности можно удалить. Оставить только даты начала/конца активности. Данные пакетов хранить какое-то время(например 1 месяц), затем удалять. Треки хранить отдельно в виде gpx/geojson.
3 . На этапе проектирования совместных прогулок стало понятно, что этот функциона может значительно нагружать БД. Для прототипа PostgreSql должно хватить. Возможно, в будущем, для хранения данных пакетов стоит использовать более производительное специализированное решение.
4 . Для совместных прогулок нужно учесть допустимую погрешность ~10м для gps приемников. https://ru.wikipedia.org/wiki/GPS http://helpform.ru/544777
Соответственно, проверять, что устройства находятся на расстоянии 6 метров может быть проблематичо. Скорее здесь стоит ориентироваться на длительность совместной прогулки. Пороговое расстояние между девайсами можно увеличить. Допустим, в течении N минут расстояние между 2 девайсами было не более 30м. Это вполне можно считать совместной прогулкой. Также можно ввести проверку на пройденное расстояние. Если 2 девайса просто лежали рядом, то это не должно считаться совместной прогулкой.
В качестве основной БД используется PostgreSql
Таблицы:
- trackpoint - содержит данные пакетов "Трек"
- device - содержит информацию об устройствах
- activity_type - содержит сами активности
- activity - содержит данные пакетов "Активность"
- device_status - содержит текущий статус для каждого девайса
- track - содержит информацию о треках
- walk - содержит информацию о совместных прогулках
Для работы с координатами в PostgreSql можно использовать расширение PostGIS.
Нужно реализовать Rest API. Использовать PHP + один из фреймворков(Yii2/Symfony/Laravel/other). Для всех запросов должна быть авторизация по access token.
отсеивать дублирующиеся пакеты (по типу пакета и timestamp)
1 . POST api.olivia.ru/trackpoint - api метод принимает на вход пакет "Трек". Получает id девайса Проверяет на дубликат, сохраняет в БД.
2 . POST api.olivia.ru/activity - api метод принимает на вход пакет "Активность". Получает id девайса Проверяет на дубликат, сохраняет в БД.
-
Для проверки пакета на дубликат можно использоват timestamp(не более 1 пакета в секунду). Либо пару timestamp, координаты(возможно, хэш). Ну и, понятно, тип пакета.
-
Возможен вариант с использованием GUID, но тут зависит от требований, возможностей устройства и среды передачи. Возможно, этот вариант не очень подходит, т.к. увеличивает размер пакета и, впоследствии, размер базы данных.
-
Возможно, нужно реализовать batch загрузку пакетов для отложенной загрузки.
Отдавать последнюю координату устройства
GET api.olivia.ru/device/{device_id}/last-position Тут все довольно просто. Выбираем записи из таблицы trackpoint либо activity. Сортировка по timestamp. Выбираем самую позднюю запись.
отдавать текущие координаты устройств внутри определенного bounding box
POST api.olivia.ru/bounding-box/devices
Если я правильно понял задачу: На вход передается массив данных - координаты(3 и более). В результате по точкам строится полигон. Затем выбираются последние координаты для всех устройств. Можно сразу исключить устройства, которые заведомо не попадают в полигон(сравнение с min/max latitude/longitude).
Для остальных можно использовать функцию ST_Contains в PostGIS. Или подобный механизм. https://postgis.net/docs/ST_Contains.html
Пример: https://stackoverflow.com/questions/1012504/sql-query-for-point-in-polygon-using-postgresql https://www.thutat.com/web/en/programming-and-tech-stuff/web-programming/find-if-a-point-is-inside-a-polygon-with-native-postgresql/
сохранять и агрегировать статистику по активности, отдельно вычислять активность которая была в рамках записи трека
1 . Для получения общей статистики по активности получим запрос такого типа:
GET api.olivia.ru/device/{device_id}/statistics/
Пример SQL запроса:
SELECT type_id, count(*) FROM activity GROUP BY type_id
В результате получим количество записей активности для каждого типа. Допустим, пакет активности приходит каждые 5 секунд. Тогда количество записей * 5 равно количеству секунд и можно посчитать время для каждой активности.
2 . Чтобы получить статистику активности по треку, нужно знать timestamp начала и конца трека. По ним отфильтровать пакеты.
GET api.olivia.ru/device/{device_id}/statistics/{track_id}
Пример SQL запроса:
SELECT type_id, count(*) FROM activity GROUP BY type_id WHERE timestamp BETWEEN :start_timestamp AND :end_timestamp
Получение трека и его данных описано в следующем пункте.
Можно получить все треки:
GET api.olivia.ru/tracks
Либо конкретный трек:
GET api.olivia.ru/track/{track_id}
Треки хранятся в таблице track. Хранится timestamp начала и конца, id девайса, возможно, данные трека(geojson). Или путь к файлу(gpx/geojson). Возможно, дополнительная информация(прим: протяженность)
Треки генерируются в фоновом режиме. Для начала нужно получить timestamp начала и конца для всех треков для конкретного девайса.
Для этого нужно найти пакеты треков с разницей timestamp больше порогового значения(прим 60 сек). Таким образом можно получить первый и последний пакет для каждого трека. Затем на основании этого собрать все пакеты по треку, добавить запись в таблицу track, сгенерировать gpx/geojson.
Пример sql для получения начала/конца для треков треков:
SELECT this.* FROM trackpoint this
LEFT JOIN trackpoint prev ON prev.timestamp = (SELECT MAX(t1.timestamp) FROM test t1 WHERE t1.timestamp < this.timestamp)
LEFT JOIN trackpoint next ON next.timestamp = (SELECT MIN(t2.timestamp) FROM test t2 WHERE t2.timestamp > this.timestamp)
WHERE (this.timestamp - prev.timestamp > 60 OR prev.timestamp IS NULL) OR (next.timestamp - this.timestamp > 60 OR next.timestamp IS NULL)
AND device_id = :device_id
отправлять пуш уведомления при изменения статус устройства
В методы /trackpoint, /activity добавить логику для проверки статуса девайса. Текущий статус девайса берется из таблицы device_status. Возможно, стоит использовать redis или другое nosql хранилище. Если статус девайса в пакете не совпадает с текущим статусом, нужно отправить push уведомление(очередь) и поменять текущий статус. Также нужно реализовать логику для проверки актуальности пакета и, соответственно, статуса устройства.
Отправка push сообщений происходит через стронний сервис Например: pushwoosh
Уведомления отправляются асинхронно, через очередь. В качестве очереди можно использовать RabbitMQ, Redis и т.д.
описать алгоритм работы подсистемы, вычисляющей совместные прогулки
Совместные прогулки просчитываются скриптом в фоновом режиме. Скрипт имеет смысл запускать периодически(по cron) для всех девайсов. Или, возможно, запускать в определенное время для конкретных девайсов. Наприме, после добавления нового трека.
Для определения совместной прогулки можно использовать такой алгоритм:
1 . С помощью метода, описанного выше (см. Получение треков) получаем треки для девайса за определенное время(прим: 30 дней).
2 . Для каждого трека пытаемся найти совместные прогулки.
3 . Проходим по треку. Берем данные из таблицы trackpoint. Проходим от 1го до последнего пакета, принадлежащего к треку. Проверяем каждый пакет.
4 . Для каждого пакета пытаемся найти похожие пакеты с других девайсов. Ищем пакеты с других девайсов, проверяем, что расстояние между точками не превышает пороговое.
Разница между timestamp также не должна превышать пороговое значение. Пороговым значением для timestamp является период отправки пакета "Трек". Например, если пакеты "Трек" отправляются каждые 5 сек, то пороговое значение timestamp будет равно 5.
Для определения расстояния между координатами можно использовать функцию ST_Distance.
5 . Оба пакета помечаем, как стартовые пакеты для прогулки. Затем смотрим следующие пакеты для каждого девайса и попарно сравниваем. Если расстояние между двумя точками не превышает пороговое, то продолжаем. Если расстояние превышает пороговое, то прекращаем перебор. Запоминаем последний пакет.
6 . Вычисляем длительность прогулки - разность timestamp между первым и последним пакетом. Проверяем, что длительность прогулки больше пороговой(прим: 10 мин) Проверяем, что прогулка с такими параметрами не сушествует(id девайсов, timestamp начала и конца)
Если оба условия выполнены сохраняем прогулку в таблицу walk. Указываем id обоих девайсов, длительность прогулки. Также timestamp начала и конца прогулки для обоих девайсов(может отличаться в рамках периода отправки пакетов).
В результате:
- вычисляются пары прогулок для всех устройств.
- совместная прогулка считается на базе точек трека, независимо от трека в целом.
- если треки попадают в систему с задержкой, то есть возможность пересчитать совместные прогулки и добавить недостающие.
Инфраструктура обычная для проекта на php.
Используется VPS c linux (ubuntu/debian/centos/other) Вебсервер: Nginx + php-fpm Приложение: PHP7, Symfony/Yii2/Laravel База данных: PostgreSql + PostGis Дополнительно: Redis, возможно что-то еще
Докеризация, кластер, балансировщик - при необходимости.