ОбзорДокументацияВойти
/
oop_nust_misis
/
tp_003_lecture_lru_cache-alexanderbondarev
Код
Запросы
1
Пакеты
0
Релизы
0
CI/CD
Аналитика
Безопасность

tp_003_lecture_lru_cache-alexanderbondarev

0

Описание

58 KiB
README
В избранном0
Форки0
2
2
0
.gitverse
6 месяцев назад
.gitignore
6 месяцев назад
README.md
6 месяцев назад
README.md

tp_003_lecture_lru_cache

Задание: Разработка потокобезопасного in-memory кеша

Одной из самых частых задач при оптимизации производительности является кеширование — снижение нагрузки на базу данных или внешние сервисы за счет хранения часто используемых данных в быстрой памяти

Это задание — спроектировать и реализовать один из ключевых архитектурных компонентов: потокобезопасный in-memory кеш с поддержкой TTL (Time-To-Live) и политикой вытеснения LRU (Least Recently Used), доступный по сети

Задача:
Написать библиотеку (в виде одного класса или модуля) и обернуть ее в простой REST API сервис. Язык на выбор: C++, Python, Rust

Техническое Задание (ТЗ)

1. Основной интерфейс библиотеки:

Библиотека должна предоставлять простой интерфейс для взаимодействия с кешем:

  • set(key, value, ttl_seconds): Добавляет или обновляет значение по ключу. ttl_seconds — необязательный параметр, время жизни записи в секундах
  • get(key): Возвращает значение по ключу или null/None/Optional-эквивалент, если ключ отсутствует или его время жизни истекло
  • delete(key): Удаляет значение по ключу.

2. Ключевые требования к кешу:

  • Потокобезопасность (Thread Safety): Кеш должен корректно работать в многопоточной среде. Все операции (set, get, delete) должны быть атомарными и не приводить к состоянию гонки (race condition)
  • Ограничение размера (Capacity Limit): Кеш должен иметь настраиваемую максимальную вместимость (например, 1000 элементов)
  • Политика вытеснения LRU (Least Recently Used): Когда кеш заполнен и в него добавляется новый элемент, самый "старый" (давно неиспользуемый) элемент должен быть удален. "Использование" элемента — это вызов get или set для него.
  • Время жизни (TTL): Записи должны автоматически считаться недействительными по истечении их времени жизни. Попытка получить (get) просроченную запись должна вести себя так, как будто записи нет (и, в идеале, удалять ее из кеша).

3. Сетевой интерфейс (REST API):

Чтобы приблизить задачу к реальным условиям, где кеш часто используется как отдельный сервис, необходимо обернуть вашу библиотеку в простой HTTP-сервер со следующими эндпоинтами:

  • GET /cache/<key>: Получить значение.
    • Успех: 200 OK с JSON-телом {"key": "...", "value": "..."}.
    • Неудача: 404 Not Found, если ключ отсутствует или истек.
  • POST /cache: Добавить/обновить значение.
    • Тело запроса: JSON {"key": "...", "value": "...", "ttl_seconds": ...} (ttl_seconds опционально).
    • Ответ: 201 Created с пустым телом.
  • DELETE /cache/<key>: Удалить значение.
    • Ответ: 204 No Content.

Рекомендуемые фреймворки:

Архитектура и алгоритм

Классическая и эффективная реализация LRU-кеша использует комбинацию двух структур данных:

  1. Хеш-таблица (HashMap/dict/unordered_map): Для хранения пар ключ -> узел_в_списке. Это обеспечивает мгновенный доступ к данным по ключу за O(1).
  2. Двусвязный список (Doubly Linked List): Для отслеживания порядка использования элементов. В начало списка мы будем помещать самые свежие (недавно использованные) элементы. В хвосте списка, соответственно, будут находиться самые старые кандидаты на вытеснение.

Схема работы:

Пример интерфейса на разных языках

C++

Python

Rust

Этапы выполнения

Предполагается выполнять в 2 этапа

Основы и TTL

  1. Создайте базовую структуру класса/модуля кеша
  2. Реализуйте хранение на основе хеш-таблицы без ограничения размера и LRU.
  3. Добавьте логику для поддержки TTL (например, хранить вместе со значением время истечения).
  4. Напишите простые однопоточные тесты, проверяющие set, get, delete и корректность работы TTL

LRU, потокобезопасность и API

  1. Интегрируйте двусвязный список для отслеживания порядка использования
  2. Реализуйте логику вытеснения LRU при превышении capacity
  3. Обеспечьте потокобезопасность всех публичных методов с помощью мьютексов (C++/Rust) или threading.Lock (Python)
  4. Напишите многопоточные тесты: несколько потоков одновременно читают и пишут в кеш
  5. Реализуйте REST API обертку над вашим кешем, покрыв все эндпоинты

Дополнительное Задание (для заинтересованных)

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

Проблема: В базовой реализации просроченные записи удаляются только при попытке их получить (get). Это неэффективно, так как "мертвые" записи продолжают занимать память до тех пор, пока к ним не обратятся

Задача: Создать фоновый поток (background thread), который будет периодически (например, раз в 10 секунд) проходиться по кешу и удалять все записи с истекшим TTL

Сложность: Необходимо обеспечить потокобезопасный доступ к внутренним структурам кеша не только из API-обработчиков, но и из фонового потока, избегая дедлоков и длительных блокировок, которые могут замедлить основные операции