Введение 4
Постановка задачи 6
1. Обзор предметной области 7
1.1. Термины 7
1.2. Классическая версия задачи о разладке 7
1.2.1 Алгоритм поиска двоичной сегментации 8
1.2.2 Алгоритм скользящего окна 8
1.2.3 Алгоритм объединения отрезков снизу вверх 8
1.3. Интервальная версия задачи о разладке 8
1.4. Анализ производительности программ 9
1.5. Выводы 9
2. Методы и алгоритмы 10
2.1. Методы 10
2.2. Метрики 11
2.3. Объединение точек в интервалы 11
2.4. Алгоритм поиска двоичной сегментации 11
2.5. Алгоритм скользящего окна 12
2.6. Алгоритм объединения отрезков снизу вверх 13
3. Результаты 15
3.1. Тестовый набор данных 15
3.2. Функция оценки 15
3.3. Результаты на тестовом наборе данных 17
3.3.1 Алгоритм поиска двоичной сегментации с использованием метрик 17
3.3.2 Алгоритм скользящего окна с использованием метрик . 18
3.3.3 Алгоритм скользящего окна с использованием критериев 18
3.3.4 Алгоритм объединения отрезков снизу вверх с использованием метрик 18
3.3.5 Алгоритм объединения отрезков снизу вверх с использованием критериев 19
3.4. Результаты на реальных данных 19
3.5. Материалы работы 21
Заключение 22
Список литературы 23
Для крупных современных информационных систем очень важно следить за производительностью, чтобы ни одна часть огромного продукта в процессе разработки не начинала работать медленнее. В хоть сколько-то крупной системе отслеживать такие изменения вручную практически невозможно из-за больших объемов работы. Поэтому очень важно, чтобы эта часть мониторинга была автоматизирована.
Данные, по которым можно отслеживать изменения производительности, снимаются с помощью регулярного проведения замеров времени работы каждой части кода в отдельности. И уже по этим данным необходимо находить изменения.
Важно заметить, что производительность участка кода может не только снижаться или увеличиваться после внесения правок, но и иметь более сложный характер изменений. Например, на части входных данных код может начать работать медленнее, а на части - ускоряться. И такие изменения тоже необходимо отслеживать. Для этого нужно находить моменты, когда меняется распределение времен замеров в целом, а не только какие-то его параметры.
Также для необходимой быстрой реакции на меняющиеся изменения нужно оперативно уметь определять, что в распределении поступающих из тестов данных что-то поменялось. Полезно учитывать данные тестирования не только окончательных версий продукта, но и всех рабочих версий разработчиков. Это не только позволяет увеличить размер анализируемых данных, а значит точность результата, но и дает возможность находить проблемы с производительностью на ранних этапах разработки. Важная тонкость, которую нужно учитывать в такой постановке - изменения в распределении в серии данных происходят не мгновенно, по какому-то одному коммиту, а происходят в течение какого-то промежутка времени, пока изменяющий код доставляется до всех рабочих версий. Это приводит к необходимости на этапе анализа данных искать интервал времени, в который произошло изменение, а не точную временную метку. Стоит также отметить, что решение задачи в такой постановке может позволить упростить соблюдение важного свойства такого мониторинга - персистентности. При добавлении новых измерений во временную серию определяемые точки разладки могут незначительно сдвигаться, что очень не удобно с точки зрения обработки результатов. В случае, когда работа идет с интервалами — небольшой сдвиг интервала не так критичен, его можно пересечь с интервалами находящимися рядом и найденными на прошлых итерациях, и получить фиксированный достоверный интервал разладки.
Научная ценность данной работы заключается в представлении расширения существующего подхода к автоматическому мониторингу производительности в крупных информационных системах. Результаты исследования будут полезны для разработчиков и технических специалистов, занимающихся оптимизацией производительности систем, а также для научного сообщества, занимающегося проблемами автоматического мониторинга производительности.
В рамках работы были разработаны новые алгоритмы решения интервальной версии задачи о разладке на основе существующих решений для решения классической версии задачи. Была построена программная реализация алгоритмов на языке Python. Все результаты были применены на искусственных данных и проверены на реальных данных. Программный код размещен в открытом доступе и может быть использован в дальнейших работах по этой теме. Данная тема имеет множество перспектив для дальнейшего развития.
