Skip to content

Instantly share code, notes, and snippets.

@bagart

bagart/averia-task.md

Forked from AlexGx/averia-task.md
Last active February 20, 2019 13:07
Show Gist options
  • Save bagart/7caaaf3d42d3293b339a7cee008ae182 to your computer and use it in GitHub Desktop.
Save bagart/7caaaf3d42d3293b339a7cee008ae182 to your computer and use it in GitHub Desktop.
Download ZIP
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:

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

здесь разделиит решения в зависимости от требований. нужны ли нам доступные по 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 протокол
    • Сервисами логирования, тестирования, повторного выполнения проблемных задач, воспроизводства по времени

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment