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

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

Фил Карлтон

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

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

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

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

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

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

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

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

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

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

 private map> cache // private func realFunction // (a,b) -> c get(a, b) { c result; map endCache; if (cache[b] expired or not present) { remove all b -> * entries in cache; endCache = new map(); 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, должна измениться на

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

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

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

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

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

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

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

FRP объясняется более подробно в этой речи «Суть FRP» и в этом SO-ответе .

В разговоре Cell s представляет собой кешированный объект / объект, а Cell обновляется, если обновляется одна из ее зависимостей.

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


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

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

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

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

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


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

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

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

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

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

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

Общее решение отсутствует, но:

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

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

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

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

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

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

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

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

Давайте будем гением компьютера.