МОГучие способности: новые приемы анализа больших данных

Джеффри Коэн, Брайен Долэн, Марк Данлэп, Джозеф Хеллерстейн, Кейлэб Велтон.
Перевод: Сергей Кузнецов

Оригинал: Jeffrey Cohen, Brian Dolan, Mark Dunlap, Joseph M. Hellerstein, Caleb Welton. MAD Skills: New Analysis Practices for Big Data. Proceedings of the VLDB'09 Conference, Lyon, France, August 24-28, 2009,

Содержание

От переводчика: идеи Стоунбрейкера живут и побеждают!

Аннотация

1. Введение

1.1. Вклад авторов

2. История вопроса: если вы не МОГучи

2.1. OLAP и кубы данных

2.2. Базы данных и статистические пакеты

2.3. MapReduce и параллельное программирование

2.4. Интеллектуальный анализ данных и аналитика в базе данных

3. FOX Audience Network

4. Проектирование МОГучих баз данных

4.1. Новые требования

4.2. Обретение большего МОГущества

5. Статистика, параллельная по данным

5.1. Векторы и матрицы

5.2. Аналитические методы на основе матриц

5.3. Функционалы

5.4. Методы повторного взятия образцов

6. МОГучая СУБД

6.1. Загрузка и выгрузка

6.2. Эволюция данных: хранение и разделение

6.3. МОГучее программирование

7. Направления и размышления

7.1. Когда наступит будущее?

8. Благодарности

Литература

От переводчика: идеи Стоунбрейкера живут и побеждают!

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

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

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

Наконец, хотя явно в данной статье об этом не говорится, СУБД Greenplum основана на исходных текстах PostgreSQL, которая, в свою очередь, выросла из проекта Стоунбрейкера Postgres. (Подтверждение этому можно найти, например, здесь.) И оказывается, что заложенные Стоунбрейкером в Postgres возможности расширения средств СУБД позволяют и интегрировать в систему баз данных развитые средства аналитики, и обеспечить поддержку MapReduce внутри системы.

Конечно, в статье содержится много интересного материала, и не имеющего отношения к идеям Стоунбрейкера. Но я оставляю судить об этом читателям...

Аннотация

Поскольку все проще и дешевле накапливать и сохранять огромные объемы данных, самые разнообразные предприятия нанимают статистиков для выполнения сложного анализа данных. В этой статье основное внимание уделяется новым приемам магнетичного, основательного, гибкого анализа данных ("МОГучего" анализа данных – Magnetic, Agile, Deep (MAD) data analysis) как радикального отхода от корпоративных хранилищ данных (Enterprise Data Warehouses) и бизнес-аналитики (Business Intelligence). Мы представляем свою философию разработки, методы и опыт, обеспечивающие MAD-аналитику в компании Fox Audience Network на основе использования параллельной системы баз данных Greenplum. Мы описываем методологию проектирования баз данных, поддерживающую гибкий стиль анализа данных в этой среде. Мы также представляем параллельные по данным алгоритмы, используемые в сложных статистических методах, причем фокусируемся на плотностных методах (density method). Наконец, мы размышляем о средствах систем баз данных, допускающих гибкие проектирование и разработку алгоритмов с совместным использованием интерфейсов SQL и MapReduce поверх различных механизмов хранения данных.

1. Введение

Если вы подыскиваете род деятельности, в котором ваши усилия будут высоко востребованы, вам следует найти область, в которой вы сможете обеспечить дефицитные дополнительные услуги по отношению к тому, что повсеместно распространено и дешево обходится. А что повсеместно распространо и дешево обходится? Данные. А что является дополнительной услугой по отношению к данным? Анализ.
– Профессор Хал Вариан, университет Беркли, главный экономист Google [5]

mad (прил.): прилагательное, используемое для усиления смысла существительного.
1- dude, you got skills (чувак, ты кое-что можешь).
2- dude, you got mad skills (чувак, ты могуч).
– UrbanDictionary.com [12]

Стандартная бизнес-практика крупномасштабного анализа данных опирается на понятие "корпоративного хранилища данных" (Enterprise DataWarehouse, EDW), запросы к которому поступают из программного обеспечения "бизнес-аналитики" (Business Intelligence, BI). Инструментальные средства BI позволяют создавать отчеты и интерактивные интерфейсы, обобщающие данные на основе применения агрегатных функций (вычисляющих, например, количество или среднее значение) к различным иерархическим разбиениям данных на группы. В 1990-е гг. это являлось темой значительных академических исследований и производственных разработок.

Традиционно считается, что тщательно спроектированное EDW играет центральную роль при правильном применении IT. Проектирование и эволюция детальной схемы EDW служит общим принципом дисциплинированной интеграции данных крупных предприятий, совершенствуя результаты и представления всех бизнес-процессов. Результирующая база данных играет роль репозитория характеристик критических бизнес-функций. Кроме того, сервер баз данных, сохраняющий EDW, традиционно является основным вычислительным средством, служащим центральным, масштабируемым механизмом ключевой корпоративной аналитики. Концептуальное и вычислительное центральное положение EDW делает его критически важным дорогостоящим ресурсом, используемым для производства отчетов над большим количеством данных, и эти отчеты ориентируются на руководящих лиц, принимающих решения. EDW традиционно контролируется специально назначаемыми сотрудниками IT, которые не только сопровождают систему, но и тщательно контролируют доступ к ней, чтобы руководящие лица могли гарантированно расчитывать на высокий уровень обслуживания. [13]

Хотя во многих ситуациях этот ортодоксальный подход EWD продолжает применяться, ряд факторов способствует продвижению совсем другой философии управления крупномасштабными данными на предприятиях. Во-первых, хранение данных теперь обходится настолько дешево, что небольшие подгруппы предприятия могут разработать изолированную базу данных астрономического масштаба в пределах своего собственного бюджета. Наиболее крупное хранилище данных всего лишь десятилетней давности можно было бы теперь сохранить на менее чем 20 дисках стоимостью менее 100 долларов. Отдельный департамент может сам заплатить за систему хранения данных объемнее на 1-2 порядка без согласования этого с руководством. Тем временем, число внутрикорпоративных крупномасштабных источников данных значительно возрастает: крупные базы данных сегодня возникают даже на основе единственного источника потоков данных о посещении Web-сайтов (click-stream), журналов программных систем, архивов электронной почты и дискуссионных форумов и т.д. Наконец, общепризнанной стала значимость анализа данных, и многочисленные компании демонстрируют, что сложный анализ данных способствует сокращению расходов и даже прямому росту доходов. Результатом этих возможностей является массовый переход к сбору и использованию данных в нескольких оранизационных единицах корпораций. Преимущество этого перехода состоит в том, что он содействует повышению эффективности и росту культуры использования данными, но он усиливает децентрализацию данных, с которой призвано бороться хранилище данных.

В этом изменяющемся климате сбора разрозненных крупномасштабных данных целесообразен подход, который мы называемым МОГучим анализом данных (MAD analisys). Акроним MAD происходит от трех аспектов этой среды, отличающих ее от ортодоксальных EDW:

• Магнетичность (magnetic): Подходы к организации традиционных EDW предполагают "отталкивание" новых источников данных, т.е. данные из нового источника не включаются в EDW, пока они не будут очищены и интегрированы. С учетом повсеместности данных в современных организациях сегодняшнее хранилище данных может идти в ногу с аналитическими потребностями организации, только будучи "притягательным" ("магнетичным"), притягивая все источники данных, появляющиеся в организации, независимо от их качества.
• Гибкость (agile): Традиционные хранилища данных основываются на долгосрочном тщательном проектировании и планировании. С учетом роста числа источников данных и потребности во все более сложном и критически важном анализе данных современное хранилище данных должно вместо этого позволять аналитикам простым образом воспринимать, классифицировать, производить и перерабатывать данные в быстром темпе. Для этого требуется база данных, логическое и физическое содержимое которой может постоянно и быстро изменяться.
• Основательность (deep): В современном анализе данных используются все более сложные статистические методы, далеко выходящие за пределы обобщения (rollup) и детализации (drilldown) традиционных методов BI. Кроме того, при выполнении этих алгоритмов аналитикам часто требуется одновременно видеть и лес целиком, и отдельные деревья – им нужно исследовать огромные наборы данных, не прибегая к использованию образцов и выборок. Современное хранилище данных должно служить и основательным (глубоким) репозиторием данных, и механизмом поддержки выполнения сложных алгоритмов.

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

1.1. Вклад авторов

В этой статье описываются методы и навыки, полученные при разработке средств МОГучей аналитики для компании Fox Audience Network с использованием крупной установки системы Greenplum Database. Мы обсуждаем свою методологию проектирования баз данных, которая ориентирована на обеспечение гибкого, но, вместе с тем, организованного подхода к анализу данных (разд. 4). Мы представляем ряд параллельных по данным статистических алгоритмов, разработанных для этой среды, которые фокусируются на моделировании и сравнении плотностей распределений. К их числу относятся специальные методы, такие как обычный метод наименьших квадратов (Ordinary Least Squares), метод слпряженных градиентов (Conjugate Gradiant) и метод, основанный на U-критерии Манна-Уитни (Mann-Whitney U Testing), а также методы общего назначения, такие как метод перемножения матриц (matrix multiplication) и метод раскрутки (Bootstrapping) (разд. 5). Наконец, мы размышляем о важных средствах систем баз данных, делающих возможными быструю и гибкую разработку алгоритмов, включая высокопроизводительное включение/извлечение данных (data ingress/egress), хранение неоднородных данных, а также гибкое программирование с использованием расширяемых интерфейсов SQL и MapReduce к единой системе (разд. 6).

Наше обсуждение бросает вызов многим общепринятым положениям. В области проектирования и анализа хранилищ данных мы отстаиваем тезис "Меньше моделируйте, больше итерируйте" (Model Less, Iterate More). Этот тезис противоречит позиции ортодоксов хранилищ данных, и его смысл означает передачу всей полноты власти от администраторов баз данных аналитикам. Мы говорим о потребности в однородных системах, поддерживающих и интегрирующих разнообразные стили программирования с большими объемами данных, поскольку аналитики происходят из многих разных профессиональных сообществ. Это означает отказ от религиозных дебатов относительно преимуществ SQL над MapReduce или R над Java с целью сосредоточиться на развитии единого параллельного механизма обработки потоков данных, который может поддерживать различные стили программирования средств нетривиальной аналитики. Наконец, мы утверждаем, что этот параллельный механизм обработки потоков данных может и должен объединять много источников данных и форматов хранения. Это направлено на более гладкую интеграцию или консолидацию традиционно разрозненных инструментальных средств, включая традиционные реляционные базы данных, поколоночные системы хранения, средства ETL и распределенные файловые системы.

2. История вопроса: если вы не МОГучи

Аналитическая обработка данных – это не новая область. В этом разделе мы описываем стандартные приемы и родственные работы в направлениях BI и крупномасштабного анализа данных, чтобы образовать контекст для представления своего МОГучего подхода.

2.1. OLAP и кубы данных

В 1990-е гг. получили распространение кубы данных и оперативная аналитическая обработка данных (On-Line Analytic Processing, OLAP), что привело к интенсивным коммерческим разработкам и значительным академическим исследованиям. В реляционной среде основная идея OLAP преобразовалась в расширение SQL CUBE BY [8]. Инструментальные средства BI оформляли эти сводные показатели в виде интуитивно понятных "межтабличных" визуализаций. При группировке по немногим измерениям аналитик видит грубую столбчатую диаграмму "обобщения" (roll-up); группировка по большему числу измерений позволяет перейти на более детальный уровень (drill down). Для этого вида анализа статистики используют термин дескриптивная (описательная) статистика. Такой подход традиционно применяется к результатам экспериментальных исследований. Эта функциональность полезна для получения интуитивного представления о процессе, определяющем данный эксперимент. Например, за счет описания потока данных о посещении некоторого Web-сайта можно получить лучшие интуитивные знания об основных свойствах состава пользователей.

В отличие от этого, статистика выводов (inferential statistics), или индуктивная статистика (inductive statistics) направлена на то, чтобы напрямую фиксировать основные свойства популяции. В число используемых приемов входят подбор моделей и параметров для данных и вычисление функций правдоподобия. Для применения статистики выводов требуется больше вычислений, чем для получения простых сводных данных, предоставляемых OLAP, но при этом обеспечивается большая вероятностная мощность, которую можно использовать для решения таких задач, как предсказание (например, "какие пользователи, вероятно, кликнули бы по этому новому рекламному банеру?"), анализ причинных связей (например, "какие свойства данной страницы приводят к ее повторному посещению пользователями?") и дистрибутивное сравнение (distributional comparison) (например, "чем модель покупательского поведения владельцев грузовиков отличается от аналогичной модели владельцев легковых автомобилей с кузовом "седан"?"). Индуктивный подход также является более устойчивым к наличию аномальных значений и других особенностей в заданном наборе данных. Хотя OLAP и кубы данных остаются полезными для получения инстуитивного понимания, использование статистики выводов становится необходимой во многих важных автоматических и полуавтоматических бизнес-процессах, включая размещение рекламы, оптимизацию Web-сайтов и управление связями с заказчиками.

2.2. Базы данных и статистические пакеты

Средства BI обладают довольно ограниченными статистическими функциональными возможностями. Поэтому во многих организациях стандартным приемом является извлечение частей базы данных в настольные программные пакеты: статистические пакеты типа SAS, Matlab или R, электронные таблицы наподобие Excel или собственный код пользователей, написанный на языках типа Java.

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

Лучший подход состоит в тесной интеграции статистических пакетов с массивно параллельной базой данных. К сожалению, для многих имеющихся в настоящее время статистических пакетов отсутствуют параллельные реализации какого-либо вида. Параллелизованные статистические библиотеки, (например, посредством ScaLAPACK [2]) основываются на использовании протоколов обмена сообщениями между процессорами (на базе MPI) и не интегрируются естественным образом с параллелизмом по данным популярных решений для обработки больших объемов данных.

2.3. MapReduce и параллельное программирование

В то время как для корпоративного использования предлагались методологии BI и EDW, внимание многих разработчиков привлекла модель программирования MapReduce, введенная компанией Google. Очень заметные успехи Google в областях размещения рекламы и обработки текстов (и их публичное принятие методов статистического машинного обучения) способствовали быстрому росту популярности этого подхода. В недавней статье о реализации алгоритмов машинного обучения в среде MapReduce [3] был выделен ряд стандартных методов, которые могут быть применены в параллельном по данным стиле посредством обобщения. Проект Apache Mahout является попыткой реализовать эти методы в открытой реализации MapReduce Hadoop. Результаты, описанные в этой статье, равно применимы и к SQL, но важно технико-социальное явление, сопутствующее MapReduce: появление этой модели привело к тому, что ряд расположенных к статистике исследователей и разработчиков сфокусировался на крупных данных и параллельном по данным программировании, а не на программировании для мультипроцессоров на основе MPI. Этот дух параллельного по данным программирования способствовал разработке и наших алгоритмов, описываемых в разд. 5. Но, как отмечается в разд. 4, стиль программирования – это лишь один аспект подхода MAD к управлению процессом аналитики.

2.4. Интеллектуальный анализ данных и аналитика в базе данных

У параллельных алгоритмов интеллектуального анализа данных (data mining) имеется серьезная библиография; см., например, подборку Заки (Zaki) и Хо (Ho) [24]. Наиболее распространенные методы data mining (кластеризация, классификация, поиск ассоциативных правил) имеют дело с тем, что можно было бы назвать поточечным принятием решений (pointwise decisions). При кластеризации и классификации ставится соответствие между индивидуальными точками и когортами (cohort) (метками классов или идентификаторами кластеров); результатом действия ассоциативных правил являются комбинаторные коллекции индивидуальных точек. Хотя эти проблемы нетривиальны, в области статистического моделирования имеются и некоторые другие методы. Например, распространенным методом анализа рекламы является A/B-тестирование (A/B testing), в котором берутся показатели отклика (response rates) некоторой подгруппы населения и некоторой контрольной группы, и с использованием различных метрик сравниваются их статистические плотности.

Стандартные методы data mining в коммерческих базах данных полезны, но очень прицельны: они соответствуют лишь малому числу из сотен статистических библиотек, поставляемых в составе статистических пакетов, таких как R, SAS или Matlab. Кроме того, они обычно реализуются в виде "черного ящика" – код компилируется в плагин сервера баз данных. В отличие от этого, статистические пакета типа R или Matlab являются гибкими средами программирования, в которых библиотечные подпрограммы могут расширяться и модифицироваться аналитиками. В MAD-анализе требуется, чтобы аналогичные возможности программирования на основе расширяемых средств SQL и/или MapReduce были привнесены в сценарии использования крупных данных. В этом контексте иногда могут быть полезны и процедуры data mining в виде черных ящиков, но только в небольшом числе случаев.

Кроме нашей работы, в литературе описаны и другие интересные попытки выполнения значительных научных вычислений на языке SQL; наиболее значительная работа выполнена в связи с Sloan Digital Sky Survey [22]. Уместно также упомянуть управление экспериментами [14] и сложным SQL-кодом [16]. Кроме того, интересующимся читателям стоит познакомиться с работами, посвященными новым исследовательским системам управления научными данными [21] и масштабируемости R [25]. Что касается интеграции данных, то нашей МОГучей философии близка и идея "пространств данных" [6].

Содержание Вперёд