(no subject)

[stas]

Вопрос для программистов:

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

1. Когда что-то кладется в кеш, клиент говорит срок годности (возьми А и держи 5 минут)
2. Когда что-то берется из кеша, клиент говорит срок годности (дай мне А не старше 5 минут)

Есть ли какие-то причины предпочитать один из этих способов другому, и если да, то какие?

Comments

[stas]

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

Я что-то не понимаю

[zanuda.livejournal.com]

Во втором случае из кеша ничего убирать нельзя? Всегда модет прийти клиент и попросить A за последнии 100 лет? А в первом через 5 минут А можно убирать, да?

Re: Я что-то не понимаю

[stas]

Попросить он может, но получение не гарантируется - это кеш, а не база данных :)
Но в реальных задачах просить за 100 лет не будут - времена в обоих случаях будут сходные.
В первом можно убирать, но на самом деле не очень нужно - т.е. задачи, чтобы в кеше не было "старых" данных, нет - не будет, хорошо, будет - тоже не очень страшно.

[bugabuga.livejournal.com]

А почему нельзя 1 и 2? :) В смысле раскидывать их по мелким суб-кешам с датой тухлости, при приходе запроса А не старше 5 минут заглядывается в суб-кеш который 0-5 минут. Размер субкеша будет не больше чем всё одним куском, поиск будет не медленнее чем одним куском.
Очистка может состоять в выкидывании суб-кеша -5-0 в урну :)
Разумеется, надо думать как именно разбить на суб-кеши -- даже наверное построить график распределения объектов по времени протухания.

[stas]

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

[bugabuga.livejournal.com]

Ну зачем ими сильно управлять :) Скажем, если всё честным образом укладывается в 5-минутные слоты, то выбор одного из кешей превращается в простую операцию вычисления индекса.
В случае, если скорость реакции кеша действительно супер-важна, отсечение ненужных кеш-деревьев из леса ускоряет поиск.

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


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

[oxfv.livejournal.com]

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

[http://users.livejournal.com/__si__/]

а как во втором случае данные в кеше буду устаревать для самого кеша (не для клиента) ?

[stas]

Как ему (кешу) захочется - т.е. реально когда данные там лежат слишком долго и/или их сликом много, то производится очистка по LRU или FIFO.

[http://users.livejournal.com/__si__/]

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

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

вообще второй способ вполне можно скомбинировать с первым, т.е данные в кеш имеют с ttl который указывается при store, но клиент может при запросе указать "свежесть" данных.
таким образом для разных данных можно получить разные политики комбинируя разные параметры.

P.S тут http://www.hpl.hp.com/techreports/1999/HPL-1999-69.html про cache policy для squid, может что для себя найдете полезного.

[pierre-denis.livejournal.com]

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

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

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