Introduction aux bases de données NoSQL

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 dun 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. Cest un sc nario de type Workflow,

impl menter avec des web

que lon 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 quun

grand volume de donn es Donn es

distribu es.

On

MapReduce qui utilise cette approche.

lalgorithme

cours

verra

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 dapr 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 nSuds voient

1. Consistency (coh rence) :

exactement les m mes donn es en m me temps

: L chec dun nSud

2. Availability (disponibilit )

nemp che pas les survivants de continuer fonctionner

3. Partition tolerance (r sistance au partitionnement) :

Le syst me continue fonctionner malgr la perte dun

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 nSud N1 et dessayer de la lire partir du

nSud 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 cest

chances dun chec de

un syst me distribu ,

les

transmission sont assez importantes, ce qui provoquera une

attente infinie de N2. Do 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 . Do

violation de la Tol rance au partitionnement.

21

21

Le th or me CAP

pendant lenvoi du message M, d ` d

en g n ral,

la r sistance au partitionnement nest 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. Cest 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

nint 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 dutilisation : 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 dutiliser

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 nSud parent

l'ayant sollicit .

26

26

13

Algorithme MapReduce

Le programmeur d finit 2 fonctions :

1. Map : transforme lentr e en couples (clef, valeur)

2. Reduce : calcule 1 valeur partir de la liste des

valeurs associ es chaque clef

lalgorithme

dex cution

MapReduce soccupe de laspect distribution :

le

programme est distribu sur les diff rents nSuds, on

a donc une ex cution en parall le.

de

Lenvironnement

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

Il sagit 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 nimporte quel objet.

2. Read (key) : lire un objet connaissant sa clef

3. Update (key, value) : mettre jour lobjet 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 nest pas possible

dy acc der sans passer par la clef

Labsence de typage a un impact sur le requ tage : toute

lintelligence port e avant par les requ tes devra tre

port e par lapplicatif 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 dune 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

dam 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

quune seule table contenant

toutes les donn es (et donc

colonnes) dont on a besoin et non plus une multitude de tables

comme cest 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. Lhistorisation des donn es se fait la valeur

et non pas la ligne comme dans les SGBDR cela

emp che le stockage dinformations 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 dhistorisation

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 lindexation 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 lon

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 lanalyse 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 deux

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

dinformations 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 nimporte quel objet, via une s rialization

les documents nont pas de sch ma : grande flexibilit

Quelques exemples :

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

QQuelques 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

dutilisateurs

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

Sappuie sur les notions de nSuds, 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 dobjets 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

nSuds

Utilisent un m canisme de description d arcs

(relations entre les nSuds), 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 lemplacement (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 nexiste pas de langage de requ tage unifi (tel

que SQL)

Requ tage moins expressif que SQL

Moins mature que les SGDBR (dizaine dann es vs

40+)

Moins doutils 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