Лучшие магистерские диссертации выпускников «Программного обеспечения высоконагруженных систем»
Лучшие магистерские диссертации выпускников «Программного обеспечения высоконагруженных систем»
Этим летом состоялся первый выпуск корпоративной магистратуры Яндекса «Программное обеспечение высоконагруженных систем». Программу успешно окончили 20 специалистов, которые за время обучения прокачались до уровня middle+ вместе с преподавателями-практиками Яндекс Образования и научились работать с распределенными и гетерогенными проектами. Сегодня мы рады представить две выпускные работы, признанные лучшими на программе: алгоритм адаптивного управления стратегиями синхронизации и систему навигации по кодовой базе в сверхбольшом монорепозитории.
- Георгий Кашин
Разработка алгоритма адаптивного управления стратегиями синхронизации в зависимости от уровня конкуренции за ресурсы
Современные высоконагруженные приложения используют десятки и сотни логических ядер, что неизбежно приводит к конкуренции потоков за разделяемые ресурсы. Стандартные схемы взаимного исключения основаны на жестко заданном режиме либо активного ожидания, либо блокировки, игнорируя текущий контекст выполнения. В результате система может тратить до 30% процессорного времени на пустое спин-ожидание или терять производительность из-за частых переключений контекста. Для кластеров крупных компаний даже 5−10% ускорения означает значительное снижение эксплуатационных расходов.
Цель моей работы — построение пользовательского (user-space) примитива, который автоматически выбирает стратегию ожидания, минимизируя совокупные потери процессорного времени и задержки доступа к критической секции. Алгоритм работает следующим образом: сначала в мьютексе в реальном времени снимается определенный набор метрик — время исполнения критической секции, количество ожидающих потоков, среднее время ожидания и другие. Затем эти метрики преобразовываются в формулы для оценки уровня конкуренции, на основании которых принимается решение о переключении стратегии алгоритма синхронизации. Сами формулы выведены из анализа графиков метрик, полученных для разных сценариев нагрузки.
В результате я разработал адаптивный мьютекс, который можно использовать на серверах Linux в дата-центрах, что позволяет увеличить производительность и сократить количество необходимых серверов. Мой алгоритм показал прирост пропускной способности мьютекса до 7−12% в коротких критических секциях и до 20% в длинных.
Сейчас я продолжаю работать над этой темой, а в будущем планирую представить результаты в виде публикации или доклада на конференции.
Современные высоконагруженные приложения используют десятки и сотни логических ядер, что неизбежно приводит к конкуренции потоков за разделяемые ресурсы. Стандартные схемы взаимного исключения основаны на жестко заданном режиме либо активного ожидания, либо блокировки, игнорируя текущий контекст выполнения. В результате система может тратить до 30% процессорного времени на пустое спин-ожидание или терять производительность из-за частых переключений контекста. Для кластеров крупных компаний даже 5−10% ускорения означает значительное снижение эксплуатационных расходов.
Цель моей работы — построение пользовательского (user-space) примитива, который автоматически выбирает стратегию ожидания, минимизируя совокупные потери процессорного времени и задержки доступа к критической секции. Алгоритм работает следующим образом: сначала в мьютексе в реальном времени снимается определенный набор метрик — время исполнения критической секции, количество ожидающих потоков, среднее время ожидания и другие. Затем эти метрики преобразовываются в формулы для оценки уровня конкуренции, на основании которых принимается решение о переключении стратегии алгоритма синхронизации. Сами формулы выведены из анализа графиков метрик, полученных для разных сценариев нагрузки.
В результате я разработал адаптивный мьютекс, который можно использовать на серверах Linux в дата-центрах, что позволяет увеличить производительность и сократить количество необходимых серверов. Мой алгоритм показал прирост пропускной способности мьютекса до 7−12% в коротких критических секциях и до 20% в длинных.
Сейчас я продолжаю работать над этой темой, а в будущем планирую представить результаты в виде публикации или доклада на конференции.
- Михаил Шишацкий
Разработка системы навигации по кодовой базе в монорепозитории
В своей магистерской диссертации я разработал новую систему семантической навигации по коду, предназначенную для эффективной работы в сверхбольших монорепозиториях, таких как Arcadia в Яндексе.
Основная проблема большинства аналогов — часовые задержки при обновлении индекса для обработки накопившихся в репозитории изменений, что не позволяло, например, переиспользовать такой индекс в сценариях разработки в IDE. Мое решение предлагает пофайловую инкрементальность: при изменении одного файла переиндексируется только он, что сокращает время обновления до нескольких секунд.
Центральная идея работы заключается в отказе от графовых моделей в пользу системы переписывания строк. В моем решении семантические связи и правила разрешения имен (включая области видимости, импорты и наследование) кодируются в виде набора строковых правил. Процесс навигации, например, «Переход к определению», сводится к последовательному применению этих правил к строке-контексту, представляющей ссылку, до тех пор, пока она не приведет к строке, обозначающей определение. Для подтверждения жизнеспособности подхода я реализовал систему правил для языка Python, включая индексатор и LSP-сервер для интеграции с IDE. Эксперименты показали, что мой подход сокращает время переиндексации Python примерно в 100 раз, обеспечивая качество навигации и время отклика, сопоставимые с существующими решениями.
По сравнению с такими системами, как Kythe, Glean и SourceGraph, а также с текущим инструментом, используемым в Яндексе, мое решение на порядки ускоряет индексацию за счет пофайлово-инкрементального подхода. Фундаментально мы переносим часть сложности анализа языка в саму модель данных и реализуем ленивое разрешение ссылок в момент запроса. Поскольку модель является языко-независимой, это упрощает добавление поддержки для специфичных доменных языков, что сводится к написанию генератора правил переписывания по коду. В отличие от модели Stack Graphs, которая послужила основой для моего решения, оно более гетерогенно, прозрачно и отказоустойчиво, а таже обеспечивает сопоставимые показатели скорости индексации и полноты индекса при значительно меньшем размере индекса.
Прямое практическое применение моей системы — внедрение в инструменты разработки Яндекса. Учитывая масштабы компании, это может иметь значительный эффект. Хотя система была создана для Arcadia, ее архитектурные принципы универсальны. Результаты работы могут послужить основой для создания новых или улучшения существующих open source инструментов для анализа кода, предназначенных для работы с большими проектами, которые становятся все более распространенными.
В своей магистерской диссертации я разработал новую систему семантической навигации по коду, предназначенную для эффективной работы в сверхбольших монорепозиториях, таких как Arcadia в Яндексе.
Основная проблема большинства аналогов — часовые задержки при обновлении индекса для обработки накопившихся в репозитории изменений, что не позволяло, например, переиспользовать такой индекс в сценариях разработки в IDE. Мое решение предлагает пофайловую инкрементальность: при изменении одного файла переиндексируется только он, что сокращает время обновления до нескольких секунд.
Центральная идея работы заключается в отказе от графовых моделей в пользу системы переписывания строк. В моем решении семантические связи и правила разрешения имен (включая области видимости, импорты и наследование) кодируются в виде набора строковых правил. Процесс навигации, например, «Переход к определению», сводится к последовательному применению этих правил к строке-контексту, представляющей ссылку, до тех пор, пока она не приведет к строке, обозначающей определение. Для подтверждения жизнеспособности подхода я реализовал систему правил для языка Python, включая индексатор и LSP-сервер для интеграции с IDE. Эксперименты показали, что мой подход сокращает время переиндексации Python примерно в 100 раз, обеспечивая качество навигации и время отклика, сопоставимые с существующими решениями.
По сравнению с такими системами, как Kythe, Glean и SourceGraph, а также с текущим инструментом, используемым в Яндексе, мое решение на порядки ускоряет индексацию за счет пофайлово-инкрементального подхода. Фундаментально мы переносим часть сложности анализа языка в саму модель данных и реализуем ленивое разрешение ссылок в момент запроса. Поскольку модель является языко-независимой, это упрощает добавление поддержки для специфичных доменных языков, что сводится к написанию генератора правил переписывания по коду. В отличие от модели Stack Graphs, которая послужила основой для моего решения, оно более гетерогенно, прозрачно и отказоустойчиво, а таже обеспечивает сопоставимые показатели скорости индексации и полноты индекса при значительно меньшем размере индекса.
Прямое практическое применение моей системы — внедрение в инструменты разработки Яндекса. Учитывая масштабы компании, это может иметь значительный эффект. Хотя система была создана для Arcadia, ее архитектурные принципы универсальны. Результаты работы могут послужить основой для создания новых или улучшения существующих open source инструментов для анализа кода, предназначенных для работы с большими проектами, которые становятся все более распространенными.