Стратегия размещения данных в многопроцессорных системах с симметричной иерархической архитектурой[*] (стр. 4 )

.

По теореме 1 из формулы получаем

.

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

Теорема доказана.

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

Теорема 4. Пусть T ‑ регулярное DM‑дерево высоты . Пусть фрагмент располагается на диске . Обозначим степень уровня l дерева T как . Обозначим ‑ суммарная трудоемкость покортежного формирования всех реплик фрагмента без учета помех. Тогда

.

Доказательство. Доказательство проведем индукцией по высоте H дерева T.

Пусть . Тогда число дисков в дереве T равно . В соответствии с теоремой 3 трудоемкость покортежного формирования любой реплики фрагмента в этом случае имеет следующую оценку:

.

Следовательно, суммарная трудоемкость покортежного формирования всех реплик фрагмента без учета помех может быть оценена следующим образом:

,

что согласуется с формулой при .

Пусть . Тогда дерево T содержит поддеревьев высоты :

.

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

.

Без ограничения общности мы можем считать, что . Тогда в силу симметричности дерева T из получаем

.

В соответствии с теоремой 3 для любой реплики , располагающаяся в поддереве , имеем

.

В силу симметричности дерева T, суммарное количество дисков в поддереве равно . Учитывая этот факт, из получаем

.

С другой стороны, по предположению индукции имеем

.

Подставляя в значения правых частей из и, имеем

Теорема доказана.

Определим рекурсивно нормальную функцию репликации следующим образом:

9.  1) для :

10.  2) для :

Справедлива следующая теорема.

Теорема 5. Пусть T ‑ регулярное DM‑дерево высоты . Пусть ‑ множество фрагментов, составляющих базу данных. Пусть ‑ множество всех реплик всех фрагментов из множества , построенных с использованием нормальной функции репликации. Пусть ‑ размер базы данных в кортежах (здесь мы предполагаем, что все кортежи имеют одинаковую длину в байтах). ‑ суммарная трудоемкость покортежного формирования всех реплик без учета помех. Тогда

,

где k ‑ некоторая константа, не зависящая от .

Доказательство теоремы непосредственно следует из теоремы 4 и определения нормальной функции репликации.

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

5. Заключение

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

В качестве основных направлений дальнейших исследований можно выделить следующие. Во-первых, это ‑ аналитическое получение оценок трудоемкости обновления реплик с учетом помех. Во-вторых, мы планируем на баз DM‑модели разработать программу, моделирующую работу иерархической многопроцессорной системы баз данных, и провести с ее помощью эксперименты по исследованию проблем распределения данных и балансировки загрузки. В-третьих, мы предполагаем реализовать описанные методы и алгоритмы в прототипе параллельной СУБД Омега [12] для кластеров и Grid‑систем.

Литература[Л. Б.11] 

1[Л. Б.12] [Л. Б.13] . Обзор архитектур параллельных систем баз данных // Программирование. ‑2004. ‑№ 6. С. 49‑63.

2. Foster I. T., Grossman R. L.[Л. Б.14]  Blueprint for the future of high-performance networking: Data integration in a bandwidth-rich world // Communications of the ACM. -2003. - Vol. 46, No. 11. - P. 50-57.

3. Bitton D., Gray J. Disk Shadowing // Fourteenth International Conference on Very Large Data Bases, August 29 ‑ September 1, 1988, Los Angeles, California, USA, Proceedings. Morgan Kaufmann. ‑1988. ‑P. 331-338.

4. Chen S., Towsley D. F. Performance of a Mirrored Disk in a Real-Time Transaction System // 1991 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, San Diego, California, USA, May 21-24, 1991, Proceedings. Performance Evaluation Review. ‑May 1991. ‑Vol. 19, No. 1. ‑P. 198-207.

5. Mehta M., DeWitt D. J. Data Placement in Shared-Nothing Parallel Database Systems // The VLDB Journal. ‑January 1997. ‑Vol. 6, No. 1. ‑P. 53-72.

6. Williams M. H., Zhou S. Data Placement in Parallel Database Systems // Parallel database techniques / IEEE Computer society. ‑1998. ‑P. 203-218.

7. , Моделирование иерархических архитектур параллельных систем баз данных // Научный сервис в сети Интернет: технологии распределенных вычислений: Труды Всероссийск. науч. конф. (19-24 сентября 2005 г., г. Новороссийск). ‑М.: Изд-во МГУ. ‑2005. ‑C. 21-24.

8. Искусство программирования, т. 1. Основные алгоритмы, 3-е изд. ‑М.: Издательский дом "Вильямс", 2000. ‑720 с.

9. Lu H., Tan K.-L. Dynamic and Load-balanced Task-Oriented Database Query Processing in Parallel Systems // Advances in Database Technology ‑ EDBT'92, 3rd Int. Conf. on Extending Database Technology, Vienna, Austria, March 23-27, 1992, Proceedings. Lect. Not. in Comp. Sc., Vol. 580. Springer. ‑1992. ‑P. 357-372.

10. Omiecinski E. Performance Analysis of a Load Balancing Hash-Join Algorithm for a Shared Memory Multiprocessor // 17th International Conference on Very Large Data Bases, September 3-6, 1991, Barcelona, Catalonia, Spain, Proceedings. Morgan Kaufmann. ‑1991. ‑P. 375-385.

11. Организация параллельного выполнения запросов в многопроцессорной машине баз данных с иерархической архитектурой // Программирование. ‑2001. -№6. - C. 13-29.

12. Прототип параллельной СУБД Омега [http://su. ru/prototype/].

[*] Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований
(проект 06-07-89148).

[†] Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований
(проект 06-07-89148).

 [Л. Б.1]Нумерация заголовков уровня 1 выполняется путем вставки поля {LISTNUM "Заголовок" \l1}.

 [Л. Б.2]Ссылка на литературу реализуется путем вставки перекрестной ссылки на соответствующую библиографическую закладку (см. примечания к списку литературы).

 [Л. Б.3]Рисунок вместе с подписью следует помещать в таблицу из одной строки и одного столбца со свойствами: «Выравнивание ‑ по центру», «Обтекание ‑ нет».

 [Л. Б.4]Для нумерации подписей к рисункам необходимо в меню <Вставка/Ссылка/Название/Создать...> создать новое название <Рис.> (если оно не было создано ранее).

 [Л. Б.5]Нумерация рисунков выполняется с помощью команды меню <Вставка/Ссылка/Название...>, где необходимо выбрать подпись <Рис.>.

 [Л. Б.6]Ссылка на рисунок выполняется с помощью команды меню <Вставка/Ссылка/Перекрестная ссылка...>, где необходимо выбрать тип ссылки: <Рис.>.

 [Л. Б.7]Нумерация заголовков уровня 2 выполняется путем вставки поля {LISTNUM "Заголовок" \l2}.

 [Л. Б.8]На номер теоремы навешивается закладка, имя которой начинается с латинской буквы «T», например, ‑ «T_размер_реплики».

 [Л. Б.9]Теоремы нумеруются с помощью поля {LISTNUM "Теорема"}.

 [Л. Б.10]Ссылка на номер теоремы реализуется путем вставки перекрестной ссылки на соответствующую закладку.

 [Л. Б.11]Образцы оформления ссылок на разные виды публикаций можно найти на http://su. ru/asp/index. html

 [Л. Б.12]Элементы списка «Литература» необходимо нумеровать путем вставки поля {LISTNUM "Литература"}.

 [Л. Б.13]На номер необходимо навешивать закладку вида B_<шифр>. Шифр следует брать из библиографического каталога на http://su. ac. ru/bibl/. Например: B_Соколинский_04. При этом пробелы в шифре следует заменять подчерком. Первая буква «B» должна быть английской. Она необходима для того, чтобы в общем списке закладок легко находить «библиографические» закладки.

 [Л. Б.14]Фамилии и инициалы авторов следует выделять курсивом.