astronet2009

Идеи для гранта РФФИ на 2009-2011 гг.

Проблемы хранения очень больших научных баз данных

• Много данных - порог петабайтных БД преодолен, сотни террабайт архивы становятся привычным. Yahoo (2008) анонсировала >2Pb online (PostgreSQL+vertical) хранилище - ComputerWorld - May 22, 2008,http://www.computerworld.com/action/article.do?command=viewArticleBasic&taxonomyId=18&articleId=9087918&intsrc=hm_topic - Size matters: Yahoo claims 2-petabyte database is world's biggest, busiest” (Computerworld)
  • Largest table: “multiple trillions of rows”
  • “The 2 Pb database requires fewer than 1,000 PC servers”
• Новые типы данных, новые виды запросов
• Глобализация науки → децентрализация хранилищ
• программный доступ к данным становится преобладающим
• Требование масштабирования хранилищ с использованием "commodity" оборудования
• Традиционные СУБД не обеспечивают всего этого, требуются внешние надстройки

Развитие СУБД идет в нескольких направлениях:

• Создание специализированных БД, например, для работы с потоками данных (StreamDB)
• БД для работы с данными вида (ключ,значение) - этo Google BigTable, Amazon SimpleDB, HyperTable. Намеренная простота таких БД компенсируется великолепной масштабированностью как по дисковому хранилищу, так и по процессорам.
• Поддержка обычными RDBMS распределенности и параллельности в архитектуре shared-nothing (кластер с полностью независимыми commodity серверами):
  • Немодифицированная БД, внешний контроллер
  • Модифицированное ядро - Greenplum (PostgreSQL) + MapReduce
• Использование СУБД в архитектуре Cloud Computing, которая предоставляет неограниченное масштабирование по требованию, например, EnterpriseDB предоставляет PostgreSQL Plus + Elastra.
• СУБД с атрибутно-ориентированным хранилищем, которое для некоторых задач лучше масштабируются. Примеры, Vertica, ParAccel,Exasol (comm), C-Store (open-source)
• Специализированные сервера с использование сопроцессоров (FPGA), например XtreemeData http://www.xtremedatainc.com/, модифицированный PostgreSQL, интегрированный в FPGA, для аналитических систем

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

Сообщества научное и разработчики СУБД решили взаимодействовать для создания новой SciDBMS для XLDB (http://en.wikipedia.org/wiki/XLDB). Несколько совещаний:

• 1st Workshop on Extremely Large Databases, SLAC, Oct. 2007, http://www-conf.slac.stanford.edu/xldb07/ - All of the industry representatives had more than 10 petabytes of data, and their largest individual systems were all at least 1 petabyte in size.
• SciDBMS Meeting, Asilomar, Apr. 2008, http://silicondetector.org/display/XLDB/xldb2 - SciDBMS must be able to scale to databases of hundreds of petabytes, with individual tables measured in trillions of rows

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

• Почему эта проблематика важна для нашей группы ? В ближайшие нескольких лет
  • вводится 2.5-метровый автоматический телескоп (около Кисловодска), ожидается большой поток наблюдательных данных
  • Космический обзор неба "Лира" с МКС, совместно с РосКосмос - ожидается 300-400 терабайт данных
  • Группа давно занимается разработкой PostgreSQL и сделала немало важных проектов - системы расширяемости GiST и GIN, полнотекстовый поиск, эффективная работа с массивами, хранение и работа с очень большими астрономическими каталогами (данные со сферическими атрибутами)
  • В рамках проекта "Астронет" реализован узел Виртуальной Обсерватории (vo.astronet.ru), который предоставляет интерактивный и программный доступ к терабайтным астрономическим БД

Алгоритмы и структуры данных очень больших СУБД и развитие архитектуры "Астронет"

• Протестировать все структуры в PostgreSQL и алгоритмы для использования в XLDB (петабайтные БД).
• Сравнение производительности вертикально-ориентированных БД с возможными реализациями на основе PostgreSQL:
  • index-only scan - все колонки проиндексированы, запрещен последовательный доступ к данным
  • декомпозиция таблицы на множество таблиц вида(PK, NPK) Вертикальные БД интересны для хранения "сырых" данных, где доступ к архивам осуществляется только по первичному ключу,а сами данные сериализованы в один бинарный атрибут.
• Исследование возможности применимости параллельных и распределенных БД для хранения очень больших научных БД на основе PostgreSQL - PostgreSQL Plus, Greenplum.
• Улучшение производительности при работе с большим количеством атрибутов переменной длины. Сейчас существует очень заметный оверхед, особенно заметный при массивной загрузки данных (100% cpu при загрузке SDSS каталога ~ 300 млн. записей с несколько сотнями колонок).
• IOT (Index Organized Tables) - индексно-организованная таблица (таблица с индексной организацией) . Индекс-таблица - это индекс, построенный по первичному ключу, который вместо ссылки на запись в таблице, содержит саму запись в листьях дерева. Иначе, данные сгруппированы по первичному ключу. Экономия IO и ,возможно, места.
• Алгоритмы оптимальной кластеризации бинарных сигнатур на диске для эффективного создания GiST индексов. Массивы → сигнатуры, текущий вариант - квадратичный алгоритм Гуттмана с использованием расстояния Хемминга. Недостаток - малое количество возможных уникальных расстояний (n+1), где n - это длина сигнатуры, как следствие - плохая селективность индекса.
• GIN для скалярных типов данных, построение GIN индекса по нескольким атрибутам
• UTF-8 для pg_trgm - расширение для триграмного поиска
• Быстрая приближенная статистика на основе индекса (GiST, GIN)
• Эффективная работа с RDF (тройки данных "объект - предикат - субъект") в PostgreSQL (в поддержку semantic web) - тип данных, методы доступа с индексной поддержкой, функциональный интерфейс.
• Phrase search - требуется разработка непротиворечивой алгебры поискового запроса с поддержкой логических операций (AND, OR, NOT, PAND) и группировки. Здесь PAND - это обозначение логической операции AND с ограничением по расстоянию между операндами. Основная трудность - поддержка произвольных словарей, которые могут превращать лексему в массив лексем, объединенных AND или OR.
• Fallback search
• Predictive search
• Тип данных для временных интервалов
• Расширение GiST API - добавление операций навигации по дереву
• Поиск ближайших соседей (KNN)
• Расширение инфраструктуры полнотекстового поиска в PostgreSQL для обеспечения более гибких настроек пользовательского поиска ( словари-фильтры, например).
• Реализация поисковых интерфейсов с подсказкой фраз на основе журнала запросов, материалов проекта "Астронет" как новый элемент навигации по сайту
• Подготовка экспериментальной онтологии астрономии на основе астрономического глоссария проекта Астронет - разметка в тексте с использованием микроформатов, экспериментальный интерфейс для поиска. Используем RDF для описания свойств ресурсов (объектов), а онтологию (OWL или другой способ) для описания связей между ресурсами (объектами).
• Эффективное склеивание астрономических изображений и их масштабирование