LG

Respect des transactions ACID : Atomicité (tout ou rien), Cohérence (respect des contraintes d'intégrité), Isolation (pas d'interférence si concurrence d'accès, personne ne peut voir les états intermédiare), Durabilité (log, réplication). En cas de base de données répartie utilisation de algorithme du commit à deux phases.

Propriétés CAP : Consistency (cohérence, tout le monde voit les mêmes valeurs), Availability (Disponibilité même en cas de problème matériel), Partition Tolerance (résistance au partitionnement, le système marche encore s'il est déconnecté de la réplication). Il n'est pas possible d'avoir un fonctionnement avec les 3 en même temps. ACID, c'est C et A.

Consistency Tuning In Cassandra – experience@imaginea Archive du 04/09/2013 le 23/10/2019

Guy Harrison - Yet Another Database Blog - Consistency models in Non relational Databases Archive du 13/06/2010 le 23/10/2019

• La plupart des BD NoSQL son AP (sans le C). Avantages : forme affaiblie de cohérence, simplification des transactions, garanties minimum sur le comportement.
• Pas forcément ACID (BASE : Basically Available, Soft-state et Eventually consistant) donc réduction des coûts et amélioration de la performance mais moins de cohérence.
• Intéressant en cas de très grand nombres de requêtes, disponibilité par répartition, extensibilité horizontale.
• Flexibilité des schémas de données (pas forcément obligé d'avoir les mêmes colonnes).
• Plus de jointure, beaucoup moins axé base relationnelle.
• Manipulation de données non normalisées, redondance possible. Pour réduire le risque d'incohérence, la modélisation consiste plutôt à embarquer les données et/ou les références (qui aidera aux jointures logicielles) aux autres données.

Cours CNAM, Archive

• Passage des écritures (cohérente) par un nœud maître puis propagation. La lecture (risque d'incohérence) se fait sur tous les nœuds.
• Passage des écritures sans un nœud maître puis propagation. La lecture se fait sur tous les nœuds. Risque d'incohérence dans la lecture et de conflit dans l'écriture (deux écritures différentes sur deux nœuds au même instant).

Traitement des incohérences, trié par degré de complexité :

Chaque valeur possède un temps. En cas de conflit, on prends la plus récente.

Problèmes :

• Délai entre l'envoi et la réception de l'information
• Mise à jour d'informations sur la base d'une ancienne version.
• Synchronisation de l'horloge ?

On ne travaille plus avec un compteur de temps mais par un incrément d'un compteur. Si la valeur est différente, la transaction est rejetée.

Problème : grand nombre de nœuds et nombreuses sollicitations

Copies multiples d'une même donnée puis synchronisation et détection de conflit.

Solution : pour chaque donnée, chaque nœud stocke le compteur de temps de tous les nœuds (enfin… la dernière valeur connue). On a donc pour chaque nœud, en plus de chaque donnée, un vecteur dont la taille est la même que le nombre de nœuds de la base de données.

Au début, le vecteur est initialisé à 0 pour le nœud en cours et inconnu pour les autres nœuds.

Si un nœud reçoit une demande de modification, il l'applique et incrémente son compteur de 1.

Quand il envoie la donnée à un autre nœud, il l'accompagne de son vecteur. Le nœud qui le reçoit à trois possibilités :

• tous les nombres du nouveau vecteur sont inférieurs ou égaux à ceux qu'il possède. Le nœud ignore la valeur car obsolète.
• tous les nombres du nouveau vecteur sont supérieurs ou égaux à ceux qu'il possède. Le nœud remplace la valeur et met à jour son horloge vectorielle avec le nouveau vecteur.
• certains nombres sont supérieurs, d'autres inférieurs : conflit ⇒ règle applicative.

Dans un système de base de données NoSQL, le volume de données est très nombreux et dépasse la capacité d'une machine d'où la nécessite de faire de la répartition. Comme la répartition est simple à faire, on utilise plutôt beaucoup de machine à bas coup plutôt que 2-3 très élevé. Il est donc courant de voir apparaître et disparaître des nœuds. Chaque nœud manifeste sa présence par un système de Watchdog.

Problème :

• partitionnement équilibré,
• trouver la partition,
• le tout dans une configuration dynamique

Données en mémoire pour éviter l'accès à la base de données. Stratégie généralement de type LRU “Dernier utilisé, premier éjecté”.

Les données sont réparties dans le cache de tous les serveurs. Pour trouver dans quel serveur est la donnée, on utilise ((hash de la clé) modulo le nombre de serveur). Si le nombre de serveur est important, toutes les données peuvent être en cache. Si certains serveurs ont plus de mémoire que d'autre, on peut considérer qu'ils comptent comme deux ou plus de serveurs, en fonction de leur mémoire interne.

Si des nœuds disparessent, le modulo va changer puis le système va se recalculer via le LRU.

Généralement, pour une sécurité très bonne, deux doublons, c'est déjà très bien.

• En asynchrone : un maître qui reçoit les écritures (possibilités de découper les requêtes en bloc) et se synchronise avec les autres nœuds en charge de répliquer. Tous les nœuds précédents reçoivent les lectures. Inconvénient : si le nœud maître tombe, la donnée est perdue. Avantage, réponse favorable plus rapide mais risque de faux.
• En synchrone : le maître reçoit l'écriture et ne rend la main qu'une fois toutes les réplications faites. Inconvénient : plus lent. Avantage : préservation des données.

Répartir les données qui vont être accessibles en même temps dans une même partition. Mapping statique ou dynamique entre les partitions et les nœuds. Ici, on parle du stockage persistant des données en opposition avec le cache.

Encore une fois, la correspondance objet-partition par hash cohérent. C'est une nécessité pour éviter qu'en cas de modification du nombre de nœuds (Redundant Array of Inexpensive Servers (RAIS)), le stockage persistant des données change de nœuds. Le principe consiste à recalculer le hash en fonction de la modification.

Inconvénient : jointure possible uniquement sur les données d'une même partition.

Méthode :

• Remplissage : on place via un hash la position des nœuds (base de données) et des blocs (données) sur un cercle. On parcourt le cercle toujours dans le même sens et on stocke chaque donnée dans le prochain nœud trouvé.
• Si un nœud disparaît, on stocke tous les blocs orphelin dans le nœud suivant. En l'état, cela consiste à surcharger le nœud suivant.
• Division d'un nœud de façon “répartie” autour du cercle. Création de nœuds virtuels en découpant le nœud en N parties. Dans ce cas, il n'y a plus que le nombre de données contenu dans le nœud virtuel à déplacer (1/N)

• Lien clé/valeur.
• CRUD uniquement de clés. Requête uniquement SELECT … WHERE …. Éléments atomiques ⇒ intégrité forcément.
• Structure des objets totalement libre.
• Représentation JSON, XML ou autre.
• Exemple : Redis, Riak, Voldemort.

• Sur la base clé/valeur (document).
• Le document est structuré et accessible lors de l'accès mais sans cohérence entre les documents.
• Possibilité de faire des requêtes sur les champs des documents mais pas de jointure naturelle ⇒ pas d'intégrité référentielle.
• Représentation JSON, XML ou autre.
• Exemple : MongoDB, CouchDB, Terrastore

• Ressemble à SQL :
  • une base est composée de tables,
  • une table est composée de lignes (documents) avec une clé et les données,
  • les données sont des colonnes qui contiennent une ou plusieurs valeurs (ex : liste de pair <date, valeur>).
  • Super colonne : colonne contenant plusieurs colonnes.
  • Famille de colonne : regroupement de (super)colonne qui définit un type.
• Les attributs ne sont plus atomiques.
• Les attributs ne sont pas fixes.
• Une même colonne peut être dans plusieurs objets.
• Cassandra, Amazon SimpleDb, Google BigTable, HBase.

• Architecture totalement différente des autres bases NoSQL.
• Les entités de données sont des nœuds. Chaque nœud est relié à d'autres nœuds par des arcs orientés. Les arcs possèdent également leurs propres données.
• Exemple : Neo4j, OrientDB.

Logiciel libre Hadoop en Java.

Implémentation de deux classes :

• Map : ensemble de clé/valeur d'un document par exemple. Fait un prétraitement parallèle.
• Reduce : traite la map, non parallélisable

Et au final Hadoop se débrouille à propager les deux classes aux différents nœuds. Faire migrer les traitements vers les données. Réduit les flux, très grand nombre de serveurs.

Système de fichier HDFS : Hadoop Distributed File System.

• Orientée documents
• Interface REST (CRUD) et API, pas de schéma fixe, format JSON, versionnement (historique jusqu'à une commande de maintenance), requêtes via des vues (similaire à SQL) en lecture seule.
• Les structures internes des documents sont connues de la base.
• Chaque document à un identifiant de version.
• Chaque serveur dispose de l'ensemble des données ⇒ contrainte au plus petit serveur. Solution avec BigCouch : partitionnement des données et leur répartition sur différents serveurs.

• Orientée documents
• Interface REST (CRUD) et API, pas de schéma fixe, format JSON (REST, BSON pour API).
• Les structures internes des documents inconnues de la base.
• Chaque document à un identifiant de version.
• Mode centralisé avec serveur unique ou réplication asynchrone sur nœuds esclaves.
• Mode décentralisé avec un Replica Set composé de N serveurs physiques (mongod) avec des niveaux de priorité. L'un est le nœud primaire qui gère les écritures et qui réplique de façon asynchrone.
• Mode partitionnement (sharding) : Un shard regroupe des Replica Set. Ils sont gérés par des serveurs Mongo. Intérêt : routage vers le bon Replica Set et allègement de la charge des Mongod.

• Orientée colonnes.
• Interface API, requêtes simple similaire à SQL.
• Écriture : attente d'un quorum (une quantité) de nœuds validant l'écriture et la réplication. Nombre défini dans la configuration ou la requête (ZERO (pas de vérification), ANY (une écriture), ONE (une écriture + log), QUORUM (la majorité + 1), ALL (tous les nœuds)). Pareil pour la lecture, si plusieurs versions, on prend la plus récente. Possibilité donc de faire travailler en système CA et non plus AP (BASE).
• Architecture distribué (Sharding)