Hbase/BigTable SQL on Hadoop/Impala Некоторые типичные задачи больших данных Spark/Shark Проблемы больших данных 1

HBase – распределенная система хранения данных ориентированная на доступ к данным как к столбцам таблицы (поверх HDFS) HBase - Apache проект с открытым кодом, цель которого – предоставление удобного доступа к данным для вычислений в среде Hadoop Данные логически объединены в таблицы, строки и столбцы 2

3 HBase построена на основе HDFS HBase файлы хранятся в HDFS

Обе являются распределенными системами, которые легко расширяются до тысяч узлов HDFS is хороша для пакетной обработки (полное чтение больших файлов) Не удобна для поиска конкретной записи Не удобна для добавления небольших объемов данных Не поддерживает обновления 4

HBase разработана для разрешения указанных неудобств Быстрый поиск конкретной записи Поддержка вставки записей Поддержка обновлений (удаление/вставка, не замещение на том же месте) Hbase обновления выполняются путем создания новой версии записи 5

HBase поcтроена на основе модели Bigtable (от Google) – пара : Таблицы отсортированы по строкам (ключам) Схема таблицы определяет семейства столбцов. Каждое семейство состоит из произвольного количества столбцов Каждый столбец может иметь произвольное количество «версий» Хранятся только реальные значения столбцов, NULL не хранятся. Столбцы семейства отсортированы и хранятся вместе Значение представляет из себя массив байтов, byte[] (Строка,Семейство:Cтолбец, Версия) 6

7

8 Различные множества столбцов могут иметь различные свойства и тип доступа Для каждого семейства можно конфигурировать Тип компресии (нет, gzip, LZO) Стратегию сохранения версий Кэш-приоритет Семейства столбцов хранятся отдельно на диске: доступ к одному семейству не требует ввода-вывода других Каждое семейство столбцов HTable разделяется (горизонтально) на регионы по значениям ключа. В определенном смысле регионы являются аналогом HDFS блоков

Таблица people создается с 3 семействами столбцов: personal, contactinfo, creditcard Configuration conf = HBaseConfiguration.create(); HBaseAdmin admin = new HBaseAdmin(conf); HTableDescriptor tableDescriptor = newHTableDescriptor(TableName.valueOf("people")); tableDescriptor.addFamily(new HColumnDescriptor("personal")); tableDescriptor.addFamily(new HColumnDescriptor("contactinfo")); tableDescriptor.addFamily(new HColumnDescriptor("creditcard")); admin.createTable(tableDescriptor); 9

Configuration conf = HBaseConfiguration.create(); HTable table = new HTable(conf, "people"); Put put = new Put(Bytes.toBytes("doe-john-m-12345")); put.add(Bytes.toBytes("personal"), Bytes.toBytes("givenName"), Bytes.toBytes("John")); put.add(Bytes.toBytes("personal"), Bytes.toBytes("mi"), Bytes.toBytes("M")); put.add(Bytes.toBytes("personal"), Bytes.toBytes("surname"), Bytes.toBytes("Doe")); put.add(Bytes.toBytes("contactinfo"), Bytes.toBytes(" "), table.put(put); table.flushCommits(); table.close(); 10

11 Get get = new Get(Bytes.toBytes("doe-john-m-12345")); get.addFamily(Bytes.toBytes("personal")); get.setMaxVersions(3); результат результат = table.get(get); Scan scan = new Scan(Bytes.toBytes("smith-")); scan.addColumn(Bytes.toBytes("personal"), Bytes.toBytes("givenName")); scan.addColumn(Bytes.toBytes("contactinfo"), Bytes.toBytes(" ")); scan.setFilter(new PageFilter(25)); ResultScanner scanner = table.getScanner(scan); for (результат результат : scanner) { //... }

12 Мастер Контролирует серверы регионов Балансирует загрузку для регионов Направляет клиента на нужный сервер региона Может иметь резервную копию Сервера регионов - роботы Обслуживают запросы клиентов (чтение/запись/сканирование) Посылают сигналы готовности (HeartBeat) Мастеру Обеспечивают масштабируемость регионов

13

HBase зависит от ZooKeeper – ПО для конфигурации и управления кластером По умолчанию HBase управляет ZooKeeper т.е. стартует и останавливает ZooKeeper HMaster и HRegionServers регистрируются в сервисах ZooKeeper 14

Apache ZooKeeper это программный проект Apache Software Foundation, обеспечивая открытым исходным кодом распределенной службы настройки, службы синхронизации и именования реестра для крупных распределенных систем. ZooKeeper был суб проект Hadoop, но теперь проект верхнего уровня в своем собственном праве.Apache Software Foundationоткрытым исходным кодомраспределенных системHadoop Архитектура зоопарка поддерживает высокую доступность через избыточных услуг. Таким образом, клиенты могут задать еще один мастер зоопарка, если первый не отвечает. Боец узлы хранят свои данные в иерархическом пространстве имен, так же, как в файловой системе или TRIE DataStructure. Клиенты могут читать и писать из / в узлах и таким образом, имеют общую службу конфигурации. Обновления вполне упорядочено.высокую доступностьTRIEвполне упорядочено Apache ZooKeeper is a software project of the Apache Software Foundation, providing an open source distributed configuration service, synchronization service, and naming registry for large distributed systems. ZooKeeper was a sub project of Hadoop but is now a top-level project in its own right.Apache Software Foundationopen sourcedistributed systemsHadoop ZooKeeper's architecture supports high availability through redundant services. The clients can thus ask another ZooKeeper master if the first fails to answer. ZooKeeper nodes store their data in a hierarchical name space, much like a file system or a trie datastructure. Clients can чтение and запись from/to the nodes and in this way have a shared configuration service. Updates are totally ordered.high availabilitytrietotally ordered 15

HBase не поддерживает соединения(joins) Необходимо программировать на уровне приложения 16

17 HDFS/MapReduceHBASE Запись Только добавление Выборочная запись, массовое добавление Чтение Полное сканирование, сканирование раздела Выборочное чтение, чтение интервала, полное сканирование Hive/SQL эффективность Высокая 4-5 раз медленнее Максимальный размер данных 30+ PB1 PB

18 Необходим произвольный доступ для чтения и/или записи Требуется большое количество (простых) операций в секунду над записями больших файлов ( порядка TB) Тип доступа простой и заранее определен (поиск по ключу, вставка/удаление/обновление отдельной записи, чтение записей с ключом в заданном интервале)

Cloudera - американская компания, разработчик ПО, выпускающая коммерческую версию программной среды Apache Hadoop Компания была основана в октябре 2008 года в Бёрлингейме (штат Калифорния) со стартовым капиталом $5 млн, основной целью бизнеса выбрана коммерциализация проекта Hadoop К середине 2013 года за пять раундов инвестиций компания получила в общей сумме $141 млн, а в очередном раунде в марте 2014 года компания привлекла ещё $900 млн., в том числе $740 млн от Intel, при оценке бизнеса Cloudera приблизительно в $4 млрд., при этом компания Intel отказалась от развития созданного годом ранее собственного дистрибутива Hadoop в пользу продвижения решений от Cloudera 19

Современный инструмент обработки SQL запросов (с открытым кодом). Заменяет MapReduce, который Ориентирован на пакетную обработку Требует много времени, потому что записывает промежуточные результаты на диск Рассчитан больше на разработчиков, чем на рядовых пользователей Как насчет Hive? Также ориентирован на пакетную обработку Не рассчитан на работу в реальном времени, на параллельное исполнение нескольких работ 20

Impala интегрирована с HDFS и Hbase, не требуя перемещения данных или преобразования. Используется аналитиками и исследователями данных (data scientist) для работы с данными хранимыми в форматах Hadoop с привлечением SQL и систем (автоматичести) генерирующих SQL запросы, когда система построена в терминологии бизнес объектов С начала 2013 года объявлена поддержка столбцового формата Parquet С декабря 2013 Amazon объявил о поддержке Impala для AWS (Amazon Web Service) Использует SQL синтакс типа HiveQL 21

Общецелевой инструмент обработки SQL запросов. Обрабатывает достаточно сложные аналитические запросы Хорошо масштабируется Обрабатывает работы в диапазоне от милли-секунд до нескольких часов Тысячи параллельно выполняемых работ Работает напрямую с Hadoop? Может читать различные форматы файлов Использует тот же кластер 22

Высокая производительность. Реальный параллелизм (MPP) обработки запросов C++ вместо Java Генерация машинного кода во время исполнения (LLVM) Новая исполняющая система (не MapReduce) Полностью открытый код Apache License

SQL-92 без коррелированных под-запросов Подобен HiveQL ORDER требует LIMIT (в разработке) Нет сложных типов данных (в разработке) Другие удобства INSERT INTO SELECT CREATE TABLE AS SELECT LOAD INTO UDF, UDAF (C++ и Java) JOINs должны умещаться в памяти исполняющих узлов Постоянно добавляются новые (недостающие) возможности языка SQL 24

Логистическая регрессия Метод K-средних Машинное обучение 25

26 Пусть X – вектор независимых переменных, Y – т.наз. классификатор, предположим P(Y|X) – вероятность события, классифицируемого Y W = (W1, W2, … Wn) – вектор параметров, X=(X1, X2, …, Xn), WX – скалярное произведение Логистическая функция (сигмоид):

27 Выборка – пациенты различного возраста (независимая переменная) Событие - инфаркт (Y, 1 или 0, зависимая переменная) Линейная функция плохо оценивает вероятность инфаркта, сигмоид – гораздо лучше

28 Логистическая регрессия исследует условное распределение P(y|x) Пусть p y (x;w) – наша оценка P(y|x), где w – вектор настраиваемых параметров Предположим, имеется 2 класса, y = 0 и y = 1 Это эквивалентно Т.е. логарифм «шансов» попадания в класс 1 является линейной функцией от x Как подобрать W?

29 Функция правдоподобия определяется «обучающей выборкой» с соответствующими значениями классификатора. Параметры W определяются путем максимизации функции правдоподобия где w = - вектор оцениваемых параметров (модели), y l – наблюдаемое значение в l-том примере обучения, и x l – значения независимых переменных в l-том примере обучения

30 Максимизация функции правдоподобия эквивалентна максимизации ее логарифма : Обозначим это как l(W), что может быть переписано как Заметим, здесь будет использоваться факт, что Y может принимать только значения 0 или 1, поэтому только одно слагаемое под суммой будет ненулевым для любого конкретного y l

31 Не существует явного решения задачи максимизации (логарифма) функции правдоподобия l(w) по w. Возможный способ решения – использование градиентных методов i-тая компонента вектора градиента имеет вид

32

33

36 Изучает распределение условной вероятности P(y|x) Методы локального поиска. Начинаем с начального вектора параметров Максимизируем целевую фукцию итерационным методом Целевая фукция - логарифм функции правдоподобия l(w). После оценки параметров по обучающей выборке, можно оценить условную вероятность P(y|x) отнесения (нового) вектора х к классам 1/0 Причем тут большие данные?

37 k-means (метод k-средних) - наиболее популярный метод кластеризации Задача - минимизировать суммарное квадратичное отклонение точек кластеров от центров этих кластеров Алгоритм Штейнгауза/Ллойда Инициализация. Выбираются K начальных точек – центроидов (случайно, или погружением точек в минимальный куб и размещением начальных точек по его диагонали) Итерация. Точки разбиваются на кластеры приданием каждой ближайшему центроиду, центроиды пересчитываются как центры кластеров Итерации повторяются до тех пор пока ни один центроид не изменится

38 Начальное множество точек

39 Выбрать начальные центроиды произвольным образом

40 Отнести точки к ближайшему центроиду

41 Пересчитать центроиды в полученных кластерах

42 Переназначить точки новым центроидам

43 Пересчитать центроиды в полученных кластерах

44 Переназначить точки новым центроидам

45 Пересчитать центроиды в полученных кластерах

46 Переназначить точки новым центроидам Нет изменений – конец алгоритма

47 Вычисление расстояний INSERT INTO YD SELECT i, j,sum((YV.val-C.val)**2) FROM YV, C WHERE YV.l = C.l GROUP BY i, j; Нахождение ближайшего центроида INSERT INTO YNN SELECT YD.i, YD.j FROM YD, (SELECT i, min(distance) AS mindist FROM YD GROUP BY i) YMIND WHERE D.i = YMIND.i and YD.distance = YMIND.mindist; Обновление центроидов INSERT INTO W SELECT j,count(*) FROM YNN GROUP BY j; UPDATE W SET w = w/model.n; INSERT INTO C SELECT l, j, avg(Y V.val) FROM YV, YNN WHERE YV.i = YNN.i GROUP BY l, j; INSERT INTO R SELECT C.l, C.j,avg( (YV.val C.val) 2) FROM C, YV, YNN WHERE YV.i = YNN.i and YV.l = C.l and YNN.j = C.j GROUP BY C.l, C.j; Может быть очень медленным из-за большого количества создания и обновления больших таблиц

48 Подраздел искусственного интеллекта, изучающий методы построения моделей, способных обучаться, и алгоритмов для их построения и обучения. Обучение по прецедентам, или индуктивное обучение, основано на выявлении закономерностей в эмпирических данных. Имеется множество объектов (ситуаций) и множество возможных ответов (откликов, реакций). Существует некоторая зависимость между ответами и объектами, но она неизвестна. Известна только конечная совокупность прецедентов пар «объект, ответ», называемая обучающей выборкой. На основе этих данных требуется восстановить зависимость, то есть построить алгоритм, способный для любого объекта выдать достаточно точный ответ. Для измерения точности ответов определённым образом вводится функционал качества/потерь Некоторые классические задачи, решаемые с помощью машинного обучения Классификация, как правило, выполняется с помощью обучения с учителем на этапе собственно обучения. Кластеризация, как правило, выполняется с помощью обучения без учителя Для эффективной работы с большими обучающими выборками требуется специальный инструмент, традиционные РБД и SQL не подходят

Быстрая вычислительная система на кластере совместимая с Apache Hadoop Улучшает производтельость путем: Конструкций для работы в опер.памяти Общего графа вычислений Удобство использования: Богатый API для Scala, Java, Python Интерактивная среда (shell) До 100× быстрее (2-10× с диском) Часто код короче 5×

MapReduce значительно упростил анализ больших данных (для определенных типов приложений) Но, по мере того, как он приобрел популярность, пользователи захотели большего: Более сложную (многошаговую) аналитику Произвольные запросы в интерактивном режиме Обработки больших потоков данных в режиме реального времени Все 3 типа требуют быстрого доступа к общим данным между параллельными работами

итер. 1 итер ввод HDFS чтение HDFS запись HDFS чтение HDFS запись ввод запрос 1 запрос 2 запрос 3 результат 1 результат 2 результат 3... HDFS чтение Медленно из-за дублирования, сериализации, дискового ввода/вывода

итер. 1 итер ввод Распределенная память ввод запрос 1 запрос 2 запрос 3... Одноразовая обработка × быстрее, чем сеть и диск

Ключевая идея: эластичные распределенные наборы данных (resilient distributed datasets, RDDs) Распределенные наборы объектов, которые могут храниться и обрабатываться в памяти/кэше узлов кластера Обрабатываются с использованием (специальных) параллельных операторов Автоматически перевычисляются при отказах Программный интерфейс Функциональный APIs для Scala, Java, Python Интерактивное использование из оболочки Scala

Загрузить сообщения об ошибках из журнала в память, затем интерактивно искать различные шаблоны lines = spark.textFile(hdfs://...) errors = lines.filter(lambda x: x.startswith(ERROR)) errors.cache() блок 1 блок 2 блок 3 робот Драйвер errors.filter(lambda x: foo in x).count errors.filter(lambda x: bar in x).count... задачи результаты кэш 1 кэш 2 кэш 3 Базовый набор Преобразован ный набор действие результат: масштабируемый до 1TB в 5-7 сек. (против 170 сек. для данных на диске)

Поддерживаемые операторы map filter groupBy sort union join leftOuterJoin rightOuterJoin reduce count fold reduceByKey groupByKey cogroup cross zip sample take first partitionBy mapWith pipe save...

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

Столбцовый SQL аналитический инструмент на основе Spark Поддерживает и SQL, и сложную аналитику До 100 раз быстрее, чем Hive Совместим с Hive HiveQL, UDF/UDAF, Scripts Мажет работать на существующих хранилищах данных, использующих Hive Используется в Yahoo! для быстрого OLAP анализа в оперативной памяти

Мета- данные HDFS Клиент Драйвер Разбор SQL Оптимизация запроса План выпол- нения запроса выполнение CLIJDBC MapReduce

Мета- данные HDFS Клиент Драйвер Разбор SQL План выпол- нения запроса выполнение CLIJDBC Spark управление кэшем Оптимизация запроса

1.7 TB Warehouse Data на 100 EC2 узлах

Небольшая задержка обработки (Spark выполняет работы длительностью в пол-секунды) Поддержка общих ориентированных графов Хранение данных по столбцам и высокая компрессия Новые методы оптимизации и выполнения запросов

Единая система для SQL, обработки графов, машинного обучения Все используют то же множество роботов и кэшей

Аналитика для больших данных развивается, включая: Более сложные области применения (например, машинное обучение) Больше интерактивных специальных запросов Больше потоковой обработки в реальном времени Spark – это быстрая платформа, которая объединяет такие приложения Больше информации на: spark.apache.org

Первые успехи Moneyball, 2002, Oakland Athletics, статистический подход к выбору игроков в бейсболе. Модель Google распространения гриппа, 2009 H1N1, корреляция между определенными запросами и распространением гриппа в пространстве и времени, 450 млн моделей, 45 терминов показали сильную корреляцию. Oren Etszioni, инициировал нескольно компаний, работающих с «большими данными» до того, как сам термин утвердился. Farecast, продажа авиа-билетов, к 2012 г. Система давала правильный прогноз в 75% случаев и экономила пользователю, в среднем $50 на билет, MicroSoft купила Farecast за $110 млн.

Борьба с ошибками «Измерить – значит узнать»(Кельвин), «Знание - сила» (Бэкон) Измерения имеют погрешность, больше измерений – больше ошибок, больше задержка в обработке Проверка текста (по словарю) и грамматики, Microsoft Word, Google Translator CPI, 90 городов, ценников, поддержка - $20 млн./год, задержка в 2-3 месяца. 2 экономиста из МИТ разработали модель, получающую данные с Интернета, и позволяющую быстрее реагировать на признаки кризиса Тенденция в обработке данных - от частичных «очищенных» данных к большему объему или к полным данным, содержащим ошибки и «пустоты»

Корреляция Amazon.com, изменение стратегии рекламы от прошлых покупок, через корреляцию с похожими покупателями, к корреляции между продуктами и вкусами покупателя Target, аналитика для прогнозирования. Школьница получила купон на детскую одежду и кроватку. Женщины, ожидающие ребенка, регистрируются в программе детских подарков. Их «покупательские корзины» анализируются. Затем анализируются корзины других покупателей и, если корреляция высока, то высылается соответствующая реклама. Обслуживание смотровых колодцев в Нью Йорке ( колодцев, км подземных кабелей). Группа анализировала 106 параметров, влияющих на аварийность. 10% колодцев из составленного списка имели 44% проблем.

Корреляция без причины, пример Корреляция: Разводы на 1000 жителей Потребление маргарина, фунтов

Корреляция без причины, пример ,59419,75320,73420,83123,02923,59723,58425,52527,73129,449 5,6886,1986,4626,6357,3367,2487,4918,1618,5789,000 Корреляция: Расходы США на науку и технологию Самоубийства путем повешения/удушения

Построение 3-х мерной модели протеинов на аснове анализа ДНК и статического анализа не отменяет необходимости понимания физики и биохимии Тот же алгоритм анализа больших данных может давить худший результат в изменившихся условиях. Google Flu Trends. Данные с Web или телефонных опросов могут быть не репрезентативными. Успехи больших данных – в относительно типичных, хорошо известных областях. Google три-граммы и перевод. Нарушение прав личности на частную жизнь Навязчивая реклама. Нестотря на определенные успехи, достижения в области больших данных не могут сравниться с такими достижениями прошлых веков как антибиотики, самолеты, интернет, сотовые телефоны

pdf osdi04. pdf pdf pdf Nate Silver. The Signal and the Noise: Why So Many Predictions Fail but Some Don't Viktor Mayer-Schonbrger and Kenneth Cukier. Big Data