PRINCIPE D’UN SYSTEME DISTRIBUE PAR CLUSTER COMPUTING AVEC APACHE MESOS ET SPARK

Télécharger le fichier pdf d’un mémoire de fin d’études

Système à mémoires partagées

Les machines à mémoire partagée ont une mémoire unique à laquelle tous les processeurs ont accès. Dès lors qu’un processeur a fini d’utiliser une donnée, ou a calculé un résultat, et que cette donnée ou ce résultat est de nouveau stocké dans la mémoire de l’ordinateur, n’importe quel autre processeur peut en disposer, la mémoire étant une ressource globale. D’une manière générale, les processeurs s’échangent des informations grâce à une mémoire ou des variables communes qu’ils peuvent tous lire et modifier à l’aide d’instructions du type READ et WRITE.

Mémoires distribuées (message passing)

Les ordinateurs à mémoire distribuée ne disposent pas de mémoire commune accessible par l’ensemble des processeurs. Chaque processeur possède sa propre mémoire qui lui est strictement attachée, et aucun autre processeur ne peut y accéder. Dans ce cas la mémoire est locale à chaque processeur. Lorsqu’un processeur a besoin d’une donnée stockée dans la mémoire locale d’un autre processeur, il doit en faire la demande explicite au processeur en question qui en réponse lui transmettra la donnée via le réseau de communication de l’ordinateur. En effet, dans le cas des machines à mémoire distribuée, les processeurs sont connectés entre eux par un réseau physique, la topologie de ce réseau variant d’une machine à l’autre. Cette demande est réalisée grâce à des instructions du type SEND et RECEIVE.

Aperçu sur la communication inter-système

Chaque processeur ne peut communiquer directement qu’avec un certain nombre de processeurs, ses voisins. On modélise de tels systèmes naturellement par un graphe connexe. Les sommets sont les processeurs, et les arêtes les liens directs de communication. On supposera que le graphe est non-orienté et sans multi-arêtes. [1]

Réseau de diffusion

Chaque processeur peut communiquer le même message simultanément à un certain nombre de récepteur, comme un émetteur radio le ferait. Là encore il y a de nombreuses variantes suivant que les réceptions multiples en un processeur créent ou non des collisions et si les collisions sont détectables en tant que telles. [1]

Etapes de partitionnement de fonction dans le traitement distribué et placement

Le partitionnement vise à découper un problème en plusieurs sous-problèmes. Il s’agit de découper les calculs et les données relatives en tâches aussi indépendantes que possible les unes des autres, une tâche étant constituée par les calculs et les données associées.
Le partitionnement est généralement suivi d’une étape d’agglomération afin :
 d’augmenter la taille des tâches en les regroupant.
 d’équilibrer leur taille pour réduire les disparités sur les temps de calcul de chaque tâche.
 de diminuer le volume des communications entre ces tâches.
La taille d’une tâche est déterminante pour le temps calcul puisque plus une tâche est dite petite, c’est-à-dire qu’elle représente une faible charge de travail, plus le temps de calcul requis pour son exécution sera court. D’autre part, plus un problème est découpé en un nombre important de tâches, meilleur est le parallélisme potentiel.
La qualité d’un partitionnement repose sur les trois critères suivants :
 découper le problème en divisant le calcul aussi bien que les données.
 découper le problème en tâches de tailles à peu près identiques.
 découper le problème en tâches aussi indépendantes que possible.
Diviser le calcul et les données, c’est ce qui constitue l’approche du calcul distribué. Le problème consiste à découper intelligemment les données en fonction des calculs et réciproquement pour préserver le plus possible l’indépendance des tâches.
Construire des tâches de taille identique permet d’équilibrer la charge de travail par processeur. Il est clair que quel que soit le nombre de tâches, le temps calcul sera de toutes manières supérieur au temps nécessaire pour effectuer la tâche la plus longue.
La considération de la machine cible est le plus souvent repoussée à la phase de placement qui consiste à affecter effectivement les tâches aux processeurs. Il n’est cependant pas interdit de prendre en compte les paramètres de la machine dans les étapes préliminaires mais c’est souvent hors de propos car d’une part trop complexe et d’autre part cela réduit les garanties de portabilité du programme parallèle. [2]

Systèmes distribués de systèmes

Un rapport récent traite de l’émergence de systèmes distribués à très grande échelle (Ultra-Large-Scale ou ULS). Le rapport stipule la complexité des systèmes distribués modernes en se référant à de telles architectures (physiques) en tant que systèmes de systèmes (reflétant la vision d’internet en tant que réseau de réseaux). Un système de systèmes peut être défini comme un système complexe constitué d’une série de sous-systèmes qui sont des systèmes à part entière et qui se réunissent pour exécuter une tâche ou des tâches particulières.
À titre d’exemple d’un système de systèmes, envisageons un système de gestion de l’environnement pour la prévision des inondations. Dans un tel scénario, des réseaux de capteurs seront déployés pour surveiller l’état de divers paramètres environnementaux relatifs aux rivières, aux plaines inondables, aux effets de marées, etc. Cela peut ensuite être couplé avec des systèmes qui sont responsables de la prédiction de la probabilité d’inondations, en exécutant des simulations (souvent complexes) sur, par exemple, des ordinateurs en cluster. D’autres systèmes peuvent être mis en place pour maintenir et analyser les données historiques ou pour fournir des systèmes d’alerte précoce aux principales parties prenantes via les téléphones mobiles. [5]

Eléments architecturaux

Pour comprendre les blocs de construction fondamentaux d’un système distribué, il est nécessaire de considérer quatre questions clés : Quelles sont les entités qui communiquent dans le système distribué ? Comment communiquent-ils, ou plus précisément, quel paradigme de communication est utilisé ? Quels rôles et responsabilités (potentiellement changeants) ont-ils dans l’architecture globale ? Comment sont-ils mappés sur l’infrastructure physique distribuée (quel est leur emplacement) ?
 Entités communicantes : Les deux premières questions ci-dessus sont absolument essentielles à la compréhension des systèmes distribués ; ce qui communique et comment ces entités communiquent ensemble, définissent un espace de conception riche pour le développeur de systèmes distribués. Il est utile d’aborder la première question d’un point de vue systémique et orienté sur les problèmes. Du point de vue du système, la réponse est normalement très claire dans la mesure où les entités qui communiquent dans un système réparti sont généralement des processus, conduisant à la vision dominante d’un système distribué en tant que processus couplés à des paradigmes de communications interprocessus appropriés, avec deux mises en garde :
 Dans certains environnements primitifs, tels que les réseaux de capteurs, les systèmes d’exploitation sous-jacents peuvent ne pas prendre en charge les abstractions de processus (ou toute forme d’isolation)
 Dans la plupart des environnements distribués, les processus sont complétés par des threads, donc, à proprement dit, ce sont les threads qui sont les points de terminaison de la communication.

Solutions middleware associées

Le middleware a déjà été introduit dans le chapitre 1 et revu dans la discussion sur la superposition. La tâche du middleware est de fournir une abstraction de programmation de plus haut niveau pour le développement de systèmes distribués et, par superposition, d’abstraire l’hétérogénéité de l’infrastructure sous-jacente pour promouvoir l’interopérabilité et la portabilité. Les solutions middleware sont basées sur les modèles architecturaux. [5]

Programmes distribués

Un programme réparti est composé d’un ensemble de ? processus asynchrones ?1, ?2,… ??, … ?? qui peuvent se communiquer par passage de messages sur le réseau de communication. Dans un contexte général, nous supposons que chaque processus s’exécute sur des processeurs différents. Les processus ne partagent pas une mémoire globale et communiquent uniquement par transmission de messages.
Soit ??? le canal du processus ??au processus ??et soit ??? un message envoyé par ??à ??. Le délai de communication est limité et imprévisible. De plus, ces processus ne partagent pas une horloge globale instantanément accessible à ces processus. L’exécution du processus et le transfert des messages sont asynchrones.
L’état global d’un calcul distribué est composé des états des processus et des canaux de communication. L’état d’un processus est caractérisé par l’état de sa mémoire locale et dépend du contexte. L’état d’un canal est caractérisé par l’ensemble des messages en transit dans le canal. [9]

Modèle d’exécutions distribuées

L’exécution d’un processus consiste en une exécution séquentielle de ses actions. Les actions sont atomiques et les actions d’un processus sont modélisées comme trois types d’événements, à savoir, les événements internes, les événements d’envoi de message et les événements de réception de message.
Soit ??? le ?-ème événement au processus ??. Pour un message ?, ????(?) et ???(?) dénote ses évènements d’envoi et de réception, respectivement.
L’apparition d’événements modifie les états des processus et canaux respectifs, provoquant ainsi des transitions dans l’état global du système.
Un événement ???? (ou un événement ???????) modifie l’état du processus qui envoie (ou reçoit) le message et l’état du canal sur lequel le message est envoyé (ou reçu). Un événement interne affecte uniquement le processus auquel il se produit.
Les événements d’un processus sont triés linéairement selon leur ordre d’occurrence. L’exécution du processus ?? produit une suite d’événements ??1, ??2,…, ???, ???+1 et est désigné par ℋ? :
ℋ?=(ℎ?,→?) (2.01).
où ℎ? est l’ensemble des événements produits par ?? et la relation binaire →? définit un ordre linéaire sur ces événements. La relation (→?) exprime des dépendances causales parmi les événements de ??.
Les événements ???? et ??????? signifient le flux d’informations entre les processus et établissent une dépendance causale entre le processus émetteur et le processus récepteur.
Une relation →??? qui capture la dépendance causale due à l’échange de messages est définie comme suit :
Pour chaque message ? qui est échangé entre deux processus, nous avons : ????(?)→??????(?).

Etat global d’un système

L’état global d’un système distribué est une collection des états locaux de ses composants, à savoir les processus et les canaux de communication. L’état d’un processus à tout moment est défini par le contenu des registres du processeur, des piles de la mémoire locale, etc. et dépend du contexte local de l’application distribuée. L’état d’un canal est donné par l’ensemble des messages en transit dans le canal.
L’apparition d’événements modifie les états des processus et canaux respectifs, provoquant ainsi des transitions dans l’état du système global. Par exemple, un événement interne modifie l’état du processus auquel il se produit. Un événement send (ou un événement receive) modifie l’état du processus qui envoie (ou reçoit) le message et l’état du canal sur lequel le message est envoyé (ou reçu).
Soit ???? l’état du processus ?? apres l’apparition de l’évènement ??? et avant l’évènement ???+1. Soit ???0 l’état initial du processus ??. ???? est le résultat de l’exécution de tous les évènements jusqu’à l’apparition de ???.
Soit ????(?)≤???? du fait que ∀?:1≤?≤? , ???=????(?). De même, ???(?)≰???? du fait que ∀?:1≤?≤? ???≠???(?).
L’état d’un canal de communication est difficile définir formellement car le canal est une entité distribuée et son état dépend de l’état des processus qui lui sont rattachés. Soit ?????? l’état du canal qui peut être défini comme suit : ??????={???|????(???)≤???? ⋀ ???(???)≰????} (2.03).
Ainsi, l’état ??????est défini comme tous les messages que ?? partant de l’évènement ??? et que le processus ?? n’a pas encore reçu jusqu’à l’évènement ???. [9]
D’une notation intuitive, l’état global GS est alors défini comme : ??={⋃?????,⋃??????,??,?,? ?} (2.04).

Checkpointing ou point de contrôle et le rollback ou restauration 

Aujourd’hui, les systèmes distribués sont omniprésents et permettent de nombreuses applications, y compris les systèmes client-serveur, le traitement des transactions, le World Wide Web et l’informatique scientifique. Les systèmes distribués ne tolèrent pas les pannes et le grand potentiel de calcul de ces systèmes est souvent entravé par leur susceptibilité aux pannes. De nombreuses techniques ont été développées pour améliorer la fiabilité et la haute disponibilité des systèmes distribués. Ces techniques incluent les transactions, la communication de groupe et la restauration. La restauration traite une application système répartie comme une collection de processus qui communiquent sur un réseau. Il atteint la tolérance aux pannes en sauvegardant périodiquement l’état d’un processus pendant l’exécution sans défaillance, ce qui lui permet de redémarrer à partir d’un état sauvegardé en cas d’échec pour réduire la quantité de travail perdu. L’état enregistré est appelé un point de contrôle et la procédure de redémarrage à partir d’un état précédemment vérifié est appelée restauration. Un point de contrôle peut être sauvegardé sur le stockage stable ou sur le stockage volatile en fonction des scénarios de défaillance à tolérer.
Dans les systèmes distribués, la restauration est compliquée car les messages induisent des dépendances interprocessus lors d’un fonctionnement sans échec. En cas de défaillance d’un ou de plusieurs processus dans un système, ces dépendances peuvent forcer certains processus qui n’ont pas échoué à revenir en arrière, ce qui est généralement appelé une propagation de restauration. Pour voir pourquoi la propagation de restauration se produit, considérons la situation où l’expéditeur d’un message ? revient à un état qui précède l’envoi de ?. Le destinataire de ? doit également revenir à un état qui précède la réception de ?; sinon, les états des deux processus seraient incohérents car ils montreraient que le message ? a été reçu sans être envoyé, ce qui est impossible dans toute exécution correcte sans défaillance. Ce phénomène de restauration en cascade est appelé l’effet domino. Dans certaines situations, la propagation de restauration peut revenir à l’état initial du calcul, perdant tout le travail effectué avant la panne.
Dans un système distribué, si chaque processus participant prend ses points de contrôles indépendamment, alors le système est sensible à l’effet domino. Cette approche est appelée point de contrôle indépendant ou non coordonné. Il est évidemment souhaitable d’éviter l’effet domino et donc plusieurs techniques ont été développées pour l’empêcher. Une telle technique est un point de contrôle coordonné où les processus coordonnent leurs points de contrôle pour former un état cohérent à l’échelle du système. En cas de défaillance d’un processus, l’état du système peut être restauré sur un ensemble cohérent de points de contrôles, ce qui empêche la propagation de l’annulation. En variante, le point de contrôle induit par la communication oblige chaque processus à prendre des points de contrôles en fonction des informations greffées sur les messages d’application qu’il reçoit d’autres processus. Les points de contrôles sont pris de telle sorte qu’un état cohérent à l’échelle du système existe toujours sur un stockage stable, évitant ainsi l’effet domino. [9]

Modèle de réseaux de communications et modèle de transfert de messages pour une communication interprocessus

La communication interprocessus est une dimension de la variabilité dans un système distribué. Deux modèles principaux capturent l’essence de la communication interprocessus dont le modèle de passage de message et le modèle de mémoire partagée comme vue dans le chapitre précédent.

Actions de processus

On représente un système distribué par un graphe ?=(?,?), où ? est un ensemble de noeuds et ? est un ensemble d’arêtes joignant des paires de noeuds. Chaque noeud est un processus séquentiel, et chaque front correspond à un canal de communication entre deux processus.
Les actions d’un noeud peuvent être divisées en quatre classes :
 Action interne : Une action est une action interne lorsqu’un processus effectue des calculs dans son propre espace d’adressage entraînant la modification d’une ou de plusieurs de ses variables locales.
 Action de communication : Une action est une action de communication lorsqu’un processus envoie un message à un autre processus ou reçoit un message d’un autre processus.
 Action d’entrée : une action est une action d’entrée lorsqu’un processus lit des données provenant de sources externes au système.
 Action de sortie : une action est une action de sortie lorsqu’elle contrôle des opérations externes au système [10]

Table des matières

CHAPITRE 1 GENERALITES SUR LES SYSTEMES DISTRIBUES
1.1 Introduction
1.2 Définitions
1.3 Bref historique de l’apparition de ces systèmes
1.4 Exemples de systèmes distribués
1.4.1 Recherche sur le Web
1.4.2 Jeux en ligne massivement multi-joueurs (JLMM)
1.4.3 Système informatique financier
1.5 Nature de la distribution
1.6 Type de systèmes distribués
1.6.1 Système embarqué distribué
1.6.2 Système d’information distribué
1.6.3 Systèmes informatiques distribués
1.7 Migration vers des systèmes distribués
1.7.1 Rapidité d’exécution
1.7.2 Besoin de mémoire
1.7.3 Traitement distribué
1.8 Relation entre les composants des systèmes distribués
1.9 Défis dans le domaine
1.9.1 Hétérogénéité
1.9.2 Extensibilité
1.9.3 Sécurité
1.9.4 Évolutivité
1.9.4.1 Contrôler le coût des ressources physiques
1.9.4.2 Contrôler la perte de performance
1.9.4.3 Se prévenir de l’épuisement des ressources logicielles
1.9.4.4 Éviter les goulots d’étranglement au niveau des performances
1.9.5 Gestion des défaillances
1.9.5.1 Détection des failles
1.9.5.2 Masquage
1.9.5.3 Tolérer des pannes
1.9.5.4 Récupération après pannes
1.9.5.5 Redondance
1.9.6 Concurrence
1.9.7 Transparence
1.9.8 Qualité de service
1.11 Sous-problèmes communs dans les systèmes distribués
1.11.1 Election de leader
1.11.2 Exclusion mutuelle
1.11.3 Synchronisation de l’horloge
1.11.4 Etat global
1.11.5 Multidiffusion
1.11.6 Gestion des répliques
1.12 Désavantages rencontrés
1.13 Introduction aux modèles des systèmes distribués
1.13.1 Types de modèles de systèmes distribués
1.13.1.1 Système à mémoires partagées
1.13.1.2 Mémoires distribuées (message passing)
1.13.2 Aperçu sur la communication inter-système
1.13.2.1 Point-à-point
1.13.2.2 Réseau de diffusion
1.13.3 Etapes de partitionnement de fonction dans le traitement distribué et placement
1.13.3.1 Partitionnement
1.13.3.2 Placement
1.14 Conclusion
CHAPITRE 2 MODELES ET CONCEPTIONS DE SYSTEMES DISTRIBUES
2.1 Introduction
2.2 Conception de systèmes distribués
2.2.1 Motifs architecturaux généraux des systèmes
2.2.1.1 Les modèles physiques
2.2.1.2 Les modèles architecturaux
2.2.2 Programmes distribués
2.2.3 Modèle d’exécutions distribuées
2.2.4 Etat global d’un système
2.2.5 Checkpointing ou point de contrôle et le rollback ou restauration
2.2.6 Modèle de réseaux de communications et modèle de transfert de messages pour une communication interprocessus
2.2.6.1 Actions de processus
2.2.6.2 Canaux de communication
2.2.6.3 Systèmes synchrones et systèmes asynchrones
2.2.7 Modèle Maître-esclave
2.3 Sécurité dans les systèmes distribués
2.3.1 Chiffrement
2.3.2 Signature numérique
2.3.3 Hachage
2.3.4 Sécurité pour les clusters informatiques
2.3.4.1 Authentification distribuée
2.3.4.2 Contrôle d’accès distribué
2.3.4.3 Surveillance ou monitoring distribuée
2.3.4.4 Communications sécurisées distribuées
2.3.5 Sécurité du système de grille
2.4 Conclusion
CHAPITRE 3 PRINCIPE D’UN SYSTEME DISTRIBUE PAR CLUSTER COMPUTING AVEC APACHE MESOS ET SPARK
3.1 Introduction
3.2 Cluster Computing
3.2.1 Composants matériels
3.2.2 Matériel de noeud de cluster
3.2.3 Matériel de réseau de cluster
3.2.4 Composants logiciels
3.3 Apache Spark
3.3.1 Introduction sur Spark
3.3.1.1 Apache Hadoop
3.3.1.2 Quelques points sur la concurrence Hadoop et Spark
3.3.2 Naissance d’Apache Spark
3.3.3 Fonctionnement de Spark pour le big data
3.3.4 Modèle de calculs parallèles avec Spark
3.3.4.1 L’évaluation paresseuse
3.3.4.2 Stockage en mémoire et gestion de la mémoire
3.3.4.3 Immuabilité et l’interface RDD
3.3.4.4 Transformations et Actions
3.3.4.5 Dépendances larges et étroites
3.3.5 Ordonnanceur de job Spark
3.3.5.1 Allocation de ressources à travers les applications
3.3.5.2 Applications Spark
3.3.5.3 Anatomie d’un job Spark
3.3.5.4 Graphe Acyclique Dirigé
3.3.5.5 Travail ou job
3.3.5.6 Étapes
3.3.5.7 Tâches
3.3.6 Concept de partitionnement en Spark
3.4 Apache Mesos
3.4.1 Introduction à Mesos
3.4.2 L’architecture de Mesos
3.4.3 Frameworks de Mesos
3.4.4 Ordonnancement à deux niveaux
3.4.5 Allocation de ressources
3.4.5.1 Rôles
3.4.5.2 Pondérations
3.4.5.3 Réservation de ressources
3.4.6 Isolation des ressources
3.4.7 Haute disponibilité et tolérance aux pannes
3.4.7.1 Contrôler la haute disponibilité
3.4.7.2 Tolérance aux pannes de l’ordonnanceur du framework
3.4.7.3 Tolérance de panne esclave
3.4.7.4 Défaillance de la tâche ou de l’exécuteur
3.4.7.5 Récupération esclave
3.4.7.6 Réconciliation
3.5 Apache Spark sur Apache Mesos
3.6 Conclusion
CHAPITRE 4 APACHE SPARK AVEC MESOS POUR LES TRAITEMENT COMPLEXES : MULTIPLICATION DISTRIBUEE DE LARGE MATRICE ET RECHERCHE DE GRAND NOMBRE PREMIER.
4.1 Introduction
4.2 Multiplication distribuée de large matrice avec Apache Spark et la Marlin library
4.2.1 Introduction
4.2.2 Matrice distribuée par Apache Spark
4.2.2.1 RowMatrix et IndexedRowMatrix
4.2.2.2 CoordinateMatrix
4.2.2.3 BlockMatrix
4.2.3 Vecteurs locaux et matrices
4.2.4 Quelques bibliothèques utilisées dans la multiplication matricielle : Breeze, BLAS, JBLAS
4.2.5 Fonctionnalités mise en jeu dans les calculs matriciels par Marlin
4.2.5.1 Accélération par de bibliothèque d’algèbre linéaire native
4.2.5.2 Tolérance aux pannes en mode grain fin (fine-grained) et facilité d’utilisation
4.2.5.3 Opérations matricielles distribuées efficaces
4.2.6 Approche 1: Multiplication matricielle par division de blocs
4.2.7 Approche 2: Multiplication matricielle CARMA
4.2.8 Approche 3: Multiplication de la matrice par diffusion
4.2.9 Approches Analyse et Sélection
4.3 Installation et dépendances requises dans le déploiement de notre système distribué .
4.3.1 Installation d’Apache Mesos et mise en marche sur Debian 9
4.3.1.1 Dépendances requises
4.3.1.2 Compilation des sources de Mesos
4.3.1.3 Configuration de l’Apache Zookeeper
4.3.1.4 Premier lancement du Mesos maître
4.3.1.5 Premier lancement du Mesos agent ou esclave
4.3.1.6 Configuration et installation de Hadoop v.2.7.6 sur le maître
4.3.1.7 Téléversement du package Spark
4.3.2 Configuration d’Apache Spark et premier lancement
4.3.2.1 Configuration des variables
4.3.2.2 Premier lancement
4.3.3 Remarque
4.4 Réalisation de la multiplication matricielle
4.4.1 Résultat de multiplication
4.4.2 Interface de monitoring de l’application
4.4.3 Facteur défaillant de la performance de l’application
4.5 Recherche de grand nombre premier
4.5.1 Le nombre premier
4.5.2 Défi dans la recherche de nombre premier
4.5.3 Approche de calcul dans notre application
4.5.4 Application
4.6 Conclusion
CONCLUSION GENERALE
ANNEXE 1 PRINCIPES FONDAMENTAUX DE SCALA
ANNEXE 2 MONTAGES MATERIELS DU SYSTEME UTILISE
BIBLIOGRAPHIE

Télécharger le rapport complet