Инвалидация кэша — есть ли общее решение?

Question

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

Фил Карлтон

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

Например, рассмотрим функцию 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

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

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

Answer 4

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

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

FRP более подробно объясняется в этом Доклад «Суть FRP» и в этом ТАК ответ.

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

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

---

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

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

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

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

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

---

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

Answer 5

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

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

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 лекцию о нем: Cache Oblivious Алгоритмы