Как определить, какой набор данных лучше всего кэшировать?

Question

У меня есть простой веб-сервис, который обслуживает наборы данных XML (они могут быть размером до 250 МБ).Эти данные поступают из сложных запросов к базе данных.Чтобы ускорить обслуживание, я бы хотел кешировать результаты некоторых запросов.Однако у меня ограниченный объем оперативной памяти (~ 2 ГБ).Я не знаю заранее, каков наиболее запрашиваемый набор данных XML.Кроме того, со временем это может измениться (например, вчера набор данных X является наиболее часто запрашиваемым, завтра это может быть набор данных Y).

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

Answer 1

Один из вариантов: http://en.wikipedia.org/wiki/Exponential_smoothing времени между запросами или количества запросов в последовательных минутах.Если ваши документы действительно большие, у вас есть возможность хранить некоторую информацию в документе, когда он находится вне кэша, так что вы можете по крайней мере попробовать более широкий набор подходов, чем те, которые обычно используются для замены страниц в ВМ, такие как LRU,которые отслеживают запросы только для объектов в кэше.

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

Answer 2

Почему бы вам не прочитать некоторые статьи об общих структурах кэша?:

http://en.wikipedia.org/wiki/Cache

Я бы также рекомендовал прочитать статью, касающуюся кеш-памяти процессора:

http://en.wikipedia.org/wiki/CPU_cache

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

---

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

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

Answer 3

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

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