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