Популярные алгоритмы кэширования: LFU кэш
Привет, дорогой читатель!
Сегодняшний пост я бы хотел начать со стандартного вопроса на собеседовании: «Какими достижениями на работе ты особенно гордишься?» Этот вопрос может удивить или даже оскорбить, ведь сегодня оказывается недостаточно просто хорошо выполнять свои обязанности, этим надо обязательно гордиться. Но не дай интервьюеру тебя застать врасплох. Если помещение просторное, то в этот момент лучше даже встать со стула, твой моноспектакль должен зажигать огонь в глазах. Обернул на днях метод в try / catch? Не стесняйся — ты уже предостерёг компанию от исключительной ситуации! Месяц назад исправил очередной баг? Это было не просто исправление, это было спасение компании от потенциального банкротства! И тут главное не перестараться, ведь интервьюер скорее всего тоже часто посещает собеседования, и уже не раз «спасал компанию от банкротства». А лучше, конечно, заранее подготовиться к этому вопросу.
Но это стандартный вопрос. А мы вернёмся к нестандартному. В предыдущем посте мы уже познакомились с кэшированием и алгоритмом LRU вытеснения элементов. Предлагаю рассмотреть следующий пример:
var cache = new LruCache<string, int>(2);
for (int i = 0; i < 100; ++i)
{
cache.Add("x", 1);
}
cache.Add("y", 3);
cache.Add("z", 1);
if (cache.TryGet("x", out var x))
{
Console.WriteLine($"Element 'x' is equal {x}");
}
else
{
Console.WriteLine($"Element 'x' was not found");
}В консоли мы увидим "Element 'x' was not found". Таким образом, из кэша будет вытеснен элемент x, к которому было в 100 раз больше обращений, но LRU стратегия никак это не учитывает. Этот пример хоть и достаточно искусственный, но он хорошо иллюстрирует ограничения LRU стратегии. В этом посте рассмотрим новую стратегию, которая будет учитывать частоту обращений к элементам. Поехали!
LFU (least frequently used) — стратегия вытеснения элемента, который использовался реже всего. Под данным элементом понимается элемент, доступ к которому по ключу (методы добавления и получения значения) осуществлялся наименьшее количество раз. В случае, если таких элементов несколько, то вытесняется элемент, доступ к которому не осуществлялся дольше всего.
Полную реализацию LFU кэша на C#, как всегда, можно посмотреть на GitHub проекта coding-interview.
Ну а мы вернёмся к реализации. Начнём с самого простого варианта. Реализуем обёртку вокруг ассоциативного массива без стратегии вытеснения:
public class LfuCache<TKey, TValue>
{
public LfuCache()
{
_cache = new Dictionary<TKey, TValue>();
}
public void Add(TKey key, TValue value)
{
_cache[key] = value;
}
public bool TryGet(TKey key, [MaybeNullWhen(false)] out TValue value)
{
return _cache.TryGetValue(key, out value);
}
public bool Remove(TKey key)
{
return _cache.Remove(key);
}
public void Clear()
{
_cache.Clear();
}
private readonly Dictionary<TKey, TValue> _cache;
}Ограничим наш кэш максимально допустимым количеством элементов capacity. Создадим общий счётчик доступа к элементам totalAccessSteps, который будем увеличивать при каждом последующем доступе. Для каждого сохранённого элемента будем хранить время доступа к нему accessStepsByKey и количество обращений к данному элементу frequenciesByKey. Забегая вперёд отметим, что данная реализация не является оптимальной, в процессе она будет улучшена.
public class LfuCache<TKey, TValue>
{
public LfuCache(int capacity)
{
if (capacity <= 0)
{
var exMessage = $"must be a positive value";
throw new ArgumentOutOfRangeException(nameof(capacity), capacity, exMessage);
}
_capacity = capacity;
_cache = new Dictionary<TKey, TValue>();
_frequenciesByKey = new Dictionary<TKey, int>();
_accessStepsByKey = new Dictionary<TKey, int>();
_totalAccessSteps = 0;
}
// ...
private readonly Dictionary<TKey, TValue> _cache;
private readonly Dictionary<TKey, int> _frequenciesByKey;
private readonly Dictionary<TKey, int> _accessStepsByKey;
private readonly int _capacity;
private int _totalAccessSteps;
}Обновим очевидные операции удаления элемента и очистки кэша:
public bool Remove(TKey key)
{
_accessStepsByKey.Remove(key);
_frequenciesByKey.Remove(key);
return _cache.Remove(key);
}
public void Clear()
{
_cache.Clear();
_frequenciesByKey.Clear();
_accessStepsByKey.Clear();
_totalAccessSteps = 0;
}Рассмотрим операцию добавления элемента в кэш. В зависимости от ситуации могут возникнуть три следующих случая:
- Если данный элемент присутствует в кэше, то обновляем его значение, количество обращений и время доступа;
- Если кэш содержит меньше элементов, чем его вместимость, то просто сохраняем новый элемент;
- Если кэш содержит уже максимально допустимое количество элементов, то удаляем элемент, который использовался наименьшее количество раз. Если таких элементов несколько, то удаляем элемент, доступ к которому осуществлялся раньше всего. После чего добавляем новый элемент.
public void Add(TKey key, TValue value)
{
if (_cache.ContainsKey(key))
{
Update(key, value);
}
else if (_cache.Count < _capacity)
{
AddNew(key, value);
}
else
{
Evict();
AddNew(key, value);
}
++_totalAccessSteps;
}
private void AddNew(TKey key, TValue value)
{
_cache[key] = value;
_accessStepsByKey[key] = _totalAccessSteps;
_frequenciesByKey[key] = 1;
}
private void Update(TKey key, TValue value)
{
_cache[key] = value;
_accessStepsByKey[key] = _totalAccessSteps;
_frequenciesByKey[key] = _frequenciesByKey[key] + 1;
}
private void Evict()
{
var minFrequency = _frequenciesByKey.Values.Min();
var minFrequencyKeys = _frequenciesByKey
.Where((x) => x.Value == minFrequency)
.Select((x) => x.Key);
var lfuItemKey = minFrequencyKeys
.Aggregate((l, r) => _accessStepsByKey[l] < _accessStepsByKey[r] ? l : r);
Remove(lfuItemKey);
}Операция доступа к элементу по ключу также должна поменять время доступа и количество обращений к элементу, поэтому воспользуемся уже реализованным Update методом:
public bool TryGet(TKey key, [MaybeNullWhen(false)] out TValue value)
{
if (_cache.TryGetValue(key, out value))
{
Update(key, value);
return true;
}
value = default!;
return false;
}Как отмечалось выше, данная реализация не является оптимальной. Основная проблема находится в методе Evict, где мы полным перебором ищем элемент, который будет вытеснен из кэша. Займёмся оптимизацией!
Разобьём наши элементы на группы по частоте использования. В каждой группе упорядочим все наши элементы в виде списка в порядке добавления от более раннего к более позднему. По вертикали будем располагать частотные группы, а по горизонтали будем располагать элементы в каждой группе (квадраты обозначают частотные группы, а круги — элементы, где слева записан ключ, а справа — значение):
Посмотрим, как будет изменяться структура под воздействием различных операций. Операция очистки кэша очевидна. Поэтому рассмотрим оставшиеся операции (далее красным цветом будем показывать удаление вершины или группы, а синим — добавление):
- Операция удаления элемента из кэша. В данном случае мы удаляем элемент из частотной группы. Если элемент являлся последним в группе, то удаляем и данную частотную группу:
- Операция добавления нового элемента, если кэш содержит меньше элементов, чем максимально допустимое значение. В данном случае добавляется новый элемент в конце списка в группу элементов с частотой обращения равной единице:
- Операция добавления нового элемента, если кэш содержит максимально допустимое количество элементов. В данном случае удаляется элемент, который находится в списке первым в группе с самой низкой частотой обращений, так как время доступа к нему меньше, чем время доступа к любому другому элементу. После удаления мы получаем структуру, в которой количество элементов меньше, чем максимально допустимое. А значит верно то, что описано в пункте выше:
- Операция обновления существующего элемента. Новое значение элемента при этом может быть любым, так как оно не влияет на сортировку элементов. Заметим, что если элемент был последним в группе, то данная группа удаляется. При необходимости создаётся новая частотная группа:
- Операция получения значения по ключу. Данная операция эквивалентна операции обновления существующего элемента с сохранением его исходного значения.
Осталось научиться быстро находить элемент в списке по ключу. Для этого будем хранить для каждого ключа ссылку на нужный элемент. Для быстрого поиска частотной группы, также будем хранить для каждой частоты ссылку на соответствующую частотную группу.
internal class LfuItem<TKey, TValue>
{
public LfuItem(TKey key, TValue value, int frequency)
{
Key = key;
Value = value;
Frequency = frequency;
}
public TKey Key { get; }
public TValue Value { get; }
public int Frequency { get; }
}
internal class LfuFrequencyGroup<TKey, TValue>
{
public LfuFrequencyGroup(int frequency)
{
Frequency = frequency;
Items = new LinkedList<LfuItem<TKey, TValue>>();
}
public int Frequency { get; }
public LinkedList<LfuItem<TKey, TValue>> Items { get; }
}
public class LfuCache<TKey, TValue>
{
public LfuCache(int capacity)
{
if (capacity <= 0)
{
var exMessage = $"must be a positive value";
throw new ArgumentOutOfRangeException(nameof(capacity), capacity, exMessage);
}
_capacity = capacity;
_itemNodesByKey = new Dictionary<TKey, LinkedListNode<LfuItem<TKey, TValue>>>();
_frequencyGroupsByFrequency = new Dictionary<
int,
LinkedListNode<LfuFrequencyGroup<TKey, TValue>>
>();
_frequencyGroups = new LinkedList<LfuFrequencyGroup<TKey, TValue>>();
}
// ...
private readonly Dictionary<TKey, LinkedListNode<LfuItem<TKey, TValue>>> _itemNodesByKey;
private readonly Dictionary<
int,
LinkedListNode<LfuFrequencyGroup<TKey, TValue>>
> _frequencyGroupsByFrequency;
private readonly LinkedList<LfuFrequencyGroup<TKey, TValue>> _frequencyGroups;
private readonly int _capacity;
}Перепишем методы очистки и удаления элемента из кэша:
public bool Remove(TKey key)
{
if (_itemNodesByKey.TryGetValue(key, out var itemNode))
{
var frequencyGroupNode = _frequencyGroupsByFrequency[itemNode.Value.Frequency];
frequencyGroupNode.Value.Items.Remove(itemNode);
if (frequencyGroupNode.Value.Items.Count == 0)
{
_frequencyGroupsByFrequency.Remove(itemNode.Value.Frequency);
_frequencyGroups.Remove(frequencyGroupNode);
}
_itemNodesByKey.Remove(key);
return true;
}
return false;
}
public void Clear()
{
_itemNodesByKey.Clear();
_frequencyGroups.Clear();
_frequencyGroupsByFrequency.Clear();
}Методы добавления элемента (заметим, что реализация основного метода Add осталась прежней):
public void Add(TKey key, TValue value)
{
if (_itemNodesByKey.ContainsKey(key))
{
Update(key, value);
}
else if (_itemNodesByKey.Count < _capacity)
{
AddNew(key, value);
}
else
{
Evict();
AddNew(key, value);
}
}
private void AddNew(TKey key, TValue value)
{
var lfuItem = new LfuItem<TKey, TValue>(key, value, 1);
if (!_frequencyGroupsByFrequency.TryGetValue(1, out var frequencyGroupNode))
{
frequencyGroupNode = _frequencyGroups
.AddFirst(new LfuFrequencyGroup<TKey, TValue>(1));
_frequencyGroupsByFrequency.Add(1, frequencyGroupNode);
}
_itemNodesByKey[key] = frequencyGroupNode.Value.Items.AddLast(lfuItem);
}
private void Update(TKey key, TValue value)
{
var itemNode = _itemNodesByKey[key];
var frequency = itemNode.Value.Frequency;
var frequencyNode = _frequencyGroupsByFrequency[itemNode.Value.Frequency];
var nextFrequency = frequency + 1;
if (!_frequencyGroupsByFrequency.TryGetValue(
nextFrequency,
out var nextFrequencyNode
))
{
nextFrequencyNode = _frequencyGroups.AddAfter(
frequencyNode,
new LfuFrequencyGroup<TKey, TValue>(nextFrequency)
);
_frequencyGroupsByFrequency[nextFrequency] = nextFrequencyNode;
}
Remove(key);
var nextItemNode = nextFrequencyNode.Value.Items.AddLast(new LfuItem<TKey, TValue>(
key,
value,
nextFrequency
));
_itemNodesByKey[key] = nextItemNode;
}
private void Evict()
{
var lfuItemNode = _frequencyGroups.First.Value.Items.First;
Remove(lfuItemNode.Value.Key);
}И метод получения элемента (реализация метода TryGet практически не поменялась):
public bool TryGet(TKey key, [MaybeNullWhen(false)] out TValue value)
{
if (_itemNodesByKey.TryGetValue(key, out var itemNode))
{
value = itemNode.Value.Value;
Update(key, value);
return true;
}
value = default!;
return false;
}На этом реализация LFU кэширования закончена. Мне надо прощаться, а тебе, дорогой читатель, предлагаю ознакомиться с другими разборами задач, которые могут попадаться на технических собеседованиях. До скорых встреч!
