Проектирование программно-аппаратных комплексов для массовой обработки данных в экономических информационных системах

Проектирование программно-аппаратных комплексов для массовой обработки данных в экономических информационных системах

к.т.н., доцент В.И. Мунерман

Ключевые слова: Big Data, модели данных, параллельное программирование.

Часть экспериментальных результатов получена в рамках грантов, предоставленных Смоленскому государственному университету корпорацией Microsoft.

В статье рассматривается проблема оптимизации массовой обработки структурированных больших данных (МОД). Традиционно МОД широко используется для решения многих задач в различных предметных областях в тех случаях, когда в вычисления включается значительная часть содержащихся в базе данных. К числу таких задач в экономике относятся: оперативная статистическая обработка данных, задача «Операционный день банка», ежедневные задачи учета и планирования производства в современных системах управления (стандарты ERP [13]), задачи статистического анализа и синтеза подсистем послепродажного обслуживания в системах интегрированной логистической поддержки наукоемкой продукции [11].

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

Массовая обработка данных: основные понятия. Традиционно массовую обработку данных связывают с параллельными вычислениями и чаще всего определяют следующим образом: массовая параллельная обработка -- способ параллельной обработки больших объемов данных большим числом процессоров. В настоящее время массовую обработку данных связывают с направлением, получившим название Big Data. Big Data (большие данные) -- общий термин, который обозначает структурированные, неструктурированные и полуструктурированные данные сверхбольших и постоянно возрастающих объемов, вновь создающиеся в процессе решения задач. Загрузка таких данных в обычную (например, реляционную) базу данных и последующая обработка требуют больших затрат ресурсов вычислительных комплексов [12]. Далее рассматривается один из классов массовой обработки -- обработка структурированных данных. При этом ставится задача повышения производительности вычислительных средств без использования специфического (и, как правило, дорогостоящего) программного и аппаратного обеспечения. Предполагается, что используемые и обрабатываемые в задачах МОД данные хранятся в базах данных (БД) и обрабатываются системами управления базами данных (СУБД). Для повышения эффективности МОД используется теоретико-множественная (файловая) модель данных в качестве промежуточной между моделью вычислений и моделью данных уровня проектирования: реляционной, объектной или любой другой. Она обеспечивает наибольшее соответствие существующих моделей данных архитектурам вычислительных комплексов и позволяет на основе этих моделей и соответствующих им СУБД разработать способы организации данных во внешней памяти и алгоритмы реализации операций, в наибольшей степени соответствующих структурам данных и архитектурам вычислительных комплексов. Файловая модель основана на следующих предположениях:

1. Данные хранятся в базе данных (БД) и управляются системой управления базами данных (СУБД).

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

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

4. Время выборки данных из базы в файл минимально (на практике оно определяется свойствами СУБД).

Реализация МОД осуществляется посредством обработки файлов специальным набором операций. В этот набор, который не меняется с конца 50-х гг. ХХ в. до настоящего времени, входят следующие операции:

1) сортировка. В реляционной модели данных нет явной операции сортировки, но в языке SQL есть возможность упорядочить результат запроса;

2) выборка. В реляционной модели ей соответствует операция SELECT;

3) сжатие. В реляционной модели этой операции соответствует операция PROJECT, которая реализуется в языке SQL возможностью выборки не всех полей отношения и применения операции GROUP BY;

4) слияние строго упорядоченных файлов. На самом деле это не одна операция, а класс операций, соответствующих классу теоретико-множественных операций в реляционной модели;

5) слияние нестрого упорядоченных файлов. В реляционной модели этой операции соответствует операция естественного соединения (JOIN).

Для обеспечения эффективности реализации задач МОД необходима возможность параллельной обработки структурированных и высокоактивных данных. Эффективные методы параллельной реализации задачи МОД могут быть реализованы не только в рамках файловых систем [3], но и средствами любых СУБД. При этом модель данных, на которой основана СУБД (реляционная, объектная, SQL, NoSQL), не имеет принципиального значения. Однако эти модели не учитывают основные факторы, определяющие эффективность МОД: структурированность и активность данных. Они разрабатывались как универсальные модели, пригодные для решения любых классов задач обработки данных. Но проблемы распараллеливания данных и оптимизации запросов неотделимы от знания структуры данных и оценки вычислительной сложности алгоритмов, которая определяется величиной входного потока [1]. Поэтому невозможно разработать общие методы распараллеливания и оптимизации обработки, которые бы позволяли одинаково хорошо оптимизировать обработку данных для всех возможных классов задач. Решение этих проблем возможно при применении файловой модели [4, 5, 7, 8].

Формальное описание теоретико-множественной (файловой) модели. Пусть Л = [Л_р ..., Л_р} некоторая конечная система конечных множеств, а N = {Л^,N} конечное множество элементов, назы

ваемых именами множеств Л,, ..., Л . Множества Л,, ..., Л могут состоять из элементов любой природы: чисел с фиксированной или плавающей точкой, строк, а также таких структур, как массивы или кортежи (записи). На множествах Л₁, ..., Л_р могут быть заданы операции и отношения, тогда Л₁, ..., Л_р называются типами. Полем записи называется пара F = <Ж, Л₁ > (/ = 1, ..., р). N -- имя, а Л₁ -- множество значений поля. Кортеж Я = ^, ..., F_p} называется записью типа Я. Кортеж вида Я * = {< N_l, А* >,..., < N, Ар >} (А* е А₁, г = 1,..., р) называется экземпляром записи типа Я.

Множество X экземпляров записей типа Я называется множеством записей типа Я или множеством однотипных записей.

Пусть К = {К,...,К_т},(т < р) -- конечное множество полей записи Я, такое, что К₁ = Я,..., К_т = Я_а , причем все А_а (г = 1,..., т) -- типы, на которых заданы отношения порядка. Множество К называется множеством ключей, а его элементы ключами. Кортеж К * = {К*,..., К*_т}, для элементов которого выполняется правило К* е А_а (г = 1,...,т), называется экземпляром множества ключей (К* называется экземпляром ключа).

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

Две однотипные записи называются эквивалентными, если они содержат одинаковые экземпляры множества ключей. Задание множества ключей К разбивает множество однотипных записей X на классы эквивалентности, содержащие записи с одинаковыми значениями ключей -- эквивалентные записи. Совокупность всех классов эквивалентности по отношению, заданному множеством ключей, образует фактор-множество множества однотипных записей X. Такое фактормножество обозначается X_K, составляющие его классы эквивалентности -- X ,, или X , ,X , .... Если некоторому экземпляру множества ^КК(1) ^К(2)

ключей во множестве X не соответствует ни одной записи, считается, что ему соответствует универсальная неопределенная запись ©. Класс эквивалентности, соответствующий экземпляру множества ключей К и состоящий из единственной записи ©, будет обозначаться ©_К*

Файлом X_K называется фактор-множество множества однотипных записей X по отношению к эквивалентности, порожденной множеством К. При таком подходе файл не может быть неупорядоченным. Если каждый класс эквивалентности файла X_K содержит единственную запись, то файл X_K называется строго упорядоченным, если же в каждом классе эквивалентности может быть более одной записи -- нестрого упорядоченным. В этих терминах можно задать теоретикомножественные описания операций над файлами.

Сортировка (sort). Выполнение операции сортировки приводит к построению из исходного множества однотипных записей X файла X_K (фактор-множества X по заданному множеству ключей K). Практические соображения требуют, чтобы для любого множества X можно было подобрать такое множество ключей K, по которому файл X_K будет строго упорядоченным. оптимизация обработка данные программный

Выборка (sel). Пусть даны файл X_K и n(K) предикат, определенный на множестве ключей K. Операция выборки приводит к созданию файла XK , удовлетворяющего следующим условиям: XK з X_K, т.е. файл XK есть подмножество файла X_K; УК*(X_K, е XK л п(К *)) ,т.е. класс эквивалентности X_R. присутствует в файле X” тогда и только тогда, когда все значения ключей в экземпляре множества ключей K* превращают предикат n(K) в истинное высказывание.

Сжатие (quant). Пусть даны файлы X_K, нестрого упорядоченный по множеству ключей K, и Y_K, строго упорядоченный по множеству ключей K. Классы эквивалентности этих файлов связаны соотношением Y_K. = f ( X_к, ), где f -- функция, реализующая групповую операцию (операцию квантификации). Тогда считается, что файл Y_K получен из файла X_K в результате применения операции сжатия.

Слияние строго упорядоченных файлов (ms). Пусть даны два файла X_K и Y_K, строго упорядоченные по одному и тому же множеству ключей K. В результате слияния этих строго упорядоченных файлов образуется файл Z_K, классы эквивалентности задаются соотношением Z. = f (X ,,Y.). Функция f (X„,,Y.), определенная на классах эквивалентности исходных файлов, задает характер операции. В задачах массовой обработки данных построение функции f может быть следующим:

g_x(Y_K.), если* =©k*

g₂( ^Xk *⁾,^{если Y}k * =®k *

ft( ^XK `Y *)'ЄСЛИ ^XK - *®K *Y_K * *®K **

Функции g_v g₂, g₃ реализуют формирование записи выходного файла с вычислением новых значений неключевых полей, из значений неключевых полей записей Х_к. и Y_K,. Значения ключей все три функции переносят в выходную запись Х_к, без изменений.

Слияние нестрого упорядоченных файлов (mns). Пусть X_K и Y_L -- файлы, упорядоченные (возможно строго) по множествам ключей K и L, причем выполняется условие K n L ф 0, и пусть М -- множество ключей, связанное с множествами K и L соотношениями: М з K u L, М n K ф 0 и М n L ф 0. Это означает, что по крайней мере один файл Х_М , Y_M нестрого упорядочен по множеству ключей М. Слияние файлов производится по множеству ключей М. Класс эквивалентности файла 2_М вычисляется по следующему правилу:

Г©..., если X , =© . или Y , =©,

Z J MM MM M

^M 1 f (X_M* ,Y. ) в противном случае.

Функция f (X_R, ,Y_l, ) определена на классах эквивалентности X_R, и Y* , а ее значение -- класс эквивалентности Z_M , состоящий из элементов, каждый из которых вычисляется из пары элементов, принадлежащих декартову произведению X_R, х Y_l, .

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

Программно-аппаратная реализация МОД. Файловая модель позволяет использовать для параллельной реализации задач МОД потоковую модель вычислений на основе архитектуры вычислительных систем с ассоциативным распределением ресурсов.

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

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

Таким образом, в задачах МОД можно выделить две основные цели оптимизации: ускорение отдельных операций обработки одного или нескольких файлов и построение оптимальных последовательностей операций (процессов или запросов) для решения конкретных задач.

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

Рис. 1. Конвейерный вычислительный комплекс для вычисления цепочки операций JOIN

При использовании файловой модели необходимо реализовать распределение данных между памятью вычислителей. В [6] предложен способ распределения файлов, который называется симметричным горизонтальным распределением данных, а для его реализации -- эвристический алгоритм, названный алгоритмом бустрофедона. В терминах файловой модели данных алгебраической моделью процесса МОД служит алгебраическое выражение вида А = Е (А₁, ..., А_и), правая часть которого состоит из файлов А₁, ..., А_и, соединенных знаками операций над файлами, а левая -- из выходного файла. Далее рассматриваются только аддитивная операция слияния строго упорядоченных файлов и мультипликативная операция слияния нестрого упорядоченных файлов. Тогда правая часть алгебраического выражения Е (А₁, ..., А_и) может быть сведена к «сумме произведений» исходных файлов. В реляционной модели данных

операции слияния нестрого упорядоченных файлов соответствует операция JOIN, поэтому в дальнейшем будет применяться это имя операции. Далее рассмотрено создание вычислительного комплекса для параллельного вычисления цепочки «произведений» файлов. Для этого можно использовать конвейерную архитектуру (рис. 1). Этот комплекс состоит из p /о/я-процессоров, первый из которых начинает обработку первых двух «сомножителей». Как только готов очередной фрагмент (один или несколько классов эквивалентности) файла-результата, он передается следующему /о/я-процессору, который обрабатывает этот фрагмент с соответствующим классом эквивалентности файла A , и так далее по конвейеру. Последний /о/я-процессор конвейера принимает классы эквивалентности файла, полученного в результате предыдущих произведений, и обрабатывает их с соответствующими классами эквивалентности последнего файла в цепочке.

Среди операций МОД операция JOIN имеет наибольшую вычислительную сложность. На основе файловой модели Join-процессор можно организовать как вычислительный комплекс на основе SIMD- архитектуры (рис. 2). Фрагменты файлов-операндов, обрабатываемых /-м фрагмент-процессором, можно рассматривать как совокупность пар G_n, ..., G_p, каждая из которых содержит два соответствующих друг другу класса эквивалентности файлов-операндов. Размещение данных в памяти фрагмент-процессоров производится на основе принципа симметричного горизонтального распределения.

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

При таком сочетании конвейерной и SIMD-архитектур вычислительных комплексов можно добиться значительного повышения эффективности процессов МОД.

Рис. 2. SIMD-архитектура /ог'я-процессора

Для проверки предложенных методов повышения эффективности МОД проведен ряд вычислительных экспериментов [9, 10], в которых на основе теоретико-множественной и многомерно-матричной моделей были построены программно-аппаратные комплексы с различными архитектурами:

1) симметричное мультипроцессирование (SMP) на основе рабочей станции с четырехъядерным процессором Intel Core i7 (с технологией Hyper Threading);

2) массово-параллельная архитектура на основе локальной вычислительной сети с однотипными рабочими станциями;

3) массово-параллельная архитектура на основе облачной системы Windows Azure c распределением вычислений между виртуальными машинами и отдельными базами данных.

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

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

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

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

3. Сокращение времени решения задач повышает степень актуальности информации, что особенно важно при работе с большими данными.

Литература