[Moscow.pm] Идеальный Map-ер и Reduce-ер

[Ruslan Zakirov]

Знаете что такое оператор шварца?

@sorted = map $_->[0] sort { $a->[1] <=> $b->[1] } map [ $_,
$_->sort_order ], @objects;

reducer - map+sort слева
mapper - map справа
task - сортировка
task data - @objects;

Теперь все это параллелим:

* в диспечере: my @block = splice @objects, 0, 100;
* запихиваем @block в свободный мапер
* мапер: return map { operation-sort-task-x => [ $_, $_->sort_order ] } @block
* локальный комбинатор получает ключ и список значений с этим ключом
полученный от локального мапера
* локальный комбинатор sub {
   my $key = shift; @values = @_;
   return $key, [ sort { $a->[1] <=> $b->[1] } @_ ];
}
* запихиваем в хранилище результат
* после окончания мапинга раздаем задачи по редьюсу
* редьюсеры сортируют уже предварительно отсортированные блоки и
возвращают объекты
* репортеры складывают результат куда нам нужно

Все просто, но куча веселых вопросов.

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

редьюсерам начинаем раздавать задачи раньше после накопления
определенного количества блоков. редьюсер возращает не объекты, а
опять блоки, но объединенные и отсортированные. Получиться алгоритм
сортировки по типу разделяй и властвуй.

Я бы не назвал это редьюсером, а глобальным комбинером. и в задаче
сортировки не было бы редьюсера совсем. Или можно назвать re-entrant
reducer'ом.

Репортер знает, что мы передаем блоки и знает где забрать объекты.

Вот такая хрень.

2009/1/21 Павел Тимонин <gg.error на gmail.com>:
> Сильно - в смысле "здравствуйте, Михаил" :) - строчка, после которой я это
> написал. такое обращение к самому себе.
> поэтому и извинялся за оффтоп - никакого отношения к теме это не имеет.
> сама же тема мне очень непонятна и интересна, тред читаю, но ничего не
> понимаю - я в этом ни в зуб ногой. но вижу большуя практическую пользу.
> 21 января 2009 г. 1:20 пользователь Михаил Монашёв
> <postmaster на softsearch.ru> написал:
>>
>> Здравствуйте, Павел.
>>
>> ПТ> Здравствуйте, Михаил.
>> ПТ> А вот это сильно.
>> ПТ> Сорри за оффтоп.
>>
>> В каком смысле "сильно"? Грибы у меня забористые или идея понравилась?
>> Можно поняснить.
>>
>> Я  просто  тут пытаюсь людей спровоцировать на диалог. Тема, видимо не
>> всем понятна, а потому любое обсуждение ИМХО полезно.
>>
>> Есть  например  большой  вопрос об эффективности использовании ssh как
>> транспорта.  Но при этом Disco и Parallel::MapReduce их используют. Мы
>> же   не  MapReduce-ботнет  делаем.  А  во  внутренней  сетке  всё  это
>> запускаем. Шифрование там лишнее ИМХО.
>>
>> Также  есть  мысль,  что  перед  мапером  должен  запускаться какой-то
>> итератор,  который  поставляет  маперу  данные  в  формате хэша. Также
>> должно  быть  какое-то  хранилище,  чтобы складывать результаты работы
>> маперов, потом агркгировать их по ключам и раздавать редьюсерам.
>>
>> Ещё  есть  ощущение,  что  редьюсеры  особенно лично мне и не нужны. И
>> потому  MapReduce  вырождается  просто  в  запускалку  в  параллель на
>> нескольких серверах каких-то скриптов. Хотя возможно просто не хватает
>> практики, чтобы понять всю мощь MapReduce и начать использовать его.
>>
>> --
>>
>> С уважением,
>> Михаил Монашёв, SoftSearch.ru
>> mailto:postmaster на softsearch.ru
>> ICQ# 166233339
>> http://michael.mindmix.ru/
>> Без бэкапа по жизни.
>>
>> --
>> Moscow.pm mailing list
>> moscow-pm на pm.org | http://moscow.pm.org
>
>
> --
> Moscow.pm mailing list
> moscow-pm на pm.org | http://moscow.pm.org
>
>



-- 
Best regards, Ruslan.