Apache Hadoop bas le record du tri le plus rapide

Apache Hadoop a permis à Yahoo de remporter le benchmark du tri distribué le plus rapide. Hadoop a permis de trier 1 Tera-octets (1,000,000,000,000) de données en 62 secondes.

Mais qu'est ce qu'Hadoop et comment peut-il trier les de telles quantités aussi rapidement?

Pour comprendre Hadoop, il faut revenir sur deux fonctions rendu populaire grâce à la programmation fonctionnelle: map et reduce. Ces deux fonctions sont des briques intéressantes pour construire un algorithme qui s'exécute en parallèle.

map() et reduce()

La fonction map() prend un élément des données d'entrée, lui applique un traitement quelconque, et retourne le résultat. Cette fonction est parallélisable car il est possible d'exécuter autant de map en parallèle qu'il y a de processeurs/cœurs.

La fonction reduce() prend deux éléments, applique un traitement quelconque, et retourne un seul résultat. Cette fonction aussi parallélisable aisément, il suffit de faire autant de reduce en parallèle qu'il y a de processeur/cœurs.

Le fonctionement de map-reduce est simple. Vous prenez un tableau en entrée, vous appliquez la fonction map() sur chaque élément pour avoir les données mappée. Ensuite vous utilisez la fonction reduce() sur les données mappée jusqu'à ce qu'il n'y ai plus qu'un résultat.

Par exemple, imaginez que vous voulez calculez la somme des carrés d'un tableau d'entrée, la fonction map serait quelque chose comme:

function map(input) {
   return input * input;
}

La fonction reduce serait:

function reduce(input1, input2) {
  return input1 + input2;
} 

Vous donnez l'entrée, la fonction map et la fonction reduce a un algorithme de map-reduce parallèle (par exemple QtConcurrent ou TBB), et votre algorithme utilise tout les processeurs disponible sur l'ordinateur.

Hadoop

Revenons à Hadoop, Hadoop est un système permettant de distribuer map-reduce sur des cluster d'ordinateurs. Le tri a été réalisé sur 1460 ordinateurs, chacun ayant 4 cœurs.