« Все записи

Понимание MapReduce

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

Основной принцип

Основу MapReduce составляют два этапа. Я предполагаю, что вы не будете очень удивлены, когда я скажу вам, что эти шаги называются Map и Reduce.

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

Процесс Reduce использует выходные данные процесса Map и комбинирует/отбрасывает данные для получения результата. Опять же довольно просто, правильно? Существует одна загвоздка с Reduce. Следует выводить точно такую ​​же структуру данных, которая использовалась в качестве входных данных. Суть в том, что вы можете, выполнить тот же самый процесс Reduce несколько раз, если захотите. Я еще вернусь к тому, почему вы, возможно, захотите сделать это.

Простой пример

Следующий код загружает несколько заказов и выполняет над ними работу MapReduce.

private static void MapReduce()
{
    var orders = LoadOrders();
    Print(orders);
 
    var mapped = Map(orders);
    Print(mapped);
 
    var reduced = Reduce(mapped);
    Print(reduced);
}

Стурктура данных заказов (Orders) выглядит так:

public class Order
{
    public Order()
    {
        Lines = new List<OrderLine>();
    }
 
    public int CustomerId { get; set; }
    public List<OrderLine> Lines { get; set; }
}
 
public class OrderLine
{
    public string Book { get; set; }
    public int Quantity { get; set; }
    public decimal Price { get; set; }
}

Как вы можете видеть у нас есть заказ (Order) от клиента с несколькими строками - позициями заказа (OrderLine). Каждая строка заказа содержит название книги, количество и сумму, за которую он был продан. Во время процесса Map мы просто извлекаем интересующие нас данные, в этом случае это название книги и цена, за которую она была продана. Мы сохраним это в следующую структуру:

public class ReducedTo
{
    public string Book { get; set; }
    public decimal Amount { get; set; }
}

Процесс Map

Таким образом, Функция Map принимает на входе коллекцию заказов Orders и возвращает коллекцию элементов ReduceTo.

private static IEnumerable<ReducedTo> Map(IEnumerable<Order> orders)
{
    var result = new List<ReducedTo>();
 
    foreach (var order in orders)
    {
        foreach (var line in order.Lines)
        {
            result.Add(new ReducedTo()
            {
                Book = line.Book,
                Amount = line.Price
            });
        }
    }
 
    return result;
}

На самом деле вы можете легко преобразовать это в LINQ-запрос:

private static IEnumerable<ReducedTo> Map(IEnumerable<Order> orders)
{
    return from order in orders
           from line in order.Lines
           select new ReducedTo
           {
               Book = line.Book,
               Amount = line.Price
           };
}

На самом деле это все и есть процесс Map, это просто LINQ-выражение Select. И когда вы взглянете на него таким образом, его становится намного проще и легче понять :-)

Процесс Reduce

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

private static IEnumerable<ReducedTo> Reduce(IEnumerable<ReducedT> input)
{
    var result = new List<ReducedTo>();
 
    foreach (var reduced in input)
    {
        var existing = result.FirstOrDefault(r => r.Book == reduced.Book);
        if (existing != null)
        {
            existing.Amount += reduced.Amount;
        }
        else
        {
            result.Add(reduced);
        }
    }
 
    return result;
}

Будет еще проще, если мы подумаем о ней на самом деле просто как о группировке. Так же, как с процессом Map, мы можем легко переписать функцию в виде LINQ-запроса group by:

private static IEnumerable<ReducedTo> Reduce(IEnumerable<ReducedTo> input)
{
    return from sale in input
           group sale by sale.Book into grp
           select new ReducedTo()
            {
                Book = grp.Key,
                Amount = grp.Sum(item => item.Amount)
            };
}

Как и процесс Map представляет собой функцию Select, процесс Reduce - это просто LINQ group by c дополнительной коллекцией, входной тип которой такой же, как выходной. Всё становится намного проще, правда? :-)

Запущенный код примера выведет что-то похожее на это:

Преимущества MapReduce

Мы увидели, что MapReduce - это просто еще один способ сделать LINQ-запрос group by, так в чем же дело? Одним из самых больших преимуществ MapReduce является тот факт, что вы можете их распараллеливать. Вы можете сделать это несколькими потоками внутри одного процесса или, если вы хотите масштабировать, на множестве машин. Ключом к этому является возможность повторить шаг Reduce несколько раз.

Предположим, мы хотим проанализировать множество данных о продажах и вычислить объем продаж за статью. Мы могли бы разделить данные на столько наборов, сколько мы хотим. Давайте предположим, что мы разделили заказы на три набора. Для каждого набора заказов мы можем преобразовать данные с помощью Map в коллекцию пар статей и сумм продаж, где каждая статья может содержаться несколько раз. После того, как это будет сделано, на шаге Reduce данные группируются, в результате чего мы имеем в каждом наборе данных одну пару для каждой статьи с общей суммой продаж для этого набора. Теперь, когда это было сделано для каждого набора данных, мы объединяем три обработанные набора в один. Он очень похож на набор данных после первого процесса Map, так как содержит повторяющиеся записи для каждой статьи, и все что нужно сделать, это запустить тот же процесс Reduce над этим гораздо меньшим набором данных, чтобы получить конечный результат. Таким образом, это всего лишь принцип "разделяй и властвуй", где мы делим исходные данные на столько наборов, сколько мы хотим. А другими словами, это действительно простая система масштабирования сценариев :-)

Это очень легко проделать с теми же функциями Map и Reduce, которые мы использовали раньее. Приведенный ниже код загружает 25 различных наборов заказов и запускает процессы Map и Reduce для каждого из них. Как только это будет сделано, он комбинирует различные выходные наборы в один новый входной и выполняет еще раз Reduce для получения конечного результата.

private static void ParallelMapReduce()
{
    var tasks = new List<Task<IEnumerable<ReducedTo>>>();
    for (int i = 0; i < 25; i++)
    {
        var task = Task>.Factory.StartNew(() =>
        {
            var orders = LoadOrders();
            var mapped = Map(orders);
            var reduced = Reduce(mapped);
            return reduced;
        });
        tasks.Add(task);
    }
 
    Task.WaitAll(tasks.ToArray());
 
    foreach (var task in tasks)
    {
        Print(task.Result);
    }
 
    var result = Reduce(tasks.Select(t => t.Result));
    Print(result);
}

Чтобы объединить различные результаты, я создал простую перегруженную функцию Reduce, которая объединяет несколько входных данных и вызывает оригинальную функцию Reduce следующим образом:

private static IEnumerable Reduce(IEnumerable> args)
{
    var input = new List<ReducedTo>();
 
    foreach (var item in args)
    {
        input.AddRange(item);
    }
 
    return Reduce(input);
}

Запуск этого кода выведет то, что показано ниже. Белый цвет - это вывод из 25 первоначальных задач Reduce, а желтый - это результат работы второй функции Reduce, которой были обработаны данные первых 25 задач.

Заключение

MapReduce - это просто еще один способ сделать group by из LINQ, но такой, который является масштабируемым из-за нескольких простых правил. И как только вы поймете, что больше нет оснований бояться принципа MapReduce, вы начнете лучше относиться к его возможностям.

Наслаждайтесь!

P.S. Примечание переводчика: я взялся переводить эту статью для себя, потому что изначально был действительно "запуган" этой концепцией. :-) К счастью, эта статья содержит достаточно простой и наглядный пример на знакомом мне языке C#, поэтому теперь у меня с MapReduce нет проблем.

comments powered by Disqus