Пишем свой In-Memory Cache на C#
Дмитрий Бахтенков
Введение
В прошлой статье мы рассматривали основные концепции кэширования и типы кэша. В этой статье мы попробуем написать свою реализацию In-Memory Cache на C#.
Кратко про кэш
В общем случае, кэш - это некоторый промежуточный буфер для быстрого доступа к часто используемым данным. Его цель - ускорить получение данных за счёт хранения копии часто используемых данных в некотором расположении, к которому можно получить доступ быстрее, чем к основному источнику данных.
In-Memory кэш - это механизм кэширования данных в оперативной памяти приложения. Это может быть полезно в самых разных случаях, например фильтрация данных. Допустим, у нас есть интернет-магазин, и пользователи часто фильтруют товары по категории. В таком случае, при первом запросе товаров с категорией “электроника” наше приложение пойдёт в БД, а после закэширует результат в памяти. При повторном запросе данных с той же категорией, приложение уже не будет долбиться в БД, а возьмёт данные из памяти, что будет в разы быстрее.
💡 Важно! Реализация кэша в статье является по большей части учебным примером - чтобы лучше понимать, как работают внутри существующие решения. Не пишите костыль без необходимости, используйте готовые решения!
Основные моменты в реализации In-Memory Cache
Структура данных для хранения данных
По своей сути, кэш - это некоторый словарь, где данные хранятся в формате “ключ-значение”. Поэтому использование структуры данных Dictionary<TKey, TValue> напрашивается само собой. Но словарь - это не потокобезопасная структура данных, поэтому при конкурентном доступе к данным могут быть проблемы. В таком случае, проще всего использовать ConcurrentDictionary<>. Про concurrent collections есть отличная статья на хабре и документация Microsoft.
Также для реализации политик вытеснения, например LRU (Last Recently Used) может использоваться связный список - LinkedList. С помощью него можно отобразить порядок элементов при добавлении, а также управлять расположением наиболее “свежих” элементов - при повторном доступе к ним перемещать их в начало списка.
Time to live (TTL) для элементов кэша
Элементы в кэше могут иметь ограниченное время жизни. Мы можем кэшировать данные на несколько секунд, чтобы через некоторое время эти данные автоматически обновлялись. Реализацию удаления элементов по времени можно реализовать множеством способов, например:
- С помощью сравнения TTL и текущего времени при получении данных
- С помощью фонового потока, который раз в некоторое время будет искать неактуальные данные и затирать их
- С помощью объектов таймера
В нашей реализации мы остановимся на первом варианте, так как он максимально простой и понятный.
Инвалидация кэша
Также необходимо давать пользователям нашего кэша возможность явно инвалидировать кэш - очищать данные. Для этого можно просто добавить метод, который очищает кэш по набору ключей, или вообще полностью.
Политики вытеснения данных
Нам нужно определить логику, которой будет следовать кэш при достижении максимального размера. Это называется политикой вытеснения данных, и существует два наиболее популярных варианта:
- Last Recently Used - заменяем те элементы, которые давно не использовались
- Least Frequently Used - заменяем те элементы, к которым было меньше всего обращений.
В общем, в первом случае смотрим на время, когда в последний раз было обращение к этому ключу, а во втором на количество обращений к элементам.
Реализация кэша
Для начала опишем один элемент кэша:
public class CacheItem
{
/// <summary>
/// Ключ элемента
/// </summary>
public string Key { get; set; }
/// <summary>
/// Значение элемента
/// </summary>
public object Value { get; set; }
/// <summary>
/// Время жизни элемента в секундах
/// </summary>
public int TTL { get; set; }
/// <summary>
/// Время последнего обращения к элементу
/// </summary>
public DateTime LastAccess { get; set; }
public CacheItem(string key, object value, int ttl)
{
Key = key;
Value = value;
TTL = ttl;
LastAccess = DateTime.UtcNow;
}
/// <summary>
/// Преобразовать значение в какой-то тип
/// </summary>
public T GetValue<T>()
{
return Value is T value ? value : throw new InvalidCastException();
}
}
Далее определим “контракт” для нашего кэша - интерфейс с описанием методов:
public interface ICustomMemoryCache
{
/// <summary>
/// Получить элемент из кэша или добавить новый
/// </summary>
/// <param name="key">Ключ для доступа к данным</param>
/// <param name="ttl">Время жизни данных при сохранении</param>
/// <param name="getter">Функция для получения данных</param>
/// <typeparam name="T">Тип объекта, который пытаемся получить</typeparam>
/// <returns></returns>
public Task<T> GetOrAdd<T>(string key, int ttl, Func<Task<T>> getter);
/// <summary>
/// Инвалидировать кэш
/// </summary>
/// <param name="keys">список ключей, по которым необходимо очистить данные. Если пустой, очищаем весь кэш</param>
public void Invalidate(params string[] keys);
}
Для простоты оставим всего лишь два метода - GetOrAdd для получения и сохранения данных и Invalidate для инвалидации.
Для начала напишем простую реализацию без политики вытеснения данных. Её можно описать на схеме:
А вот реализация:
public class CustomMemoryCache : ICustomMemoryCache
{
private readonly ConcurrentDictionary<string, CacheItem> _cache;
public CustomMemoryCache()
{
_cache = new ConcurrentDictionary<string, CacheItem>();
}
public async Task<T> GetOrAdd<T>(string key, int ttl, Func<Task<T>> getter)
{
// если элемент уже существует
if (_cache.TryGetValue(key, out var item))
{
// если время истекло
if (DateTime.UtcNow - item.LastAccess > TimeSpan.FromSeconds(item.TTL))
{
var data = await getter();
item = new CacheItem(key, data, ttl);
}
item.LastAccess = DateTime.UtcNow;
return item.GetValue<T>();
}
else
{
var data = await getter();
var newItem = new CacheItem(key, data, ttl);
_cache[key] = newItem;
return data;
}
}
public void Invalidate(params string[] keys)
{
if (!keys.Any())
{
_cache.Clear();
}
else
{
foreach (var key in keys)
{
_cache.Remove(key, out _);
}
}
}
}
Если кратко - мы добавляем элемент в кэш, если он не найден или время его жизни истекло. Иначе возвращаем данные из кэша.
Попробуем добавить политику вытеснения LRU. Будем действовать по следующему плану:
- Для простоты в качестве размера кэша будем использовать количество элементов в словаре, где хранятся наши данные
- Добавим поле _capacity в наш кэш, чтобы указывать предел размера кэша
- При добавлении или обновлении элемента будем проверять, не закончился ли у нас размер и удалять старые элементы из кэша.
Для хранения элементов кэша дополнительно будем использовать связный список, потому что он позволяет быстро перемещать элементы в начало или конец списка, а также быстро удалять элементы из списка. Это удобно для реализации политики LRU, которая удаляет из кэша те элементы, которые давно не использовалсь. Связный список также позволяет хранить элементы в порядке их использования, что упрощает поиск и обновление элементов в кэше.
Наша схема обновится следующим образом:
Ну и реализация. Для начала добавим новые свойства в CacheItem:
...
/// <summary>
/// Узел связного списка,
/// в котором находится элемент кэша
/// </summary>
public LinkedListNode<CacheItem>? Node { get; set; }
...
Добавим новые поля в CustomMemoryCache, отвечающие за размеры данных:
// словарь для хранения данных в кэше
private readonly ConcurrentDictionary<string, CacheItem> _cache;
// связный список элементов кэша для отображения элементов кэша
// в порядке их использования
private readonly LinkedList<CacheItem> _cacheItems;
// максимальный размер кэша
private readonly int _capacity;
public CustomMemoryCache(int capacity)
{
_capacity = capacity;
_cache = new ConcurrentDictionary<string, CacheItem>();
_cacheItems = new LinkedList<CacheItem>();
}
И обновим реализацию метода GetOrAdd:
public async Task<T> GetOrAdd<T>(string key, int ttl, Func<Task<T>> getter)
{
// если элемент в кэше есть
if (_cache.TryGetValue(key, out var item))
{
// если время истекло
if (DateTime.UtcNow - item.LastAccess > TimeSpan.FromSeconds(item.TTL))
{
var data = await getter();
// обновляем данные и TTL
item.Value = data;
item.TTL = ttl;
}
// проставляем текущую дату использования данных
item.LastAccess = DateTime.UtcNow;
// перемещаем элемент в начало списка, так как у него
// самое свежее время использования
MoveToHead(item);
// При необходимости очищаем кэш от старых элементов
// по политике LRU
ClearLastRecentlyUsed();
return item.GetValue<T>();
}
else
{
var data = await getter();
var newItem = new CacheItem(key, data, ttl);
// добавляем новую запись в кэш
_cache[key] = newItem;
// помещаем новый элемент в начало кэша
newItem.Node = _cacheItems.AddFirst(newItem);
// при необходимости очищаем кэш от старых данных
ClearLastRecentlyUsed();
return data;
}
}
Следует обратить внимание на тот факт, что у нас добавились новые приватные методы.
Очищение кэша по политике LRU:
private void ClearLastRecentlyUsed()
{
while (_cache.Count > _capacity)
{
// Удаляем последний элемент из связного списка и словаря
var oldestItem = _cacheItems.Last?.Value;
if (oldestItem is not null)
{
Delete(oldestItem.Key);
}
}
}
Перемещение элемента в начало списка:
private void MoveToHead(CacheItem item)
{
// Если элемент уже находится в начале списка, то ничего не делаем
if (item.Node == _cacheItems.First) return;
// Если элемент находится в середине или в конце списка, то удаляем его из списка
if (item.Node != null)
{
_cacheItems.Remove(item.Node);
}
// Добавляем элемент в начало списка и сохраняем ссылку на узел
item.Node = _cacheItems.AddFirst(item);
}
Удаление элемента по ключу:
private void Delete(string key)
{
if (_cache.TryRemove(key, out var item))
{
// Удаляем элемент из связного списка
if (item.Node is not null)
{
_cacheItems.Remove(item.Node);
}
}
}
А ещё немного поменялся метод инвалидации:
public void Invalidate(params string[] keys)
{
// если не указали ни одного ключа - очищаем весь кэш
var keysForDelete = keys.Any() ? keys : _cache.Keys;
foreach (var key in keysForDelete)
{
Delete(key);
}
}
В целом по реализации всё. Перейдём к тестированию.
Тестим
Я добавил тестовый проект xUnit и написал несколько тестов
public class CacheTests
{
[Fact]
public async Task GetOrAdd_ShouldReturnDataFromGetter_WhenKeyIsNotInCache()
{
// Arrange
var cache = new CustomMemoryCache(1000);
var key = "test";
var ttl = 10;
var data = 42;
// Act
var result = await cache.GetOrAdd(key, ttl, () => Task.FromResult(data));
// Assert
Assert.Equal(data, result);
}
[Fact]
public async Task GetOrAdd_ShouldReturnDataFromCache_WhenKeyIsInCacheAndNotExpired()
{
// Arrange
var cache = new CustomMemoryCache(1000);
var key = "test";
var ttl = 10;
var data = 42;
await cache.GetOrAdd(key, ttl, () => Task.FromResult(data)); // добавляем данные в кэш
// Act
var result =
await cache.GetOrAdd(key, ttl, () => Task.FromResult(data + 1)); // пытаемся получить данные из кэша
// Assert
Assert.Equal(data, result); // должны получить старые данные, а не новые
}
[Fact]
public async Task GetOrAdd_ShouldReturnDataFromGetter_WhenKeyIsInCacheAndExpired()
{
// Arrange
var cache = new CustomMemoryCache(1000);
var key = "test";
var ttl = 1; // устанавливаем очень маленькое время жизни данных
var data = 42;
await cache.GetOrAdd(key, ttl, () => Task.FromResult(data)); // добавляем данные в кэш
// Act
await Task.Delay(2000); // ждем больше, чем время жизни данных
var result =
await cache.GetOrAdd(key, ttl, () => Task.FromResult(data + 1)); // пытаемся получить данные из кэша
// Assert
Assert.Equal(data + 1, result); // должны получить новые данные, а не старые
}
[Fact]
public async Task GetOrAdd_ShouldRemoveLeastRecentlyUsedItem_WhenCacheIsFull()
{
// Arrange
var cache = new CustomMemoryCache(2);
var key1 = "test1";
var key2 = "test2";
var key3 = "test3";
var ttl = 10;
var data1 = 42;
var data2 = 43;
var data3 = 44;
await cache.GetOrAdd(key1, ttl, () => Task.FromResult(data1)); // добавляем первые данные в кэш
await cache.GetOrAdd(key2, ttl, () => Task.FromResult(data2)); // добавляем вторые данные в кэш
// Act
await cache.GetOrAdd(key3, ttl, () => Task.FromResult(data3)); // добавляем третьи данные в кэш
// Assert
Assert.False(cache.ContainsKey(key1)); // первые данные должны быть удалены из кэша как наименее используемые
Assert.True(cache.ContainsKey(key2)); // вторые данные должны остаться в кэше
Assert.True(cache.ContainsKey(key3)); // третьи данные должны остаться в кэше
}
}
И кстати, они прошли успешно
Заключение
Стоит ли использовать кастомный кэш в своих проектах?
Короткий ответ - скорее нет, чем да. Кастомный кэш можно оптимизировать непосредственно под конкретное приложение, добавить в него различные функции, логи и так далее. Это, несомненно, плюс. Однако этот код надо будет поддерживать, проверять и покрывать тестами, фиксить там баги - и это должно быть оправдано в рамках конкретного проекта.
Для реализации кэша в памяти есть множество библиотек, которые поддерживаются сообществом, в которых уже решены основные проблемы, и лучше использовать их.
Спасибо за внимание!
Весь код доступен на гитхабе.
С вами был Flex Code.