HighLoad Cup. Победитель из Технотрека
9 Октябрь 2017
Неделю назад мы рассказывали о HighLoad Cup - соревновании разработчиков высоконагруженных систем. Напомним, что в рамках соревнования участникам было предложено создать автономное отзывчивое серверное приложение, собрать его в docker-контейнер и залить в хранилище, а затем обстрелять на выданных боевых данных.
Первое место в HighLoad Cup занял студент Технотрека Никита Уваров. В этой статье он рассказывает о предпосылках, технических деталях и фишке, обеспечившей победу.
Хобби, которое станет работой
Я начал с “языка” Scratch, в седьмом классе познакомился с Си, а 9 классе занялся олимпиадным программированием и занимаюсь им до сих пор. Надеюсь попасть на финал ACM ICPC. В основном я пишу на C++, немного - на Python. Мне нравится заниматься алгоритмическими и оптимизационными марафонскими задачами. Кроме того, я посматриваю в сторону машинного обучения. Программирование для меня - это хобби, которое, думаю, станет моей работой.
Три причины участвовать в HighLoad Cup
Почему я решил участвовать в HLC? Мне хотелось выиграть iPad :) А поскольку чемпионат проводился впервые, я подумал, что сильной конкуренции быть не должно (как же сильно я ошибся!). Вместе с этим я был уверен, что мне помогут алгоритмические навыки - все-таки речь шла об оптимизации запросов.
Время на победу
Чем больше участвуешь в безумной гонке, тем обиднее проигрывать, поэтому я занимался решением почти каждый день. Думаю, суммарно я потратил на чемпионат около 60-70 часов.
Что было “под капотом”
“Под капотом” моего решения - “велосипед” на C/C++, который использует epoll API для работы с сетью, вручную парсит HTTP протокол и формирует ответы. Для минимизации времени отклика я использовал busy polling, кешировал полный HTTP ответ на статические запросы (которых было 60%). В динамических запросах с фильтрацией по времени старался не “пробегаться” по лишним записям, предварительно определяя границы нужного диапазона бинарным поиском. Думаю, это стандартный набор оптимизацией у всех топовых участников.
Ключевой фишкой своего решения, которую я добавил в последний день, я считаю попытку обойти аномальное “вставание” системных вызовов accept и write - у себя на компьютере я заметил, что в условиях большого числа одновременных соединений эти вызовы иногда выполняются не за 50-100 мкс (что является средним временем их выполнения), а, к примеру, за полсекунды. Такая задержка моментально сказывается на результате, а вдобавок еще и заставляет исполнителя обстрела повышать число одновременных соединений (поскольку он стремится выдавать постоянное число запросов в единицу времени). Причину этих задержек я не нашел, но, чтобы нивелировать их влияние, исхитрился в архитектуре: у меня 4 потока. Один из них читает (epoll_wait, read) и обрабатывает все запросы, а остальные выполняют системные вызовы accept и write. В результате, как мне кажется, мое решение более устойчиво к “пикам”, то есть оно чаще выдает результат, близкий к своему теоретически минимальному. В финале было 24 запуска, может показаться, что это много, но, по некоторым причинам, “хороших” (тех, на которых не встало слишком много системных вызовов, и которые пришлись на “быстрые” сервера) из них всего 5-6. А чем больше “хороших” запусков, тем больше дисперсия играет на участника.
Поиск идей
Стоит сказать, что никакого опыта Highload и даже web-разработки до конкурса у меня не было. Первое, что я загуглил, - какие существуют библиотеки и API для высокопроизводительной работы с сетью. Спустя неделю был готов объемный каркас “велосипедного” сервера. Дальнейшая работа над заданием состояла в экспериментах. Я много читал про устройство TCP-стека, а также изучал документацию по различным опциям сокетов. Сложно было из ниоткуда находить новые идеи для тюнинга.
Извлеченный опыт
До конкурса мое представление о сети было следующим: есть recv/send, которые во всех примерах по сокетам, и есть boost::asio, который каким-то магическим образом решает проблему c10k, устроен очень сложно и человеческому пониманию не поддается. Теперь же я знаю, что никакой магии нет, и boost::asio реально обойти, если спуститься на уровень ниже.
Техническую фишку, которую я считаю ключевой, я описал выше. А в общем, мне помогло выиграть то, что, будучи безработным студентом, я потратил на решение много времени :)
Я планирую посмотреть на следующий HighLoad Cup. Организаторы обещают данные, которые не помещаются в память, - очень интересно, можно ли на велосипеде обогнать enterprise базы данных.
В качестве совета будущим участникам скажу следующее: помимо базового знакомства с сетью на уровне принципов, нужно просто быть готовым много гуглить и экспериментировать. Сегодня победил велосипедный C++, завтра победит Tarantool.
Хотелось бы сказать организаторам спасибо за познавательный и очень динамичный конкурс. Когда в 4 часа ночи, сидя в пустом аэропорту, находишь эту самую волшебную пилюлю, busy polling, и поднимаешь планку лидерборда с 30 секунд до 15 - это море адреналина.
Первое место в HighLoad Cup занял студент Технотрека Никита Уваров. В этой статье он рассказывает о предпосылках, технических деталях и фишке, обеспечившей победу.
Хобби, которое станет работой
Я начал с “языка” Scratch, в седьмом классе познакомился с Си, а 9 классе занялся олимпиадным программированием и занимаюсь им до сих пор. Надеюсь попасть на финал ACM ICPC. В основном я пишу на C++, немного - на Python. Мне нравится заниматься алгоритмическими и оптимизационными марафонскими задачами. Кроме того, я посматриваю в сторону машинного обучения. Программирование для меня - это хобби, которое, думаю, станет моей работой.
Три причины участвовать в HighLoad Cup
Почему я решил участвовать в HLC? Мне хотелось выиграть iPad :) А поскольку чемпионат проводился впервые, я подумал, что сильной конкуренции быть не должно (как же сильно я ошибся!). Вместе с этим я был уверен, что мне помогут алгоритмические навыки - все-таки речь шла об оптимизации запросов.
Время на победу
Чем больше участвуешь в безумной гонке, тем обиднее проигрывать, поэтому я занимался решением почти каждый день. Думаю, суммарно я потратил на чемпионат около 60-70 часов.
Что было “под капотом”
“Под капотом” моего решения - “велосипед” на C/C++, который использует epoll API для работы с сетью, вручную парсит HTTP протокол и формирует ответы. Для минимизации времени отклика я использовал busy polling, кешировал полный HTTP ответ на статические запросы (которых было 60%). В динамических запросах с фильтрацией по времени старался не “пробегаться” по лишним записям, предварительно определяя границы нужного диапазона бинарным поиском. Думаю, это стандартный набор оптимизацией у всех топовых участников.
Ключевой фишкой своего решения, которую я добавил в последний день, я считаю попытку обойти аномальное “вставание” системных вызовов accept и write - у себя на компьютере я заметил, что в условиях большого числа одновременных соединений эти вызовы иногда выполняются не за 50-100 мкс (что является средним временем их выполнения), а, к примеру, за полсекунды. Такая задержка моментально сказывается на результате, а вдобавок еще и заставляет исполнителя обстрела повышать число одновременных соединений (поскольку он стремится выдавать постоянное число запросов в единицу времени). Причину этих задержек я не нашел, но, чтобы нивелировать их влияние, исхитрился в архитектуре: у меня 4 потока. Один из них читает (epoll_wait, read) и обрабатывает все запросы, а остальные выполняют системные вызовы accept и write. В результате, как мне кажется, мое решение более устойчиво к “пикам”, то есть оно чаще выдает результат, близкий к своему теоретически минимальному. В финале было 24 запуска, может показаться, что это много, но, по некоторым причинам, “хороших” (тех, на которых не встало слишком много системных вызовов, и которые пришлись на “быстрые” сервера) из них всего 5-6. А чем больше “хороших” запусков, тем больше дисперсия играет на участника.
Поиск идей
Стоит сказать, что никакого опыта Highload и даже web-разработки до конкурса у меня не было. Первое, что я загуглил, - какие существуют библиотеки и API для высокопроизводительной работы с сетью. Спустя неделю был готов объемный каркас “велосипедного” сервера. Дальнейшая работа над заданием состояла в экспериментах. Я много читал про устройство TCP-стека, а также изучал документацию по различным опциям сокетов. Сложно было из ниоткуда находить новые идеи для тюнинга.
Извлеченный опыт
До конкурса мое представление о сети было следующим: есть recv/send, которые во всех примерах по сокетам, и есть boost::asio, который каким-то магическим образом решает проблему c10k, устроен очень сложно и человеческому пониманию не поддается. Теперь же я знаю, что никакой магии нет, и boost::asio реально обойти, если спуститься на уровень ниже.
Техническую фишку, которую я считаю ключевой, я описал выше. А в общем, мне помогло выиграть то, что, будучи безработным студентом, я потратил на решение много времени :)
Я планирую посмотреть на следующий HighLoad Cup. Организаторы обещают данные, которые не помещаются в память, - очень интересно, можно ли на велосипеде обогнать enterprise базы данных.
В качестве совета будущим участникам скажу следующее: помимо базового знакомства с сетью на уровне принципов, нужно просто быть готовым много гуглить и экспериментировать. Сегодня победил велосипедный C++, завтра победит Tarantool.
Хотелось бы сказать организаторам спасибо за познавательный и очень динамичный конкурс. Когда в 4 часа ночи, сидя в пустом аэропорту, находишь эту самую волшебную пилюлю, busy polling, и поднимаешь планку лидерборда с 30 секунд до 15 - это море адреналина.
