Ученые-компьютерщики изобрели очень эффективный, но невероятно простой алгоритм, позволяющий решить, какие элементы выбросить из веб-кэша, чтобы освободить место для новых. Новый алгоритм с открытым исходным кодом, известный как SIEVE, потенциально может изменить управление веб-трафиком в больших масштабах.

SIEVE — это совместный проект ученых-компьютерщиков из Университета Эмори, Университета Карнеги-Меллона и Фонда Пеликан. Доклад группы по SIEVE будет представлен на 21-м симпозиуме USENIX по проектированию и внедрению сетевых систем (NSDI) в Санта-Кларе, Калифорния, в апреле.

Препринт статьи уже наделал много шума.

«SIEVE больше и значительнее, чем просто мы», — говорит Ячжуо Чжан, доктор философии Эмори. студент и соавтор статьи. «Он уже работает хорошо, но мы получаем много хороших предложений, как сделать его еще лучше. В этом красота мира с открытым исходным кодом».

Чжан разделяет первое авторство статьи с Цзюньчэном (Джейсоном) Яном, который получил степень магистра компьютерных наук в Эмори и сейчас является доктором философии. кандидат в Карнеги-Меллон.

«SIEVE — это простое улучшение проверенного алгоритма вытеснения кэша , который использовался десятилетиями, а в мире вычислений это буквально столетия», — говорит Имир Вигфуссон, доцент кафедры компьютерных наук Университета Эмори.

Вигфуссон является соавтором статьи вместе с Рашми Винаяк, доцентом кафедры компьютерных наук Карнеги-Меллона. Яо Юэ, компьютерный инженер из Фонда Пеликан, также является соавтором.

Помимо скорости и эффективности, ключевым фактором, вызывающим интерес к SIEVE, является его простота, обеспечивающая масштабируемость.

«Простота — это высшая степень изысканности», — говорит Вигфуссон. «Чем проще элементы системы, предназначенной для обслуживания миллиардов людей за доли секунды, тем легче эффективно внедрить и поддерживать эту систему».

Держите «горячие предметы» под рукой

Многие люди понимают ценность регулярной реорганизации своего гардероба. Предметы, которые никогда не используются, можно выбросить, а те, которые используются редко, можно перенести на чердак или в другое удаленное место. Благодаря этому предметы, которые чаще всего носят, находятся в пределах легкой досягаемости, поэтому их можно быстро найти, не роясь вокруг.

Кэш подобен хорошо организованному шкафу для компьютерных данных. Кэш заполняется копиями наиболее популярных объектов, запрашиваемых пользователями, или «горячих объектов» в ИТ-терминологии. Кэш хранит эту небольшую коллекцию «горячих» объектов отдельно от основной базы данных компьютерной сети, которая подобна огромному складу, заполненному всей информацией, которую может обслужить система.

Кэширование «горячих» объектов позволяет сетевой системе работать более эффективно, быстро реагируя на запросы пользователей. Веб-приложение может эффективно обрабатывать больший трафик, заходя в удобный шкаф и захватывая большинство нужных пользователям объектов, вместо того, чтобы отправляться на склад и искать в огромной базе данных каждый запрос.

«Кэширование присутствует повсюду», — говорит Чжан. «Это важно для каждой компании, большой или маленькой, использующей веб-приложения. Каждому веб-сайту необходима система кэширования».

И все же кэширование относительно недостаточно изучено в области информатики.

Как работает кэширование

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

Эксплуатация быстрой кэш-памяти требует больших затрат, но она имеет решающее значение для удобства работы веб-пользователей. Цель состоит в том, чтобы сохранить наиболее полезную будущую информацию в кеше. Другие объекты необходимо постоянно отсеивать или «выселять», выражаясь технической терминологией, чтобы освободить место для меняющегося массива горячих объектов.

Алгоритмы вытеснения кэша определяют, какие объекты выбрасывать и когда это делать.

FIFO, или «первым пришел — первым ушел», — это классический алгоритм выселения, разработанный в 1960-х годах. Представьте себе объекты, выстроенные в ряд на конвейерной ленте. Новые запрошенные объекты поступают слева, а самые старые объекты удаляются, когда они достигают конца строки справа.

В алгоритме LRU («наименее недавно использованный») объекты также перемещаются по линии в сторону выселения в конце. Однако если объект запрашивается снова во время его движения по конвейерной ленте, он перемещается обратно в начало линии.

Существуют сотни вариантов алгоритмов выселения, но для повышения эффективности они имеют тенденцию усложняться. Обычно это означает, что они непрозрачны для размышлений и требуют серьезного обслуживания, особенно при работе с огромными рабочими нагрузками.

«Если алгоритм очень сложен, в нем, как правило, больше ошибок, и все эти ошибки необходимо исправлять», — объясняет Чжан.

Простая идея

Подобно LRU и некоторым другим алгоритмам, SIEVE вносит простую настройку в базовую схему FIFO.

SIEVE изначально помечает запрошенный объект как «ноль». Если объект запрашивается повторно при движении по ленте, его статус меняется на «один». Когда объект с меткой «один» достигает конца строки, он автоматически сбрасывается на «ноль» и вытесняется.

Указатель или «движущаяся рука» также сканирует объекты, когда они перемещаются по линии. Указатель начинается в конце линии, а затем прыгает к голове, двигаясь по непрерывному кругу. Каждый раз, когда указатель попадает на объект с меткой «ноль», объект удаляется.

«Важно как можно быстрее выселять непопулярные объекты, и SIEVE очень быстро справляется с этой задачей», — говорит Чжан.

В дополнение к этому быстрому понижению статуса объектов SIEVE удается поддерживать популярные объекты в кеше с минимальными вычислительными затратами, что в компьютерной терминологии называется «ленивым продвижением». Исследователи полагают, что SIEVE — это простейший алгоритм удаления кэша, позволяющий эффективно добиться как быстрого понижения уровня, так и ленивого продвижения.

Меньший коэффициент промахов

Целью кэширования является достижение низкого коэффициента ошибок — доли запрошенных объектов, которая должна быть извлечена из «склада».

Чтобы оценить SIEVE, исследователи провели эксперименты со следами веб-кэша с открытым исходным кодом из Wikimedia, X и четырех других крупных наборов данных. Результаты показали, что SIEVE достигает более низкого коэффициента ошибок, чем девять современных алгоритмов, на более чем 45% трасс. Следующий лучший алгоритм имеет меньший коэффициент ошибок — всего 15%.

Легкость и простота SIEVE поднимает вопрос, почему никто раньше не придумал этот метод. По мнению Чжана, внимание команды SIEVE к тому, как изменились модели веб-трафика за последние годы, возможно, имело значение.

«Например, — говорит она, — новые предметы теперь быстро становятся «горячими», но также быстро и исчезают. Люди постоянно теряют к вещам интерес, потому что новые вещи продолжают появляться».

Рабочие нагрузки веб-кэша, как правило, следуют так называемым обобщенным распределениям Zipfian, где на небольшое подмножество объектов приходится большая часть запросов. SIEVE, возможно, нашел золотую середину Zipfian для текущих рабочих нагрузок.

«Это явно преобразующий момент в нашем понимании вытеснения веб-кэша», — говорит Вигфуссон. «Это меняет конструкцию, которая так долго использовалась вслепую».

Даже небольшое улучшение системы веб-кэширования, добавляет он, может сэкономить миллионы долларов в крупном центре обработки данных.

Чжан и Ян собираются получить докторскую степень в мае.

«Они проделывают невероятную работу», — говорит Вигфуссон. «Можно с уверенностью сказать, что они оба сейчас входят в число мировых экспертов по вытеснению веб-кэша».