SIEVE – «цифровое решето» для просеивания веб-кэша

На симпозиуме NSDI’24, который будет проводиться в апреле этого года в Калифорнии, ожидается представление проекта SIEVE (англ. sieve – сито, решето). Это алгоритм с открытым исходным кодом для простого и высокоэффективного «просеивания» веб-кэша. Алгоритм решает, какие элементы следует убирать из кэша, чтобы освободить место для новых записей.

Опубликованная для предварительного ознакомления часть доклада о SIEVE уже заинтересовала специалистов и вызвала волну откликов. 

Разработчики SIEVE отмечают, что алгоритм и сейчас работает хорошо, но они надеются, что при участии заинтересованных участников «open source»-комьюнити проект будет улучшаться и дальше. По их мнению, кэширование важно для любой компании, использующей веб-приложения, ведь каждый веб-сайт нуждается в системе кэширования. Однако кэширование остаётся мало изученной областью компьютерных наук.

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

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

Однако как быть, если «шкафом» пользуются миллионы людей с постоянно меняющимися потребностями? Как сделать так, чтобы самая ценная информация всегда была в кэше под рукой, а устаревшие данные отсеивались, исключались из кэша? Алгоритмы, решающие эту задачу, носят название «алгоритмы вытеснения» (cache-eviction algorithms) – они определяют, что и когда должно быть удалено из кэша.

Классическим алгоритмом вытеснения является разработанный в 1960-х годах FIFO (“first-in, first-out” – «первый на входе, первый на выходе»), незатейливо удаляющий из кэша самые старые объекты. Это словно вещи, движущиеся по ленте конвейера – дошли до конца пути – и исчезли из вида.

Алгоритм LRU (“least recently used” – «максимально долго не используемый») тоже убирает устаревшие объекты, однако если к каким-то данным за время их нахождения в кэше поступает обращение, то объект передвигается в очереди выше, то есть «перекладывается» в начало этого конвейера, тем самым увеличивая время своей жизни.

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

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

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

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

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

По материалам статьи “Computer scientists invent simple method to speed cache sifting” Carol Clark,  Emory University (https://techxplore.com/news/2024-01-scientists-simple-method-cache-sifting.html)