В 1998 году на симпозиуме IEEE по высокопроизводительным распределенным вычислениям Вильям Джонсон представил доклад, в котором описывалась эволюция вычислений над большими объемами данных (Data-Intensive Computing) в предыдущие десять лет. Достижения, отмечавшиеся в докладе, соответствовали уровню технологий тех лет, но они производят скромное впечатление по сравнению с масштабом проблем, с которыми сегодня повседневно сталкиваются при разработке приложений, ориентированных на обработку больших объемов данных. Позднее в других публикациях описывалась масштабность проблем вычислений над данными большого объема. Требуется проведение исследований и разработок, направленных на создание масштабируемых аппаратных и программных решений проблем вычислений над данными большого объема.

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

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

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

Астрономия. Большой обзорный телескоп Large Synoptic Survey Telescope (www.lsst.org ) каждый год генерирует несколько петабайт новых изображений и каталожных данных. Радиотелескоп Square Kilometer Array ( www.skatelescope.org) будет производить около 200 Гбайт сырых данных в секунду, и для получения подробных радиокарт звездного неба потребуются вычислительные средства петафлопной (а может быть, и экзафлопной) производительности. Чтобы обработать такой объем данных и привести их к виду, полезному для научного сообщества, требуется решить ряд серьезных проблем.

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

Социальный компьютинг. На таких сайтах, как Internet Archive (www.archive.org ) и MySpace (www.myspace.com ), хранится контент огромного объема, которым необходимо управлять и обеспечивать возможности поиска и оперативной доставки результатов запросов. Разработка инфраструктуры и алгоритмов для сайтов такого масштаба представляет собой актуальную задачу.

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

Первая «регулярная» статья подборки, которую написали Йонг Ксю, Вей Ван, Ингджай Ли, Джай Гуанг, Линийан Бай, Инг Ванг и Джианвен Ай, называется «Количественная выборка геофизических параметров с использованием спутниковых данных» (Quantitative Retrieval of Geophysical Parameters Using Satellite Data).

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

Характерный пример — использование видеоспектрорадиометра. Для получения количественных параметров аэрозолей при условии полного покрытия большей части территории Китая за 30 дней накапливается 4 Тбайт данных. Кроме того, в приложениях выборки количественных параметров из данных дистанционного зондирования обычно требуется обработка данных и обратные вычисления. Задачи, выполняемые в потоке обработки данных, могут обладать разной сложностью, разными требованиями к пересылке данных и временем выполнения, что приводит к смешанной рабочей нагрузке с чередованием массивно параллельных задач, для которых необходима высокая пропускная способность и быстрое время ответа.

В Институте приложений дистанционного зондирования Китайской академии наук разработана инфраструктура RSIN (remote sensing information service grid node), поддерживающая выполнение приложений количественной выборки из данных дистанционного зондирования путем применения grid-вычислений. RSIN содержит множество агентов. Каждое приложение запускает некоторый набор агентов, отвечающих за отслеживание ресурсов и управление ими, сбор статистики и планирование задач. Коды алгоритма сохраняются в RSIN в виде модулей. Модуль обработки данных занимается предварительной обработкой «сырых» данных, полученных со спутника, в то время как модуль модели обеспечивает реальную выборку количественных параметров.

Оресте Вилла, Даниэле Паоло Скарпацца и Фабрицио Петрини представили статью «Ускорение поиска цепочек в реальном времени за счет использования многоядерных процессоров» (Accelerating Real-Time String Searching with Multicore Processors).

Объем цифровых данных, которые производятся и распространяются в мире, возрастает взрывообразно. Важным становится не только обеспечение доступа к данным и их поиск, но и защита от вирусов, вредоносных и шпионских программ, спама и попыток преднамеренного вторжения. Системы обнаружения вторжений уже не в состоянии отфильтровывать нежелательный трафик с использованием только информации заголовков пакетов, поскольку угрозы часто нацеливаются на прикладной уровень. Необходимо прибегать к «глубокой проверке пакетов» (deep packet inspection, DPI), включающей сопоставление информационного содержимого пакетов с базой данных сигнатур угроз. Однако при постоянно возрастающем числе угроз и повышающейся скорости каналов становится все сложнее выполнять глубокую проверку в реальном времени.

Имеется ряд алгоритмов, направленных на удовлетворение потребности в поиске и фильтрации информации. Эти алгоритмы лежат в основе поисковых машин, систем обнаружения вторжений, средств обнаружения вирусов, фильтров спама и систем мониторинга контента. Быстрые реализации поиска строк традиционно основываются на использовании специализированных аппаратных средств, таких как программируемые логические матрицы (field-programmable gate array, FPGA) и процессоры со специализированными системами команд (application-specific instruction-set processor), но появление многоядерных архитектур, подобных IBM Cell Broadband Engine (CBE), добавляет в эту игру новых важных игроков.

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

В 2007 году авторы статьи представили параллельный алгоритм для CBE, основанный на детерминированном конечном автомате, который обеспечил пропускную способность поиска, превышающую 5 Гбайт/с в расчете на один «синергический процессорный элемент» (synergistic processing element, SPE). В совокупности восемь SPE, входившие в состав CBE, обеспечили пропускную способность в 40 Гбайт/с при использовании словаря из 200 шаблонов и 5 Гбайт/с при работе со словарем из 1500 шаблонов. Эта пропускная способность очень велика, однако ее можно достичь только при использовании небольших словарей, что делает данное решение бесполезным для многих приложений.

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

Статью «Семантические запросы к большим биомедицинским наборам изображений» (Semantic Querying in Large Biomedical Image Datasets) написали Виджай Кумар, Сиварамакришнан Нараянан, Тахсин Курк, Джан Конг, Метин Гуркан и Джоэл Сальц.

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

Процесс прогнозирования нейробластомы включает последовательность шагов, выполнение которого над большим набором изображений может занять несколько часов или дней, что мешает эффективному компьютеризованному прогнозированию на основе анализа изображений. При анализе изображений может обеспечиваться семантическая информация в виде аннотаций и классификаций. Схема классификации может организовываться иерархическим образом. Во многих проектах исследователи стремятся к построению семантической базы данных на основе результатов анализа для поддержки более эффективной организации и агрегации информации об изображениях и интеграции этой информации с другими типами данных, такими как клинические и молекулярные данные, для проведения дальнейшего анализа. Крупномасштабные исследования в области семантической интеграции неоднородных данных на основе использования grid-технологий выполняются в проектах Biomedical Informatics Grid (caBIG, cabig.nci.nih.gov), Cardiovascular Research Grid (CVRG, cvrgrid.org), Biomedical Informatics Research Network (BIRN, www.nbirn.net ).

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

Авторами статьи «Аппаратные технологии для высокопроизводительных вычислений над большими объемами данных» (Hardware Technologies for High-Performance Data-Intensive Computing) являются Мая Гокхейл, Джонатан Коэн, Энди Ю, Маркус Миллер, Арпит Джакоб, Крейг Алмер и Роджер Пирс.

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

Новые технологии могут на порядок улучшить производительность алгоритмов, ориентированных на работу с данными большого объема. Графические процессоры (graphics processor unit, GPU) и FPGA могут значительно ускорить выполнение некоторых классов приложений. Кроме того, эти сопроцессоры взаимодействуют с внутрикристальной основной памятью, а не с традиционным кэшем.

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

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

Последняя статья подборки, озаглавленная «ProDA: сквозная, основанная на вейвлетах OLAP-система для больших наборов данных» (ProDA: An End-to-End Wavelet-Based OLAP System for Massive Datasets), написана Кирусом Шахаби, Мердадом Джахангири и Фарнушем Банаи-Кашани.

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

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

Средства оперативной аналитической обработки (online analytical processing, OLAP) направлены на снятие ограничений традиционных баз данных и приложений электронных таблиц и могут работать с очень большими наборами данных. За последние пять лет авторы спроектировали, разработали и довели до работоспособного состояния аналитическую систему ProDA (Progressive Data Analysis), которая позволяет эффективно анализировать большие наборы данных. ProDA — клиент-серверная система с трехуровневой архитектурой. На нижнем уровне системы поддерживается хранение данных, на среднем уровне обрабатываются запросы; в совокупности эти два уровня составляют серверную часть ProDA. В клиентской части ProDA располагается уровень визуализации, обеспечивающий формулировку запросов и представление их результатов.

ProDA поддерживает широкий набор аналитических запросов над большими наборами данных. По сравнению с традиционными средствами OLAP в ProDA обеспечиваются расширенные и усовершенствованные возможности оперативного выполнения аналитических запросов за счет применения собственной технологии, основанной на использовании вейвлетов (www.cs.usc.edu/Research/TechReports/07-893.pdf ).

В ProDA поддерживаются сложные аналитические запросы, включая все семейство полиномиальных агрегатных запросов и класс графовых запросов (plot query), которые раньше не поддерживались средствами OLAP. Кроме того, в отличие от традиционных средств оперативной аналитической обработки, в ProDA поддерживаются произвольные оперативные запросы. Аналитические запросы выполняются не в клиентских приложениях, а на стороне сервера, поблизости от данных. Используются замечательные свойства вейвлет-преобразований, позволяющих точно аппроксимировать результаты запросов при минимальном числе доступов к исходным данным. Новшество состоит в том, что преобразуются и запросы, и данные. Свойство переменной разрешающей способности вейвлет-преобразований позволяет аппроксимировать результаты запросов либо с заданной точностью, либо с заданным временем выполнения запроса.

Вне тематической подборки опубликована статья «Использование сопоставления цепочек для глубокой проверки пакетов» (Using String Matching for Deep Packet Inspection), авторами которой являются По-Чинг Лин, Йинг-Дар Лин, Юань-Ченг Лай и Церн-Хью Ли.

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

До 2001 года исследователей более всего интересовали методы сопоставления по наиболее длинному префиксу (longest-prefix matching) в таблицах маршрутизации марштрутизаторов Internet и классификации по нескольким полям (multifield packet classification) заголовка пакетов для межсетевых экранов и приложений поддержки качества обслуживания. Однако теперь наибольший интерес представляют методы глубокой проверки сетевых пакетов для разных видов сигнатур.

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

Анализ публикаций в электронных библиотеках IEEE Xplore (ieeexplore.ieee.org) и ACM DL (portal.acm.org/dl.cfm), показывает, что исследователи раньше в большей степени интересовались чистыми алгоритмами, пригодными в теоретических целях или в приложениях общего назначения. Позднее они стали проявлять больший интерес к алгоритмам, применимым для глубокой проверки сетевых пакетов. Аналогично, в ответ на требования повышенной скорости обработки исследователи фокусируются на аппаратных реализациях на основе специализированных интегральных схем (ASIC) и программируемых логических матриц (FPGA), а также на возможностях использования параллельных микропроцессоров.

До конца августа можно подписаться на издания IEEE Computer Society и вступить в члены сообщества на вторую половину 2008 года (www.computer.org/portal/pages/ieeecs/join/index.xml ). Всегда готов ответить на соответствующие вопросы, Сергей Кузнецов, kuzloc@ispras.ru .