Module 5 : Introduction aux bases de données NoSQL
Riadh ZAAFRANI Novembre 2020
1ère année MP2L
1
2
Plan
◼Introduction ◼Contexte
◼Recherche sur le Web ◼Système distribué
◼Bases NoSQL ◼Types des BDDs NoSQL ◼Conclusion
1
2
1
Introduction
➢ NoSQL : ”Not Only SQL”, ce n’est pas du relationnel, et le contexte d’utilisation n’est donc pas celui des SGBDR. ➢ Origine : recherche d’information sur le web, moteurs type Google, Yahoo, données des réseaux sociaux, Facebook, Twitter, LinkedIn …
➢ Besoin de stockage d’énormes masses de données. Twitter par exemple reçoit plusieurs Tera-octets de données par jour. ➢ Système distribué ➢ table d’associations - Map - de couples (clef,valeur) ➢ Différentes approches, rangées dans la famille ”NoSQL”.3
3
Introduction
Pourquoi ces technologies sont passées des acteurs du web au ”grand public” ? ➢Big Data → Volume, Variété, Vélocité ➢Exploitation
externes ajoutées aux données internes, quelles (relationnelles, structurées soient multidimensionnelles) (e.g. documentaires)
données
non
de
ou
4
4
2
Introduction
➢ Quelques exemples de Big Data :
:
(données
➢ Service marketing
informatique
décisionnelle couplée avec ”classique” l’exploitation non internes structurés), et des réseaux sociaux (données externes non structurées).
structurées), (données
de mails
➢ Recherche Scientifique : capteurs qui
ramènent énormément de données numériques (accélérateur de particules, télescope, ...) ou nécessité de partager des données très volumineuses (génomique, ...)
➢ NoSQL
n’est
qu’une
partie
de
cette
vaste
problématique du Big Data.
5
5
6
Plan ◼Introduction ◼Contexte
◼Recherche sur le Web ◼Système distribué
◼Bases NoSQL ◼Types des BDDs NoSQL ◼Conclusion
6
3
Contexte : Recherche sur le Web
➢ Collecter les documents publiés sur le web = ”web crawling”. + détecter des changements sur un document déjà parcouru.
➢ Traiter
ces
l’information significatifs
documents
pour contiennent
qu’ils
extraire : mots
➢ construire un index permettant de retrouver les documents les plus pertinents pour 1 mot clef ou un ensemble de mots clefs = ”inverted files”
7
7
Inverted File
➢ comme le glossaire d’un livre ➢ à 1 mot clef on associe une collection de documents
qui contiennent ce mot
8
8
4
Inverted File - structure
◼ on connaît le nombre de documents ni associés à un
terme ti .
◼ on donne un poids wk à chaque document dk associé au terme ti. Le poids traduit la pertinence du document pour ce terme.
9
9
10
Plan ◼Introduction ◼Contexte
◼Recherche sur le Web ◼Système distribué
◼Bases NoSQL ◼Types des BDDs NoSQL ◼Conclusion
10
5
Système distribué
➢ Système distribué = système logiciel qui permet de coordonner plusieurs ordinateurs. Généralement, cette coordination se fait par envoi de messages via un réseau auquel sont reliés ces ordinateurs.
➢ Pourquoi ? parce qu’on manipule un très grand volume de données. Sans distribution, on n’a pas d’application ”scalable”.
11
11
Scalabilité horizontale et verticale
◼ Avec l'explosion de la taille des données à gérer les bases de que connaissent certaines sociétés, données traditionnelles n'arrivent pas à fournir un alors deux temps de solutions sont envisageables :
satisfaisant,
réponse
◼ Soit augmenter les ressources de la machine (la puissance du processeur, la mémoire, etc.) : c'est ce que l'on appelle une scalabilité verticale
◼ Soit utiliser un cluster de machines, c'est ce que
l'on appelle une scalabilité horizontale.
12
12
6
Scalabilité horizontale et verticale
◼ La première solution (scalabilité verticale), a ses limites. En effet, on ne peut pas augmenter la puissance du processeur à l'infini, par exemple, d'autant plus que l'augmentation des performances des composants est plus suivie importante.
augmentation
encore
d'une
prix
du
◼ La seconde solution (scalabilité horizontale) permet en théorie, une augmentation illimitée des capacités avec un coût de revient moindre, car il suffit d'ajouter d'autres machines au cluster.
◼ Attention : au-delà d'une certaine taille de données, il n'y
a que la deuxième solution qui demeure plausible.
13
13
Scalabilité horizontale et verticale
◼ Le problème, c'est que dans un cluster, les points forts des bases de données relationnelles, transactions, jointures et propriétés ACID (Atomicity, Consistency, Isolation, Durability) handicapent les temps de réponse.
◼ C'est suite à ce constat que les bases de données NoSQL ont émergé, ces bases se caractérisant par l'abandon des jointures et des transactions au profit d'un temps de réponse court.
◼ La question qui se pose est donc de savoir comment concevoir son schéma de données dans un tel contexte ? ◼ La solution réside dans la dénormalisation des données14
14
7
Système distribué
◼ On peut imaginer 2 scenarii de traitement des
données : 1. On dispose d’un grand ensemble de données, et on doit leur appliquer des traitements disponibles sur des sites distincts. Il faut donc envoyer les données aux endroits appropriés, et enchaîner exécutions distantes. C’est un scénario de type Workflow, implémenter avec des web que l’on peut services → Traitements distribués.
les
15
15
16
Système distribué
2. Les données sont distribuées sur un certain les nombre de serveurs, et on ”pousse” programmes vers ces serveurs. Il est en effet plus efficace de transférer un petit programme sur le réseau plutôt qu’un grand volume de données → Données distribuées. On MapReduce qui utilise cette approche.
l’algorithme
cours
verra
Publicité
dans
ce
16
8
Exemple : Data Centers de Google
➢ Utilise des LANs (Local Area Networks). On
distingue 3 niveaux de communication : 1. Les serveurs sont regroupés en ”racks”. Liaison réseau rapide, environ 1Go/sec.
2. Un data center consiste en un grand nombre de racks, interconnectés par des routeurs (switches). Liaison à 100 Mo/sec.
3. Entre différents data centers, il y a aussi une
possibilité de communication mais par liaison assez lente (internet - 2-3 Mo/sec)
17
17
Exemple : Data Centers de Google
➢ Les serveurs communiquent par envoi de messages, Ils ne
partagent pas de disque ni de ressource de traitement. = architecture ”shared nothing”.
➢ Début 2010 : 1 data center Google contient entre 100 et 200 racks, chacun contenant 40 serveurs. Environ 5000 serveurs par data-center pour un total de 1 millions de serveurs (estimation d’après la consommation électrique).
➢ 2010 : 1 Data center de Facebook :
➢ 2500 cpu (serveurs) ➢ 1 PetaByte dʼespace disque (= milleTerabytes) ➢ Plus de 250 Gigabytes données compressées (plus de 2
Terabytes non compressés)
18
18
9
Schéma : LAN/data center
19
Le théorème CAP
➢ Aucun système distribué ne peut fournir les 3 propriétés suivantes :
tous les nœuds voient
1. Consistency (cohérence) : exactement les mêmes données en même temps : L’échec d’un nœud 2. Availability (disponibilité) n’empêche pas les survivants de continuer à fonctionner 3. Partition tolerance (résistance au partitionnement) : Le système continue à fonctionner malgré la perte d’un message dû à une panne. Autrement dit, en cas de morcellement du réseau, chaque sous-réseau doit pouvoir fonctionner de façon autonome.
20
19
20
10
Le théorème CAP expliqué
◼ Pourquoi est-il
impossible de satisfaire les 3 propriétés
CAP en même temps?
◼ Soit un système distribué. On est entrain de modifier une donnée sur le nœud N1 et d’essayer de la lire à partir du nœud N2 ◼ N2 peut retourner la dernière bonne valeur dont il dispose, ce
qui viole la Consistance
◼ N2 attend que la nouvelle valeur lui parvienne. Comme c’est chances d’un échec de un système distribué, les transmission sont assez importantes, ce qui provoquera une attente infinie de N2. D’où une violation de la Disponibilité ◼ Si on veut satisfaire à la fois la consistance et la disponibilité, le système de stockage ne doit pas être partitionné. D’où violation de la Tolérance au partitionnement.
21
21
Le théorème CAP
pendant l’envoi du message M, d ≠ d’
➢ en général,
la résistance au partitionnement n’est pas discutable dans un système distribué : on doit choisir en A+P ou C+P
➢ Un SGBD relationnel classique va privilégier C+P, avec un système transactionnel distribué et la vérification des propriétés ACID. C’est au détriment des performances !
22
➢ En NoSQL, on choisit plutôt A+P. 22
11
Caractéristiques des Bases NoSQL
◼ Privilégient la Disponibilité à la Cohérence (théorème de CAP) ◼ AP (Disponible + Résistant au partitionnement) plutôt que CP (Cohérent + Résistant au partitionnement)
◼ Généralement elles
n’intègrent pas de gestion de transactions
◼ Mode d'utilisation : peu
d'écritures, beaucoup de lectures
23
24
Plan ◼Introduction ◼Contexte
◼Recherche sur le Web ◼Système distribué
◼Bases NoSQL ◼Types des BDDs NoSQL ◼ Conclusion
23
24
12
Bases NoSQL
➢ Dans un contexte distribué, avec un très grand volume de données, sont apparues plusieurs solutions englobées sous le terme de ”NoSQL”.
➢ Ces bases de données ont certaines caractéristiques :
➢ pas de schéma pour les données ➢ données de structures complexes ou imbriquées ➢ mode d’utilisation : peu d’écritures, beaucoup de lectures ➢ on privilégie la disponibilité à la cohérence : A+P plutôt que C+P, → ces solutions NoSQL ne contiennent pas de support pour les transactions (ou rarement)
➢ Données distribuées : on a souvent la possibilité d’utiliser
des algorithmes MapReduce.
25
25
Qu'est-ce que le MapReduce ?
◼ MapReduce
un
est
patron
de développement informatique, popularisé (et non inventé) par Google, dans lequel sont effectués des calculs parallèles, données potentiellement très volumineuses.
d'architecture
distribués,
souvent
de
et
◼ Utilisé dans tous les systèmes à forte volumétrie
(NoSQL, BigData, ... ).
◼ Une tâche MapReduce s'effectue en deux temps : ◼ Map : Analyse d'un problème, découpé en sous
problèmes (peut être récursif).
◼ Reduce : Remontée des résultats au nœud parent
l'ayant sollicité.
26
26
13
Algorithme MapReduce
➢ Le programmeur définit 2 fonctions :
1. Map : transforme l’entrée en couples (clef, valeur) 2. Reduce : calcule 1 valeur à partir de la liste des valeurs associées à chaque clef l’algorithme d’exécution MapReduce s’occupe de l’aspect distribution : le programme est distribué sur les différents nœuds, on a donc une exécution en parallèle.
de
➢ L’environnement
➢ Un programme complexe est décomposé en une
succession de tâches Map et Reduce
27
27
28
Fonctions de base
1. map : (K, V) → list(K0, V0) function map(uri, doc) // uri : nom (id) du document, doc : le contenu du document for each distinct term in doc
output (term, count(term, doc)) 2. shuffle : list(K0, V0) → list(K0, list(V0)) regroupe les couples intermédiaires en fonction de leur clef. 3. reduce : (K0, list(V0)) → (K00, V00) function reduce(term, counts)
output (term, sum(counts))
28
14
Exemple
➢ Si on reprend le document du transparent 8, et on applique les fonctions map et reduce du transparent précédent pour compter le nombre de documents par terme.
29
Exemple
➢ On obtiendra :
30
29
30
15
Plan ◼Introduction ◼Contexte
◼Recherche sur le Web ◼Système distribué
◼Bases NoSQL ◼Types des BDDs NoSQL ◼Conclusion
31
31
Bases NoSQL
➢ Nous allons revoir les différents paradigmes
utilisés pour les bases NoSQL. 1. stockage de couples (clé, valeur) 2. bases orientées colonnes 3. bases de documents 4. bases de graphes
32
32
16
Types des BDDs NoSQL
Publicité
◼ Il s’agit de choisir la façon la mieux adaptée à la
représentation des informations stockés :
➢ « Clé-valeur / Key-value » : chaque objet est identifié par une clé unique constituant la seule manière de le requêter
➢ « Colonne / Column» : permet de disposer d'un très grand nombre de valeurs sur une même ligne, de stocker des relations « one-to-many», d'effectuer des requêtes par clé (adaptés au stockage de listes : messages, posts, commentaires, ...)
33
33
34
Types des BDDs NoSQL
➢ «Document» : gestion de collections de documents, composés chacun de champs et de valeurs associées, valeurs pouvant être requêtées (adaptées au stockage de profils utilisateur)
➢ «Graphe» : pour gérer des relations multiples entre les objets (adaptés aux données issues de réseaux sociaux, …)
34
17
1-Type orienté «Clé / Valeur»
➢ La base est une table de hachage distribuée. On
dispose en général de 4 opérations : 1. Create (key, value) : créer un nouveau couple (clef, valeur). La valeur est n’importe quel objet. 2. Read (key) : lire un objet connaissant sa clef 3. Update (key, value) : mettre à jour l’objet associé à une clef 4. Delete (key) : supprimer un objet connaissant sa clef
➢ On ne peut pas effectuer de requête sur le contenu
des objets stockés.
35
35
1-Type orienté «Clé / Valeur»
➢ Conçues pour sauvegarder les données sans définir de schéma, Toutes les données sont sous forme de clef/valeur
➢ La valeur peut être une chaîne de caractères, un objet
sérialisé, blob…
➢ La donnée est opaque au système : il n’est pas possible
d’y accéder sans passer par la clef
➢ L’absence de typage a un impact sur le requêtage : toute l’intelligence portée avant par les requêtes devra être portée par l’applicatif qui interroge la BD ➢ Fournir un accès rapide aux informations
36
36
18
1-Type orienté «Clé / Valeur»
➢Qui s'intéresse à des fonctionnalités aussi simples ? Quelques exemples : Redis (VMWare) : Vodafone, Trip Advisor, Nokia, Samsung, Docker Memcached (Danga) : LiveJournal, Wikipédia, Flickr, Wordpress Azure Cosmos DB (Microsoft) : Real Madrid, Orange tribes, MSN, LG, Schneider Electric SimpleDB (Amazon)
37
37
«Clé / Valeur» Forces et Faiblesses
➢ Forces : ➢ modèle de données simple ➢ bonne mise à l'échelle horizontale pour les lectures et écritures :
➢ évolutivité (scalable) ➢ Disponibilité ➢ pas de maintenances requises lors d'ajout/suppression de
colonnes
➢ Faiblesses : modèle de données TROP simple :
➢ pauvre pour les données complexes ➢ interrogation seulement sur clé ➢ déporte une grande partie de la complexité de l'application
sur la couche application elle-même
38
38
19
2-Type orienté «Colonne»
➢ Les données sont stockées par colonne, non par ligne ➢ On peut facilement ajouter des colonnes aux tables,
par contre l'insertion d'une ligne est plus coûteuse
➢ Quand les données d'une colonne se ressemblent, on
peut facilement compresser la colonne
➢ Modèle proche d'une table dans un SGBDR mais ici le
nombre de colonnes : ➢ est dynamique ➢ peut varier d'un enregistrement à un autre ce qui évite de retrouver des colonnes ayant des valeurs NULL
39
2-Type orienté «Colonne»
40
20
39
40
2-Type orienté «Colonne»
◼ Les deux principales différences entre les BD colonnes et
les
bases de données relationnelles:
◼ 1. Les colonnes sont dynamiques. Au sein d’une même table deux individus peuvent ne pas avoir le même nombre de colonnes car les valeurs nulles ne sont pas stockées (ce qui est le cas dans les SGBDR relationnels).
➢ Cette propriété permet de libérer de la place de stockage et d’améliorer les performances de traitement car la volumétrie de données à traiter est plus faible.
➢ Avec cette propriété, on a plus tendance également à ne créer qu’une seule table contenant toutes les données (et donc colonnes) dont on a besoin et non plus une multitude de tables comme c’est le cas dans les modèles relationnels. Cette absence de ‘jointure’ entre les tables améliore également les performances.
41
41
2-Type orienté «Colonne»
◼ 2. L’historisation des données se fait à la valeur et non pas à la ligne comme dans les SGBDR cela empêche le stockage d’informations en doublon et de ce fait allège considérablement la base de données et les temps de calcul.
◼ Une table orientée données sérialise toutes les valeurs d'une ligne ensemble, puis les valeurs de la ligne suivante, etc.
◼ Une base de données orientée colonne sérialise les valeurs d'une colonne ensemble, puis les valeurs de la colonne suivante, etc.
42
42
21
2-Type orienté «Colonne» Exemple d’historisation
➢ On constate que les valeurs ‘Black et George’ sont stockées deux fois côté SGBDR vs 1 fois côté Nosql orienté colonne.
2-Type orienté «Colonne»
43
44
43
44
22
2-Type orienté «Colonne»
➢ Quelques exemples en NoSQL :
➢ BigTable de Google et son implémentation open source (Apache) HBase. Google utilise BigTable pour l’indexation des pages web, Google Earth, Google analytics, …
➢ SimpleDB de Amazon ➢ Cassandra fondation Apache, projet né chez
Facebook.
45
45
«Colonne» Usage principal
◼ Dépôt de données avec besoins de requêtage très
simples
◼ Ces bases sont particulièrement bien adaptées nombreux stocker très
lorsque l’on évènements qui doivent être mis à jour régulièrement. Comme par exemple :
très
doit
de
◼ Le suivi de colis (de nombreux évènements dont le statut change : En préparation, en cours de livraison, livré..)
◼ La récupération et l’analyse de données en temps
réel issues de capteurs, IOT etc…..
46
46
23
«Colonne» Forces et Faiblesses
◼ Forces : ◼ Très adaptée pour effectuer des traitements sur des colonnes comme les agrégats (comptage, moyennes, co-occurences...).
◼ Naturellement indexé (colonnes) ◼ Bonne mise à l'échelle à l'horizontale ◼ Utilisation de MapReduce pour le scaling horizontal, on peut
voir les résultats de requêtes en temps réel
◼ Faiblesses : ◼ A éviter pour des données interconnectés (comme la distance
ou calculs de la trajectoire)
◼ A éviter pour les lectures de données complexes ◼ Exige de la maintenance -lors de l'ajout / suppression de
47
colonnes et leur regroupements
47
3-Type orienté «Document»
➢ Étendent
le paradigme clef/valeur, avec des «documents» plus complexes à la place des données simples, et une clef unique pour chacun d’eux
➢ Un «Document» est de type JSON ou XML ➢ Chaque Document est un objet, contient un ou plusieurs champs, et chaque champ contient une valeur typée (string, date, binary ou array)
➢ Permettent de stocker, extraire et gérer
les informations
orientées documents (données semi-structurées)
➢ Avantage: pouvoir récupérer, via une seule clef, un ensemble
d’informations structurées de manière hiérarchique ➢ Dans un SGDBR, cela impliquerait plusieurs jointures
48
48
24
3-Type orienté «Document»
49
49
3-Type orienté «Document»
➢ On peut stocker n’importe quel objet, via une sérialization ➢ les documents n’ont pas de schéma : grande flexibilité ➢ Quelques exemples :
Publicité
➢ MongoDB (MongoDB) : ADP, Adobe, Bosch, Cisco,
eBay, Electronic Arts, Expedia, Foursquare
➢ CouchBase (Apache, Hadoop) Comcast, Disney, PayPal, Ryanair
: AOL, AT&T,
➢ DynamoDB (Amazon) : BMW, Dropcam, Duolingo,
Supercell, Zynga
➢ Cassandra (Facebook -> Apache) : NY Times, eBay,
Sky, Pearson Education
50
50
25
«Document» Usage principal
❑Quelques exemples d'utilisation :
➢ gestion de contenu (bibliothèques numériques, collections de produits, dépôts de logiciels, collections multimédia, etc.), ➢ framework stockant des objets, ➢ collection d’événements complexes, ➢ gestion
d’utilisateurs
historiques
des
sur
réseaux sociaux,
➢ …
51
51
«Document» Forces et Faiblesses
◼ Forces : ◼ Modèle de données simple mais puissant
(expression de structures imbriquées)
◼ Bonne mise à l'échelle (surtout si le sharding
est pris en charge)
◼ Pas de maintenance de la BD requise pour
ajouter/supprimer des «colonnes»
◼ Forte expressivité de requêtage (requêtes
assez complexes sur des structures)
52
52
26
«Document» Forces et Faiblesses
◼Faiblesses : ◼Inadaptée pour les données
interconnectées
◼Modèle de requête limitée à des clés (et
indexes)
◼Peut alors être lent pour les grandes
requêtes (avec MapReduce)
53
53
4-Type orienté «Graphe»
➢ Basées sur les théories des graphes ➢ S’appuie sur les notions de nœuds, de relations et des
propriétés qui leur sont rattachées ➢ Conçues pour les données dont
les relations sont représentées comme graphes, et ayant des éléments interconnectés, avec un nombre indéterminé de relations entre elles
➢ Une base de données orientée graphe correspond à un système de stockage capable de fournir une adjacence entre éléments voisins : chaque voisin d'une entité est accessible grâce à un pointeur physique.
54
54
27
4-Type orienté «Graphe»
➢ Adapté à la manipulation d’objets complexes organisés en réseaux : cartographie, réseaux sociaux, web sémantique …
➢ Utilisent un moteur de stockage similaire à les
une base documentaire pour stocker nœuds
➢ Utilisent un mécanisme de description dʼarcs (relations entre les nœuds), arcs orientés et avec propriétés (nom, date, ...)
55
4-Type orienté «Graphe»
55
56
56
28
«Graphe» Usage principal
◼ Quelles bases de données gèrent de gros graphes ? ➢ Neo4j : eBay, Cisco, UBS, HP, TomTom, The National
Geographic Society
➢ OrientDB (Apache) : Comcast, Warner Music Group, Cisco,
Sky, United Nations, VErisign
➢ FlockDB (Twitter) : Twitter ◼ Quelques idées d'applications reposant sur des bases
orientées graphes :
➢ réseaux
sociaux
(recommandation, plus
court
chemin,
cluster...),
➢ réseaux SIG (routes, réseau électrique, fret...), ➢ web social (Linked Data) ➢ … 57
57
«Graphe» Forces et Faiblesses
◼ Forces : ◼ Modèle de données puissant ◼ Rapide pour les données liées, bien plus rapide que
SGBDR
◼ Modèles d'interrogation bien établis et performants ◼ Faiblesses : ◼ Fragmentation (sharding) : ◼ Même si elles peuvent évoluer assez bien
58
58
29
Plan
◼Introduction ◼Contexte
◼Recherche sur le Web ◼Système distribué
◼Bases NoSQL ◼Types des BDDs NoSQL ◼ Conclusion
59
59
NoSQL - Atouts
◼ Adapté au BigData (grand volume, données structurées, semi-structurées ou non-structurées, données stockées et gérées à plusieurs endroits)
◼ Disponibilité continue des données ◼ Utilisent une architecture hautement distribuée ◼ Indépendance de l’emplacement (Possibilité de consulter et modifier une BD sans savoir où est- ce que ces opérations ont réellement lieu)
◼ Modèles de données flexibles
60
60
30
NoSQL -Faiblesses
Choix de NoSQL, en opposition aux bases de données relationnelles, conduits par les contraintes du marché et les besoins techniques
◼ Il n’existe pas de langage de requêtage unifié (tel
que SQL)
◼ Requêtage moins expressif que SQL ◼ Moins mature que les SGDBR (dizaine d’années vs
40+)
◼ Moins d’outils que les SGDBR
SQL est de retour - NewSQL
61
62
61
62
31
SQL est de retour - NewSQL
◼ NewSQL désigne une catégorie de systèmes de gestion de base de données (SGBD) relationnelles modernes qui cherchent à fournir la même puissance évolutive que les systèmes traitement transactionnel en ligne (lecture-écriture), tout en maintenant les propriétés ACID d'un système de base de données traditionnel.
NoSQL
pour
le
63
64
Conclusion
Utilisez données pour le bon problème
le bon modèle de
Merci pour votre attention!
63
64
32