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

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

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

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

Источник: Ferra