Как начать пользоваться школой!

Интересно? Полезно?
Подпишись на обновления в блоге одним кликом!
Реклама на блоге
Начинаем знакомство с лучших постов
Бронирование гостиниц
Продвижение сайтов


Rambler's Top100
Рейтинг блогов

Powered by  MyPagerank.Net
Яндекс цитирования

Моя аська: 155ноль54семь9 (всегда invisible)
Мой скайп: remarka.reklama
Мой емайл: masterxbablorub@gmail.com

среда, 12 сентября 2012 г.

Задачка для программиста

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

Если у вас есть гениальная мысль, как это сделать, и при этом вы еще и на РНР+МайСкуль свободно программируете, то пишите мне на masterxbablorub@gmail.com. Если ваши мысли совпадут с моим решением данной проблемы или окажутся лучше его, то пригласим за деньги или долю, или деньги и долю - к работе над онлайн-сервисом по выборкам.

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

Если нужна еще какая-то конкретика, то спрашивайте.


15 коммент.:

Вместо PHP лучше Node.js ассинхронность дает и MongoDB вместо Mysql даст тоже скорость. Плюс реплики сервера баз данных и шардирование. Можно прослойку Sphinx попробовать прикрутить для большего ускорения, но и так должно все шустро обрабатывать. У людей базы по 100 Гб нормально так ворочает.

без претензии на раб.место. SOLR вам нужен

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

@guts ну вот когда у вас рабочий прототип будет...:)
а так SOLR/Sphinx только с индексами без данных(только id)
при выборке по id "почти" без разницы, что у вас там за база данных.
ну а Node.js... да модно:)

а вам точно поиск по регекспам нужен? обычный полнотекстовый поиск для MySQL с неплохим стеммингом русского языка можно запилить на sphinx http://sphinxsearch.com/. Поиск по регекспам приходилось использовать в связке Mongodb + Mongoid + Ruby on Rails (http://www.mongodb.org/display/DOCS/Advanced+Queries#AdvancedQueries-RegularExpressions). В MySQL поддержка регекспов тоже есть http://dev.mysql.com/doc/refman/5.1/en/regexp.html но они не используют индексы для поиска, потому будет медленно. В данном случае комбинация LIKE & REGEXP может спасти "отца русской демократии". Ну или Mongodb таки )). на чем фронтенд будет (php или еще что) -принципиальной разницЫ нет.

"По любому запросу программный код должен полностью обойти всю базу" можно попробовать распаралелить поиск - искать в несколько потоков - каждый поток ищет в своей части базы )). это если обходить всю базу обязательно.

Не морочь голову себе и серверу, загрузки БД на амазон и делайте выборку оттуда. Облака справятся с нагрузкой. Копайте в сторону Amazon Relational Database

А база только на чтение будет работать в обычном режиме? Или пополняться тоже?

Не нужны тут облака. Более практичное решение отправил на указанную почту

Дима, знай, только подключением Sphinx можно не завалить сервер при данных задачах. В Sphinx встроен и stemming - также пригодится.

Дима, помни, "... программный код должен полностью обойти всю базу" - неправильно! Правильно: "... программный код должен полностью обойти весь ИНДЕКС", т.е. вся "on the fly"(ты же планируешь сервис) работа должна проделываться Sphinx.

Дима, учти, если позволишь себе сервер только для БД с оперативкой, в которую влезет вся база (также и в средней перспективе) - загоняй всё / работай с MySQL. Если нет - работай с NoSQL-управлением данными.

Дима, не лоханись, если много работы с регулярными выражениями - только perl!

--
Бесплатные и толковые советы даны толковым сервисом бесплатных объявлений SLANET - http://slanet.ru
SLANET - лучшей архитектуры приложения для мужчины нет :-)

Можно попробовать запрограммировать дерево ключевых слов (бор, trie). Дальше останется продумать реализацию джокеров, скажем с "*" всё просто. Ну и работать будет очень быстро, а именно линейно от суммарной длины ответа.

Для ограниченного бюджета, я бы разбил данные на 33бд по алфавиту, чтобы уменьшить объемы выборок. Далее действовал бы по методике rambler и cisco, выделил бы n пополняемых кэшей, которые бы создали различные ветви запросов. Примерно так: http://www.masters.donntu.edu.ua/2005/fvti/shadiaburuck/diss/images/animation.gif
Т.е. рамблер ищет сначала например по top 100, потом по товарам и т.д. аналогично можно выделить другие области.

Любые лайки, регэкспы, полнотекстовые поиски - начальный путь в тупик. Это будущая проблема с производительностью.

Организация поиска :
1. Создается таблица
2. Каждая исходная ключевая фраза разбивается на отдельные слова, каждое слово записывается новой записью, указывается ключ на полную фразу(доп время на связку) или вся фраза целиком(увеличение объемов хранения)
3. Для релевантности - учесть особенности русской морфологии, при составлении таблицы поиска у слов придется отсекать лишнее (окончания и т.д.).

В итоге должно получится что-то типа :
поиск поисковая фраза
фраз поисковая фраза

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

Организация таблицы :
1. Два поля : Word - слово, phrase - фраза целиком или ключ другой таблице
2. Партиционирование таблицы - на вкус, я бы использовал в данном случае hash партиционирование разбив на 30-50 партиций, опять же определяться на вкус и после проведения предварительных тестов.
3. Индекс по полю Word

В итоге получаем увеличение записей в 3-5 раз.
Партиционирование позволяет не сканить всю таблицу, попадая в нужный раздел.
Использование индекса помогает быстро найти то, что надо.

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

my buddy's half-sister makes $62 every hour on the laptop. She has been without work for seven months but last month her payment was $20367 just working on the laptop for a few hours. Read more on this web site http://Run19.com

Отправить комментарий

Популярные сообщения

Эту страницу: Twitter Facebook Favorites More