Представим что у нас есть высоконагруженный сервис, в котором публикуется 1000 постов в минуту.

У каждой статьи по 5-10 тегов. Самих тегов тоже много, допустим миллион.

Теги выводятся под каждой статьёй, а также можно выбрать определённый тег и найти все статьи по нему.

Как нам обеспечить достаточное быстродействие такой системы?

1. Решение “в лоб”.

posts

  • id
  • name

post_tag

  • post_id
  • tag_id

tags

  • id
  • name

При таком подходе мы словим “состояние гонки” - Race condition. Добавляя несколько статей с одним и тем же новым тегом параллельно, будет добавлено несколько тегов с одинаковым именем. Для нас это проблема, так как мы хотим чтобы в таблице тегов все имена тегов были разные.

Рассмотрим как это произойдёт.

Почти одновременно были созданы два запроса к системе, один запрос на добавление статьи “A” с тегом “X”, другой на добавление статьи “B” с тегом “X”. Запросы выполняются двумя процессами параллельно.

  1. Запрос 1. Записываем статью “A” в БД.

  2. Запрос 1. Ищем тег “X”, убеждаемся что его нет, решаем его добавить.

  3. Запрос 2. Записываем статью “B” в БД.

  4. Запрос 2. Ищем тег “X”, убеждаемся что его (пока ещё) нет, решаем его добавить.

  5. Запрос 1. Добавляем тег “X” в таблицу тегов.

  6. Запрос 1. Добавляем связь тега “X” со статьёй “A” в таблицу связей.

  7. Запрос 2. Добавляем ещё один тег “X” в таблицу тегов.

  8. Запрос 2. Добавляем связь тега “X” со статьёй “B” в таблицу связей.

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

В чём проблема с дубликатами?

Дублирующиеся теги будут путаться под ногами, когда мы будем выводить список статей по тегам.

Представим, как это выглядит на сайте. Вот список популярных тегов, с количеством статей по тегу. В списке есть дубликат по тегу “Node.js”.

Популярные теги: React (3), Node.js (1), Node.js (1), CSS (11)

Мало того, что один и тот же тег “Node.js” выводится несколько раз, так ещё при клике по первому тегу будет одна статья, а по второму - другая. Пользователь точно не ждёт такого поведения. В лучшем случае мы приведём его в замешательство.

Придётся чистить таблицу тегов и как-то склеивать дубликаты в один тег, привязывая к нему обе статьи.

Если на тег завязаны дополнительные сущности, например статистика кликов по определённому тегу, то придётся объединять статистику. Если эта статистика ведётся в режиме Write Only, то это будет то ещё веселье.

В общем, лучше бы дубликатов вообще не возникало.

2. Решение с уникальным ключом.

Но постойте, можно ведь добавить уникальный ключ. Он защитит нас от попытки вставить один и тот же тег дважды.

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

Нам останется:

  1. Добавить уникальный ключ на поле имени тега.

  2. Отследить ошибку при вставке.

  3. Если произошла ошибка при вставке тега, найти в таблице нужный тег и использовать его ID в дальнейших действиях.

У этого решения есть свои минусы. Во-первых, код становится сложнее. Во-вторых, сама проверка уникальности потребует дополнительных временных расходов на обработку движком БД. Если тегов очень много и они вставляются часто то это может вылиться в тормоза системы.

3. Решение с блокировкой.

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

Тогда запрос 2 “узнает” что по этому тегу уже добавляется статья, и может подождать, прежде чем закончится обработка другим запросом.

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

4. Решение с денормализацией.

Если денормализовать эту структуру таблиц, то можно решить задачу без транзакций и блокировок.

Термин “денормализация” означает, что мы продублируем некоторую информацию в нашей БД. У нас этой информацией будет имя тега - оно будет храниться в двух таблицах сразу.

posts

  • id
  • name

post_tag

  • post_id
  • tag_id NULL
  • tag_name

tags

  • id
  • name

При добавлении статьи, записываем статью и добавляем все теги по статье в таблицу post_tag, вписывая ID статьи и имя тега. В поле post_tag.tag_id при этом вписываем NULL.

В фоне запускается задача, которая ищет записи таблицы “post_tag” со значением NULL в поле “tag_id”.

  1. Нашли запись “post_tag” где “tag_id” = NULL.

  2. Нашли запись в “tags” с таким же именем тега как в “post_tag”. Проставили значение “post_tag.tag_id” по ID найденного тега.

  3. Не нашли запись в “tags”, тогда добавили тег и также проставили значение “post_tag.tag_id” по ID добавленного тега.

Последовательно обрабатывая эти записи в единственном процессе, мы исключаем возможность того, что тег будет дважды добавлен в таблицу “tags”. Нам даже не потребуется уникальный индекс.

Это решение должно работать максимально быстро, так как:

  1. При сохранении статьи мы выполняем только вставку;

  2. Не читаем таблицу тегов;

  3. Не проверяем уникальность по индексу;

  4. Не используем блокировку.