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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Большие данные: распределенноехранение и обработка данных спомощью модели вычислений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.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций