Partie 2 : Sérialisation des données
Bonjour à toutes et tous! 😄
On se retrouve pour la seconde partie de notre implémentation de sqlite en Rust.
Vous pouvez trouver la partie 1 ici où l'on a créé le REPL. Nous allons réutiliser notre travail aujourd'hui.
Dans cette partie nous allons attaquer le stockage des données.
Cette section sera légèrement plus dense que la précédente mais on devrait s'en sortir. 😅
Modéliser une ligne d'enregistrement
Avant de stocker de la données, il faut savoir comment la modéliser.
La solution naïve est d'en faire une structure.
Pour rappelle notre commande d'insert ressemble à insert 1 name email
.
Il n'est pas déconnant de modéliser cela ainsi:
Bon, on a notre modèle, maintenant il faut la stocker. Mais où?
Pour commencer simplement, nous allons stocker dans un tableau de bytes en mémoire.
Son type sera [u8; 1024]
, 1ko de mémoire, parce que ici on est riche!! 💰
Ne vous inquiétez pas pour cette simplicité apparente, les prochains articles vont être démentiellement plus complexes. 😈
La question maintenant est
Comment transformer notre structure en des
&[u8]
?
Serde (ma version)
Ce principe de transformer une structure de données en des données transférables sur un autre support, se nomme la sérialisation.
L'opération inverse de re-transformer les données sérialisées en une structure de données se nomme la désérialisation.
J'ai déjà réalisé un article sur le mécanisme utilisé par Rust pour normalisé ces opérations, vous pouvez y jeter un coup d'oeil, si vous êtes curieuse/curieux.
Mais aujourd'hui, au vu de la contrainte qui nous autorise uniquement la lib standard, nous ne pourront pas utiliser serde.
Au lieu de ça, nous allons en bâtir notre propre version qui sera plus simple, mais plus adaptée à nos usages.
La première chose que nous allons définir est l'interface publique de notre "serde".
Nous allons définir deux traits:
- Serializable : qui permet de passer de la structure de données au
&[u8]
. - Deserializable: qui permet l'inverse
Nous avons quelques petites choses à rectifier, il nous manque les définitions de:
- SerializationError
- DeserializationError
Commençons par les erreurs, qui sont le plus simple à définir. On reviendra sur les variantes plus tard.
//------------------------
// DeserializationError
//------------------------
//----------------------
// SerializationError
//----------------------
Implémentation du serde sur User
Pour cela, il faut un peu réfléchir à comment un ordinateur stocke les données.
Encodage des i64
Commençons par essayer de stocker un i64
. Comme son nom l'indique, il s'agit d'un entier stocké sur 64 bits ou 8 octets.
Pour s'en convaincre, nous pouvons appeler la méthode size_of.
dbg!; // 8
Un ordinateur travaille avec une granularité minimale de l'octets, cela signifie que pour stocker notre entier, il nous faut 8 cases, 8 u8
de notre buffer.
Mais du coup comment est-il stocké?
Si on en fait la représentation binaire du nombre 42 sur 64 bits, cela nous donnes:
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00101010
^ ^
MSB LSB
Most Significant Bit signifie "Bit de poids fort" et Least Significant Bit signifie "Bit de poids faible".
Le LSB permet de repérer le bit qui encode la valeur 1 si tous les autres bits sont à 0.
Il y a deux manières de stocker la données:
- Soit l'on lit de gauche à droite et on stocke du MSB vers le LSB.
- Soit l'on lit de droite à gauche et on stocke du LSB vers le MSB.
Ce principe de nomme l'endianess et est une convention que l'on doit suivre à la fois en lecture et en écriture pour être capable de récupérer les données stockées.
On va passer notre nombre binaire en hexa pour que ça soit plus simple.
00 00 00 00 00 00 00 2A
Si l'on stocke du MSB vers le LSB, en Big Endian, cela nous donne le tableau suivant.
let data =
Si par contre on stocke du LSB vers le MSB, alors on sera en Little Endian:
let data =
Rust fourni des outils pour désérialiser (car c'est de ça qu'il s'agit) les bytes en un i64
.
Il existe deux méthodes:
- i64::from_le_bytes : lecture en Little Endian
- i64::from_be_bytes: lecture en Big Endian
Petite expérience:
// Little endian
let data = ;
dbg!; // 3026418949592973312
dbg!; // 42
// Big endian
let data = ;
dbg!; // 42
dbg!; // 3026418949592973312
On voit bien ici l'importance capitale de l'endianess dans la manipulation des données.
Ok cool, mais comment on transforme notre i64
en bytes ?
Pareil, Rust a tout prévu, il y a les méthodes pour:
- i64::to_be_bytes : consomme un i64 et encode le en Big Endian
- i64::to_le_bytes : consomme un i64 et encode le en Little Endian
let data = 42_i64.to_le_bytes;
dbg!; // 42
dbg!; // 3026418949592973312
let data = 42_i64.to_be_bytes;
dbg!; // 42
dbg!; // 3026418949592973312
De manière totalement arbitraire, j'ai choisi de faire du Little Endian. C'est ce qui est utilisé sur les archi x86, alors pourquoi pas.
Du coup, on passe comment de nombre à de la données sérialisé dans notre buffer?
Et bien on va tout simplement copier les bytes dans notre tableau.
Pour cela, nous alons utiliser la méthode copy_from_slice, mais attention, elle est extrêmement capricieuse.
Elle panique si la slice de destination et de source n'ont pas exactement la même taille.
Heureursement, nous on sait la taille que ça prendra : size_of::<i64>()
.
On peut alors encoder dans notre buffer notre entier en Little Endian.
let mut buffer = ;
buffer.copy_from_slice;
assert_eq!;
Le
.try_into().unwrap()
est nécessaire car la signature estpub const
Ce qui n'est pas un
&[u8]
, le try_into réalise la conversion. Le unwrap assure que exactement 8 octets sont transférés.
Encodage des String
Le stockage des chaînes de caractères est un vaste sujet qui a fait coulé beaucoup d'encre.
Dans les années 60, seuls les américains semblent faire de l'informatique et imposent leur alphabet et leur manière de stocker le texte. j'ai nommé le American Standard Code for Information Interchange ou ASCII.
L'idée est simple, chaque chiffre codé sur 8 bits ou un octet, correspond à une lettre dans le "charset" occidental américain .
!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~
C'est bien, mais les français, aiment beaucoup les accents et les cédilles et autres œ
. Bref, on était pas content et on a fait notre sauce. On a alors créé le latin-1.
Mais les griefs que l'on avait, les autres peuples, les avaient également:
- latin-2 : pour l'europe centrale
- latin-3 : pour les turques
- grec : pour les grecques
- arabe : pour les arabes
- etc...
Tout le monde est partie de son côté bâtir son monde idéal.
Et à côté de tout ce beau monde, l'Asie a également développé son propre charset, mais à la différence des précédents, celui-ci mélange des alphabets entre eux pour pouvoir encoder des choses comme:
日本語版Wikipedia
Ce besoin est dû à la très forte influence occidentale qui a été imposé à la fois par le colonialisme et les occupations successives qui ont amené à rendre courant l'usage du syllabaire occidental en plus du régional.
Mais il y a infiniement plus de caractères dans du japonais ou du chinois que dans du français ou de l'anglais.
Tellement que l'on ne peut plus coder sur 8 bits les caractères, il en faut plus, au moins 2 octets pour le japonais.
On se retrouve alors au début des années 2000 avec une foultitudes de standards qui ne sont standards que de nom car quasi incompatible les uns par-rapport aux autres.
Bref, c'est le zbeul !
Une volonté d'unification de tout ce bazar, va conduire à un effort de standardisation mondiale qui n'a rien de moins comme objectif d'encoder tous les dialectes de la planète.
J'ai nommé l'UTF-8.
Contrairement à l'ASCII, le codage des caractères n'est pas réalisé de manière fixe, on peut avoir 1 octet, 2 octets, 3 octets ou 4 octets pour encoder un caractères.
Un fort lobbyisme a dû avoir lieu à l'époque, car le premier octet est celui de l'ASCII. Autrement dit, tant que vous ne fricottez pas avec les accents ou autres caractères reniés par l'Oncle Sam, une chaîne ASCII est compatible avec de UTF-8 et vice versa.
La conséquence est que la longeur sera la même également.
Pourquoi je vous est parlé d'encodage de string et d'UTF-8?
C'est parce que Rust gère nativement l'UTF-8. Et le gère bien, pas de soucis à se faire sur la longueur de la chaîne par exemple.
dbg!; // 5
dbg!; // 4
De même que récupérer les bytes est aisé.
println!; // [74, C3, AA, 74, 65]
println!; // [74, 65, 74, 65]
On remarque également que l'encodage se fait de gauche à droite, d'abord le 't' puis le 'e', puis le 't', ...
Et aussi que 'ê' n'est pas un 'e'+'^', c'est autre chose, mais cette complexité est cachée, et ça nous arrange bien. 😄
Et l'opération est réversible. On peut retransformer les bytes en string via la méthode String::from_utf8.
println!; // tête
println!; // tete
L'opération peut échouer si la séquence de bytes est inconnue de UTF-8
Du coup il est aisé de venir encoder la chaîne dans notre buffer.
let mut buffer = ;
let data = "tête".to_string;
buffer.copy_from_slice;
assert_eq!;
Alors oui, vu qu'on connais la données à rechercher, c'est facile de récupérer la bonne slice à décoder dans le buffer.
Mais si vous ne savez pas ce que vous cherchez, vous pouvez vous arrêter trop tard ou trop tôt.
Pour y arriver, nous allons ruser et encoder la taille de la String dans l'octet avant les données.
let mut buffer = ;
let data = "tête".to_string;
// on stocke la taille dans le premier octet
buffer= data.len as u8;
// on avance d'un pour stocker
buffer.copy_from_slice;
// lors de la lecture on récupère la taille à lire du premier octet
let size = buffer as usize;
assert_eq!;
Encodage de la structure User
Encoder une structure, consiste à encoder successivement chacun de ses champs.
Mais il y a une subtilité: il faut se décaler d'autant que ce que l'on a écrit pour le premier champ, pour pouvoir écrire le second et ainsi de suite.
On va donc introduire une variable cursor
qui va mémoriser notre état d'avancement.
Nous pouvons implémenter notre sérialisation en utilisant toutes les connaissances que l'on possède désormais.
Et de même la désérialisation
On en profite pour rajouter les variates d'erreur
On peut alors vérifier notre travail
Et voilà! On sérialise notre structure! 🤩
Curseur
C'est bien, mais quelque chose m'ennuie: je n'aime pas gérer à la main les offsets dans le buffer. 😑
Heureusement, ce que l'on réalise est du basico-basique, des problèmes vu et revu, et donc il existe un outils dans la lib standard qui se nomme Cursor qui a pour exact but de fournir cette aspect de déplacement dans la donnée.
Mais aussi des traits Read et Write permettant de lire et d'écrire dans le buffer au fur et à mesure que l'on avance.
Notre sérialisation devient:
On se créé une BufferError pour l'occasion que l'on rajoute dans notre SerializationError
Puis on implémente la désérialisation
On se rajoute aussi notre BufferError dans DeserializationError
Et voilà !! Plus besoin de s'occuper du curseur ! 😄
Implémentation de serde sur les types primitifs
Alors oui, c'est mieux, mais on sent que les opération de sérialisation et désérialisation des champs "username" et "email" sont identiques. Cela manque de factorisation!
Et c'est là qu'on est heureux d'être en Rust car on peut accrocher des comportements sur des types primitifs.
Cela veut dire: pouvoir implémenter Serializable et Deserializable sur String.
Et on peut faire de même sur du i64
Cela nous donnera quelque chose comme ça:
C'est élégant non ? 🤩
par contre ça ne marche pas du tout! Comme on reset le Cursor à chaque serialize et deserialize, notre cursor est toujours à l'offset 0 lorsqu'il débute.
La solution? Balader le curseur qui wrap le buffer.
Pour ça on doit un peut modifier notre interface serde
Modifier les implementations pour String et i64
Et modifier l'implémentation pour User
Il faut aussi modifier notre test en conséquence
Et bingo ! 🎯
Nous avons une interface stable pour manipuler nos données! 😍
Conclusion
Dans cette partie on est rentré au coeur des données, on a analysé comment elle était agencée et comment on pouvait la transformer en un format de transport au travers de la sérialisation.
Dans la partie suivante nous allons voir comment utiliser notre API bas niveau de sérialisation pour construire une API haut niveau qui vous semblera bien plus familière.
Puis nous fusionnerons cette API avec le REPL fabriqué en Partie 1 pour pouvoir interagir avec notre API de haut niveau.
Vous pouvez trouver le code de la partie 2 ici. Ainsi que le diff.
Merci de votre lecture et à la prochaine. ❤️
Ce travail est sous licence CC BY-NC-SA 4.0.