Как спроектировать хранилище данных для системы многораздельных тегов?

Question

Как спроектировать хранилище данных для огромной системы тегов (например, Digg или Delicious)?

Уже обсуждается об этом, но речь идет о централизованной базе данных. Поскольку предполагается, что данные будут расти, рано или поздно нам потребуется разделить данные на несколько сегментов. Итак, возникает вопрос: Как спроектировать хранилище данных для системы многораздельных тегов?

Система тегирования в основном имеет 3 таблицы:

Item (item_id, item_content)

Tag (tag_id, tag_title)

TagMapping(map_id, tag_id, item_id)

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

Для таблицы Item мы можем разделить ее содержимое с помощью ключа item_id . Для таблицы Tag мы можем разбить ее содержимое по ключу tag_id . Например, мы хотим разбить таблицу Tag на K базы данных. Мы можем просто выбрать номер (tag_id% K) базу данных для хранения данного тега.

Но как разбить таблицу TagMapping ?

Таблица TagMapping представляет отношение «многие ко многим». Я могу только изображение, чтобы иметь дублирование. То есть одно и то же содержимое TagMappping имеет две копии. Один разделен с tag_id , а другой разделен с item_id . В сценарии для поиска тегов для данного элемента мы используем раздел с tag_id . Если сценарий для поиска элементов по данному тегу, мы используем раздел с item_id .

В результате возникает избыточность данных. И уровень приложения должен поддерживать согласованность всех таблиц. Это выглядит тяжело.

Есть ли лучшее решение для решения этой проблемы с разделами «многие ко многим»?

Answer 1

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

Поиск тегов для данного элемента

A1. Вы собираетесь одновременно отобразить всех тегов для данного элемента

A2. Вы убедитесь, что все тегов предмета уникальны

Поиск элементов по заданному тегу

B1. Вам понадобится несколько элементов для данного тега за раз (чтобы заполнить страницу результатов поиска)

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

B3. Вы собираетесь отсортировать элементы по заданному тегу (или тегам) по некоторому показателю популярности

Учитывая вышесказанное, я думаю, что хорошим подходом было бы разбиение TagMapping по элементам. Таким образом, все теги для данного элемента находятся в одном разделе. Разбиение может быть более детальным, поскольку, вероятно, элементов гораздо больше, чем тегов, и у каждого элемента есть только несколько тегов. Это делает поиск простым (A1) и уникальность может быть обеспечена в пределах одного раздела (A2). Кроме того, этот единственный раздел может сообщить вам, соответствует ли элемент нескольким тегам (B2).

Поскольку вам нужно только несколько элементов для данного тега (или тегов) за один раз (B1), вы можете запрашивать разделы по одному в некотором порядке, пока у вас не будет столько записей, сколько нужно заполнить страницу результатов. Сколько разделов вы будете запрашивать, будет зависеть от того, сколько разделов у вас есть, сколько результатов вы хотите отобразить и как часто используется тег. Каждый раздел будет иметь собственный индекс tag_id для эффективного ответа на этот запрос.

Порядок, в котором вы выбираете разделы, будет иметь важное значение, поскольку он будет влиять на группировку результатов поиска. Если порядок не важен (то есть B3 не имеет значения), выбирайте разделы случайным образом, чтобы ни один из ваших разделов не был слишком горячим. Если порядок важен, вы можете создать идентификатор элемента так, чтобы он кодировал информацию, относящуюся к порядку, в котором должны быть отсортированы результаты. Тогда соответствующая схема разбиения будет помнить об этой кодировке. Например, если результаты представляют собой URL-адреса, отсортированные по популярности, то вы можете объединить идентификатор последовательного элемента с оценкой рейтинга страницы Google для этого URL-адреса (или чего-либо подобного). Схема разделения должна гарантировать, что все элементы в данном разделе имеют одинаковую оценку. Запросы выбирают разделы в порядке очков, чтобы вначале возвращались более популярные элементы (B3). Очевидно, что это допускает только один вид сортировки, а используемые свойства должны быть постоянными, поскольку теперь они являются частью ключа и определяют раздел записи. Однако это не является новым ограничением, так как в любом случае нелегко поддерживать различные сортировки или сортировки по изменчивым свойствам с секционированными данными.

Answer 2

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

Вы говорите о распределении БД, обычно это в основном проблема синхронизации . Чтение, которое обычно составляет около 90% работы, может быть выполнено в реплицированной базе данных. Вопрос заключается в том, как обновить одну БД и сохранить согласованность всех остальных без потери производительности. Это зависит от деталей вашего сценария.

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

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

PS: не забывайте о кешировании, оно сэкономит вам больше, чем распределенная БД.

Answer 3

Правило состоит в том, что вы разбиваете по полям, по которым вы будете запрашивать. В противном случае вам придется просматривать все разделы. Вы уверены, что вам нужно будет запросить таблицу тегов только по tag_id? Я полагаю, нет, вам также нужно сделать запрос по названию тега. Для таблицы Item это не так очевидно, но, возможно, вы также захотите запросить что-то вроде URL, чтобы найти для него item_id, когда другой пользователь назначит для него теги.

Но обратите внимание, что таблицы Tag и Item имеют неизменный заголовок и URL. Это означает, что вы можете использовать следующую технику:

1. Выберите раздел из заголовка (для тега) или URL (для элемента).
2. Выберите последовательность для этого раздела, чтобы создать идентификатор.

В качестве глобального идентификатора вы используете пару partition-localID или наборы непересекающихся чисел. В любом случае, теперь вы можете вычислять разделы из полей id и title / URL. Не знаете заранее количество разделов или беспокоитесь, что это может измениться в будущем? Создайте их и объедините в группы, чтобы в будущем их можно было перегруппировать.

Конечно, вы не можете сделать то же самое для таблицы TagMapping, поэтому вам нужно продублировать. Вам нужно сделать запрос по map_id, tag_id, item_id, верно? Таким образом, даже без разделения вы должны дублировать данные, создав 3 индекса. Таким образом, разница в том, что вы используете разные разделы (по разным полям) для каждого индекса. Я не вижу причин для беспокойства.