David Bigot & Julien Vehent - 2010

Ce cours couvre les principes généraux des bases de données depuis les fondamentaux jusqu'aux technologies plus récentes de bases de type key/value.

Une base de données (DBMS: DataBase Management System, ajouter un “R” au début pour Relational) est un mécanisme de classification de l'information, facilitant la consultation, l'ajout, la mise à jour et la suppression. Il existe de nombreux types de bases de données, et ce cours va couvrir en profondeur les modèles relationnels et key/value (clé/valeur).

Le DBMS de référence est Postgresql. D'autres DBMS comme Oracle, Mysql ou MongoDB seront également abordés dans certains chapitres.

La nécessité de classer l'information apparait avec les premiers écrits. Parmi les plus anciennes bases de données, on note la grande Bibliothèque d'Alexandrie, qui disparaitra sous les flammes. On a là à la fois la première grande base de données, déployant des trésors de technologies (index, tri, …), et la première manifestation du risque sur les données: la perte de disponibilité.

Au fil des siècles, la classification de l'information, son organisation et son stockage, évolue lentement. Le travail de réplication est essentiellement réalisé par les moines, donc lent et cher. Cela n'empêche toutefois pas la constitution d'immenses bibliothèques et, avec elles, le développement des techniques de classification, consultation et mise à jour.

L'unité de plus petite taille étant le livre, il est impossible de découper l'information pour gagner en taille de stockage. Un livre contient un auteur, une date de publication, un éditeur et un contenu (recopiant parfois partiellement ou complètement le contenu d'ouvrages tiers).

Il faudra attendre les annèes 1960 pour qu'un modèle permettant de découper l'information en unité plus petite soit mis en place. On attribue généralement la définition théorique du modèle relationnel au Dr. Edgar Codd, travaillant à IBM Research, dans un article publié en 1969. L'idée de Codd est de découper une information en unités indépendantes, pouvant être utilisées plusieurs fois, puis de créer des liens entre ces unités pour reconstituer l'information initiale.

Ainsi, Sir Arthur Conan Doyle, publié chez McClure, Phillips and Co, et ayant écrit The Sign of Four en 1890, The Hound of the Baskervilles en 1902, et His Last Bow en 1917 sera stocké sous la forme suivante:

• Sir Arthur Conan Doyle est stocké une seule fois
• McClure, Phillips and Co est stocké une seule fois
• Chacun des trois livres, avec sa date de publication, est stocké une seule fois
• Chacun des trois livres contient un lien vers son auteur et son éditeur

On économise ainsi le stockage inutile de l'auteur et de l'éditeur pour chaque livre.

Ce modèle relationnel a grandi et évolué depuis les années 1970, mais le principe initial reste le même. Les évolutions ont suivies les besoins en termes de performances et de sécurité des architectures informatiques, et le modèle fonctionne si bien que, rapidement, TOUT est stocké en base de données (et parfois même ce qui ne devrait pas l'être, comme des fichiers de configuration…).

Il y a de nombreux types d'utilisateurs de base de données. Le secteur tertiare, gros consommateurs de données fortement stables (bougeant peu), utilise souvent des logiciels pachidermiques mais dont la solidité est prouvée. A l'inverse, nombre de startups ont de gros problèmes a utiliser le modèle relationnel, trop contraignant, et préfère plus de flexibilité. Dans ce derniers cas, les bases de données objets (ou NoSQL mais le terme est inapproprié) stockant des associations clé/valeurs sont pertinentes.

Cette omniprésence pose évidemment des contraintes, en particuliers concernant la sécurité des données. Et c'est l'objet de ce cours que de présenter la technologie et les méthodes permettant d'assurer sa fiabilité.

Tout tourne autour de la donnée, c'est la seule valeur d'un réseau informatique. Bien avant que les états ne reconnaissent sa valeur stratégiques, les grands groupes financiers avaient déjà identifié le risque de perte de l'information. Traiter la sécurité des supports de stockages de l'information, et donc en particulier des bases de données, n'est pas une option. C'est une obligation réglementaire dans la plupart des cas. Tout groupe financier, ou groupe industriel coté en Bourse, doit être doté de mécanisme protégeant ses informations de leurs disparition éventuelle, mais également du vol ou de la fuite.

Aujourd'hui, en 2010, on peut dire que la grande majorité des entreprises du CAC40 ou du Nasdaq sait traiter ces questions. Pour exemple, lors d'un test de plan de continuité dans une grande entreprise internationale, le comité de crise est placé face a une inondation majeure. Les voies de communication vers les locaux et les datacenters sont inaccessibles. Sans hésiter, le chef d'entreprise prend position sur les actions prioritaires: “Laissez tomber la communication, l'organisation du site de crise ou n'importe quoi d'autre. Ce que je veux, en premier, et rapidement, c'est que les serveurs soient sécurisés et les sauvegardes dans un lieu sur ! Après, on avisera.” En clair, interrompre l'activité pendant une ou deux semaines n'est pas critique (le contexte de cet entreprise le permettait toutefois). Mais perdre des données est inacceptable: c'est la survie de l'entreprise qui est en jeu.

Le développement des réseaux passe par le découpage des architectures. Dès la fin des années 70, le modèle MVC voit le jour. MVC, Model-View-Controller, présente une séparation dans laquelle:

• “Model” gère l'information. C'est la base de donnée.
• “View” présente l'information provenant du “Model”
• “Controller” gère les actions entre “View” et “Model”

La représentation n-tiers n'apparait que plus tard, au début des années 90. A la différence de MVC, c'est un modèle linéaire client-server dans lequel le client n'interagit jamais avec la base de données directement. Les requêtes passent systématiquement par un “Middleware” (un logiciel du milieu…).

ntiers.dia

Le modèle n-tiers est aujourd'hui le plus courant. Son fonctionnement en couche permet d'être de plus en plus restrictif quand on s'approche de la base de données. Le cas le plus classique est celui de l'application web, avec:

1. couche extérieure: reverse proxy et cache de fichier statiques (images, fichiers css, etc…)
2. couche centrale: l'application web (Java, PHP, C, …) et les bases de données applicatives (droits des utilisateurs, etc…)
3. couche intérieure: les bases de données métiers (DB2, Oracle, …)

On voit aussi se type d'architecture se développer en oignon, avec des quartiers dédiés a des domaines métiers, qui peuvent être vus comme des zones de confiances. C'est du partitionnement d'architecture.

oignon.dia

L'architecture d'une base de données se compose de trois niveaux: externe, conceptuel et interne.

1. Le niveau externe représente la donnée sous sa forme consultable. C'est la représentation vue par l'utilisateur. (ex: un tableau des livraisons par fournisseur).
2. Le niveau interne est la structure physique de la base de données. Ce sont les fichiers binaires manipulés par les moteurs de bases de données (ex: les fichiers TABLESPACE d'Oracle).
3. Le niveau conceptuel fait le lien entre les deux. C'est la représentation logique qui détermine le découpage des données, typiquement en tables contenant des colonnes. Ce niveau est également en charge de conserver la cohérence des données dans la base.

La séparation nette de ces trois niveaux est un principe central des bases de données relationnelles.

employees.dia
Base de données “employees”

L'accès au DBMS par le réseau se fait généralement via un connecteur Open DataBase Connectivity (ODBC).

<note important> Avant d'aller plus loin, il est important de préciser que les exemples Postgresql qui suivront ont été réalisés sur les versions Linux 8.4 et 9.0 du logiciel, sur la base de données employees et sous les rôles empadm et postgres. La connection au DBMS se fait via la commande :

$ psql -U empadm -W -h localhost -d employees

</note>

Le traitement d'une opération par le DBMS est appelé “Transaction”. Le traitement des transactions est un aspect essentiel des bases de données et de leur sécurité. Les DBMS sont des logiciels pouvant traiter plusieurs milliers (voir millions) de requêtes par secondes. Dans un tel contexte, la probabilité pour que deux requêtes modifient les mêmes valeurs est importante.

Prenons le cas suivant:

• Bob est le manager d'Alejandro Brender (employé n. 10039) et de Sajjad Mitsuhashi (employé n.33570). Il a décidé de leur donner une augmentation et de leur donner le même salaire que leur collègue Yechiam Marciano (employé n. 100181).
• John est le manager de Yechiam Marciano et, ce dernier ayant quitté l'entreprise, décide de le supprimer de la base des salaires.

La situation initiale des trois employés est la suivante:

employees=> SELECT employees.emp_no, employees.birth_date, employees.first_name, 
            employees.last_name, departments.dept_no,departments.dept_name,salary
            FROM employees, dept_emp, departments, salaries
            WHERE employees.emp_no = dept_emp.emp_no
            AND dept_emp.dept_no = departments.dept_no
            AND employees.emp_no = salaries.emp_no
            AND salaries.to_date > CURRENT_DATE
            AND (employees.emp_no = 10039 OR employees.emp_no = 33570 OR employees.emp_no = 100181);
 
 emp_no | birth_date | first_name | last_name  | dept_no |    dept_name    | salary 
--------+------------+------------+------------+---------+-----------------+--------
  10039 | 1959-10-01 | Alejandro  | Brender    | d003    | Human Resources |  63918
  33570 | 1962-01-12 | Sajjad     | Mitsuhashi | d003    | Human Resources |  62168
 100181 | 1957-06-17 | Yechiam    | Marciano   | d003    | Human Resources |  66000

Evidemment, ces opérations vont se croiser. Bob va exécuter sa première mise à jour:

employees=> UPDATE salaries SET salary = (SELECT salary FROM salaries WHERE emp_no = 100181 AND to_date > CURRENT_DATE) WHERE emp_no = 10039;

Et John, au même moment, exécute sa suppression:

employees=> DELETE FROM salaries WHERE emp_no = 100181;

La requête de John passe entre les deux requêtes de Bob, et la seconde requête de Bob se termine avec une erreur:

employees=> UPDATE salaries SET salary = (SELECT salary FROM salaries WHERE emp_no = 100181 AND to_date > CURRENT_DATE) WHERE emp_no = 33570;
ERROR:  NULL VALUE IN COLUMN "salary" violates not-NULL CONSTRAINT

Au final, la base est dans l'état suivant:

 emp_no | birth_date | first_name | last_name  | dept_no |    dept_name    | salary 
--------+------------+------------+------------+---------+-----------------+--------
  10039 | 1959-10-01 | Alejandro  | Brender    | d003    | Human Resources |  66000
  33570 | 1962-01-12 | Sajjad     | Mitsuhashi | d003    | Human Resources |  62385
(2 ROWS)

Le premier employé a été augmenté, mais pas le second. Et l'entrée concernant Yechiam Marciano a disparut.

Evidemment, cela n'est pas acceptable. C'est pour cela que la notion de Transaction est apparut dans les DBMS pour pallier à ce problème. L'aspect central est qu'une transaction représente une série d'opération qui doivent être réalisées ensemble, ou pas réalisé du tout. Afin de préserver l'intégrité de l'information, les transactions doivent normalement suivrent la règle ACID:

1. [A]tomicity : Dans une transaction, soit TOUS les changements sont pris en compte, soit AUCUN changement n'est pris en compte. L'atomicité définit qu'une transaction doit être traitée comme un ensemble indivisible.
2. [C]onsistency: Une transaction ne peut pas enfreindre les règles de cohérence de la base (ex. violer l'intégrité référentielle).
3. [I]solation: Deux transactions simultannées ne peuvent pas s'influencer entre elles. Les résultats intermédiaires d'une transaction A ne doivent pas être connus d'une transaction B se déroulant en même temps.
4. [D]urability: Les transactions terminées et validées (committées) ne peuvent pas être annulées. Le résultat d'une transaction doit être sécurisé par le DBMS.

Le modèle ACID est la base de la définition des RDBMS: la fiabilité d'une base de données passe toujours par le respect de la règle ACID. C'est donc un point important à valider lors du choix d'une solution (relationnelle ou non).

Le problème précédant peut être résolu en incluant les deux requêtes UPDATE de Bob au sein d'une transaction. On l'écrira de la manière suivante.

BEGIN;
UPDATE salaries SET salary = (SELECT salary FROM salaries WHERE emp_no = 100181 AND to_date > CURRENT_DATE) WHERE emp_no = 10039;
UPDATE salaries SET salary = (SELECT salary FROM salaries WHERE emp_no = 100181 AND to_date > CURRENT_DATE) WHERE emp_no = 33570;
COMMIT;

John, au même moment, lance sa requête de suppression qui est exécutée entre les deux updates de Bob.

employees=> DELETE FROM salaries WHERE emp_no = 100181;
DELETE 15

Bob est toujours dans sa transaction. Il lance sa deuxième requête update et voit l'erreur. A ce stade, la première requête a été exécutée mais son résultat est encore en attente d'écriture. Ainsi, la base est toujours dans l'état initial suivant:

emp_no | birth_date | first_name | last_name  | dept_no |    dept_name    | salary 
--------+------------+------------+------------+---------+-----------------+--------
  10039 | 1959-10-01 | Alejandro  | Brender    | d003    | Human Resources |  63918
  33570 | 1962-01-12 | Sajjad     | Mitsuhashi | d003    | Human Resources |  62168
(2 ROWS)

Aucun des deux employés n'a été augmenté. Bob, ne pouvant terminer sa transaction, peux annuler son premier changement via la commande ROLLBACK. La requête de mise à jour concernant Alejandro Brender, qui avait pourtant été exécutée, est ainsi annulée et la base reste dans son étant initial.

La séquence complète vue par Bob est la suivante:

employees=> BEGIN;
BEGIN
 
employees=> UPDATE salaries SET salary = (SELECT salary FROM salaries WHERE emp_no = 100181 AND to_date > CURRENT_DATE) WHERE emp_no = 10039;
UPDATE 15
 
employees=> UPDATE salaries SET salary = (SELECT salary FROM salaries WHERE emp_no = 100181 AND to_date > CURRENT_DATE) WHERE emp_no = 33570;
ERROR:  NULL VALUE IN COLUMN "salary" violates not-NULL CONSTRAINT
 
employees=> ROLLBACK;
ROLLBACK

A noter que Bob pourrait également accepter de ne faire qu'un update sur les deux et réaliser son COMMIT malgré l'erreur sur la deuxième requête. Techniquement, rien ne l'en empêche, mais dans ce dernier cas, c'est l'utilisateur qui accepte de réduire l'atomicité de ses opérations, pas le DBMS.

L'isolation telle que définit dans le « I » de ACID implique que les résultats intermédiaires d'une transaction soient invisibles aux sessions voisines tant que la transaction n'est pas validée (COMMIT). Ainsi, lorsque Bob réalise ses deux requêtes update dans une transaction, John ne voit pas les résultats mis à jour tant que Bob n'a pas tapé « COMMIT; ».

Lorsque Bob démarre une transaction, et modifie les salaires des employés 10039 et 33570, il positionne un LOCK sur ces deux valeurs. Tant que Bob n'a pas terminé sa transaction par un COMMIT ou un ROLLBACK, aucune autre transaction ne peux modifier ces valeurs.

Des mécanismes plus complexes existent dans les RDBMS afin de positionner des points de sauvegardes pour les transactions très longues. Il est ainsi possible de réaliser un ROLLBACK vers une étape intermédiaire et de ne passer en COMMIT que le début de la requête.

Les fichiers binaires manipulés par une base de données peuvent être organisés de multiples manières. Une méthode courante est d'organiser les données en B-Tree (Binary Balanced Tree) et d'écrire directement ce B-Tree sur disque dans un fichier binaire. Il est également possible de stocker les résultats d'une requête directement sur le disque, dans un fichier particulier. C'est la méthode des vues matérialisées.

Les RDBMS comme Oracle et Postgresql permettent de manipuler des fichiers de stockages appelés TABLESPACE. Il s'agit en fait de fichiers binaires eux-mêmes stockés sur disque et qui vont contenir les tables, index et procédures de la base de données. L’intérêt des TABLESPACE est qu'ils fournissent une méthode fiable pour ventiler une base de données sur plusieurs disques, ou entre plusieurs environnements de stockages. On peut ainsi imaginer avoir des index très rapides stockés sur un disque a haute vitesse, type SSD, puis le corps de la base de données sur un SAN, et enfin les tables contenant des données peu utilisées sur un stockage moins couteux.

On crée un tablespace dans un répertoire vide sur une partition au choix.

postgres@server:~$ mkdir /tmp/pgtmpdata
 
postgres@server:~$ psql
psql (8.4.5)
Type "help" for help.
 
postgres=# create tablespace tmpdata location '/tmp/pgtmpdata';
CREATE TABLESPACE

Ce tablespace peut ensuite être utilisé pour stocker des données de la base, comme un index de colonne.

employees=# CREATE INDEX employees_birth_date_index ON employees(birth_date) tablespace tmpdata;
CREATE INDEX

Les tablespaces existant sont disponibles dans la table système pg_tablespace:

postgres=> SELECT spcname FROM pg_tablespace;
  spcname   
------------
 pg_default
 pg_global
 tmpdata
(3 ROWS)

On contrôle la taille d'un tablespace toujours dans ces tables système:

postgres=# SELECT pg_size_pretty(pg_tablespace_size('tmpdata'));
 pg_size_pretty 
----------------
 6604 kB
(1 ROW)

Le stockage par défaut du DBMS Postgresql est également un tablespace portant le nom pg_default. On peut connaitre sa taille avec la même requête que précedemment.

Le principe d'une base de données relationnelle est de contenir des tables contenant des colonnes. Chaque colonne d'une table peut avoir une relation avec une colonne d'une autre table. Dans l'exemple de la base employees, la colonne salaries.emp_no a une relation avec la colonne employees.emp_no: les deux colonnes contiennent la même information, salaries.emp_no est une clé étrangère prenant en référence employees.emp_no. Charge ensuite au RDBMS de maintenir l'intégrité des différentes tables, en particulier, si l'employé est supprimé de la table employees, il doit être également supprimé dans la table salaries. C'est l'intégrité référentielle. Dans l'exemple ci-dessous, on vient que le RDBMS refuse la suppression de l'employé numéro 10039 car cela violerait cette intégrité référentielle :

employees=> DELETE FROM employees WHERE emp_no = 10039;
 
ERROR:  UPDATE OR DELETE ON TABLE "employees" violates FOREIGN KEY CONSTRAINT "dept_emp_emp_no_fkey" ON TABLE "dept_emp"
 
DETAIL:  KEY (emp_no)=(10039) IS still referenced FROM TABLE "dept_emp".

Si l'information est organisée en colonne, lors de la consultation ce sont des lignes que nous allons visualiser. On assemble une ligne d'une table (ou des colonnes particulières d'une ligne) avec une ligne d'une autre table en utilisant des critères contenus dans une requête (ex: SQL). Chaque ligne retournée par une requête correspond à la représentation externe de l'information.

On verra plus tard que dans un autre type de bases de données, les ODBMS (Object DataBase Management Systems), ce ne sont pas des lignes mais des collections d'objets qui sont retournés.

L'un des critères déterminants pour un DBMS est la performance. Sur de large volume de données, le temps (CPU et I/O) prit pour compléter une requête est critique, et les étapes permettant la complétion de la requête sont appelée Plan d'exécution.

Comprendre les étapes composants le plan d'exécution d'une requête est déterminant pour optimiser et les requêtes et la structure de la base de données. On l'utilisera également pour observer l'utilisation des index.

PostgreSQL et Oracle intégrent des fonctions avancées de plan d'exécution. Lors de la saisie d'une requête, le DBMS tente de choisir le meilleur plan en fonction de la structure de la requête et des propriétés des données.

Un plan est composé de noeuds. La commande EXPLAIN permet de visualiser ces noeuds. Sur une requête simple, voici ce que retourne EXPLAIN:

employees=> EXPLAIN SELECT * FROM employees;
 
                            QUERY PLAN
------------------------------------------------------------------
 Seq Scan ON employees  (cost=0.00..5170.24 ROWS=300024 width=29)
(1 ROW)

Comme la requête consiste à retourner toutes les entrées de la table de manière séquentielle, la seule action (le seul noeud) retournée par le plan d'exécution est un Seq Scan (parcours séquentiel). Les métriques donnent les informations suivantes, de gauche à droite:

1. cost=0.00 : coût estimé du lancement (temps passé avant que l'affichage de la sortie ne commence, c'est-à-dire pour faire le tri dans un noeud de tri) ;
2. ..5170.24: coût total estimé (si toutes les lignes doivent être récupérées, ce qui pourrait ne pas être le cas : par exemple une requête avec une clause LIMIT ne paiera pas le coût total du noeud d'entrée du noeud du plan Limit) ;
3. rows=300014: nombre de lignes estimé en sortie par ce noeud de plan (encore une fois, seulement si exécuté jusqu'au bout) ;
4. width=29: largeur moyenne estimée (en octets) des lignes en sortie par ce noeud de plan;

L'information coût cost est calculée en unités propres à postgresql, dont la base est seq_page_cost. seq_page_cost a pour valeur par défaut 1, et représente le coût de récupération d'une page contenant des données. (Pour rappel, une page mémoire a une taille par défaut de 4Ko sous Linux, voir 'getconf PAGESIZE').

On peut réaliser le calcul de coût total estimé manuellement, de la façon suivante:

• Nombre de lignes : NbLignes= 300024
• Longueur moyenne d'une ligne: AvgLength = 29
• Taille d'une page en octets: PageSize = 4096

Donc

• Nombre de pages pour contenir la table : TotPages = (NbLignes x AvgLength) / PageSize = (300024 x 29) / 4096 ~= 2125 pages.

Le coût estimé est calculé via la formule:

• coût total: cost = (TotPages x seq_page_cost) + (NgLignes x cpu_tuple_cost) = (2125 x 1) + (300024 x 0.01) = 5125.24

La valeur obtenu par le calcul manuel diffère quelque peu de celle retournée par Postgresql car nous avons utilisé une longueur moyenne de lignes à la place d'une valeur déterministe.

cpu_tuple_cost est une autre constante interne de postgresql qui définit le temps CPU de traitement d'une ligne, initialisé à 0.01.

<note tip>Lorsqu'une requête est composée de plusieurs noeuds, le noeuds de niveau supérieur affiche le coût total de tous les noeuds fils. Ainsi, pour connaître le coût d'un noeud en particulier, on doit y soustraire le coût du noeud inférieur.</note>

Sur une requête réalisant un JOIN entre deux tables, on voit clairement l'impact des différents noeuds:

employees=> SELECT title, MIN(salary) FROM salaries INNER JOIN titles ON salaries.emp_no = titles.emp_no GROUP BY title;
       title        |  MIN
--------------------+-------
 Technique Leader   | 38623
 Senior Engineer    | 38786
 Staff              | 38735
 Assistant Engineer | 38850
 Senior Staff       | 38735
 Engineer           | 38849
 Manager            | 40000
(7 ROWS)
 
employees=> EXPLAIN SELECT title, MIN(salary) FROM salaries INNER JOIN titles ON salaries.emp_no = titles.emp_no GROUP BY title;
 
                                     QUERY PLAN
------------------------------------------------------------------------------------
 HashAggregate  (cost=395402.61..395402.70 ROWS=7 width=15)
   ->  Hash JOIN  (cost=90475.06..371726.93 ROWS=4735136 width=15)
         Hash Cond: (titles.emp_no = salaries.emp_no)
         ->  Seq Scan ON titles  (cost=0.00..7335.08 ROWS=443308 width=15)
         ->  Hash  (cost=43814.47..43814.47 ROWS=2844047 width=8)
               ->  Seq Scan ON salaries  (cost=0.00..43814.47 ROWS=2844047 width=8)
(6 ROWS)

Ce que cette requête nous montre, c'est un noeud Hash Join qui a un coût total de 371726, alors que les noeuds inférieur ont des coûts respectifs de 7335 (Seq Scan sur titles pour récupérer les différents title) et 43814 (pour parcourir les salaires). Donc, l'opération INNER JOIN coûte 320577 a elle seule, soit environ 80% du temps de réalisation de la requête.

On peut également ajouter la commande ANALYZE avec EXPLAIN pour avoir une comparaison entre l'estimation faite par EXPLAIN et le temps d'exécution constaté par ANALYZE. En effet, ANALYZE exécute réellement la requête et affiche les temps d'exécution constatés pour chaque noeuds du plan d'exécution.

Sur la requête précédente, cela donne le résultat suivant:

employees=> EXPLAIN analyze SELECT title, MIN(salary) FROM salaries INNER JOIN titles ON salaries.emp_no = titles.emp_no GROUP BY title;
                                                               QUERY PLAN
 
----------------------------------------------------------------------------------------------------------------------------------
------
 HashAggregate  (cost=395402.61..395402.70 ROWS=7 width=15) (actual TIME=93582.739..93582.769 ROWS=7 loops=1)
   ->  Hash JOIN  (cost=90475.06..371726.93 ROWS=4735136 width=15) (actual TIME=32968.274..66783.143 ROWS=4638507 loops=1)
         Hash Cond: (titles.emp_no = salaries.emp_no)
         ->  Seq Scan ON titles  (cost=0.00..7335.08 ROWS=443308 width=15) (actual TIME=0.000..2682.386 ROWS=443308 loops=1)
         ->  Hash  (cost=43814.47..43814.47 ROWS=2844047 width=8) (actual TIME=32961.543..32961.543 ROWS=2844047 loops=1)
               Buckets: 4096  Batches: 128  Memory Usage: 650kB
               ->  Seq Scan ON salaries  (cost=0.00..43814.47 ROWS=2844047 width=8) (actual TIME=0.000..15892.273 ROWS=2844047 loo
ps=1)
 Total runtime: 93586.241 ms
(8 ROWS)
 
TIME: 93589.616 ms

On voit que la requête a pris un temps total de 93 secondes, donc 66 passées dans le INNER JOIN.

Un index est une référence des données contenues dans la base qui permet de trouver une information plus rapidement (comme l'index à la fin d'un livre). Dans un base de données relationnelles, des index placés sur les bonnes colonnes permettent d'accélérer la résolution d'une requête. Par exemple, si un grand nombre de requêtes consistent à rechercher un produit par son numéro id, alors on placera un index sur cette colonne. Selon le type d'index, les temps de recherches varieront mais seront de toute façon plus rapide qu'un parcours linéaire de la colonne.

Il existe plusieurs types d'index, le plus courant étant l'arbre binaire balancé, ou B-Tree.

Un B-Tree est une structure de donnée en forme d'arbre dans lequel chaque noeud N pointe vers deux (ou plus) autres branches contenant des valeurs inférieures et supérieures aux valeurs contenues dans N.

L'intéret d'un B-Tree est de permettre la recherche, l'insertion et la suppression de valeur à vitesse O(log n) (à comparer a une recherche linéaire qui a une vitesse de O(n)).

Dans la base de données employees, si un grand nombre de requêtes consistent à rechercher un salaire par sa valeur numérique dans salaries.salary, de la façon suivante:

employees=> SELECT COUNT(salaries.salary) FROM salaries WHERE salary = '45001';
 COUNT
-------
    65
(1 ROW)

Alors, sans index, le DBMS doit parcourir la colonne salary de façon linéaire jusqu'à trouver toutes les valeurs '45001'. On peut créer un index B-Tree sur cette colonne pour accélérer la recherche. Dans Postgresql, c'est fait de la manière suivante:

create index salaries_salary_index on salaries(salary);

L'index de type B-tree est l'index par défaut dans Postgresql, c'est pour cela qu'il est inutile de préciser un type.

Sans l'index, le coût d'exécution de la requête précédente est de 50924.

employees=> EXPLAIN SELECT COUNT(salary) FROM salaries WHERE salary=45001;
                            QUERY PLAN                             
-------------------------------------------------------------------
 Aggregate  (cost=50924.72..50924.73 ROWS=1 width=4)
   ->  Seq Scan ON salaries  (cost=0.00..50924.59 ROWS=52 width=4)
         FILTER: (salary = 45001)
(3 ROWS)

Avec l'index, ce coût descend drastiquement a 204 ! Mieux encore, seules 5 unités de temps sont prises pour le parcours de l'index.

employees=> CREATE INDEX salaries_salary_index ON salaries(salary);
CREATE INDEX
 
employees=> EXPLAIN SELECT COUNT(salary) FROM salaries WHERE salary=45001;
                                        QUERY PLAN                                         
-------------------------------------------------------------------------------------------
 Aggregate  (cost=204.67..204.68 ROWS=1 width=4)
   ->  Bitmap Heap Scan ON salaries  (cost=4.97..204.54 ROWS=52 width=4)
         Recheck Cond: (salary = 45001)
         ->  Bitmap INDEX Scan ON salaries_salary_index  (cost=0.00..4.95 ROWS=52 width=0)
               INDEX Cond: (salary = 45001)
(5 ROWS)

La contrepartie du gain réalisé sur les temps de recherche est que la création et la maintenance de l'arbre sont des opérations très coûteuses pour le DBMS. De plus, le stockage de l'index dans le DBMS est lui aussi couteux, car cela revient à stocker les champs de la colonne deux fois.

Un index de hash permet d'accèder très rapidement à une valeur donnée. A la différence du B-Tree, qui permet de réaliser des recherches de types “plus grand que” ou “inférieur à”, un index de hash permet de pointer sur une égalité beaucoup plus rapidement, mais est limité à cela.

index_hash.dia

Une requête sur la colonne last_name de type:

employees=> SELECT emp_no, first_name,last_name FROM employees WHERE last_name = 'Shanbhogue';

utilisera l'index Hash de la façon suivante:

1. Hachage de 'Shanbhogue' via l'algorithme de hash, la valeur récupérée est '18d1cc85f'.
2. Recherche de la valeur '18d1cc85f' dans l'index de hash
3. Recupération de toutes les lignes pointées par '18d1cc85f' dans l'index.

Sans index de Hash (et en l'absence d'index), le DBMS doit parcourir toutes les lignes de la table et réaliser une comparaison de chaîne de caractères pour chaque entrées.

Un index de type hash peut être crée dans postgresql via la requête suivante:

employees=> CREATE INDEX employees_last_name_index ON employees USING hash (last_name);

Sur la table employees, on peut mesurer l'impact d'un index hash en requêtant un comptage des employés portant le même nom.

employees=> SELECT COUNT(last_name) FROM employees WHERE last_name = 'Shanbhogue';
 COUNT 
-------
   194
(1 ROW)
 
TIME: 104.005 ms
employees=> EXPLAIN SELECT COUNT(last_name) FROM employees WHERE last_name = 'Shanbhogue';
                             QUERY PLAN                             
--------------------------------------------------------------------
 Aggregate  (cost=5992.74..5992.76 ROWS=1 width=8)
   ->  Seq Scan ON employees  (cost=0.00..5992.30 ROWS=177 width=8)
         FILTER: ((last_name)::text = 'Shanbhogue'::text)
(3 ROWS)
 
TIME: 0.848 ms

La requête sans index prend 104 ms et coûte 5992. Créons maintenant un index hash sur cette colonne.

employees=> CREATE INDEX employees_last_name_index ON employees USING hash (last_name);
CREATE INDEX
TIME: 1028.218 ms

employees=> EXPLAIN SELECT COUNT(last_name) FROM employees WHERE last_name = 'Shanbhogue';
                                           QUERY PLAN                                           
------------------------------------------------------------------------------------------------
 Aggregate  (cost=550.65..550.66 ROWS=1 width=8)
   ->  Bitmap Heap Scan ON employees  (cost=5.67..550.21 ROWS=177 width=8)
         Recheck Cond: ((last_name)::text = 'Shanbhogue'::text)
         ->  Bitmap INDEX Scan ON employees_last_name_index  (cost=0.00..5.63 ROWS=177 width=0)
               INDEX Cond: ((last_name)::text = 'Shanbhogue'::text)
(5 ROWS)
 
TIME: 1.417 ms
employees=> SELECT COUNT(last_name) FROM employees WHERE last_name = 'Shanbhogue';
 COUNT 
-------
   194
(1 ROW)
 
TIME: 4.587 ms

La requête avec l'index prend 4.5 ms et coûte 550. Alors que le parcours séquentiels coûtait près de 6000 précedemment, le parcours de l'index de Hash coûte à peine 5.63.

Lorsqu'une colonne a une quantité limitée de types de données (par exemple, le sexe d'une personne = deux types), alors il est possible d'utiliser un index de type bitmap. Cet index est en fait un tableau à deux dimensions qui contient autant de colonnes que de types, et le même nombre de lignes que d'entrées dans la table. L'intérêt d'un index bitmap est de pouvoir sélectionner un ensemble de lignes très rapidement en faisant simplement une comparaison binaire.

Dans la table employees, on a une colonne gender sur laquelle il est possible d'utiliser un index bitmap qui sera représenté de la façon suivante:

Avec un index de ce type, le DBMS va pouvoir réaliser une sélection sur le sexe en utilisant un bitmap. Par exemple, si l'on ne veut que les employés de sexe masculin, via la requête:

employees=> SELECT emp_no,gender,first_name,last_name FROM employees WHERE gender = 'M';
 
 emp_no | gender |   first_name   |    last_name
--------+--------+----------------+------------------
  10001 | M      | Georgi         | Facello
  10003 | M      | Parto          | Bamford
  10004 | M      | Chirstian      | Koblick
  10005 | M      | Kyoichi        | Maliniak
  10008 | M      | Saniya         | Kalloufi
  10012 | M      | Patricio       | Bridgland

Alors, le DBMS va créer un champ bitmap ayant pour valeur 01 (2 bits) et va comparer ce champs avec l'index bitmap en utilisant un ET LOGIQUE &.

bitmap_req = 01

pour chaque ligne dans "index bitmap employees"
faire
   
   # comparaison ET LOGIQUE
   # bitmap_req = 01      |  bitmap_req = 01
   # ligne      = 10      |  ligne      = 01
   #    &         ---     |    &         --- 
   # not match--> 00      |     match---> 01  
   #
   si ( bitmap_req & ligne == bitmap_req )
   alors, sélectionner ligne
fin

L'intérêt de l'index bitmap est d'utiliser l'opération ET LOGIQUE qui est beaucoup plus rapide qu'une comparaison de chaîne de caractères.

Seul Oracle permet d'utiliser des index bitmaps stockés sur disque. La création sous Oracle se fait via la commande suivante:

> CREATE bitmap INDEX employees_gender_index ON employees(gender);

Si la gestion de la disponilité sur des infrastructures de calculs peut être traités par un simple ajout de noeuds, dans une infrastructures de bases de données ce n'est pas le cas. Et l'un des problèmes les plus complexes de la sécurité des bases de données concernant le maintien de la cohérence des données, tout en fournissant la disponibilité. Voyons dans un premier temps les méthodes traditionnelles de sauvegardes et restauration, puis la réplication et enfin le clustering, et nous terminerons avec les travers de cette dernières méthodes.

Tout DBMS inclut des mécanismes de sauvegarde, et la sauvegarde d'une base de données doit être réalisée périodiquement. La majorité des architectures de taille importante choisit de répliquer la base de donnée maître vers une base de donnée esclave en guise de sauvegarde, mais cela ne résout pas le problème de corruption des données.

On peut noter deux méthodes de sauvegardes courantes:

• L'export au format SQL
• La sauvegarde du système de fichier

Cette méthode est de loin la plus simple et consiste à exporter l'ensemble de la base de données dans un fichier “dump” au format SQL. Ce fichier pouvant ensuite être utilisé pour ré-importer la base dans un nouveau DBMS.

Postgresql implémente cela via les outils pg_dump et pg_restore. Le premier permettant de créer une copie de la base, et le second de restaurer à partir de la copie.

Cette méthode à l'avantage de fournir un fichier SQL, donc au format texte, lisible et manipulable en dehors du DBMS. Ce “dump” pourra être utilisé pour migrer le contenu de la base vers un autre DBMS ou vers une autre version de Postgresql.

Toutefois, cela implique également que l'ensemble de la base soit sauvegardé. Hors, si la sauvegarde est lancée quotidiennement, il est inutile d'en créer un copie complète à chaque fois.

De plus, pg_dump ne copie que le contenu de la base sélectionnée, et pas le contenu des bases “systèmes” qui stockent les utilisateurs, leurs permissions, les descriptions des TABLESPACE, les paramètres internes, etc…. Pour sauvegarder ces derniers, il faudra utiliser pg_dumpall.

Si la sauvegarde via pg_dump peut être faite par n'importe quel utilisateur ayant un accès complet à la base, pg_dumpall nécessitera un accès super-utilisateur (generalement via l'utilisateur 'postgres').

<note>pg_dump ne sauvegarde pas le contenu des index, mais la commande pour les recréer.</note>

Un export peut se faire de la facon suivante:

# su postgres
$ pg_dumpall > /tmp/backup_postgres.sql
 
$ less /tmp/backup_postgres.sql
 
--
-- PostgreSQL database cluster dump
--
 
\connect postgres
 
SET client_encoding = 'UTF8';
SET standard_conforming_strings = off;
SET escape_string_warning = off;
 
--
-- Roles
--
 
CREATE ROLE empadm;
ALTER ROLE empadm WITH NOSUPERUSER INHERIT NOCREATEROLE NOCREATEDB LOGIN PASSWORD 'md57338b9f359bce1658a76752a172a1729';
CREATE ROLE postgres;
ALTER ROLE postgres WITH SUPERUSER INHERIT CREATEROLE CREATEDB LOGIN;
 
--
-- Database creation
--
 
CREATE DATABASE employees WITH TEMPLATE = template0 OWNER = postgres;
REVOKE ALL ON DATABASE employees FROM PUBLIC;
REVOKE ALL ON DATABASE employees FROM postgres;
GRANT ALL ON DATABASE employees TO postgres;
GRANT CONNECT,TEMPORARY ON DATABASE employees TO PUBLIC;
GRANT ALL ON DATABASE employees TO empadm;
REVOKE ALL ON DATABASE template1 FROM PUBLIC;
REVOKE ALL ON DATABASE template1 FROM postgres;
GRANT ALL ON DATABASE template1 TO postgres;
GRANT CONNECT ON DATABASE template1 TO PUBLIC;
 
\connect employees
 
--
-- PostgreSQL database dump
--
 
SET statement_timeout = 0;
SET client_encoding = 'UTF8';
SET standard_conforming_strings = off;
SET check_function_bodies = false;
SET client_min_messages = warning;
SET escape_string_warning = off;
 
--
-- Name: plpgsql; Type: PROCEDURAL LANGUAGE; Schema: -; Owner: postgres
--
 
CREATE OR REPLACE PROCEDURAL LANGUAGE plpgsql;
ALTER PROCEDURAL LANGUAGE plpgsql OWNER TO postgres;
SET search_path = public, pg_catalog;
SET default_tablespace = '';
SET default_with_oids = false;
 
--
-- Name: departments; Type: TABLE; Schema: public; Owner: empadm; Tablespace: 
--
 
CREATE TABLE departments (
    dept_no character(4) NOT NULL,
    dept_name character varying(40) NOT NULL
);
 
ALTER TABLE public.departments OWNER TO empadm;
 
[...]

L'import est similaire:

# su postgres
$ psql < /tmp/backup_postgres.sql
You are now connected to database "postgres".
SET
SET
SET
CREATE ROLE
ALTER ROLE
[...]

Il est possible de sauvegarder une base de données en copiant l'ensemble de ses fichiers sur disques. Ce mécanisme n'est pas propre aux DBMS mais aux architectures de systèmes de fichiers. Toutefois, la majorité des DBMS déconseillent fortement de copier des fichiers quand le DBMS est en cours d'exécution. Il faut donc couper les processus pour réaliser la copie des répertoires, ce qui est contraignant.

Une approche distribuée consiste à positionner les fichiers de la base de données sur un stockage réseau (type SAN).Il est ensuite possible de réaliser une synchronisation par block du SAN, ce qui fournit une copie binaire du DBMS 'd'un SAN à un autre.

Il existe également des systèmes de fichiers répartis en cluster, de type GFS ou DRDB, qui peuvent couvrir la sauvegarde des fichiers d'une base de données.

La réplication peut être considérée comme une version évoluée de la sauvegarde dans laquelle le serveur esclave maintien à jour un copie du serveur maitre et est près à repartir au plus tôt en cas de problème. La réplication consiste donc à faire redescendre les données d'un serveur maître vers un ou plusieurs eslaves. Le degré de réplication s'évalue essentiellement sur la fréquence des mises à jour des esclaves, ainsi que sur le fait que les esclaves soient accessibles aux clients ou non.

La limitation d'une sauvegarde est conditionné par le fait que les transactions en cours et non encore committées n'apparaissent ni dans le dump d'une base au format SQL, ni dans la copie du système de fichiers. Il faut manipuler les journaux de transactions pour retrouver les transactions en cours qui n'ont pas encore été committées par le DBMS. Cette technique est également appelée sauvegarde à chaud, ou log shipping.

Cela consiste à initialiser le serveur esclave avec une copie complète du système de fichiers du maître, puis à répliquer les fichiers journaux au fur et à mesure. Comme on l'a vu, ces journaux conservent un état des transactions qui peut être rejoué. Cela permet donc de récupérer l'état de la base jusqu'au dernier journal répliqué, et également de réduire la quantité de donnée transférée du maitre à l'esclave à chaque instanciation.

La conservation des journaux permet également de restaurer la base à une date antérieure, en ne rejouant que les journaux allant jusqu'à cette date.

Sous Postgresql, ce sont les fichiers WAL (Write Ahead Logs) qui contiennent ces journaux. Mettre en place ce type de sauvegarde requiert de Postgresql qu'il archive tous les fichiers journaux WAL (au lieu de les recycler périodiquement). Techniquement, cela signifie que le DBMS remplit les fichiers journaux WAL les uns après les autres, et dès qu'un fichier est remplit, il copie ce fichier vers le serveur esclave. La copie est assurée automatiquement par Postgresql, qui s'assure que le fichier est bien arrivé à destination. Si c'est le cas, le fichier WAL est sera éventuellement recyclé par le maître.

Ainsi, seul le serveur esclave conserve tous les fichiers WAL et doit supporter l'espace disque supplémentaire pour cela. Le serveur maître recyclera ses journaux au fur et à mesure pour éviter de saturer l'espace disque avec des journaux anciens.

<note important>Une base ayant peu de transactions ne verra pas ses fichiers se remplir rapidement, et l'archivage des fichiers WAL n'étant lancé que sur des fichiers complets, cela signifie qu'il faudra placer un age limite des fichiers WAL au dela duquel l'archivage DOIT être lancé.</note>

Ce mode de sauvegarde est appelé Warm Standby, car le serveur esclave est prêt à prendre la main en cas de crash du maître, mais n'est pas accessible par les clients tant que le maître fonctionne.

Il s'agit d'une amélioration du mode précédant dans lequel les esclaves sont accessibles par les clients, mais seulement pour les requêtes de consultation (SELECT). Les esclaves ne peuvent pas réaliser de mises à jour, cela doit être fait sur le maître.

Toutefois, la réplication se faisant toujours à fréquence de remplissage des fichiers WAL, un important délai est à attendre entre la mise à jour d'une donnée sur le maitre et sa réplication sur les esclaves, ce qui peut être génant quand une requête atteint un esclave et que ce dernier renvoi une donnée obsolète.

Il est possible de réduire le délai de réplication en permettant à l'esclave d'être en permanence connecté au maître afin de récupérer les changements effectués sur ce dernier. Cette technique, appelée streaming replication permet d'atteindre des délais de l'ordre de la seconde.

Comme on le voit, ces techniques de sauvegarde et de réplication limite l'architecture à un maitre seul responsable de la mise à jour des données. En fait, le problème d'avoir plusieurs maitres pouvant réaliser des mises à jour, tout en conservant un ensemble fiable, a été décrit dans le théorème de CAP. En 2000, Dr. Eric Brewer a produit ce théorème (CAP = Consistency, Availability and Partition tolerance) qui établit qu'il est impossible de traiter à la fois la perte de cohérence des données, la perte de disponibilité et le risque de partitionnement des noeuds. Il est uniquement possible d'en traiter deux en même temps. Voyons pourquoi.

Sur un système multi-noeuds, chaque noeud peut être mis à jour indépendamment de ses voisins. Si une requête de mise à jour de Valeur-1 est envoyée a noeud-A, suivie juste après une requête de lecture de la même Valeur-1 envoyée à noeud-B, alors la cohérence des données est assurée si la valeur retournée par noeud-B est la valeur mise à jour. En pratique, cela signifie que noeud-A et noeud-B doivent être en synchronisation constante, que cette synchronisation doit être la plus rapide et efficace possible. (problème de type “race to zero”). Mais cela signifie également que noeud-B, lorsqu'il reçoit la requête de lecture, doit s'assurer que Valeur-1 n'a pas été mise à jour dans un autre noeud avant de renvoyer sa réponse.

Donc, maintenir la cohérence des données implique que TOUS les noeuds soient disponibles. Si un noeud est manquant, alors il est possible que ce noeud manquant contienne une version mise à jour de Valeur-1. Il est donc impossible de fournir une réponse sans vérifier ce noeud et sans violer la cohérence des données.

La disponibilité d'une infrastructure de bases de données est définit par le fait que, quoi qu'il arrive sur le réseau, chaque requête reçut par le système doit faire l'objet d'une réponse. Cela signifie que chaque noeud de l'infrastructure doit répondre aux requêtes qu'ils reçoit avec l'information qu'il possède. En théorie, une disponibilité de 100% est idéale. En pratique, c'est impossible mais il est courant de voir des infrastructures approcher les quelques secondes d'indisponibilités par an.

<note tip>Pour rappel, une heure d'indisponibilité par an égal 99.988% de disponibilité. Mais il est également possible de calculer une disponibilité selon le temps de réponse, par exemple: 95% des requêtes répondus en mois d'une seconde, 98% en moins de 2 secondes, 99,5% en moins de trois secondes, etc..</note>

En Anglais, Partition Tolerance. Partitionner une infrastructure de base de données, c'est isoler les noeuds les uns des autres. Cela arrive lorsque les connections réseaux entre les noeuds, ou entre les clients et les noeuds, sont interrompus. Ce premier cas étant d'ailleurs le plus simple à traiter car, si un noeud arrête de répondre, l'erreur est simple à relever, alors que si un noeud renvoi des réponses fausses, il est difficile d'identifier et souvent de corriger le problème.

Il est tout simplement impossible de couvrir complètement le risque de partitionnement, car cela impliquerait d'avoir une infrastructure système et réseaux de disponibilité 100%, et donc un risque zéro, ce qui n'existe pas.

Il est toutefois possible de calculer la probabilité d'occurence d'une panne sur l'ensemble de l'infrastructure via la formule suivante:

P(panne) = 1 - P(disponibilité)^(nb noeuds)

Avec:

• P(panne) la probabilité d'une panne sur l'infrastructure
• P(disponibilité) la disponibilité de chaque noeud, ou probabilité de résistance a une panne
• nb noeuds le nombre de noeuds dans l'infrastructure.

Exemple: 4 noeuds avec une disponibilité individuelle de 99.9% P(panne) = 1 - (0.999^4) = 1 - 0.996 = 0.00398 ~= 0.4%

0.4% signifie que, sur un an, l'infrastructure aura une probabilité de panne de l'ordre de 126144 secondes, soit 1.46 jours.

Traiter le partitionnement est obligatoire dans les systèmes modernes. Ainsi, le choix entre partitionnement, disponibilité et cohérence (sachant que l'on ne peut en prendre que deux) se limite en fait à choisir entre disponibilité et cohérence.

Imaginons trois noeuds: {A}, {B} et {C}. Ces trois noeuds disposent chacuns d'une copie complète de la base de données, les tables, les index, etc…

Une panne survient sur le lien qui relie {A} et {B} a {C}. {C} est isolé de ses voisins mais reçoit toujours les requêtes de ses clients.

Si un client X envoi une requête de mise à jour a {C}, ce dernier a deux options:

1. Accepter la mise à jour, sachant que ni {A} ni {B} ne pourront être prévenu de celle-ci. On sacrifie donc la cohérence des données, mais le système renvoi une réponse valide et est donc disponible.
2. Refuser la mise à jour sur le prétexte que ni {A} ni {B} ne peuvent être prévenu, on maintient donc la cohérence des données mais le système est indisponible.

Il n'y a pas d'autre choix possible, soit on maintien la cohérence, soit on maintien la disponibilité.

harvest et Yield.

Le renforcement du niveau de confidentialité d'une base de données passe avant tout par une gestion des droits sur les éléments de la base.

La notion de rôle est très similaire à celle d'utilisateur et de groupes sur les systèmes d'exploitations. Un rôle dispose de droits (permissions) lui permettant de réaliser des actions sur différents éléments de la base de données. Les DBMS possèdent des tables internes, propres au DBMS, qui permettent de définir et stocker ces rôles et droits: ils ne sont jamais stockés dans la base de données à laquelle ils s'appliquent, mais dans une table système.

<note important>Il ne faut pas confondre les roles et droits qui permettent d'accèder à la base de données, et les rôles et droits des utilisateurs de lápplication. Ces derniers sont bien de la responsabilité de l'application et stockés dans les tables de l'application. Ici, nous couvrirons uniquement les permissions internes du DBMS.</note>

Dans Postgresql, c'est la table pg_roles qui contient les rôles du DBMS. On peut lister les rôles existant via une simple requête SELECT ou via la commande \du:

postgres=# SELECT * FROM pg_roles;
 rolname  | rolsuper | rolinherit | rolcreaterole | rolcreatedb | rolcatupdate | rolcanlogin | rolconnlimit | rolpassword | rolvaliduntil | rolconfig |  oid  
----------+----------+------------+---------------+-------------+--------------+-------------+--------------+-------------+---------------+-----------+-------
 empadm   | f        | t          | f             | f           | f            | t           |           -1 | ********    |               |           | 16384
 postgres | t        | t          | t             | t           | t            | t           |           -1 | ********    |               |           |    10
(2 ROWS)

Un rôle est un objet simple auquel on va appliquer des droits via la commande GRANT, et révoquer ces droits via la commande REVOKE. Un rôle peut également hériter des droits d'un rôle parents et hérite systèmatiquement des droits “public”. Les droits d'un rôle sur un objet de la base de données sont déterminés par:

1. les droits dont le rôle dispose lui_même;
2. les droits hérités des rôles dont le rôle est membre;
3. des droits publics.

roles.dia

Sous Postgresql, la création d'un rôle est simple:

CREATE ROLE nom_role;

On peut ajouter les options suivantes:

• LOGIN: Autorise le rôle à se connecter à la base de données.
• SUPERUSER: donne les pouvoirs de superutilisateur aux rôle
• CREATEROLE: permet au role de créer d'autres rôles;
• PASSWORD: affecte un mot de passe au rôle.

Un rôle peut hériter d'un autre rôle. Pour cela, il faut créer les deux rôles et, via la commande GRANT, ajouter le rôle fils dans le rôle père:

CREATE ROLE pere;
CREATE ROLE fils LOGIN INHERIT;
GRANT pere TO fils;

L'attribut INHERIT permet de définir que le rôle “fils” récupère automatiquement les droits du rôle “père”. Sans cet attribut, lorsque “fils” se connecte, il dispose de ses droits propres, et doit déclencher un changement de rôle pour accèder aux droits de père.

Le changement de rôle s'opère (depuis la session de “fils”) via la commande :

SET ROLE pere;

Toutefois, cette commande signifie que fils est maintenant identifié en tant de pere et avec les droits de pere. Il n'a plus accès à ses droits spécifiques. Il peut toutefois retourner dans son propre rôle avec la commande “SET ROLE fils”.

Il n'y a pas de limite au nombre de niveaux qu'il est possible d'encapsuler, tant qu'aucune définition circulaire n'apparait.

Le propriétaire d'un objet (par défaut, son créateur) dispose automatiquement de tous les droits sur l'objet. Pour les autres rôles, il faut positionner les droits manuellement. Il est toutefois possible de déclarer un objet comme étant “public”, ce qui le rend accessible à tous les rôles.

Lors de l'exécution d'une requête, le DBMS vérifie que le rôle qui exécute l'action dispose du droit nécessaire. Chaque utilisateur ou client est représenté par un rôle, l'action est généralement spécifiée comme premier mot clé de la requête (SELECT, INSERT, …) et le droit doit être positionnée au préalable via la commande GRANT.

Le DBMS va donc maintenir une liste des droits liant des rôles à des actions et contrôler cette liste pour chaque opération réalisée.

Admettons qu'une application consult (connu sous un rôle nommé “consult”) ait besoin de lire les salaires des employés, mais pas leurs noms. On peut donc positionner, sur la base de données employees, la permission suivante:

GRANT SELECT ON salaries TO consult;

Cela permet au rôle “consult” de lister toutes les colonnes et lignes de la table employees.salaries.

postgres=# CREATE ROLE consult login;
 
postgres=# \CONNECT employees;
 
employees=# GRANT SELECT ON salaries TO consult;
GRANT
 
employees=# SET ROLE consult;
SET
 
employees=> SELECT * FROM salaries WHERE salary = 45000;
 emp_no | salary | from_date  |  to_date   
--------+--------+------------+------------
  13484 |  45000 | 1995-01-01 | 1996-01-01
  14605 |  45000 | 1991-03-12 | 1992-03-11
  15959 |  45000 | 1999-01-26 | 2000-01-26
  36039 |  45000 | 1991-06-07 | 1992-06-06
[...]
 
employees=> SELECT * FROM employees WHERE last_name LIKE 'Callaway';
ERROR:  permission denied FOR relation employees

Maintenant admettons que l'application dashboard ait également besoin d'accèder à la liste des salaires, mais uniquement pour en réaliser des statistiques (calculs de salaire moyen, max, min, etc…). Donner l'accès à toute la table employees.salaries expose inutilement le lien entre un salarié (par son numéro ID) et son salaire, lien qui est souvent confidentiel. Dans un cas pareil, il est possible de ne donner accès qu'a certaines colonnes de la table. La syntaxe de GRANT n'est que légèrement différente de l'exemple précédent.

employees=# CREATE ROLE dashboard login;
CREATE ROLE
employees=# GRANT SELECT (salary) ON salaries TO dashboard;
GRANT
employees=> SELECT avg(salary) FROM salaries;
        avg         
--------------------
 63810.744836143706
(1 ROW)
 
employees=> SELECT avg(salary),COUNT(emp_no) FROM salaries;
ERROR:  permission denied FOR relation salaries

<note important> S'il est possible de limiter les permissions aux colonnes, il est impossible de le faire pour les lignes, et un droit SELECT aura toujours accès à toutes les lignes de la table. Un DBMS ne peut déterminer qu'une ligne est confidentielle qu'en la lisant, et donc en violant le droit éventuel.</note>

La gestion des droits sur une base de données peut s'appliquer à des niveaux de granularités variables, que l'on peut représenter dans une matrice à deux dimensions (les colonnes représentent le type de droits, et les lignes les objets auquels ils s'appliquent):

La commande REVOKE est symétrique à GRANT et permet de révoquer une permission attribuée. Les mêmes règles que pour GRANT s'appliquent.

Lors de l'attribution d'une permission, il est possible de permettre au rôle d'attribuer cette même permission à d'autres rôles par la suite. Pour cela, les nits clés “WITH GRANT OPTION” doivent être présent à la fin de la requête.

GRANT INSERT ON employee.salaries TO bigboss WITH GRANT OPTION;

Enfin, Postgresql permet de lister les permissions sur une table via la commande \dp.

employees=# \dp
                                Access privileges
 Schema |     Name     | TYPE  |   Access privileges   | COLUMN access privileges 
--------+--------------+-------+-----------------------+--------------------------
 public | departments  | TABLE |                       | 
 public | dept_emp     | TABLE |                       | 
 public | dept_manager | TABLE |                       | 
 public | employees    | TABLE |                       | 
 public | salaries     | TABLE | empadm=arwdDxt/empadm | salary:
                               : consult=r/empadm      :   dashboard=r/empadm
 public | titles       | TABLE |                       | 
(6 ROWS)

Les domaines de la cryptographie sont nombreux et nous ne les couvrirons pas tous ici. Deux besoins différents peuvent être couverts par les mécanismes classiques:

1. la vérification qu'une donnée fournit correspond à la donnée stockée (le cas d'un mot de passe)
2. le stockage et la lecture d'une donnée sensible

Le premier cas peut être couvert par les mécanismes de hachage (typiquement md5 et sha1). Le second requiert le chiffrement symétrique ou asymétrique.

Il est généralement conseillé de stocker les mots de passe sous une forme inintelligible via un algorithme de Hachage, et de vérifier les mots de passe proposés en comparant les empreintes. Les algorithmes MD5 et SHA1 (bien que tout deux ayant des faiblesses cryptographiques) permettent de calculer des empreintes allant de 128 à 168 bits (et plus avec les versions suivantes de SHA). Ces deux algorithmes sont couramment utilisés par les DBMS, et on les retrouve dans MySQL sous la commande PASSWORD et dans PostgreSQL sous la commande md5(). Toutefois, ces deux fonctions ne réalisent pas de salage des données avant hachage. Dans le cas du stockage de mot de passe, les mêmes règles de sécurité que pour tout autre système s'applique, et le stockage d'une empreinte non salée sera faiblement resistante à une attaque de type rainbow table. <note> Pour rappel: un algorithme de hachage calculera toujours la même empreinte pour la même donnée. Ainsi, si deux utilisateurs ont le même mot de passe, la valeur de md5(mot de passe) sera la même. Pour cette raison, il est préférable d'ajouter un “sel” (une valeur aléatoire) avant hachage pour s'assurer que deux mot de passes identiques, mais avec un sel différent, ne produiront pas la même empreinte.</note>

Pour calculer des mots de passe avec salage, PostgreSQL propose le module pgcrypto qui inclut la fonction crypt. Oracle a introduit dans sa version 11g un système de calcul des mots de passe utilisant SHA-1 et un salage.

<note important>Avant utilisation du module crypto, il faut importer son set de fonctions dans le DBMS.

postgres=# \i /usr/share/postgresql/8.4/contrib/pgcrypto.sql

</note>

Pour créer un mot de passe salé sous PG:

postgres=# SELECT crypt('ultrapassword', gen_salt('md5'));
               crypt                
------------------------------------
 $1$y5aceMSV$GUP7iR1ihte4AlPkM2Law0
(1 ROW)
 
postgres=# SELECT crypt('ultrapassword', gen_salt('md5'));
               crypt                
------------------------------------
 $1$zoaNojOt$ByhLhrKi5.t0JoS56YM/r/
(1 ROW)
 
postgres=# SELECT crypt('ultrapassword', gen_salt('md5'));
               crypt                
------------------------------------
 $1$RG9ODqk6$kNBLZcI9.zXBv8ACvrowA0
(1 ROW)

<note>Par defaut, postgresql stocke les mots de passe de ses utilisateurs internes sous forme md5 salée.

postgres=# ALTER ROLE consult WITH password 'oisad@iojda09721';
ALTER ROLE
 
postgres=# SELECT * FROM pg_shadow;
  usename  | usesysid | usecreatedb | usesuper | usecatupd |               passwd                | valuntil | useconfig 
-----------+----------+-------------+----------+-----------+-------------------------------------+----------+-----------
 empadm    |    16384 | f           | f        | f         | md57338b9f359bce1658a76752a172a1729 |          | 
 postgres  |       10 | t           | t        | t         |                                     |          | 
 dashboard |    16450 | f           | f        | f         |                                     |          | 
 consult   |    16449 | f           | f        | f         | md5a529f4a366c8aebb64058629093d3d36 |          | 
(4 ROWS)

</note>

Toutefois, si ce mode de stockage des mots de passe est bien meilleur qu'un stockage en texte clair, il peut être amélioré. En effet, le système d'authentification est l'un des rares où les temps de latences ne sont pas un problème: un utilisateur acceptera facilement d'attendre 1 ou 2 secondes avant de voir sa session ouverte. Ce temps peut être mis à disposition du processus de vérification du mot de passe pour ralentir l'authentification. En ajoutant un délai, on rend complètement impossible les attaques pas brute force (qui requiert de tester plusieurs millions de mots de passe par seconde).

Sous Postgresql, une fonction du module crypto est prévu pour cela. Il est possible d'utiliser un algorithme Blowfish a la place du md5, et de modifier le nombre d'itération afin d'augmenter le temps d'authentification.

Voici une comparaison des temps de calcul avec les différentes méthodes:

postgres=# SELECT crypt('ultrapassword', gen_salt('md5'));
               crypt                
------------------------------------
 $1$KA.Ev3vf$fzesnQ5cCwGSLTeYkg4cr0
(1 ROW)
 
TIME: 1.084 ms
 
 
postgres=# SELECT crypt('ultrapassword', gen_salt('bf'));
                            crypt                             
--------------------------------------------------------------
 $2a$06$tq5OES3.0ucJ/0C.7WL8neF1LAZ/Hlhg7meWLW/YrRKToPmjkdaXa
(1 ROW)
 
TIME: 8.934 ms
 
 
postgres=# SELECT crypt('ultrapassword', gen_salt('bf',8));
                            crypt                             
--------------------------------------------------------------
 $2a$08$hOMT/bCTeKBMPJ6vtd7ffu0u1tsiBJc7OCasUVzWA46Qvo/UDwNIq
(1 ROW)
 
TIME: 35.394 ms

: verification de mot de passe

Chaque DBMS a ses propres fonctions pour chiffrer les données en bases. Dans le cas de Postgresql, il s'agit d'une importation des fonctions de GnuPG. Ces dernières permettent de réaliser des opérations de chiffrements symètriques et asymètriques dans les requêtes.

Un exemple simple ci-dessous permet d'illustrer le chiffrement de la valeur 'secret data' avec la clé 'secretkey123'. Les paramètres de chiffrement sont positionnés à la fin de la commande.

postgres=> SELECT pgp_sym_encrypt('secret data', 'secretkey123','compress-algo=2, cipher-algo=aes256');

On peut utiliser cette fonction pour chiffrer une donnée avant de l'insérer en base. Il faut que cette donnée soit de type bytea pour stocker des données binaires. Par exemple, si nous souhaiter chiffrer le salaire d'Alejandro Brender, on peut le faire de la facon suivante:

employees=# ALTER TABLE salaries ADD crypt_salary bytea;
ALTER TABLE
 
employees=# UPDATE salaries SET crypt_salary = pgp_sym_encrypt('120000', 'secretkey123','compress-algo=2, cipher-algo=aes256') WHERE emp_no = 10039 AND to_date > CURRENT_DATE;
UPDATE 1
 
employees=# SELECT crypt_salary FROM salaries WHERE emp_no = 10039 AND to_date > CURRENT_DATE;
crypt_salary                                                                                                                  
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 \303\015\004\011\003\002\235\265\334W%~\033\022v\322A\001w\0301\006\015o\034\255\352%\003\267\240\377Ir\346\302e\354\355\306\002\337\277M:|\255a\362>\322eu\203\367>\245#0=\235\007o\205\357\355MW<R\355!\344\347\2568\314\177\024\024\361\336
(1 ROW)

Pour lire la valeur, il faut déchiffrer les données dans la requête :

employees=# SELECT pgp_sym_decrypt(crypt_salary,'secretkey123') FROM salaries WHERE emp_no = 10039 AND to_date > CURRENT_DATE;
 pgp_sym_decrypt 
-----------------
 120000
(1 ROW)

Et avec la mauvaise clé, on recoit l'erreur suivante:

employees=# SELECT pgp_sym_decrypt(crypt_salary,'faussecle') FROM salaries WHERE emp_no = 10039 AND to_date > CURRENT_DATE;
ERROR:  Wrong KEY OR corrupt DATA

Il est des cas où la protection des données ne peux pas passer par une technique d'offuscation. Un exemple: alors que dans 98% des cas, il est recommandé, voir imposé, de ne pas stocker de mots de passe en clair dans la base, cela est indispensable lorsque l'on souhaite utiliser un algorithme d'authentification basé sur les challenges/responses. DIGEST-MD5 fonctionne comme cela. Il implique que le client et le serveur calculent une empreinte du mot de passe de d'une donnée variable via MD5, puis le client envoi son empreinte au serveur, qui compare avec son empreinte locale. Cela évite que le mot de passe ne soit échangé, mais impose que le serveur puisse lire le mot de passe en clair dans la base pour calculer sa propre empreinte.

Oracle Dabatase Security

Postgresql 9.0 doc fr

You can't sacrifice partition tolerance

GreenSQL

Wikipedia Database Book

MongoDB

Postgresql tips and tricks

Data Modeling

Data Normalization

SQL: Basics, SELECT

SQL: Joins, subqueries, views

SQL: Connecting to database servers

exams

QCM #1

QCM #2

Transactions and Recovery Study Question Solutions