Лекция 6. Введение в GFS и Google MapReduce (2015 Лекции)

Большие данные: распределенноехранение и обработка данных спомощью модели вычисленийMapReduceЛекция №2. Введение в GFS и Google MapReducehttp://bigdata.cs.msu.rubigdata@cs.msu.ruВремя чтения 1 TB данныхSequential read speed : 70-120 MB/sec ~ 0,342 TB/hour~3 ЧАСА!!!Поиск min значения #1#define BUF_SIZE 1024double find_min(const char *filename){double arr[BUF_SIZE];int f=open(filename, O_RDONLY);size_t n;min=-DBL_MAX;while((n=read(f, arr, BUF_SIZE*sizeof(double))))>0)for(int i=0; i<n;i++)if(arr[i]<min) min=arr[i];return min;}char * filename[]={“/disk1/a.txt”, “/disk2/b.txt”, ”/disk3/c.txt”}int fd[2];pipe(fd);int i;for(i=0;i<3;i++)if(0==fork()) break;double min=find_min(filename[i]);if(i<2){write(fd[1], &min, sizeof(double));return;}close(fd[1]);total_min=min;while((read(fd[0], &min, sizeof(double))) >0)if(min<total_min) total_min=min;printf(“%f”, total_min);“/disk1/a.txt”“/disk2/b.txt”“/disk3/c.txt”1ТБ1ТБ1ТБ3 часа / 3 → 1 час + deltaПоиск min значения #2...read(f, &values, sizeof(double)*BUF_SIZE);...3 часа / 3 → 1 час + deltaХороши ли эти решения?1.2.3.4.Масштабируемость по объему данныхКлассы решаемых задачЭффективное использование вычислительных мощностейНадежность в случае аппаратных сбоевМасштабированиеСпособность системы справляться с увеличением рабочей нагрузки (увеличиватьсвою производительность) при добавлении ресурсовВертикальное масштабированиеГоризонтальное масштабированиеТехнологии организация параллельнойобработки данныхЧего хочется?Горизонтально масштабируемый фреймворкдля решения пакетных вычислительных задачширокого класса на больших массивахвходных данных, обладающий устойчивостьюк аппаратным сбоям.GFS & MapReduce●●Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung “The Google FileSystem”, 2003 http://research.google.com/archive/gfs.htmlJeffrey Dean and Sanjay Ghemawat “MapReduce: Simplified DataProcessing on Large Clusters”, 2004 http://research.google.com/archive/mapreduce.htmlThe Google File SystemGFS, 2000 годКонцепции●●●●●●Дешевое ненадежное оборудование.Эффективная работа с большим числом (миллионы) больших файлов(от 100МБ).

Поддержка небольших файлов.Эффективное последовательное чтение большими порциями (от 1 МБ).Редкое чтение по произвольному смещению.Эффективное последовательное дописывание (append) большимипорциями. Редкая запись по произвольному смещению.Эффективная реализации модели producer-consumer при массовомдописовании файла (сотни producers). Consumer может читать данныекак после завершения всез записей, так и параллельно с ними сминимальными издержками на синхронизацию.Высокая пропускная способность вместо быстрого отклика.GFS: архитектураКомпоненты● client (1..*)● master (1)● chunkservers (1..*)Ключевые термины● chunk (обычно 64МБ)● chunk handle● replica (обычно 3)Операции● create● delete● open● close● read● write● appendMaster1.Метаданные - хранятся в оперативной памятиa.b.c.d.2.3.4.5.ИменаМаппинги: файл -> чанкиТекущее местоположение репликПрава доступаЖурнал операцийРепликация журнала операций masterКонтрольные точкиОперации Mastera.b.c.Управление атомарностьюСборка мусора (чанков удаленных файлов)РерепликацияGFS: что еще?●●●Гарантия атомарности (создание файла, множественный append)Контроль целостности данных на chunkserversРезервные копии (Snapshots)MapReduceMapReduce, 2004“...MapReduce - модель вычислений и ее реализация для обработки и генерациибольших наборов данных.

Пользователю достаточно задать функцииmap (k1,v1) → list(k2,v2)иreduce (k2,list(v2)) → list(v3)Программы, написанные в таком функциональном стиле могут бытьавтоматически распараллелены и исполнены на больших кластерах.”“...Система исполнения позаботится о разбиении входных данных,планировании вычислений, ситуациях отказа оборудования, необходимомвзаимодействии между узлами. Это позволяет программисту без опытанаписания параллельных и распределенных программ, с легкостьюиспользовать ресурсы кластера для решения больших вычислительных задач.”Псевдокод WordCountmap(String key, String value):// key: document name// value: document contentsfor each word w in value:EmitIntermediate(w, "1");reduce(String key, Iterator values):// key: a word// values: a list of counts int result = 0;for each v in values:result += ParseInt(v);Emit(AsString(result));Модель исполненияWordCount #1mapmapmapmapmapmapmapmapmapmapmapmapmapmapmapmapmapmap12Mappermapmapmapmapmapmapmr,1sherlok,1who,1was,1usually,1in,1mornings,1...holmes,1very,1late,1the,1those,1not,1he,1...MapperMr Sherlock Holmes, who was usuallyvery late in the mornings, save uponthose not infrequent occasions whenhe was up all night, was seated at thebreakfast table.

I stood upon thehearth-rug and picked up the stickwhich our visitor had left behind himthe night before. It was a fine, thickpiece of wood, bulbous-headed, of thesort which is known as a “Penanglawyer.” Just under the head was abroad silver band nearly an inchacross. “To James Mortimer, M.R.C.S., from his friends of the C.C.H.,” wasengraved upon it, with the date “1884.”It was just such a stick as the oldfashioned family practitioner used tocarry — dignified, solid, andreassuring.“Well, Watson, what do you make ofit?”Holmes was sitting with his back tome, and I had given him no sign of myoccupation.sort,1which,1is,1known,1as,1a,1under,1...penang,1lawyer,1just,1the,1head,1broad,1band,1...Mappersplit #3split #2split #1map(0, ‘Mr Sherlock Holmes, who was usually’)→[(‘mr’,1),(‘sherlok’,1),(‘holmes’,1),(‘who’,1),(‘was’,1),(’usually’,1)]int hash(key){ return key[0]; }R=2r=hash(key)%Rwell,1watson,1what,1you,1make,1of,1it,1...reassuring,1do,1holmes,1his,1back,1to,1had,1...ShuffleReducer#1mr,1sherlok,1who,1was,1usually,1in,1mornings,1…sort,1which,1is,1known,1as,1a,1under,1...well,1watson,1what,1you,1make,1of,1it,1...a,1as,1in,1is,1it,1known,1make,1mornings,1mr,1of,1sherlok,1sort,1under,1usually,1was,1watson,1well,1what,1which,1who,1you,1Reducer#2holmes,1very,1late,1the,1those,1not,1he,1…penang,1lawyer,1just,1the,1head,1broad,1band,1reassuring,1do,1holmes,1his,1back,1to,1had,1...back,1band,1broad,1do,1had,1he,1head,1his,1holmes,1holmes,1just,1late,1lawyer,1not,1penang,1reassuring,1the,1the,1those,1to,1very,1......SortingSortingWordCount #2Reducer#1mr,1sherlok,1who,1was,1usually,1in,1mornings,1…sort,1which,1is,1known,1as,1a,1under,1...well,1watson,1what,1you,1make,1of,1it,1...Reducer#2a,1as,1in,1is,1it,1known,1make,1mornings,1mr,1of,1sherlok,1sort,1under,1usually,1was,1watson,1well,1what,1which,1who,1you,1reduce(‘a’,[1])reduce(‘as’,[1])reduce(‘in’,[1])reduce(‘is’,[1])reduce(‘it’,[1])reduce(‘known’,[1])reduce(‘make’,[1])reduce(‘mornings’,[1])reduce(‘mr’,[1])reduce(‘of’,[1])reduce(‘sherlok’,[1])reduce(‘sort’,[1])reduce(‘under’,[1])reduce(‘usually’,[1])reduce(‘was’,[1])reduce(‘watson’,[1])reduce(‘well’,[1])reduce(‘what’,[1])reduce(‘which’,[1])reduce(‘who’,[1])reduce(‘you’,[1])......Sortinga,1as,1in,1is,1it,1known,1make,1mornings,1mr,1of,1sherlok,1sort,1under,1usually,1was,1watson,1well,1what,1which,1who,1you,1holmes,1very,1late,1the,1those,1not,1he,1…penang,1lawyer,1just,1the,1head,1broad,1band,1reassuring,1do,1holmes,1his,1back,1to,1had,1...back,1band,1broad,1do,1had,1he,1head,1his,1holmes,1holmes,1just,1late,1lawyer,1not,1penang,1reassuring,1the,1the,1those,1to,1very,1...Sortingreduce(‘back’,[1])reduce(‘band’,[1])reduce(‘broad’,[1])reduce(‘do’,[1])reduce(‘had’,[1])reduce(‘he’,[1])reduce(‘head’,[1])reduce(‘his’,[1])reduce(‘holmes’,[1,1])reduce(‘just’,[1])reduce(‘late’,[1])reduce(‘lawyer’,[1])reduce(‘not’,[1])reduce(‘penang’,[1])reduce(‘reassuring’,[1])reduce(‘the’,[1,1])reduce(‘those’,[1])reduce(‘to’,[1])reduce(‘very’,[1])...back,1band,1broad,1do,1had,1he,1head,1his,1holmes,2just,1late,1lawyer,1not,1penang,1reassuring,1the,2those,1to,1very,1...Схема взаимодействия1.2.3.4.5.6.7.Входные данные разбиваются на M частей (M - определяется числом блоков заданной длиныв данных)Стартуют master (основная программа + планировщик) и workersMaster разбивает исходные данные на M splits и назначет M map заданий workers (опираясьна GFS locality chunk’ов, входящих в каждый split)Worker, получивший map задание, читает и распарсивает свой split и многократно вызываетфункцию map с выделенными key,value.