Расширенная история одной стажировки

21 июля 2021

Вот уже несколько лет как Qrator Labs работает с различными университетами с целью найти студентов, заинтересованных во вполне определенных задачах, над которыми мы работаем. Студентам это помогает получить новый опыт или обозначить будущую карьерную тропу в области сетевой и, в общем, компьютерной инженерии. А Qrator Labs — найти потенциальных сотрудников.

На данный момент в составе Qrator Labs работают несколько сотрудников, пришедших со стажировки, в свою очередь начавшейся с участия в небольших проектах, курируемых разработчиками Qrator Labs в рамках университетского “инновационного практикума”. Конечно, далеко не все в итоге выбирают компьютерную инженерию в качестве области специализации: из 23 студентов, прошедших практику под нашим кураторством в 2019 и 2020 годах, лишь 9 были приглашены на стажировку. И только четверо из них стали нашими коллегами, что делает каждую такую историю особенной.

В этот раз мы бы хотели подробнее рассказать об одном из наших коллег — Дмитрии Камальдинове, который все еще находится на пути к обретению степени магистра. Однако бакалаврская степень была присвоена Дмитрию после успешной защиты диплома, над которым он работал, будучи интерном в Qrator Labs.

По признанию Димы, первоначально поставленная задача не была связана напрямую ни с деятельностью компании как таковой, ни с тем, чем сейчас Дмитрий занимается в Qrator Labs. Задача заключалась в предоставлении доступа к опенсорсной C++ библиотеке из Python. Звучит как хорошее задание для студента? Вы можете сами ознакомиться с имеющимся результатом: https://github.com/QratorLabs/pysdsl.

Спустя некоторое время после этого погружения в стажерскую практику Дмитрию необходимо было подобрать тему бакалаврской диссертации. Факультет Дмитрия позволял ему выбирать любого научного руководителя, которого он хотел, не ограничиваясь только профессорами университета. После ответов на пару вопросов другой наш коллега-математик, Артем Шворин, связался с Дмитрием и предположил, что задача доработки и специализации известного алгоритма Space Saving может быть хорошей темой для диплома и подходящей для решения задач, над которыми в то время работала команда Qrator Core. Другая задача заключалась в доработке идеи алгоритма выделения тяжелых потоков с помощью дерева принятия решений.
Наконец, оценив обе идеи, Дмитрий выбрал вторую. Далее мы кратко опишем суть алгоритма, и каких результатов удалось достичь.

Задача выделения тяжелых потоков (heavy hitters) уже интересна сама по себе: постоянно публикуются новые статьи, где предлагаются новые алгоритмы и различные оптимизации существующих. Эта область знаний оказывается особенно полезной в задачах анализа трафика, в первую очередь из-за растущего распространения IPv6. Напомним, что в IPv6 количество уникальных адресов равно 2^128, что исключает любые тривиальные подходы, такие как отдельная обработка каждого адреса.

Sketch-based алгоритмы — группа алгоритмов, которые уменьшают размер исходного пространства ключей, разделяя его на подмножества, причем с важной особенностью — разбиение может осуществляться динамически. Хотя в большинстве подобных алгоритмов используется фиксированное разбиение, идея, предложенная Артемом Швориным заключалась в том, чтобы сделать его динамическим, то есть изменяющимся во время работы алгоритма. Структура данных, которая управляет этим процессом, представляет собой дерево решений, двоичное дерево с предикатами, где используется префиксная маска в качестве предиката, в его узлах, в соответствии с которым принимается решение о спуске ключа либо в левое, либо в правое поддерево.

Основными моментами разработки алгоритма, о которых Дмитрий рассказал в своей работе, были эффективное обновление структуры при получении нового ключа, поддержание устойчивости дерева на стационарных потоках, эффективный поиск новой префиксной маски при необходимости. И, наконец, стратегия применения алгоритма при фильтрации трафика. В окончательной версии используются хорошо известные идеи (например, повороты, широко используемые для балансировки двоичных деревьев), а также некоторые новые преобразования и алгоритмы, которые привели к хорошей асимптотике обновления. Было также показано, что алгоритм хорошо работает на некоторых нетривиальных паттернах трафика.