pg 2011

Исследование алгоритмов поиска слабо-структурированной и неточной информации для классических и сверхбольших баз данных

ФОРМА 4. СОДЕРЖАНИЕ ИНИЦИАТИВНОГО ПРОЕКТА

4.1. Фундаментальная научная проблема, на решение которой направлен проект:

Значительная часть научно-технической информации, накопленной ранее, уже переведена в электронную форму. Что касается вновь получаемой информации, то последние годы уже 99.9% (а возможно - и 100%) сразу возникает также в электронной форме. Успехи в технологии

По своей природе вся такая информация относится к классу нечетко-структурированной (или полуструктурированной, semistructured). Кроме того, к этому же классу относится сейчас и практически вся общая информация, накопленная в мировом web. Все нарастающее требование интеграции информации из различных источников как в науке, так и в бизнесе, также приводит к появлению большого объема нечетко-структурированной информации, причем даже при наличии строгой схемы данных в индивидуальных источниках, из-за большого разнообразия форматов хранения и описания данных. Колоссальные объемы этой информации уже 5-10 лет назад выдвинули на первый план задачи организации поиска именно в таких массивах информации. Машины стали основными производителями информации и ее потребителями, поэтому на первый план выступает задача обеcпечения программного доступа к данным для автоматизации рутинных операций, чтобы машины могли работать с машинами.

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

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

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

Так, классические реляционные базы данных, несмотря на все их усовершенствования последнего десятилетия, оказываются практически неработоспособными на объемах данных выше 50-150 терабайт. И это положение оказывается невозможно исправить ни применением самых мощных современных суперкомпьютеров, ни использованием наиболее совершенных аппаратных хранилищ данных.

Это положение оказывается особенно критическим для науки в целом, и, особенно, для тех наук, в которых сейчас накапливаются огромные объемы первичных данных ("data driving sciences"), таких как физика элементарных частиц, метеорология, астрономия, аэродинамика, и многих других. Уже сейчас стали реальностью накопленные массивы данных, объем которых превышает петабайт. Современные научные эксперименты из разряда "большой науки" сталкиваются с необходимостью работы с беспрецендентными объемами данных, на грани возможностей, которые предоставляет компьютерная индустрия и информационные технологии. Речь идет о таких экспериментах, как LHC (большой Адронный Коллайдер), LSST (Большой обзор неба) с их петабайтами информации. Детектор ATLAS, предназначенный для поиска бозона Хиггса, выдает около петабайта сырых данных в секунду. Такие объемы и скорость современная индустрия обеспечить не может, поэтому сырые данные в режиме реального времени обрабатываются и "неинтересные события" фильтруются, оставляя около 100 мбайт в секунду (несколько сотен событий) или около петабайта в год.

Современный бизнес также сталкивается с проблемой хранения,обработки и анализа гигантских объемов данных, так например, поисковый гигант Гугл заявляет, что ежесуточно сервера компании обрабатывают 24 петабайта информации в сутки, а электронный аукцион Ebay и крупные социальные сети давно перешагнули петабайтный порог и тоже стоят перед проблемой управления большими объемами данных.

Начиная с 2008 года, ряд крупных изданий такие как, Nature (2008), CACM (2008), The Economist (2010) ,Science (2011), выпустили специальные издания, посвященные проблеме Больших Данных (Big Data), термину, который принято использовать для описания проблемы, когда для работы с данными, объем которых превышает возможности доступных на данный момент технологических средств, требуется разработка специальных инструментов. И уже совсем полное признание проблеме "Big Data" придало упоминание, в вышедшем 26 июля 2011 года традиционном исследовании компании Gartner "Hype Cycle for Emerging Technologies, 2011", нового тренда '"Big Data" and Extreme Information Processing and Management', который позиционируется на участке первоначального роста, когда рынок еще до конца не понял, что точно ожидать от этой технологии и связывает с ней слишком большие ожидания.

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

Осознание проблемы "Больших Данных" в науке и бизнесе привело к пониманию новой архитектуры информационных систем, которая призвана справиться с этими "цунами данных". В первую очередь, это должен быть кластер независимых многоядерных компьютеров, имеющих собственные диски, соединенные быстрой сетью, на котором установлена СУБД, ориентированная на работу с распределенными очень большими данными и параллельную обработку. Гигантские объемы данных делают старый способ обработки данных на суперкомпьютерных кластерах, когда данные из хранилища копируются в большой вычислительный кластер, экономически невыгодным и неэффективным.

Если рассматривать "Big Data", как данные, которые производят люди и машины, то основным производителем данных являются именно последние, так как рост населения Земли ни в коей мере не следует закону Мура и за последние 10 лет население увеличилось всего на 20%, в то время как количество транзисторов (а вместе с ним и емкость жестких дисков) увеличилось более чем на 2000% (Daniel Abadi). Машины стали основными производителями информации и ее потребителями, поэтому требуется обеcпечить прежде всего не интерактивную работу с данными, а программный доступ к ним, чтобы можно было автоматизировать рутинные работы обработки наблюдений, поиска данных, чтобы машины могли работать с машинами. Одной из основной проблемой для организации межмашинного взаимодействия является проблема неточных данных, когда приходится работать с данными, чьи значения известны с ошибкой, например, с результатами измерений. Сенсоры, по своей физической природе, генерят данные с некоторой ошибкой, а гигантские сенсорные сети уже сейчас производят "цунами данных", которые надо не только уметь хранить, но и обрабатывать, а затем делать выводы, принимать решения и все это с учетом "неточности", заложенных в данных.

В настоящее время не существует готовых инструментов для работы с большими данными и требуются новые алгоритмы работы, ориентированные на данные петабайтных размеров, не требующие дополнительного дискового пространства, устойчивые к сбоям системы, параллелизующиеся по процессорам и узлам. Помимо стандартных операций с данными, требуется реализовать новую функциональность, такую как работу с неточными данными, версионность данных и процедур обработки данных. Такие популярные задачи, как сведение данных, полученных из разных источников (data cleaning, data merging, de-deduplication), требуют особых методов анализа в случае неточных данных, особенно для данных петабайтных размеров.

4.2. Конкретная фундаментальная задача в рамках проблемы, на решение которой направлен проект:

Группа авторов данной заявки уже более 10 лет ведет активные исследования в области алгоритмов поиска и методов хранения нечетко-структурированной (эти исследования поддерживались, в частности, грантами РФФИ 96-07-89395-в, 99-07-90069-в, 03-07-90187-в, 06-07-89182-а, 09-07-00471-а, а также целым рядом грантов других фондов и организаций). Поэтому представляется естественным, учитывая накопленный опыт, сконцентрироваться на наиболее актуальных задачах именно этого класса, с учетом специфики сверхбольших объемов данных.

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

Известно, что при работе с нечетко-структурированной информацией важнейшую роль играют такие понятия, как точность результатов поиска и выбор метрики релевации результатов. При этом, очевидно, достичь заданной точности тем труднее, чем больше объем информации, с которой мы работаем (это можно сформулировать и по другому: чем больше объем данных, тем выше требуемая точность - просто из соображений практичности). Абсолютно такая же ситуация и с релевантностью. Чем больше объем данных, тем более сложные и "умные" метрики для релевантности становятся необходимыми. В этом отношении задачи и направления исследований данного класса, которые были актуальны последние годы, полностью сохраняют свою важность.

С другой стороны, как было отмечено выше, многие классические методы, используемые в современных СУБД, становятся непригодными при переходе к данным объемами в сотни терабайт и в петабайты, и более того, как утверждает один из создателей всего направления DB Michael Stonebraker, пора прекратить "штопать" традиционные СУБД, которые были разработаны для старой архитектуры компьютерных систем, и приступить к разработке "с нуля" новой СУБД, ориентированной на использование в кластерах многоядерных компьютеров, соединенных быстрой сетью, и предназначенной для сверхбольших баз данных (XLDB). Проект получил название SciDB (www.scidb.org) и успешно развивается последние 3 года, внедряя большое количество инноваций, такие как вертикально-ориентированное хранилище, многомерные вложенные массивы как основной тип данных, версионность данных, и многие другие. Однако, разработка принципиально новой СУБД является сложным и долгих процессом с неустойчивыми программными интерфейсами, что затрудняет исследование и внедрение новых прикладных алгоритмов, поэтому на данном этапе логично использовать уже существующиe реляционныe СУБД, например, свободно распространяемую PostgreSQL, для исследовательских задач и реализации программных модулей, которые уже можно использовать в реальных приложениях. Учитывая популярность PostgreSQL в научном сообществе и что часть авторов данной заявки являются ключевыми членами мирового сообщества по развитию PostgreSQL, представляется разумным вести разработки проекта именно в данной технологической среде. При этом, как уже показал опыт работы над предыдущими проектами, обеспечивается высокая степень координации исследований с другими ведущими мировыми коллективами, работающими в данной области, и на порядки повышается практическая востребованность результатов работ.

И последнее важнейшее соображение, определяющее выбор конкретных задач данного проекта. Как показывает многолетняя мировая практика, работы такого плана (исследование алгоритмов, работающих на больших объемах данных) довольно часто оказываются слаборезультативными, если исследователи не опираются на некоторую конкретную "тестовую площадку", которая активно используется в практической работе. Это совсем не означает, что работа превращается в создание какой-то одной технической реализации, и приобретает рутинный характер. Наоборот, очень часто чисто практические запросы такой "тестовой площадки") приводят к созданию алгоритмов, имеющих фундаментальное значение, и востребованных в дальнейшем в очень широком классе приложений.

Для данного проекта такой "тестовой площадкой" является объединенная информационная астрономическая система. Ее основой являются ведущий российский проект "Астронет", который будет (в рамках отдельного проекта) интегрироваться с коллекцией крупнейших мировых астрономических каталогов (которые уже реально существуют в рамках системы vo.astronet.ru), а также с создаваемыми сейчас в ГАИШ МГУ хранилищами астрономических фотографий (оцифровка "стеклянной библиотеки" - наблюдения за 150 лет, космический обзор неба "Лира" - автоматический телескоп, установленный на Международной Космической Станции, вход в строй нового 2.5-метрового автоматического телескопа и некоторые другие).

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

- Дальнейшее развитие расширяемости PostgreSQL в сторону поддержки небалансированных поисковых деревьев, а именно, разработка SP-GiST (Space-partitioned GiST) - программного шаблона для реализации небалансированных поисковых деревьев. Это позволит реализовать такие структуры, как квадратичные деревья, суффиксные деревья, имеющие большое значение для научных исследований, например, для астрономии, биологии. Существующие системы расширяемости PostgreSQL поддерживают только балансированные деревья;

- создание алгоритмов для увеличения эффективности работы обобщенных индексов GiST и GIN, расширения набора типов данных, допускающих такое индексирование, а также для реализации более сложных методов сравнения;

- Разработка алгоритмов массовой вставки (bulk upload) для всех классов поисковых деревьев (GiST, GIN, SP-GiST) для ускорения построения индексов, что чрезвычайно важно для работы с очень большими объемами данных;

- Работы по развитию планировщика и оптимизатора для лучшей поддержки новых пользовательских типов и операций;

- Исследование новых возможностей, предоставляемые, так называемых, Index-Only Scan Tables (IOS), например, для ускорения полнотекстовых запросов;

- Дальнейщее развитие полнотекстового поиска, в частности, создание алгебры полнотекстовых запросов и ее реализация, использование для реализации полнотекстового поиска с учетом расстояния между словами (поиск фраз), реализация неполного поиска и разработка новых методов ранжирования результатов поиска;

- Исследование алгоритмов работы с неточными данными в СУБД, реализация нового типа неточных данных и операций для работы с ним;

- Исследование эффективности использования разных типов данных для работы с очень большими массивами данных со сферическими атрибутами (ГИС, астрономия, науки о земле);

- разработка новых возможностей по интеграции данных - работа с внешними данными доступными, используя реализацию SQL/MED (http://wiki.postgresql.org/wiki/SQL/MED) в PostgreSQL;

Полный список задач (всего их около 20) и их конкретизация приведены в плане работ (п.4.3).

4.3. Предлагаемые методы и подходы:

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

Авторы проекта уже традиционно используют в своих работах только открытое (opensource) программное обеспечение, а результаты исследований и конкретные имплементации также становятся доступными мировому сообществу как opensource. Этот подход планируется применять и в данном проекте. Практически все задачи будут решаться в рамках общего развития свободно распространяемой СУБД PostgreSQL. Такой подход гарантирует высокую актуальность всех решаемых задач как для данного проекта, так и для мирового научного сообщества в целом. Кроме того, это обеспечивает высокую востребованность всех получаемых результатов, т.к. большинство успешных разработок сразу либо включаются в ядро PostgreSQL, либо становятся общедоступными как расширения PostgreSQL.

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

Как легко видеть по плану работ, значительная часть задач связана с развитием расширяемости PostgreSQL - алгоритмов работы для GiST, GIN и SP-GiST индексов (Generalized Search Tree, Generalized Inverted Index, Space-Partitioned GiST), а также с их использованием. Данные типы индексов (к созданию и имплементации которых в ядро PostgreSQL авторы проекта имеют непосредственное отношение), собственно, и создавались как уникальное по своей гибкости средство расширения возможностей СУБД, позволяющее вводить новые типы индексируемых данных, и новые операции, связанные с индексным поиском. Весь опыт развития и использования PostgreSQL в мире за последние 10 лет подтверждает уникальную гибкость и эффективность такого подхода. Поэтому активное продолжение исследований в этом направлении представляется крайне актуальным, кроме того - это очень востребованное направление развития современных СУБД. Использование этих инфраструктур расширяемости предполагается использовать и для разработки новых типов "неточных" данных и операций с ними.

Многие результаты исследований и разработки, апробированные в PostgreSQL, могут быть использованы в SciDB, разработка которой в настоящее время сконцентрирована в основном на базовой функциональности.

План работ по проекту

Первый год

1. Разработка прототипа нового поискового дерева – SP-GiST (Space-partitioned GiST) - разработка программного шаблона для реализации небалансированных поисковых деревьев. Это включает разработку базовых методов работы с поисковым деревом, выработку программных интерфейсов и реализацию индексной поддержки для нескольких структур - quadtree и suffix tree, как наиболее востребуемых в задачах информационного поиска.

2. Исследование методов построения репрезентативной выборки и алгоритмов построения гистограммы частотности для получения надежной оценки селективности для операций contains, contained by и overlap. Имплементация этих алгоритмов в ядро СУБД и проведение тестов для разных типов данных. На данный момент хорошую оценку селективности имеют только скалярные типы данных, для которых используется B-tree индекс.

3. Оптимизация OR и IN() запросов для скалярных типов данных, например, учет перекрывающихся диапазонов, так что,выражение (a > 1 AND a < 5) OR (a > 4 AND a < 6) приводится к более простому выражению (a > 1 AND a < 6). Подобные виды запросов часто встречаются в автоматически-генерящихся запросах.

4. Переписывание неперекрывающихся диапазонов в соответствии с условием сортировки в ORDER BY, что позволит использовать просто index scan, что гораздо эффективнее использования bitmap index scan с последующей сортировкой.

5. Оптимизация OR и IN() запросов, используя GiST/GIN/SP-GiST индексы, поддерживающие операции contains, contained и overlap. При этом OR/IN запросы могут быть переписаны используя операцию contained.

6. Разработка расширения PostgreSQL для управления "видимостью" индексов для планера, что удобно для разработчиков и для отлаживания запросов.

7. Разработка расширения PostgreSQL для анализа поисковых деревьев - необходимый инструмент для разработчика новых индексов.

8. Разработка эффективного поиска ближайших соседей для SP-GiST, используя модификацию алгоритма Самета, что позволит выполнять процедуры слияния данных, нахождения дубликатов, поисковые запросы для неточных данных на очень больших объемах данных, минимизируя работу с диском и процессором.

9. Исследование новых возможностей, предоставляемые, так называемых, Index-Only Scan Tables, например, для ускорения полнотекстовых запросов. В настоящее время, производительность полнотекстового поиска лимитируется доступом к таблице для получения информации о "видимости" записи, в то время как непосредственно поиск в индексе (GiST, GIN) происходит очень быстро. Кроме этого, для релевации результатов поиска требуется также обратиться к запросу, чтобы получить необходимую информацию (координаты слов из запроса в документе), что происходит в режиме случайного чтение (random heap scan) и сильно медленно. IOT позволяют избежать первую причину чтения таблицы, так как информация о "видимости" будет доступна при работе с индексом. Интересно было бы добавить возможность хранения координатной информации в самом индексе, так что поиск по индексу мог возвращать указатели на записи в таблице в правильном (согласно используемой функции ранжирования) порядке.

10. Исследование подходов и методов для реализации поддержки неточных данных в PostgreSQL. Разработка нового типа данных, описывающий оба типа неопределённости информации - как величины записи, так и её наличия - и предоставляющий удобные интерфейсы для ввода данных с произвольными распределениями вероятности. При этом требуется поддержка как аналитически задаваемых распределений (нормальные, равномерные итд), так и описываемые дискретными, либо приближёнными гистограммами распределения величин, также как категориальные. Реализация базовых (арифметических) операций для этого типа данных с соответствующим преобразованием функций их распределения. Определение вероятностных аналогов обычных операций отношения двух величин (операции сравнения и другие) на задаваемом пользователем уровне значимости.

11. Исследование и разработка эффективных методов работы с исторической информацией, в частности, с неточными историческими датами, задаваемыми временными интервалами - как замкнутыми, так и открытыми, и реализующий поддержку подмножества Алленовской логики (http://en.wikipedia.org/wiki/Allen%27s_Interval_Algebra), требуемого для основных операций сравнения и сортировки таких данных.

12. Исследование различных алгоритмов кластеризации для SP-GiST для эффективной работы с индексом. Как известно, такие структуры данных, как quadtree, suffix tree, известны своей хорошей производительностью при использовании их в памяти, но для сверхбольших массивов данных, которые не помещаются в память, требуется эффективная поддержка работы с дисковой памятью. Модификация структур требует изменения всех алгоритмов работы, поэтому наиболее предпочтительным способом представляется разработка промежуточного слоя, который маппирует узлы дерева на дисковые страницы, сохраняя локальность и оптимальную заполняемость страниц.

13. Разработать поддержки конкурентности и восстанавливаемости после сбоев для SP-GiST.

14. Разработка поддержки конкурентного вакуума для SP-GiST, который необходим для сбора статистики и очистки индекса.

15. Сравнение производительности SP-GiST с B-tree и GiST для разных типов данных на основе синтетических и реальных данных. Предоставление реализации SP-GiST для рецензирования и тестирования, доведение разработки до принятия сообществом.

16.Разработка алгебры запросов для поиска фраз (phrase search) в полнотекстовом поиске. Перед пользователями поисковых систем часто встает задача найти весь текст по одной, известной пользователю, фразе. Текущая реализация полнотекстовго поиска позволяет найти все тексты, содержащие все слова из фразы, пусть даже эти слова разбросаны по всему тексту. Это приводит к слабой релевантности результатов поиска. Для поддержки поиска фраз предлагается дополнить стандартный набор операций (AND, OR,NOT и группировки) над словами в поисковом запросе операцией NEAR, являющейся операцией AND с ограничением расстояния между операндами и сохранением порядка операндов. Для корректного введение этой операции необходимо разработать непротиворечивую алгребру расширенного комплекта операций (AND, OR, NOT и NEAR).

17. Разработка новой функции ранжирования поисковых запросов для реализации неполного поиска (incomplete search), который предполагает "расширение" слишком "узкого" поискового запроса, который не дал ни одного результата. Современные поисковые машины используют технику переписывания оригинального запроса, например, если запрос 'A AND B AND C' не привел ни к чему, то используется более "широкий" запрос 'A OR B OR C'. Ранжирование результатов подобного поиска должно учитывать как количество совпадающих слов из запроса, так и их плотность (расстояние между ними). Существующие ранжирующие функции не предоставляют подобную возможность одновременно, поэтому требуется разработать новую функцию ранжирования.

18. Сравнение эффективности использования разных индексов для работы с очень большими массивами данных со сферическими атрибутами. Предполагается исследование B-tree индекса, который используется в нашем расширении Q3C (q3c.sourceforge.net), GiST-индекса для встроенного R-tree, PgSphere (http://pgsphere.projects.postgresql.org/), PostGIS и нового поискового дерева SP-GiST для quadtree. Важность такого исследования состоит в популярности использования этих данных в астрономии, науках о Земле, в Гео-информационных системах (ГИС), и необходимости оптимальной работы с ними в разных режимах - создание индекса, обновление индекса, поиск в и

19. Исследование возможностей по ускорению массовой вставки в поисковое дерево с использование буфферных деревьев. Предполагается ускорение GiST, SP-GiST поисковых деревьев. На больших объемах данных создание индекса может стать серьезной проблемой, особенно для сложных типов данных.

20. Разработка новых возможностей по интеграции данных - работа с данными доступными через веб-сервис (внешние данные) с помощью стандартного языка структурированных запросов (SQL/MED),например, выборка данных доступных через веб сервис с учётом различных критериев (фильтры, сортировка, агрегация и другие возможности языка структурированных запросов), выборка данных доступных через веб сервис с их последующим объединением с другими табличными данными (возможно другими данными доступными через веб сервис);

2. Исследование алгоритмов оптимальной кластеризации бинарных сигнатур на диске для эффективного создания GiST индексов. Решение этой задачи позволит сильно улучшить поддержку массивов в PostgreSQL. Существующий вариант кластеризации использует квадратичный алгоритм Гуттмана с использованием расстояния Хемминга (количество несовпадающих битов) между сигнатурами. Недостаток такого подхода для больших и сверхбольших объемов данных - малое количество возможных уникальных расстояний, что приводит к плохой селективности индекса.

9.

Второй год

1. Исследование возможности применимости параллельных и распределенных БД PostgreSQL Plus, Greenplum, AsterData для хранения очень больших научных БД. Общим для этих коммерческих СУБД является то, что все они разрабатывались на основе PostgreSQL и доступны для тестирования. Практической целью этой задачи является получение конкретных данных по производительности и эффективности работы примененных в этих БД методов на различных конкретных наборах астрономических данных сверхбольшого объема, которые будут доступны в системе Астронет. Работы в этом направлении, вероятнее всего, будет необходимо проводить как во второй, так и в третий год работы над проектом (по мере того, как в хранилище Астронет будут возникать новые каталоги многотерабайтного объема). Это необходимо для более правильного понимания выбора стратегии развития, и для более точного выбора алгоритмов работы со сверхбольшими наборами данных.

2

3.

5.

6.

7. Расширение инфраструктуры полнотекстового поиска (http://www.postgresql.org/docs/current/static/textsearch.html) в PostgreSQL для обеспечения более гибких настроек пользовательского поиска. Существующая реализация предполагает использование стека словарей, которые пытаются привести входное слово к некоторой "стандартной", с точки зрения текущего словаря, форме. Предполагается улучшить интерфейсы настройки конфигурации поиска и поведения как словарей, так и самого стека.

Третий год

1.

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

3. Сравнение производительности вертикально-ориентированных БД и изучение возможности реализации выбранных алгоритмов для интеграции в PostgreSQL. Здесь необходимо подробно исследовать два подхода: - index-only scan - все колонки проиндексированы, запрещен последовательный доступ к данным; - декомпозиция исходной таблицы на множество таблиц для каждого атрибута

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

Исследование данной задачи, в случае положительных результатов, ляжет в основу создания интегрированных в PostgreSQL методов вертикального хранения (и доступа) данных, которые будут эффективны на сверхбольших объемах научных (в частности - астрономических) данных.

4.4. Ожидаемые в конце 2009 года научные результаты:

К концу 2009 года будут получены следующие результаты:

- будут созданы и имплементированы алгоритмы работы с Index Organized Tables в PostgreSQL;

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

- будет реализована схема с отложенным обновлением обратного индекса GIN.

- будет разработан и реализован алгоритм частичного поиска в GIN-индексе.

- будут созданы и реализованы методы работы с композитным GIN-индексом.

- будет проведено исследование возможности построения и использования быстрой приближенной статистики на основе индексов GiST и GIN. При положительном результате исследования (если окажется, что выигрыш достигается в значительном числе реальных случаев), данная технология будет реализована.

- на основе композитных GIN-индексов будут созданы модули для индексирования скалярных атрибутов.

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

- для модуля работы с триграммами (pg_trgm) будет реализована поддержка кодировки UTF-8.

Все разработанные реализации будут интегрированы в СУБД PostgreSQL и сделаны публично доступными.

4.5. Современное состояние исследований в данной области науки, сравнение ожидаемых результатов с мировым уровнем:

В настоящее время в интернете появилось много дискуссий о кризисе традиционных СУБД, которые не удовлетворяют новым требованиям. Это обусловлено следующими факторами:

  • Много данных - порог петабайтных БД преодолен, архивы в сотни терабайт становятся привычными. Современные научные эксперименты из разряда "большой науки" сталкиваются с необходимостью работы с беспрецендентными объемами данных, на грани возможностей, которые предоставляет компьютерная индустрия и информационные технологии. Развитие технологии производства сенсоров привело к лавинообразному увеличению данных (data deluge). Так, например, весь архив телескопа Хаббла,накопленный за 15 лет работы, занимает около 25 Тб, в то время как большой обзорный телескоп (LSST) c диаметром зеркала 8.4 метра и матрицей 3 гигапиксела будет производить 30 Тб данных только за одну ночь, а полный объем наблюдательного архива оценивается в 200 петабайт. Бизнес также сталкивается с проблемой хранения,обработки и анализа гигантских объемов данных. Термин "Big Data" появился как раз для описания ситуации, когда для работы с данными, объем которых превышает возможности доступных на данный момент технологических средств, требуется разработка специальных инструментов.
  • Современная наука оперирует произвольными данными в самых разных форматах - это могут быть табличные данные в СУБД, иерархические данные, документы, видео, изображения, аудио файлы,и так далее, что приводит к высокой сложности систем управления и обработки. Кроме того, появились новые запросы, которые выходят за рамки операций сравнения.
  • Большие научные эксперименты стали настолько сложны и дороги, что для их подготовки и проведения привлекаются многие страны и сотни организаций. Это приводит к необходимости обмена данными, использованию открытых стандартов и лицензий. Кроме того, существует необходимость исследовать и публиковать полученные данные в строго определенный срок для того, чтобы успеть подготовить и подать успешную заявку на следующий цикл исследований. Это приводит к предельной интенсификации изучения полученных данных и требует соответствующих инструментов для быстрого анализа и поиска данных.
  • Развитие приемных устройств требует очень сложной процедуры обработки данных, так что необходимо хранить "сырые данные" для возможной переобработки данных, что накладывает существенные требования на размеры хранилища для хранения всех возможных версий обработанных (научных) данных.
  • Скорость поступления данных может сильно меняться от редких массовых поступлений, до непрерывного потока данных. Гигантский радиотелескоп с суммарной площадью антенн 1 квадратный километр (SKA) , планирующийся к запуску в 2015 году, будет передавать сигналы с одной антенны со скоростью 160 Gb/s, что в 10 раз превышает весь нынешний интернет трафик. Ожидаемое количество получаемых сырых данных в день оценивается в 1 экзабайт!, которые будут сжиматься до 10 петабайт изображений для дальнейшего хранения. Для обработки данных в реальном времени необходимо 100 терафлоп. Анализ данных в науке пока не требует учета изменяемости данных, когда требуется принять решение на основе только что поступивших данных, как, например, на рынке ценных бумаг, тем более в условиях конкурентности (новый трансатлантический кабель будет введен в 2013 году специально для ускорения доступа к онлайне торговле на 6 милисекунд, что требует инвестиций в 300 млн долларов).
  • Клиенты стали другими - раньше были операторы, сейчас в основном это бездушные клиенты, большой уровень конкурентности. Машины стали основными производителями информации и ее потребителями, поэтому требуется обеcпечить прежде всего не интерактивную работу с данными, а программный доступ к ним, чтобы можно было автоматизировать рутинные работы обработки наблюдений, поиска данных, чтобы машины могли работать с машинами. Автоматизация работы с данными привносит много трудностей, в первую очередь, связанные с необходимостью стандартизации описания данных (метаданных) и их форматов. Сенсоры, по своей физической природе, генерят данные с некоторой ошибкой, а гигантские сенсорные сети уже сейчас производят "цунами данных", которые надо не только уметь хранить, но и обрабатывать, а затем делать выводы, принимать решения и все это с учетом "неточности". Неточные данные (данные с погрешностями) являются сейчас большой проблемой в задаче организации межмашинного взаимодействия.
  • "Железо" стало дешевым - нужны новые алгоритмы, ориентированные на использование памяти и большого количество дешевых компьютеров. Существенно стали дешевле хранилища данных с гарантированным резервированием как по дискам, так и по питанию. Хранение данных на сегодняшний момент не является проблемой "Big Data", и, скорее всего, не будет таковой и в будущем, так как технология производства сенсоров (сенсоры и сенсорные сети являются основным источником данных) и компьютерная индустрия довольно хорошо следуют одному и тому же закону Мура. Недавно, IBM объявило о создании хранилища данных, размером 120 петабайт (200,000 жестких дисков !) для задачи предсказания погоды, в особенности, ураганов.

В каких направлениях идет развитие СУБД, чтобы отвечать новым требованиям?

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

Осознание этих изменений в науке и бизнесе привело к пониманию новой архитектуры информационных систем, которая призвана справиться с этими "цунами данных". В первую очередь, это должен быть кластер независимых многоядерных компьютеров, имеющих собственные диски, соединенные быстрой сетью, на котором установлена СУБД, ориентированная на работу с распределенными очень большими данными и параллельную обработку. Гигантские объемы данных делают старый способ обработки данных на суперкомпьютерных кластерах, когда данные из хранилища копируются в большой вычислительный кластер, экономически невыгодным и неэффективным. Алгоритмы работы с данными должны уметь работать не требуя дополнительного дискового пространства и быть устойчивыми к сбоям системы. Уже сейчас существуют решения, реализующие в том или ином виде такую архитектуру, например, система "GrayWulf", или открытый проект по созданию новой СУБД для науки SciDB, и конечно, решения, основанные на Hadoop - открытой реализации MapReduce, программной инфраструктуры для разработки систем, ориентированных на распределенную обработку больших массивов данных.

Видный участник DB-сообщества Майкл Стоунбрейкер, все это являются полумерами и требуется кардинальные изменения в технологии СУБД, а именно - изменение принципа хранения данных. Он считает, что эра обычных больших СУБД общего назначения прошла (http://www.databasecolumn.com/2007/09/one-size-fits-all.html) и требуется совершенно новые подходы для создания современной БД, которая с самого начала будет ориентирована на распределенность, параллельное исполнение запросов, компрессию, ориентацию на хранение по атрибутам, высокую доступность, линейное масштабирование с использование кластеров независимых серверов.

Научное сообщество на ежегодных совещаниях по сверхбольшим базам данных (XLDB) выработало основные требования к базе данных для Большой Науки:

  • открытая модель развития - гарантирует независимость от вендора и защиту инвестиций, а также способствует привлечению разработчиков.
  • отказ от строгого соблюдения ACID, хранилище оптимизированое в основном на чтение, загрузка данных только большими порциями (bulk load), многомерные массивы как основная структура данных
  • масштабируемость на сотни петабайт, при этом SciDB должна работать как на ноутбуке, так и на кластере в тысячи серверов. Минимизация административных затрат на поддержание работоспособности кластера.
  • интерфейсы к научным приложениям, таким как R, MATLAB, IDL, к языкам программирования (C++, Python)
  • Поддержка версионности данных, отслеживание источников данных, поддержка данных с ошибками

Однако, несмотря на всю активность в новых направлениях, которая вероятнее всего приведет к революции в СУБД, уже сегодня существует необходимость работы с тера/пета БД с требованиями транзакционности, масштабирования и поддержки богатого набора запросов и всего того набора сервисов, предоставляемые реляционными БД. Поэтому важной задачей является исследование проблем в алгоритмах и структурах данных современных БД и их улучшение. С другой стороны, анализ существующих прототипов новых БД, преимуществ и проблем, необходим для понимания будущих направлений развития СУБД PostgreSQL, которая несомненно является лучшим кандидатом среди открытых СУБД для таких работ. Это особенно важно так как закрытость многих разработок, рекламный характер публикаций, ограниченность практических примеров использования, зачастую мешает пониманию реальных преимуществ, принципиальных проблем и недоработок.

Для исследований проблемы неточных данных мы также предполагаем использовать PostgreSQL, так как считаем, что это позволит нам не только быстро начать разработку, но и использовать разработанные методы в реальных проектах, которые уже использует PostgreSQL, в отличие от реализации в сторонних СУБД, которые хотя и ориентированы на неточные данные, но обладают более слабым функционалом.

Почему выбрана СУБД PostgreSQL?

  • Лицензия BSD, либеральная
  • Многоплатформенность - Unix, Windows, MacOSX,
  • Большое устойчивое сообщество, не принадлежит никакой компании - защищенность инвестиций
  • Долгая история, возникла в Беркли как научный проект, оказал большое влияение на развитие СУБД (http://www.sai.msu.su/~megera/postgres/talks/what_is_postgresql.html)
  • Производные СУБД - это лидеры инноваций - либеральная лицензия, модульность, богатый набор возможностей - PostgreSQL Plus Cloud Edition - поддержка расширяемости через Cloud Computing (Amazon веб-сервисы, http://www.enterprisedb.com/community/blades/elastra.do) - GreenPlum (http://www.greenplum.com/) - параллельное исполнение запросов, поддержка технологии MapReduce. - AsterData (http://www.asterdata.com/) - паралелльное исполнение запросов, поддержка технологии MapReduce - Yahoo Everest - PostgreSQL с вертикальных хранилищем (см. ниже) - TelegraphCQ (http://telegraph.cs.berkeley.edu/telegraphcq/) - потоковая СУБД, его коммерческая версия - StreamBase
  • Расширяемость - возможность создания новых типов данных, новых запросов, эффективных (индексная поддержка) предметными специалистами, а не разработчиками ядра СУБД. Неполный список расширений: - Blastgres (http://sourceforge.net/projects/blastgres) - расширение для эффективной работы с биологическими последовательностями. - PostGIS (www.postgis.org) - поддержка геоданных. - Owlgres (http://pellet.owldl.com/owlgres) - семантическое расширение PostgreSQL.

Кроме того, наша группа на протяжении почти 10 лет принимает активное участие в разработке PostgreSQL и использует его в разных проектах. В частности, мы занимаемся разработкой и поддержкой инфраструктуры расширяемости PostgreSQL (GiST, GIN), которая позволяет создавать пользовательские типы данных и запросы, нами разработан полнотекстовый поиск в PostgreSQL и некоторые другие расширения для эффективной работы с множествами.

Таким образом, не отрицая необходимость разработки новой БД для Большой науки, на что потребуется немалое количество лет, мы придерживаемся точки зрения, что необходимо проанализировать современный PostgreSQL для выявления возможных препятствий (bottleneck) в алгоритмах и структурах, изучить опыт сторонних компаний, которые добавили атрибутно-ориентированное хранилище (Yahoo Everest), параллельное исполнение запросов (Greenplum, AsterData). Мы планируем продолжать наши работы по развитию и улучшению расширяемости PostgreSQL, на основе которой будут реализованы новые расширения, тестирование и апробация которых предполагается на сайте Астронет, на котором есть возможность тестирования как на очень больших базах астрономических данных, так и на коллекции полнотекстовых документов. Результаты работ будут доложены на ежегодных конференциях разработчиков PostgreSQL и после дополнительного тестирования часть из них войдет в будущие версии PostgreSQL, тем самым они станут доступными большому количеству пользователей. Учитывая такие факторы, как широкое использование PostgreSQL в науке, его доступность, богатый набор возможностей, а также совместимость с коммерческими вариантами (для которых существует большое число научных приложений, т.е. должна обеспечиваться преемственность и возможность миграции), мы верим в его применимость как универсального хранилища для научных баз данных. В частности, мы планируем уже в рамках этого проекта начать работы по созданию сверхбольшого хранилища для космического проекта астрономического обзора неба совместно с РКК Энергия.

4.6. Имеющийся у коллектива научный задел по предлагаемому проекту; полученные ранее результаты, разработанные методы: Предлагаемый проект является прямым развитием направления работ по исследованию методов поиска в массивах слабо структурированной информации. Авторы проекта активно работают в этой области еще с 1998-1999 года. Результатом этих работ является, в частности, создание поисковой технологической основы для информационной системы Астронет (www.astronet.ru), поиска по астрономическим сайтам России (http://astronet.ru/db/astrosearch/), поиска по сайтам МГУ (http://astronet.ru/db/msusearch/). Созданные технологии применялись также в целом ряде других проектов, таких как контентная часть портала Рамблер, в Федеральной системе образовательных порталов, и многих других.

Кроме того, с самого начала все работы в данном направлении ведутся в рамках Оpen Source (и, в частности, в рамках развития свободно распространяемой СУБД PostgreSQL). Некоторые из авторов проекта являются членами core team разработчиков PostgreSQL. Это обеспечило широкое распространение и востребованность всех полученных результатов практически во всем мире. Отметим, что ключевые технологии PostgreSQL для работы со слабо структурированными данными - это индексы GiST и GIN (Generalized Search Tree и Generalized Inverted Index) также являются в значительной степени (а GIN - полностью) результатом работ авторов проекта в данной области. И дальнейшее развитие и обобщение этих методов и технологий является ключевой предпосылкой для успешного выполнения предлагаемого проекта.

Работы в этом направлении были поддержаны целым рядом научных фондов и коммерческих фирм, а также грантами РФФИ 99-07-90069-в, 03-07-90187-в, 05-07-90225-в, 06-07-89182-а, 09-07-00471-а.

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

Основным научным заделом для предлагаемого проекта является большая группа поисковых методов и алгоритмов для работы со слабо структурированной информацией, уже реализованными авторами в рамках проекта Астронет (astronet.ru), в рамках пилотных работ по созданию коллекции больших астрономических каталогов (vo.astronet.ru) и специфических методов поиска по этим каталогам (например, ConeSearch и CrossMatch). Одно только перечисление всех этих методов является достаточно объемным, поэтому здесь мы сошлемся, в первую очередь, на отчеты по гранту 06-07-89182-а (там содержится полный список), и на финальный отчет по гранту 05-07-90225-в (где описаны поисковые методы, специфичные для астрономических данных).

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

Для предлагаемого проекта такой тестовой площадкой будет являться объединенная астрономическая информационная система, создание которой планируется на основе интеграции проекта Астронет и хранилища массивных астрономических данных (гду уже сейчас содержится свыше 15TB данных, а в ближайшие три года этот объем превысит 100TB). Методы и алгоритмы работы со сверхбольшими объемами данных будут практически "обкатываться" именно на упомянутом интеграционном проекте, а результаты предлагаемого проекта во многом составят технологическую поисковую основу для будущего Астронет (как интегрированной информационной системы, объединяющей все типы астрономических данных - как текстовые, так и экспериментальные).

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