Cache Invalidation - существует ли общее решение?

"В" Информатике "есть только две трудные проблемы: недействительность кэша и именование вещей".

Фил Карлтон

Есть ли общее решение или метод для недействительности кеша; знать, когда запись устарела, поэтому вы всегда сможете получать свежие данные?

Например, рассмотрим функцию getData(), которая получает данные из файла. Он кэширует его на основе последнего измененного времени файла, которое он проверяет каждый раз, когда он вызывает.
Затем вы добавляете вторую функцию transformData(), которая преобразует данные и кэширует ее результат в следующий раз, когда вызывается функция. Он не знает о файле - как вы добавляете зависимость, которая, если файл изменен, этот кеш становится недействительным?

Вы можете называть getData() каждый раз при вызове transformData() и сравнивать его со значением, которое было использовано для создания кеша, но это может оказаться очень дорогостоящим.

Ответ 1

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

Если у вас есть идемпотентная функция от a, b до c, где, если a и b совпадают, то c совпадает, но стоимость проверки b равна но вы также:

согласитесь, что вы когда-нибудь работаете с устаревшей информацией и не всегда проверяете b
сделайте свой уровень лучше, чтобы сделать проверку b как можно быстрее

Вы не можете получить свой торт и съесть его...

Если вы можете сложить дополнительный кеш на основе a сверху, это влияет на начальную проблему не на один бит. Если вы выбрали 1, то у вас есть свобода, которую вы дали себе, и, таким образом, можете больше кэшировать, но должны помнить о действительности кешированного значения b. Если вы выбрали 2, вы все равно должны проверять b каждый раз, но можете вернуться в кеш для a, если b проверяет.

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

Если вы знаете, что a всегда имеет силу, если b делает это, вы можете упорядочить свой кеш так (псевдокод):

private map<b,map<a,c>> cache // 
private func realFunction    // (a,b) -> c

get(a, b) 
{
    c result;
    map<a,c> endCache;
    if (cache[b] expired or not present)
    {
        remove all b -> * entries in cache;   
        endCache = new map<a,c>();      
        add to cache b -> endCache;
    }
    else
    {
        endCache = cache[b];     
    }
    if (endCache[a] not present)     // important line
    {
        result = realFunction(a,b); 
        endCache[a] = result;
    }
    else   
    {
        result = endCache[a];
    }
    return result;
}

Очевидно, что последовательное расслоение (скажем, x) тривиально до тех пор, пока на каждом этапе достоверность вновь добавленного ввода соответствует соотношению a: b для x: b и x:. a

Однако вполне возможно, что вы могли бы получить три входа, действительность которых была полностью независимой (или была циклической), поэтому невозможно было бы расслоение. Это означало бы, что строка, помеченная //important, должна была бы измениться на

if (endCache [a] истек или нет)

Ответ 2

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

Я не думаю, что есть какое-то общее волшебное решение, чтобы проблема исчезла. Но во многих практических случаях вполне могут быть возможности трансформировать подход, основанный на опросе, на основе "прерывания", который может заставить проблему просто уйти.

Ответ 3

Если вы собираетесь getData() каждый раз, когда вы выполняете преобразование, то вы исключили все преимущества кэша.

В вашем примере кажется, что решение будет возникать при создании преобразованных данных, а также сохранить имя файла и последнее измененное время файла, из которого были сгенерированы данные (вы уже сохранили это в любой структуре данных by getData(), поэтому вы просто копируете эту запись в структуру данных, возвращаемую функцией transformData()), а затем, когда вы снова вызываете transformData(), проверьте последнее измененное время файла.

Ответ 4

Сейчас я работаю над подходом, основанным на PostSharp и memoizing functions. Я запустил его мимо моего наставника, и он согласен с тем, что это хорошая реализация кэширования в агностическом контексте.

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

Ответ 5

IMHO, функциональное реактивное программирование (FRP) в некотором смысле является общим способом решения проблемы отказа от кэширования.

Вот почему: устаревшие данные в терминологии FRP называются сбой. Одна из целей FRP - гарантировать отсутствие сбоев.

FRP более подробно объясняется в этом "Суть обсуждения FRP" и в этом SO ответьте.

В talk Cell представляет кешированный объект/сущность, а Cell обновляется, если обновляется одна из этих зависимостей,

FRP скрывает сантехнический код, связанный с графиком зависимостей, и гарантирует, что нет устаревших Cell s.

Ответ 6

Есть ли общее решение или метод создания кеша, чтобы знать, когда запись устарела, поэтому вы всегда сможете получать свежие данные?

Нет, потому что все данные разные. Некоторые данные могут быть "устаревшими" через минуту, некоторые через час, а некоторые могут быть прекрасными в течение нескольких дней или месяцев.

Что касается вашего конкретного примера, самым простым решением является функция "проверки кеша" для файлов, которые вы вызываете как из getData, так и transformData.

Ответ 7

Нет общего решения, но:

Кэш может действовать как прокси (pull). Предположим, что ваш кеш знает последнюю временную метку изменения времени, когда кто-то звонит getData(), кеш запрашивает источник для последней метки времени изменения, если то же самое, он возвращает кеш, в противном случае он обновляет свой контент с исходным кодом и возвращает его содержимое, (Вариант - это клиент для прямой отправки метки времени по запросу, источник будет возвращать только содержимое, если его временная метка отличается.)
Вы все равно можете использовать процесс уведомления (push), кеш наблюдаете за источником, если источник изменяется, он отправляет уведомление в кеш, который затем помечен как "грязный". Если кто-то звонит getData(), кеш будет сначала обновляться до источника, удалите флаг "грязный"; затем верните его содержимое.

Выбор, вообще говоря, зависит от:

Частота: многие вызовы на getData() предпочли бы push, чтобы избежать того, чтобы источник был затоплен функцией getTimestamp.
Ваш доступ к источнику: владеете ли вы исходной моделью? Если нет, возможно, вы не можете добавить процесс уведомления.

Примечание. Поскольку использование метки времени является традиционным способом работы http-прокси, другой подход заключается в совместном использовании хеша содержимого. Единственный способ, которым я знаю, чтобы два объекта были обновлены вместе, либо я называю вас (тянуть), либо вы называете меня... (нажмите), что все.

Ответ 8

Возможно, кэш-забывающие алгоритмы будут наиболее общими (или, по крайней мере, менее зависимыми от конфигурации оборудования), поскольку они сначала будут использовать самый быстрый кеш и перейти оттуда. Здесь лекция MIT на нем: Кэшированные забытые алгоритмы