Eléments logiciels pour le traitement des données massives

ENSAE - OMI309

Cours animé par : Matthieu Durut [2], Xavier Dupré [2], Antoine Ly [2]

Le cours est évalué avec un projet informatique.


Eléments techniques

Anatomie et histoire d’un ordinateur

  • mémoire, cache, northbridge, southbridge
  • CPU, GPU, FGPA, ASICS
  • 2004 - espace entre deux circuits intégrés de 32 ns, passage à 24 ns ? effet quantique, passage d’électron
  • optimisation des calculs, parallélisation, notion de cache et de latence

Lectures


Eléments théoriques

Crypographie, block chain

  • commitment et signature (RSA)
  • Tiers de confiance et distributed consensus (PAXOS), RAFT
  • Block chain, Bitcoin, Attque (Incentive, long term consensus, la probabilité qu’on soit en désaccord décroît avec le temps, monnaie stable, sûre, anonyme ?)
  • Ethereum

Lectures


Eléments logiciels

Structures de données

Lectures

Threads et synchronisation

  • threads, application multi-threadées
  • variables globales, synchronisation

Lectures

Compression des données

Lorsque les données sont volumineuses. Une solution consiste à les compresser.

Lectures

Modules

Workflow de données

Lectures

Modules


Map Reduce

Map Reduce en pratique

  • Itérateurs, lien avec le SQL (voir Séries temporelles et map reduce)
  • Distribution à base de hash (voir Hash et distribution)
  • Mapper, Reducer, Combiner, Partitionner
  • Graphe d’exécution, synchronisation - Map Reduce Flow Chart
  • Exemple : moyennes par groupes
  • Pas d’ordre des observations, tri sur l’ensemble des données à éviter
  • Produit matriciel, représentation d’une matrice en trois colonnes, matrice sparse
  • Graphe : pas facile en map/reduce, exemple avec l’algorithme des random walk with restarts
  • Problème des skewed datasets –> clés très mal distribués (voir Hash et distribution)
  • Descente du gradient : itératif
  • Stratégie de parallélisation, propriétés mathématiques optimisation d’une fonction convexe
  • Exemple de k-means distribué
  • Le hasard en distribué, Réservoir sampling (correction)
  • Schéma des langages de map/reduce : lazy evaluation (évalusation presseuse, dask, Spark, PIG)

avec PIG sur Azure et Cloudera

Les trois séances suivantes sont plus appliquées et dédiées à la découverte de Hadoop, un environnement qui permet d’exécuter des tâches Map/Reduce. Plusieurs angles d’approche sont possibles. Celle retenue est l’utilisation du langage PIG-latin dont la logique ressemble beaucoup à celle du SQL. Les outils Python [1] simplifient la communication avec le cluster.

Trois projets réalisés par les élèves lors de l’année 2014-2015 :

Lectures

Getting started, installation, setup

PIG

Ces enseignements vous sont proposés via des notebooks. Ils requièrent une surcouche apporté par le module pyensae. Le python n’est pas l’objet de ce cours, les notebooks sont utilisés pour pouvoir regrouper dans un même document toutes les opérations effectuées dans un langage Map/Reduce. La page En résumé : Anaconda décrit comment installer ces outils sur les trois OS principaux Windows, OS X, Linux.


Bibliographie

Articles

Liens

Librairies / outils

  • amazon-dsstne : moteur de recommandation d’Amazon
  • Elastic Search : moteur de recherche
  • Giraph : Large-scale graph processing on Hadoop
  • Hadoop : système de fichier distribué + Map Reduce simple
  • Kafka : distributed streaming platform, conçu pour stocker et récupérer en temps réel des événements de sites web
  • Mesos : Apache Mesos abstracts CPU, memory, storage, and other compute resources away from machines (physical or virtual), Elixi
  • MLlib : distributed machine learning for Spark
  • Parquet : Apache Parquet is a columnar storage format available to any project in the Hadoop ecosystem.
  • Presto : Distributed SQL Query Engine for Big Data (Facebook)
  • pyCUDA (A Monte Carlo Option Pricer avec numbapro)
  • Spark : Map Reduce, minimise les accès disques, (DPark clone Python de Spark)
  • Spark SQL : SQL distribué, sur couche de Spark
  • Storm : Apache Storm is a free and open source distributed realtime computation system, conçu pour distribuer des pipelines de traitements de données
  • YARN : Ressource negociator

Librairies à suivre

  • multiverso : framework de parallélisation
  • CNTK : librairie de deep learning chez Microsoft
  • lightLDA : Latent Dirichlet Application parallélisée
  • lightGBM : A fast, distributed, high performance gradient boosting (GBDT, GBRT, GBM or MART) framework based on decision tree algorithms.

Footnotes

[1]C’est l’objet du paragraphe Getting started, installation, setup.
[2](1, 2, 3) Contributeur et coordinateur du cours.
[3]Contributeur, encadrant.