Продолжаем посты на тему технических интервью. Новый пост, который мы позаимствовали у автора Дилана Смита, будет для джунов по специальностям «Системный аналитик», «Backend‑разработчик» и «Fullstack‑разработчик». Иногда такой вопрос также попадается на интервью архитекторам и инженерам баз данных. Ответ на вопрос из заголовка может быть как очень коротким, где всего четыре пункта, так и развернутым — включая примеры кода и диаграммы. Естественно, мы рассмотрим тему во всех подробностях.
***

Как только на каком-либо проекте создается новое приложение, предполагающее регистрацию пользователей, задача проверки уникальности имен становится актуальной. На техническом собеседовании проверка уникальности имени пользователя может быть рассмотрена как задача на оптимизацию, масштабирование или архитектуру ПО, в зависимости от специализации, на которую претендует кандидат. 

1. Проверка в базе данных

Наиболее прямолинейный способ — проверка наличия имени пользователя непосредственно в базе данных. При регистрации выполняется SQL-запрос, который проверяет, существует ли уже запись с таким именем. Если запись найдена, пользователю предлагается выбрать другое имя. Этот метод прост в реализации, но может оказаться не оптимальным выбором при большом количестве пользователей, так как частые обращения к базе данных увеличивают нагрузку на нее и время отклика.

Если обсудить недостатки этого метода, то они таковы:

1. Возможны проблемы с производительностью при относительно высокой задержке. Если число пользователей огромно, скорость выполнения запросов будет низкой с тенденцией к дальнейшим задержкам по мере роста количества пользователей. Кроме того, запросы к базе данных предполагают сетевое взаимодействие между сервером, на котором запущено приложение и сервером базы данных. Время, необходимое для установления соединения, отправки запросов и получения ответов, также является причиной задержки.

2. Частое выполнение запросов SELECT для проверки уникальности имен пользователей, и каждый запрос потребляет ресурсы базы данных, включая ресурсы процессора и ввода-вывода. Иными словами, нагрузка на базу данных м.б. чрезмерна.

3. Низкая масштабируемость, т.к. базы данных имеют ограничения на количество одновременных подключений.

Как пример, можно привести простой SQL-запрос для проверки наличия имени пользователя в таблице users, где столбец username хранит имена пользователей:

SELECT username 
FROM users 
WHERE username = 'новое_имя_пользователя';

Запрос фильтрует строки таблицы users, проверяя, существует ли имя пользователя, которое передано в качестве параметра. Если запрос возвращает строку, это означает, что указанное имя уже существует в таблице. Пользователю нужно будет выбрать другое имя. 

Если использовать SQL в сочетании с программным кодом, например, на Python, это можно оформить так:

import sqlite3
# Подключение к базе данных
conn = sqlite3.connect('your_database.db')
cursor = conn.cursor()

# Имя пользователя для проверки
username = 'новое_имя_пользователя'

# Проверка на уникальность имени пользователя
query = "SELECT username FROM users WHERE username = ?"
cursor.execute(query, (username,))
result = cursor.fetchone()

if result:
    print("Имя пользователя уже занято. Пожалуйста, выберите другое.")
else:
    print("Имя пользователя доступно.")

# Закрытие соединения с базой данных
conn.close()

Такой код помогает более эффективно обрабатывать данные пользователя и предотвращать дублирование записей в таблице users.

Однако, метод SQL-запроса для проверки наличия имени пользователя желательно использовать для относительно небольших систем. Если количество регистраций насчитывает сотни тысяч и продолжает расти, серверу базы данных может быть тяжело справиться с растущим числом входящих запросов. При этом, добавление дополнительных аппаратных ресурсов на сервер БД или в серверный кластер является дорогостоящей опцией. 

2. Использование кэширующих систем

Первый абзац — короткий ответ на вопрос из заголовка статьи: «Для повышения производительности при поиске совпадений username можно использовать кэширующие системы, такие как Redis. При регистрации имя пользователя сначала проверяется в кэше. Если оно занято, возвращается соответствующее сообщение. Если нет, выполняется проверка в базе данных, и в случае отсутствия записи имя добавляется в кэш. Этот подход снижает нагрузку на базу данных и ускоряет процесс проверки».

А если интервью предполагает более глубокую проверку знаний кандидата, то могут попросить прокомментировать пример кода на Java, в модуле проверки уникальности имен пользователей при регистрации. Код быстро проверяет наличие имени пользователя с использованием Redis, что позволяет сократить задержки и уменьшить нагрузку на основную базу данных.

import org.redisson.Redisson; 
import org.redisson.api.RedissonClient; 
import org.redisson.config.Config; 
import org.redisson.api.RMap; 

public class UserExistenceChecker { 

   // Redis hash map name to store user information 
   private static final String USER_HASH_NAME = "users"; 

   public static void main(String[] args) { 
       // Create a Redisson client 
       RedissonClient redisson = createRedissonClient(); 

       // Retrieve the hash map to store user information 
       RMap<String, String> users = redisson.getMap(USER_HASH_NAME); 

       // Add a user to the hash map 
       users.put("user123", "someUserInfo"); // Here "someUserInfo" could be a JSON string, UUID, etc. 

       // Check if a user exists 
       boolean exists = users.containsKey("user123"); 
       System.out.println("User 'user123' exists? " + exists); 

       // Check for a non-existent user 
       exists = users.containsKey("user456"); 
       System.out.println("User 'user456' exists? " + exists); 

       // Shutdown the Redisson client 
       redisson.shutdown(); 
   } 

   // Helper method to create a Redisson client 
   private static RedissonClient createRedissonClient() { 
       Config config = new Config(); 
       config.useSingleServer() 
               .setAddress("redis://127.0.0.1:6379") // Adjust to your Redis address 
               .setPassword("yourpassword"); // Provide your Redis password if any 

       return Redisson.create(config); 
   } 
}

Прокомментируем этот пример кода, как если бы вы это делали на интервью:

1. Подключение к Redis с использованием Redisson:

   • Код использует библиотеку Redisson для взаимодействия с Redis-сервером.

   • Метод createRedissonClient создаёт конфигурацию для подключения к Redis, указывая адрес сервера (127.0.0.1:6379) и пароль (если установлен).

2. Использование Redis-хэш:

   • Переменная USER_HASH_NAME указывает имя Redis-хэша (users), который используется для хранения данных о пользователях.

   • Хэш в Redis позволяет хранить пары ключ-значение, что делает его удобным для хранения информации о пользователях,
     например, username -> данные пользователя.

3. Добавление пользователя в Redis:

   • Код добавляет информацию о пользователе user123 с некоторыми данными (someUserInfo) в Redis-хэш.

4. Проверка наличия пользователя:

   • С помощью метода containsKey проверяется, существует ли пользователь user123 в Redis.

   • Также производится проверка для пользователя user456, который не был добавлен, чтобы показать отсутствие записи.

5. Вывод результата:

Программа выводит в консоль результаты проверки уникальности пользователя:
User 'user123' exists? true  
User 'user456' exists? false  

6. Завершение работы:

   • После завершения всех операций клиент Redisson корректно завершает работу, чтобы освободить ресурсы, вызвав метод shutdown.

Некоторая проблема при использовании кэширования, которая тем не менее решается по мере удешевления электронных компонентов — это потребление памяти на кэширующем сервере. Предположим, каждое имя пользователя требует примерно 16 байт памяти. Если потребуется хранить один миллиард имен пользователей, то потребуется порядка 16 ГБ чистой памяти (+ накладные расходы памяти), что в целом не сказать, что будет чрезмерно дорогое удовольствие.

Обычные облачные системы в РФ в лучшем случае насчитывают миллионы пользователей, так что кэширование имен пользователей — м.б. вполне себе рабочим решением.

3. Применение фильтра Блума

Фильтр Блума — это вероятностная структура данных, позволяющая быстро проверять принадлежность элемента множеству с минимальными затратами памяти. Она использует битовый массив для краткого представления множества и может определять принадлежность элемента к этому множеству. 

При регистрации имя пользователя проверяется с помощью фильтра Блума. Если фильтр указывает, что имя занято, выполняется дополнительная проверка в базе данных для подтверждения, так как фильтр может давать ложные срабатывания. Если имя свободно, оно добавляется в фильтр и базу данных. Этот метод особенно полезен при работе с очень большими наборами данных, так как позволяет быстро отсеивать большинство проверок.

Итак, основная идея фильтра Блума заключается в использовании битового массива (bit array) и набора хэш-функций. Попробуем проиллюстрировать это (рисунки заимствованы у автора):

В битовом массиве каждый бит изначально равен 0.

При вставке значения x используются k хэш-функций (3 таких на рисунке ниже) для хэширования значения x соответственно. Далее берется остаток от хэш-значения и емкости (длины битового массива) фильтра Блума, и значение соответствующего бита, представленного результатом, устанавливается в 1.

Процесс поиска совпадений username аналогичен процессу вставки. Для хэширования искомого значения используется k хэш-функций. Только когда значение каждого бита, полученного в результате хэширования, равно 1, это указывает на то, что значение "возможно" действительно существует; и наоборот, если значение любого бита равно 0, это указывает на то, что значение не должно существовать. Например, y1 не должно существовать, а y2 может существовать.

Redis поддерживает структуру данных фильтра Блума. Это можно проиллюстрировать вот таким кодом (описание действий. которые выполняет код, будет сразу ниже):

import org.redisson.Redisson;
import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.redisson.config.Config;

public class UserExistenceChecker {

   // Name of the Bloom Filter in Redis
   private static final String BLOOM_FILTER_NAME = "user_existence_filter";

   public static void main(String[] args) {
       // Create a Redisson client
       RedissonClient redisson = createRedissonClient();

       // Retrieve or create a Bloom Filter instance
       // Expected number of elements and false positive probability are parameters
       RBloomFilter<String> bloomFilter = redisson.getBloomFilter(BLOOM_FILTER_NAME);
       bloomFilter.tryInit(100000L, 0.001); // Initialize the Bloom Filter with expected elements and false positive rate

       // Add a user to the Bloom Filter
       bloomFilter.add("user123");

       // Check if a user exists
       boolean exists = bloomFilter.contains("user123"); // Should return true
       System.out.println("User 'user123' exists? " + exists);

       // Check for a non-existent user (might falsely report as true due to Bloom Filter's nature)
       exists = bloomFilter.contains("user456"); // Assuming not added, should ideally return false, but could be a false positive
       System.out.println("User 'user456' exists? " + exists);

       // Shutdown the Redisson client
       redisson.shutdown();
   }

   // Helper method to create a Redisson client
   private static RedissonClient createRedissonClient() {
       Config config = new Config();
       config.useSingleServer()
               .setAddress("redis://127.0.0.1:6379"); // Adjust to your Redis address
//                .setPassword("yourpassword"); // Provide your Redis password if any

       return Redisson.create(config);
   }
}

В этом примере кода реализуется фильтр Блума с помощью библиотеки Redisson для проверки существования имени пользователя.  

1. Подключение к Redis:

   • RedissonClient создаётся для подключения к серверу Redis. Адрес сервера (redis://127.0.0.1:6379) указан в конфигурации.

   • Этот клиент используется для взаимодействия с фильтром Блума, который сохраняется в Redis.

2. Создание и инициализация фильтра Блума:

   • RBloomFilter<String> bloomFilter = redisson.getBloomFilter(BLOOM_FILTER_NAME);
     Проверяется наличие или создаётся экземпляр фильтра Блума с именем user_existence_filter в Redis.

   • bloomFilter.tryInit(100000L, 0.001);
     Инициализирует фильтр с ожидаемым количеством элементов (100,000) и заданной вероятностью ложных срабатываний (0.001, или 0.1%).

3. Добавление пользователя в фильтр:

   • bloomFilter.add("user123");
     Имя пользователя user123 добавляется в фильтр.

4. Проверка существования пользователя:

   • bloomFilter.contains("user123");
     Проверяет, содержится ли имя пользователя user123 в фильтре. Поскольку пользователь был добавлен, результат будет true.

   • bloomFilter.contains("user456");
     Проверяет, существует ли имя пользователя user456.

     • Если имя пользователя не добавлено, фильтр вероятно вернет false.

     • Однако фильтр Блума может с небольшой вероятностью вернуть ложноположительный результат из-за своей природы.

5. Завершение работы:

   • Метод redisson.shutdown(); завершает работу клиента, закрывая соединение с Redis.

Преимущества фильтра Блума:

• Экономия места в памяти, т.к. по сравнению с использованием хэш-таблиц, фильтр Блума обычно требует меньше места в памяти, поскольку в нем хранятся не реальные элементы, а только их хэш-значения. Для хранения того же самого 1 миллиарда записей с вероятностью ошибки 0,001 требуется всего 1,67 Гб памяти. По сравнению с упомянутыми выше 16+ Гб при методе кэширования имеем значительную экономию памяти.

• Быстрый поиск за счет того, что фильтр Блума может почти моментально определить, существует ли элемент в наборе, за постоянное время (O(1)), не обходя весь набор.

Недостатки метода проверки username с фильтром Блума:

1. Частота ложных срабатываний — хотя фильтр Блума быстро определяет, существует ли искомый элемент, возможен определенный процент ложных срабатываний. 

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

Резюме: эффективность фильтра Блума достигается ценой ошибок — при определении принадлежности элемента к определенному набору можно ошибочно посчитать элемент, не принадлежащий к набору (т.н. ложное срабатывание).

Фильтр Блума не подходит для сценариев проверки username, где есть жесткие требования «нулевых ошибок». Однако в сценариях масс-маркет применений, допускающих низкий процент ошибок, фильтр Блума позволяет добиться значительной экономии памяти сервера за счет допущения малого количества ошибок.

4. Комбинированный подход

На практике, для ускорения поиска username может использоваться комбинация вышеуказанных методов 1-2-3. Например, сначала проверка выполняется с помощью фильтра Блума, затем в кэше, и только после этого в базе данных. Это позволяет достичь баланса между скоростью проверки и точностью результатов.

ВАЖНО: Если фильтр Блума утверждает, что данный username отсутствует, можно быть уверенным, что он действительно отсутствует. Если фильтр говорит, что элемент есть, потребуется дополнительная проверка (например, SQL-запрос) для уточнения.

Заключение

Обеспечение уникальности имен пользователей — ключевой аспект при разработке системы регистрации. Выбор подходящего метода проверки зависит от специфики проекта, объема данных и требований к производительности системы. Разработчикам и аналитикам приходится учитывать следующие факторы при выборе метода проверки username:

• Масштаб системы — для небольших систем достаточно проверки в базе данных. Для крупных систем с миллионами пользователей рекомендуется использовать кэширующие системы и фильтры Блума для повышения производительности.

• Требования к точности — если допустимы редкие ложные срабатывания, можно использовать фильтр Блума. В противном случае следует комбинировать его с другими методами для повышения точности.

• Оценка ресурсов системы: использование кэша и фильтра Блума требует дополнительной памяти, процессоров, быстрых сетевых карт и адаптеров ввода/вывода, поэтому необходимо учитывать доступные аппаратные ресурсы при выборе подхода.

Капля HR-рекламы от нашего блога: мы будем рады видеть в рядах компании SSP SOFT специалистов, готовых работать оффлайн в Москве и Томске, а также удаленно из любой точки России. Текущие вакансии на нашей странице на hh.ru. Если вашей специальности нет в списке вакансий, не стесняйтесь прислать нам резюме — в SSP SOFT новые позиции открываются регулярно. Резюме можно направить в Telegram или на почту job@ssp-soft.com.

Успехов на техинтервью и при работе с БД на ваших проектах!