I. Introduction▲
Cet article est le second de la série sur la création d’un triplestore dans la perspective d’une gestion grâce à la norme RDF pour la gestion des connaissances.
Nous y trouverons notamment les réflexions et une série de tests sur l’organisation des données au sein d’un fichier – binaire, forcément – et comment la représentation de l’information joue sur notre propre perception d’un moteur de base et dans la programmation.
Il s’arrêtera sur une proposition fonctionnelle d’un service triplestore. Mais tout d’abord un long travail de préparation nous attend…
II. Un petit outil de conception de requêtes HTTP▲
Rapidement, il peut devenir pénible de taper à la main les requêtes de test, sans un minimum de confort. Une fois que le service de triplestore sera opérationnel, ce sera même frustrant ! Il serait plus aisé que notre base fournisse ses propres instruments. Et c’est (facilement) possible ! Comme nous l’avions vu dans la première partie, les chemins de chaque requête sont testés afin de permettre des exceptions – des requêtes qui ne concernent pas directement le silo.
Dans le fichier page.html créé précédemment, ajouter le code suivant :
Vous aurez désormais un outil minimal mais opérationnel pour éditer des requêtes simples. L’appel à l’URL http://127.0.0.1:888/page permet d’y accéder lorsque le serveur est lancé.
Le fonctionnement est simple : les éléments du formulaire fourni préparent une requête via la technologie AJAX, et l’envoi au serveur. Le retour est affiché, quel qu’il soit.
Il peut être utile d’avoir une forme – plus que basique certes – d’éditeur dans un contexte REST.
Attention tout de même : tous les navigateurs ne gèrent pas à l’identique la technologie AJAX – particulièrement le traitement de certains entêtes. Ainsi sous Firefox, inutile d’indiquer une taille du contenu, le navigateur s’en charge et n’enverra pas de corps si le protocole HTTP n’en prévoit pas (cas de GET notamment).
III. Gérer des données au-delà de la communication▲
III-A. La manière d’écrire (et pas seulement de s’écrire !)▲
Il est primordial de s’accorder, lors de la conception d’un outil, sur les modalités de l’échange. Évidemment, une grande part repose sur HTTP : mais il s’agit là du transport pour la partie « réseau ». Or le transport n’agit pas directement sur le contenu envoyé (même s’il y a des transformations : la source, l’origine, doit être retrouvée au moment de l’analyse).
En réalité, une fois la partie transport résolue, le problème de communication reste entier. Il s’agit maintenant de concevoir ce que le client doit envoyer pour être compris et ce qu’il recevra en retour – gardez à l’esprit qu’il s’agit là de la « charge utile » pour le client comme pour le serveur, peu importe la modalité de transmission. Nous quittons la sphère HTTP pour celle du cœur de la programmation – ce qui correspondrait, en quelque sorte, à notre langage de requête.
Un triplet, comme je l’expliquais en introduction de la série d’articles, est une base de trois données fondamentales, sous la forme d’une chaîne de caractères – c’est en tout cas ce que notre triplestore acceptera. Le format général est donc le suivant :
texte( Sujet ) texte( Prédicat ) texte( Objet )
Il est plutôt embêtant de ne gérer s’il n’y a qu’un seul triplet à la fois – souvent ils sont très courts, comme nous le verrons dans le dernier article, grâce à l’utilisation des préfixes et d’URI.
Alors notre triplestore comprendra – et renverra – possiblement 0, 1 ou n triplets à chaque requête, et sans réelle limite du nombre de triplets. Ces triplets se présenteront sous la forme d’un triplet par ligne, chaque partie du triplet étant séparée par un caractère de tabulation. Bref : nous utiliserons un format qui ressemble bigrement au TSV – une des alternatives du CSV.
Chaque ligne d’un corps de requête devra pouvoir répondre précisément à cette expression régulière :
^(
?P<
subject>
[^
\t]+
)\t
(
?P<
predicate>
[^
\t]+
)\t
(
?P<
object>
[^
\t]+
)$
Enfin, pour les transactions d’insertion de nouveaux triplets, si une ligne est invalide, l’ensemble de la transaction est invalide : soit la transaction est entièrement cohérente (code HTTP 200), soit elle ne doit pas être exécutée (code HTTP 400).
Il y a un avantage à ce format : pouvoir analyser au fur et à mesure de la récupération d’un corps de requête par exemple, des triplets - sans à avoir à charger en une fois l’ensemble de la chaîne. Si une des lignes est invalide, il n’est pas nécessaire de récupérer et traiter le reste du corps de la requête !
Voici un exemple d’un corps de requête qui serait analysé au fur et à mesure :
Le retour valide est :
requête valide : [{'subject'
: '<http://example.org/arnaud#me>'
, 'predicate'
: '<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>'
, 'object'
: '<http://xmlns.com/foaf/0.1/Person>'
}, {'subject'
: '<http://example.org/arnaud#me>'
, 'predicate'
: '<http://xmlns.com/foaf/0.1/knows>'
, 'object'
: '<http://example.org/béatrice#me>'
}, {'subject'
: '<http://example.org/arnaud#me>'
, 'predicate'
: '<http://schema.org/birthDate>'
, 'object'
: '"1990-07-14"^^<http://www.w3.org/2001/XMLSchema#date>'
}, {'subject'
: '<http://example.org/arnaud#me>'
, 'predicate'
: '<http://xmlns.com/foaf/0.1/topic_interest>'
, 'object'
: '<http://www.wikidata.org/entity/Q12418>'
}, {'subject'
: '<http://www.wikidata.org/entity/Q12418>'
, 'predicate'
: '<http://purl.org/dc/terms/title>'
, 'object'
: '"La Joconde"'
}, {'subject'
: '<http://www.wikidata.org/entity/Q12418>'
, 'predicate'
: '<http://purl.org/dc/terms/creator>'
, 'object'
: '<http://fr.dbpedia.org/resource/Léonard_de_Vinci>'
}, {'subject'
: '<http://data.europeana.eu/item/04802/243FA8618938F4117025F17A8B813C5F9AA4D619>'
, 'predicate'
: '<http://purl.org/dc/terms/subject>'
, 'object'
: '<http://www.wikidata.org/entity/Q12418>'
}]
... poursuivre ...
Et le retour invalide est radical (le reste de la chaîne n’est pas traitée) :
requête invalide
... poursuivre ...
III-B. Quel type choisir ?▲
Le stockage des données n’est pas seulement propre au stockage en lui-même dans la base de données, ou encore la manière dont on communique (transport et commande). Le stockage est aussi en RAM, lors des calculs et des opérations de lecture/écriture.
Pour ce dernier point, « stockage » est mal usité : il s’agit plutôt de mémoire – et à court terme, car le moindre arrêt du programme ou du serveur, sauf l’utilisation d’images et de certains systèmes virtuels, provoquera la perte de la donnée.
La mémorisation donc, est une question de performance, mais aussi de lisibilité et de style. Trois solutions s’offrent à vous :
- l’utilisation d’une classe, par exemple avec une instance par enregistrement, qui permet d’avoir une sorte de « super enregistrement » qui contiendrait en plus d’informations, des méthodes propres et éventuellement des contrôles. La lisibilité est idéale et, de plus, la surcharge de __getitem__ et __putitem__ permet un contrôle des données écrites ;
- l’utilisation d’un dictionnaire, avec un bon vieux système clé/valeur. La clé peut être du texte, et c’est utile pour la lisibilité, mais il y a clairement une différence sur la gestion des méthodes – l’évolution pour le développeur n’est pas aisée. Par contre, c’est un compromis idéal entre un indice non-numérique et l’utilisation des objets ;
- l’utilisation d’une liste : plus de clé en texte, seulement des indices numériques. Et contrairement à un dictionnaire, une liste se réorganise. C’est-à-dire que si un petit malin dans votre programme s’amuse à faire un tri sur une liste et que l’ordre était important (lien entre un indice et une clé stockée autrement), vous ne perdez pas les données, mais vous ne savez pas à quoi correspond le nouvel indice. Passons rapidement donc ce type qui ne nous intéresse pas ici ;
- l’utilisation d’un tuple – une liste « figée » ) en quelque sorte. Le terme technique retenu est immuable et résume à la fois sa faiblesse mais sa grande force : elle n’évolue pas. Ce qui ne veut pas dire qu’elle ne dispose pas de fonctions, mais celle-ci ne fournit que l’accès aux données triées.
Vous pouvez avoir des tuples « nommés » se rapprochant d’un dictionnaire, avec le module Collections et la fonction namedtuple. Cependant, cela ne nous intéressera pas ici. J’ai mis aussi de côté les set.
Dans votre IDLE préféré, copiez-collez le code suivant :
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
import
datetime
nbre =
1000000
debut =
datetime.datetime.now
(
)
for
i in
range(
0
, nbre ):
class
A:
sujet =
0
predicat =
1
objet =
2
a =
A
(
)
b =
a.predicat
fin =
datetime.datetime.now
(
)
print
(
"object :"
, fin-
debut )
debut =
datetime.datetime.now
(
)
for
i in
range(
0
, nbre ):
a =
{ "sujet"
: 0
, "predicat"
: 1
, "objet"
: 2
}
b =
a["predicat"
]
fin =
datetime.datetime.now
(
)
print
(
"dict :"
, fin-
debut )
debut =
datetime.datetime.now
(
)
for
i in
range(
0
, nbre ):
a =
[ 0
, 1
, 2
]
b =
a[1
]
fin =
datetime.datetime.now
(
)
print
(
"list :"
, fin-
debut )
debut =
datetime.datetime.now
(
)
for
i in
range(
0
, nbre ):
a =
(
0
, 1
, 2
)
b =
a[1
]
fin =
datetime.datetime.now
(
)
print
(
"tuple :"
, fin-
debut )
… Il représente pour chaque type évoqué au-dessus, un million d’itérations de création et d’un accès. J’ai mis le nom des parties d’un triplet (sujet, prédicat, objet). Lancez l’exécution et constatez que le résultat est sans appel :
object : 0:00:08.982256
dict : 0:00:00.417122
list : 0:00:00.249939
tuple : 0:00:00.156250
Les objets dans ce contexte sont hors de propos : et comme nous passerons notre temps à lire des portions de l’index et du contenu, pour des questions de tri et d’extraction, sa lenteur ne nous convient pas. Pour autant, s’il y a de nombreux traitements à faire derrière, le choix de l’objet pour sa praticité et sa souplesse (héritage, surcharge, etc.) n’est pas à ignorer.
Il reste les dictionnaires, qui offrent le meilleur compromis temps/lisibilité. Loin, certes, des tuples mais après tout, le sacrifice de la performance pour garder un code digeste parfois…
III-C. Quel type choisir (bis) ? ▲
En se creusant les méninges, il reste cependant une solution : un ensemble de tuples – un peu comme en LISP.
Ainsi nous gardons la performance des tuples, mais aussi un (relatif) confort avec des accès par chaîne de caractères.
En somme, avoir le meilleur des deux. Testons ce scénario :
Aïe ! Les résultats ne sont pas au rendez-vous :
tuple-complexe : 0:00:00.577991
dict : 0:00:00.328054
Ce qui est finalement logique, car l’on utilise une fonction au sein de la fonction : index, afin de retrouver l’indice numérique à utiliser sur le triplet. Pour le dictionnaire, tout cela est « caché » par le haut niveau de programmation utilisé en Python, de manière performante.
Cependant, ce constat est vrai si nous prenons un triplet en individuel. Ramener cela à une liste – par exemple extraire plusieurs triplets -, et la situation change assez radicalement en utilisant à chaque fois des « listes en intention » :
Le retour de la console ne se fait pas attendre :
[1, 1, 1]
tuple-complexe : 0:00:01.843313
dict : 0:00:02.655625
L’utilisation d’un type est donc liée à un contexte et pas – du tout – à ses qualités propres !
Pour autant, nous utilisons dans notre code les dictionnaires, moins performants, mais plus lisibles.
IV. Bytes : ce n’est pas qu’une question de taille▲
Durant cet article, nous allons beaucoup, beaucoup utiliser des nombres et de la « représentation » de texte au format binaire. En réalité, techniquement, c’est l’inverse : ce que vous voyez à l’écran lorsqu’il s’agit de texte au format « Bytes » n’est pas du texte mais sa représentation (et Bytearray est tel Bytes mais mutable, c’est-à-dire modifiable après création).
Compliqué à suivre ? Pas vraiment, comme nous l’apprend l’IDLE :
Et pour en rajouter une couche :
>>>
texte =
b"a"
>>>
chr(
int(
bin
(
ord(
texte ) ), 2
) ).encode
(
"utf-8"
) ==
texte
True
Vous n’avez rien suivi : c’est normal. Une même information - la lettre « a » de type str en Python, la variable bytes b"a" et le chiffre 97 – est représentée différemment. Du moins ce que l’humain en comprend. Mais en programmation, ce n’est pas la même chose. Pas du tout : c’est un problème.
Tentons de résumer – les puristes me pardonneront les imprécisions :
- 97 en Python est un entier (un int) ;
- le nombre 97 dans la table d’encodage UTF-8 est le signe « a » ;
- l’UTF-8 en Python est de type bytes ;
- la lettre « a » en Python est une string.
Ainsi, je peux avoir un entier et je m’en sers pour d’indice dans une table d’encodage pour obtenir un signe. Ce signe, je peux tenter de le transformer en chaîne de caractères au sein de Python. Puis refaire la chaîne inverse.
La bonne nouvelle, c’est que ça permet des trucs rigolos :
IV-A. La taille, toujours…▲
C’est rigolo, mais ça conduit à des erreurs parfois, si l’on ne prend pas garde à quelques précautions.
Cela permet surtout, parfois, de réduire la taille occupée par une information – attention, je parle bien d’information et non de la donnée utilisée par la machine.
Par exemple, la valeur 12 équivaut à « 12 » en entier chez Python, à « 0xc » en hexadécimal et à « 0b1100 » en binaire.
Si l’on compare la « charge utile » de ces représentations, nous avons donc en termes de signes utilisés :
- (entier) 12 → 2
- (hexadécimal) c → 1
- (binaire) 1100 → 4
Ainsi stocker dans un fichier la valeur 12, prend plus ou moins de place suivant sous quelle forme on le stocke. Mais c’est parce que vous êtes humain ! Pour la machine, la place est rigoureusement la même…
2.
3.
4.
5.
6.
>>>
bin
(
12
) # pour la démonstration
'0b1100'
>>>
bin
(
ord(
"c"
) ) # = 99
'0b1100011'
>>>
"0b1100"
# identique évidemment, à l’entier 12
'0b1100'
Vous allez me dire : c’est n’importe quoi ton truc, l’hexadécimal prend 7 bits et les deux autres sont identiques avec 4 bits ! Certes. Mais ramener à un octet et non pas aux seuls bits nécessaires, en remplissant de 0 les bits manquants, la taille occupée est rigoureusement la même : '0b00001100' ou 0b01100011' sont équivalents à 1 octet.
Si l’on prend des valeurs plus élevées, on comprend rapidement la différence et combien cette problématique de « représentation » est importante :
Ainsi une représentation d’une même information – ici un nombre très élevé, peu importe sa valeur exacte – peut sembler être moins importante en version hexadécimale (32 signes) au lieu d’un entier (39 signes). Cependant, la représentation « réelle » pour le programme, au niveau machine, est qu’une chaîne de caractères pour représenter un nombre sera toujours plus imposant en taille.
La conclusion de cette partie, c’est qu’il est préférable en termes d’efficience de stocker et garder en mémoire des nombres que des chaînes, et ne pas se fier simplement à un comptage « bête et méchant » des signes qui représente l’information, car souvent, nous sommes sur une représentation de cette information.
IV-B. Bytes : ne pas être confus mais efficace▲
Tout cela peut vous sembler peu pertinent, c’est pourquoi nous en arrivons à l’essence même : passer de la mémoire (RAM) au stockage (DD sous toutes ses formes).
Dans les deux cas, c’est le binaire qui est utilisé et pour cette série d’articles, nous travaillerons toujours sur la base d’un octet – c’est-à-dire 8 bits qui doivent être ensemble dans un certain ordre pour former l’information d’origine.
Le problème comme nous l’avons vu, c’est qu’une machine ne fait jamais que stocker et traiter des nombres – enfin quelque chose qui s’en approche pour elle. Là où des caractères s’affichent, c’est grâce à une convention – l’encodage. D’où l’usage de fonctions comme « ord » ou « chr » qui font le lien entre valeur et représentation attendue.
Lorsque vous êtes en train de travailler sur une information en RAM, celle-ci est connue, repérée, bornée. Sur Python, lorsque vous accédez à la variable « toto », vous ne vous occupez pas de savoir où elle est stockée : l’interpréteur s’en charge pour vous.
Dans un fichier « texte », lorsqu’il est lu, ce dernier récupère en réalité une valeur – un nombre sous forme octale – avec une correspondance. D’où l’usage fréquent de :
open(
mon_fichier, "r"
, encoding=
"utf-8"
)
… Vous indiquez que vous aller lire « signe par signe » (en réalité bloc par bloc, ici un bloc étant un octet) en fonction d’un certain encodage. Vous auriez pu aussi écrire :
open(
mon_fichier, "rb"
)
… Alors la lecture vous aurait retourné la même valeur – le contenu du fichier ne change pas – mais la représentation n’est pas la même ».
Dans un logiciel de bloc-notes (Notepad++ ou autre), écrivez une phrase et enregistrez le fichier. Par défaut, la plupart utilisent l’UTF-8 justement – cela nous ira très bien. Puis exécutez le code suivant pour y accéder :
Surprise : la même fonction ne retourne pas le même type d’accès !
<
class
'_io.TextIOWrapper'
>
<
class
'_io.BufferedReader'
>
À la lecture, logiquement, vous n’avez pas le même retour – quand bien même vous avez exécuté a priori la même fonction de lecture :
… retourne dans mon cas…
ceci est un texte
b'ceci est un texte'
Là encore, méfiez-vous : dans les deux cas, vous avez une représentation certes, nous l’avons déjà vu. Des représentations qui ne sont pas de même nature pour notre langage de serpent préféré. Mais cela va plus loin : Python et son interpréteur ne savent absolument pas « détecter » naturellement des portions ou des parties dans un fichier. Les sauts de lignes, les tabulations, etc. ne sont jamais que d’autres valeurs numériques auxquelles ont été fixés des signes d’imprimerie et qui permettent un affichage « humain ».
Rien dans le texte que le code retourne, n’est en réalité autre chose qu’une valeur numérique au format octal (j’insiste : RIEN) :
… retourne…
[99
, 101
, 99
, 105
, 32
, 101
, 115
, 116
, 32
, 117
, 110
, 32
, 116
, 101
, 120
, 116
, 101
]
Et sans surprise :
>>>
[ i for
i in
b'ceci est un texte'
]
[99
, 101
, 99
, 105
, 32
, 101
, 115
, 116
, 32
, 117
, 110
, 32
, 116
, 101
, 120
, 116
, 101
]
Le présupposé, c’est donc que la chaîne binaire proposée repose sur un encodage UTF-8 dans les deux cas. Bingo :
Vous aurez compris que chr( 32 ) retournerait un espace et chr( 101 ) un « e » !
Mais alors comment distinguer des parties dans ce qui revient à être une chaîne de nombres ? Deux solutions :
- celle, lisible, par l’être humain : par exemple le CSV. Vos séparateurs sont certains signes non-échappés, que le parseur va comprendre, car il traite la représentation qui lui est adressée. Dans le même esprit, avec plus de raffinement, vous avez XML ou JSON… pour récupérer une partie dans un contenu plus large, il faut donc « comprendre » le fichier par le système, ce qui est long et coûteux en ressources pour la machine ;
- utiliser un plan de données, c’est-à-dire une organisation qui ne se préoccupe pas de confondre le contenu avec l’organisation du contenu. C’est un avantage mais cela demande une grande justesse – et toute erreur fut-elle minime, peut « corrompre » un fichier et le rendre inexploitable.
Pour le stockage de nos triplets, nous allons utiliser la seconde solution.
IV-C. La carte aux trésors et des bits en plus des bytes▲
Dans les prochains exemples, nous utiliserons des « fichiers virtuels », c’est-à-dire des objets qui se comportent comme des fichiers réguliers mais qui sont en réalité en RAM – pour des questions de praticité.
Un fichier vu par Python et bien d’autres langages de programmation, c’est avant tout une suite de valeurs numériques que l’on parcourt – parfois dans un sens – et parfois que l’on modifie. Comme un curseur dans un éditeur de texte, la position retourne la valeur à venir (c’est-à-dire qu’elle n’est pas lue). Cela se révèle pratique : une valeur numérique peut donc être stockée et représenter la taille du contenu à suivre. En somme, quelque chose qui se comporte ainsi :
Et là miracle, notre fichier est structuré et l’organisation ne se confond pas avec le contenu lors de la récupération :
contenu du fichier : b"
\x1a
wahou c'est trop cool ! :)"
contenu de la variable : wahou c'est trop cool ! :)
Par contre, il y a des limites : la taille, codée sur des octets, précède toujours le contenu. Et il faut pouvoir savoir quand s’arrête la définition de la taille, du début du contenu.
Ainsi un octet a une valeur de 0 (pas de contenu) à 255 : soit un contenu de 255 « valeurs » ou octets, soit autant de signes possibles. Pour 2 octets par contre… la magie du binaire augmente fortement ce chiffre ! À 65 535 très précisément – soit 65 Ko. Pour trois octets, 16,7 Mo…
Voici une petite fonction personnelle pour vous aider :
2.
3.
4.
>>>
def
taillePossible
(
i):
return
int(
"0b"
+(
"1"
*
8
*
i), 2
)
>>>
print
(
taillePossible
(
8
) )
18446744073709551615
Vous aurez noté que pour 8 octets, on peut stocker une taille de contenu de 18 446 pétaoctets…
Vous pouvez également avoir une version améliorée, très utilisée pour les Web Sockets par exempleet qui permet de ne pas savoir à l’avance la taille en octets du nombre à récupérer. Il faut jouer sur le bit le plus fort (celui utilisé pour stocker le signe du nombre, positif ou négatif) qui devient une sorte de consigne pour continuer ou arrêter la lecture du prochain octet comme faisant partie du nombre en cours.
Ce qui tombe bien, c’est que pour Python, un entier est en soi une représentation d’un octet valable (ou plusieurs si l’entier est grand, négatif…). C’est-à-dire que l’on applique les opérations booléennes à un entier – et voir le résultat se transformer. Ce qui veut dire que les opérations s’appliquent entre deux entiers via les bits qui sont concernés.
petit rappel avant tout : pour 8 bits, la plage de valeurs par bit est 1 ; 2 ; 4 ; 8 ; 16 ; 32 ; 64 ; et enfin 128. Soit un total de 255 == 1+2+4+8+16+32+64+128.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
>>>
0
^
128
# ou
128
>>>
128
^
64
192
>>>
bin
(
0
)
'0b0'
>>>
bin
(
128
)
'0b10000000'
>>>
bin
(
64
)
'0b1000000'
>>>
bin
(
192
)
'0b11000000'
2.
3.
4.
5.
6.
7.
8.
>>>
192
&
64
# et
64
>>>
192
&
32
0
>>>
(
192
&
64
) ==
64
True
>>>
(
192
&
32
) ==
32
False
2.
3.
4.
5.
6.
>>>
(
0
<<
1
) # décalage de bits
0
>>>
(
1
<<
1
)
2
>>>
(
64
<<
1
)
128
Nous pouvons donc avec un parcours naïf, récupérer une valeur dont on ne connaît pas la taille de définition (c’est-à-dire le nombre d’octets utilisés pour stocker la valeur).
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
import
random
valeurs =
[]
for
i in
range(
0
, 10
):
valeurs.append
(
random.randint
(
0
, 255
) )
print
(
valeurs )
_valeursPertinentes =
[ "0b"
]
for
v in
valeurs:
if
v >
128
: # on continue : le bit de poids élevé vaut Vrai
_valeursPertinentes.append
(
bin
(
v )[3
:] )
else
: # on s'arrête : le bit de poids élevé vaut Faut
break
try
:
print
(
_valeursPertinentes )
valeurFinale =
int(
""
.join
(
_valeursPertinentes ), 2
)
print
(
valeurFinale )
except
ValueError
:
print
(
"pas assez de valeurs en entrée pour calculer - le hasard a mal fait la chose !"
)
Vous donnera un résultat aléatoire qui pourrait être :
[183, 171, 185, 187, 255, 53, 154, 181, 86, 189]
['0b', '0110111', '0101011', '0111001', '0111011', '1111111']
14855069183
Il a fallu 5 octets pour stocker l’entier 14 855 069 183 – et nous ne le savions pas au début.
Pour la fonction inverse, pour le même nombre, le code peut être le suivant :
Les plus observateurs auront noté tout de même quelque chose d’étrange : la production de la valeur finale a pourtant pris cinq valeurs initiales alors que l’opération en sens inverse, n’en produit que trois ?!
Le code n’est pas faux et s’explique très bien : les valeurs au hasard n’utilisaient pas pleinement tous les bits de chaque octet comme nous le faisons avec le second code. Dit autrement, la valeur finale – 14 855 069 183 – est produite par les deux l’utilisation des valeurs suivantes avec cette méthode :
- [183, 171, 185, 187, 255]
- [238, 214, 242]
… C’est dire si, parfois, il faut se méfier des apparences et que décidément, tout est une affaire de nombres représentés… et finalement du poids relatif des bits.
V. La création de notre premier silo▲
Bien, nous avons vu les principales généralités à connaître. Avant de l’accoupler à un moteur HTTP avec REST, tentons d’avoir déjà les principales commandes avec une classe qui fonctionne localement.
Je ne vais pas vous faire attendre : voici la proposition…
V-A. Commençons le commentaire…▲
Dans cette classe, j’ai séparé ce qui tient de l’index et de ce qui tient de l’enregistrement. Cette séparation n’est pas seulement esthétique : l’index a une taille fixe (ici 37 octets) et précède le contenu. Le contenu a ensuite une organisation particulière, ici avec trois parties pouvant être de taille maximale identique. Cette « complexité » d’organisation est largement suffisant pour du stockage de triplets.
Si vous souhaitez parcourir rapidement le fichier, vous devez donc lire les 37 premiers octets, les comprendre et trouver la taille du contenu, puis aller directement lire à partir de l’octet suivant cette même taille. En somme, un enregistrement « complet » (l’index et l’enregistrement lui-même) fait 37 + la taille de l’enregistrement.
Sans lecture ET compréhension de l’index, nous ne pourrions pas déterminer la position de l’index suivant. Ce choix n’est pas nécessairement le meilleur, surtout si votre index est composé de nombreux champs (date, type, etc.), et est beaucoup utilisé. Grâce à une taille fixe, dans un fichier séparé du contenu, vous pouvez ainsi naviguer en sautant de taille d’index en taille d’index. Dans notre cas, ce serait de 37 octets en 37 octets.
Si le fichier d’index et de contenu sont différents, alors l’index doit indiquer non seulement la taille du contenu, mais aussi sa position de départ au sein du fichier de contenu.
Dans le fichier de contenu lui-même, ces derniers n’ont aucune organisation et sont ajoutés les uns à la suite des autres : on retrouve l’organisation grâce à l’index.
V-B. Ajouter, c’est facile… le reste moins▲
Ajouter du contenu dans un fichier, binaire ou non, c’est facile : le fichier s’étend par miracle (l’OS se charge de tout !). Le modifier presque tout autant : avec le couple seek et tell, vous pouvez vous déplacer puis écrire « par dessus » (en réalité, vous ne faites que modifier la valeur de l’octet, d’où le terme « d’écrasement »). Par exemple, si l’on représente un fichier sous la forme d’une suite de valeurs :
abcdefghi # = 9
Mais… lorsque vous voulez modifier au même endroit, le « z » par « xyz », c’est la catastrophe :
abcxyzghi # = 9
La taille ne change pas ! Nous ne sommes pas dans un éditeur de texte. L’écrasement (le changement de valeurs) se poursuit. En somme, votre fichier peut grandir (ajout), réduire (toujours par la fin, sous certaines conditions, avec truncate), être écrit (modifié). Mais il n’y a pas de garantie pour avoir ces opérations combinées entre elles afin de former un comportement en particulier (l’insertion et non l’écrasement par exemple).
Dans le code du silo, je vous propose d’utiliser dans l’index, un octet qui a la valeur 0 ou 1 – soit respectivement inactif ou actif. Lorsque la modification est demandée, il suffit de rendre inactif l’enregistrement actuel (soit l’écrasement d’un seul octet), puis de réécrire son contenu modifié comme un nouvel enregistrement. Ainsi le problème de la taille de la modification disparaît, car le fichier est agrandi.
Ce n’est pas sans incidence : beaucoup de modifications donnent des tailles de fichiers impressionnantes, avec énormément de pertes : les enregistrements finissent par être majoritairement marqués comme inactifs. La fonction d’optimisation est là pour cela : elle réécrit, si l’on dépasse un certain seuil calculé avec une banale fonction de comptages (« statistiquer »), dans un nouveau fichier seulement les enregistrements actifs.
Dans un vrai moteur de bases de données évidemment, il faudrait d’abord comparer la taille de modifications, voire si l’on peut effectuer la modification sans incidence sur la taille. Mais attention : ce qui est vrai pour une modification « en plus » l’est aussi « en moins ». Un contenu moins grand que la taille prévue… Et vous risquez d’avoir la lecture de votre prochain index à la mauvaise position.
Là encore une solution existe : plutôt que de stocker dans l’index le couple position et taille, vous pouvez avoir le couple position du contenu actuel, puis position de l’index du contenu suivant avec la taille – histoire de prévenir tout désordre si votre modification est « en moins ». Mais elle prévient pas celle « en plus » et oblige à avoir une vérification et encore une combinaison d’opérations…
Cependant, avec la relative efficacité en vitesse de lecture et d’écriture des SDD, il est parfois plus simple à coder et à maintenir, un système comme la solution du code proposée : marquer inactif + réécrire avec les modifications. Appelons là la solution du « moins pire compromis ». Ce n’est pas le meilleur, mais c’est celui qui retient le moins de défauts en gardant en mémoire que l’intérêt est pédagogique (donc de la clarté).
Une autre solution est de « décaler » le reste du fichier (et « couper » un éventuel excédent de place totale), pour ajouter ou retirer du contenu à un enregistrement dont la taille varie – mais imaginez si à chaque modification, vous devez réécrire des centaines de Go… à chaque instant ou presque ?
Pour la solution du « moins pire compromis », j’y vois aussi un mérite : la réécriture facilite l’archivage et pas seulement l’efficacité même du stockage. En effet, lorsque vous réécrivez pour optimiser la taille de fichier qui était alors en production, vous libérez ce même fichier à la fin du processus – il sera lourd certes, mais complet. Vous pouvez donc le réécrire une seconde fois, dans un autre processus et hors de la production, pour avoir un fichier de sauvegarde vertueux. Ou simplement le garder en l’état si vos indications de suppression ont de l’importance pour vous.
Si vous préférez un stockage en RAM – un peu comme le propose avec le système clés/valeurs Redis –, des listes de tuples en Python restent probablement une meilleure option que d’utiliser des fonctions de lectures et d’écritures sur des fichiers « virtuels ».
V-C. Et les droits ?▲
C’est une question épineuse. En soi un moteur de base de données reçoit des commandes et les exécute. Dans le premier article de la série, j’ai spécialisé mes classes. Je reste sur cette logique : le code que je propose pour votre étude se contente d’un UID pour chaque enregistrement (mais il peut rester à 0 : il est donc facultatif) ainsi qu’un « groupe ». Charge à vous de faire le rapprochement entre un utilisateur ou plusieurs utilisateurs et un groupe… c’est à ce moment-là que l’authentification devrait se faire, et non au moment de l’exécution de la commande. Avec les questions subsidiaires : autoriser ou non une modification, un ajout ou encore un utilisateur à utiliser un ou plusieurs groupes…
En réalité, la question des droits rejoint plus précisément celui d’un éventuel langage de requête comme MySQL. Une fois identifié, vous disposez de droits. Mais vous pouvez ne pas l’être et en avoir quand même (des différents).
Nous verrons dans le troisième article concernant précisément RDF, que le langage de requête pour les triplets et les triplestores est Sparql.
Lorsqu’un client (et l’utilisateur derrière – identifié ou non) envoie sa requête, nous pouvons imaginer que c’est le moment de vérifier ses droits donc, et de préparer une commande que le moteur de base de données puisse comprendre – notamment vérifier éventuellement la cohérence des données et/ou la validité de la syntaxe de la commande.
V-D. Tout peut être amélioré – au prix (souvent) de la lisibilité…▲
… et la lisibilité est le début du chemin de croix de la maintenabilité.
Intéressons-nous à la fonction « ajouter ». Celle-ci a une contrainte : pour connaître précisément et écrire dans le fichier, elle a besoin de la taille « réelle » de l’enregistrement (c’est-à-dire le contenu et la taille de chaque partie du contenu). Très logiquement, j’utilise une variable pour temporiser l’index et les parties qui forment le contenu, avant d’écrire dans l’ordre l’enregistrement complet.
Cependant ce n’est pas très efficace : je dois doubler en mémoire la taille de tout le contenu de l’enregistrement (un type str et une chaîne binaire encodée en UTF-8).
Par ailleurs et pour mémoire, une opération d’encodage/de décodage prend très peu de temps et de ressources :
2.
3.
encode : 0
:00
:00.296841
décode : 0
:00
:00.343635
mixte : 0
:00
:00.546781
Alors n’y a-t-il pas un moyen plus ingénieux que ce double stockage ?
Eh bien oui, il y a :
Plutôt que d’attendre d’avoir toutes les informations, je vais écrire dans le fichier une chaîne de valeurs nulle mais qui correspond à la taille de mon index. Cette taille-là est fixe, je la connais donc sans attendre. Puis j’écris les parties de l’enregistrement un à un – pas la peine de tous les avoir en mémoire doublés en même temps.
Pour chaque partie de l’enregistrement, je peux utiliser cette technique qui est en quelque sorte une « pré-allocation » dans le fichier. Cette technique, plus rapide et moins coûteuse en mémoire, a cependant le défaut d’agir davantage sur la position du curseur dans le fichier… ce n’est pas sans risque si un problème survient et que la fonction échoue : des données partielles peuvent avoir été écrites.
V-E. « Aie, ma fonction d’écriture a échoué ! » ou la délicate gestion d’erreurs ▲
Un imprévu, une erreur… Bref l’écriture, quelle que soit la quantité de données à écrire, échoue. Le problème n’est pas la récupération de l’erreur (Python le gérera très bien si vous utilisez try/except) mais préserver la cohérence du fichier. Comme vous l’avez vu, le moindre problème non géré et l’organisation du fichier « fout » le camp. Évidemment, vous avez la possibilité de relire le fichier depuis le début et tenter une « réparation » - mais c’est complexe et pas toujours possible.
Pire : c’est parfois une erreur « définitive » : si le disque est plein, vous aurez beau tenter, ça ne fonctionnera pas jusqu’à libération de l’espace suffisant. L’idéal est de ne pas tenter une opération qui de toute façon n’aboutira pas et renvoyer, dès réception d’une commande, un message signalant l’impossibilité de l’opération.
Cependant, comment faire concrètement ? Tout d’abord gérer correctement ses erreurs : dès que vous allez commencer une opération d’écriture (pour ajouter ou modifier des données), pensez à tester si la variable d’accès au fichier ne retourne pas une valeur incorrecte ou nulle. C’est facile : faites un tell sur la fin actuelle du fichier par exemple (l’opération dans un contexte normal, ne retourne jamais une erreur), si vous êtes sur un ajout. Puis lancer au sein de la fonction de test, la fonction d’ajout et contrôlez son fonctionnement (try/except/else).
Si cet ajout échoue, alors vous pourrez grâce à la gestion de l’exception, tenter de supprimer des données éventuellement écrites qui ne seraient pas valides. Vous penserez également à laisser éventuellement un « état » à votre silo : est-il disponible seulement pour la lecture mais pas à l’écriture par exemple (et le pourquoi : paramètre de départ, disque plein, problème de droit, une erreur temporaire du programme, etc.).
Ce sont toutes ces petites réflexions, qui forment progressivement la qualité et permettent le respect des critères ACID.
V-F. Et les filtres dans tout ça ?▲
Probablement avez-vous déjà vu un paramètre à certaines fonctions - « filtres » - qui correspond à la possibilité de ne pas garder certains résultats. Nous verrons lors de l’intégration de ce code à notre serveur qu’il s’agit en réalité d’un croisement entre :
- des triplets qui, pris par « paquet », seront soumis à un test ;
- des requêtes qui, provenant de chaque client, formeront le test. C’est ici ce que j’ai appelé des « motifs » (ici un motif = une requête, c’est-à-dire la commande en lecture seule d’un client).
Le croisement positif entre une requête et un triplet permet de valider l’envoi de ce même triplet au client d’où provient la requête. Ce croisement peut être l’utilisation des expressions régulières, d’une comparaison de texte, etc.
En attendant d’avoir une fonction de renvoi – qui sera en réalité l’écriture sur le socket concerné, produisons la boucle de test qui pourrait être utilisée :
Pour deux clients, trois triplets et un million d’itérations (soit 6 millions de tests au final), nous arrivons à un chiffre qui semble assez catastrophique de près de 10 secondes sur mon poste – et 7,3 secondes si je n’utilise que la comparaison de texte et aucune expression régulière. Vous l’aurez compris, avec le même poste depuis le début de la rédaction de cette série d’articles, c’est le filtrage (et son corollaire le tri) qui est le plus chronophage de toutes les étapes. En tout cas cette forme.
Face à cela, de nombreuses solutions peuvent existent et dépendent de la qualité de la programmation ; de la liberté laissée à utiliser telle ou telle possibilité au sein du moteur de base de données ; de la puissance de la machine et de la répartition du travail. C’est ce dernier point qui nous occupe : le problème du tri ici, peut être l’absence de répartition de la charge entre plusieurs « travailleurs ».
Cette répartition peut prendre plusieurs formes (multiprocessus, threads, embauche de stagiaires supplémentaires, etc.), mais testons-en deux ici :
- soit une série de threads, mais il faudrait veiller à synchroniser les résultats entre la partie asynchrone du serveur Web et la partie synchrone au sein du thread ;
- soit en utilisant une série de fonctions en concurrence grâce à asyncio, permettant d’utiliser la boucle générale du serveur mais celle-ci pourrait se retrouver fortement saturée.
Testons d’une manière naïve ces deux familles :
Les threads mettent 1 minute et 11 secondes – là où le code sans « optimisation » mettait une dizaine de secondes. Plusieurs facteurs expliquent ce résultat (piteux), dont l’échange de données vers les threads via la queue (qui utilise un verrou interne), peu optimisé pour de nombreux petits échanges ; ainsi que le GIL qui impose à l’interpréteur Python un travail supplémentaire (particulièrement vrai sous CPython).
Bref c’est moyen-moyen… Asyncio seul s’en sort mieux avec 17,2 secondes, mais sans être exceptionnel – loin de là. Normal, ils ne sont pas prévus pour optimiser un « calcul pur », ce qui est plus ou moins notre cas ici :
Finalement notre premier code, celui sans « optimisation » n’était pas si catastrophique. Malheureusement, nous ne pourrons l’utiliser en l’état : ce serait bloquer de manière indéterminée la boucle principale. Nous devons donc accepter une prévisible perte de performance au profit d’une absence de blocage et utiliser Asyncio.
Relativisons cependant cette perte : 17 secondes pour nos 6 millions de comparaisons, cela représente par opération, 2,8 secondes… exposant -6. J’ai abordé ici l’optimisation du tri sous une forme naïve. Python dispose d’autres outils et il faut parfois découper son code sur plusieurs processus, faire des tests… et boire beaucoup de café.
VI. Serveur et silo… enfin réunis▲
Ou presque : le plus dur est maintenant (surtout pour vous, lecteur !). Nous allons revoir de manière assez radicale l’attendu de l’exercice afin de rester dans une limite déjà honorable de taille de code.
Je vous fournis ici une version fonctionnelle ; cependant, je vous incite fortement à faire par vous-même la combinaison de fonctions et d’opérations que nous avons vues jusqu’à présent. C’est en forgeant que l’on devient forgeron…
Notre triplestore remplira désormais les conditions suivantes :
- pour chaque commande, il distingue une requête (lecture seule), d’une transaction (écriture possible) et s’organise en conséquence ;
- la possibilité de lire, écrire et supprimer des triplets via HTTP (sans modifier ceux existant) ;
- il permet d’envoyer une page HTML pour l’édition de requête suivant une URL particulière ;
- chaque type d’opération dispose par requête, d’un filtre et/ou d’un UID limitant ;
- les filtres peuvent accepter des expressions régulières ;
- un UID (comme formulé grâce à UUID4) dans notre triplestore, est un entier pouvant être stocké sur 16 octets maximum. Il permet de regrouper un ou plusieurs triplets dans un même ensemble, et s’échange au format hexadécimal ;
- il ne prend pas en charge l’authentification ni aucune notion de sécurité ;
- il n’utilisera pas la possibilité « chuncked » de HTTP 1.1 pour les réponses, mais l’envoi d’un bloc lorsque la requête est terminée ;
- il n’agira que sur un seul fichier (f = index + contenu) et non sur deux (f1 = index, f2 = contenu) – un enregistrement correspond donc à une partie index et une partie contenu.
Vous noterez que l’encodage des requêtes entrant n’est pas considéré : ainsi le serveur ne supporte que du contenu au format UTF-8.
Certaines fonctions (optimisation, groupe, etc.) ne seront donc pas traitées. Concernant les filtres, un tableau nous permet d’y voir plus clair et entre ceux s’appliquant à chaque item du triplet (appelé « Filtre » et l’UID d’un triplet) :
Filtre |
UID |
La requête s’applique à… |
---|---|---|
Non |
Non |
Tous les triplets sans limite |
Non |
Oui |
Au(x) seul(s) triplet(s) pourvu(s) de l’UID demandé |
Oui |
Non |
Tous les triplets du triplestore répondant au filtre |
Oui |
Oui |
Le ou les triplets du triplestore répondant au filtre et disposant de l’UID demandé |
Nous terminons ici cette seconde partie ; nous aurons l’occasion de décortiquer plus en détail le code proposé ci-dessous dans la troisième et dernière partie, introduisant l’intérêt de RDF.
VI-A. Quelle limite théorique en taille du silo ?▲
Vous aurez l’occasion de le voir dans le code suivant, notre silo est bien « physiquement » limité en taille. En effet, comme évoqué sur le passage sur les représentations, nous utilisons un nombre défini préalablement d’octets pour coder les index (taille de l’enregistrement, tailles internes à l’organisation de l’enregistrement…).
Au-delà, notre silo est un fichier – ni plus, ni moins. Sous NTFS par exemple, la valeur théorique d’un fichier est de 16 Tio – pour autant ce serait une erreur de tenter un tel silo à cette taille. Le parcours risquerait de prendre du temps (plus si vous utilisez des systèmes de fichier sur plusieurs disques). Pour le coup, la limite est aussi celle de l’efficience du système que nous concevons !
En cas de nombreuses données (plusieurs centaines de Go, il faudrait mieux le montage d’un entrepôt de données (c’est-à-dire le rassemblement de nombreux silos d’une manière plus ou moins transparente).
VI-B. Organisation des fichiers▲
Afin de s’y retrouver, il devient nécessaire de découper notre code en une multitude de parties :
VI-B-1. main.py – ce qui lance le service▲
VI-B-2. CommandeHTTP.py ▲
VI-B-3. Silo.py▲
VI-B-4. Triplets.py ▲
VII. Note de la rédaction de Developpez.com▲
Nous tenons à remercier f-leb pour la relecture orthographique de ce tutoriel.