Experimental chill

Удивительно, не думал, что об этом писали, но мы аж 2 года назад выложили статью про так называемый Flash cache! https://www.usenix.org/conference/atc22/presentation/yang-tzu-wei

Проблема: HDD дешёвый и, в основном, данные лежат на нём, но вот читать часто горячие куски с HDD не хочется. По всему гуглу перед чтением из Colossus (successor to Google File System) стоит SSD cache. Кеш этот большой и автоматический, то есть ничего пользователям не надо делать.

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

Была выбрана LARC стратегия, потому что 60% всех чтений с диска -- одноразовые, а LARC вставлял элемент в кеш только если его читали во второй раз (то есть было два промаха сравнительно недавно). Прожило это дело лет 6, со временем стало недостаточно, потому что если вы прочитали 1000 файлов, а потом ещё раз 1000 файлов быстро, то окажется, что вы очень сильно и быстро нагрузили SSD. Эту проблему пытались полечить SSD Throttler, чтобы писать меньше в короткие промежутки, но такое решение не учитывало разнообразие того, как ведут себя разные клиенты. Кому-то реально надо прочитать два раза, но зато потом не будет никаких промахов. Ещё одна проблема, что LARC всё таки промахивается два раза перед тем, как не промахиваться и в итоге была эвристика, которая оценивала, хорош ли LARC и выключала себя, если промахиваться два раза всё таки было странным. Всё обростало эвристиками и сложностями, и надо было переделывать на что-то более автоматическое.

В итоге решение было многогранным: взять много стратегий по своей жёсткости и оценивать насколько они хорошо работают в режиме реального времени. Учитывать это для принятие решений.

Были выбраны такие стратегии:

NeverAdmit < AdmitOnSecondMiss < AdmitOnMiss < AdmitOnWrite.

То есть никогда не вставлять блоки, вставлять только если промазали 2 раза, вставлять, если промазали (но не совсем как LRU, а с TTL) и вставлять если записали или промазали.

Чтобы понять какие стратегии самые лучшие, решаются задачи о рюкзаке. С данным TTL, статистикой доступа от клиентов и разными стратегиями, стоимостью разных операций (прочитать с HDD и тд), определяется оптимальная стратегия. Раз в какое-то время снова решают такие задачи. Выбирают один TTL с лучшей стратегией.

В результатах получается суммарная стоимость меньше на 6%, более адаптивный подход к SSD кешу и счастливые пользователи.

Внутри этот кеш достаточно известен, потому что находится во всех дэшбордах.

Wikipedia

Adaptive replacement cache

cache management algorithm

www.group-telegram.com/us/experimentalchill.com/275

19.3K viewsJul 5, 2024 at 13:17

Удивительно, не думал, что об этом писали, но мы аж 2 года назад выложили статью про так называемый Flash cache! https://www.usenix.org/conference/atc22/presentation/yang-tzu-wei

Проблема: HDD дешёвый и, в основном, данные лежат на нём, но вот читать часто горячие куски с HDD не хочется. По всему гуглу перед чтением из Colossus (successor to Google File System) стоит SSD cache. Кеш этот большой и автоматический, то есть ничего пользователям не надо делать.

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

Была выбрана LARC стратегия, потому что 60% всех чтений с диска -- одноразовые, а LARC вставлял элемент в кеш только если его читали во второй раз (то есть было два промаха сравнительно недавно). Прожило это дело лет 6, со временем стало недостаточно, потому что если вы прочитали 1000 файлов, а потом ещё раз 1000 файлов быстро, то окажется, что вы очень сильно и быстро нагрузили SSD. Эту проблему пытались полечить SSD Throttler, чтобы писать меньше в короткие промежутки, но такое решение не учитывало разнообразие того, как ведут себя разные клиенты. Кому-то реально надо прочитать два раза, но зато потом не будет никаких промахов. Ещё одна проблема, что LARC всё таки промахивается два раза перед тем, как не промахиваться и в итоге была эвристика, которая оценивала, хорош ли LARC и выключала себя, если промахиваться два раза всё таки было странным. Всё обростало эвристиками и сложностями, и надо было переделывать на что-то более автоматическое.

В итоге решение было многогранным: взять много стратегий по своей жёсткости и оценивать насколько они хорошо работают в режиме реального времени. Учитывать это для принятие решений.

Были выбраны такие стратегии:

NeverAdmit < AdmitOnSecondMiss < AdmitOnMiss < AdmitOnWrite.

То есть никогда не вставлять блоки, вставлять только если промазали 2 раза, вставлять, если промазали (но не совсем как LRU, а с TTL) и вставлять если записали или промазали.

Чтобы понять какие стратегии самые лучшие, решаются задачи о рюкзаке. С данным TTL, статистикой доступа от клиентов и разными стратегиями, стоимостью разных операций (прочитать с HDD и тд), определяется оптимальная стратегия. Раз в какое-то время снова решают такие задачи. Выбирают один TTL с лучшей стратегией.

В результатах получается суммарная стоимость меньше на 6%, более адаптивный подход к SSD кешу и счастливые пользователи.

Внутри этот кеш достаточно известен, потому что находится во всех дэшбордах.

BY Experimental chill