Первоисточник:jtrainingИсточник перевода:Lixiangобновить:Saber
введение
Мы все слышали о тайниках, и когда вы спросите их, что такое тайник, они дадут вам идеальный ответ, но они не знают, как строится тайник, или не скажут вам, какие критерии следует использовать для выбора тайника. кеширующий фреймворк. В этой статье мы обсудим кеширование, алгоритмы кеширования, фреймворки кеширования и какой фреймворк кеширования лучше.
интервью
«Кэш — это временное место для хранения данных (часто используемых данных), потому что стоимость извлечения исходных данных слишком высока, поэтому я могу получить их быстрее».
Это ответ первого программиста (программист один - собеседуемый) на собеседовании (месяц назад он отправил свое резюме в компанию и хотел претендовать на должность разработчика java с богатым опытом в области кэширования, фреймворка кэширования и больших - манипулирование данными масштаба).
Первый программист реализует свой собственный кеш через хэш-таблицу, но все, что он знает, это его кеш и его хэш-таблица, в которой хранится 150 записей, что он и думает о крупномасштабных данных (кэш = хеш-таблица, нужно только хранить в хеш-таблице Просто посмотрите), так что давайте посмотрим на процесс интервью.
Интервьюер: Какой стандарт вы выбрали для решения кэширования?
программист 1: Мм, (думает 5 минут) Ну, на основе, на основе, на основе данных (кашель...)
Интервьюер: Извините, вы можете повторить?
программист первый: данные? !
Интервьюер: Хорошо. Расскажите о нескольких алгоритмах кэширования и их роли
Программист 1: (смотрит на интервьюера с очень странным выражением лица, никто не знал, что люди могут делать такое выражение лица)
Интервьюер: Ну, позвольте мне сказать по-другому, что произойдет, когда кеш заполнится?
Программист один: Вместимость? Хм (думая о... нет ограничений на емкость хеш-таблицы, я могу добавлять элементы произвольно, и это автоматически расширит емкость) (это идея программиста, но он этого не сказал)
Интервьюер поблагодарил первого программиста (собеседование длилось 10 минут), после чего подошла дама и сказала: спасибо за уделенное время, мы вам перезвоним, желаем хорошего настроения. Это худшее собеседование для программиста (он не видит требований к кандидатам на работу с богатым кэшированным опытом, на самом деле он видит только хорошую оплату).
сделай как обещал
После того, как первый программист ушел, он захотел узнать вопросы и ответы, которые сказал интервьюер, поэтому он пошел в интернет, чтобы проверить, первый программист ничего не знал о кэшировании, кроме: когда мне нужно было кэширование, я использовал хэш-таблицу.
После поиска в своей любимой поисковой системе он нашел отличную статью о кэшировании и начал читать...
Зачем нам кэширование?
Давным-давно, когда не было кеша... Пользователи часто запрашивали объект, и этот объект выбирался из базы данных, а затем объект становился все больше и больше, и время запроса пользователя становилось все больше и больше. также усложняла базу данных, поскольку она становилась все длиннее, он все время работал. Итак, эта вещь очень злит пользователя и базу данных, и тогда могут произойти две вещи:
1. Пользователь раздражает, жалуется и даже не использует приложение (такое случается в большинстве случаев)
2. База запакована домой, выхожу из приложения, а дальше, большая беда (нет места для хранения данных) (встречается в редких случаях)
Бог послал кеш
Несколько лет спустя исследователи из IBM (в 1960-х годах) представили новую концепцию под названием «кэш».
Что такое кеш?
Как говорилось в начале, кеш — это «временное место для хранения данных (часто используемых данных), потому что стоимость извлечения исходных данных слишком высока, поэтому я могу получить их быстрее».
Кэш можно рассматривать как пул данных, которые копируются из реальных данных в базе данных и помечаются (идентификатор ключа) для правильного извлечения. чудесный
Первый программист уже знает это, но он еще не знает приведенный ниже термин кэша.
удар:
Когда клиент делает запрос (допустим, он хочет просмотреть информацию о продукте), наше приложение принимает запрос, и если это первая проверка кеша, ему нужно обратиться к базе данных, чтобы прочитать информацию о продукте.
Если в кеше найдена запись с тегом, эта запись используется, и мы называем это попаданием в кеш. Поэтому процент попаданий понять несложно.
Кэш мисс:
Но вот две вещи, на которые стоит обратить внимание:
1. Если в кэше еще есть место, объекты, которые не попали, будут сохранены в кэше.
2. Если кеш заполнен и кеш не попал, то по определенной стратегии старые объекты в кеше будут выкинуты, а новые объекты будут добавлены в пул кеша. Эти стратегии вместе называются стратегиями замещения (алгоритмами кэширования), и эти стратегии определяют, какие объекты должны быть представлены.
Стоимость хранения:
Когда хита нет, мы извлекаем данные из базы данных и помещаем их в кеш. Время и пространство, необходимые для помещения этих данных в кэш, являются стоимостью хранения.
Стоимость индекса:
и затраты на хранение аналогичны.
потерпеть неудачу:
Когда данные в кеше необходимо обновить, это означает, что данные в кеше недействительны.
Альтернативные стратегии:
Когда кеш пропускает попадание и емкость кеша заполнена, старая запись должна быть удалена из кеша и добавлена новая запись, а какая запись должна быть удалена, определяется стратегией замены.
Оптимальная альтернативная стратегия:
Оптимальная стратегия замены — выкинуть из кеша самую бесполезную запись, но будущее нельзя предсказать, поэтому эта стратегия невозможна. Но есть много стратегий, и все они работают на это настоящее.
Кошмар улицы Явы:
Пока первый программист читал это, он уснул и ему приснился кошмар (кошмары бывают у всех).
первый программист: нихахха, я тебя отключу! (безумное состояние)
Сохраненный объект: Не надо, оставь меня в живых, я им еще нужен, у меня дети.
программист первый: каждый объект кеша говорит это перед тем, как сделать его недействительным. Когда вы начали рожать детей? Не волнуйтесь, это ушло сейчас и навсегда!
Хахахахаха... программист номер один ужасно расхохотался, но тишину нарушила сирена, программиста номер один поймала полиция и обвинила его в убийстве (аннулировании) объекта кеша, который еще нужно было использовать, и его посадили в тюрьму.
Программист один проснулся внезапно, он был испуган и вспотел, он стал осматриваться и обнаружил, что это действительно был сон, а затем торопливо продолжил читать эту статью, пытаясь устранить свою панику.
После того, как программист один проснулся, он снова начал читать статьи.
алгоритм кэширования
Никто не может сказать, какой алгоритм кэширования лучше, чем другие
Наименее часто используемые (LFU):
Привет всем, я LFU, и я рассчитываю для каждого кэшированного объекта, как часто они используются. Я бы выбросил наименее часто используемые кешированные объекты.
Последний пользователь (LRU):
Я применяю алгоритм кэширования LRU, и я выбрасываю наименее использовавшиеся кешированные объекты.
Мне всегда нужно знать, какой объект кеша когда использовался. Это очень сложно, если кто-то хочет понять, почему я всегда выбрасываю наименее использовавшийся объект.
Браузер просто использует меня (LRU) в качестве алгоритма кэширования. Новые объекты будут размещены в верхней части кеша. Когда кеш достигает предела емкости, я удаляю нижние объекты, и хитрость заключается в том, что я помещаю недавно доступ к кэшированным объектам в верхнюю часть пула кешей.
Таким образом, кэшированные объекты, которые часто считываются, всегда остаются в кэш-пуле. Есть два способа получить меня: массив или связанный список.
Я быстрый, и я также могу адаптироваться к шаблону доступа к данным. У меня большая семья, и все они могут меня усовершенствовать, даже лучше меня (иногда я завидую, но это нормально). Некоторые члены моей семьи, в том числе LRU2 и 2Q, существуют для того, чтобы совершенствовать LRU.
Наименее использовавшиеся 2 (LRU2):
Я наименее недавно использовавшийся 2, и меня дважды назвали наименее недавно использовавшимся 2, что я предпочитаю. Я помещаю объекты, к которым обращаются дважды, в пул буферов, и когда пул буферов заполняется, я выбрасываю кэшированные объекты, которые реже всего используются дважды. Поскольку объект необходимо отслеживать дважды, нагрузка доступа будет увеличиваться по мере увеличения буферного пула. Если я буду использовать его в большом буферном пуле, возникнут проблемы. Кроме того, мне нужно отслеживать те объекты, которые больше не кэшируются, потому что они не были прочитаны во второй раз. Я лучше, чем LRU, и адаптирован к режиму доступа.
Две очереди (2Q):
Я Две очереди; я помещаю полученные данные в кэш LRU, и если к объекту снова обращаются, я перемещаю его во второй, больший кэш LRU.
Я удалил объекты кеша, чтобы размер первого пула кеша составлял 1/3 размера второго пула кеша. При фиксированной нагрузке доступа к кешу лучше заменить LRU на LRU2, чем увеличивать емкость кеша. Этот механизм делает меня лучше, чем LRU2, я также являюсь членом семьи LRU и адаптирован к режиму доступа.
Кэш адаптивной замены (ARC):
Я ARC, некоторые люди говорят, что я между LRU и LFU, для улучшения эффекта я составлен из 2 LRU, первый, который является L1, содержит записи, которые недавно использовались только один раз, а третий Два LRU, L2, содержат записи, которые в последний раз использовались дважды. Поэтому L1 ставит новые объекты, а L2 ставит часто используемые объекты. Поэтому окружающие будут думать, что я между ЛРУ и ЛФУ, но это неважно, я не против.
Считаюсь одним из самых эффективных алгоритмов кэширования, самонастройки и низкой нагрузки. Я также сохраняю объекты истории, чтобы помнить, какие из них были удалены, а также позволять мне видеть, можно ли оставить удаленные объекты и выкинуть их. У меня плохая память, но я быстр и адаптируюсь.
Наиболее недавно использовавшиеся (MRU):
Я MRU, что соответствует LRU. Я удалю самые последние использованные объекты, вы обязательно спросите меня, почему. Что ж, позвольте мне сказать вам, что некоторые вещи непредсказуемы, когда приходит визит, и поиск наименее использовавшегося объекта в системе кэширования - очень сложная операция по времени, поэтому я - лучший выбор.
Я как часто в базе данных memcache! Всякий раз, когда используется кешированная запись, я помещаю ее на вершину стека. Когда стек заполнен, угадайте, что? Я заменю объект в верхней части стека новым входящим объектом!
Первым пришел первым ушел (FIFO):
Я FIFO, я низконагруженный алгоритм, и я не очень требователен к управлению кэшированными объектами. Я использую очередь для отслеживания всех кэшированных объектов. Самые последние использованные кэшированные объекты помещаются в конец, а более ранние кэшированные объекты помещаются вперед. Когда емкость кэша заполнена, кэшированные объекты на переднем плане будут быть выкинутым, а затем помещенным. Добавлен новый объект кеша. Я быстро, но я не применяю.
Второй шанс:
Привет всем, я Second Chance.Я модифицировал его через FIFO.Это называется алгоритм кэширования второго шанса.Чем я лучше FIFO, так это тем, что я улучшил стоимость FIFO. Я - FIFO, и я также нахожусь в начале очереди наблюдения, но FIFO немедленно выбрасывается. Я проверю, есть ли у объекта, который собирается выгнать, флаг, который использовался ранее (представленный 1 бит), и он не был использован, я его выгоню, в противном случае я сниму флаг и добавлю объект кеша в очередь как новый объект кеша. Вы можете себе представить, что это похоже на кольцевую очередь. Когда я снова наткнулся на этот объект в начале очереди, я сразу же выкинул его, потому что у него больше не было этого маркера. я быстрее чем ФИФО работает быстро.
Часы:
Я часы, лучший FIFO и лучше, чем второй шанс. Потому что я не буду ставить помеченный объект кеша в конец очереди, как второй шанс, но он также может достичь эффекта второго шанса.
Я держу круговой список кешированных объектов, и указатель головы указывает на самый старый кешированный объект в списке. Когда происходит промах кеша и нет нового места в кеше, я буду запрашивать флаги кэшированного объекта, на который указывает указатель, чтобы решить, что мне делать. Если флаг равен 0, я буду напрямую заменять объект кеша новым объектом кеша; если флаг равен 1, я буду увеличивать указатель головы и повторять процесс до тех пор, пока новый объект кеша не будет вставлен. Я быстрее второго шанса.
Простой, основанный на времени:
Я простой алгоритм кэширования на основе времени, я аннулирую эти кэшированные объекты по абсолютному периоду времени. Для вновь добавленных объектов я сэкономлю определенное время. Я быстро, но я не применяю.
Расширенный срок действия на основе времени:
Я использую алгоритм кэширования с расширенным сроком действия на основе времени, я использую относительное время для аннулирования объектов кэша; для вновь добавленных объектов кэша я буду сохранять определенное время, например, каждые 5 минут в 12 часов каждый день.
Скользящее истечение по времени:
У меня скользящий срок действия, основанный на времени.Отличие от предыдущего заключается в том, что начальная точка жизни управляемого мной объекта кеша отсчитывается от времени последнего доступа к кешу. Я быстр, но и не очень применим.
Другие алгоритмы кэширования также учитывают следующее:
Стоимость: Если кешированные объекты имеют разную стоимость, вам следует сохранить эти труднодоступные объекты.
емкость: если кешированные объекты имеют разные размеры, более крупные кешированные объекты должны быть очищены, чтобы могло попасть больше мелких кешированных объектов.
время: Некоторые кэши также сохраняют время истечения срока действия кэша. Компьютеры отключат их, потому что срок их действия истек.
В зависимости от размера кэшируемого объекта могут потребоваться другие алгоритмы кэширования.
Эл. адрес!
Прочитав эту статью, один программист задумался над этим, а потом решил написать автору письмо, почувствовав, что имя автора уже слышали раньше, но не мог его вспомнить. Он все равно отправил электронное письмо и спросил автора, как кэширование работает в распределенной среде.
Автор статьи получил электронное письмо, по иронии судьбы именно этот автор брал интервью у первого программиста, и автор ответил...
В этой части мы рассмотрим, как реализовать эти известные алгоритмы кэширования. Следующий код является лишь примером. Если вы хотите реализовать алгоритм кэширования самостоятельно, вам, возможно, придется добавить дополнительную работу самостоятельно.
Механизм LeftOver
После того, как программист прочитал статью, он прочитал комментарии к статье, в одном из которых упоминался остаточный механизм - случайный кеш.
Random Cache
Я случайный кеш, я заменяю кешированные сущности по своему желанию, никто не смеет жаловаться. Можно сказать, что заменяемому объекту не повезло. С помощью этих действий я кэширую сущности везде, где хочу. Я лучше, чем механизм FIFO, а в некоторых случаях я даже лучше, чем LRU, но обычно LRU лучше меня.
Пришло время комментировать
Когда первый программист продолжил читать комментарии, он нашел комментарий очень интересным, в этом комментарии реализованы некоторые алгоритмы кэширования, следует сказать, что этот комментарий сделал ссылку на сайт комментатора, первый программист перешел по ссылке на этот сайт, а затем прочитал .
Взгляните на элементы кеша (сущности кеша)
public class CacheElement
{
private Object objectValue;
private Object objectKey;
private int index;
private int hitCount; // getters and setters
}Этот кэшированный объект имеет кэшированные ключ и значение, и структура данных этого объекта будет использоваться всеми следующими алгоритмами кэширования.
Общий код для алгоритмов кэширования
public final synchronized void addElement(Object key, Object value)
{
int index;
Object obj;
// get the entry from the table
obj = table.get(key);
// If we have the entry already in our table
// then get it and replace only its value.
obj = table.get(key);
if (obj != null)
{
CacheElement element;
element = (CacheElement) obj;
element.setObjectValue(value);
element.setObjectKey(key);
return;
}
｝Приведенный выше код будет использоваться всеми реализациями алгоритма кэширования. Этот код используется для проверки, находится ли закешированный элемент в кеше, и если да, то мы его заменяем, но что делать, если мы не можем найти кеш для этого ключа? Итак, давайте внимательно посмотрим, что происходит!
Посещение сайта
Сегодняшняя функция особенная, потому что у нас есть специальные гости, которые на самом деле являются посетителями, которых мы хотим услышать, но сначала давайте представим наших гостей: Random Cache, FIFO Cache. Начнем со случайного кэша.
Взгляните на реализацию случайного кеша
public final synchronized void addElement(Object key, Object value)
{
int index;
Object obj;
obj = table.get(key);
if (obj != null)
{
CacheElement element;// Just replace the value.
element = (CacheElement) obj;
element.setObjectValue(value);
element.setObjectKey(key);
return;
}// If we haven't filled the cache yet, put it at the end.
if (!isFull())
{
index = numEntries;
++numEntries;
}
else { // Otherwise, replace a random entry.
index = (int) (cache.length * random.nextFloat());
table.remove(cache[index].getObjectKey());
}
cache[index].setObjectValue(value);
cache[index].setObjectKey(key);
table.put(key, cache[index]);
}Взгляните на реализацию алгоритма буфера FIFO.
public final synchronized void addElement(Objectkey, Object value)
{
int index;
Object obj;
obj = table.get(key);
if (obj != null)
{
CacheElement element; // Just replace the value.
element = (CacheElement) obj;
element.setObjectValue(value);
element.setObjectKey(key);
return;
}
// If we haven't filled the cache yet, put it at the end.
if (!isFull())
{
index = numEntries;
++numEntries;
}
else { // Otherwise, replace the current pointer,
// entry with the new one.
index = current;
// in order to make Circular FIFO
if (++current >= cache.length)
current = 0;
table.remove(cache[index].getObjectKey());
}
cache[index].setObjectValue(value);
cache[index].setObjectKey(key);
table.put(key, cache[index]);
}Взгляните на реализацию алгоритма кэширования LFU.
public synchronized Object getElement(Object key)
{
Object obj;
obj = table.get(key);
if (obj != null)
{
CacheElement element = (CacheElement) obj;
element.setHitCount(element.getHitCount() + 1);
return element.getObjectValue();
}
return null;
}
public final synchronized void addElement(Object key, Object value)
{
Object obj;
obj = table.get(key);
if (obj != null)
{
CacheElement element; // Just replace the value.
element = (CacheElement) obj;
element.setObjectValue(value);
element.setObjectKey(key);
return;
}
if (!isFull())
{
index = numEntries;
++numEntries;
}
else
{
CacheElement element = removeLfuElement();
index = element.getIndex();
table.remove(element.getObjectKey());
}
cache[index].setObjectValue(value);
cache[index].setObjectKey(key);
cache[index].setIndex(index);
table.put(key, cache[index]);
}
public CacheElement removeLfuElement()
{
CacheElement[] elements = getElementsFromTable();
CacheElement leastElement = leastHit(elements);
return leastElement;
}
public static CacheElement leastHit(CacheElement[] elements)
{
CacheElement lowestElement = null;
for (int i = 0; i < elements.length; i++)
{
CacheElement element = elements[i];
if (lowestElement == null)
{
lowestElement = element;
}
else {
if (element.getHitCount() < lowestElement.getHitCount())
{
lowestElement = element;
}
}
}
return lowestElement;
}Самым важным кодом должен быть метод наименьший хит, который должен найти элемент с наименьшим hitCount, а затем удалить его, оставив место для вновь введенного элемента кеша.
Взгляните на реализацию алгоритма кэширования LRU.
private void moveToFront(int index)
{
int nextIndex, prevIndex;
if(head != index)
{
nextIndex = next[index];
prevIndex = prev[index];
// Only the head has a prev entry that is an invalid index
// so we don't check.
next[prevIndex] = nextIndex;
// Make sure index is valid. If it isn't, we're at the tail
// and don't set prev[next].
if(nextIndex >= 0)
prev[nextIndex] = prevIndex;
else
tail = prevIndex;
prev[index] = -1;
next[index] = head;
prev[head] = index;
head = index;
}
}
public final synchronized void addElement(Object key, Object value)
{
int index;Object obj;
obj = table.get(key);
if(obj != null)
{
CacheElement entry;
// Just replace the value, but move it to the front.
entry = (CacheElement)obj;
entry.setObjectValue(value);
entry.setObjectKey(key);
moveToFront(entry.getIndex());
return;
}
// If we haven't filled the cache yet, place in next available
// spot and move to front.
if(!isFull())
{
if(_numEntries > 0)
{
prev[_numEntries] = tail;
next[_numEntries] = -1;
moveToFront(numEntries);
}
++numEntries;
}
else { // We replace the tail of the list.
table.remove(cache[tail].getObjectKey());
moveToFront(tail);
}
cache[head].setObjectValue(value);
cache[head].setObjectKey(key);
table.put(key, cache[head]);
}Логика этого кода аналогична описанию алгоритма LRU: повторно используемый кэш извлекается на передний план, и каждый раз удаляется последний элемент.
В заключение
Мы видели, как реализован алгоритм кэширования LFU и алгоритм кэширования LRU.Что касается того, как это реализовать, использовать ли массив или LinkedHashMap решать вам.Если этого недостаточно, я обычно использую массив для небольшого кэша. емкость и LinkedHashMap для большой.
свяжитесь со мной
- Электронная почта: xmusaber@163.com
- QQ: 932191671
Эта статья является оригинальным выпуском моего личного публичного аккаунта «Menghui Juvenile», пожалуйста, отсканируйте и обратите внимание.