Gestion de Données Objets

Planche : 1

Expériences de Gestion de Données Objets
ou
Les bases de données vues du sol

Travail en partie financé par le programme européen :

BIO4-CT96-0110

Integrated Protein Database

Coordinateur du projet : Hans-Werner Mewes, MIPS, Munich.
Collaborateur principal : Louis M. Jones.
Un des objectifs : développer la technologie « Bases de données ».
Plus précisément : OODBMS (Systèmes de Gestion de Données Objets, SGDOs).

Pourquoi les SGDOs ?

Voici trois échantillons de ce qu'il faut écrire pour remporter un appel d'offres :

« Classical RDBMS do not readily facilitate the intuitive representation of complex objects. Genes are perfect examples for multicomponent objects: ... »

« The project will provide suitable software tools to merge protein sequences from different scientific reports into a canonical sequence database entry. These developing procedures will be incorporated into the integrated system within ObjectStore (TM). »

« This concept will be applied to create a number of species specific data sets which will integrate information from genomic sequencing and functional analysis projects (S. cerevisiae, A. thaliana). »

Le dernier est le plus important : cela s'appelle une problématique scientifique.

Gestion de données imprévisibles

Les SGBD-R sont un cadre assez rigide qui ne se prête sans doute pas assez bien à l'accueil de données produites par une activité de recherche, foisonnante et imprévisible.

Si les données sont très bien rangées, il sera probablement difficile d'y introduire des informations non prévues à l'avance. Les SGBD-R sont très bien rangés.

Les SGDOs donnent l'espoir d'une plus grande souplesse.

Comment est organisée une base de données relationnelle ?

Sous forme de table rectangulaire :

Identifiant	Nom	Prénom	Âge	Résidence
12	Martin	Pierre	35	Paris
14	Dupont	Martine	25	Lyon
15	Durand	Anne	32	Nantes
23	Dupont	Cécile	40	Bordeaux
...	...	...	...	...

-1cm0cm

SwissProt en relationnel

[t]1.4cm Entrée

AC ac#-1
ID ident
DT créa.
DT maj.
DT anno.
DE desc.
OG ogl.
OC taxon
GN gène
CC com.
KW kw.

[t]1.4cm Accession AC ac#-1 ac# AC ac#-n	[t]1.4cm Espèce AC ac#-1 spec# OS esp.	[t]1.4cm Banque AC ac#-1 dbref# DR dbref
[t]1.4cm Référence AC ac#-1 RN ref# RP txt RC txt RX xref. RT txt	[t]1.4cm Auteur AC ac#-1 RN ref# aut# RA nom	[t]1.4cm Journal AC ac#-1 RN ref# journal# RL pub.

[t]1.4cm Feature

AC ac#-1
feature#
keyname
FROM
TO
Desc.

[t]1.4cm Séquence

AC ac#-1
AA aa
MW mw
CRC crc
seq-txt

Contraintes des SGBD-R

Les tables doivent être rectangulaires et les valeurs dans les cases atomiques.

Quelques questions :

si l'unicité du premier « accession number » n'est pas vérifiée tout s'écroule ;
tout changement, notamment dans l'arité des attributs remet beaucoup de choses en cause parce que tous les objets doivent entrer dans le même cadre exactement ;
le texte de la séquence dans une table : cela va parce que ce sont des protéines (® BLOB) ;
chaque objet-séquence est découpé en rondelles pour entrer dans des tables, donc :
- le reconstituer demande le recollage des morceaux,
- tout traitement effectué dans la partie « client » du logiciel sera inefficace,
- surtout, usage efficace du cache impossible ;
en d'autres termes, les résultats des requêtes ne sont généralement pas de « bons objets » pour un langage de programmation.

Ce schéma n'est pas idéal

Plus précisément :

ici la table des espèces reproduit pour chaque entrée les valeurs des champs « OS », une par ligne ;
il serait plus élégant de pointer sur une table générale des espèces ;
mais il n'existe pas de telle table, d'ailleurs la constituer est un domaine de recherche en soi ;
de même pour les auteurs des références ;
mais il n'existe pas de répertoire des auteurs.

Qualités des SGBD-R

Les avantages :

l'organisation en tables rectangulaires permet (en principe) de bonnes performances (pour les traitements qui entrent bien dans ce moule) ;
l'interrogation se fait au moyen de SQL, un langage déclaratif, non-procédural : ceci permet une optimisation des traitements réalisés par la partie « serveur » du logiciel. En effet la requête indique quelles sont les données à extraire, pas comment, le processeur de requêtes est libre de sa stratégie ;
tout traitement qui peut se faire par simple parcours d'une table unique est efficace.

L'idée des SGDOs

rendre persistantes les données sous leur forme en mémoire pendant leur traitement par un programme.
plus de découpage en rondelles ;
plus de cadre rectangulaire ;
souplesse dans le format des objets ;
les traitements réalisés par le « client » devraient être efficaces.

Technique de la persistance

l'espace disque est plus ou moins considéré comme de la mémoire virtuelle ;
en C++, une armée de classes gèrent la base de données ;
l'allocation de mémoire persistante se fait avec l'opérateur new doté de l'argument facultatif mais standard de placement qui fait référence à la base ;
pour améliorer les performances ObjectStore utilise la technique dite de l'image--mémoire ;
la méthode d'accès à la mémoire persistante est mmap ;
C++ utilise des pointeurs explicites : beaucoup de SGDOs traitent les pointeurs par pointer swizzling, remplacement des pointeurs par des OIDs.

ObjectStore

ObjectStore évite le pointer swizzling en donnant à ses objets des adresses fixes dans des segments contigus de mémoire virtuelle ;
les OID's sont de vrais pointeurs ;
mais : soit la base n'est pas plus grosse que la mémoire virtuelle et c'est possible ;
soit la base est plus grosse que la mémoire virtuelle et il y a des collisions ;
et quand on a le serveur en adresses 64 bits et le client en 32 bits...
pour ces cas ObjectStore propose la classe os_soft_pointer... et le swizzling.

Comment cela fonctionne

Pour accéder à un objet on déréférence un pointeur. Si la référence est vers la mémoire persistante : mmap et swizzling. Il faut éviter cette situation.

Les collections (listes, tableaux, dictionnaires, ensembles, sacs) permettent d'optimiser certains traitements : une requête sur une collection peut admettre comme réponse une sous--collection.

Cette requête à réponse multiple pourra renvoyer, au lieu de la sous--collection, un itérateur qui en facilitera le traitement.

Pour que ceci soit raisonnablement efficace, il faut que les données soient le plus souvent possible en mémoire virtuelle.

Notion de transaction : à la fermeture d'une transaction les pointeurs sont invalidés. Donc on fera des transactions longues (très longues), mais cela a un prix élevé : intégrité, reprise...

Questions de performance

Images/Sgbo/hiera_mem.5

Questions de performance (suite)

Une instruction simple : 1,2 à 1,5 cycles.

Mais :

3 ou 4 instructions en parallèle ;
10 étages de pipe-line.

Un cycle : de l'ordre de la nanoseconde.

Accès au cache L1 : 1 ou 2 cycles.

Accès au cache L2 : 4 à 8 cycles.

Accès à la mémoire : 40 à 100 cycles.

Accès à la mémoire de pages : 500 000 à 1 000 000 cycles.

Mesures de performance

-1cm0cm

Les processeurs Alpha comportent un circuit destiné au profilage en continu : il échantillonne tous les n cycles un certain nombre d'informations, notamment l'image en cours d'exécution. Le logiciel Dcpi permet de stocker et d'analyser les résultats. Typiquement, n = 63 488.

	17 576 insertions	17 576 insertions	17 576
	dans une base	dans une base	écritures
	ObjectStore ; C	ObjectStore	dans un
	clés aléatoires	Scheme	fichier plat
libos.so	26 371	26 517
osserver	876	859
liboscol.so	1 122	1 151
libosqry.so	2	2
oscmgr	11	11
libosmop	0	1
./call-os	669	628	1 121
libbigloo	6	11	1 259
libgc.so	130	134	669
Total	29 186	29 311	3 049

	676 interrogations	676 interrogations
	dans un fichier plat	base ObjectStore
	clés aléatoires	clés aléatoires
	réponses multiples	réponses multiples
libos.so	0	2 221 545
osserver	0	2 154
liboscol.so	0	1 752 100
libosqry.so	0	565 367
oscmgr6	0	92
libosmop.so	0	995
./call-os	265 091	253
libbigloo.so	1 011 736	383
libgc.so	829 611	232
Total	2 106 439	4 543 121

Des insertions :

Insertions :	5 000	7 500	10 000	12 500
libos.so	11 399	15 103	19 034	25 193
osserver	1 203	1 332	1 501	1 834
liboscol.so	284	445	522	730
call-os	196	276	394	480
libgc.so	140	145	140	141
libbigloo	9	7	10	3
oscmgr6	9	8	7	10

Images/Sgbo/cyc-exec-inserInsertions0.5

Images/Sgbo/cyc-exec-petitInsertions0.5

-1cm0cm

Des interrogations :

Insertions :	50	100	150	200
libos.so	517 807	716 064	892 926	1 084 122
liboscol.so	220 148	414 716	610 072	784 392
libosqry.so	65 719	122 241	193 609	247 662
osserver	3 161	3 687	3 665	3 807
oscmgr6	11	36	76	48
libosmop.so	77	160	275	364
call-os	33	68	87	125
libbigloo	47	85	104	154
libgc.so	135	181	172	184

Images/Sgbo/cyc-exec-queriesInterrogations0.5

Images/Sgbo/cyc-exec-petitInterrogations0.5

Images/Sgbo/cyc-exec-trespetitInterrogations0.5

Travaux sur ce sujet

D'autres personnes ont fait des essais similaires aux nôtres :

À l'EBI, Patricia Rodriguez-Tomé travaille régulièrement avec Sybase, Oracle et PostgreSQL. Elle a essayé ObjectStore.
À l'Université de l'Utah, Gary Lindstrom, du département d'informatique, a collaboré avec le centre de recherche sur le génome humain qui avait une base de données de laboratoire (un LIMS) sous Sybase ; ils ont porté la chose sous ObjectStore parce qu'ils étaient las des changements permanents qui remettaient en cause le schéma de la base.

http://www-sor.inria.fr/~lindstro/ http://www.cs.utah.edu/~gary/home.html

Conclusions analogues

là où le SGBD-R est très lent, le SGDO est trois fois plus rapide ;
ailleurs il est trois fois plus lent ;
pas de protection au niveau de l'objet ;
pas de langage d'interrogation ;
système fermé, utilisable en gros par l'auteur de la base.

Oublier la persistance ?

L'échec des SGDOs est-il celui de la persistance ? Une grande partie des difficultés et des inefficacités tient à l'implantation de la persistance au-dessus d'un système d'exploitation et, surtout, d'un système de fichiers inadaptés.

Dans le passé des systèmes d'exploitation ont aboli la distinction entre mémoire et système de fichiers : la mémoire était découpée en segments, dont certains avaient une résidence permanente sur disque (Multics).

D'autres systèmes d'exploitation ont été construits autour d'une base de données : chaque objet du système a sa place dans la base, tout objet de la base est connu du système (Pick). Le langage d'interrogation est le langage de commandes du système.

Le système de l'AS400 répond peu ou prou au même principe.

Un système persistant digne de ce nom ne saurait s'empêtrer d'un système de fichiers.

Recherches en persistance

Persistance orthogonale :

toute donnée doit pouvoir être rendue persistante aussi longtemps que de besoin ;
les moyens d'accès à chaque donnée doivent être indépendants de sa durée de vie, persistante ou transiente.

La notion de fichier disparaît. La persistance est un attribut parmi les autres, fourni à titre de service par le système d'exploitation.

Chaque donnée a un propriétaire, des droits d'accès, une protection.

Recherches en persistance (suite)

Le projet MONADS a démarré en 1976 à l'Université Monash (Australie). L'abstraction de base est le segment, à la Multics : persistance à gros grain.

Clouds vient du Georgia Institute of Technology (1988). Les abstractions sont l'objet et le thread. Micro-noyau Ra.

Eumel et son successeur L3 ont leur origine en 1979 au GMD (« Gesellschaft für Mathematik und Datenverarbeitung », équivalent allemand de l'INRIA). Premier système à persistance orthogonale.

Recherches en persistance (suite)

Grasshoper est un système à persistance orthogonale développé à l'Université de Saint Andrews, Écosse. Les entités persistantes sont des containers, des loci et des capabilities. Dans les systèmes classiques la notion d'espace--adresse est inextricablement mêlée à celle de processus. Les containers et les loci sont des entités analogues mais mieux distinguées (pardon : orthogonales), qui ont vocation à persister. Le noyau du système lui-même est persistant (il y a quand même toujours une partie non--persistante, ne serait-ce que pour le boot .

Recherches en persistance (suite)

Charm est le successeur de Grasshoper. Le noyau de Charm n'exporte aucune abstraction pour le support de la persistance, mais uniquement des domaines de protection capable de communiquer avec le noyau.

Charm appartient à une nouvelle tendance parmi les systèmes d'exploitation : au lieu de cacher le matériel derrière des abstractions, il l'expose afin que les stratégies de gestion des ressources soient implémentées en « mode utilisateur ». Cela suppose des dispositions favorables de l'architecture matérielle : en fait, le matériel n'exhibe qu'un TLB, le reste est fait en logiciel.

Le motif est de séparer :

les règles de gestion des ressources de bas niveau ;
des mécanismes qui les implémentent.

L'auteur du système de haut niveau est libre d'implémenter règles et mécanismes par une bibliothèque.

La notion de reprise sur point de contrôle est bien sûr au coeur de tous ces systèmes.

Références

[cattell-1997]: Cattell (Rick G. G.). -- Object Data Management. -- Reading, Massachusetts, Addison-Wesley, 1997.
[Dearle-2000]: Dearle (Alan) et Hulse (David). -- Operating system support for persistent systems: past, present and future. Software Practice and Experience, vol. 30, 2000, pp. 295--324.
[ostore]: eXcelon Corporation. -- ObjectStore. -- Rapport technique, Burlington, MA, USA, (disponible localement sur Nefertiti), 2000. file:/local/ostore/doc/index.htm/.
[spe]: Hosking (Antony) et Cutts (Quintin). -- Special issue: persistent object systems. Software Practice and Experience, vol. 30-4, 2000. -- http://www.interscience.wiley.com/.
[lindstrom]: Lindstrom (Gary). -- Gary Lindstrom's home page. -- Rapport technique, Rocquencourt, France, INRIA, 1998. http://www-sor.inria.fr/ lindstro/.
[gary]: Lindstrom (Gary). -- Gary Lindstrom's home page. -- Rapport technique, Salt Lake City, University of Utah, 2000. http://www.cs.utah.edu/ gary/home.html.
[Morrison-2000]: Morrison (Ron), Balasubramaniam (Dharini), Greenwood (Mark), Kirby (Graham), Mayes (Ken), Munro (Dave) et Warboys (Brian). -- A compliant persistent architecture. Software Practice and Experience, vol. 30, 2000, pp. 363--386.
[seq-rdb-merck-2000]: Xie (Guochun), DeMarco (Reynold), Blevins (Richard) et Wang (Yuhong). -- Storing biological sequence database in relational form. Bioinformatics, vol. 16, n-.25em.2ex 3, 2000, pp. 288--289.

Exemples de programmes

./../../Bases/Obj-Swiss/C_Src/read_os_db.cc

./../../Bases/Obj-Swiss/C_Src/insert_os_db.cc

./../../Bases/Obj-Swiss/C_Src/lecture-swiss.h

./../../Bases/Obj-Swiss/Nostore/lecture-swiss.scm

Ce document a été traduit de L^AT_EX par H^EV^EA.