bagart/averia-task.md

## averia-task.md

      
    Raw
  

              averia-task.md
            
          
    Тестовое задание averia-task

устройство отправляет сообщения (назовем их пакеты) с навигационными данными и данными об активности

пакеты могут дублироваться
пакеты могут прийти не в хронологическом порядке

авторизационные данные находятся в заголовке HTTP, payload в теле сообщения, все как обычно
существует 2 вида пакетов:
пакет "Трек" содержит поля:

int8 статус устройства
int32 таймстамп в UTC
floаt "lat" широта в градусах
float "lon" долгота в градусах
int8 высота в метрах
int8 "accu" точность в метрах

пакет "Активность" содержит поля:

int8 статус устройства
int32 таймстамп в UTC
int8 тип активности (0 - сон,1 - шаг,3 - галоп,6 - рысь,255 - шаги не измеряются)
int кол-во шагов

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

отсеивать дублирующиеся пакеты (по типу пакета и timestamp)
отдавать последнюю координату устройства
отдавать текущие координаты устройств внутри определенного bounding box
сохранять и агрегировать статистику по активности, отдельно вычислять активность которая была в рамках записи трека
отправлять пуш уведомления при изменения статус устройства
описать алгоритм работы подсистемы, вычисляющей совместные прогулки

совместные прогулки
прогулка является совместной если 2 устройства находились рядом (на расстоянии до 6 метров) в течение N минут (N=10),
вычисления производятся на основе данных трека (координаты и timestamp)
стоит обратить внимание:

совместная прогулка может содержать более 2х устройств, необходимо вычислять пары прогулок для каждого из устройств
совместная прогулка может прерываться и возобновляться в рамках одного трека (гуляли-разошлись-потом опять встретились)
совместная прогулка одного устройства, может пересекаться с N совместных прогулок другого устройства
нет гарантии что треки попадают на сервер сразу (например, устройство одного участника загружает трек сразу, а
устройство другого участника через 8 часов), продумать механизм дообсчета "старых" треков


Анализ задания

Предположим, мы строим систему для достаточно большого кол-ва устройств / RPS (Response Per Second)
Мы имеем дело с распределенными, легковесными, односторонне направленными(клиент-сервер), периодичными запросами.
Особенности:


Нам не нужен ответ кроме подтверждения получения
Балансировка трафика легко достижима

параллельная обработчиков запроса на разных машинах. Для PHP это:

PHP-FPM
RoadRunner
Nginx Unit
...


балансировка входящего трафика:

явная синхронизация списка доменов : +/-

1 домен = 1 физический сервер
по текущему GEO-распределению (особенно подходит с логикой поиска совместных прогулок)
сприоритетзированные списки
резервный domain в случае отказов в обслуживании
ранжирование доменов с одним приоритетом по response time
...


автоматическая: Round Robin DNS +/- базовый домен по регионам(минусы: отложенное изменение)
распределенное проксирование бинарных запросов(HAProxy, Traefic, Nginx+)
...


В ТЗ предложен протокол HTTP в качестве транспортного.
Хороший выбор для периодичных, но не слишком частых запросов через глобальный интернет. Но в ТЗ не указана периодичность.
Для частых запросов оптимальные решения подразумевают изменение ТЗ по крайней мере в качестве дальнейшей оптимизации
Примеры:

Bulk запросы с разумной периодичностью (задержки не всегда приемлемы)
отказ от REST в пользу WebSocket или raw socket (со своими подтверждениями, реконнектами и проблемами)
Протокол данных: ProtoBuf для экономия на трафике.
Облачные "Вендорлок" решения. Google pubsub, AWS IoT Messaging, Google Firebase...
...

Анализ пакетов

int32 таймстамп в UTC

Максимальное дата в int32=2147483647 =>19 January 2038, unsigned_int32=4294967295 =>7 February 2106
Некоторые цифровые решения разработанные 19+ лет назад все еще продаются или новые имеют обратную совместимость
Более того, желательно иметь возможность снимать показатели чаще, чем раз в секунду:

проф.спорт, медицинский мониторинг
сглаживание округлением значений и с помощью нейросетей и учетом конкретныъ мест (затруднено на конечном устройстве).
датчики имеют большую погрешность. средняя точность GPS без преград  - 6-8м.


Возможны определяемые преграды: вода во время плавания, крытый стадион, ...

floаt "lat" широта в градусах, float "lon" долгота в градусах

Крайние значения долготы +/-180гр, широты +/-90гр
В Postgres для real заявлено: 6 decimal digits precision
Максимальная точность single float32 это 7 десятизначных цифр с плавающей точкой или 0.0001гр для долготы
На экваторе (с известной длиной) 0.0001гр ~= 40075696/360*0.0001 ~= 11.132137778м
Но у нас в ТЗ заявлена 6-ти метровая расчетная точность. разрядность не достаточная
Для double с разряждность. 15 цифр минимальная точность геокодирования ~0.00011132137мм

В PHP нет float(32) и float приводится к double :)

var_dump(-179.999999999999, (double)-180);//double(-180), double(-180)
var_dump(-179.999999999999==(double)-180);//bool(false)
int8 высота в метрах

Клиенты могут погружаться в воду и летать на самолете
int16 - достаточен для бытовых метрик с метровой точностью.
Но даже для летчиков-испытателей с метровой точностью нужна большая разрядность
int8 "accu" точность в метрах

напрашивается uint8, но даже его не достаточно для геопозиционирования по сотовым вышкам
Features

отсеивать дублирующиеся пакеты (по типу пакета и timestamp)

У одного пользователя могут быть несколько устройств, у 1 устройства могут быть несколько пользователей
=> требуется device_id (+ желательно и для Auth)
составной ключ уникальности: user_id*, device_id, package_type, timestamp
user_id*

наиболее частый фильтр
аггрегирующее поле
ключ шардирования - все данные по пользователю рядом
эффективная селективность

отдавать последнюю координату устройства

отдавать текущие координаты устройств внутри определенного bounding box

Зависит от частоты подобных запросов и  требованиям гео-поиска.
Возможно, достаточно использование основной базы треков с индексами device_id и timestamp(desc)
Самая вероятная ситуация - ищем только активных клиентов
Решение:

отдельный сервис со своей DB
очистка устаревших данных 10мин - 1 час (нужно бизнес решение). TTL или Cron
если данные нужны для любой периодичности - будет разумным переносить в отдельную базу для "холодных" device_id
персистентное хранение
ИЛИ failover в основную "трек" DB для отсутствующих данных
ИЛИ програв после паденя без перезаписи реальных актуальных данных для гео-поиска
+/- шардинг по device_id с учетом DataCenter
здесь же можно хранить последню активность(не требуется по ТЗ)

С определенными допущениями (поиск по прямоугольнику с определенной погрешностью на кривизну земли)
решается математикой вне DB и двумя условиями between range
С учетом этого допущения выбор DB очень широкий, но так как в любой момент требования могут усложнится
лучше использовать DB с GEO-дввижком с уникальным device_id:

Postgres + PostGIS https://postgis.net/features/
Elasticsearch https://www.elastic.co/blog/geo-location-and-search
Tarantool https://github.com/tarantool/gis
...

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

здесь разделиит решения в зависимости от требований. нужны ли нам доступные по API исторические данные?
...
Решение:

аггрегированные данные нужно хранять явно
DB для сырых данных:

SQL DB для временныъ данных, если хранить сырые данные не требуется
Clickhouse (высоая производительность на вставке пачками - потеря realtime)
ElasticSearch(не для реалтайм) аггрегация и поиск могут не учиитывать послежгние изменения)


сырые данные нужно хранить как минимум до смены активности (зависит от деталей задачи)
+/- устаревшие аггрегированные данные нужно переносить в холодную DB
Хорошие решения для аггрегации сырых метрик:

Clickhouse
ElasticSearch


DB для Аггрегированных данных:

SQL + историческое партицирование
Clickhouse
ElasticSearch


отправлять пуш уведомления при изменения статус устройства

Решение:
для мобильных и вэб Firebase (+/- APN)
возможна реализация socket.io+redis(pub/sub) или reactPHP

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

продумать механизм дообсчета "старых" треков

Уточнения:

Активность по сути не имет особый смысл:

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

Важно что при активности со скоростью не превышающую условный велосипед

гео-позиции синхронно меняются
исключения: автопробка, беговая дорожка (фитнес организации имеют спорное значение для "совместных прогулок")

на мой взгляд нет смысла отбраковывать по активности, а надо их уточнять
на расстоянии до 6 метров
И напомню, актуальные устройства зачастую имеют большую погрешность

препятствия
рассинхронизация по времени
после пробуждения нужно время для калибровки aGPS и, тем более, GPS

Возможная оптимизация:


обсчитывать разово все актуальные на момент времени треки, а не одиночный трек

использовать задержку обсчета при которой будет

зафиксировано в бд больинство треков от большинства активных устрройств
отправлен и трек и его активность


искать расстояния средствами самой БД
если данные при ходят с опозданием использовать поиск по конкретным координатам (Queue)

Анализ задачи:


Устройства может иметь не актуальное время. допустим прием устаревших треков.
Значит надо посчитать отклонение времени от сервера и использовать на устройстве timestamp с коррекцией отклонения
Обсчет "устаревших" данных делает невозможным использование временного горячего кэша
Эту задачу можно сделать разными способами исходя из выбора БД.
агрегировать прогулки по +/- 1 sec как допустимое отклонение - у нас секундный timestamp
4 человека могут разойтись по 2 => прогулки могут меняться, объединяться и разбиваться
в задаче явно сказаны прогулки, но возможны совместные катания на велосипеде, транспорте, сидение на скамейке, ...
Ни ElasticSearch, ни Clickhouse не обеспечивают ACID (а именно с подтверждением читабельности после вставки)
а мы не можем оперировать не консистентными данными
Значит нужно либо

задержка на синхронизацию в NoSQL

самый дешевый по кол-ву кода, железа и стоимости масштабирования
выбор баланс допустимости потерь и задержки времени обсчета rfr (лучше после стат анализа нагрузочного)


использовть SQL как основную "трэк" DB

Postgres с партицированием по времени +/- шард по регинам
...


использовать in-memory(опционально) SQL для горячих данных (1 час?), треки с задержкой:

обрабатывать "поштучно" в основной DB (оптимально)
hot cache => cold cache
прогреваь кэщ


использовать самописный демон (go, node.js) идеально подходящий именно для этой задачи

шардирование по гео-прямоугольникам (полигонам)
хэш-таблица по timestamp за последний час(?)
b+tree для диапазонов отдельно lat и отдельно lng


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

Архитектура решения

1 Решение: простой и универсальный

своя или общая ACID(консистентная) DB с прямым матчингом каждого нового запроса по timestamp, lat between, lng between

2 Решение: оптимизированное

ежесекундный крон запускающий обработку данных
обрабатываем горячие треки не в реалтайм (delay) (не забываем про +/- 1 секунда)
обработка "пачкой" всех данных по timestamp +/- region
queue  работой для треков близких к delay минус 5 sec (с задержкой) или больше delay

для каждой обработанной записи савить флаг в redis с TTL для обработанных track_id
не обрабатывать queue job если в редисе есть флаг что он обработан


отдельная DB/table для конечного и промежуточноых результатов

Алгоритм

В зависимости от подхода:

находим лижайшие точки

аггрегация по timestamp: обрабатывать все имеющиеся кейсы по времени в памяти приложения
аггрегация по timestamp, lat,lng: искать ближайшие точки средствами БД

по честному радиусу в GIS (Polygon)
упрозщенно но быстро: в прямоугольнике используя предпосчитанные крайние точки сс поиском в b-tree: timestamp, lat
+/- timestamp, lng - сть DB умеет мержить инжексы(Postgres меет)


полученные пары складываем во временную таблицу по timestamp, user_id_1, user_id_2(сортировка по user_id на 1 и 2)
временные данные аггрегируем после отсутствия пересечений заданный срок

с допуском пропусков(исходя из бизнес требований)
с минимальным допустимым временем нахождения рядом чтобы считать совместным(от бизнес требований)


Архитектура для нового приложения

В зависимости от расчетных нагрузок, бизнес требваний и возможностей:

ОТ

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


ДО

Kubernates, Docker
MSA (User/Auth, Track, Activity, CoupleActivity)
reproducible incoming binlog (EventSourcing)
Messaging:

Kafka как балансировка входящего трафика и MSA Subscribers (избыточно)
AMQP с приоритезацией, разбиением задач на подзадачи и каскадированием задач


межсервисный Protobuf протокол
Сервисами логирования, тестирования, повторного выполнения проблемных задач, воспроизводства по времени


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