Параллельные системы баз данных

Серия
Суперкомпьютерное 
Образование

Координационный совет
Системы научно-образовательных центров
суперкомпьютерных технологий

Председатель Координационного совета
В. А.  Садовничий,
ректор МГУ имени М. В.  Ломоносова,
академик

Заместители председателя совета
Е. И.  Моисеев,
декан факультета вычислительной математики и кибернетики
МГУ имени М. В.  Ломоносова, 
академик

А. В.  Тихонравов,
директор Научно-исследовательского вычислительного центра
МГУ имени М. В.  Ломоносова, 
профессор

Члены совета

В. Н. Васильев, ректор Санкт-Пе тер  бургского национального исследовательского госу дар ственного университета инфор ма ционных технологий, механики 
и оптики, чл.-корр. РАН, профессор; В. Г. Захаревич, ректор Южного федерального университета, профессор; Н. Н. Кудрявцев, ректор Московского физико-технического института, чл.-корр. РАН, профессор; Г. В. Майер, 
ректор национального исследовательско го Томско го государственного университета, профессор; А. А. Фаткулин, проректор по науке и инновациям 
Дальневосточного федерального университета, профессор; Е. В. Чупрунов, 
ректор националь ного исследовательского Ниже городского го су дарственного 
университета, про фессор; А. Л. Шестаков, ректор национального исследовательского Южно- Уральского государственного университета, профессор; 
В. Н. Чубариков, декан механико-математического факультета МГУ имени 
М. В. Ломоносова, профессор; М. И. Панасюк, директор Научно-ис сле дова тельского института ядерной физики МГУ имени М. В.  Ломоно сова, профессор; Вл. В. Воеводин, заме ститель директора Научно-исследо ва тель ского 
вычислительного центра МГУ имени М. В.  Ломоносова, исполнительный директор 
НОЦ «СКТ-Центр», член-корреспондент РАН.

Издательство Московского университета
2013

Национальный исследовательский
Южно-Уральский государственный университет

Параллельные системы 
баз данных

Л.Б.Соколинский

Допущено 
УМО по классическому университетскому образованию 
в качестве учебного пособия для студентов высших учебных заведений, 
обучающихся по направлениям ВПО 
010400 «Прикладная математика и информатика» 
и 010300 «Фундаментальная информатика 
и информационные технологии»

© Соколинский Л. Б., 2012 
© Издательство Московского 
университета, 2012
ISBN 978-5-211-06482-9

Соколинский Л. Б. 
Параллельные системы баз данных: Учебное пособие / Предисл.: 
В. А. Садовничий. – М.: Издательство Московского университета, 
2013. – 184 с., илл. – (Серия «Суперкомпьютерное образование»)

ISBN 978-5-211-06482-9

С59

Цель учебного пособия состоит в изложении основ технологий параллельных систем баз данных. Особое внимание уделяется вопросам реализации 
СУБД для кластерных систем. Дается классификация известных форм параллельной обработки транзакций. Приводится сравнительный анализ различных архитектур параллельных систем баз данных. Рассматриваются возможные технологические подходы к организации параллельной обработки запросов. Обсуждается итерационная модель, синхронный и асинхронный 
конвейеры. Излагаются методы фрагментации данных и способы организации межпроцессорных обменов. Предлагается подход к автоматическому преобразованию последовательного плана выполнения запроса в параллельный. 
Большое внимание уделяется вопросам моделирования параллельных систем 
баз данных и организации эффективной буферизации в условиях использования фрагментного параллелизма.
Книга ориентирована на студентов, аспирантов и научных работников, специализирующихся в области разработки технологий параллельных систем 
баз данных и их применения для обработки сверхбольших объемов данных на 
современных многоядерных и многопроцессорных системах с кластерной архитектурой.
Ключевые слова: параллельные системы баз данных, фрагментный параллелизм, асинхронный конвейер, балансировка загрузки, моделирование параллельной обработки транзакций, алгоритм LFU-K.
УДК 007 (075) 
ББК 32.973.2

УДК 007 (075) 
ББК 32.973.2
С59

Уважаемый читатель!

Вы держите в руках одну из книг серии «Суперкомпьютерное образование», выпущенную в рамках реализации проекта комиссии 
Президента РФ по модернизации и технологическому развитию экономики России «Со здание системы подготовки высококвалифицированных кадров в области суперкомпьютерных технологий и специализированного 
программного 
обеспечения». 
Инициатором 
издания выступил Суперкомпью терный консорциум университетов 
России.
Серия включает более 20 учебников и учебных пособий, подготовленных ведущими отечественными специалистами в области 
супер компьютерных технологий. В книгах представлен ценный опыт 
преподавания супер компьютерных технологий в таких авторитетных вузах России, как МГУ, ННГУ, ТГУ, ЮУрГУ, СПбГУ ИТМО 
и многих других. При подготовке изданий были учтены рекомендации, сформулированные в Своде знаний и умений в области суперкомпьютерных технологий, подготовленном группой экспертов 
Суперкомпьютерного консорциума, а также международный опыт.
Современный уровень развития вычислительной техники и методов математического моделирования дает уникальную возможность 
для перевода промышленного производства и научных исследований на качественно новый этап. Эффективность такого перехода напрямую зависит от наличия достаточного числа высококвалифицированных специалистов. Данная серия книг предназначена для 
широкого круга студентов, аспирантов и специалистов, желающих 
изучить и практически использовать параллельные компьютерные 
системы для решения трудоемких вычислительных задач.

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

Ректор Московского университета,
Президент Суперкомпьютерного консорциума 
университетов России,
академик РАН  В. А. Садовничий

Оглавление

Введение ....................................................................................................

ЧАСТЬ I. АРХИТЕКТУРА ПАРАЛЛЕЛЬНЫХ СИСТЕМ БАЗ ДАННЫХ .....................................................................................................

Глава 1. Базисные концепции ...................................................................

§ 1.1. Введение в параллельную обработку запросов ........................
§ 1.2. Формы параллельной обработки транзакций ..........................
§ 1.3. Определение параллельной системы баз данных ....................

Глава 2. Классификация параллельных архитектур .................................

§ 2.1. Структурно-функциональная классификация ........................
§ 2.2. Виртуально-иерархическая классификация ............................

Глава 3. Требования к параллельной системе баз данных .........................

§ 3.1. Масштабируемость ....................................................................
§ 3.2. Производительность .................................................................
§ 3.3. Доступность данных ..................................................................
§ 3.4. Сравнительный анализ архитектур параллельных систем баз 
данных .......................................................................................

ЧАСТЬ II. ТЕХНОЛОГИИ ПАРАЛЛЕЛЬНЫХ СИСТЕМ БАЗ ДАННЫХ ........................................................................................................

Глава 4. Выполнение запросов ..................................................................

§ 4.1. Итераторы ..................................................................................
§ 4.2. Синхронный конвейер ..............................................................
§ 4.3. Асинхронный конвейер ............................................................

Глава 5. Распределение данных ................................................................

§ 5.1. Фрагментация данных ..............................................................
§ 5.2. Пересылка данных ....................................................................
§ 5.3. Оператор обмена exchange .........................................................

Глава 6. Модель параллельной системы баз данных ................................

§ 6.1. Определения из теории графов .................................................

9

13

15

15
21
27

33

34
37

45

45
47
52

53

57

59

59
61
75

81

81
86
89

94

94

Оглавление

§ 6.2. Модель аппаратной платформы ...............................................
§ 6.3. Модель операционной среды ....................................................
§ 6.4. Стоимостная модель ..................................................................
§ 6.5. Модель транзакций ....................................................................

Глава 7. Балансировка загрузки.................................................................

§ 7.1. Сегментация и репликация данных ..........................................
§ 7.2. Зеркалирование в симметричных DM-деревьях .......................
§ 7.3. Функция зеркалирования ..........................................................
§ 7.4. Алгоритм балансировки загрузки ..............................................

Глава 8. Буферизация в параллельных СУБД............................................

§ 8.1. Буферизация и замещение страниц ...........................................
§ 8.2. Требования к стратегии замещения ...........................................
§ 8.3. Стратегии LRU и LFU .................................................................
§ 8.4. Специальные стратегии замещения ..........................................
§ 8.5. Общие стратегии замещения .....................................................
§ 8.6. Алгоритм LFU-2 ..........................................................................
§ 8.7. Формальное описание стратегии LFU-K ...................................
§ 8.8. Аналитическая оценка параметра m алгоритма LFU-K ............
§ 8.9. Реализация алгоритма LFU-K ....................................................

Литература ................................................................................................

Предметный указатель ..............................................................................

95
103
106
107

115

115
117
122
128

132

132
134
140
142
145
155
157
160
170

175

177

Введение

Комплекс сложных научно-технических проблем, связанных 
с созданием высокопроизводительных и надежных систем баз 
данных, в условиях перехода общества от индустриальной эры 
к информационной не только сохраняет, но и усиливает свою 
актуальность. Об этом свидетельствуют интенсивные научные 
исследования в области баз данных, проводимые в России и за 
рубежом.
В настоящее время системы управления базами данных 
(СУБД) используются практически во всех сферах человеческой 
деятельности, связанных с хранением и переработкой информации. Прогресс, достигнутый в области технологий баз данных, 
в значительной мере базируется на реляционной модели, предложенной Э. Коддом на рубеже 60–70-х годов ХХ века. За свою 
тридцатилетнюю историю реляционные СУБД прошли путь от 
научно-исследовательских прототипов, наиболее значительными 
из которых являются System R и Ingres, до коммерческих продуктов, способных хранить и обрабатывать терабайты информации. Однако научная и практическая деятельность человека 
выдвигает все новые масштабные задачи, требующие обработки 
сверхбольших баз данных. Возникновение сверхбольших баз данных связано с расширением видов и сфер применения СУБД. 
Примерами приложений, характеризующихся сверхбольшим 
объемом хранимых данных, являются электронная коммерция, 
электронные библиотеки, геоинформационные системы, мультимедийные архивы, социальные сети, поисковые системы, 
научные базы данных и др.
Одной из самых больших и быстро наполняемых научных 
баз данных является база данных проекта WLCG (Worldwide 
Large Hadron Collider Computing Grid). Главной целью проекта 
WLCG является использование грид-среды для обработки экс

Введение

периментальных данных, получаемых с Большого адронного 
коллайдера (Large Hadron Collider, LHC) Европейского центра 
ядерных исследований (CERN). Поток экспериментальных 
данных, который необходимо обрабатывать, составляет около 
15 петабайт в год.
Другим примером сверхбольших баз данных являются базы 
данных, хранящие обзоры звездного неба, полученные различными телескопами мира. Так, например, база данных системы 
SkyServer проекта SDSS (Sloan Digital Sky Survey) хранит обзор 
одной четвертой части звездного неба, полученный с помощью 
2,5-метрового широкоугольного телескопа в Обсерватории 
Апачи-Пойнт, Нью-Мексико. Суммарный объем данных, накопленных к 2008 году в результате первой и второй фаз проекта, 
составил 40 терабайт. Третья фаза проекта SDSS, начатая в 2008 
году, предусматривает ввод в строй еще четырех телескопов. К 
моменту ее завершения в 2014 году общий объем данных, поставляемых телескопами, будет составлять несколько петабайт в год. 
Новая парадигма «синоптической», или временно-зависимой, 
астрономии реализуется в рамках проекта Pan-STARRS и LSST. 
Проект Pan-STARRS предусматривает строительство системы из 
четырех панорамных телескопов на вершине вулкана Мауна-Кеа 
на острове Гавайи. Этой системе телескопов будет доступно 3/4 
всего неба. Одна и та же область неба будет повторно сниматься 
с интервалом в несколько десятков минут. Основная задача – 
обнаружение объектов, меняющихся во времени. Примерами 
таких объектов служат сверхновые звезды или астероиды. После каждого сканирования будет получено несколько терабайт 
данных. К настоящему моменту запущен в эксплуатацию первый 
Pan-STARRS телескоп, который генерирует 2 терабайта данных за 
одну ночь, что составляет 800 терабайт в год. Второй Pan-STARRS 
телескоп планируется запустить в 2013 году. После запуска всех 
четырех телескопов, объем генерируемых данных составит около 
4 петабайт в год. Проект LSST (Large Synoptic Survey Telescope) 
предусматривает строительство в Чили широкоугольного об