Недействительность кэша - есть ли общее решение?

Question

"В Computer Science есть только две серьезные проблемы: аннулирование кэша и присвоение имен".

Фил Карлтон

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

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

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

Answer 1

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

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

1. принять, что вы когда-нибудь оперируете устаревшей информацией и не всегда проверяете b
2. сделай свой уровень лучше, чтобы сделать проверку 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,

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

если (endCache[a] истек или отсутствует)

Answer 2

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

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

Answer 3

ИМХО, Функциональное Реактивное Программирование (FRP) в некотором смысле является общим способом решения аннулирования кэша.

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

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

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

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

---

Другой способ (отличный от FRP), который я могу придумать, - это обернуть вычисленное значение (типа bв писательскую монаду Writer (Set (uuid)) b где Set (uuid) (Нотация Haskell) содержит все идентификаторы изменяемых значений, по которым вычисляется значение b зависит. Так, uuid это некоторый уникальный идентификатор, который идентифицирует изменяемое значение / переменную (скажем, строку в базе данных), по которой вычисляется b зависит.

Объедините эту идею с комбинаторами, которые работают с писателем Монадой такого рода, и это может привести к некоторому общему решению по аннулированию кэша, если вы используете эти комбинаторы только для вычисления нового b, Такие комбинаторы (скажем специальная версия filter) взять писатель монады и (uuid, a)-в качестве входов, где a изменяемые данные / переменная, идентифицируемая uuid,

Поэтому каждый раз, когда вы меняете "оригинальные" данные (uuid, a) (скажем, нормализованные данные в базе данных, из которой b был вычислен), на котором вычисляется значение типа b зависит, то вы можете сделать недействительным кеш, который содержит b если вы измените любое значение a на котором вычисляется b значение зависит, потому что на основе Set (uuid) в монаде писателя вы можете сказать, когда это произойдет.

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

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

---

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

Answer 4

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

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

Answer 5

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

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

Answer 6

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

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

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

Answer 7

Там нет общего решения, но:

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

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

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

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

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

Answer 8

Кеш сложен, потому что вам нужно учитывать: 1) кеш состоит из нескольких узлов, для них нужен консенсус 2) время аннулирования 3) состояние состязания, когда происходит множественное получение / установка

это хорошее чтение: https://www.confluent.io/blog/turning-the-database-inside-out-with-apache-samza/

Answer 9

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