Профильное задание

Асимптотика методов

• set(key, value, ttl): O(1) среднее, O(n) худший случай
• get(key): O(1) среднее, O(n) худший случай
• remove(key): O(1) среднее, O(n) худший случай
• getManySorted(prefix, count): O(m + k) где m - длина префикса, k - количество результатов
• removeExpiredEntry(): O(log n) для получения истекших записей

Оверхед на запись

• Entry структура: 40 байт (std::string + uint32_t)
• Trie узел: 64 байт на символ ключа
• TTL запись: 24 байт (time_point + iterator)
• Общий оверхед: 128 байт на запись

Я сделал getManySorted через дерево бора (для эффективного поиска записей с определенным префиксом) и DFS (для вывода данных записей в лексиографическом порядке ключей).

Я использую storage_mutex_ для защиты основного хранилища, trie_mutex_ для защиты дерева бора, и cleanup_mutex_ для фоновой очистки истекших записей. Mutex блокировки в данном случае эффективны, поскольку по ТЗ 95% нагрузки – чтение.

Асинхронность реализована в фоновом потоке чистки TTL.