html текст
All interests
  • All interests
  • Design
  • Food
  • Gadgets
  • Humor
  • News
  • Photo
  • Travel
  • Video
Click to see the next recommended page
Like it
Don't like
Add to Favorites

Объясняем суть MapReduce "на пальцах"


Уж целую неделю мы постепенно разжевываем NoSQL/NewSQL, но вопросы не убывают (как я ожидал), но только нарастают.

Разделавшись намедни с основами команд memcached, сейчас я хочу попытаться максимально просто, насколько это возможно для меня, ответить на частый и важный вопрос — что такое MapReduce.

Что такое MapReduce?

Это типовой подход, алгоритм, ну или паттерн, тут уж как кто назовет, параллельной обработки больших объемов сырых данных, например — результатов работы краулеров или логов веб-запросов.

Вообще по статистике, до 80% задач могут свободно и очень выгодно маппиться на MapReduce, и именно MapReduce драйвит сейчас в NoSQL.

Существуют разные имплементации MapReduce. Достаточно известная и запатентованная реализация этого алгоритма и подхода — у Google. Или как пример MySpace Qizmt — MySpace’s Open Source Mapreduce Framework, также используется в Hadoop, MongoDb и еще много разных примеров можно привести. Более детально можно почитать в статье (PDF): MapReduce: Simplified Data Processing on Large Clusters.

Основы основ

Итак, типичная реализация этого алгоритма получает на вход 3 аргумента: исходную коллекцию, Map-функцию, Reduce-функцию, — и возвращает новую коллекцию данных после обработки.

Collection MapReduce(Collection source, Function map, Function reduce)

Алгоритм состоит из нескольких шагов. В качестве первого шага выполняется Map-функция к каждому элементу исходной коллекции. Map вернет ноль либо создаст экземпляры Key/Value объектов.

ArrayOfKeyValue Map(object itemFromSourceCollection)

То есть, можно сказать, что обязанность Map-функции конвертировать элементы исходной коллекции в ноль или несколько экземпляров Key/Value объектов. Это продемонстрировано ниже на изображении:

MapReduce Map Reduce NoSQL php highload high load мэп рэдьюс

Следующим шагом, алгоритм отсортирует все пары Key/Value и создаст новые экземпляры объектов, где все значения (value ) будут сгруппированы по ключу.

MapReduce Map Reduce NoSQL php highload high load

Последним шагом выполнится функция Reduce — для каждого сгруппированного экземпляра Key/Value объекта

ItemResult Reduce(KeyWithArrayOfValues item)

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

MapReduce Map Reduce NoSQL php highload high load

Пример-реализация

В качестве примера реализуем очень простую и наглядную имплементацию этого алгоритма на C#. Мой пример считает количество гласных построчно в наборе строк.

В примере создана обобщённая функция MapReduce , — как основная в этом алгоритме, — которая просто вызывает специализированные функции Map и Reduce , распараллеливая их выполнение. Собственно сами функции Map и Reduce , реализация которых является уже специфической для той задачи, которую мы пытаемся решить (в каждом конкретном случае), а в данном случае, — это «посчитать количество гласных в наборе строк».

Итак, поехали:

using System;
using System.Collections.Generic;
using System.Collections.Concurrent;
using System.Linq;
using System.Threading.Tasks;
 
namespace MapReduceSample
{
   // Элемент результирующей коллекции, гласная и ее количество
    class VocalCount
    {
        public char Vocal;
        public int Count;
    }
 
    clаss Program
    {
        stаtic vоid Mаin(string[] args)
        {
            // "lines" - это исходная коллекция.
            var lines = new[] {
                "How many vocals do",
                "these two lines have?"
            };
 
            forеach (var line in lines)
            {
                Cоnsole.WriteLine(line);
            }
            Cоnsole.WriteLine();
 
            // Вызывается MapReduce
            var results = MаpReduce(lines, Map, Reduce);
 
            // Отображение результата
            foreаch (var result in results)
            {
                Consоle.WriteLine("{0} = {1}", result.Vocal, result.Count);
            }
 
            Consоle.ReadKey();
        }
 
        /// <summary>
        /// Функция Map считает количество гласных в строке
        /// </summary>
        /// <param name="sourceItem" />Строка для подсчета</param>
        /// <returns>Коллекция экземпляров Key/Value.
        /// Где key - гласная, и значение ее количество.</returns>
        static IEnumеrable<KeyValuePair<char, int>> Map(string sourceItem)
        {
            return sоurceItem
                .ToLower()
                .Where(c => "aeiou".Contains(c))
                .GroupBy(c => c, (c, instances) => new KeyValuePair<char, int>(c, instances.Count()));
 
        }
 
        /// <summary>
        /// Функция Reduce считает общее число каждой гласной
        /// </summary>
         /// <param name="reduceItem" />Экземпляр Key/Values, где key - гласная,
        /// и value - список всех подсчетов гласных по строкам</param>
        /// <returns>Экземпляр элемента результирующей коллекции, VocalCоunt</returns>
        static VocalCount Reduce(KeyValuePair<char, IEnumerable<int>> reduceItem)
        {
            return new VocalCount
            {
                Vocal = rеduceItem.Key,
                Count = rеduceItem.Value.Sum()  // Computes total count
            };
        }
 
        /// <summary>
        /// Обобщенная реализация функции MapReduce
        /// </summary>
        /// <typeparam name="TSource">Тип элементов исходной коллекции</typeparam>
        /// <typeparam name="TKey">Типа ключа Key используемого в функциях Map и Reduce</typeparam>
        /// <typeparam name="TValue">Тип Value используемый в функциях Map и Reduce</typeparam>
        /// <typeparam name="TResult">Тип элементов результирующей коллекции</typeparam>
        /// <param name="source" />Исходная коллекция</param>
        /// <param name="map" />Функция Map</param>
        /// <param name="reduce" />Функция Reduce</param>       
        static IEnumerable<TResult>  MapReduce<TSource, TKey, TValue, TResult>(
            IEnumerable<TSource> source,
            Func<TSource, IEnumerable<KeyValuePair<TKey, TValue>>> map,
            Func<KeyValuePair<TKey, IEnumerable<TValue>>, TResult> reduce)
        {
            // Коллекция, где сохраним результаты нашей map-функции
            var mapResults = new ConcurrentBag<KeyValuePair<TKey, TValue>>();
 
            // Выполним функцию Map паралельно для каждого элемента исходной коллекции
            Parallel.ForEаch(source, sourceItem =>
            {
                foreаch (var mapResult in map(sourceItem))
                {
                    mapResults.Add(mapResult);
                }
            });
 
            // Сгрупируем все значения по ключам
            var reduceSources = mapResults.GroupBy(
                    item => itеm.Key,
                    (key, values) => new KeyValuePair<TKey, IEnumеrable<TValue>>(key, values.Select(i=>i.Value)));
 
            var resultCollection = new BlockingCollection<TResult>();
 
            // Старуем reduce
            Task.Factory.StartNew(() =>
            {
                // Выполняем функцию Reduce паралельно для каждого элемента reduceSources
                Parallel.ForEаch(reduceSources,
                                (reduceItem) => resultCollection.Add(reduce(reduceItem)));
                 
                resultCollection.CompleteAdding();
            });
             
            return resultCollection.GetConsumingEnumerable();
        }
    }
}

Довесок: Хронология развития технологии MapReduce, также для всех жаждущих серьёзных подробностей могу порекомендовать очень хороший курс на эту тему «MapReduce course at the University of Maryland for Spring 2013», выложенный полностью в онлайн.

Читать дальше
Twitter
Одноклассники
Мой Мир

материал с blogerator.ru

110
    +92 surfers

      Add

      You can create thematic collections and keep, for instance, all recipes in one place so you will never lose them.

      No images found
      Previous Next 0 / 0
      500
      • Advertisement
      • Animals
      • Architecture
      • Art
      • Auto
      • Aviation
      • Books
      • Cartoons
      • Celebrities
      • Children
      • Culture
      • Design
      • Economics
      • Education
      • Entertainment
      • Fashion
      • Fitness
      • Food
      • Gadgets
      • Games
      • Health
      • History
      • Hobby
      • Humor
      • Interior
      • Moto
      • Movies
      • Music
      • Nature
      • News
      • Photo
      • Pictures
      • Politics
      • Psychology
      • Science
      • Society
      • Sport
      • Technology
      • Travel
      • Video
      • Weapons
      • Web
      • Work
        Submit
        Valid formats are JPG, PNG, GIF.
        Not more than 5 Мb, please.
        30
        surfingbird.ru/site/
        RSS format guidelines
        500
        • Advertisement
        • Animals
        • Architecture
        • Art
        • Auto
        • Aviation
        • Books
        • Cartoons
        • Celebrities
        • Children
        • Culture
        • Design
        • Economics
        • Education
        • Entertainment
        • Fashion
        • Fitness
        • Food
        • Gadgets
        • Games
        • Health
        • History
        • Hobby
        • Humor
        • Interior
        • Moto
        • Movies
        • Music
        • Nature
        • News
        • Photo
        • Pictures
        • Politics
        • Psychology
        • Science
        • Society
        • Sport
        • Technology
        • Travel
        • Video
        • Weapons
        • Web
        • Work

          Submit

          Thank you! Wait for moderation.

          Тебе это не нравится?

          You can block the domain, tag, user or channel, and we'll stop recommend it to you. You can always unblock them in your settings.

          • pleshner
          • домен blogerator.ru

          Get a link

          Спасибо, твоя жалоба принята.

          Log on to Surfingbird

          Recover
          Sign up

          or

          Welcome to Surfingbird.com!

          You'll find thousands of interesting pages, photos, and videos inside.
          Join!

          • Personal
            recommendations

          • Stash
            interesting and useful stuff

          • Anywhere,
            anytime

          Do we already know you? Login or restore the password.

          Close

          Add to collection

             

            Facebook

            Ваш профиль на рассмотрении, обновите страницу через несколько секунд

            Facebook

            К сожалению, вы не попадаете под условия акции