Компания Google провела эксперимент по сортировке 1 ПБ данных при помощи фреймворка MapReduce. Данные были представлены в виде 10 триллионов записей, каждая длиной 100 байт. Для сортировки были задействованы 4000 компьютеров. Этот беспрецедентный для такого типа задач объем данных удалось отсортировать за 6 часов 2 минуты.

В ходе эксперимента сотрудникам Google пришлось решать проблему с размещением 1 ПБ данных. Дело в том, что при каждом новом запуске сортировки, выходил из строя хотя бы один из 48 000 используемых жестких дисков. В итоге, было решено дать Google File System команду хранить по три копии каждого файла на разных жестких дисках.

Сортировка меньшего объема данных в 1 ТБ на 1000 компьютерах заняла 68 секунд. Этим самым в Google побили предыдущий рекорд по сортировке аналогичного объема данных, составляющий 209 секунд на 910 компьютерах.

Для сравнения, общий объем фотографий, хранимых в Facebook, составляет 1 ПБ, Большой Адронный Коллайдер будет производить 15 ПБ данных в год, а Google обрабатывает около 20 ПБ данных в день.

В дополнение к сервисам Amazon Elastic Compute Cloud (EC2) и Amazon Simple Storage Service (Amazon S3) компания Amazon сообщила об открытии нового сервиса Amazon Elastic MapReduce, который на данный момент пребывает в статусе беты.

Elastic MapReduce — вебсервис, который позволят с легкостью обрабатывать огромные количества разнообразных данных. Сервис основан на совместном использовании EC2 и S3, а также фреймворка Hadoop.

Инженер из компании Google весьма критически отозвался о технологиях Microsoft в области распределённой вычислительной инфраструктуры для веб-приложений.

Маленький скандальчик случился на конференции Structure 09, которая посвящена облачным вычислениям. Всё началось с выступления Наджама Ахмада (Najam Ahmad), главного менеджера по глобальным сетевым сервисам Microsoft. Он подробно рассказал, как Microsoft пытается увеличить производительность множества своих сервисов. Мол, проблема в огромном их количестве, так что невозможно подобрать настройки так, чтобы все эти сервисы одинаково эффективно работали на одной платформе. Приходится фрагментировать инфраструктуру, ставить разные серверы с разными настройками для отдельных приложений, таких как Messenger или Virtual Earth, и оптимизировать их по отдельности. Он подробно рассказал, как тщательно они сейчас оптимизируют Virtual Earth.

Сразу после этого слово взял Виджай Гилл (Vijay Gill), старший инженер по архитектуре из Google, и, как говорится, пропесочил конкурента по полной программе.

В январе 2007, двое убеленных сединами, RDBMS специалиста, David J. DeWitt и Michael Stonebraker опубликовали страшную вещь. А они действительно убеленные сединами, и действительно специалисты, так вот, они покусились на святое, на MapReduce — см. “MapReduce: A major step backwards” В статье они критикуют MapReduce вообще и называют его шагом назад по сравнению с RDBMS. Само собой, в коментах молодые герои их смешали с говном. Впочем были и аргументированные ответы — см. “Databases are hammers; MapReduce is a screwdriver” И тут Девиду и Майклу показалось мало, они публикуют статью-ответ на всю критику сразу см. “MapReduce II”. Все эти статьи очень интересное чтиво, включая коментарии.

Рекомендую.

Интересное вчерашнее объявление от Myspace.com 

Сегодня мы открываем в Open Source Qizmt, внутренний фреймворк для распределенных вычислений, созданный командой Data Mining в Myspace. Qizmt может быть использован для многочисленных операций, которые требуют процессинга больших объемов данных. Таких как фильтрация в системе рекомендаций и аналитика.

Некоторые источники уже отчитались по этому поводу и написали, что это фреймворк для системы рекомендаций. Это не так. Это полноценная имплементация MapReduce, написанная для Windows.

Не так часто любителей .NET сталкиваются с open source проектами такого уровня. Несмотря на то, что система заявленая как Alpha заявлено довольно много функциональности (что неудивительно, поскольку это вроде как работающий на myspace framework)

• Быстрая разработка mapreduce jobs в C#
• Легкий инсталлер
• Встроенный IDE/Debugger (включая step through отладку jobs на кластере)
• Из любой машины в кластере:
• Cluster Assembly Cache (CAC) – кеш .NET assemblies для mapreduce jobs
• 3 вида jobs:
  — Mapreduce – set логика для больших объемов данных
  — Remote – для тех задач, которые не подходят под шаблон mapreducer
  — Local – оркестрация связей между Mapreduce и Remote jobs
  
• 3 способа обмена данных в mapreduce
  
  — Отсортированные – key/value пары равномерно отсортированы по кластеру
  — Сгруппированные – неотсортированные, но похожие пары key/value на одному reducer
  — Сортированные по хэшу – супер быстрый способ сортировки случайных данных
  

Выглядит все это довольно внушительно, хотя у думаю сейчас уже не особо важно на чем такие frameworks написаны. Используют их все равно платформо независимыми методами – легкими сервисами а-ля REST/REST2. Говорят тот же Bing использует Hadoop. Но в любом случае приятно что коллеги из Myspace поделились кодом.

Да, код на гуглокоде

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

С некоторой статистикой вы можете ознакомиться в ЖЖ главного организатора Дмитрия Завалишина из Digital Zone.

Вкратце по темам – MongoDB, Clojure, MapReduce и Azure. В ходе первоначального знакомства всех пришедших стало известно, что основная часть людей пришла послушать про мир без SQL в лице MongoDB.

Сначала расскажу об изменениях в SDKs, а потом о MapReduce.

Итак,
— Увеличение квот TaskQueue с 50 запросов на приложение до 50 запросов на очередь, в последующих резилах ожидаются дальнейшие улучшения этого сервиса.
— Возможность настройки лимита хранилища для TaskQueue.
— Прекомпиляция для Python, в настоящее время отключена по умолчанию, включается в конфиге.
— Добавлены программные интерфейсы для доступа к blob-файлам напрямую из приложения. Идет работа над созданием и редактированием blob из приложения, пока не готово.
— Для local python SDK задания теперь выполняются автоматически.

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

Давно хотел рассказать про MapReduce, а то как ни взгляшешь на подобное — такая заумь, что просто ужас берет, а на самом деле очень простой и полезный подход для многих целей. И реализовать самому — не так уж и сложно.

Сразу скажу — топик — для тех, кто не разобрался что такое MapReduce. Для тех, кто разобрался — полезного тут ничего не будет.

Начнем с того как собственно родилась лично у меня идея MapReduce (хотя я и не знал, что он так называется, и, разумеется, пришла она мне куда позже чем Гугловсцам).

Сначала опишу как она рождалась (подход был неправильный), а потом как надо правильно делать.

Как посчитать все слова в Википедии (неправильный подход)

А родилась она, как и, наверное, везде — для подсчета частоты слов, когда обычной памяти не хватает (подсчет частоты всех слов в Википедии). Вместо слова «частота» тут скорее должно быть «количество вхождений», но для простоты оставлю «частота».

В самом простом случае мы можем завести хеш (dict, map, hash, ассоциативный массив, array() в PHP) и считать в нем слова.

$dict['word1'] += 1

Но что делать когда память под хеш кончится, а мы посчитали только одну сотую всех слов?

Чтобы не откладывать в долгий ящик сразу порассказываю несколько других примеров для MapReduce, обещанные в топике "MapReduce без зауми". (Если не понимаете полностью что такое MapReduce — прочитайте тот топик сначала! Без него не разберетесь)

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

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

Входящие ссылки

Допустим у нас есть Интернет. В Интернете есть исходящие ссылки.

Допустим на входе у нас есть такие данные об ИСХОДЯЩИХ ссылках, собранные нашим паучком:

habrahabr.ru -> thematicmedia.ru, apple.ru, microsoft.com, ubuntu.com, yandex.ru
thematicmedia.ru -> habrahabr.ru, autokadabra.ru
autokadabra.ru -> habrahabr.ru, yandex.ru

Т.е. мы знаем, что Хабр ссылается на Apple, MS, Ubuntu и Яндекс но кто ссылается на Хабр? Да, вопрос примитивный, но все же разложим на MapReduce. Дальше будет интереснее и этот пример понадобится.

Те, кто включил в своём приложении на GAE поддержку сессий, знают, что сессии, во-первых, записываются в datastore, а во-вторых, автоматически оттуда не исчезают. От протухших сессий надо как-то избавляться самостоятельно.

Я как-то не заботился о протухших сессиях, и за полтора года их накопилось полтора миллиона штук. Недавно размер хранимых в datastore данных превысил бесплатную квоту и, так как 99% было занято сессиями, я решил поудалять протухшие.

В Калифорнийском университете в Беркли разработали фреймворк Spark для распределённых вычислений в кластерах. На некоторых задачах он превосходит Hadoop в 10-30 раз, сохраняя при этом масштабируемость и надёжность MapReduce.

Увеличение производительности до 30х возможно на специфических задачах, в которых идёт постоянное обращение к одному и тому же набору данных. Например, это интерактивный дата-майнинг и итерационные алгоритмы, которые активно используются, например, в системах машинного обучения. Собственно, для этих двух задач проект и создавался. Но Spark превосходит Hadoop не только в системах машинного обучения, но и в традиционных приложениях по обработке данных.

Организация Common Crawl сделала щедрый подарок разработчикам и компаниям, которые работают в области поиска и обработки информации. В открытый доступ на Amazon S3 выложен индекс из 5 миллиардов веб-страниц с метаданными, PageRank и графом гиперссылок.

Если вы видели в логах веб-сервера CCBot/1.0, то это их краулер. Некоммерческая организация Common Crawl выступает за свободу информации и поставила целью сделать общедоступный поисковый индекс, который будет доступен каждому разработчику или стартапу. Предполагается, что это приведёт к созданию целой плеяды инновационных веб-сервисов.

Я продолжаю свое погружение в Эрланг. Уже есть хитрый план переписать один из наших сервисов для мониторинга на Эрланге. Мы тут осваиваем облака Windows Azure и Amazon EC2 в качестве платформы для некоторых продуктов и внутренних задач типа QA, поэтому возможность использовать много ядер и машин без переписывания кода выглядить перспективно.

Итак, для начала простой, но реальный пример — есть проект ~2000 файлов. Надо составить список используемых переменных окружения. То есть найти вхождения строк «getenv(...)» и «GetVariable(...)» (это наш wrapper) и выдрать из них параметр.

Задача незамысловатая и давно решается программой на C++, которая даже обход каталогов не делает, а просто вызывает юниксовый «find», генерирующий список файлов по маске, и затем по списку лопатит файлы. На 2000 файлах работает пару секунд в один поток.

Теперь Эрланг. Тут хочется замутить что-нибудь более кучерявое, чем последовательный обход файлов. MapReduce как раз в тему — можно составить список файлов, затем анализ каждого файла делать параллельно (Map), аккумулируя найденных имена переменных, и в конце обработать все полученные входждение (Reduce), в нашем случае просто подсчитать количество вхождения каждой переменной.

Известная платформа для массово-параллельной обработки данных Apache Hadoop вышла в версии 1.0.0 (release notes). Для другого проекта выпуск первой версии мог бы считаться знаменательным событием и вехой в развитии, но здесь ситуация совсем другая. На самом деле Hadoop был готов к использованию в самых серьёзных коммерческих проектах ещё с версии 0.20. В связке с MapReduce он уже давно работает на Facebook, Yahoo, Twitter и др. В марте 2011 года Hadoop удостоен ежегодной награды MediaGuardian Innovation Awards как самая инновационная технология, а на церемонии вручения Hadoop назвали «швейцарским армейским ножом 21 века».

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

На сайте sortbenchmark.org ежегодно проводятся конкурсы по сортировке больших наборов данных. Один из видов соревнований — minute sort, в котором необходимо за минуту прочитать с диска и сортировать как можно большее число записей и сохранить результат в файл. Конкурс проходит в двух категориях — Indy, без ограничений на используемое железо, и Daytona — должны использоваться только обычные компьютеры “из магазина”.

Команде Microsoft Research удалось многократно превысить державшийся с 2009 года рекорд Yahoo в категории Daytona. Их кластер, состоящий из 1033 дисков на 250 машинах, справился с 1401 гигабайтом данных. Это почти втрое лучше результата Yahoo (500 гигабайт), при том, что кластер Yahoo был почти в шесть раз больше (5624 диска на 1406 машинах). Более того, майкрософтовский кластер побил и прошлогодний рекорд в категории Indy (1353 гигабайта).

Так случилось, что первый посмотренный мною фильм с упоминанием слова «суперкомпьютер» был Терминатор. Но, как ни странно, моя (тогда еще) не сформировавшаяся психика не посчитала скайнет мировым злом, списав агрессивное поведение первого в мире ИИ на недостаточное покрытие юнит тестами.

На тот момент у меня был ZX Spectrum (чьих 128 Kb явно не хватало на запуск чего-то похожего на ИИ) и много (думаю лет 10) свободного времени. Благодаря последнему факту, я благополучно дождался эры виртуализации. Можно было снять хоть 10K VPS, установить между ними канал связи и начинать создавать ИИ. Но мне хотелось заниматься программированием, а не администрированием/конфигурацией grid-системы, и я разумно начал ждать, когда вычислительные ресурсы начнут предоставляться как сервис.

Моей радости не было конца, когда появились облачные сервисы. Но радость длилась недолго: стало понятно, что пока прямые коммуникации между отдельными вычислительными инстансами – это фантастика код, который нужно писать самому (то есть с большой вероятностью он работать не будет). Попереживав пару лет по этому поводу, я (мы все) дождался Hadoop, сначала «on-premises», а потом и эластичного «on-demand». Но и там, как оказалось, не всё так эластично гладко

Технологии Big Data сегодня очень популярны, о чем говорит хотя бы то, что на текущий момент это наиболее часто встречающийся термин в IT-публикациях. Достаточно посмотреть на статистику таких известных поисковых систем, как Google или Yandex по словосочетанию «Big Data», и становится понятным, что так называемые «Большие Данные» действительно сейчас можно назвать одним из самых востребованных и интересных направлений развития информационных технологий.

Так в чем же секрет популярности этих технологий и что означает термин «Big Data»?

Если ты ИТшник, то нельзя просто так взять и выйти на работу 2-го января: пересмотреть 3-ий сезон битвы экстрасенсов или запись программы «Гордон» на НТВ (дело умственных способностей вкуса).
Нельзя потому, что у других сотрудников обязательно будут для тебя подарки: у секретарши закончился кофе, у МП — закончились дедлайны, а у администратора баз данных — амнезия память.
Оказалось, что инженеры из команды Hadoop тоже любят побаловать друг друга новогодними сюрпризами.

2008

2 января. Упуская подробное описание эмоционально-психологического состояния лиц, участвующих в описанных ниже событиях, сразу перейду к факту: поставлен таск MAPREDUCE-279 «Map-Reduce 2.0». Оставив шутки про число, обращу внимание, что до 1-ой стабильной версии Hadoop остается чуть менее 4 лет.

За это время проект Hadoop пройдет эволюцию из маленького инновационного снежка, запущенного в 2005, в большой снежный com ком, надвигающийся на ИТ, в 2012.
Ниже мы предпримем попытку разобраться, какое же значение январский таск MAPREDUCE-279 играл (и, уверен, еще сыграет в 2013) в эволюции платформы Hadoop.

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



Чтобы понять, что хочет пользователь, нужен контекст. Когда-то всем контекстом, который был доступен Яндексу, был текст поискового запроса. Со временем мы научились учитывать, из какого региона его задают.

Важным этапом стала персонализация ответа для разных пользователей — мы стали использовать знания о конкретном человеке, чтобы дать ему более точный ответ. Для этого мы использовали данные, посчитанные на истории запросов и кликов пользователя. Причём они были посчитаны как по истории за длинный период, так и по недавней. Мы рассказывали на Хабре об этом этапе.

Каждый раз дополнение пользовательского контекста влечёт за собой изменение качества работы системы, а иногда и пользовательского поведения.

Некоторое время назад мы рассказывали на Хабре о том, что поиск Яндекса стал более персонализированным. Он учитывает не только постоянные, но и сиюминутные интересы пользователя, ориентируясь на последние несколько запросов и действий.

Сегодня мы хотим рассказать о технологии Real Time MapReduce, благодаря которой всё это стало возможно. Она обеспечивает передачу и обработку огромных объёмов данных, необходимых для этой задачи, и чтобы сделать это, нам даже не пришлось переписывать код для MapReduce, который у нас уже использовался.



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