Логистика - нещо прекрасно. Уърт погледнете в трезора на супермаркет - и става ясно: без внимателни поръчване на стоки там и реч не може да отиде по всяко ефективно търговия. В същото време, гигантски търговски къщи тихо отвориха вратите си за десетки хиляди потребители и лесно търсене в дълбините на бездънните си складове искаше предмети.
С информацията, ситуацията е почти същата. Запишете го - просто една от задачите. Информация изисква лечение. Без значение колко ефективно всеки магазин за данни, това няма да помогне да я лекува.
В Google, запознат с проблема от първа ръка. Нейните трудолюбиви роботи събират съдържание денонощно цял процъфтяващата Интернет и да го изпратят на Google клъстер, където цари GFS разпределена файлова система. Той разпределя петабайта данни за стотици хиляди сървъри парче по-добри от опитен експерт в областта на логистиката, в този процес, като им предоставя сигурно съхранение, който не вреди на евентуални неизправности или дефекти в оборудването.
Но търсачката - тя е не толкова за съхранение на съдържание като система от най-бързо намиране на части за ключовите думи, които въвеждате в лентата за търсене.
Как мога да разбера, на която уеб страници са тези ключови думи? Какво ресурс съдържа само една дума, и какво - само някои от тях? Тук, без да е добра базата на индекса е задължително.
За да се формира база в набор от данни на пета с мащаб - не е тривиална задача. Всъщност изисква от своя страна на "разходка" на всеки документ, за да се определи дали той съдържа думата, която искате. Както и да е, линеен процес.
Но не и за компания, която разполага с група от половин милион компютри.
С нея лесно можете да използвате най-известните парадигма на информатиката на "разделяй и владей", като се раздели на данните, посочени в части и даване на всеки един от тях с отделен индекс сървър. Е, след като индексирането е да събира части от намереното решение заедно.
Тя е за такава работа и е разработена технология за Google MapReduce - ефективно средство за parallelizing задачи, при нормални условия, за решаване на линейни.
Вдъхновение от миналото
Не забравяйте, че като дете в уроците по майчин език бяхме натоварени със задачата да се грижи? Намерени, например, на страницата на "Златната рибка" всички буквата "О" и разчита на техния брой. Студентите съвестно, ред по ред, гледа за "O", да ги подчертават, а след това многозначително обобщени.
Сега си представете, как бързо да изпрати делото, ако сме били дадени на линията всеки ученик в класа, която, отчитане на броя на буквите ще го информира предварително определен "майстор магията." Без да навлизаме в подробности, MapReduce технология работи по този начин.
Разбира се, развитието на MapReduce, служителите на Google Джефри Дийн (Джефри Дийн) и Санджай Gemavat (Санджай Ghemawat) вдъхнови не училищното образование. Те имаха още един чудесен източник на ентусиазъм. Обратно в края на петдесетте години на миналия век до данните, предоставени от линеен списък, той е проектиран Lisp език за програмиране - прародител на цялото семейство на езици, използвайки парадигмата на функционалното програмиране.
Lisp и други функционални езици поддържат интересен модел за програмиране, наречен Карта / намали. От името му означава, че в него работят две процедури - карта, се прилага правилното функциониране на всеки елемент от списъка, и да се намали, като съчетава картата на резултати.
Операциите, извършени от функцията на картата и да се намали. В най-простия случай, данните за обединяване на "ключът" стойност.
За да изпълните индексиране съхранява в Google клъстер от разработчиците на уеб съдържание на MapReduce адаптиран общия модел на функционални езици за програмиране на техните цели.
Те предполагат, че цялата MapReduce обработената информация може да бъде представена като списък от двойки, всяка от които се състои от ключ и стойност. В масива от ключово уеб съдържание, разбира се, това е търсене на думата и нейното значение - числото 1, което потвърждава наличието на думата.
В най-простия вариант на Google MapReduce процедура програмен модел карта отнема като вход на списък от думи, съдържащи се в преработени документи. Той преобразува всеки елемент в двойката, един от елементите на което е една дума, а другият - номер 1.
След това, за да бъде взето списъка процедура се намали, която включва списък от елементи с един и същ ключ (т.е. думите) и добавя edinichki. В резултат на това на изхода е даден списък на всички ключови думи в размер на справки за тях в различните документи. И това е в основата на индекса на търсачката.
Добър пример на работните функции на картата и да се намали.
Както можете да видите, нищо ново създатели не измислят MapReduce. Техният истински заслуги в другата. В действителност MapReduce - не е само един модел за програмиране, като се използват които можем да решим проблема на сортиране и групиране на данните. Това - в цялата архитектура, която гласи:
- автоматично паралелно извършване на данни от голям масив от множество обработващи възли, изпълняващи Карта процедура / намали;
- ефективно балансиране на натоварването на изчислителната възли, не им дава покой или претоварване извън мярка;
- безотказен технология постижения, които от факта, че в рамките на общата задача на обработващите елементи могат да бъдат повредени или поради някаква друга причина, за да спре обработката на данни.
По този начин, MapReduce Google, от една страна, това предоставя на потребителя с процедурите за обработка на данни, а от друга - го прави прозрачен за паралелно извършване на обработката на могъщата Google клъстера.
Как са го направили?
Паралелни Solvers, GFS, както и всички същия клъстер
Най-блестящата идея за проектиране е идеята на MapReduce място модули, които да прилагат процедури за карта и да намалят, за същите късовете на сървърите - въз основа на GFS файловата система. Този подход носи съхраняват в GPS модул с функциите на тяхното лечение. Запазване на мрежовия трафик там.
Повече - повече. Както GFS, MapReduce технология се основава на принципа на "главната. - подчинен" "Head» MapReduce - процедура Master - контролира множество разпръснати късовете на сървъри "на работниците" (работниците), някои от които са отговорни за картата на функциите (те се наричат картографи, или "картограф"), както и други, съответно, за се намали (регулатори - "redyusery").
Резултатът е нова, разделени в масив от междинния данни, включително неподредените списъци на двойки ключ - стойност. В идеалния случай, броят на частите на този междинен масив трябва да бъде равна на R, т.е. същият като броя на "лица", отговорен за операцията намали. Въпреки това, на практика масив от двойки, които имат един и същ ключ може да бъде много по-голям (например, ако ключът - това е един от най-популярните думи в заявката за търсене).
За да се намали неговия размер, на MapReduce използва предварителен процес данни агрегация чрез определяне толкова популярен нови двойки междинна стойност. Тази процедура се нарича комбайна и по своята същност е много подобен на намаляване. Трябва да се отбележи, че комбайна може да се използва само в случаите, когато функцията, която се използва за намаляване на стъпки за комбиниране на данни, която има свойствата на commutativity и асоциативност.
Обобщено до желания размер на междинен масив от данни могат да бъдат предоставени на R «Работници" летящ намали. Добре е да припомним, че се намалява с по-простата си форма работи с всички стойности на ключ - например, с броя на споменавания на думата. Това означава, че за всеки "работник" е желателно да се прилага един чифт с един и същ ключ. Проблемът се състои в това, че те са разпръснати в различни части на списък генерира четящото устройство. Как е възможно това?
MapReduce - това е не само в процеса на изчисления. Това е система с централизирано управление, проследяване и го паралелизация за грешки по време на неговото изпълнение.
Последната стъпка преди извършване на процедурата е да намали процедурата за разпределение (разделяне), в резултат на двойките, които имат един и същ ключ за да получите същите "работници". Да, този процес изисква време и значително трафика в мрежата, но това се компенсира от скоростта на работа на следващия етап.
Всеки redyuser в крайна сметка създава файл, който съхранява списъка подредени (например, по азбучен ред) на ключове, за които той е отговорен, и в резултат на обработката на тези ключови стойности (например, тяхната сума).
За да се намали количеството на резултати изчислителни, MapReduce внимателно разпределя междинен данни възли намаляват.
Така че в недрата на Google клъстер е роден и в базата на индекса на интернет, изграждане на графика на популярността на URL и извършва други необходими за работата на търсачката.
И не само за нея. разработчиците на приложения на Google, които изискват обработка на големи масиви от данни бързо оценени предимства на MapReduce паралелно калкулатор и пишат свои собствени версии на картата и да намалят процедури. Точно актуализирана база данни дума Google Translate преводач, така че тя генерира данни за десетки правописна проверка на правописа Google Docs езици и индекси глас морфема Google Voice. Не са открити MapReduce приложения резултати.
Както е случаят с файлови двигатели GFS, Google обясни само MapReduce идеология, без да разкриват конкретни реализации на своите алгоритми. Все пак, това е достатъчно, за да отвори кода на общността в рамките на проекта Hadoop е внедрил Task Scheduler разпределение възел клъстър компютър Hadoop прежди Hadoop и рамката на MapReduce, за да създадете свой собствен картограф и redyusery.
Технологията на MapReduce, фокусирани върху пакетна обработка (магистър разпределена работа чакаше, се събраха резултати) не може да се справи ефективно с тези постоянни промени.
По-ясно от полза за Google Caffeine архитектура с предишни решения и да не си представяли.
Използване на най-добрите си постижения и внимателно проучване на тенденциите от съвместната ни работа в интернет, Google се опитва да направи проактивни стъпки в развитието на сърцето му - търсачката.