Поиск по осколкам?

Краткая версия

Если я разделю своих пользователей на сегменты, как мне предложить «поиск пользователей»? Очевидно, я не хочу, чтобы каждый поиск попадал в каждый осколок.

Длинная версия

Под осколком я имею в виду наличие нескольких баз данных, каждая из которых содержит часть общих данных. Для (наивного) примера базы данных UserA, UserB и т. д. могут содержать пользователей, чьи имена начинаются с «A», «B» и т. д. Когда новый пользователь регистрируется, я просто проверяю его имя и помещаю его в правильную база данных. Когда вернувшийся пользователь входит в систему, я снова смотрю на его имя, чтобы определить правильную базу данных, из которой нужно извлечь его информацию.

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

Между тем, шарды не заботятся о записи друг друга. Если Брайан зарегистрируется в сегменте UserB, сегменту UserA не нужно об этом знать. Если Брайан отправит сообщение Алексу, я смогу записать этот факт как на осколках UserA, так и на UserB. Таким образом, когда Алекс или Брайан входят в систему, они могут получить все свои отправленные и полученные сообщения из своего собственного сегмента, не запрашивая все сегменты.

Все идет нормально. Что с поисками? В этом примере, если Брайан ищет «Алекс», я могу проверить UserA. Но что, если он будет искать Алекса по его фамилии «Смит»? В каждом осколке есть кузнецы. Отсюда я вижу два варианта:

  1. Пусть приложение ищет кузнецов на каждом осколке. Это можно сделать медленно (последовательный запрос каждого сегмента) или быстро (параллельный запрос каждого сегмента), но в любом случае каждый сегмент должен быть задействован в каждом поиске. Точно так же, как репликация чтения не масштабирует запись, поиск, попадающий в каждый сегмент, не масштабирует ваши поиски. Вы можете достичь момента, когда ваш объем поиска будет достаточно высок, чтобы перегрузить каждый сегмент, и добавление сегментов вам не поможет, поскольку все они получают одинаковый объем.
  2. Какая-то индексация, которая сама по себе терпима к шардингу. Например, допустим, у меня есть постоянное количество полей, по которым я хочу искать: имя и фамилия. В дополнение к UserA, UserB и т. д. у меня также есть IndexA, IndexB и т. д. Когда регистрируется новый пользователь, я прикрепляю его к каждому индексу, по которому я хочу, чтобы его можно было найти. Поэтому я поместил Алекса Смита и в IndexA, и в IndexS, и его можно найти либо в «Алексе», либо в «Смите», но не в подстроках. Таким образом, вам не нужно запрашивать каждый сегмент, поэтому поиск можно масштабировать.

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


person Community    schedule 04.11.2008    source источник


Ответы (5)


Волшебной пули не существует.

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

Итак, вы хотите искать параллельно, если вам нужно.

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

Ключевой вывод, который вы можете использовать, заключается в том, что при поиске вам редко нужен полный набор результатов. Вам нужна только первая (или n-я) страница результатов. Таким образом, есть довольно много места для маневра, которое вы можете использовать для уменьшения времени отклика.

Индексирование

Если вы знаете атрибуты, по которым будет производиться поиск пользователей, вы можете создать для них настраиваемые отдельные индексы. Вы можете создать свой собственный инвертированный индекс, который будет указывать на кортеж (shard, recordId) для каждого поисковый запрос, или вы можете сохранить его в базе данных. Обновляйте его лениво и асинхронно. Я не знаю ваших требований к приложению, может быть даже можно просто перестраивать индекс каждую ночь (это означает, что у вас не будет самых последних записей в любой день, но это может быть для вас нормально). Обязательно оптимизируйте этот индекс по размеру, чтобы он мог поместиться в памяти; обратите внимание, что вы можете сегментировать этот индекс, если вам нужно.

Естественно, если люди могут искать что-то вроде "lastname='Smith' OR lastname='Jones'", вы можете прочитать индекс для Смита, прочитать индекс для Джонса и вычислить объединение — вам не нужно хранить все возможные запросы, а только их составные части.

Параллельный поиск

Для каждого запроса отправляйте запросы на каждый сегмент, если вы не знаете, какой сегмент искать, потому что поиск выполняется по ключу распределения. Сделайте запросы асинхронными. Ответьте пользователю, как только вы получите первые результаты на странице; собрать остальные и кэшировать локально, чтобы, если пользователь нажмет «Далее», у вас были готовы результаты, и вам не нужно повторно запрашивать серверы. Таким образом, если некоторые из серверов занимают больше времени, чем другие, вам не нужно ждать, пока они обслужат запрос.

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

person SquareCog    schedule 06.11.2008

Я предполагаю, что вы говорите об осколках а-ля: http://highscalability.com/unorthodox-approach-database-design-coming-shard

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

person Zak    schedule 04.11.2008
comment
Спасибо. Я действительно много читал этот сайт. Я попытался уточнить свой вопрос выше; который, надеюсь, выходит за рамки статьи, которую вы любезно связали. - person ; 04.11.2008

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

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

person user33830    schedule 04.11.2008
comment
Пожалуйста, смотрите мое пояснение выше. - person ; 04.11.2008

Вы можете взглянуть на Sphinx (http://www.sphinxsearch.com/articles.html). Он поддерживает распределенный поиск. GigaSpaces поддерживает параллельные запросы и слияния. Это также можно сделать с помощью прокси-сервера MySQL (http://jan.kneschke.de/2008/6/2/mysql-proxy-merging-resultsets).

Чтобы построить нешардированные индексированные виды поражений, цель шарда в первую очередь :-) Централизованный индекс, вероятно, не будет работать, если шарды были необходимы.

Я думаю, все осколки нужно бить параллельно. Результаты необходимо отфильтровать, ранжировать, отсортировать, сгруппировать и объединить результаты всех осколков. Если сами осколки перегружены, вам нужно будет выполнить обычное действие (перераспределить, увеличить масштаб и т. д.), чтобы снова их не перегрузить.

person Todd Hoff    schedule 06.11.2008

RDBM не являются хорошим инструментом для текстового поиска. Вам будет гораздо лучше взглянуть на Solr. Разница в производительности между Solr и базой данных будет порядка 100X.

person jeff musk    schedule 11.02.2012