# Введение в большие данные и модель вычислений MapReduce. Лекция 1

## Большие данные представляют собой:

1. Массивы (не)(слабо)структурированных данных, объемы которых настолкьо велики, что их обработка традиционными средствами неэффективна или же невозможна.
2. Комплекс средств и методов для обработки и анализа массивыв данных, попадающих под определение больших данных.

## Набор признаков больших данных **VVV**:
1. V - velocity, скорость роста
2. V - volume, объем
3. V - variety, многообразие

## Задачи в больших данных:
1. Поисковые системы: построение поискового ндекса, поиск дубликатов документов, ранжирование веб-страниц.
2. Компьютерная лингвистика: опредеоение спама, машинный перевод, подбор статей для новостных сервисов.
3. ИАД в маркетинге: поиск ЦА, ценообразование, рекомендации.

## Подход к решению задач в больших данных

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

Ключевая идея: предоставить функциональные абстракции для этих двух операций.

## Знакомство с MapReduce

Из функционального программировнаия известно 2 часто используемые операции:
1. **map** - отображение (переход по записи).
2. **reduce** или **fold** - свертка (объединение промежуточных результатов).


### Map

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

### Reduce

Эта функция производит преобразование структуры данных к единственному атомарному значению при помощи комбинирующей функции g.

## Модель MapReduce - модель параллельных вычислений

Программист определяет 2 функции:
1. map (k1, v1) → [(k2, v2)]
map принимает на вход кортеж в виде пары ключ-значение, на выходе получается список пар ключ-значение

2. reduce (k2, [v2]) → [(k3, v3)]
reduce принимает на вход кортеж в виде пары ключ-значение, где ключ имеет тип k2, а значение [v2] - это список элементов типа v2, на выходе получается список пар ключ-значение типов k3 и v3 соответственно.

Предполагается, что все пары с одинаковыми ключами, полученные на выходе map, группируются для формирования входа reduce.

Фреймворк MapReduce должен запустить множество независимых экземпляров функции map и, насколько это возможно, распределить равномерно между ними весь массив входных данных.

### Пример

В приведенном примере на входе 6 пар ключ-значение и 4 экземпляра фуннкции map:


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

✓ Общей сортировки между экземплярами reduce нет.
✓Количество экземпляров reduce может задавать пользователь.

## Combine и partition

Программист также определяет:
1. combine (k2, [v2]) → [(k2, v2)]
✓ Используется в качестве оптимизации для снижения сетевого трафика на reduce.
✓ Мини-reduce, которые выполняются над выходом map.

2. partition (k2, number of partitions) → partition index
✓ Разделяет множество ключей для параллельных операций reduce.
✓ Принимает на вход ключ типа k2 и количество разделов, возвращает индекс разделов. Индекс разделов вычисляется как остаток от деления хэша ключа на количество разделов: hash(key) mod (number of partitions)


--------

# Фреймворк Hadoop и его системные принципы. Лекция 2

## Системные принципы

1. Горизонтальное масштабировнаие
✓ Добавить больше машин к существующему окружению
✓ Уровень приложений поддерживает добавление и удаление узлов
2. Отправка кода к данным
3. Умение обрабатывать ошибки программ и отказы оборудования
4. Инкапсуляция сложности работы распределенных и многопоточных приложений

Hadoop разрабатывается с учетом отказов железа:
1. Применяется репликация данных
2. Осуществляется перезапауск задач

## Инкапсуляция сложности реализации

Имеет небольшое число компонентов:
1. Hadoop common - библиотеки и утилиты
2. HDFS - хранение файлов больших размеров
3. YARN - управление ресурсами, планирование заданий
4. MapReduce

Освобождает от заботы системнгого уровня:
1. Состояние гонки, взаимная блокировка
2. Организация передачи данных
3. Распределение данных
4. Доставка кода