Оптимизация экономики облачных вычислений с помощью линейного эластичного кэширования
Линейное эластичное кэширование минимизирует общие затраты на кэширование, рассматривая вытеснение страниц как задачу проката лыж, используя легковесное машинное обучение для оптимизации компромисса между объемом используемой памяти и промахами кэша.
Современные высокопроизводительные системы баз данных и облачные сервисы используют кэширование в оперативной памяти для хранения часто используемых данных, что позволяет обойти медленные операции с диском и обеспечить молниеносную скорость отклика, ожидаемую пользователями. Но за эту производительность приходится платить (в прямом смысле): высокоскоростная память дорога, и некоторые поставщики бессерверных облачных услуг взимают до 3 долларов в день всего за 1 ГБ памяти.
Исторически управление кэшем рассматривалось как задача с фиксированным объемом ресурсов. При использовании обычного кэширования фиксированного размера инженеры выделяют определенный объем памяти для кэша, а система использует политики вытеснения, такие как алгоритм наименее часто используемых данных (LRU), чтобы определить, какие данные следует сохранить, когда это пространство закончится. Это приводит к классической проблеме «золотой середины»: слишком маленький размер кэша приводит к резкому падению производительности; слишком большой размер для пиковой нагрузки приводит к потере тысяч долларов на простаивающей памяти.
В статье, опубликованной на конференции по инновационным исследованиям в области систем обработки данных (CIDR), мы представили линейное эластичное кэширование — новый подход, разработанный для минимизации общей стоимости владения (TCO) управлением кэшем за счет динамической корректировки размера кэша в ответ на рабочие нагрузки в реальном времени. Вместо того чтобы рассматривать память как фиксированный, предварительно выделенный ресурс, мы рассматриваем ее как утилиту, стоимость которой линейно зависит как от размера кэшированных данных, так и от продолжительности их хранения в кэше. Рассматривая объем используемой памяти как переменную стоимость, интегрируемую во времени, мы показали, что можем значительно снизить затраты без ущерба для производительности системы.
Подход к запоминанию, напоминающий «прокат лыж».
Чтобы решить задачу динамического изменения размера кэша, давайте воспользуемся классической задачей проката лыж. Представьте, что вы отправляетесь в лыжную поездку неизвестной продолжительности. Каждый день перед вами встает выбор: арендовать лыжи за небольшую ежедневную плату или купить их за большую сумму и кататься бесплатно после этого. Если бы вы точно знали, сколько дней будете кататься, выбор был бы очевиден. Но без этой информации вам нужен алгоритм, который минимизирует ваши общие затраты.
Аналогично, в линейном эластичном кэше каждый фрагмент данных сталкивается с сопоставимой дилеммой. При обращении к фрагменту данных система должна выбрать один из двух вариантов:
- «Аренда» пространства: храните данные в оперативной памяти и платите постоянную плату за занимаемую ею память.
- «Выкупить» промах: удалить данные, чтобы сэкономить память, но рискнуть понести дополнительные издержки (задержку и потери при вводе-выводе), если данные понадобятся снова в ближайшее время.
В то же время система не может оптимизировать каждый фрагмент данных независимо, поскольку кэш имеет максимальный выделенный размер (представьте себе большую группу людей на горнолыжном курорте, где курорт предлагает лишь ограниченное количество лыж). Наш основной теоретический вклад доказывает, что мы можем оптимизировать эти два фактора — политику вытеснения и продолжительность «аренды» — по отдельности. Такое разделение хорошо подходит для чистой практической реализации. Мы можем использовать алгоритм проката лыж для определения времени жизни (TTL) страницы (аналогично продолжительности аренды). Если страница не используется повторно до истечения срока действия TTL, она автоматически вытесняется. Но если кэш физически заполняется, вступает в действие традиционная политика вытеснения, такая как политика наименее часто используемых (LRU), для управления пространством.
Традиционные алгоритмы для онлайн-сервисов ориентированы на обеспечение гарантий производительности в наихудшем случае. В задаче проката лыж классический алгоритм «точки безубыточности» заключается в том, чтобы сдавать лыжи в аренду до тех пор, пока накопленная стоимость не сравняется с ценой покупки, а затем покупать их. Хотя этот подход (и его рандомизированный аналог) обеспечивают надежные гарантии производительности в наихудшем случае, производственные нагрузки в основном предсказуемы. Доступ к данным в таких системах, как Spanner — наша глобально распределенная база данных — часто следует определенным закономерностям, которые можно использовать для принятия более эффективных решений о прокате.
Тестирование линейного эластичного кэширования
Чтобы убедиться в достоверности нашей теории в реальных условиях, мы провели обширные эксперименты, используя два основных источника:
- Производственные нагрузки: Мы интегрировали систему в Spanner.
- Публичные трассировки: Мы провели тестирование с использованием различных общедоступных трассировок кэша из отраслевых бенчмарков, чтобы убедиться, что результаты не являются специфичными для инфраструктуры Google.
Производственные нагрузки
Мы разработали практичный алгоритм, который назначает время жизни (TTL) кэшированной странице при каждом запросе страницы на основе шаблонов доступа к странице и стоимости. Поскольку Spanner обрабатывает миллиарды запросов в секунду, эта модель прогнозирования TTL должна быть невероятно легковесной. Мы выбрали неглубокое дерево решений, которое можно преобразовать в несколько строк кода на C++. Полученный код также легко интерпретируется и предоставляет ценную информацию о характеристиках рабочей нагрузки. Эта модель учитывает такие характеристики, как размер данных, стоимость промаха кэша (когда данные отсутствуют в кэше, и системе необходимо получить их из другой, более медленной системы, например, диска) и тип выполняемой операции с базой данных, чтобы предсказать оптимальное значение TTL для каждой страницы.
Мы внедряли политику эластичного кэширования на производственные серверы Spanner в течение нескольких месяцев. По сравнению со стандартным кэшем фиксированного размера результаты оказались существенными:
- Использование памяти: снижено на 15,5%.
- Количество промахов кэша: увеличилось всего на 5,5%.
- Общая стоимость владения (TCO): снижена примерно на 5%.
Что особенно важно, поскольку алгоритм учитывает затраты, неболькое увеличение количества промахов кэша было сосредоточено на данных, которые дешево извлекать из хранилища, а это значит, что влияние на фактические затраты на ввод-вывод составило незначительные 0,5%.
Общедоступные следы
Мы также оценили наш подход к эластичному кэшированию, используя несколько общедоступных трассировок кэша. В качестве базовой политики фиксированного размера кэша мы использовали оптимизированную реализацию алгоритма вытеснения жадного алгоритма с двойной частотой изменения размера (GDSF) — обобщение известной политики LRU, допускающее страницы разных размеров.
Мы рассмотрели четыре варианта эластичного кэширования в зависимости от используемого алгоритма проката лыж и от того, применяли ли мы модель машинного обучения. Поскольку доступные общедоступные трассировки не содержат функций на уровне приложения, доступных для обучения, мы не использовали деревья решений для прогнозирования. Вместо этого мы разработали простую стратегию обучения, которая разделяет каждую трассировку пополам и использует первую половину для обучения. Для каждой отдельной страницы в обучающей трассировке мы вычисляли оптимальное значение TTL для страницы, которое минимизирует затраты по всей обучающей трассировке.
Поскольку поведение кэша меняется в зависимости от его первоначального содержимого, распространенной практикой, известной как «прогрев», является использование некоторого префикса трассировки кэша для его заполнения, но без фактического измерения производительности. Мы прогрели все кэши запросами за один день из второй половины трассировки, а остальную часть использовали для тестирования и измерений. Во время тестовой трассировки, если мы встречали страницу, которая уже встречалась во время обучения, мы устанавливали TTL равным наилучшему предварительно вычисленному значению TTL для этой страницы. В противном случае мы устанавливали TTL, используя либо политику безубыточности, либо рандомизированную политику.
Результаты
Мы обнаружили, что эластичное кэширование неизменно превосходит кэши фиксированного размера при различных рабочих нагрузках. По мере увеличения стоимости памяти относительно стоимости промаха кэша экономия, обеспечиваемая эластичным кэшированием, становится еще более заметной.
Как показывают приведенные ниже данные, эластичные политики кэширования приводят к значительному снижению общих затрат за счет динамической адаптации размера кэша к рабочей нагрузке. Мы также отмечаем, что эластичные политики приводят к гораздо более низкому проценту промахов кэша по сравнению с политиками фиксированного размера при сопоставимом объеме.
График зависимости общей стоимости (память + промахи кэша), понесенной при различных политиках кэширования, от емкости кэша. По мере увеличения емкости кэша базовая политика GDSF приводит к высоким затратам из-за увеличения расходов на память, в то время как эластичная политика кэширования адаптирует используемый размер кэша к рабочему набору задач и поддерживает более низкую общую стоимость.
График зависимости частоты промахов кэша от среднего размера кэша. Диаграмма демонстрирует, что (варианты) эластичных политик кэширования стабильно поддерживают значительно более низкую частоту промахов кэша по сравнению с традиционной политикой фиксированного размера, подчеркивая эффективность динамического перераспределения памяти в реальном времени по сравнению с выделением статических лимитов.
Заключение
Линейное эластичное кэширование представляет собой сдвиг в нашем понимании облачной инфраструктуры. Отказавшись от статического выделения ресурсов в пиковые нагрузки и перейдя к динамической, учитывающей затраты модели, мы можем создавать системы, которые будут одновременно высокопроизводительными и экономически эффективными.
Наша оценка эффективности этих обученных стратегий проката лыж в различных рабочих нагрузках Spanner показывает, что даже небольшие, легковесные модели машинного обучения могут оказать огромное влияние при применении к основной инфраструктуре. Поскольку облачные среды продолжают предлагать более детализированное ценообразование с оплатой по мере использования ресурсов, гибкие стратегии станут необходимыми для любого крупномасштабного сервиса, стремящегося оптимизировать свою глобальную сеть.
Благодарности
Это результат совместной работы с Тамашем Сарлосом (Google) и Рави Кумаром (Google), представленный на конференции по инновационным исследованиям в области систем обработки данных (CIDR) 2025.
Источник: research.google
Оцените материал:
