Introduction

Nous allons expérimenter le modèle de parallélisme via le logiciel Spark, ainsi qu'Hadoop pour gérer les machines. Pour exploiter notre installation, nous avons choisis de programmer en Python via la bibliothèque Pyspark.

Jeu de Données

Pour établir notre jeu de données, nous avons décidés de prendre le deux jeux de données concernant la France métropolitaine. Ces données, issues de la SNCF et de l'aviation civile, nous renseignent sur la fréquentation des gares et des aéroports en France métropolitaine.

Nettoyage en amont des données

Pour pouvoir exploiter ces jeux de données, il a fallu nettoyer certains champs. En effet, les plages temporelles de données diffèrent, nous avons donc sélectionnées uniquement les données de 2015 à 2024. De plus, certains lieux ont fermés au fil du temps, nous avons gardés uniquement les gares et aéroports encore en activité en 2024. Enfin, les données de l'aviation civile étaient au mois, une somme a du être effectuée sur les données concernant les aéroports pour les mettre à l'année.

Démarche scientifique

Pour traiter ces données, il est nécessaire d'établir un calcul scientifique précis. Ici, nous avons choisis de résoudre une variante d'un problème d'emplacements d'installations, le but étant de déterminer l'emplacements de n entrepôts parmi tout les emplacements des gares et des aéroports de manière à minimiser la somme des distances pondérées (par le nombre de voyageurs) entre chaque gares ou aéroports et un entrepôt. Notre approche utilise une heuristique gloutonne distribué via Spark afin d'approcher la solution optimale.

Nettoyage

Jeu de données sur le nombre de voyageurs / Gares, chaque gare doit avoir un code postal associé pour pouvoir associé un aéroport du même département (parse_train.py).
Jeu de données aéroport, ajouter un code postal en fonction du code IOCA (parse_aeroport.py).
Jeu de données géographiques de la france pour récupérer les coordonnées géographiques des départements pour les calculs suivants.

Format

IOCA ou UIC, Année (2015-2024), latitude, longitude, Coordonnées.

Définitions :
Le code OACI (ou ICAO code en anglais) est un code attribué par l'Organisation de l'aviation civile internationale (OACI, ou ICAO en anglais) à un aérodrome, une région aérienne, une compagnie aérienne, un type d'aéronef ou une immatriculation d'aéronef.

Le code réseau UIC est un code numérique à deux chiffres attribué par l'Union internationale des chemins de fer (UIC) et par l'Organisation pour la coopération des chemins de fer (OSJD) pour désigner de 1964 à 2003 les compagnies de chemins de fer membres de ces organisations. Ce code intervenait notamment dans la composition des numéros de wagons et de voitures de chemin de fer et était décrit dans la fiche UIC no 920-1 « Codification numérique unifiée des réseaux de Chemin de fer ».

Algorithme de résolution

Notre algorithme se base sur une heuristique au tour par tour, au tour 1, on cherche l'emplacment pour 1 entrepôt qui satisfait le plus les conditions pour toutes les gares et aéroports (distance pondérée par le nombre de voyageurs en fonction des années), puis pour les n-1 prochains tours on recherche un nouvel emplacements en prenant en compte les entrepôts déjà placés, cela nous permet d'éviter de tester toutes les combinaisons possibles tout en s'approchant de la solution optimale.

Installation Hadoop

Nous allons installer Hadoop pour gérer les clusters, ici des machines virtuelles sur Ubuntu.

Versions

• Ubuntu : 24.04
• Java : 11
• Hadoop : 3.4.1

Installation de Java et ajout d'un utilisateur Hadoop

sudo apt update && sudo apt upgrade # mise à jour de la machine

sudo apt install openjdk-11-jdk -y # installation java 11

sudo adduser hadoop # Ajout d'un utilisateur hadoop

sudo usermod -aG sudo hadoop

su hadoop

sudo systemctl start ssh

ssh-keygen -t rsa -P '' -f ~/.ssh/id_rsa

cat ~/.ssh/id_rsa.pub >> ~/.ssh/authorized_keys

chmod 600 ~/.ssh/authorized_keys

Téléchargement d'Hadoop

wget https://dlcdn.apache.org/hadoop/common/hadoop-3.4.1/hadoop-3.4.1.tar.gz # Récupération du paquet

tar -xzf hadoop-3.4.1.tar.gz

sudo mv hadoop-3.4.1 /usr/local/hadoop

sudo chown -R hadoop:hadoop /usr/local/hadoop

sudo nano ~/.bashrc # ajout des variables d'environnement
export HADOOP_HOME=/usr/local/hadoop
export HADOOP_INSTALL=$HADOOP_HOME
export HADOOP_MAPRED_HOME=$HADOOP_HOME
export HADOOP_COMMON_HOME=$HADOOP_HOME
export HADOOP_HDFS_HOME=$HADOOP_HOME
export YARN_HOME=$HADOOP_HOME
export HADOOP_COMMON_LIB_NATIVE_DIR=$HADOOP_HOME/lib/native
export PATH=$PATH:$HADOOP_HOME/sbin:$HADOOP_HOME/bin
export HADOOP_OPTS="-Djava.library.path=$HADOOP_HOME/lib/native"
export JAVA_HOME=$(dirname $(dirname $(readlink -f $(which java))))
export PATH=$PATH:$JAVA_HOME/binecho  

source ~/.bashrc
echo  $JAVA_HOME
echo $HADOOP_HOME

nano $HADOOP_HOME/etc/hadoop/hadoop-env.sh

export JAVA_HOME=/usr/lib/jvm/java-11-openjdk-amd64 # Définition du Java 11 dans hadoop-env.sh

mkdir -p $HADOOP_HOME/hdfs/namenode
mkdir -p $HADOOP_HOME/hdfs/datanode

sudo chown -R hadoop:hadoop $HADOOP_HOME/hdfs

configuration des fichiers XML Hadoop

nano $HADOOP_HOME/etc/hadoop/core-site.xml # configuration des fichiers XML Hadoop

<configuration>
    <property>
        <name>fs.defaultFS</name>
        <value>hdfs://localhost:9000
        <description>The default file system URI</description>
    </property>
</configuration>

nano $HADOOP_HOME/etc/hadoop/hdfs-site.xml

<configuration>
<property>
        <name>dfs.replication</name>
        <value>1</value>
        <description>Default block replication.</description>
    </property>
    <property>
        <name>dfs.name.dir</name>
        <value>file:///usr/local/hadoop/hdfs/namenode
        <description>Path on the local filesystem where the NameNode stores the namespace and transaction logs.</description>
    </property>
    <property>
        <name>dfs.data.dir</name>
        <value>file:///usr/local/hadoop/hdfs/datanode
        <description>Path on the local filesystem where the DataNode stores its blocks.</description>
    </property>
</configuration>

nano $HADOOP_HOME/etc/hadoop/mapred-site.xml

<configuration>
<property>
        <name>mapreduce.framework.name</name>
        <value>yarn</value>
        <description>The runtime framework for MapReduce. Can be local, classic or yarn.</description>
    </property>
    <property>
        <name>yarn.app.mapreduce.am.env</name>
        <value>HADOOP_MAPRED_HOME=/usr/local/hadoop</value>
    </property>
    <property>
        <name>mapreduce.map.env</name>
        <value>HADOOP_MAPRED_HOME=/usr/local/hadoop</value>
    </property>
    <property>
        <name>mapreduce.reduce.env</name>
        <value>HADOOP_MAPRED_HOME=/usr/local/hadoop</value>
    </property>
</configuration>

nano $HADOOP_HOME/etc/hadoop/yarn-site.xml

<configuration>
 <property>
        <name>yarn.nodemanager.aux-services</name>
        <value>mapreduce_shuffle</value>
        <description>Auxilliary services required by the NodeManager.</description>
    </property>
</configuration>

Lancement d'Hadoop

hdfs namenode -format

hadoop fs -mkdir -p /user/hadoop # ajtout d'un répertoire pour hdfs

hadoop fs -put ~/test.txt

start-dfs.sh # lancement de hdfs

start-yarn.sh # Lancement de yarn

jps # Vérification des processus

HDFS NameNode UI: http://localhost:9870

YARN ResourceManager UI: http://localhost:8088

Installation Spark

sudo apt install default-jdk scala git -y

wget https://dlcdn.apache.org/spark/spark-3.5.1/spark-3.5.1-bin-hadoop3.tgz

tar xvf spark-*.tgz

sudo mv spark-3.5.1-bin-hadoop3 /opt/spark

/opt/spark/bin/spark-shell --version

export SPARK_HOME=/opt/spark # ajout à .bashrc
export PATH=$PATH:$SPARK_HOME/bin:$SPARK_HOME/sbin
export PYSPARK_PYTHON=/usr/bin/python3

Lancement de Spark

Workers

start-worker.sh spark://172.28.101.172:7077 # Ajouter un worker 

Master

spark-submit --master spark://cluster1:7077 main-spark-glt.py 10 # lancement du calcul

Expérimentation

Prérequis

• Python 3
• Pyspark
• geopandas

Carte actuelle

Pour tester nos données (2015-2024), on peut visualiser les données des gares et des aéroports, sous forme de carte :

Fig 1 : Carte de la France métropolitaine, gares en rouge et aéroports en vert.

Exemple de logs

Fig 2 : Exemple de logs d'exécution du programme.

Cartes

Fig 3 : Carte de 10 points placés par l'algorithme.

Fig 4 : Carte de 100 points placés par l'algorithme.

Fig 4 : Carte de 200 points placés par l'algorithme.

Performances

En local

Une machine :

• 4 coeurs (3.00 GHz)
• 15 GiB de RAM

Nombre d'entrepôts (i.e. de points)	Temps d'exécution (en seconde)
10	22.43 s
100	158.8 s
200	235.8 s

Parallélisé

4 VMs :

• 4x2 coeurs (2.09 GHz)
• 4x2 4 GiB de RAM

La machine maître est aussi une Worker.

Nombre d'entrepôts (i.e. de points)	Temps d'exécution (en seconde)
10	50.87 s
100	314.86 s
200	606.60 s

En moyenne, 200 % plus long qu'en local.

Conclusion

Suite aux nombreux tests effectués sur notre machine et avec le paraléllisme du code Spark, celui-ci nous fait perdre en performance malgré l'usage du paraléllisme. En effet, le coût du parallélisme de Spark, comprenant les communications et l'usage du réseau fait perdre en performance. C'est pourquoi, il est plus pertinent de l'utiliser dans des contextes de grands jeux de données (e.g. en Pétaoctet), avec un nombre plus important de machines. Pour conclure notre expérience, nous remarquons que les points placés par l'algorithme sont cohérents avec le trafic français de 2015 à 2024, les grands axes sont conservés comme on peut le constater sur les cartes générées (_cf. partie Résultats).

Références

1. Trafic aérien (1990-2024), aviation civile (DGAC).

2. Fréquentation en gares (2015-2024), SNCF.

3. Coordonnées des aéroports, Ministère de la transition écologique.

4. Coordonnées des gares françaises de voyageurs de plus de 5000 voyageurs par an, SNCF.

5. Aéroports en France, Wikipédia.

6. Documentation Spark pour traiter les fichiers au format CSV, Apache.

7. Guide d'installation d'Hadoop sur Ubuntu, CherryServers.

8. Guide d'installation de Spark sur Ubuntu, Phoenixnap.

9. Code UIC, Wikipédia.

10. Code OACI, Wikipédia.

Binôme

• CLEME Louis
• SIGNOURET Nathan