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.
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.
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.
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.
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.
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 ».
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.
Nous allons installer Hadoop pour gérer les clusters, ici des machines virtuelles sur Ubuntu.
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
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
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>
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
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
start-worker.sh spark://172.28.101.172:7077 # Ajouter un worker
spark-submit --master spark://cluster1:7077 main-spark-glt.py 10 # lancement du calcul
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.
Fig 2 : Exemple de logs d'exécution du programme.
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.
Une machine :
| 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 |
4 VMs :
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.
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).
Coordonnées des aéroports, Ministère de la transition écologique.
Coordonnées des gares françaises de voyageurs de plus de 5000 voyageurs par an, SNCF.
Documentation Spark pour traiter les fichiers au format CSV, Apache.