DNSCache

Описание

DNSCache - это класс, реализующий кэш DNS, который позволяет эффективно хранить соответствия между именами доменов и их IP-адресами. Он поддерживает обновление записей и разрешение имен с учетом ограничений на максимальное количество записей в кэше. При превышении установленного лимита старые записи удаляются по принципу LRU (Least Recently Used).

Класс DNSCache обеспечивает корректную работу в многопоточном окружении. Методы update и resolve могут вызываться параллельно из разных нитей без риска возникновения состояния гонки или повреждения данных.

Сборка и запуск

Целевым бинарником являются тесты, для сборки и запуска необходимо:

1. Склонировать репозиторий:

   git clone https://github.com/ALanovaya/dns_interface

2. Установить и собрать Google Test:

   sudo apt-get update
   sudo apt-get install -y libgtest-dev
   cd /usr/src/gtest
   sudo cmake CMakeLists.txt
   sudo make
   sudo cp lib/*.a /usr/lib

3. Собрать проект:

   cd dns_interface
   cmake -B build -S .
   cmake --build build

   Проект компилируется с флагом санитайзера -fsanitize=thread

4. Запустить тесты:

   ./build/dns_cache_test

Детали реализации

Архитектура была немного переработана, в проекте существует класс DNSCacheBase, в котором содержится реализация update, resolve и getMaxSize методов, объект данного класса создать нельзя, у него есть два наследника DNSCache и DNSCacheTestable.

DNSCache был реализован с использованием паттерна проектирования Singleton, а именно Singleton Майерса, чтобы избежать гонки данных (со стандарта С++11 Singleton Майерса гарантируется быть потокобезопасным), экземпляр данного класса создается единожды при первом вызове DNSCache::get_instance(num), и живет с max_size = num, переопределить max_size нельзя (так было сделано с оглядкой на поведение реальных DNS-кэшей, чей размер ограничен и заранее определен).

Класс DNSCacheTestable имеет публичный конструктор, объекты данного класса можно создавать в любом количестве с любыми параметрами max_size.

Так было сделано из-за того, что мне хотелось протестировать работу методов при различном значение max_size, и как бы отделить тесты самих методов и тесты правильности реализации паттерна (то, что он правда потокобезопасен в моей реализации).

Сами тесты можно разделить на две логические части: проверяющие работу в случае последовательного выполнения и в случае многопоточного приложение, когда update и resolve вызываются из разных нитей параллельно.

Сложность операций

Решение использует хеш-таблицу (std::unordered_map) для хранения записей кэша и двусвязный список (std::list) для отслеживания порядка использования записей (Least Recently Used, LRU). Рассмотрим сложность операций:

1. Вставка новой записи (update):

   В худшем случае, когда кэш заполнен, необходимо удалить наименее используемую запись. Это требует:

   • Поиск записи в хеш-таблице: $O(1)$ в среднем
   • Удаление записи из списка (если кэш полон): $O(1)$
   • Добавление в начало списка: $O(1)$
   • Добавление в хэш-таблицу: $O(1)$

   Таким образом, общая сложность вставки записей составляет $O(1)$ в среднем.

2. Обновление существующей записи (update):

   • Поиск записи в хеш-таблице: $O(1)$ в среднем
   • Обновление записи в хэш-таблице: $O(1)$
   • Удаление записи из списка: $O(1)$
   • Добавление обновленной записи в начало списка: $O(1)$

   Общая сложность обновления существующих записей также составляет $O(1)$ в среднем.

3. Поиск записей (resolve):

   • Поиск записи в хеш-таблице: $O(1)$ в среднем
   • Удаление записи из списка: $O(1)$
   • Добавление записи в начало списка: $O(1)$

   Таким образом, общая сложность поиска записей составляет $O(1)$ в среднем.

Контакты

Александра Лановая (Telegram): @winxpopp