Здравствуйте!
Мне нужно реализовать базу данных под следующую задачу:
Дано примерно 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 программисты быстрее всего изучают новые технологии и знают состояние дел именно в технологическим и алгоритмическом аспекте в среднем лучше, чем на Западе. Поэтому мнение форума мне очень интересно. Задавать же вопросы некоторым ведущим западным специалистам, контакты с которыми потенциально можно найти - нельзя, так как было бы глупостью вводить в суть дела их нанимателей, которые потенциально просто сделают это сами ( если они вдруг заинтересуются идеей).

miksoft sysprg600 миллионов человек.
Если каждый из них в день в среднем пошлет 10 запросов, то получится трафик примерно в один миллион запросов в секунду.
даже если все эти 600 миллионов ломанутся к вам в один день (что я считаю абсолютно невероятным для любого сервиса в ближайшие 5 лет), то это получается около 70 тысяч запрос в секунду, но никак не миллион.Через 5 лет все мобильные устройства (телефоны, прочие гаджеты) будут постоянно подключены к Интернету и все интеллектуальные сервисы на них будут реализованы over IP. Если Вы скажете, что это нереально - посмотрите, например, на развитие IP-телефонии. 5 лет назад этот рынок рассматривали как перспективный, но все же не шло речи о том, что IP-телефония убьет обычную. Сейчас миллионы людей уже вообще не имеют у себя обычных телефонных линий, вообще все long-distance call идут через IP (даже если пользователь об этом не догадывается) и не только fixed телефония уже исчезает как класс, но и мобильные телефоны свои voice-сервисы скоро будут делать через VoIP, а не по своим древним протоколам. Точно так же будет и с прочими мобильными сервисами, все они будут реализованы over IP и все мобильные устройства перманентно будут иметь доступ к Интернету (если их хозяин пожелает им воспользоваться - сможет сделать это в любой момент). А теперь скажите мне, сколько пользователей мобильных телефонов в мире? :) Дайте им интересный сервис - и в эпоху тотального подключения всех мало-мальски развитых стран к Интернету Вы получите многие сотни миллионов клиентов. Особенно если стоить им Ваши услуги будут копейки (а некоторые будут бесплатны).

miksoftи еще - тот же Гугл и Яндекс обладают мощными командами разработчиков (в широком смысле этого слова), которые уже не один год строят свои системы.Важно понмнить - так было не всегда.

miksoftА вам нужно найти значительно больше разработчиков не меньшей квалификации, чтобы хотя бы сравняться с лидерами.Если бы эта логика была правильной, то того же google или, скажем, ICQ, eBay и прочих просто не существовало бы. Как и Microsoft, кстати.

Впрочем мы уходим в обсуждение offtopic-а - что такое бизнес и почему маленькие компании регулярно "выносят" с рынка "монстров".

guest_20040621 sysprgпофиг, какая именно ОС и какая именно современная файловая система используется ниже уровня СУБД
Дружище, Вы бы почитали что-нибудь по этому поводу, прежде чем воздух сотрясать.Вот только не нужно надувать щеки и строить из себя "крутого", фамильярничая. Файловую систему вообще обычно не используют когда нужна скорость, работая с raw разделами на дисках - именно для ускорения работы. Даже на mainframe файловую систему в СУБД не используют по назначению. От ОС же требуется по сути только драйвер дисков (работающих в режиме raw доступа), страничный механизм памяти (опять-таки - более тонкое распределение памяти - самописное во всех движках СУБД), виртуализация процессора (threads, для утилизации мультипроцессорности) и еще TCP/IP стек быстрый. Так что по сути пофиг, какая именно ОС используется - все современные ОС примерно одинаково хорошо справляются с этой базовой работой. Про мэйнфреймы IBM с их уникальным особенным железом и операционными системами за миллион долларов сдаваемыми в аренду можно мне не рассказывать.

guest_20040621 sysprgмне лично неясно, как разделить данныеКто сказал, что их нужно разделять?Логика. Разделение позволяет избежать перегрузки отдельного узла - распараллелить работу.

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

Вот благодаря подсказке в форуме удалось выяснить, что ближе всех по своим характеристикам мне подходит IBM DB2, которая реально демонстрировалась на больших кластерах и действительно работает на них и есть отзывы об этом (удалось найти статьи). Увы, система IBM не лишена недостатков - она использует подход sharing nothing, но это все же намного лучше, чем то, что показывают другие. Интересные наработки у Oracle - но похоже у них проблемы с масштабируемостью на большие кластеры.

guest_20040621Дружище, у Вас терминология на уровне школьника, - с такими знаниями незачем лезть в разработку.См. первое предложение в ответе.

miksoftкстати, еще мысль про Гугл и Яндекс - при поиске они дают приблизительный ответ, т.е. не гарантируются ни точность, ни воспроизводимость поиска! И если часть данных по какой-то причине в данный момент недоступна, но сервера оперируют тем, что у них есть.

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

miksoft sysprgВы получите многие сотни миллионов клиентов.только этих клиентов придется делить с сотнями и тысячами других аналогичных сервисов, начиная с монстров типа Гугла, и заканчивая мелкими региональными провайдерами.Опять мы про бизнес. :)
Но раз уж зашел разговор, то тут есть два соображения:
- Некоторые сервисы ценны именно своей глобальностью и будучи растащенными по отдельным провайдерам или территориям они или полностью теряют смысл, или сильно теряют привлекательность в глазах клиента. Поэтому их следует реализовывать как глобальные в плане географии и метода подключения к Сети с самого начала.
- Если повезет быть первыми - то потом другим тысячам сайтов придется пытаться урвать у тебя кусочек рынка, а не тебе с ними тягаться. :) Вспомните - когда-то Google не существовало, когда-то ICQ не существовало, когда-то eBay не существовало и даже Microsoft когда-то не существовало.

ggvмного лет назад я сказал в беседе с одним старым, опытным, и высокопоставленным телекомщиком - "канальная коммуникация must die!"
На что он мне ответил - "не дождетесь!"
Затем я долго работал в телекоме, и теперь я уже совсем не так категоричен :)
Вы привикли, что если нет света, воды, тепла, то вы всегда можете снять трубки и набрать кто 911б кто 01-02-03
IP не убъет канальную коммуникацию в обозримом будущем.У меня дома нет fixed телефона вообще, как и у миллионов других людей. Если мне нужно будет позвонить в экстренную службу, а IP-провайдер полег - я воспользуюсь мобильным телефоном. Который хотя и не использует сейчас IP, но использует пакетную передачу данных. А через некоторое время будет использовать классические VoIP технологии (по мнению ведущих западных аналитиков).

miksoftиначе бы не на форуме прожектёрством занимался, а профессионалов нанял...Hint: подскажите мне, как проще всего отличить профессионала от распальцованного "специалиста" с тысячей сертификатов ищущего нереальную зарплату? ;)

pavelvp 2 sysprg Это только мысли или у тебя помимо мыслей есть ещё и деньги?Деньги эфемерны и не в них счастье, так какой смысл обсуждать в форуме интересные проблемы в разрезе денег? Деньги приходят к тому, кто готов их взять.

AAronСтранно все это.
1. Вместо того, чтобы запустить проект для много меньшей нагрузки и начать зарабатывать деньги, автор сотрясает воздух.Деньги поначалу поступают медленнее, чем растет нагрузка. Если стартовать не имея запаса прочности, то весь проект будет провален из-за того, что элементарно поляжет под нагрузкой и дискредитирует себя в глазах своих пользователей. Но тут же на это место придут другие, как бывает всегда. Поэтому в данном случае нужно сначала проработать ядро системы на опережение (и в бизнесе, так и в технологии) и уже затем запускать сервис. Я видел, как погибали интересные бизнесы, которые не справились с нагрузкой - и на их место приходили другие ребята. Представляете как было обидно тем, первым?

AAron2. автор действительно надеется, что люди уже обладающие такими знаниями будут ими делиться?Какими знаниями? Я же не прошу технического задания для программистов или описания структуры базы данных. Меня интересует опыт участия и примерные соображения как это сделать, интересуют имеющиеся технические средства (готовые СУБД) и алгоритмические идеи - если тут присутствуют представители "академической среды".

AAron3. На мой взгляд, количество запросов в 1М/с необосновано.Сейчас - согашусь, да. Но нужно думать о будущем, если ты в проекте участвуешь не просто формально, за зарплату.

ggvесли у вас нет фиксированной линии - то это не значит, что пакетная коммутация окончательно победила :)Если сами телефонные компании гонят long-distance трафик через IP, то даже не смотря на то, что у "традиционных" абонентов пока что еще стоят обычные телефоны - это все равно говорит о том, что пакетная коммуникация победила. :) Зачастую уже дешевле платить за IP, чем за классическую fixed телефонную линию.

Anton DemidovКстати, было бы интересно посмотреть на аналогичное сравнение от IBM, может кто видел - киньте линк, плиз.
Что нашел на их сайте:
www-306.ibm.com/software/data/db2/benchmarks/111704.html
www-306.ibm.com/software/data/highlights/scalecluster.html