Здравствуйте!
Мне нужно реализовать базу данных под следующую задачу:
Дано примерно 100 миллионов записей, каждая из которых представляет собой набор атрибутов некоего объекта. Нужно уметь находить записи с помощью многокритериального поиска по произвольному набору атрибутов, выбранных пользователем.
Казалось бы классика. Но в отличие от "классической" задачи, успешно решаемой всеми реляционными СУБД, в моем случае набор атрибутов непостоянен - в процессе эксплуатации базы данных регулярно (скажем, несколько раз в неделю) добавляются новые атрибуты записей.
Более того, этих атрибутов очень-очень много - единицы тысяч. Большинство из них не заполнено у большинства записей. Это очень разряженная таблица с динамически добавляемыми колонками, если говорить в терминах таблиц.
И в любой момент времени пользователь может захотеть выполнить поиск по произвольным атрибутам, выбранным им самостоятельно.
Для простоты предположим, что значения атрибутов это только целые числа.
Система должна сохранять работоспособность при очень интенсивном потоке запросов - около 1 миллиона запросов в секунду (не опечатка).
Большинство запросов пользователя возвращают ему несколько записей. Но под другие запросы (их тоже много) потенциально подпадает очень много записей. В этом случае мне нужно получить фиксированное "n" произвольных записей, соответствующих критериям поиска, не нагружая СУБД выборкой всех сотен тысяч записей, подпадающих под критерии этого запроса - иначе никакая система не справится с миллионом запросов в секунду...
Так же система должна работать при очень интенсивном потоке обновлений (ориентировочно 1 миллион запросов на изменение значения атрибута в сутки).
В качестве отдельной дополнительной задачи (опционально, но очень желательно) нужно уметь находить "n" записей, которые по очень простой метрике наиболее близки к заданной - например, находить "n" записей, у которых наименьшее количество расхождений (сравнение на четкое равенство) значений атрибутов с заданной проверочной записью. Другими словами - "n" записей, у которых минимальное расстояние по Хаффману с заданной записью.
Какую готовую СУБД + примерную (на уровне базовых идей) организацию данных в ней (естественно я не прошу точного решения, которое стоит денег, но и не хочу получить ничем не подкрепленные ответы в стиле "Oracle решит все твои проблемы!") или какую нестандартную организацию данных Вы посоветуете для такой задачи?
Стоимость СУБД и стоимость железа не имеют значения в разумных пределах. Меня интересует возможность реализации подобной системы существующими готовыми средствами или на существующей теоретической базе, даже если стоимость железа и софта составит миллионы долларов.
Отдельный вопрос: существуют ли свободно продаваемые на рынке СУБД, которые масштабируются на кластеры из тысяч и десятков тысяч машин? Универсальные СУБД, которые можно просто взять и купить за деньги, а не заказать фирме разработку новой уникальной системы под свою конкретную задачу...

ModelRИМХО у Вас задача довольно специальная, и возможно объектные базы со специально разработанным кодом подойдут больше, чем субд общего назначения.Спасибо за ответ! Я понимаю, что задача специфическая, однако же сейчас уже существуют многие системы массового обслуживания, начиная от каких-нибудь сайтов типа www.ebay.com и заканчивая банковскими системами крупных банков, которые, согласен, являются уникальными системами, сделанными под свою конкретную задачу, но базовый-то слой у них есть, какая-то СУБД за ними всеми стоит, миллионы запросов в секунду молотит... Вот я и интересуюсь - созрели ли универсальные коммерческие системы до этого уровня или же любой такой сайт/проект - это уникальная разработка под одну конкретную задачу сделанная по сути с нуля с минимальным или чисто утилитарным использованием стандартных СУБД (чисто для хранения данных, например, но не для поиска)?
Так же интересно, есть ли люди, которым приходилось решать конкретно задачу многокритериального поиска в сильно разряженной таблице с тысячами "столбцов" по сотням миллионов записей. Пусть и не с таким рейтом запросов...

MX -- ALEXCACHE 5.2 ( InterSystems ) подходит по параметрам
Московское представительство :
http://www.intersystems.ru/cache/Спасибо за ссылку, но у них на всех диаграммах фигурирует некий "Data Server" несущий на себе нагрузку СУБД и как можно понять из прочитанных документов - это одна-единственная машина, у которой может быть backup (для надежности).
Если я прав, что тогда от нее толку? Покажите мне машину, производительности которой хватит на миллион запросов в секунду при многокритериальном поиске...
Это нереально - обрабатывать такой поток одной машиной, нужно кластерное решение, причем масштабирующееся на сотни, тысячи узлов. Сегодня у меня ожидается максимум 100 миллионов записей и миллион запросов в секунду - и скажем я рискну и начну этот бизнес. :) Но через 3 года, скажем, будет 1 миллиард записей и 10 миллионов запросов в секунду. И весь бизнес накроется медным тазом, если система не сможет масштабироваться...

miksoftесть ли атрибут, который есть у всех без исключения объектов?Есть и не один. Но, к сожалению, очень многие запросы не оперируют этими общими атрибутами. Для некоторых пользователей (и таких пользователей очень много) ценность представляют маленькие по объемам выборки по "хитрым и редким" атрибутам, а не по самым базовым. Базовые они могут вообще не затронуть выборкой.

miksoftа насчет миллиона записей в секунду - это перегиб, даже через канал 1 Гбит/с столько не пролезет чисто физическиКонечно же речь идет о системе, в которой будут работать тысячи машин, установленных на площадках основных провайдеров мирового уровня. Естественно не может быть и речи о том, чтобы собрать траффик в миллион запросов в секунду на одной-единственной машине или даже на десятке машин. Поэтому нужна кластерная система масштаба "на тысячу нод".

guest_20040621Это неправильная постановка задачи. Вам не базу данных нужно реализовать, а построить инфраструктуру, удовлетворяющую заданным характеристикам. Выбор СУБД здесь (и тем более - структуры данных) - хм... в самом конце списка задач.Как раз с инфраструктурой все более и менее понятно. Есть провайдеры, каналы которых образуют backbone Интернета. Они за разумные деньги позволяют разместить на своих площадках наши машины, принимающие клиентский трафик. Начать можно с малого - вообще с нескольких машин, а по мере роста количества клиентов количество машин можно плавно увеличивать и довести, скажем, до 1000 (для системы с миллионом запросов в секунду). В начале, пока система эксплуатируется экспериментально, она будет стоить "копейки", но затем количество клиентов начнет быстро расти, однако вместе с ними - и поступление денег, что окупит расширение инфраструктуры.
Балансировать входящую нагрузку на машины будут DNS-серверы плюс мы можем ретранслировать запросы с перегруженных принимающих узлов на другие узлы внутри своего кластера.
С точки зрения организации инфраструктуры и бизнес-модели окупающей аренду стоек и каналов у провайдеров - принципиальных проблем нет.
Проблема в том, чтобы эти 1000 машин, размещенных на жирных каналах и прекрасно связанных друг с другом (или как вариант - размещенных в одном data center с жирными входящими каналами, если внутри кластера будет своя еще более скоростная сеть) заставить решать собственно содержательную задачу многокритериального поиска.
Не в железе тут проблемы, не в каналах и не в бизнесе, окупающем аренду точек приема трафика (жирных каналов) и стоек. Проблема в том, что содержательно ни одна СУБД (насколько я понимаю) не потянет 1 миллион запросов в секунду при моей постановке задачи поиска в разряженной и динамически меняющейся таблице.

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

miksoftЯ бы дал нижнюю оценку вашего трафика в 10-100 Гбит/с. И это не считая трафика по поддержанию актуальности данных на серверах...
Так что, имхо, одним датацентром и DNS-балансировкой тут не обойдешься.
Сейчас в Европе живет около 800 миллионов человек, в США около 300 миллионов, в Японии - 130 миллионов, в Южной Корее - 50 миллионов и так далее, не говоря уже об Индии (1 миллиард человек) и Китае (1.3 миллиарда человек). В Европе, в США, в Японии уже практически все люди 16...45 лет так или иначе постоянно используют Интернет (дома, на работе, в библиотеках, в интернет-кафе и т.п.), а через 5 лет человек, который не пользуется Интернетом в повседневной жизни, будет казаться таким же странным, как сейчас человек без мобильника. Кстати мобильные сервисы опять-таки будут все реализованы через IP! (это важно).
Предположим, что есть некий сервис, ожидаемое число активных пользователей которого через 4-5 лет составит около 300 миллионов человек, а количество разовых посетителей может быть еще в два раза больше, где-то 600 миллионов человек.
Если каждый из них в день в среднем пошлет 10 запросов, то получится трафик примерно в один миллион запросов в секунду.
Конечно, нет и речи о том, что у сервиса сразу будет столько пользователей - но специфика такова, что есть смысл создавать его только в полной уверенности, что в ближайшие 5 лет компания не столкнется с проблемой взрывного роста популярности и сервис не упадет из-за неспособности наших серверов "переварить" трафик. Не должно быть именно технических проблем - они угробят всю идею.
Идея этого бизнеса такова, что он должен стать именно глобальным и войти в повседневную жизнь масс.

miksoftимхо, цифра в миллион запросов в секунду - абсолютно безосновательна!
в мире порядка одного миллиарда интернет-пользователей, неужели они все круглые сутки будут каждую тысячу секунд делать по запросу?Через 5 лет - будут. Они будут делать эти запросы не только сидя за клавиатурой классических PC, но так же со своих мобильных телефонов, всяких гаджетов, из автомобилей и так далее.

Кстати отдельное спасибо за статистику. :)

miksoft sysprgя написал в данную конференцию, чтобы убедится в этом - ведь от этого зависит принятие решений по проекту (вплоть до отказа от проекта, если он вообще технически или алгоритмически нереален).этот проект сможет реализовать только тот, кто не знает, что он невозможен! :)
и при условии, что найдет миллионы долларов на предварительные исследования... и не при текущем уровне развития интернета...Все когда-то начиналось как проекты, имеющие сотню пользователей, а затем НЕКОТОРЫЕ из этих компаний получили сотни миллионов пользователей. Почему бы не попытать счастья? :) Необходимое условие в данном случае - наличие технической/алгоритмической базы - так как было бы действительно глупостью делать проект, который уже через год столкнется с гораздо меньшим, но уже большим трафиком, все сайты полягут, время реакции станет неадекватным и доверие к ресурсу у пользователей будет необратимо подорвано.
Я видел как загибались некоторые интересные проекты не справившись с наплывом посетителей. А затем их место занимали другие.

MX -- ALEXу них 5-6 сентября конференция (см на сайте)
Будут интересные разработчики.
Вам возможно надо поговорить напрямую
например - системы в мобильной связи на CACHE
Спасибо за информацию!

Last_AlienСначал по второй таблице ищем атрибут, который содержится в наименьшем количестве записей. Потом по этому атрибуту делаем предварительную выборку из первой таблицы. Потом по ID и остальным iAttr делаем отсев ненужного.

P.S. Если у проекта так хорошо с деньгами, может и мне $50k за идею подкинете?:-)))Увы, тривиальные решения работают только на тривиальных задачах. Пользователь может запросить информацию по двум атрибутам, по каждому из которых есть, скажем, 10000 записей, а их пересечение - всего-навсего 100 записей. Если я буду из базы выгребать даже 10000 записей для последующего отсеивания, то мне никаких машинных мощностей не хватит при большом потоке запросов. Как я сказал в постановке задачи, многих пользователей интересуют "нетривиальные" пересечения, у которых короткий ответ, но по "ID" атрибутов это предсказать трудно - даже по самому "короткому" из них может быть достаточно много записей (не миллионы, но много).

guest_20040621Это заблуждение. Основные затраты - это не набитые серверами шкафы и не аренда места в датацентрах (это-то как раз дешево), а программная реализация файловой системы, сервера приложений и СУБД. При условии, разумеется, что есть операционная система, которая готова с ними работать. ;)) Напрасно Вы labs.google.com проигнорировали.
В том-то и дело - именно поэтому я и спрашиваю в этом форуме о существовании ГОТОВЫХ СУБД с такими характеристиками - пусть даже частично удовлетворяющих требованиям. Именно из-за четкого осознания того, что разработка соответствующего ПО самостоятельно - чрезвычайно сложная, трудоемкая и долгая в реализации задача (без гарантии успеха, кстати).

А вот файловая система и ОС подойдут "любые" - сейчас это фактически просто низкий уровень, как процессор, например. Мы ставим разные процессоры в свои компьютеры, а приложения не сильно напрягаются анализом того, какой именно процессор там установлен (если система команд одна и та же, например Intel x86). До такого же уровня развития дошли и ОС, файловые системы - по большому счету (если не брать крайности) уже пофиг, какая именно ОС и какая именно современная файловая система используется ниже уровня СУБД. Собственно все упирается в саму СУБД (которая файловую систему может не использовать вовсе, а от ОС ей нужны только средства управления страничной памятью, TCP/IP и еще драйвер диска, по большому счету).

guest_20040621Для того, чтобы приложение обеспечивало обработку 1M запросов в секунду, совсем не обязательно, чтобы отдельный экземпляр СУБД обеспечивал такую производительность.Это понятно, но мне лично неясно, как разделить данные и при этом не потерять возможность обрабатывать запросы с помощью СТАНДАРТНЫХ средств (даже самых развитых СУБД, представленных на рынке). Однако вопрос для меня важный, поэтому хотелось убедится, что подходящего готового решения нет. Чтобы не: 1). отказаться от проекта, который на самом деле может быть сделан, 2). не ввязываться в свою разработку в том случае, если подобные готовые движки все же существуют и могут быть куплены в готовом виде.

kdvя тоже сомневаюсь, что при такой постановке задачи человек вообще пойдет что-либо спрашивать, и тем более сюда, при всем уважении к этому форуму.IMHO в ex-USSR программисты быстрее всего изучают новые технологии и знают состояние дел именно в технологическим и алгоритмическом аспекте в среднем лучше, чем на Западе. Поэтому мнение форума мне очень интересно. Задавать же вопросы некоторым ведущим западным специалистам, контакты с которыми потенциально можно найти - нельзя, так как было бы глупостью вводить в суть дела их нанимателей, которые потенциально просто сделают это сами ( если они вдруг заинтересуются идеей).