Under de senaste åren har Google MapReduce vuxit fram som en ledande storskalig databehandlingsarkitektur. Antagna av företag som Amazon, Facebook, Google, IBM och Yahoo! I dagligt bruk, och på senare tid i bruk av flera universitet, möjliggör det parallell bearbetning av enorma mängder data över kluster av maskiner. Hadoop är en gratis Java implementering av MapReduce. I Hadoop delas filer upp i block och kopieras och sprids över alla servrar i ett nätverk. Varje jobb delas också upp i många små bitar som kallas uppgifter. Flera uppgifter behandlas på en enda server och ett jobb slutförs inte förrän alla tilldelade uppgifter är klara. En avgörande faktor som påverkar slutförandet av ett jobb är den särskilda tilldelningen av uppgifter till servrar. Med tanke på en placering av inmatningsdata över servrar, vill man hitta den uppgift som minimerar slutförandet tid. I den här artikeln föreslås en idealiserad Hadoop-modell för att undersöka problemet med Hadoop-uppdraget. Det visas att det inte finns någon genomförbar algoritm för att hitta den optimala Hadoop uppgiftstilldelningen om inte P = N P. Uppdrag som beräknas av round robin algoritm inspirerad av den nuvarande Hadoop schemaläggaren visas avvika från optimal med en multiplikativ faktor i värsta fall. En flödesbaserad algoritm presenteras som beräknar uppgifter som är optimala inom en additiv konstant.
I REF undersöker de uppgiftsuppdrag i Hadoop och ger en idealiserad Hadoop-modell för att utvärdera kostnaden för uppdrag.
Assigning tasks for efficiency in Hadoop: extended abstract
{'venue': "SPAA '10", 'journal': None, 'mag_field_of_study': ['Computer Science']}