алгоритм замены записи в кэш

Question

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

Теперь я хочу кешировать хеш-значения, чтобы повысить производительность последующих сравнений. Для любой записи в кэше у меня есть следующие метрики:

• Количество хитов
• дата / время последнего изменения
• размер объекта хешируется

Итак, к моему вопросу. Учитывая необходимость ограничить размер кэша (ограничить его определенным количеством записей), каков сбалансированный подход к замене элементов кэша?

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

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

Все мысли, комментарии приветствуются.

Answer 1

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

Answer 2

Предполагая возможность записи, когда к записи последний раз обращались, я бы выбрал «Стоимость» для каждой записи, где вы в любой момент удалите наименее дорогую запись.

Cost = Size * N - TimeSinceLastUse * M 

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

Answer 3

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

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

Answer 4

Вам нужно подумать о природе предметов.Подумайте о вероятности повторного вызова объектов в ближайшее время.И удалите наименее вероятный объект.

Это очень специфично для используемого вами программного обеспечения и природы объектов.
Если они используются в программе постоянно, они, вероятно, будут соответствовать * 1004.* Местность ссылки принцип.Поэтому вам следует использовать алгоритм LRU (наименьшее из недавно использованных).

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

Возьмитепосмотрите на Алгоритмы кеширования

В принципе вам нужно вычислить:

мин (p * стоимость)

p = вероятность повторного вызова.
cost = Стоимость повторного кэширования этого объекта.

Answer 5

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