ZK Huge Grouping Model fr"

From Documentation
 
(26 intermediate revisions by the same user not shown)
Line 15: Line 15:
 
Sur bases des certains concepts (pagination au niveau de la DB et séparation du contrôle de la pagination de la grid) cet article propose une stratégie et présente un exemple implémenté de comment faire du groupement de données à l'identique.
 
Sur bases des certains concepts (pagination au niveau de la DB et séparation du contrôle de la pagination de la grid) cet article propose une stratégie et présente un exemple implémenté de comment faire du groupement de données à l'identique.
  
Cependant, les choses se compliquent ici quelques peu... j'espère donc au final donner une idée de comment cacher les parties compliquées, et laisser le développeur se concentrer sur la récupération et l'affichage des données.
+
Cependant, les choses se compliquent ici quelques peu... j'espère donc au final donner une idée de comment ZK masque les parties compliquées, et laisse le développeur se concentrer sur la récupération et l'affichage des données.
  
=The Challenges=
+
=Les défis=
Grouping is a powerful feature in ZK but also adds an extra layer of complexity.
+
Le Groupement est une caractéristique puissante de ZK mais qui amène aussi une couche supplémentaire de complexité.
  
One might argue whether it is useful to display such a long list in this way (especially without pre-filtering the results).
+
Certains pourraient se demander s'il est utile d'afficher une liste aussi longue de cette manière (en particulier sans pré-filtrage des résultats).
  
We are here to show that it is possible, maxing out the limits ... ZK GroupsModel supports indexes of int-datatype so we will go up to  somewhere around Integer.MAX_VALUE (~ 2.000.000.000 records - 2 Billion)
+
Nous sommes ici pour montrer que c'est possible possible, jusqu'à quelles limites ... et bien, ZK GroupsModel supporte des index de type int, nous pouvons donc aller jusqu'à environ Integer.MAX_VALUE (~ 2.000.000.000 enregistrements - 2 milliards)
  
==Paging and grouping challenges==
+
==Les défis de la pagination et du regroupement==
  
1. Groups can be open or closed (initially and  interactively)
+
1. Les groupes peuvent être ouverts ou fermés (initialement ou de façon interactive)
:-> The total count and the number of pages change, when opening/closing nodes... this needs efficient counting, and state keeping
+
:-> Le nombre total et le nombre de pages changent à l'ouverture/la fermeture des nœuds d'index (nodes)... ceci requiert un comptage efficace et continuellement à jour
  
2. Groups can have arbitrary number of children
+
2. Les groupes peuvent avoir un nombre arbitraire d'enfants
:-> Random access to a specific page can become tricky ... how to know the current group and position inside the group for that page
+
:-> L'accès aléatoire à une page spécifique peut devenir délicat ... comment connaitre le groupe actuel et la position à l'intérieur de ce groupe pour cette page
:--> How to implement a feasible search?
+
:--> Comment implémenter une recherche réalisable ?
  
3. Minimize DB operations (accumulating network/DB latency)
+
3. Minimiser les opérations DB (accumulation des latences réseau/DB)
:-> Consider caching vs. memory consumption
+
:-> Prendre en considération la mise en cache versus la consommation de la mémoire
  
1. + 2. + 3. This article will discuss how to combine all three aspects in an efficient, memory preserving (almost predictable) way, and a few trade offs, that have to be made. Also some extension points are highlighted, where if possible the general purpose implementation can be replaced by a more specific one, knowing more details about your own data model.
+
1. + 2. + 3. Cet article va expliquer comment combiner ces trois aspects de manière efficace en préservant la mémoire (presque prévisible) et quelques compromis qui doivent être faits. Aussi, quelques points d'extension sont mis en évidence, , si possible, la mise en oeuvre d'usage général peut être remplacée par une autre plus spécifique, en fonction des détails de votre propre modèle de données.
  
==Some Limitations==
+
==Quelques limites==
  
* The example only works on static data - when data changes, the model needs to be reinitialized and caches need to be cleared.
+
* Cet exemple fonctionne uniquement sur des données statiques - si les données changent, le modèle doit être réinitialisé et les caches doivent être vidées.
* As not all rows are present in memory, you cannot send UI events to components currently not on the screen (you manipulate the model state instead)
+
* Vu que toutes les lignes ne sont pas présentes en mémoire, vous pouvez envoyer des événements UI à des composants qui ne sont pas affichés à l'écran (vous manipulez l'état du modèle à la place)
* The example needs to store the open/close state in memory ("humans are limited", one is unlikely to toggle 100+ groups) - So should be no problem.
+
* L'état ouvert/fermé est stocké en mémoire ("les humains ont des limites", il est peu probable de dépasser les 100 groupes) - Il ne devrait donc pas y avoir de problème.
* Some "dummy" components are required to make the <grid> accept the limited (windowed) view over the data.
+
* Certains composants "maquettes" sont nécessaires pour que le <grid> accepte la vue limitée (fenêtrée) sur les données.
  
=Implementation=
+
=Implémentation=
  
The [[#Download|example package]] is a maven project, with the following structure:
+
Le [[#Download|package exemple]] est un projet maven, avec la structure suivante:
  
 
[[File:hugeGrouping_files.png]]
 
[[File:hugeGrouping_files.png]]
  
The "src"-folder contains the following files/folders/packages:
+
Le dossier "src" contient les différents fichiers/dossiers/packages:
  
Generic enabling classes (explained below):
+
Classes génériques (expliqué plus bas):
 
; org.zkoss.grouping.model
 
; org.zkoss.grouping.model
: generic paging GroupsModel implementation
+
: implémentation pagination générique GroupsModel  
 
; org.zkoss.grouping.model.search
 
; org.zkoss.grouping.model.search
: grouping position search implementations
+
: implémentation des recherches de positions
  
  
Example specific implementations (showing the usage of the above)
+
Implémentations spécifiques à l'exemple (montrant l'utilisation des éléments ci-dessus)
 
; org.zkoss.grouping.dao
 
; org.zkoss.grouping.dao
: in memory Dao class simulating huge data
+
: Classe Dao en mémoire qui simule des grosses quantités de données
 
; org.zkoss.grouping
 
; org.zkoss.grouping
: the actual Composer (MVC) / ViewModel (MVVM) and (Dao-backed) PagingGroupsModel implementations
+
: Les implémentation du Composer actuel (MVC) / ViewModel (MVVM) et (Dao-backed) PagingGroupsModel
  
Corresponding zul-files (in src/main/webapp):
+
Fichiers ZUL correspondants (dans src/main/webapp):
  
 
; accesslog.zul
 
; accesslog.zul
: MVC usage of PagingGroupsModel
+
: utilisation MVC de PagingGroupsModel
 
; accesslog_mvvm.zul
 
; accesslog_mvvm.zul
: MVVM usage of PagingGroupsModel together with DelegatingSinglePageGroupsModel
+
: utilisation MVVM de PagingGroupsModel avec DelegatingSinglePageGroupsModel
 
; accesslog_mvvm_default_paging.zul
 
; accesslog_mvvm_default_paging.zul
: MVVM example highlighting the performance issues without separate paging control, using a much smaller data set
+
: Exemple MVVM mettant en évidence les problèmes de performance sans contrôle de pagination séparé, en utilisant un set de données plus petit
  
==Accessing the data==
+
==Accéder aux données==
  
===Data Record and Dao===
+
===Data Record et Dao===
  
We start with a simple data record representing access log data.
+
Nous commencons avec un simple enregistrement de données représentant des access logs.
  
 
<source lang="java">
 
<source lang="java">
Line 97: Line 97:
 
</source>
 
</source>
  
The AccessDataDao is a mock implementation, generating the data on the fly not using a DB (just deterministic random values...) caching the group sizes in memory.
+
L'AccessDataDao est une implémentation mock générant les données à la volée sans utiliser une DB (juste des valeurs aléatoires) et qui stocke la taille des groupes en mémoire.
Initially 40.000.000 of group's child counts stored in an int[] are still 160 MB of memory.
 
  
So ignoring the random data generation, your Dao would need to implement the following 5 operations with according SQL/HQL/Criteria/noSQL queries. I am aware that even counting big amounts of Data at DB level is not a piece of cake. There is always some preparation of your data at DB level to be done: e.g. proper indexing, pre aggregated groups/counts (this is nothing the front end framework can support you with).
+
Donc, en oubliant la génération de données aléatoire, votre Dao devrait implémenter les 5 opérations suivantes suivant des requêtes SQL/HQL/Criteria/noSQL. Je suis conscient que compter des grandes quantités de données au niveau de la DB n'est pas chose simple. Il faut toujours préparer les données au niveau de la DB: ex. indexation propre, pré agrégation des groupes/compteurs (rien en quoi le 'front end framework' peut vous aider).
  
 
<source lang="java">
 
<source lang="java">
Line 139: Line 138:
 
</source>
 
</source>
  
===The Paging Model===
+
===Le modèle de pagination===
  
AccessDataGroupsModel, our specialized PagingGroupsModel<D, H, F> uses AccessDataRecord as "data"(D) and String as "head"(H) and "foot"(F) implementation.  
+
AccessDataGroupsModel, notre PagingGroupsModel<D, H, F> spécialisé utilise une implémentation d'AccessDataRecord comme "data"(D) et String comme "head"(H) et "foot"(F).  
This class implements the 4 model methods and a GroupingPositionSearch strategy - all delegating to AccessLogDao from above, to keep the workload at DB-Level.
+
Cette classe implémente les 4 méthodes du modèle et une stratégie GroupingPositionSearch - tout en déléguant à AccessLogDao d'en haut, pour garder la charge de travail au niveau de la DB.
  
 
<source lang="java">
 
<source lang="java">
Line 199: Line 198:
 
</source>
 
</source>
  
As we can see the methods are focusing on counting, and retrieving data in page sized chunks. Nothing magical here, while our DB is doing the heavy work (selecting, grouping, counting, sorting) ... that's what it is optimized for. And with huge data we'll not attempt to compete with our DB, we just want as little data as possible. Your DB admin will be happy to assist you optimizing the queries and preparing the data. ;-)
+
Comme nous pouvons le voir, les méthodes se concentrent sur le comptage et la récupération des données dans des morceaux de la taille d'une page. Rien de magique ici, pendant que notre DB fait le travaille difficile (sélection, groupement, comptage, tri) ... c'est à ça que ça sert. Et avec des grosses quantités de données, nous n'allons pas essayer de battre la DB, nous voulons seulement des données aussi petites que possible. Votre administrateur DB sera heureux de vous  aider à optimiser vos requêtes et préparer vos données. ;-)
  
==Page/Caching, Counting & Open/Close State keeping==
+
==Page/Caching, Comptage & conserver l'état ouvert/fermé==
  
===Open/Close State keeping===
+
===Conserver l'état ouvert/fermé===
  
The PagingGroupsModel will keep track of the open/close states for the toggled groups (together with the childCount of that group).
+
Le PagingGroupsModel va garder une trace des états ouvert/fermé pour les groupes dont l'état a été modifié (avec en même-temps le childCount de ce groupe).
  
If the Model is initialized with INITIALLY_OPEN, then only the closed nodes will be tracked, and vice versa.  
+
Si le Model est initialisé avec INITIALLY_OPEN, alors on gardera la trace uniquement des 'nodes' fermés, et vice versa.  
  
Assuming a human will not take the time to toggle an outrageous number of groups, this Map (groupIndex => childcount) will stay relatively small and should not compromise our performance and memory expectations. Additionally the total number of toggled groups is updated on every open/close interaction.
+
En supposant qu'un humain ne prendra pas le temps de changer l'état d'un nombre immense de groupes, cette Map (groupIndex => childcount) restera relativement petite et ne devrait pas compromettre notre performance ainsi que nos attentes au niveau de la mémoire. De plus, le nombre total de groupes dont l'état a été modifié est mis à jour à chaque interaction ouvert/fermé.
  
This information is used to adjust the number of total children (for the UI paging calculations) or the number of children between 2 groups (for Position search) - as the DB won't keep that UI state.
+
Cette information est utilisée pour ajuster le nombre total d'enfants (pour le calcul de pagination UI) ou le nombre d'enfants entre deux groupes (pour la recherche de Position) - vu que la DB ne gardera pas cet état UI.
  
see:  
+
Voir:  
 
* PagingGroupsModel#getCurrentRowCount()
 
* PagingGroupsModel#getCurrentRowCount()
 
* PagingGroupsModel#getToggledCountBetween(int groupIndexFrom, int groupIndexTo)
 
* PagingGroupsModel#getToggledCountBetween(int groupIndexFrom, int groupIndexTo)
Line 220: Line 219:
 
===Page/Caching===
 
===Page/Caching===
  
The GroupsModel interface (ZK default) offers methods to retrieve '''single''' Groups, and Children. PagingGroupsModel implements this interface.
+
L'interface GroupsModel (ZK default) offre des méthodes pour récupérer les '''single''' Groups, et les Children (enfants). PagingGroupsModel implémente cette interface.
Whenever one of these methods is called the PagingGroupsModel will check if that position is cached for the current page, and if not (re)load a '''page sized chunk''' of group-/child-data  from the DB and put into the respective cache.
+
Lorsqu'une de ces méthodes est appelée,  le PagingGroupsModel va vérifier si cette position est mise en cache pour la page courante et si pas, (re)charge un morceau de page de taille équivalente de données depuis la DB et les mes dans les caches respectives.
  
One problem here is, that the chunk retrieved from the DB will not match the page boundaries in the UI.
+
Un problème apparaît ici, la taille des données récupérées de la DB ne correspond pas aux limites de la page dans l'UI.
  
 
e.g.
 
e.g.
Line 235: Line 234:
 
</source>
 
</source>
  
'''Page size vs. Group size''': While the UI-Pages have a constant size the groups may have a variable size, and their offset may shift because of previously opened/closed nodes, the offset of the chunks loaded from the DB would vary, whenever nodes are toggled.
+
'''Taille de la page vs. Taille du groupe''': Alors que les pages de l'UI ont des tailles constantes, les groupes eux peuvent avoir des tailles variables, et leur offset peut être décalé à cause des nodes ouvert/fermé, l'offset des morceaux chargés depuis la DB vont varier lorsque l'état des nodes est modifié.
  
As we want to benefit from caching at all possible levels, keeping the method/query parameters constant will reduce our required cache size at Dao method level or in DB and will avoid duplicate load of overlapping chunks (with multiple users having different UI states).
+
Vu que nous cherchons à profiter de la mise en cache à tous les niveaux possibles, gardons les paramètres des méthodes/requêtes constants et nous réduirons ainsi la taille de la cache nécessaire au niveau de la méthode Dao ou dans la DB, et cela permettra aussi d'éviter le chargement chevauché de groupes de données (avec des utilisateurs multiples qui ont des états UI différents).
  
So in the scenario above whenever e.g. Element 3 of Group 1 needs to be loaded the PagingGroupsModel will load the chunk "Group1 Child0-9" calling this.loadChildrenPage(1, 0, 10). Perfect for caching, as it would never call e.g. this.loadChildrenPage(1, 3, 10).
+
Donc, dans le scénario ci-dessus, lorsque p.e. Element 3 du Group 1 doit être chargé, le PagingGroupsModel va charger le groupe "Group1 Child0-9" en appelant this.loadChildrenPage(1, 0, 10). Parfait pour la mise en cache, vu qu'il n'appellera jamais p.e. this.loadChildrenPage(1, 3, 10).
  
see:  
+
Voir:  
 
* AccessDataGroupsModel#loadGroupPage(int startIndex, int pageSize)
 
* AccessDataGroupsModel#loadGroupPage(int startIndex, int pageSize)
 
* AccessDataGroupsModel#loadChildrenPage(int groupIndex, int startIndex, int pageSize)
 
* AccessDataGroupsModel#loadChildrenPage(int groupIndex, int startIndex, int pageSize)
  
The same strategy applies to caching the Groups. PagingGroupsModel will also load chunks of Groups with fixed intervals. In case groups are displayed with a foot, the groups cache size can be halved, as the group foot will consume one row too.
+
La même stratégie s'applique pour la mise en cache des Groups. PagingGroupsModel va aussi charger un ensemble de Groups avec des intervalles fixes. Si les groupes sont affichés avec un 'foot', la taille en cache des groupes peut être réduite de moitié vu que le foot du groupe va aussi consommer une ligne.
  
 
<source language="java">
 
<source language="java">
Line 252: Line 251:
 
</source>
 
</source>
  
The cache size is reasonably small and the LRUMap will make sure it will not grow beyond its capacity throwing out the oldest Groups/Children, when overflowing.
+
La taille de la cache est raisonnablement petite et le LRUMap va s'assurer qu'elle ne grossit pas au-delà de ses capacités en éliminant les vieux Groups/Children lorsqu'il y débordement.
  
The disadvantage of this approach is, that in most cases at least two chunks need to be loaded to display a single page, however when caching a few of these chunks in the model, you'll have one of the two already loaded for the previous page no matter which direction you navigate.
+
Le désavantage des cette approche est que, dans la plupart des cas, au moins deux ensembles doivent être chargés pour afficher une seule page, cependant lors de la mise en cache d'un petit nombre, un des deux aura déjà été chargé pour la page précédente peut importe la direction dans laquelle vous naviguez.
  
I think the better cachability outrules the slight memory overhead. At a page size of 50, we might have 49 records too much in memory (which will likely be reused on the next page, when the user navigates, by one Page). But reducing the permutations of method/query parameters by 98% which highly improves the chance of a cache hit at method or DB level. I would even keep the cache bigger, so that back navigation by few pages does not cause a reload.
+
Je pense que la meilleur possibilité de mise en cache élimine le léger dépassement de mémoire. Sur une page de taille 50, on pourrait avoir 49 enregistrements de trop en mémoire (qui seront peut-être réutilisés sur la page suivante lorsque l'utilisateur navigue ou par une autre Page). Mais réduire les permutations des paramètres des méthodes/requêtes par 98%, ce qui augmente fortement la nécessité de cache, a un impact au niveau de la méthode ou de la  DB. Je garderai même la cache plus grande de sorte qu'en cas de navigation arrière, cela n'engendre pas de rechargement.
  
Also very small groups will result in more DB round trips, but hey ... we are talking about BIG data :)
+
Aussi, des groupes très petits engendrerons plus d'aller-retours vers la DB, mais bon ... on parle ici de GROSSES quantités de données :)
  
==Random Access Paging==
+
==Pagination à accès aléatoire==
  
When just navigating page by page, this would already be sufficient... but what if you want to navigate to page no 234.455.234 :-o  
+
Lors d'une simple navigation page par page, ce serait déjà suffisant... mais si vous voulez naviguer vers la page no 234.455.234 ? :-o  
  
This is no problem when Groups are closed by default, as each group will only consist of a Head (or Head and Foot).
+
Il n'y a pas de problèmes quand les Groups sont fermés par défaut vu que chaque groupe consiste simplement en un Head (entête) (ou Head et Foot).
  
If pages are open by default you suddenly encounter a question you might not even have thought about before, when doing pagination in a flat list without the grouping level - plus some groups open/closed.
+
Si, par défaut, les pages sont ouvertes, vous est soudainement confronté à une question à laquelle vous n'auriez même pas songé avant, lorsque vous faisiez de la pagination sur une liste plate sans le niveau de groupement - plus quelques groupes ouvert/fermé.
  
''Which group- / child-index does page X start with??''
+
''Avec quel index de groupe- / enfant la page X démarre-t-elle??''
  
The brute force way of just iterating over all the groups accumulating their size until the (page * pageSize) is reached is not feasible.
+
La manière brute qui consiste à itérer sur tous les groupes en accumulant leurs tailles jusqu'à atteindre le nombre adéquat (page * TailleDePage) n'est pas réalisable.
It will either cause many DB operations, or one big traversal over a huge result set of Group counts (Keep in mind, we don't know how many groupCounts we need to accumulate until we reach page X).
+
Cela va provoquer beaucoup d'opération DB ou un grand travail sur un grand nombre de compteurs de groupes. (Gardons en mémoire qu'on ne connait pas le nombre de groupCounts à accumuler pour atteindre la page X).
  
I am not a DB expert, so maybe there is a solution for this problem already present at DB level (and we'd have to adjust the result by the number of closed nodes the DB does not know about) and I am not a scientist so there is maybe a more sophisticated perfectly balanced search algorithm - Please comment if you know :)
+
Je ne suis pas un expert DB, il existe donc peut-être déjà une solution à ce problème au niveau de la DB (et nous devrions ajuster ce résultat en fonction du nombre de nœuds fermés que la DB ne connait d'ailleurs pas) et je ne suis pas un scientifique, il y a donc peut-être aussi un algorithme de recherche plus sophistiqué - Merci de commenter si vous en connaissez un :)
  
So here is my approach which will keep the required DB operations at a low level, and again provide high chance for cache hits, especially for the most expensive often recurring count operations.
+
Voici donc mon approche qui va garder le nombre d'opérations DB requises à un niveau faible et qui augmentera les chances de trouver dans la cache, en particulier pour les opération de comptage qui sont très coûteuses et très récurrentes.
  
A binary search:
+
Une recherche binaire:
  
1. Bisect the number of groups into Ranges and have the DB count the rows for that range
+
1. Découpez le nombre de groupes en "Ranges" et laisser la DB compter le nombre de lignes pour ce "Range"
: (I am sure the DB is faster than you in java code (assuming efficient indexing) ;)) e.g.
+
: (Je suis certain que la DB est plus rapide que vous avec le code java (en supposant une indexation efficace) ;)) p.e.
 
: <code>SELECT count(*) WHERE group_key >= x AND group_key < y</code>
 
: <code>SELECT count(*) WHERE group_key >= x AND group_key < y</code>
  
2. Check whether the result (adjusted by group-heads(, -feet) and the toggled groups) is bigger or smaller.
+
2. Regardez si le résultat (ajusté en fonction des group-heads(, -feet) et les groupes dont l'état a été inversé) est plus grand ou plus petit.
  
3. Define the next smaller range always halving the intervals.
+
3. Définissez le plus petit "Range" suivant en continuant le découpage en deux des intervalles.
  
Repeat 1-3 until you find the group.
+
Répétez 1 à 3 jusqu'à ce que vous trouviez le groupe.
  
* For 1024 groups you won't have to repeat that more than 9 times until you find the group we are interested in.
+
* Pour 1024 groupes, vous n'aurez pas à le faire plus de 9 fois avant de trouver le groupe qui vous intéresse.
* For 1024 * 1024 (about a million) it is only 19 times
+
* Pour 1024 * 1024 (environ un million) c'est seulement 19 fois
* For 1024 * 1024 * 1024 (about a billion) it is only 29 times
+
* Pour 1024 * 1024 * 1024 (environ un milliard) c'est seulement 29 fois
  
So you see this scales well 2x the data, requires only 1 additional DB round trip.
+
Vous voyez donc bien ces échelles de 2x la donnée qui nécessitent seulement un aller-retour supplémentaire dans la DB.
  
When starting with 1024 Groups a possible sequence of ranges might be
+
En démarrant avec 1024 Groups, une séquence possible de "ranges" serait
 
# 0 < 512 (WHERE group_key >= 0 AND group_key < 512)
 
# 0 < 512 (WHERE group_key >= 0 AND group_key < 512)
 
# 0 < 256 ...
 
# 0 < 256 ...
Line 304: Line 303:
 
# 156 < 160
 
# 156 < 160
 
# 156 < 158
 
# 156 < 158
# 157 < 158 :D the page start must be in in group #157
+
# 157 < 158 :D le début de la page se trouve dans le groupe #157
  
Another positive sideeffect: The most counting intensive queries will only have little variance in their query parameters, so they will be most likely in the cache already, and the memory consumption for one cache entry is very low... 3 integers (range starts and end as cache key, and another integer for the count) -> Caching a few hundred(or thousand) of those results does not weigh too much, in contrast to caching each group count in memory (that's up to the DB)
+
Une autre conséquence positive: les requêtes les plus complexes n'auront que peu de variation dans leurs paramètres, elle seront donc pratiquement déjà en cache, et la consommation mémoire pour une entrée dans la cache est très faible... 3 entiers (début de range et fin de range comme clé de cache et un autre entier pour le compteur) -> Mettre en cache quelques centaines (ou milliers) de ces résultats ne pèse pas trop lourd en comparaison avec la mise en cache de chaque compteur de groupe dans la mémoire (ça dépend de la DB)
  
1st query is always the same
+
La 1ère requête est toujours la même,
2nd query has only 2 options
+
La 2ème requête a seulement deux options,
3rd query has 4 options  
+
La 3ème requête a 4 options
 
...
 
...
  
Still we have a penalty of several DB queries for a random access to a page, but after that the cache is hot, and single page navigation will take a similar path in the binary search, causing much fewer cache misses (except for some rare cases, where you cross the boundary of a bigger range, but still the penalty will never be as big as the first request). Additionally the ranges will be the same for concurrent users, offering the possibility to cache at a lower application level too.
+
Nous avons certes une pénalité de quelques requêtes DB pour un accès aléatoire à une page, mais après cela, la cache est prête et la navigation sur une page unique prendra un chemin similaire dans la recherche binaire, provoquant moins de ratés dans la cache (à l’exception e quelques cas rares, lorsque vous passez la limite d'un range plus gros, mais la pénalité ne sera jamais aussi grosse que la première requête). De plus, les "ranges" seront les mêmes pour des utilisateurs concurrents, donnant aussi la possibilité de mettre en cache à un niveau applicatif plus bas.
  
Since the user will most likely begin from the first page, I added an alternative approach starting from group zero, like a bottom-up search, doubling the ranges in each iteration until the searchIndex is exceeded and then refine the result reusing the binary approach.
+
Vu que l'utilisateur va plus que probablement démarrer depuis la première page, j'ai ajouté une approche alternative en commençant du groupe zéro, comme une recherche de bas en haut, doublant les "ranges" à chaque itération jusqu'à ce que l'index de recherche soit dépassé et ensuite affine le résultat en réutilisant l'approche binaire.
This postpones the expensive counting operations to a time when a "random access occurs"... as I said I am not a Scientist, so I just defined a threshold for the searchIndex. For bigger search indexes the top-to-bottom search is used.
+
Ceci reporte les opération de comptage très coûteuses à un moment où "un accès aléatoire survient"... comme j'ai dit je ne suis pas un scientifique, j'ai donc défini un seuil pour le searchIndex. Pour des index de recherches plus grands, la recherche de haut en bas est utilisée.
  
For the case someone has a better strategy, I extracted the GroupingPositionSearch interface for everyone to implement themselves (maybe a pure DB stored procedure).
+
Dans le cas où quelqu'un aurait une meilleure stratégie, j'ai extrait l’interface GroupingPositionSearch pour que tout le monde puisse l'implémenter par lui-même (peut-être une procédure pure de stockage en DB).
  
See:  
+
Voir:  
 
* org.zkoss.grouping.model.search.GroupingPositionSearch
 
* org.zkoss.grouping.model.search.GroupingPositionSearch
 
* org.zkoss.grouping.model.search.LinearGroupingPositionSearch
 
* org.zkoss.grouping.model.search.LinearGroupingPositionSearch
: an implementation for fun... to compare the performance difference
+
: une implémentation pour le fun... pour comparer la différence des performances
 
* org.zkoss.grouping.model.search.BinaryGroupingPositionSearch
 
* org.zkoss.grouping.model.search.BinaryGroupingPositionSearch
: all one needs is to implement the method getChildCountBetween() and query the DB
+
: les seuls besoins sont d'implémenter la méthode getChildCountBetween() et interroger la DB
  
Enough pseudo theoretical talk ... let's use this!
+
Assez de blabla pseudo-théorique ... utilisons cela!
  
=Using the Model in the UI=
+
=Utiliser le Model dans l'UI=
  
We have seen how to access the data, and how the caching will hopefully have some positive effects. So all that remaining is the ViewModel, and the View.
+
Nous avons vu comment accéder aux données et comment la mise en cache devrait avoir des effets positifs. Il reste donc à voir le ViewModel et le View.
  
 
==accesslog_mvvm.zul==
 
==accesslog_mvvm.zul==
Line 381: Line 380:
 
</source>
 
</source>
  
As you can see this is just a pretty basic Grouping Grid not using the "paging"-mold, but a separate paging control, as we only send a delegating Model (model="@load(vm.currentPageModel)") to the <grid> component. This is to only present as little information to the grid component as possible to avoid the component grid from caching data internally, and to gain full control over what is loaded.
+
Comme vous pouvez le voir, c'est simplement une Grouping Grid de base qui n'utilise pas le moule "paging" mais un contrôle de pagination séparé vu qu'on envoie seulement un Model délégué (model="@load(vm.currentPageModel)") au composant <grid>. On fait ceci pour présenter au composant grid aussi peu d'informations que possible, ce qui lui évite de mettre en cache interne des données et aussi d'avoir le contrôle total de ce qui est chargé.
  
Because the Grid component expect groups to open and close in a consistent way, a dummy head and/or foot needs to be added if a Page does not start with a group head, or end with a foot. (this is slightly unpleasant, but what do we get in return) ... the biggest ZK grouping grid ever.
+
Vu que le composant Grid s'attend à ce que les groupes s'ouvrent et se ferment de façon cohérente, un en-tête et/ou pied de page nominal doit être ajouté si une Page ne commence pas avec un début de groupe ou ne s'achève pas avec une fin de groupe. (c'est assez déplaisant, mais qu'avons nous en retour) ... la plus grande grille de groupement ZK de tous les temps.
  
 
==AccessDataGroupingViewModel==
 
==AccessDataGroupingViewModel==
Line 447: Line 446:
 
</source>
 
</source>
  
Besides the currently somewhat dodgy call to groupsModel.getSinglePageModel() to get the fake group models there is nothing remarkable here either
+
A part l'appel quelque peu douteux à groupsModel.getSinglePageModel() pour recevoir les faux groupes de données, il n'y a rien de remarquable ici:
* initialize the model
+
* initialisation du model
* handle paging events (updateOffsetIndex(x) in the delegating page model)
+
* gestion des paging events (updateOffsetIndex(x) dans le page model délégué)
  
The rest is done in PagingGroupsModel.
+
Le reste est fait dans PagingGroupsModel.
  
=Running the demo application=
+
=Lancer l'application démo=
  
==Using Maven==
+
==En utilisant Maven==
  
Unzip the Package and execute the mvn command:
+
Dézippez le Package et exécutez la commande mnv suivante:
  
 
     mvn jetty:run
 
     mvn jetty:run
  
open this URL in browser:
+
Ouvrez cette URL dans un naviguateur:
 
: http://localhost:8080/hugeGrouping/accesslog_mvvm.zul
 
: http://localhost:8080/hugeGrouping/accesslog_mvvm.zul
  
The application will be very responsive, whereever you navigate, open/ close groups. Looking at the console log, you'll get some information about Cache hits and Cache MISSES, notice the high number of cache hits after randomly navigating to a high page, and then visiting the next/previous page.
+
L'application sera efficace lorsque vous ouvrirez/fermerez des groupes, peut importe l'endroit où vous naviguez. Jetez un coup d’œil à la console des logs pour avoir des informations sur la cache. Notez le nombre élevé de trouvailles dans la cache après une navigation aléatoire dans une page et en visitant ensuite les pages suivantes/précédentes.
  
The initial setup of the AccessLogDao (mock) is 40 million groups with 8 to 88 children randomly distributed, so we roughly end up with 2 BILLION rows.
+
La configuration initiale d'AccessLogDao (mock) est de 40 millions de groupes avec 8 à 88 enfants distribués de façon aléatoire. On a donc environ 2 milliards de lignes.
  
The memory consumption will remain stable once the Dao is initialized (these 160MB - mentioned above - would usually be on the DB and not in memory) when navigating the list.
+
La consommation mémoire restera stable quand le Dao sera initialisé (ces 160MB - mentionnés plus haut - devraient habituellement se trouver dans la DB et non dans la mémoire) lors de la navigation dans la liste.
Once the cache of the binary grouping position search is hot, the number of DB calls is low (usually around 1-4 less frequently bigger) per page increment / decrement, after randomly accessing any arbitrary page (despite some special cases - traversing the bounds of a big binary search region).
+
Lorsque la cache de la recherche de position de groupes tourne à plein rendement, le nombre d'appels vers la DB est faible (de 1 à 4 fois plus petit) par page incrémentée / décrémentée, après un accès aléatoire à une page arbitraire (à part quelques cas spéciaux - dépasser les limites d'une grande région de recherche binaire).
  
And the data returned from the DB is very little:
+
Les données renvoyées par la DB sont très petites:
  
* loading 1 or 2 (or several very small) group children chunks (each of page size)
+
* charger 1 ou 2 (ou quelques très petits) morceaux des groupes enfants (chacun de la taille de la page)
* loading 0 or 1 new chunk(s) (of page size) of group information (without the children payload)
+
* charger 0 ou 1 nouveau(x) morceau(x) (de la taille de page) d'information de groupes (sans la charge que représente les enfants)
* usually a small number of requests that earn Cache MISSES during the binary searches for the next page's startIndex.  
+
* généralement un petit nombre de requêtes qui évite les MISSES au cours de la recherche binaire pour l'index de début de la page suivante.  
** This could be improved with a little more decisive paging event handler being aware of single page increments / decrements. To keep the sample simple we treat every position search as a random access, and still have good performance without special case handling.
+
** En tenant compte des incréments/décréments de pages simples, on peut améliorer ceci avec un gestionnaire d’événement de pagination. Pour garder l'exemple simple, on traite chaque recherche de position comme étant un accès aléatoire et nous gardons toujours une bonne performance sans traitement spécifique.
  
==War File==
+
==Fichier War==
  
If you cannot (don't want to) use maven there is also a war-file available for download. It can be deployed into an existing web app server (e.g. [[http://tomcat.apache.org/download-70.cgi Tomcat]])
+
Si vous ne pouvez pas (ne voulez pas) utiliser maven, il y a aussi un ficher war disponible pour téléchargement. Il peut être déployé dans un serveur d'applications web existant (p.e. [[http://tomcat.apache.org/download-70.cgi Tomcat]])
  
 
=Appendix=
 
=Appendix=
==Download==
+
==Téléchargement==
  
download maven project [http://sourceforge.net/projects/zkforge/files/Small%20Talks/Huge%20Data%20Grouping/hugeGrouping.zip/download hugeGrouping.zip (~24.7 kB)]
+
Télécharger le projet maven [http://sourceforge.net/projects/zkforge/files/Small%20Talks/Huge%20Data%20Grouping/hugeGrouping.zip/download hugeGrouping.zip (~24.7 kB)]
  
download as war-file [http://sourceforge.net/projects/zkforge/files/Small%20Talks/Huge%20Data%20Grouping/hugeGrouping.war/download hugeGrouping.war (~25 MB)]
+
Télécharger le fichier war [http://sourceforge.net/projects/zkforge/files/Small%20Talks/Huge%20Data%20Grouping/hugeGrouping.war/download hugeGrouping.war (~25 MB)]
  
=Comments=
+
=Commentaires=
 
{{#tag:comment
 
{{#tag:comment
 
|http://books.zkoss.org/wiki/{{SUBJECTPAGENAME}}|disqus=1
 
|http://books.zkoss.org/wiki/{{SUBJECTPAGENAME}}|disqus=1

Latest revision as of 05:59, 8 April 2014

DocumentationSmall Talks2013SeptemberZK Huge Grouping Model fr
ZK Huge Grouping Model fr

Author
Robert Wenzel, Engineer, Potix Corporation
Date
September 24, 2013
Version
ZK 6.5 (or later)


Introduction

Vous avez parfois une énorme quantité de données dans votre base de données et vous souhaitez les afficher dans une Grid ou une Listbox ZK en utilisant le groupement de données. Bien entendu, vous souhaitez utiliser une pagination parce-que la liste est bien trop grande que pour être affichée sur une seule page. Ou alors, vous voulez éviter un message 'timeout' ou "OutOfMemoryError" lors de la lecture / du parcours de ce grand nombre d'enregistrements (voir même un nombre inconnu).

Pour une liste simple, référez vous à ce sujet déjà abordé dans le Small Talks içi.

Sur bases des certains concepts (pagination au niveau de la DB et séparation du contrôle de la pagination de la grid) cet article propose une stratégie et présente un exemple implémenté de comment faire du groupement de données à l'identique.

Cependant, les choses se compliquent ici quelques peu... j'espère donc au final donner une idée de comment ZK masque les parties compliquées, et laisse le développeur se concentrer sur la récupération et l'affichage des données.

Les défis

Le Groupement est une caractéristique puissante de ZK mais qui amène aussi une couche supplémentaire de complexité.

Certains pourraient se demander s'il est utile d'afficher une liste aussi longue de cette manière (en particulier sans pré-filtrage des résultats).

Nous sommes ici pour montrer que c'est possible possible, jusqu'à quelles limites ... et bien, ZK GroupsModel supporte des index de type int, nous pouvons donc aller jusqu'à environ Integer.MAX_VALUE (~ 2.000.000.000 enregistrements - 2 milliards)

Les défis de la pagination et du regroupement

1. Les groupes peuvent être ouverts ou fermés (initialement ou de façon interactive)

-> Le nombre total et le nombre de pages changent à l'ouverture/la fermeture des nœuds d'index (nodes)... ceci requiert un comptage efficace et continuellement à jour

2. Les groupes peuvent avoir un nombre arbitraire d'enfants

-> L'accès aléatoire à une page spécifique peut devenir délicat ... comment connaitre le groupe actuel et la position à l'intérieur de ce groupe pour cette page
--> Comment implémenter une recherche réalisable ?

3. Minimiser les opérations DB (accumulation des latences réseau/DB)

-> Prendre en considération la mise en cache versus la consommation de la mémoire

1. + 2. + 3. Cet article va expliquer comment combiner ces trois aspects de manière efficace en préservant la mémoire (presque prévisible) et quelques compromis qui doivent être faits. Aussi, quelques points d'extension sont mis en évidence, où, si possible, la mise en oeuvre d'usage général peut être remplacée par une autre plus spécifique, en fonction des détails de votre propre modèle de données.

Quelques limites

  • Cet exemple fonctionne uniquement sur des données statiques - si les données changent, le modèle doit être réinitialisé et les caches doivent être vidées.
  • Vu que toutes les lignes ne sont pas présentes en mémoire, vous pouvez envoyer des événements UI à des composants qui ne sont pas affichés à l'écran (vous manipulez l'état du modèle à la place)
  • L'état ouvert/fermé est stocké en mémoire ("les humains ont des limites", il est peu probable de dépasser les 100 groupes) - Il ne devrait donc pas y avoir de problème.
  • Certains composants "maquettes" sont nécessaires pour que le <grid> accepte la vue limitée (fenêtrée) sur les données.

Implémentation

Le package exemple est un projet maven, avec la structure suivante:

HugeGrouping files.png

Le dossier "src" contient les différents fichiers/dossiers/packages:

Classes génériques (expliqué plus bas):

org.zkoss.grouping.model
implémentation pagination générique GroupsModel
org.zkoss.grouping.model.search
implémentation des recherches de positions


Implémentations spécifiques à l'exemple (montrant l'utilisation des éléments ci-dessus)

org.zkoss.grouping.dao
Classe Dao en mémoire qui simule des grosses quantités de données
org.zkoss.grouping
Les implémentation du Composer actuel (MVC) / ViewModel (MVVM) et (Dao-backed) PagingGroupsModel

Fichiers ZUL correspondants (dans src/main/webapp):

accesslog.zul
utilisation MVC de PagingGroupsModel
accesslog_mvvm.zul
utilisation MVVM de PagingGroupsModel avec DelegatingSinglePageGroupsModel
accesslog_mvvm_default_paging.zul
Exemple MVVM mettant en évidence les problèmes de performance sans contrôle de pagination séparé, en utilisant un set de données plus petit

Accéder aux données

Data Record et Dao

Nous commencons avec un simple enregistrement de données représentant des access logs.

package org.zkoss.grouping.dao;

import java.util.Date;

public class AccessDataRecord {
	private String ipAddress;
	private String browser;
	private long contentLength;
	private String country;
	private Date accessTime;
	private String url;

//... Constructor + getters

L'AccessDataDao est une implémentation mock générant les données à la volée sans utiliser une DB (juste des valeurs aléatoires) et qui stocke la taille des groupes en mémoire.

Donc, en oubliant la génération de données aléatoire, votre Dao devrait implémenter les 5 opérations suivantes suivant des requêtes SQL/HQL/Criteria/noSQL. Je suis conscient que compter des grandes quantités de données au niveau de la DB n'est pas chose simple. Il faut toujours préparer les données au niveau de la DB: ex. indexation propre, pré agrégation des groupes/compteurs (rien en quoi le 'front end framework' peut vous aider).

package org.zkoss.grouping.dao;

public class AccessLogDao {

	public int getGroupCount() {
		//your DB query to count the groups
	}

	public List<GroupInfo<String, String>> getGroupInfos(int startIndex, int pageSize) {
		//your DB query and mapping to create GroupInfos for this page of groups
	}

	public List<AccessDataRecord> getChildInfos(int groupIndex, int startIndex, int pageSize) {
		//your DB query and load this page of children in the group
	}

	/**
	 * This method will count a lot and return a constant value as long as data does not change, 
	 * so caching would be desirable
	 * @return
	 */
	public int getTotalChildCount() {
		//your DB impl to calc the total number of children
	}

	/**
	 * This method will be called quite often with recurring parameters, 
	 * so caching (of most frequently used params) would be desirable !!!
	 * @return the childrenCount between 2 groups... (including groupIndexFrom and excluding groupIndexTo)
	 */
	public int getChildCountBetween(int groupIndexFrom, int groupIndexTo) {
		//your DB impl to calc the number of children between 2 groups
	}

Le modèle de pagination

AccessDataGroupsModel, notre PagingGroupsModel<D, H, F> spécialisé utilise une implémentation d'AccessDataRecord comme "data"(D) et String comme "head"(H) et "foot"(F). Cette classe implémente les 4 méthodes du modèle et une stratégie GroupingPositionSearch - tout en déléguant à AccessLogDao d'en haut, pour garder la charge de travail au niveau de la DB.

package org.zkoss.grouping;

import java.util.List;

import org.zkoss.grouping.dao.AccessLogDao;
import org.zkoss.grouping.dao.AccessDataRecord;
import org.zkoss.grouping.model.GroupInfo;
import org.zkoss.grouping.model.PagingGroupsModel;
import org.zkoss.grouping.model.search.BinaryGroupingPositionSearch;
import org.zkoss.grouping.model.search.GroupingPositionSearch;

class AccessDataGroupsModel extends
		PagingGroupsModel<AccessDataRecord, String, String> {

	private AccessLogDao groupsDao;

	public AccessDataGroupsModel(AccessLogDao groupsDao, int pageSize, boolean initialOpen, boolean hasGroupfoot) {
		super(pageSize, initialOpen, hasGroupfoot);
		this.groupsDao = groupsDao;
		setPositionSearch(binarySearch());
	}

	@Override
	protected int loadGroupCount() {
		return groupsDao.getGroupCount();
	}

	@Override
	protected List<GroupInfo<String, String>> loadGroupPage(int startIndex, int pageSize) {
		return groupsDao.getGroupInfos(startIndex, pageSize);
	}

	@Override
	protected List<AccessDataRecord> loadChildrenPage(int groupIndex, int startIndex, int pageSize) {
		return groupsDao.getChildInfos(groupIndex, startIndex, pageSize);
	}

	@Override
	protected int getTotalChildCount() {
		return groupsDao.getTotalChildCount();
	}

	private GroupingPositionSearch binarySearch() {
		return new BinaryGroupingPositionSearch(this, 4096) {
			@Override
			protected int getChildCountBetween(int groupIndexFrom, int groupIndexTo) {
				return groupsDao.getChildCountBetween(groupIndexFrom, groupIndexTo);
			}
		};
	}

}

Comme nous pouvons le voir, les méthodes se concentrent sur le comptage et la récupération des données dans des morceaux de la taille d'une page. Rien de magique ici, pendant que notre DB fait le travaille difficile (sélection, groupement, comptage, tri) ... c'est à ça que ça sert. Et avec des grosses quantités de données, nous n'allons pas essayer de battre la DB, nous voulons seulement des données aussi petites que possible. Votre administrateur DB sera heureux de vous aider à optimiser vos requêtes et préparer vos données. ;-)

Page/Caching, Comptage & conserver l'état ouvert/fermé

Conserver l'état ouvert/fermé

Le PagingGroupsModel va garder une trace des états ouvert/fermé pour les groupes dont l'état a été modifié (avec en même-temps le childCount de ce groupe).

Si le Model est initialisé avec INITIALLY_OPEN, alors on gardera la trace uniquement des 'nodes' fermés, et vice versa.

En supposant qu'un humain ne prendra pas le temps de changer l'état d'un nombre immense de groupes, cette Map (groupIndex => childcount) restera relativement petite et ne devrait pas compromettre notre performance ainsi que nos attentes au niveau de la mémoire. De plus, le nombre total de groupes dont l'état a été modifié est mis à jour à chaque interaction ouvert/fermé.

Cette information est utilisée pour ajuster le nombre total d'enfants (pour le calcul de pagination UI) ou le nombre d'enfants entre deux groupes (pour la recherche de Position) - vu que la DB ne gardera pas cet état UI.

Voir:

  • PagingGroupsModel#getCurrentRowCount()
  • PagingGroupsModel#getToggledCountBetween(int groupIndexFrom, int groupIndexTo)
  • PagingGroupsModel#toggleGroup(int groupIndex, boolean open)

Page/Caching

L'interface GroupsModel (ZK default) offre des méthodes pour récupérer les single Groups, et les Children (enfants). PagingGroupsModel implémente cette interface. Lorsqu'une de ces méthodes est appelée, le PagingGroupsModel va vérifier si cette position est mise en cache pour la page courante et si pas, (re)charge un morceau de page de taille équivalente de données depuis la DB et les mes dans les caches respectives.

Un problème apparaît ici, la taille des données récupérées de la DB ne correspond pas aux limites de la page dans l'UI.

e.g.

    1         2         3         4                
    |.........|.........|.........|.........           -> UI pages (page size 10)

    0.....1.........|......2...3......4....5           -> Groups | Chunks Group 0 open
    01.........|......2...3......4....5.....           -> Groups | Chunks Group 0 closed

Taille de la page vs. Taille du groupe: Alors que les pages de l'UI ont des tailles constantes, les groupes eux peuvent avoir des tailles variables, et leur offset peut être décalé à cause des nodes ouvert/fermé, l'offset des morceaux chargés depuis la DB vont varier lorsque l'état des nodes est modifié.

Vu que nous cherchons à profiter de la mise en cache à tous les niveaux possibles, gardons les paramètres des méthodes/requêtes constants et nous réduirons ainsi la taille de la cache nécessaire au niveau de la méthode Dao ou dans la DB, et cela permettra aussi d'éviter le chargement chevauché de groupes de données (avec des utilisateurs multiples qui ont des états UI différents).

Donc, dans le scénario ci-dessus, lorsque p.e. Element 3 du Group 1 doit être chargé, le PagingGroupsModel va charger le groupe "Group1 Child0-9" en appelant this.loadChildrenPage(1, 0, 10). Parfait pour la mise en cache, vu qu'il n'appellera jamais p.e. this.loadChildrenPage(1, 3, 10).

Voir:

  • AccessDataGroupsModel#loadGroupPage(int startIndex, int pageSize)
  • AccessDataGroupsModel#loadChildrenPage(int groupIndex, int startIndex, int pageSize)

La même stratégie s'applique pour la mise en cache des Groups. PagingGroupsModel va aussi charger un ensemble de Groups avec des intervalles fixes. Si les groupes sont affichés avec un 'foot', la taille en cache des groupes peut être réduite de moitié vu que le foot du groupe va aussi consommer une ligne.

cachedGroups = Collections.synchronizedMap(new LRUMap(pageSize * (hasGroupFoot ? 1 : 2))); //cache at least 2 pages ...
cachedChildren = Collections.synchronizedMap(new LRUMap(pageSize * 4)); //cache enough for at least a few pages

La taille de la cache est raisonnablement petite et le LRUMap va s'assurer qu'elle ne grossit pas au-delà de ses capacités en éliminant les vieux Groups/Children lorsqu'il y débordement.

Le désavantage des cette approche est que, dans la plupart des cas, au moins deux ensembles doivent être chargés pour afficher une seule page, cependant lors de la mise en cache d'un petit nombre, un des deux aura déjà été chargé pour la page précédente peut importe la direction dans laquelle vous naviguez.

Je pense que la meilleur possibilité de mise en cache élimine le léger dépassement de mémoire. Sur une page de taille 50, on pourrait avoir 49 enregistrements de trop en mémoire (qui seront peut-être réutilisés sur la page suivante lorsque l'utilisateur navigue ou par une autre Page). Mais réduire les permutations des paramètres des méthodes/requêtes par 98%, ce qui augmente fortement la nécessité de cache, a un impact au niveau de la méthode ou de la DB. Je garderai même la cache plus grande de sorte qu'en cas de navigation arrière, cela n'engendre pas de rechargement.

Aussi, des groupes très petits engendrerons plus d'aller-retours vers la DB, mais bon ... on parle ici de GROSSES quantités de données :)

Pagination à accès aléatoire

Lors d'une simple navigation page par page, ce serait déjà suffisant... mais si vous voulez naviguer vers la page no 234.455.234 ? :-o

Il n'y a pas de problèmes quand les Groups sont fermés par défaut vu que chaque groupe consiste simplement en un Head (entête) (ou Head et Foot).

Si, par défaut, les pages sont ouvertes, vous est soudainement confronté à une question à laquelle vous n'auriez même pas songé avant, lorsque vous faisiez de la pagination sur une liste plate sans le niveau de groupement - plus quelques groupes ouvert/fermé.

Avec quel index de groupe- / enfant la page X démarre-t-elle??

La manière brute qui consiste à itérer sur tous les groupes en accumulant leurs tailles jusqu'à atteindre le nombre adéquat (page * TailleDePage) n'est pas réalisable. Cela va provoquer beaucoup d'opération DB ou un grand travail sur un grand nombre de compteurs de groupes. (Gardons en mémoire qu'on ne connait pas le nombre de groupCounts à accumuler pour atteindre la page X).

Je ne suis pas un expert DB, il existe donc peut-être déjà une solution à ce problème au niveau de la DB (et nous devrions ajuster ce résultat en fonction du nombre de nœuds fermés que la DB ne connait d'ailleurs pas) et je ne suis pas un scientifique, il y a donc peut-être aussi un algorithme de recherche plus sophistiqué - Merci de commenter si vous en connaissez un :)

Voici donc mon approche qui va garder le nombre d'opérations DB requises à un niveau faible et qui augmentera les chances de trouver dans la cache, en particulier pour les opération de comptage qui sont très coûteuses et très récurrentes.

Une recherche binaire:

1. Découpez le nombre de groupes en "Ranges" et laisser la DB compter le nombre de lignes pour ce "Range"

(Je suis certain que la DB est plus rapide que vous avec le code java (en supposant une indexation efficace) ;)) p.e.
SELECT count(*) WHERE group_key >= x AND group_key < y

2. Regardez si le résultat (ajusté en fonction des group-heads(, -feet) et les groupes dont l'état a été inversé) est plus grand ou plus petit.

3. Définissez le plus petit "Range" suivant en continuant le découpage en deux des intervalles.

Répétez 1 à 3 jusqu'à ce que vous trouviez le groupe.

  • Pour 1024 groupes, vous n'aurez pas à le faire plus de 9 fois avant de trouver le groupe qui vous intéresse.
  • Pour 1024 * 1024 (environ un million) c'est seulement 19 fois
  • Pour 1024 * 1024 * 1024 (environ un milliard) c'est seulement 29 fois

Vous voyez donc bien ces échelles de 2x la donnée qui nécessitent seulement un aller-retour supplémentaire dans la DB.

En démarrant avec 1024 Groups, une séquence possible de "ranges" serait

  1. 0 < 512 (WHERE group_key >= 0 AND group_key < 512)
  2. 0 < 256 ...
  3. 128 < 192
  4. 128 < 160
  5. 144 < 160
  6. 152 < 160
  7. 156 < 160
  8. 156 < 158
  9. 157 < 158 :D le début de la page se trouve dans le groupe #157

Une autre conséquence positive: les requêtes les plus complexes n'auront que peu de variation dans leurs paramètres, elle seront donc pratiquement déjà en cache, et la consommation mémoire pour une entrée dans la cache est très faible... 3 entiers (début de range et fin de range comme clé de cache et un autre entier pour le compteur) -> Mettre en cache quelques centaines (ou milliers) de ces résultats ne pèse pas trop lourd en comparaison avec la mise en cache de chaque compteur de groupe dans la mémoire (ça dépend de la DB)

La 1ère requête est toujours la même, La 2ème requête a seulement deux options, La 3ème requête a 4 options, ...

Nous avons certes une pénalité de quelques requêtes DB pour un accès aléatoire à une page, mais après cela, la cache est prête et la navigation sur une page unique prendra un chemin similaire dans la recherche binaire, provoquant moins de ratés dans la cache (à l’exception e quelques cas rares, lorsque vous passez la limite d'un range plus gros, mais la pénalité ne sera jamais aussi grosse que la première requête). De plus, les "ranges" seront les mêmes pour des utilisateurs concurrents, donnant aussi la possibilité de mettre en cache à un niveau applicatif plus bas.

Vu que l'utilisateur va plus que probablement démarrer depuis la première page, j'ai ajouté une approche alternative en commençant du groupe zéro, comme une recherche de bas en haut, doublant les "ranges" à chaque itération jusqu'à ce que l'index de recherche soit dépassé et ensuite affine le résultat en réutilisant l'approche binaire. Ceci reporte les opération de comptage très coûteuses à un moment où "un accès aléatoire survient"... comme j'ai dit je ne suis pas un scientifique, j'ai donc défini un seuil pour le searchIndex. Pour des index de recherches plus grands, la recherche de haut en bas est utilisée.

Dans le cas où quelqu'un aurait une meilleure stratégie, j'ai extrait l’interface GroupingPositionSearch pour que tout le monde puisse l'implémenter par lui-même (peut-être une procédure pure de stockage en DB).

Voir:

  • org.zkoss.grouping.model.search.GroupingPositionSearch
  • org.zkoss.grouping.model.search.LinearGroupingPositionSearch
une implémentation pour le fun... pour comparer la différence des performances
  • org.zkoss.grouping.model.search.BinaryGroupingPositionSearch
les seuls besoins sont d'implémenter la méthode getChildCountBetween() et interroger la DB

Assez de blabla pseudo-théorique ... utilisons cela!

Utiliser le Model dans l'UI

Nous avons vu comment accéder aux données et comment la mise en cache devrait avoir des effets positifs. Il reste donc à voir le ViewModel et le View.

accesslog_mvvm.zul

	<window border="normal" height="810px" width="1200px" 
			apply="org.zkoss.bind.BindComposer" viewModel="@id('vm') 
			@init('org.zkoss.grouping.AccessDataGroupingViewModel')">
		
		<paging pageSize="@load(vm.pageSize)" 
			activePage="@bind(vm.activePage)" 
			totalSize="@load(vm.totalSize)"
			onPaging="@command('changePage', activePage=event.activePage)"
			detailed="true" />
			
		<grid model="@load(vm.currentPageModel)" >
			<columns>
				<column label="ip" ></column>
				<column label="url" ></column>
				<column label="time" ></column>
				<column label="country" ></column>
				<column label="browser" ></column>
				<column label="length" ></column>
			</columns>

			<template name="model:group">
				<group label="@init(each)" visible="@init(not(vm.isDummy(each)))" ></group>
			</template>
			
			<template name="model">
				<row>
					<label value="@init(each.ipAddress)"></label>
					<label value="@init(each.url)"></label>
					<label value="@init(each.accessTime)"></label>
					<label value="@init(each.country)"></label>
					<label value="@init(each.browser)"></label>
					<label value="@init(each.contentLength)"></label>
				</row>
			</template>
			<template name="model:groupfoot">
				<groupfoot visible="@init(not(vm.isDummy(each)))">
					<cell colspan="6" sclass="z-groupfoot-inner">
						<label value="@init(each)" sclass="z-groupfoot-cnt" />
					</cell> 
				</groupfoot>
			</template>
		</grid>
	</window>

Comme vous pouvez le voir, c'est simplement une Grouping Grid de base qui n'utilise pas le moule "paging" mais un contrôle de pagination séparé vu qu'on envoie seulement un Model délégué (model="@load(vm.currentPageModel)") au composant <grid>. On fait ceci pour présenter au composant grid aussi peu d'informations que possible, ce qui lui évite de mettre en cache interne des données et aussi d'avoir le contrôle total de ce qui est chargé.

Vu que le composant Grid s'attend à ce que les groupes s'ouvrent et se ferment de façon cohérente, un en-tête et/ou pied de page nominal doit être ajouté si une Page ne commence pas avec un début de groupe ou ne s'achève pas avec une fin de groupe. (c'est assez déplaisant, mais qu'avons nous en retour) ... la plus grande grille de groupement ZK de tous les temps.

AccessDataGroupingViewModel

public class AccessDataGroupingViewModel {
	private static final String DUMMY_FOOT = new String();
	private static final String DUMMY_HEAD = new String();
	//TODO: inject
	private AccessLogDao groupsDao = AccessLogDao.getInstance();
	private PagingGroupsModel<AccessDataRecord, String, String> groupsModel;
	
	private int pageSize;
	private int activePage;
	
	private DelegatingSinglePageGroupsModel<AccessDataRecord, String, String> currentPageModel;
	
	@Init
	public void init() {
		pageSize = 20;
		activePage = 0;
		groupsModel = new AccessDataGroupsModel(groupsDao, pageSize, 
				PagingGroupsModel.INITIALLY_OPEN, PagingGroupsModel.GROUPFOOT_ON);
		currentPageModel = groupsModel.getSinglePageModel(DUMMY_HEAD, DUMMY_FOOT, this, "totalSize");
		refreshRows();
	}
	
	@Command("changePage")
	@NotifyChange("currentPageModel")
	public void onChangePage() {
		refreshRows();
	}
	
	private void refreshRows() {
		currentPageModel.updateOffsetIndex(activePage * pageSize);
	}
	
	public int getPageSize() {
		return pageSize;
	}
	
	public int getActivePage() {
		return activePage;
	}
	
	public void setActivePage(int activePage) {
		this.activePage = activePage;
	}
	
	public int getTotalSize() {
		return groupsModel.getCurrentRowCount();
	}

	public GroupsModel<AccessDataRecord, String, String> getCurrentPageModel() {
		return currentPageModel;
	}
	
	public boolean isDummy(String string) {
		return DUMMY_HEAD == string || DUMMY_FOOT == string ;
	}
}

A part l'appel quelque peu douteux à groupsModel.getSinglePageModel() pour recevoir les faux groupes de données, il n'y a rien de remarquable ici:

  • initialisation du model
  • gestion des paging events (updateOffsetIndex(x) dans le page model délégué)

Le reste est fait dans PagingGroupsModel.

Lancer l'application démo

En utilisant Maven

Dézippez le Package et exécutez la commande mnv suivante:

   mvn jetty:run

Ouvrez cette URL dans un naviguateur:

http://localhost:8080/hugeGrouping/accesslog_mvvm.zul

L'application sera efficace lorsque vous ouvrirez/fermerez des groupes, peut importe l'endroit où vous naviguez. Jetez un coup d’œil à la console des logs pour avoir des informations sur la cache. Notez le nombre élevé de trouvailles dans la cache après une navigation aléatoire dans une page et en visitant ensuite les pages suivantes/précédentes.

La configuration initiale d'AccessLogDao (mock) est de 40 millions de groupes avec 8 à 88 enfants distribués de façon aléatoire. On a donc environ 2 milliards de lignes.

La consommation mémoire restera stable quand le Dao sera initialisé (ces 160MB - mentionnés plus haut - devraient habituellement se trouver dans la DB et non dans la mémoire) lors de la navigation dans la liste. Lorsque la cache de la recherche de position de groupes tourne à plein rendement, le nombre d'appels vers la DB est faible (de 1 à 4 fois plus petit) par page incrémentée / décrémentée, après un accès aléatoire à une page arbitraire (à part quelques cas spéciaux - dépasser les limites d'une grande région de recherche binaire).

Les données renvoyées par la DB sont très petites:

  • charger 1 ou 2 (ou quelques très petits) morceaux des groupes enfants (chacun de la taille de la page)
  • charger 0 ou 1 nouveau(x) morceau(x) (de la taille de page) d'information de groupes (sans la charge que représente les enfants)
  • généralement un petit nombre de requêtes qui évite les MISSES au cours de la recherche binaire pour l'index de début de la page suivante.
    • En tenant compte des incréments/décréments de pages simples, on peut améliorer ceci avec un gestionnaire d’événement de pagination. Pour garder l'exemple simple, on traite chaque recherche de position comme étant un accès aléatoire et nous gardons toujours une bonne performance sans traitement spécifique.

Fichier War

Si vous ne pouvez pas (ne voulez pas) utiliser maven, il y a aussi un ficher war disponible pour téléchargement. Il peut être déployé dans un serveur d'applications web existant (p.e. [Tomcat])

Appendix

Téléchargement

Télécharger le projet maven hugeGrouping.zip (~24.7 kB)

Télécharger le fichier war hugeGrouping.war (~25 MB)

Commentaires



Copyright © Potix Corporation. This article is licensed under GNU Free Documentation License.