Bases de données Forum

Sam Zoghaib Tahina Ramananandro

5 juin 2005

1 Principe

1.1 Définition

Un forum est un système de communication informatique où des utilisateurs lisent et postent des messages, lisibles par tous.

Les messages sont regroupés par thème, dans des groupes de discussion, ou en anglais newsgroups, ou, dans le jargon normalien, contis^{1}. Un message peut appartenir à plusieurs contis, mais doit appartenir à au moins l’un d’eux.

Mais les messages sont aussi organisés en arbres, grâce à une notion de père-fils, qui définit une thread^{2}, ou fil de discussion. Une thread peut s’étendre arbitrairement sur plusieurs contis.

En plus de la notion de père-fils, il existe une notion plus générale de référence d’un message à un autre (comme une bibliographie), assez rarement utilisée dans un autre usage que la relation père-fils. (Le père d’un message est le dernier message référencé par celui-ci).

1.2 Structure d’un message

Un message est constitué d’une en-tête^{3}, suivie du corps. L’en-tête définit le message par des attributs, ou champs, de la forme ATTRIBUT: valeur1, valeur2, ..., tandis que le contenu du corps est libre. Il existe un certain nombre d’attributs obligatoires, sachant que tous ceux commençant par X sont toujours facultatifs. Les principaux champs obligatoires sont :

– DATE : la date du message

– NEWSGROUPS : l’ensemble des contis auxquels appartient le message.

– FROM : le pseudonyme du posteur

– SENDER : l’identité «physique» du posteur

– SUBJECT : le sujet^{4} du message

– REFERENCES : l’ensemble des messages auxquels ce message fait référence ; la dernière référence est le père

du message. Le message est toujours identifié par un identifiant unique, le message-ID.

1.3 Exemples

Exemples d’en-têtes de messages (l’attribut DATE est omis), ainsi que l’organisation correspondante en termes de contis et threads :

1abrév. de continuum, c’est-à-dire ensemble de messages formant continuité de thème 2ou, selon certains, un thread 3Ou, selon certains, un en-tête 4A ne pas confondre avec un thème.

Message-Id: 18
NEWSGROUPS: foo, bar
FROM: zoghaib
SUBJECT: essai
REFERENCES:
Message-Id: 19
NEWSGROUPS: foo
FROM: ramanana
SUBJECT: truc
REFERENCES: 18
Message-Id: 20
NEWSGROUPS: foo
FROM: zoghaib
SUBJECT: machin
REFERENCES: 18, 19
Message-ID: 21
NEWSGROUPS: bar
FROM: ramanana
SUBJECT: test
REFERENCES: 18
Message-ID: 22
NEWSGROUPS: foo
FROM: zoghaib
SUBJECT: tu t'es trompé
REFERENCES: 19, 21

La figure n’est pas prête.

Attention, les contis préexistent aux messages (c’est-à-dire que le fait de poster un message contenant un nom de conti inconnu ne va pas automatiquement créer ledit conti).

1.4 Modération : déplacement, ou blast

Entre le post, tâche commune, et la création de contis, tâche d’administration, il existe une tâche intermédiaire, dite de modération, visant à contrôler l’appartenance de messages à des contis en fonction de leur contenu. Cette tâche est accomplie par des modérateurs. Elle se manifeste par le déplacement de certains messages d’un conti à un autre, déplacement que l’on appelle aussi blast car les messages incriminés disparaissent de leur conti d’origine.

On peut blaster :

– un message isolé, depuis un conti vers un autre

– un fil entier, mais connexe dans un même conti (c’est-à-dire que le fil est «coupé» dès que l’on trouve un message fils hors du conti considéré), vers un autre conti

Mais le blast requiert des permissions spéciales (tout le monde ne peut pas blaster).

– Le modérateur qui blaste doit avoir la permission de déplacer des messages depuis le conti source considéré.

– Il existe des contis qui sont en lecture seule, c’est-à-dire que l’on ne peut pas y poster. Un modérateur de ce conti peut toujours déplacer des messages depuis ce conti, mais n’a pas toujours le droit d’en faire un conti cible de blasts.

Prenons un exemple. Plaçons-nous dans la situation précédente, et supposons que l’on ait un troisième conti, schmilblick. Supposons que foo soit en lecture seule. Soient les deux modérateurs suivants :

                Modérateur foo                     bar   schmilblick

Alice  Oui, en lecture seule  Oui Non
Bob  Oui, en lecture et écriture Non Non

Dans ces conditions, Alice peut déplacer le message 22 de bar vers schmilblick, mais pas vers foo car il est en lecture seule. Ce que peut faire Bob, en revanche.

Toutefois, Alice, modératrice de foo, peut, comme Bob, déplacer le message 18 de foo vers bar, même si Alice n’a pas le droit d’écriture sur foo car ce droit ne s’applique que si le conti est la destination d’un blast.

Alice et Bob, modérateurs de foo, peuvent choisir de déplacer tout le fil de foo issu de 18, qui comprendra donc les messages 18, 19 et 20, mais pas 22 car son père, 21, n’est pas dans foo.

Important

Lorsqu’un message est déplacé d’un conti vers un autre, son Message-ID change.

C’est une convention utilisée dans certains forums, comme celui des élèves de l’ENS, considérant qu’un message, déplacé, n’est plus le même message (en particulier si le Message-ID est un hash du contenu du message, en-tête et corps compris).

2 Modélisation en termes de bases de données

2.1 Schéma entité-association

La figure n’est pas prête.

2.2 Tables

Nous avons choisi de stocker le corps des messages dans des fichiers, et non dans la base de données. C’est ce que l’on appelle le spool.

Le code SQL de création des tables est donné ci-dessous :

create  table  contis (
nom  text  primary key,
description  text,
lecture_seule  boolean  default  'f' not null,
prochain_numero  integer  default 0 not  null

);

create  table  droits (
moderateur  text  not null,
conti  text  foreign  key  contis  references  nom,
ecrire  boolean,
unique (moderateur,conti)

);

create  table  messages (
id text  primary key,
pere text,
fils text,
subject  text  not null,
sender  text  not null,
"from" text  not null,
date text,
numero_fichier  integer  default 0 not  null

);

create  table  messages_contis (
message  text  not null,
conti  text  foreign  key  contis  references  nom,
numero  integer  not null,
unique (message, conti),
primary  key (conti, numero)

);

create  table  refs (
       de text  not null,
       a text  not null,
       unique (de, a)

);

La table contis définit les contis. L’attribut prochain_numero définit le numéro du prochain message qui appartiendra à ce conti (car outre par son Message-ID, on peut aussi accéder à un message par un conti auquel il appartient, et le numéro au sein de ce conti, défini dans l’attribut numero de la table messages_contis).

La table droits définit les modérateurs.

La table messages définit les messages. L’attribut pere contient le Message-ID du père, ou NULL si le message n’a pas de père.

L’attribut fils contient les Message-ID des fils du message, séparés par des virgules, mais n’est pas utilisé

en pratique (un select id from messages where pere = 'id_du_pere' fait l’affaire).

L’attribut numero_fichier permet d’accéder au fichier spool correspondant au message (c’est le fichier qui contient le corps du message), dont le nom est id.numero_fichier.

La table messages_contis définit les appartenances de messages à des contis (on rappelle qu’un message peut appartenir à plusieurs contis). Comme un Message-ID peut changer, il n’est pas question d’intégrer ici pour l’attribut message une clé étrangère référençant messages.id, tout comme pour les attributs de et a de la table refs. C’est dans cette table qu’est défini le numéro d’un message au sein d’un conti (attribut numero). Cependant dans tous les contis auxquels il appartient, le message conserve son unique Message-ID.

Les tables sont utilisées :

– par le programme, pour le post et la modération

– directement, pour l’administration (création de contis et déclaration de modérateurs).

2.3 Instructions SQL pour l’administration

La création d’un conti se fait directement via l’instruction SQL suivante :

– si le conti est en lecture seule :

       insert  into  contis(nom, lecture_seule) values( 'nom_du_conti', 't' );

– sinon, au choix :

       insert  into  contis(nom) values( 'nom_du_conti' );
       insert  into  contis(nom, lecture_seule) values( 'nom_du_conti', 'f' );

Un modérateur est ajouté également directement, par insertion de valeurs, sur le modèle de la création de conti.

– si le conti n’est pas en lecture seule

  insert  into  droits(moderateur, conti)
          values( 'nom_du_moderateur', 'nom_du_conti' )

– si le conti est en lecture seule mais que l’on souhaite cependant que le modérateur ait le droit de déplacer des messages depuis et vers ce conti, on utilise au choix :

  insert  into  droits(moderateur, conti)
          values( 'nom_du_moderateur', 'nom_du_conti' )
  insert  into  droits(moderateur, conti, ecrire)
          values( 'nom_du_moderateur', 'nom_du_conti', 't' )

– si le conti est en lecture seule mais que l’on souhaite cependant que le modérateur ait le droit de déplacer des messages uniquement depuis ce conti :

  insert  into  droits(moderateur, conti, ecrire)
          values( 'nom_du_moderateur', 'nom_du_conti', 'f' )

3 Le programme

Le programme a été écrit en C, avec la librairie libpq pour l’accès à la base de données PostgreSQL. C’est le module base.c qui concerne les bases de données et le fonctionnement du forum, tandis que server.c contient les fonctionnalités réseau, permettant une utilisation plus ou moins «pratique» du programme.

3.1 Post

Le programme commence par générer des fragments de requêtes :

1. génère le Message-ID du message

2. vérifie, pour chaque message référencé, s’il existe, en exécutant^{5} :

       select * from  messages  where  id = '...'

et génère la requête d’insertion correspondante dans la table des références :

       insert  into  refs(de,a)
          values('nouveau_message','message_reference')

3. vérifie, pour chaque conti, s’il existe et s’il n’est pas en lecture seule, en exécutant :

       select * from  contis  where  id = '...' and  lecture_seule = 'f'

et génère la requête d’insertion correspondante, avec l’incrément du numéro du prochain message :

       insert  into  messages_contis (message,conti,numero) values (
          '...', '...',
          (select  prochain_numero  from  contis  where  nom = '...' )

       );

       update  contis  set  prochain_numero  = 1 +  prochain_numero
          where  nom = '...';

Si aucun conti ne convient, la création du message est annulée.

4. Sinon, le programme crée le fichier spool (contenant le corps du message), et génère la requête de création

  du message (insert into messages...).

Enfin, les différents fragments de requêtes générés sont remis dans l’ordre :

1. insertion du message

2. insertion des références

3. insertion dans les contis puis exécutés au sein d’une même transaction, avec un verrou :

lock  contis  in row  exclusive  mode

au préalable pour éviter les conflits au niveau de l’incrémentation du compteur prochain_numero.

3.2 Déplacement d’un message

Lorsqu’un modérateur souhaite déplacer un message, le programme commence par vérifier si ce modérateur :

– est modérateur du conti source :

   select * from  droits  where  moderateur = '...' and  conti = '...';

– a les droits d’écriture sur le conti cible s’il est en lecture seule :

   select * from  contis,droits
     where  conti.nom = '...' and (
       conti.lecture_seule = 'f'
       or (
          droits.conti = conti.nom
          and  droits.moderateur = '...'

5La vérification consiste à compter le nombre de lignes renvoyées par l’exécution d’une telle requête. Si aucune ligne n’est renvoyée, la vérification échoue.

       and  droits.ecrire = 't'

     )
  )

(Si le conti n’est pas en lecture seule, cette requête, exécutée, renvoie toute la table droits jointe à la ligne de contis définissant le conti cible)

Si le modérateur passe ces vérifications avec succès, alors le message peut être déplacé. Le programme :

1. copie le fichier spool pour y mettre à jour l’en-tête NEWSGROUPS

2. supprime la ligne de messages_contis liant le message au conti source :

   delete  from  messages_contis
     where  message = 'id' and  conti = 'conti_source'

3. vérifie si le message est déjà présent dans le conti cible :

   select * from  messages_contis
     where  message = 'id' and  conti = 'conti_cible'

Si c’est le cas, le programme se contente d’incrémenter le compteur numero_fichier pour prendre en compte la copie du fichier spool, sans modifier le Message-ID, et la procédure est terminée :

   update  messages  set  numero_fichier  = 1 +  numero_fichier
     where  message = 'id'

4. Si le message est absent du conti cible, alors il faut changer son Message-ID. Le programme génère alors un nouvel ID et renomme alors la copie du fichier spool dans ce sens,

5. sélectionne tous les messages faisant référence au message à déplacer :

   select  de from  refs  where a = 'ancien_id'

puis pour chacun d’eux, crée une copie du fichier spool pour y mettre à jour l’en-tête REFERENCES:, et incrémente alors, comme ci-avant, le compteur numero_fichier (dans la table messages)

6. détecte l’éventuelle présence d’un père (en deux temps, vérifie d’abord si pere contient un Message-ID valide, puis teste l’existence du message), pour mettre à jour l’attribut fils correspondant dans messages (attribut qui n’est pourtant pas utilisé outre mesure : cette étape pourrait donc très bien être ignorée et l’attribut fils supprimé dans les définitions des tables)

7. remplace alors par le nouvel ID toutes les occurrences de l’ancien parmi les fils (dans l’attribut pere de messages), ainsi que dans les attributs de et a de refs :

   update  messages  set  pere = 'nouvel_id' where  pere = 'ancien_id';
   update  refs  set de = 'nouvel_id' where  de = 'ancien_id';
   update  refs  set a = 'nouvel_id' where a = 'ancien_id';

8. modifie la ligne de définition du message dans messages, pour prendre en compte le nouvel ID :

   update  messages  set id = 'nouvel_id', numero_fichier  = 0
     where  id = 'ancien_id'

9. et enfin, signale l’appartenance du message au conti cible :

   insert  into  messages_contis(message, conti, numero) values(
     'nouvel_id', 'cible', (
       select  prochain_numero  from  contis  where  nom = 'cible'

     )
   );

   update  contis  set  prochain_numero  = 1 +  prochain_numero
     where  nom = 'cible'

Notons que toutes ces requêtes sont exécutées dans une même transaction, avec au préalable des verrous amplement suffisants comme :

lock refs,messages,messages_contis  in  exclusive  mode;
lock  contis  in row  exclusive  mode;

Ceci empêche le post de messages pendant l’opération de blast. En particulier, la réponse (par référence) à un message en train d’être déplacé (problème très désagréable en pratique : fils de discussion interrompus).

3.3 Déplacement d’un fil

On rappelle que, dans un fil, ne sont déplacés que :

– la racine, si elle appartient au conti source

– les messages appartenant au conti source et dont le père appartient au conti source

Avant toute chose, les vérifications des droits du modérateur sont effectuées une fois pour toutes.

Puis, une transaction unique est créée pour le déplacement de tout le fil. Le programme s’exécute alors récursivement, avec pour cas de base la racine du fil à déplacer :

1. Le programme déplace d’abord le message considéré du conti source vers le conti cible.

2. Puis, le programme cherche tous ses fils qui sont dans le conti source :

       select  messages.id from  messages,messages_contis
          where  messages.id = messages_contis.message
          and  messages.pere = 'nouvel_id_du_pere'
          and  messages_contis.contis = 'conti_source'

3. Puis, le programme déplace (récursivement, donc) le fil de discussion issu de chacun de ces messages, mais toujours depuis le même conti source, vers le même conti cible.

3.4 Utilisation du programme

Le programme est un serveur TCP qui écoute sur le port n^{∘}12755. On interagit donc avec lui grâce à un programme de communication réseau, typiquement telnet^{6}. Nous préconisons de travailler dans un environnement FreeBSD.

Avant de compiler le programme, il faut modifier les lignes de serv.h :

#define  SPOOLPATH "chemin_de_spool"
#define  PGCONN "host=hote_postgre␣dbname=base_de_donnees"

afin de spécifier le répertoire (à créer au préalable) où les fichiers spool seront créés, ainsi que les coordonnées de la base de données PostgreSQL contenant les tables (que l’on aura créées au préalable grâce aux instructions SQL du 2.2).

Les sources base.c, server.c, serv.h se compilent alors sous FreeBSD avec la librairie libpq :

gcc -o base -I`pg_config --includedir` -L`pg_config --libdir` -lpq
    base.c server.c

Une fois compilé, le programme base peut être lancé. Il n’admet pas d’entrée utilisateur, mais il écoute sur le port n^{∘}12755 et il peut afficher des messages décrivant son activité (en particulier les principales requêtes exécutées). Pour interagir avec base, il est donc nécessaire d’ouvrir telnet dans un autre terminal (ou carrément sur une autre machine, qui elle, peut vivre sous n’importe quel système d’exploitation pourvu de telnet) :

telnet  machine_ou_on_a_lance_base  12755

Le serveur répond alors :

Hey, how's it going ?

où l’on doit alors entrer helo utilisateur, sur quoi l’on reçoit le message :

Nice to meet you.

Là, on peut exécuter les commandes suivantes :

6Ne pas utiliser netcat dont les conventions de fin de ligne (\n) ne respectent pas les standards de communication TCP (\r\n).

BLST messageid, source, cible Déplace un message isolé. Attention à l’espace après chaque virgule.

BLTHR messageid, source, cible Déplace le fil de discussion de source dont la racine est messageid. Attention à l’espace après chaque virgule.

GET message_id Affiche le contenu du fichier spool du message dont l’ID est indiqué.

GETID conti, numero Affiche le Message-ID correspondant au message indiqué par son conti et son numéro au sein du conti. Attention, bien respecter l’espace après la virgule.

LIST conti Affiche la liste des messages (numéro et message-ID) dans le conti spécifié.

LSTNGS  Affiche la liste des contis.

POST Poste un message. Sur les lignes suivantes, il faudra indiquer successivement et dans l’ordre, les champs

NEWSGROUPS, FROM, SUBJECT et REFERENCES, sous la forme
ATTRIBUT:<espace><contenu> (en plaçant aussi une es-

pace après chaque virgule, si l’on indique plusieurs newsgroups ou plusieurs références). Ensuite, on pourra spécifier le corps du message, sur une ou plusieurs lignes, en terminant par une ligne blanche puis par une ligne ne contenant qu’un point.

QUIT  Coupe la connexion au serveur.

Notre choix d’avoir écrit un serveur permet en fait l’exécution de requêtes en parallèle depuis plusieurs machines, dans les conditions réelles d’utilisation d’un forum. On peut imaginer ce qui peut se passer si le répertoire de spool est situé sur une disquette (ou tout autre périphérique de stockage lent), par exemple.

Pour fermer le serveur, on revient là où on l’a lancé et on fait la combinaison de touches Ctrl+C.