Revenons à quelque chose de très, très utile. Il s'agit de comparer deux listes d'objets qui sont censées représenter une même réalités dans deux temporalités différentes. L'usage classique et de suivre l'évolution de cette liste de façon efficace, en notant les différences entre un état conservé mais ancien, et un état nouveau qui doit le remplacer tout en minimisant les mises à jour à apporter. L'idée est de repérer:
- les objets qui sont apparus,
- les objets qui ont disparu,
- les objets qui existaient déjà, mais dont le contenu à été modifié.
Les objets qui n'ont pas évolué sont tout simplement ignorés. On pourra ensuite lancer des ordres de mises à jour adaptés (CREATE, UPDATE, DELETE) uniquement sur les objets concernés et donc éviter le "carnage" qui consiste à tout supprimer pour ensuite tout recréer, comme je peux le voir hélas, parfois. Il y a deux écueils à éviter:
- écrire une synchronisation trop complexe, en comparant par exemple, de façon récursive, les objets champs par champs.
- écrire une synchronisation très consommatrice en parcourant inlassablement les deux listes (algorithme quadratique).
Il y a néanmoins un préalable à ce qui va suivre: identifier un objet dans la liste. dans l'exemple qui va suivre, cette identification est des plus simples : un objet est identifié par son "id", une simple valeur numérique. Bien que ce soit très souvent la réalité, la solution proposée ne repose pas sur un tel postulat. Il est parfaitement possible d'adapter le script pour qu'il utilise une clé plus complexe et/ou non numérique. Néanmoins, trois contraintes sont fondamentales et doivent être respectées:
- Les informations qui constituent l'identifiant sont des invariants stricts : elles ne peuvent en AUCUN cas évoluer.
- L'identifiant indique un unique objet, il ne peut en AUCUN cas être partagé par plusieurs objets.
- TOUS les objets ont un identifiant (il n'y a pas d'OINI : Objet Informatique Non Identifié)
Dans l'exemple qui suit (simplifié pour des raisons pédagogique évidentes) les deux états de la (toute petite) liste sont incluses dans le payload. Dans un cas "réel", on peut imaginer que l'état ancien est retiré de l'Object Store, d'une Base de Données, d'un fichier sauvegardé localement ou sur SFTP et que seul le nouvel état soit apporté par le payload.
Ici, donc un objet est nouveau (Hans KUBLER, id: 4), un objet disparait (Mary SUE, id: 3), un objet est modifié (Ralph CLARK, id: 2). L'objet David DURAND, lui n'évoluant pas, doit être ignoré. La synchronisation demandée doit donc retourner:
Pour une implémentation efficace de la fonctionnalité, nous allons utiliser deux astuces:
- Afin d'éviter d'avoir à parcourir inlassablement les deux listes, l'une d'entre elle va être transformée en map dont la clé d'accès d'un élément est son identifiant (dans DataWeave, à l'instar de JavaScrip, une map est simplement un objet dont les noms des champs sont les clés d'accès). Ceci peut être réalisé facilement en utilisant la fonction "groupBy" qui "regroupe" (pas vraiment ici puisque chaque groupe ne contient qu'un élément) mais qui aussi indexe d'élément pas son identifiant.
- Afin d'éviter d'avoir à comparer les objets champs par champs, nous allons calculer un checksum pour chacun d'eux et comparer les checksum pour détecter les évolutions. Ce procédé présente des avantages majeurs et quelques inconvénients mineurs. Les avantages sont: indépendance du procédé par rapport à la structure d'un objet (et des éventuelles évolutions de cette structure), faible encombrement si l'on doit conserver (dans ObjectStore ?) le dernier état de la liste (on n'a besoin de conserver que le checksum et non la structure complète), facilité d'écriture de la procédure de comparaison entre deux états d'un objet (c'est une simple égalité entre deux checksum). Les inconvénients sont: l'ordre des champs dans l'objet ne doit pas varier (car cela influe sur le calcul du checksum), temps de calcul du checksum (très faible au demeurant).
J'entends les esprits chagrins me dire: mais non, il y a encore un inconvénient, et majeur celui-là : deux états de l'objet peuvent produire le même checksum. Ouais. Mais non. Petit rappel de mathématique: un MD5 peut produire jusqu'à 1, 5 x 1077 combinaisons. Prenons le cas ou nous comparons 15000 objets qui sont TOUS modifiés, TOUS les jours de l'année (samedi et dimanches compris). Pour qu'on ait 50% de chance que l'incident se produise UNE fois, il nous faudrait attendre un million de milliards de milliards de milliards de milliards de milliards de milliards de fois... l'âge de l'univers !! Oubliez. L'argument est ridicule.
Le script qui nous permet d'obtenir (à peu près) le résultat donné ci dessus est:
- la fonction toCreate permet de détecter la liste des objets qui apparaissent. Elle peut aussi être utilisée pour détecter les objets qui disparaissent en lui faisant remonter le temps (et donc en inversant les liste before et after) !
- La fonction canonize calcule les checksum ET transforme la liste en map. Cela peut paraître maladroit car la partie "after" doit être utilisé sous forme liste et non map (d'où les pluck dans les fonctions toCreate et toUpdate). Mais après plusieurs écriture, c'est finalement la façon la plus simple de faire car la logique s'inverse pour détecter les suppressions. Il est donc possible d'optimiser un peu l'exécution de ce script en alourdissant significativement son écriture (ce qui n'est pas l'approche la plus pertinente pour l'exercice pédagogique de ce billet).
Let's get back to something very, very useful. It involves comparing two lists of objects that are supposed to represent the same reality in two different temporalities. The classic use is to track the evolution of this list efficiently, noting the differences between a preserved but old state, and a new state which is to replace it, while minimizing the updates required. The idea is to identify
- objects that have appeared,
- objects that have disappeared,
- objects that already existed, but whose content has been modified.
Objects that have not changed are simply ignored. You can then launch appropriate update commands (CREATE, UPDATE, DELETE) only on the objects concerned, thus avoiding the "carnage" of deleting everything and then recreating it all, as I unfortunately sometimes see. There are two pitfalls to avoid:
- write an overly complex synchronization, for example, by recursively comparing objects field by field.
- write a very time-consuming synchronization, tirelessly going through the two lists (quadratic algorithm).
In the following example, this identification is very simple: an object is identified by its "id", a simple numerical value. Although this is very often the reality, the proposed solution is not based on such an assumption. It's perfectly possible to adapt the script to use a more complex and/or non-numerical key. However, three fundamental constraints must be respected:
- The information making up the identifier is strictly invariant: it can NEVER change.
- The identifier identifies a single object, and can NEVER be shared by several objects.
- ALL objects have an identifier (there are no OINIs: Unidentified Computer Objects).
In the following example (simplified for obvious pedagogical reasons), the two states of the (very small) list are included in the payload. In a "real" case, you could imagine that the old state is retrieved from the Object Store, a Database, a file saved locally or on SFTP, and that only the new state is brought in by the payload.
Here, therefore, one object is new (Hans KUBLER, id: 4), one object disappears (Mary SUE, id: 3), one object is modified (Ralph CLARK, id: 2). As the David DURAND object does not evolve, it must be ignored. The requested synchronization must therefore return:
For an efficient implementation of the functionality, we'll use two tricks:
- To avoid having to scroll endlessly through the two lists, one of them will be transformed into a map whose element access key is its identifier (in DataWeave, like in JavaScrip, a map is simply an object whose field names are the access keys). This can easily be achieved by using the "groupBy" function, which "groups" (not really, since each group contains only one element) but also indexes the element by its identifier.
- To avoid having to compare objects field by field, we'll calculate a checksum for each of them and compare checksums to detect evolutions. This procedure has major advantages and a few minor drawbacks. The advantages are: independence of the procedure from an object's structure (and any evolutions of that structure), small footprint if we need to keep (in ObjectStore?) the last state of the list (you only need to keep the checksum and not the complete structure), easy to write the comparison procedure between two states of an object (it's a simple equality between two checksums). The disadvantages are: the order of the fields in the object must not vary (as this affects the calculation of the checksum), checksum calculation time (which is very low, by the way).
But no, there's another major drawback: two states of the object can produce the same checksum. Right. But no. A quick mathematical reminder: an MD5 can produce up to 1.5 x 1077 combinations. Let's take the case where we're comparing 15,000 objects that are ALL modified, EVERY day of the year (including Saturdays and Sundays). For us to have a 50% chance of the incident occurring ONCE, we'd have to wait a million billion billion billion billion billion billion times... the age of the universe!!! Forget it. The argument is ridiculous.
The script that allows us to obtain (roughly) the result given above is:
- The toCreate function is used to detect the list of objects that appear. It can also be used to detect objects that disappear by making it go back in time (and therefore inverting the before and after lists)!
- The canonize function calculates checksums AND transforms the list into a map. This may seem clumsy, as the "after" part should be used as a list and not a map (hence the pluck in the toCreate and toUpdate functions). However, after several writes, this is ultimately the simplest way of doing things, as the logic is reversed to detect deletions. It is therefore possible to optimize the execution of this script a little by making it significantly heavier to write (which is not the most relevant approach for the pedagogical exercise in this post).
Aucun commentaire:
Enregistrer un commentaire