Наиболее эффективный алгоритм замены кэша [закрыто]

12

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

Если я правильно помню из моего курса ОС, LRU - лучший общий алгоритм замены кэша. Но, возможно, я ошибаюсь.

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

ashes999
источник
1
Соответствует ли предварительная выборка вашему приложению? Если это так, то при выборе алгоритмов необходимо предварительно выбирать и сохранять стратегию.
rwong
Вам нужно будет получить примеры трассировок (список шаблонов доступа к данным), которые представляют предполагаемый домен приложения. Вы можете найти общедоступные тестовые наборы из научных исследований. Затем вы можете реализовать каждый алгоритм, провести симуляцию и сообщить о своих результатах. В противном случае используйте LRU с умеренно случайной заменой.
Rwong
1
Если вы «почти ничего не знаете о приложении», тогда еще рано думать об «эффективных» алгоритмах замены кэша.
Anon,
Основная память может быть дешевой, но если производительность является важной проблемой, эффективность доступа будет иметь значение. Я не думаю, что вы выберете стратегию замены кэша - если вы не главный архитектор нового компьютера. Остальные из нас получают все, что предлагает рынок. Если вам нужно идти быстро, вам нужно организовать свои вычисления и структуры данных, чтобы эффективно использовать иерархию памяти.
Омега Центавра
1
@ Omega Centauri Вы думаете только о кешах процессора, но это намного больше. Операционная система кэширует используемые файлы и каталоги, базы данных кэшируют свои данные, почти каждое приложение выполняет много операций кэширования (например, уже вычисленных результатов).
Maaartinus

Ответы:

15

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

Факторы, чтобы рассмотреть

  1. Чтение / запись баланса. (Какой процент обращений - чтение против записи)
  2. Объем кеша.
  3. Тип носителя за кешем. (Это медленные диски SATA или быстрые SSD?)
  4. Хиты против Мисс. (Как часто вещи переписываются или перечитываются?)
  5. Средний размер доступа (это касается выбора размера страницы)
  6. Насколько дорого читает и пишет.

После того, как вы рассмотрите все различные факторы, вам нужно найти алгоритм кеширования, который лучше всего справится с этим. Например, скажем, что у вас есть приложение, в котором много записей, некоторые перезаписи, чтения недавно записанных данных и что-то вроде вращающегося носителя. В этом случае вам нужен гибридный алгоритм кэширования. Для обработки данных записи вам может понадобиться что-то вроде Wise order of Writes (WOW) и алгоритм LRU для данных, считанных с диска. Причина этого заключается в том, что доступ к диску очень дорогой, а алгоритм WOW сделает его более эффективным для записи данных, а LRU будет хранить часто используемые данные всегда в кеше.

Допустим, у вас есть SSD-диски, которые имеют очень короткое время доступа, возможно, вы захотите переключиться на алгоритм LRU, поскольку доступ к дискам относительно недорог.

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

Как найти алгоритм для вас

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

В прошлом я добавил код для отслеживания всех обращений к памяти за определенный период времени. Потом я поищу шаблоны. Я ищу перечитывания, перезаписи, последовательный доступ, произвольный доступ и т. Д.

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

barrem23
источник
Большой разбивка факторов. Но я не уверен, как их применять, учитывая, что я знаю домен приложения и факторы.
ashes999
@ashes: есть старая инженерная техника: создайте несколько разных способов и определите, какая работает лучше всего.
Donal Fellows
Когда я слышу «кеш», я думаю о хранении между памятью и регистрами процессора. Здесь вы говорите о дисковом кэше, который является слоем между памятью и одним или несколькими устройствами ввода-вывода.
Омега Центавра
@ barrem23 Если вы занимаетесь распределенным программированием, необходимо учитывать и «расстояние между кешем и внутренним хранилищем». Не имеет большого значения, если у вас есть твердотельный накопитель или вращающаяся ржавчина в качестве большого, стабильного хранилища, если хранилище находится в 15 мс, вы все равно всегда будете испытывать минимум 30 мс в оба конца.
Ватин
9

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

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

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

  • С другой стороны, LRU не имеет смысла в контексте, где пользователь будет получать доступ к некоторым элементам гораздо чаще, чем к другим. Пример: я часто слушаю музыку, которая мне нравится, и может случиться, что на 400 песнях я буду слушать одни и те же пять, по крайней мере, один раз в неделю, в то время как я буду слушать не чаще одного раза в год 100 песен, которые мне тоже не нравятся много. В этом случае LFU гораздо более уместен.

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

Арсений Мурзенко
источник
Итак, как мне выбрать алгоритм? Просмотрите список Википедии и посмотрите, что подходит лучше всего?
ashes999
@ ashes999: точно! Сначала вы узнаете больше о требованиях приложения, затем проанализируете плюсы и минусы различных алгоритмов кэширования и, наконец, выберете более подходящий.
Арсений Мурзенко
3

Зачем ограничивать свой выбор только википедией? Если у вас есть доступ к исследовательской базе данных, такой как цифровая библиотека ACM, вы найдете еще больше алгоритмов. Также следует помнить о том, чтобы возиться с патентами. Например, ARC - хороший алгоритм, но, к сожалению, он запатентован.

sakisk
источник
2

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

Преждевременная оптимизация ...

Росс
источник
0

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

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

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


источник