На протяжении многих лет люди, занимающиеся информатикой и инженерией, очень усердно работали над оптимизацией разного характера. Учитывая, что мы живем в мире с ограниченными ресурсами, человечество всегда работало над способами оптимизации затрат и ускорения буквально всего.
Я бы сказал, что в разработке программного обеспечения наиболее популярным подходом к повышению производительности является кэширование. Хотя существуют различные приложения кэширования, в зависимости от области разработки программного обеспечения, идея кэширования довольно проста: хранить данные, которые часто необходимы/используются, в быстрой структуре/хранилище, чтобы их можно было очень быстро извлечь.
Фактически кэши должны быть быстрыми в двух измерениях:
- Обеспечение того, чтобы как можно больше запросов файлов шло именно на него (кэш-хит), а не по сети или в оперативную память (кэш-промах);
- Накладные расходы на его использование должны быть небольшими: проверка членства и принятие решения о замене файла должны быть максимально быстрыми.
В этой статье мы сосредоточимся на второй части: применении конкретного подхода к реализации наименее часто используемого кеша и повышении производительности его проверки принадлежности и алгоритмов вытеснения. Кроме того, мы также рассмотрим основы и рассмотрим, где такая схема кэширования может быть полезна.
Основы
LFU — это алгоритм кэширования, в котором наименее часто используемый элемент в кеше удаляется всякий раз, когда достигается предел емкости кеша. Это означает, что для каждого элемента в нашем кеше мы должны отслеживать, как часто он используется. Как только емкость кеша будет превышена, будет запущен алгоритм вытеснения, который должен выбрать и истечь (удалить) элементы из кеша.
Если вы когда-либо реализовывали кэш LFU, вы, вероятно, рассматривали возможность использования структуры данных с минимальной кучей, потому что она обрабатывает вставку, удаление и обновление в логарифмической временной сложности. В этой статье мы рассмотрим еще один подход к его реализации.
Но прежде чем мы перейдем к реализации, давайте посмотрим, в каких случаях LFU лучше альтернатив.
Где сияет LFU
Представьте кеш активов в CDN, где активы кэшируются на основе шаблонов использования. Таким образом, когда пользователи запрашивают некоторые изображения для веб-страницы, которую они запрашивают, этот CDN добавит их в свой кеш, чтобы другие пользователи могли получить их еще быстрее.
Например, одним из таких изображений (активов) является логотип сайта. Вы можете себе представить, сколько раз в день логотип Google запрашивается во всех их продуктах? Мне бы очень хотелось узнать это число, но сейчас мы, вероятно, можем согласиться с тем, что число ОГРОМНОЕ.
Такие кэши активов — идеальный вариант использования кэшей LFU. Алгоритм вытеснения кэша LFU никогда не будет вытеснять активы, к которым часто обращаются. На самом деле в таком кеше логотип Google будет закеширован практически навсегда. Напротив, если есть какие-либо изображения, которые будут доступны из-за новой целевой страницы нового продукта, которая находится на главной странице Reddit, Slashdot и Hackernews, как только ажиотаж пройдет, активы будут удалены быстрее, потому что доступ частота резко упадет, хотя за последние несколько дней к ним обращались много раз.
Как вы, возможно, уже заметили, такой подход к вытеснению кэша очень эффективен в тех случаях, когда шаблоны доступа к кэшированным объектам меняются нечасто. В то время как кэши LRU вытесняют активы, к которым в последнее время не было доступа, подход вытеснения LFU вытеснит активы, которые больше не нужны после того, как шумиха уляжется.
Реализация кэша LFU
Теперь давайте перейдем к сути. Как мы уже говорили ранее, вместо того, чтобы рассматривать мини-кучу как возможную структуру данных, которая будет поддерживать наш кеш LFU, мы собираемся рассмотреть лучший подход.
На самом деле, в 2010 году группа исследователей профессора Кетан Шах, Анирбан Митра и Дхрув Матани опубликовали статью под названием Алгоритм O(1) для реализации схемы вытеснения кэша LFU (вы можете проверить это здесь), в которой они объясняют реализацию кэша LFU, который имеет сложность выполнения O(1) для всех его операций, включая вставку, доступ и удаление (вытеснение).
Здесь я покажу вам, как мы можем реализовать этот кеш, и проведу вас через реализацию.
Структура(ы) данных
Нет, это не будет какое-то красно-черное дерево Франкенштейна. Фактически это два двусвязных списка и хеш-таблица. Да, это все.
Чтобы иметь возможность понять основы этой реализации LFU, давайте посмотрим на связанный список и хеш-таблицу как на графику. Прежде чем мы посмотрим на реальную графику, нам нужно понять, как будут использоваться хеш-таблица и связанные списки.
В хеш-таблице будут храниться все элементы с ключом, который обрабатывается с помощью алгоритма хеширования (для наших целей мы можем сделать его простым), а значением будет фактический элемент:
Связанные списки немного сложнее. Первым будет «список частот», в котором будут все частоты доступа. Каждый из узлов в этом списке будет иметь список элементов, который будет содержать все элементы, к которым обращались с соответствующей частотой. Кроме того, каждый из элементов в списке элементов будет иметь указатель на своего предка в списке частот:
Если мы посмотрим на наш графический пример выше, то заметим, что к элементам A, B, C и D обращались 1 раз. К элементам E и F обращались 4 раза и так далее. Синие линии — это указатели, которые каждый из элементов в списках элементов имеет на своего предка в списке частот.
Итак, что произойдет, если к элементу E будет получен доступ еще раз? Давайте пройдемся по шагам: 1. Получить элемент из хэш-таблицы легко (и хорошо масштабируется, O(1)) 2. Мы получим доступ к указателю элемента frequencyParent, по которому мы можем проверить, какая следующая частота в списке 3. Если присутствует новая частота (например, 8), мы поместим ее в качестве первого элемента списка элементов под частотным узлом 8. 4. Если новой частоты нет, мы создадим частотный узел 8 и добавим E в его список элементов.
Вот и все. Частота получения элемента и обновления элемента составляет O(1). Прежде чем мы перейдем к реализации алгоритма доступа, давайте сначала установим основные типы, которые нам понадобятся для работы.
Типы
Как мы уже говорили ранее, нам нужно смоделировать требуемые типы, которые будут основой нашего кеша.
Первым struct будет CacheItem. Это будет фактический элемент, который будет храниться в кеше:
type CacheItem struct {
key string // Key of entry
value interface{} // Value of item
frequencyParent *list.Element // Pointer to parent in cacheList
}Он содержит key, по которому мы можем найти его в хеш-таблице, value, который является фактическим кэшированным элементом, и frequencyParent указатель на указатель в списке частот.
Следующим struct является FrequencyItem, который представляет каждый из элементов в списке частот. Он содержит набор записей, который будет набором CacheItem указателей. Мы будем использовать map для его хранения, чтобы мы могли рассматривать его как набор, содержащий только уникальные элементы:
type FrequencyItem struct {
entries map[*CacheItem]byte // Set of entries
freq int // Access frequency
}Последний struct, который нам понадобится для бесперебойной работы кеша, — это сам Cache:
type Cache struct {
bykey map[string]*CacheItem // Hashmap containing *CacheItems for O(1) access
freqs *list.List // Linked list of frequencies
capacity int // Max number of items
size int // Current size of cache
}Cache будет содержать хэш-карту под названием bykey (название взято из документа, ссылка на который приведена выше), список частот под названием freqs, максимальную емкость кеша под названием capacity и size кеша, который представляет количество элементов, кэшированных в любой заданный момент времени. момент.
Новый, установить и получить
Давайте рассмотрим первые три функции, необходимые для работы нашего кеша. Первая — это небольшая функция-конструктор:
func New() *Cache {
cache := new(Cache)
cache.bykey = make(map[string]*CacheItem)
cache.freqs = list.New()
cache.size = 0
cache.capacity = 100
return &c
}Конструктор New создаст новую структуру Cache и установит для нее все значения по умолчанию. Если вам интересно, как работает list.New(): для списка частот мы будем использовать пакет Go container/list, который содержит аккуратную реализацию связанного списка. Вы можете проверить его документацию для более подробной информации.
Вторая функция, которая будет реализована на Cache, это функция Set:
func (cache *Cache) Set(key string, value interface{}) {
if item, ok := cache.bykey[key]; ok {
item.value = value
// Increment item access frequency here
} else {
item := new(CacheItem)
item.key = key
item.value = value
cache.bykey[key] = item
cache.size++
// Eviction, if needed
// Increment item access frequency
}
}Функция будет принимать ключ кэша и фактическое значение/элемент для кэширования в качестве аргументов. Затем он проверяет, кэширован ли элемент уже или нет. Если он кэширован, он просто обновит значение элемента. В противном случае он создаст новый CacheItem, который будет инкапсулировать фактическое значение, установит key, добавит элемент в хеш-таблицу bykey и увеличит size кэша.
Теперь в обеих логических ветвях я добавил некоторые комментарии к недостающим частям: 1. Cache должен знать, как увеличить частоту доступа для aCacheItem, но мы еще не реализовали это; 2. Cache должен знать, как удалить элемент на основе частоты доступа, если size достигает capacity.
Мы сохраним эти комментарии, пока не реализуем функции increment и evict.
Третья функция, которую получит Cache, это Get — обращение к элементу по ключу из хэш-таблицы и его возврат:
func (cache *Cache) Get(key string) interface{} {
if e, ok := cache.bykey[key]; ok {
// Increment acess frequency here
return e.value
}
return nil
}Здесь тоже нет никакой магии — мы проверяем, содержит ли хэш-таблица bykey значение с аргументом key, и возвращаем его, если оно есть. В противном случае мы возвращаем nil. Здесь, как и в Set, мы оставим комментарий-заполнитель, где мы должны добавить вызов функции увеличения частоты после ее реализации.
Обновление частоты доступа
Как мы уже видели, при каждом действии доступа к кешу мы должны обновлять частоту доступа к элементу, к которому осуществляется доступ.
Давайте посмотрим, какие шаги должна предпринять наша функция Increment. Во-первых, для того, чтобы срок действия элемента истек, нам нужно решить, является ли этот элемент уже частью хеш-таблицы и списка частот или нет. Если это так, нам нужно будет узнать его новое значение частоты и его следующую позицию частоты (узел) в списке частот.
Во-вторых, нам нужно будет выяснить, есть ли для новой частоты уже узел в списке частот или нет. Если он есть, нам нужно будет добавить элемент в его список entries и назначить ему новую частоту доступа (которая равна текущей частоте доступа + 1). Если такового нет, нам придется создать новый частотный узел в списке частот (и установить все его разумные значения по умолчанию), а затем добавить элемент в его список entries
В-третьих, как только мы обнаружим FrequencyParent, наша функция должна будет установить нового родителя в значение item, которое увеличивается, и добавить его в родительский список entries.
В качестве последнего шага функция increment удалит элемент из entries старого частотного узла (frequencyParent).
Вот код на Голанге:
func (cache *Cache) increment(item *CacheItem) {
currentFrequency := item.frequencyParent
var nextFrequencyAmount int
var nextFrequency *list.Element
if currentFrequency == nil {
nextFrequencyAmount = 1
nextFrequency = cache.freqs.Front()
} else {
nextFrequencyAmount = currentFrequency.Value.(*FrequencyItem).freq + 1
nextFrequency = currentFrequency.Next()
}
if nextFrequency == nil || nextFrequency.Value.(*FrequencyItem).freq != nextFrequencyAmount {
newFrequencyItem := new(FrequencyItem)
newFrequencyItem.freq = nextFrequencyAmount
newFrequencyItem.entries = make(map[*CacheItem]byte)
if currentFrequency == nil {
nextFrequency = cache.freqs.PushFront(newFrequencyItem)
} else {
nextFrequency = cache.freqs.InsertAfter(newFrequencyItem, currentFrequency)
}
}
item.frequencyParent = nextFrequency
nextFrequency.Value.(*FrequencyItem).entries[item] = 1
if currentFrequency != nil {
cache.remove(currentFrequency, item)
}
}Давайте вернемся к нашей исходной диаграмме частот и списков записей и пройдемся по увеличению элемента E.
Первые шаги, которые предпримет наша функция increment, — выделение указателя на узел 4 (frequencyParent) и его value (то есть 4). Поскольку узел 4 присутствует в списке, он найдет следующий узел в списке частот, которым в нашем случае является узел 7.
Как только он определит, что новая частота для узла E должна быть 5, а не 7, он добавит новый узел частоты в список между узлами 4 и 7:
Как только узел 5 будет добавлен в список, функция установит значения по умолчанию, необходимые для правильной работы узла. Затем он установит указатель E на новый frequencyParent (узел 5):
В качестве последнего шага он возьмет item, который имеет тип *CacheItem, и добавит его в список entries, удалив его из списка entries из предыдущего frequencyParent:
Давайте посмотрим, как удалить CacheItem из списка entries FrequencyItem.
Удаление записей
Как только мы узнаем узел в списке, из которого мы хотим его удалить, мы можем просто удалить элемент из списка entries, а также полностью удалить FrequencyItem из списка частот, если entries станет пустым:
func (cache *Cache) Remove(listItem *list.Element, item *CacheItem) {
frequencyItem := listItem.Value.(*FrequencyItem)
delete(frequencyItem.entries, item)
if len(frequencyItem.entries) == 0 {
cache.freqs.Remove(listItem)
}
}Выселение
Последней частью головоломки является вытеснение, или, другими словами, удаление наименее часто используемых элементов, когда кеш достигает максимальной емкости.
Мы должны знать, сколько предметов мы хотим выселить. Обычно наш кеш имеет нижнюю и верхнюю границу, поэтому, когда достигается верхняя граница, мы удаляем элементы до нижней границы. В нашем случае мы будем удалять произвольное количество элементов, которое функция Evict примет в качестве аргумента.
Функция начнет «ходить» по списку частот от начала до конца. Поскольку список частот находится в порядке возрастания, он начнет удалять entries с первого частотного узла и далее, пока не удалит столько элементов, сколько передано произвольное число.
Если частотный узел не содержит entries из-за исключения, функция Evict должна будет также удалить частотный узел из списка частот. Он сделает это, вызвав функцию Remove. Таким образом, после выселения не останется мусора.
Вот код того, что мы описали выше:
func (cache *Cache) Evict(count int) {
for i := 0; i < count; {
if item := cache.freqs.Front(); item != nil {
for entry, _ := range item.Value.(*FrequencyItem).entries {
if i < count {
delete(cache.bykey, entry.key)
cache.Remove(item, entry)
cache.size--
i++
}
}
}
}
}Назад к Установить и получить
В начале этой статьи мы реализовали функции Set и Get. Одна вещь, которой у нас тогда не было, — это функции Evict и increment, поэтому мы можем использовать их соответствующим образом. Добавим их вызов.
Увеличение частоты доступа
В функции Get, если мы находим элемент в хеш-таблице bykey, нам нужно увеличить его частоту доступа, прежде чем мы продолжим возвращать его value:
func (cache *Cache) Get(key string) interface{} {
if e, ok := cache.bykey[key]; ok {
cache.increment(e)
return e.value
}
return nil
}С этим изменением Cache будет увеличивать частоту этого конкретного элемента, прежде чем мы его вернем. Но мы что-то забываем? Кроме того, функция Set делает доступ к кэшированным элементам, когда она их действительно кэширует. Это означает, что когда элемент кэшируется, он будет немедленно добавлен в список частоты под узлом со значением 1:
func (cache *Cache) Set(key string, value interface{}) {
if item, ok := cache.bykey[key]; ok {
item.value = value
cache.increment(item)
} else {
item := new(CacheItem)
item.key = key
item.value = value
cache.bykey[key] = item
cache.size++
// Eviction, if needed
cache.increment(item)
}
}Выселение после добавления
Функция Set позволяет пользователям нашего LFU Cache кэшировать в нем больше элементов. Ключевым компонентом любого кэша является то, что он должен знать, как удалять элементы (освобождать место) при добавлении новых элементов в кэш. Для кэша LFU наименее часто используемые элементы должны быть удалены, когда кэш заполнен.
Давайте сначала добавим функцию, которая будет возвращать bool, если кеш достиг своей максимальной емкости:
func (cache *Cache) atCapacity() bool {
return cache.size >= cache.capacity
}Функция проста: проверяет, больше или равно текущее size из Cache, чем capacity.
Теперь давайте воспользуемся этим в функции Set. Как только у нас есть новый набор элементов в кеше, мы должны проверить, достиг ли кеш своей емкости, а затем удалить из него ряд элементов.
Для простоты мы будем удалять только 10 элементов каждый раз, когда мы достигаем максимальной емкости:
func (cache *Cache) Set(key string, value interface{}) {
if item, ok := cache.bykey[key]; ok {
item.value = value
cache.increment(item)
} else {
item := new(CacheItem)
item.key = key
item.value = value
cache.bykey[key] = item
cache.size++
if cache.atCapacity() {
cache.Evict(10)
}
cache.increment(item)
}
}С этим изменением, если в какой-то момент добавление элемента достигнет емкости кеша, кеш удалит наименее часто используемые элементы.
Если вы хотите увидеть весь код для этой статьи, вы можете проверить это суть.
LFU — интересная схема выселения, особенно по сравнению с LRU, на мой взгляд, в силу своей нетрадиционности. Хотя его применение ограничено, алгоритм и вспомогательные структуры данных, описанные в документе, используемом в этой статье, интересны благодаря возможности масштабирования подхода.
Если мы вернемся к бумаге, о которой мы упоминали в начале статьи, то увидим, что LFU хоть и не новость, но традиционно реализовывался с использованием min-heap, который имеет логарифмическое время на вставку, поиск и удаление. Интересно, что в этой статье авторы объясняют, что предлагаемый ими подход имеет временную сложность O(1) для каждой из операций (вставка, поиск и удаление), поскольку операции основаны на хеш-таблице. Кроме того, связанные списки не добавляют временной сложности, потому что мы не просматриваем списки в любой точке — мы просто добавляем или удаляем в них узел, если это необходимо (что является операцией O (1)).
В заключение
В этой статье мы рассмотрели основы кэшей LFU. Мы установили, какие показатели эффективности являются наиболее важными (отношение попаданий к промахам, членство и скорость исключения). Мы увидели, что, хотя это не самая широко используемая схема кэширования, в некоторых случаях она может быть очень эффективной.
Затем мы приступили к его реализации, используя подход, который достаточно хорошо масштабируется с точки зрения временной сложности. Мы увидели сложности реализации алгоритмов выселения и увеличения частоты. В конце мы еще немного изучили, как подход, который мы использовали для его реализации, масштабируется.
Первоначально опубликовано на ieftimov.com 27 февраля 2019 г.
