Как я заводил Raspberry Pi

Помимо Arduino у меня уже некоторое время валяется на полке плата Raspberry Pi. Я давно уже хочу с ней поиграться, но всё как-то не доходили руки. Вот, наконец решил попробовать запустить "PC размером с банковскую карту". Собственно "запуск" заключается в заливке на карту памяти SD образа операционной системы (в основном одного из адаптированных дистрибутивов Linux). Некоторое неудобство доставило отсутствие отдельного монитора с HDMI выходом, но и в этом случае процедура установки системы для Raspberry очень стандартная.

Итак, имеем флеш-карту формата SD на 4Гб (согласно документации это минимально возможный объём). Есть два варианта установки системы в Raspberry Pi. Первый способ - залить на флешку NOOBS (New Out Of the Box Software). Это по сути "менеджер установки системы", который позволит установить систему из одного из популярных дистрибутивов по выбору. Второй способ - залить на флешку уже непосредственно образ готовой системы. Второй способ рекомендуется для "опытных пользователей", первый, как утверждают, годится для новичков. Что-ж, пойдём первым путём, надеясь, что он более простой.

Образ NOOBS можно скачать здесь. У меня на ноутбуке установлен Windows, так что инструкции черпаем в соответствующем разделе сайта Rapberry Pi. Так же в соответствии с инструкцией нам понадобится утилита SD formatter. С помощью этой утилиты сначала форматируем карту, куда будет установлена система. Выбираем при форматировании тип файловой системы  Fat32, а так же ставим настройку "FORMAT SIZE ADJUSTMENT" равной "ON". Распаковываем скачанный архив NOOBS. Внутри архива можно обнаружить директорию ./os . В этой директории необходимо стереть все поддиректории кроме Raspbian (там будут директории с именами Arch, Pidora, RISC_OS и.т.д. Все их надо удалить). Затем редактируем файл /os/Raspbian/flavours.json. Удаляем строки, отмеченные курсивом:

{
     "flavours": [
       {
         "name": "Raspbian - Boot to Scratch",
         "description": "A version of Raspbian that boots straight into Scratch"
       },
       {
         "name": "Raspbian",
         "description": "A Debian wheezy port, optimised for the Raspberry Pi"
       }
     ]
   }

Затем в корне распакованного архива стоит подредактировать файлик recovery.cmdline. Нужно добавить волшебное слово silentinstall в конец строки:
Было:

runinstaller quiet vt.cur_default=1 coherent_pool=6M elevator=deadline

Стало:

runinstaller quiet vt.cur_default=1 coherent_pool=6M elevator=deadline silentinstall

После этого копируем содержимое архива на флешку. При загрузке с получившейся карты Raspberry автоматически установит Raspbian. Установка может занять какое-то время и рекомендуется оставить устройство в покое на часик-другой, чтобы быть точно уверенным, что система полностью установлена. Я вставил флешку в Raspberry Pi и подключил её к роутеру Ethernet-кабелем. Включив питание и подождав какое-то время я стал пытаться получить доступ к установленной системе по SSH. Для этого сначала необходим определить IP-адрес Raspberry. Поискав в интернете я нашёл, что MAC-адрес Raspberry Pi должен начинаться с B8:27:EB. Где-то в глубинах веб-интерфейса своего домашнего роутера я нашел список MAC-адресов подключённых устройств вместе с соответствующими IP-адресами, что было весьма кстати, тем более что среди них действительно был MAC-адрес, начинающийся на B8:27:EB. IP-адрес Raspberry оказался равным 192.168.1.12. Теперь остаётся залогиниться туда по SSH, например, с помощью терминала PuTTY. Следует отметить, что мне встречаются сообщения, что SSH-сервер не включен по умолчанию в системе Raspbian установленной из NOOBS 1.3.7, и понадобятся дополнительные действия для того, чтобы получить доступ. Это противоречит моему опыту (правда с версией NOOBS 1.3.9), в моём случае SSH-сервер оказался включен в "свежей" системе. По умолчанию в системе создаётся пользователь pi с паролем raspberry:

Всё! После этого я увидел, что плата работает и у меня есть контроль над системой, установленной в ней через SSH. Остаётся придумать и сделать с ней что-нибудь полезное.

Как я подключал модуль Bluetooth к Ардуино

Хочу рассказать короткую историю о том, как я ходил по граблям, пытаясь подружить плату Arduino UNO и модуль Bluetooth HC 06.

Чтобы протестировать взаимодействие между PC/смартфоном и платой Arduino UNO я после недолгих поисков по интернету собрал вот такую нехитрую схему:

В общем-то всё просто: подаём напряжения +5В, +3.3В и "землю" (GND) с Ардуино на модуль Bluetooth, для передачи же данных модуль соединяется с аппаратным последовательным портом на Arduino. Выход (Tx) на Ардуино подключается к входу (Rx) модуля (по этой линии данные передаются из Ардуино в модуль Bluetooth) и наоборот, для передачи из модуля в Ардуино подключаем (Tx) на плате HC 06 к (Rx) Ардуино. Сигнал с Ардуино подаётся на модуль через делитель напряжения, так как Bluetooth-модуль ожидает уровень сигнала 3.3В, а Ардуино выдаёт 5В. R1 я взял равным примерно 5 кОм, R2, соответственно, 10 кОм (на самом деле 5.1 кОм и 11 кОм).

От прошивки в Ардуино в этом опыте требуется только лишь возможность проверить, что данные шлются в обе стороны. Я реализовал следующую логику: если Arduino получает через Bluetooth символ '1', то в ответ высылается строчка "Hello". Eсли Arduino получает через Bluetooth символ '2', то просто мигаем встроенным светодиодом, который подключен к пину 13 на плате Arduino UNO. В ответ на любой другой символ присылается знак вопроса.

Эта схема никак не хотела работать! Было похоже, что данные не пересылаются в Ардуино. Решил попробовать, шлются ли данные в обратном направлении. Переписал скетч таким образом, чтобы Ардуино просто постоянно слал тестовую строчку с данными в модуль, и смог без проблем прочитать их на своём ноутбуке (о том, как подключаться с PC под управлением Windows пойдёт речь ниже).

Потратив 2+ часа на проверки и поиски в интернете, я нашёл, что нельзя пользоваться Rx и Tx пинами на Ардуино когда он подключен к USB-порту компьютера (я использую USB кабель для питания всей схемы). Дело в том, что при подключении USB-кабеля к ардуино, выходы контроллера Rx и Tx используются для связи с компьютером через USB (правда, сигнал Tx продолжил работать и в этом случае, так как послать данные из Ардуино в PC всё-таки получилось). При связи с другими устройствами через аппаратный последовательный порт необходимо подавать питание через разъём внешнего питания (7-12 Вольт). Я полагаю, все это очевидные вещи для мало-мальски опытного пользователя Arduino (коим я пока не являюсь). Надеюсь этот пост поможет кому-то из начинающих сэкономить время и избежать похожих проблем в будущем.

С программной реализацией последовательного обмена разработчик волен выбирать любой пин цифрового ввода/вывода платы Ардуино. Я выбрал десятый пин для приёма информации через Bluetooth, и 11-й, соответственно, для отправки данных. Схема теперь выглядит так (на схеме ошибка, 10-й и 11-й выводы платы поменяны местами):

В реальном мире это выглядит так:

Код скетча почти не изменился, так как программная реализация последовательного обмена имеет очень похожее API:

Не буду останавливаться слишком подробно на на процедуре сопряжения PC с нашим новым "гаджетом". В случае Windows всё как обычно: подключается USB-донгл, осуществляется поиск Bluetooth устройств. В моём случае устройство называлось HC-06, но имя можно поменять с помощью соответствующей AT-команды. С точки зрения программ наше устройство видится как ещё один COM-порт в системе. В свойствах устройства можно увидеть, какой номер присвоен "виртуальному COM-порту" сопряженного устройства. В моём случае получился порт COM-28. Для того чтобы слать и принимать данные в COM-порт для Windows существует множество программ. Я использовал привычный мне терминал PuTTY. Последовательность действий такова: запускаем PuTTY, выбираем Connection type: Serial и идем в категорию "Serial"

'

Здесь выставляем вот такие параметры:

Номер COM-порта может отличаться, его необходимо смотреть в свойствах устройства. Нажимаем кнопку "Open" чтобы сразу соедениться с устройством, либо идём в категорию Session, там придумываем название сессии (у меня, например, ardu-bt) и печатаем его в поле Saved sessions, затем нажимаем кнопку "Save". Это сохранит настройки сессии и позволит не конфигурировать ком-порт при каждой последующей попытке приконнектится к устройству. Достаточно будет просто выбрать сохранённую сессию в списке. После того, как программа-терминал соеденится с устройством, светодиод на модуле Bluetooth должен перестать мигать и начать светить непрерывно. В окне с сессией можно слать команды устройству, нажимая на клавиши. При нажатии на клавишу 1 устройство должно вернуть строку "Hello", при нажатии ина колавишу 2 -- пять раз помигать светодиодом на Arduino. При нажатии на другие клавиши устройство отвечает знаком вопроса. Типичный пример сессии:

Итак, удалось научится сопрягать Ардуино с ПК через Bluetooth! Теперь остаётся придумать какой-нибудь более интересный проект.

ChWiSe.Net: Проект химического поиска по Википедии

О чём проект

Хочу рассказать о chwise.net - созданном мной недавно вебсайте, предназначенном для поиска статей о химических веществах в википедии. Особенностью данного сервиса является то, что поддерживается как полнотекстовый поиск по ключевым словам, так и поиск по структурной похожести молекул. В настоящее время проиндексированы только лишь статьи на английском языке. Если проект будет пользоваться интересом, то он получит дальнейшее развитие в сторону поиска статей и на других языках.

Итак, что представляет собой описываемый сервис? На главной и единственной странице можно увидеть два поля ввода: одно отвечает за текстовую часть запроса,
другое - за химическую структуру-образец, или молекулярная часть запроса. Можно ввести структуру-образец прямо с клавиатуры в формате SMILES или создать её в редакторе химических формул (кнопка "Start structure editor").

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

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

У проекта есть твиттер, так что если интересно следить за новшествами - можно подписываться.

Что "под капотом"

ChWiSe.Net - opensource проект, опубликованный под лицензией GPL. Он базируется на моём плагине для Lucene (MolecularLucene), который позволяет искать похожие химические структуры. Исходный код доступен на GitHub под гораздо более свободной лицензией Apache. При разработке ChWiSe.Net я активно использовал opensource наработки "от третьих лиц": помимо упомянутого движка Lucene жизненно важные компоненты ChWiSe.Net - редактор химических формул из ChemDoodle Web Components (двойная лицензия: GPL/коммерческая) и Chemistry Development Kit (CDK). Ещё стоит упомянуть Twitter Bootstrap, jQuery, клиентский шаблонный движок EJS, Bootsrap Paginator и парсер вики-разметки Sweble.

В настоящее время ChWiSe.Net хостится в Google Appengine (GAE). Поисковый индекс в GAE хранится в статических данных веб-приложения, что является наиболее простым решением если обращение к индексу происходит только для чтения. Для того, чтобы библиотека Lucene версии 4.3.1 могла работать со статическим индексом в среде GAE, тербуется слегка пропатчить исходный файл RamUsageEstimator.java в исходниках Lucene и пересобрать Lucene.

Ссылки

http://www.youtube.com/watch?v=V0ddipGhPc0 - Короткая видоперзентация на английском

Поиск по структурам молекул на основе Lucene и Chemical Development Kit

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

Размышления на эту тему привели к посту на habrahabr.ru и небольшому проектику на github. Возможно, кому-то пригодится.

Scala в гостях у Hadoop. Часть 2. Запускаем кластер на Amazon EC2.

В предыдущем посте я рассказвыл о фреймворке Scoobi. В качестве иллюстрации я написал небольшое MapReduce-приложение, которое вычисляет число π/4. Теперь я собираюсь рассказть о том, как запустить его на кластере Amazon EC2. В этом посте описана пошаговая процедура запуска Scoobi-приложения, начиная от аренды сервера на Amazon и заканчивая получением результата Монте-Карло-вычислений.


Для создания Hadoop-кластера будем использовать Apache Whirr. Для работы Whirr требует ssh-клиент, поэтому будем запускать его на Linux-машине. Лично у меня на компьютере стоит Windows, поэтому я арендую на Amazon-е ещё один Linux инстанс, с которого буду управлять Hadoop-кластером с помощью Whirr (ещё одним относительно простым решением было бы создать виртуальную Linux-машину на основе VMWare или VirtualBox).

Создаём машину в Amazon EC2 для админимтрирования кластера Hadoop

Итак, сначала арендуем машину для запуска Whirr. Тут нет ничего сложного. Регистрируемся на Amazon AWS. Затем идём в AWS Management Console, затем выбираем пункт EC2 Virtual Servers in the Cloud:

Жмём на кнопку "Launch instance". Затем выбираем "Classic wizzard" (хотя можно воспользоваться и другим мастером). Затем выбираем Amazon Linux AMI.

Дальше жмём "Continue". Так как нам надо достаточно мало ресурсов, только для администрирования кластера, а не для самих вычислений, из соображений самой низкой цены цены выбираем меняем "T1 Micro" на "M1 Small" в поле Instance Type:

Далее жмём несколько раз "Continue". Доходим до страницы, на которой нам предложат ввести теги (метки) для запускаемого инстанса. Они нужны главным образом для удобства. Не пренебрежём этой возможностью, определим имя инстанса (hadoopmanager):

Жмём ещё раз "Continue". На следующей странице предлагается создать пару ключей. Вводим удобное название (например, у меня - whirrkey) и нажимаем "Create & Download your Key Pair"

Сохраняем сгенерированный файл с расширением "pem", и ни в коем случае его не теряем. На следующей странице предлагается создать "Security group". Security group определяет по каким портам разрешено коннектится к инстансу. Как минимум необходимо открыть порт 22, чтобы можно было соединяться с сервером с помощью SSH. Если я не ошибаюсь, в существующих Security group-ах по умолчанию создаётся группа default, в которой тоже открыт доступ по SSH.

Настройки групп можно поменять потом, открыв нужные или закрыв ненужные порты.

Далее жмём "Continue", затем "Launch". Наблюдаем сообщение: "Your instances are now launching". Жмём "Close". Наблюдаем список запущенных инстансов с только что созданной нами виртуалкой.

Выбрав в списке созданную виртуалку, можно узнать её доменное имя, которое мы будем использовать для доступа к машине по SSH.

Теперь остаётся получить доступ к созданному серверу, например с помощью PuTTY. Для этого нам понадобится ключ whirrkey.pem, который мы сохранили.

Если использовать популярный Windows SSH-клиент PuTTY, то надо сначала запустить PuTTYGen. Запускаем PuTTYGen, загружаем сохранённые pem-файл, нажав кнопку "Load".

После того, как pem-файл загружен, нажимаем "Save private key", и сохраняем ключ в виде файла с расширением ppk (я назвал его whirrkey.ppk). 

Теперь можно использовать PuTTY для доступа к созданному серверу.

Вводим адрес нашей машины в поле "Host name (or IP address)":

Так же указываем наш ключ whirrkey.ppk для аутентификации:

 Жмём Open. Логинимся как пользователь ec2-user. Пароль вводить не потребуется.

Настраиваем окружение для администрирования Hadoop-кластера

В соответствии с документацией Scoobi для запуска нам понадобится Hadoop CDH4, выпускаемый компанией Cloudera. Это по сути тот же Apache Hadoop определённой версии, в который компания Cloudera добавляет наиболее важные багфиксы и фичи из последующих, возможно ещё не выпущеных релизов Hadoop. Дистрибутивы Clouder Hadoop (CDHx) можно скачать с сайта cloudera.com Компания зарабатывает на технической поддержке облачных технологий, основанных на Hadoop.

Разворачивать и конфигурировать кластер "по одной ноде" довольно хлопотно. К счастью, существуют средства вроде Apache Whirr, которые заметно облегчают этот процесс. Необходимо задать сколько и каких hadoop-нод мы хотим в своём кластере, а Whirr сделает всю рутинную работу: арендует под них машины на Amazon, развернёт и сконфигурирует на них hadoop. По этому пути мы и пойдём.

Устанавливаем Hadoop CDH4

>cd ~

>wget http://archive.cloudera.com/cdh4/one-click-install/redhat/6/x86_64/cloudera-cdh-4-0.x86_64.rpm

>sudo yum --nogpgcheck localinstall cloudera-cdh-4-0.x86_64.rpm

>sudo yum install hadoop-yarn-resourcemanager

Устанавливаем Apache Whirr:

>mkdir ~/opt

>cd ~/opt

>wget http://www.sai.msu.su/apache/whirr/whirr-0.8.2/whirr-0.8.2.tar.gz

>tar -xvf ./whirr-0.8.2.tar.gz

Конфигурируем Apache Whirr:

>export AWS_ACCESS_KEY_ID=$AWS_ACCESS_KEY_ID

>export AWS_SECRET_ACCESS_KEY=$AWS_SECRET_ACCESS_KEY

Значения $AWS_ACCESS_KEY_ID и $AWS_SECRET_ACCESS_KEY  можно узнать здесь: https://portal.aws.amazon.com/gp/aws/securityCredentials. Эти параметры можно указать не только через переменные окружения, но и в файле ...

Генерируем ключи:

ssh-keygen -t rsa -P '' -f ~/.ssh/id_rsa_whirr

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

whirr.cluster-name=scoobicluster

whirr.instance-templates=1 hadoop-jobtracker+hadoop-namenode+ganglia-monitor+ganglia-metad,3 hadoop-datanode+hadoop-tasktracker+ganglia-monitor

whirr.java.install-function=install_openjdk
whirr.java.install-function=install_oab_java

whirr.hadoop.install-function=install_cdh_hadoop
whirr.hadoop.configure-function=configure_cdh_hadoop
whirr.yarn.configure-function=configure_cdh_yarn
whirr.yarn.start-function=start_cdh_yarn
whirr.mr_jobhistory.start-function=start_cdh_mr_jobhistory
whirr.env.REPO=cdh4
whirr.env.MAPREDUCE_VERSION=2

whirr.provider=aws-ec2
whirr.identity=${env:AWS_ACCESS_KEY_ID}
whirr.credential=${env:AWS_SECRET_ACCESS_KEY}
whirr.hardware-id=m1.small

whirr.cluster-user=whirr
whirr.private-key-file=/home/ec2-user/.ssh/id_rsa_whirr
whirr.public-key-file=/home/ec2-user/.ssh/id_rsa_whirr.pub

Теперь, когда все настройки заданы, остаётся запустить наш кластер:

Запускаем кластер

cd ~/opt/whirr-0.8.1

bin/whirr launch-cluster --config ~/hadoop.properties

В результате будет сгениерированно много вывода в консоль, в самом конце будут видны адреса созданных нод кластера. Убедиться, что у нас запущен кластер можно так же в панели управления AWS:

Теперь нужно собрать непосредственно то, что будем запускать на кластере, то есть вычисление pi/4, о котором я писал раньше.

Устанавливаем  sbt + git, собираем Scoobi-проект

Теперь нам нужно собрать наше Scoobi-приложение, получив в результате jar-файл. Как и для многих других scala-приложений, для сборки Scoobi-программ используется SBT.

Устанавливаем git из репозитория:

>sudo yum install git

Устанавливаем SBT:

>cd ~/opt

>wget http://scalasbt.artifactoryonline.com/scalasbt/sbt-native-packages/org/scala-sbt/sbt//0.12.3/sbt.tgz

>tar -xvf sbt.tgz

>export PATH=$PATH:~/opt/sbt/bin

Скачиваем исходники с помощью git

>cd ~/

>git clone https://github.com/AlexanderSavochkin/MCwithScoobi.git

Теперь собственно сборка jar-файла

>cd ./MCwithScoobi
>sbt assembly

Если всё прошло окей, то в директории проекта появится поддиректория target, в которой поямвитя файл MCwithScoobi-assembly-0.1.jar. Его-то мы и будем запускать в hadoop-кластере.

Запускаем вычисления в кластере

cd target
hadoop jar MCwithScoobi-assembly-0.1.jar

В результате в текущей директории появится поддиректория output, в которой в файле с названием типа ch20out2-r-00000 будет храниться результат вычисления в кластере. Он представлен в примерно таком виде:

(1,ValueEstimator(100000,0.7852700000000121,1.686227133271277E-6,-2.051820047199726E-14))

Здесь число 0.7852700000000121 - наша оценка пи/4, а следующее число - 1.686227133271277E-6 - оценка квадрата отклонения (дисперсии) оценки числа π/4.

Останавливаем кластер

Когда кластер нам больше не нужен, остановить его можно командами:

cd ~/opt/whirr-0.8.2
bin/whirr destroy-cluster --config ~/hadoop.properties


Результат как обычно можно увидеть в панели управления AWS.

Заключение

Было показано, как арендовать машину на Amazon EC2 (с которой осуществлялось администрирование Hadoop-кластера), как запустить и остановить кластер с помощью Apache Whirr и как запустить в этом кластере Scoobi-приложение. Само собой разумеется, есть другие способы сделать то же самое. Например, если ваша локальная машина работает под Linux, вы можете пропустить шаг с арендой Linux-сервера, и запускать Whirr на своей локальной машине. Можно вместо аренды Linux-машины на Amazon использовать виртуальную машину, можно сконфигурировать кластер без Whirr и.т.д. Короче говоря, здесь показан лишь один из возможных путей.

Особенность нашего "игрушечного" MapReduce-приложения было то, что оно не использует входные данные, хранимые в распределённой файловой системы HDFS, и не сохраняет в HDFS результаты, поэтому рассмотрение кластера как именно распределённого хранилища данных осталось за бортом.  Большинство hadoop-приложений всё-таки используют какие-то "большие" входные данные. Возможно, как-нибудь позже я ещё вернусь к этой теме. Кроме этого в будущем хотелось бы коснуться возможности арендовать на Amazon-е машины с процессорами NVIDIA Tesla, которые предоставляют невиданную мощь для решения параллельных числодробительных задач.

Ссылки

Более подробне описание процедуры запуска Hadoop CDH4 с помощью whirr

http://www.cloudera.com/content/cloudera-content/cloudera-docs/CDH4/4.2.0/CDH4-Installation-Guide/cdh4ig_topic_4_4.html

Scoobi: Scala в гостях у Hadoop

Пара вводных слов: Big data, Map-Reduce, Hadoop

Без сомнения, "big data" сегодня одна из "горячих" тем в мире IT.

Эти обстоятельства заставляют и меня посматривать в сторону соответствующих технологий и интересоваться новостями в области "больших данных".

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

• Шаг 1. Входные данные разбиваются на "куски", которые могут быть обработаны параллельно. Например:
      -входные данные - это множество отдельных файлов. Естественно попытаться рассматривать каждый файл как отдельный "кусок данных" и обрабатывать параллельно
      -входные данные - многострочный файл, каждая строка которого может быть обработана параллельно. Можно разбивать его на отдельные строки или на диапазоны строк.
      -входные данные - диапазоны чисел, для которых нужно провести вычисления
• Шаг 2. К каждому "куску" применяется процедура "Map", результат которой -- множество пар ключ-значение (K, V).     Вычисления Map для разных данных выполняются параллельно (часто в кластере на разных машинах).
• Шаг 3. Результаты группируются по ключу.
• Шаг 4. Сгруппированные по ключу результаты направляются на вход процедуры Reduce, которая "сворачивает" данные для каждого ключа в единый результат. Если операция Reduce ассоциативна, то она может быть эффективно распараллелена.

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

"Родным" языком Hadoop является Java, поэтому самый прямой путь - реализовать процедуры Map и Reduce на Java. Однако есть возможность использовать и другие языки программирования с помощью Hadoop Streaming.


Подобно тому, как изучение нового языка программирования обычно начинают с написания программы, выводящей на экран "Hello world", знакомство с MapReduce начинают с задачи подсчёта слов в тексте. Пусть в распределённой файловой системе лежит множество файлов - текстовых документов. Наша задача состоит в том, чтобы подсчитать, сколько раз встречается каждое слово во всех документах.

Наша процедура Map принимает на вход документ, разбивает его на отдельные слова и порождает для каждого слова w пару (w,1). Слово w здесь является ключом, 1 - значением (См. шаг 2 в описании Map-Reduce).

На вход нашаей процедуре Reduce подаётся слово и список . Этот список формируется из объединённых результатов всех выполнений процедуры Map. Если вы используете Hadoop, то вам не нужно явно заботиться об этой группировке. Это происходит автоматически, "за кулисами".

Для реализации некоторых типичных задач можно обойтись и без программирования на Java, воспользовавшись Apache Pig, который по сути тоже представляет собой язык программирования, но более высокоуровневый и изначально ориентированный на идеологию MapReduce. Можно скомбинировать PIG и Java, написав "высокоуровневую часть" на Pig, а некоторые детали реализовать в виде UDF (User-Defined Function), написанных на Java.

Scoobi. Делаем вещи проще и быстрее с помощью Scala.

Здесь я хочу описать другой путь, основанный на языке Scala и библиотеке Scoobi. Поскольку Scala совместима с Java, и из Scala можно просто напрямую использовать объекты Java, мы можем практически построчно портировать MapReduce-код c java на scala, однако такой подход на мой взгляд не раскрывает в полной мере преймуществ Scala.

Ориентированный на Scala открытай фреймворк Scoobi разработан в NICTA. Scoobi позволяет очень кратко и выразительно описывать Map-Reduce вычисления. Так, например, подсчёт разных слов в тексте запишется так (взято из примеров Scoobi):

import com.nicta.scoobi.Scoobi._

val lines = fromTextFile("hdfs://in/...")

val counts = lines.flatMap(_.split(" "))
                .map(word => (word, 1))
                .groupByKey
                .combine(_+_)

persist(counts.toTextFile("hdfs://out/...", overwrite=true))

Разберём этот код: важной частью API Scoobi является trait (аналог интерфейса Java) DList[T]. Этот тип представляет "распределённый список", который может жить на нескольких машинах Hadoop-кластера. Функция fromTextFile возвращает распределённый список строк файла типа DList[String]. К этому списку применяется метод flatMap(_.split(" ")) . В результате на выходе получаем распределённый список отдельных слов файла (того же типа:  DList[String]). К получившемуся списку применяется метод  map(word => (word, 1)) . Здесь мы генерируем распределённый список тех самых пар ключ-значение, о которых упоминалось выше, на шаге 2 описания вычислений MapReduce. Ключом у нас являетсяы слово текста, а "значением" -- 1. Метод groupByKey соответствует шагу 3.

Здесь я хочу привести свой собственный пример, использующий Scoobi: вычисление числа π (пи) методом Монте-Карло. Помимо вычисления оценки самого числа π, мы будем вычислять и среднеквадратичное отклонение этой оценки, что позволит нам судить о точности результата.

Для вычисления числа π мы будем генерировать пары (x,y) псевдослучайных чисел, каждое из которых принадлежит отрезку [0,1]. Площадь белой четверти круга на рисунке равна π/4, а площадь ограничивающего квадрата равна 1.

Следовательно, если бросать случайные точки в квадрат, то отношение числа всех точек к числу точек, попавших в четверть-круг будет стремиться к π/4. Это, конечно, весьма тривиальный и непрактичный пример применения метода Монте-Карло, но это в данном случае и хорошо, так как позволит сосредоточится в большей степени на технических деталях, а не на математике.

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

Для реализации этого подхода я создал scala-класс ValueEstimator.

//Класс "оценки числового значения".
//Содержит следующие поля:
//numTests - количество измерений
//mean - среднее значение
//variance - дисперсия
//meanError - накопленная ошибка
case class ValueEstimator(numTests:Long, 
                          mean:Double, 
                          variance:Double, 
                          meanError:Double) {
   //Комбинирует "этот" экземпляр ValueEstimator с другим,
   //Возвращает полученное значение оценки.
   def combineEstimations( other:ValueEstimator ):ValueEstimator = ...
}

//Это нужно написать чтобы Scoobi "понимал" наш класс
implicit val valueEstimatorFmt = mkCaseWireFormat(ValueEstimator, 
                                        ValueEstimator.unapply _)

Это позволит мне продемонстрировать ещё одну мощную возможность Scoobi: распределённый список DList может содержать элементы не только каких-то предопределённых типов, но и наших case-классов.

И так, вот наша реализация вычисления методом Mонте-Карло с помощью Scoobi:

package scoobimc

import scala.util.Random
import com.nicta.scoobi.Scoobi._
import com.nicta.scoobi.io.func.FunctionInput

import MCUtils._

object PiMonteCarlo extends ScoobiApp {

  val numSequencies = 10
  val generateSequenceLength = 10000

  def run() = {
    val input = FunctionInput.fromFunction(numSequencies)( x=>x )

    val pi = input.flatMap( generateRands _ )
             .map( checkIfInside )
             .groupByKey
             .combine( 
                (x:ValueEstimator, y:ValueEstimator) => 
                    x combineEstimations y 
              )

    //Сохраняем результат
    persist( toTextFile(pi, "output", overwrite=true))
  }

  //Проверяют, что точка x лежит внутри единичного четверть-круга
  def checkIfInside( x:(Double, Double) ) =
    if ( (x._1 * x._1) + (x._2 * x._2) < 1.0 )
      (1,ValueEstimator(1, 1.0, 0.0,0.0))
    else
      (1,ValueEstimator(1, 0.0, 0.0,0.0))

  //Генерирует случайные точки в единичном квадрате
  def generateRands( seed:Int ) = {
    val rand = new Random(seed)
    (1 to generateSequenceLength) map ( _ => (rand.nextDouble(),rand.nextDouble()) )
  }
}

как и в случае с подсчётом слов, разберём, что же здесь происходит. Вызов FunctionInput.fromFunction(numSequencies)( x=>x ) генерирует DList c последовательностью целых чисел от 0 до numSequencies. Затем к этому списку применяется метод flatMap( generateRands _ ) , который сопоставляет каждому числу списка последовательность псевдослучайных двумерных точек, длинной generateSequenceLength. Функция flatMap выдаёт эти последовательности в сконкатенированном виде, то есть единым DList-ом, который имеет длинну numSequencies*generateSequenceLength. К этому результату применяется метод map( checkIfInside ). На выходе, как обычно, получается DList, хранящий пары ключ-значение, где ключ - еденица, а значения -- обекты типа ValueEstimator. Для точек, попавших в четверть-круг, оценка 1, для непопавших - 0.

Нам остаётся найти среднее значение всех числовых оценок, которое должно стремиться к π/4.

Операция groupByKey в данном случае тривиальна, так как все элементы имеют один и тот же ключ, равный единице. Метод combine скомбинирует все наши ValueEstimator-ы, используя определённый нами метод combineEstimations. На выходе получим оценку среднего и дисперсии искомой величины, π/4. Переменная pi будет представлять собой маленький DList с единственной парой ключ-значение. Ключ - единица, значение - окончательный ValueEstimator числа π/4.

Надеюсь, этим постом мне удалось показать, что Scoobi является очень выразительным средством для организации распределённых MapReduce вычислений.

В одном из следующих постов я планирую написать, как запустить описанное выше вычисление числа π на кластере в Amazon EC2 из нескольких машин.

Ссылки

https://github.com/AlexanderSavochkin/MCwithScoobi - здесь выложены исходные коды к этому посту
Introducing Scoobi and Scalding: Scala DSLs for Hadoop MapReduce

Comparison of Hadoop Frameworks - обзор и сравнение фреймворков для Hadoop. Упоминается Scoobi и ряд альтернатив, ориентированных на Java/Scala/Clojure...

Разложение глюконата кальция в пламени сухого горючего

Разложение глюконата кальция в пламени сухого горючего

Недавно попался в интернете видеоролик с эффектным химическим опытом. Не смог удержаться и не повторить.

Видео ускорено в 4 раза.