D'abord un peu de contexte, solution à la fin :
Depuis la commande SCAN> Garantie de résiliation
L'algorithme SCAN est garanti de se terminer uniquement si la taille de la collection itérée reste limitée à une taille maximale donnée, sinon l'itération d'une collection qui grandit toujours peut entraîner SCAN pour ne jamais terminer une itération complète.
Ceci est facile à voir intuitivement :si la collection s'agrandit, il y a de plus en plus de travail à faire pour visiter tous les éléments possibles, et la possibilité de terminer l'itération dépend du nombre d'appels à SCAN et de la valeur de son option COUNT par rapport au taux à dont la collection s'agrandit.
Mais dans l'option COUNT, il est écrit :
Important :il n'est pas nécessaire d'utiliser la même valeur COUNT pour chaque itération. L'appelant est libre de changer le décompte d'une itération à l'autre selon ses besoins, tant que le curseur passé à l'appel suivant est celui obtenu lors de l'appel précédent à la commande.
Important à garder à l'esprit, à partir des garanties de Scan :
- Un élément donné peut être renvoyé plusieurs fois. Il appartient à l'application de gérer le cas des éléments dupliqués, par exemple en n'utilisant que les éléments retournés afin d'effectuer des opérations sûres lorsqu'elles sont réappliquées plusieurs fois.
- Les éléments qui n'étaient pas constamment présents dans la collection lors d'une itération complète, peuvent être renvoyés ou non :c'est indéfini.
La clé d'une solution se trouve dans le curseur lui-même. Voir Donner un sens au curseur SCAN de Redis. Il est possible d'en déduire le pourcentage d'avancement de votre scan car le curseur est en réalité les bits inversés d'un index à la taille de la table.
Utilisation de DBSIZE ou INFO keyspace commande, vous pouvez obtenir le nombre de clés dont vous disposez à tout moment :
> DBSIZE
(integer) 200032
> info keyspace
# Keyspace
db0:keys=200032,expires=0,avg_ttl=0
Une autre source d'informations est l'index DEBUG htstats index non documenté , juste pour avoir une idée :
> DEBUG htstats 0
[Dictionary HT]
Hash table 0 stats (main hash table):
table size: 262144
number of elements: 200032
different slots: 139805
max chain length: 8
avg chain length (counted): 1.43
avg chain length (computed): 1.43
Chain length distribution:
0: 122339 (46.67%)
1: 93163 (35.54%)
2: 35502 (13.54%)
3: 9071 (3.46%)
4: 1754 (0.67%)
5: 264 (0.10%)
6: 43 (0.02%)
7: 6 (0.00%)
8: 2 (0.00%)
[Expires HT]
No stats available for empty dictionaries
La taille du tableau est la puissance de 2 suivant votre nombre de clés :Clés :200032 => Taille du tableau :262144
La solution :
Nous calculerons un COUNT souhaité argument pour chaque analyse.
Dites que vous allez appeler SCAN avec une fréquence (F en Hz) de 10 Hz (toutes les 100 ms) et vous voulez que cela se fasse en 5 secondes (T en s). Donc, vous voulez que cela se termine en N = F*T appels, N = 50 dans cet exemple.
Avant votre première analyse, vous savez que votre progression actuelle est de 0, donc votre pourcentage restant est RP = 1 (100%).
Avant chaque SCAN appel (ou chaque nombre donné d'appels que vous souhaitez ajuster votre COUNT si vous souhaitez enregistrer le temps d'aller-retour (RTT) d'un DBSIZE call), vous appelez DBSIZE pour obtenir le nombre de clés K .
Vous utiliserez COUNT = K*RP/N
Pour le premier appel, c'est COUNT = 200032*1/50 = 4000 .
Pour tout autre appel, vous devez calculer RP = 1 - ReversedCursor/NextPowerOfTwo(K) .
Par exemple, disons que vous avez déjà passé 20 appels, donc maintenant N = 30 (nombre d'appels restant). Vous avez appelé DBSIZE et obtenu K = 281569 . Cela signifie NextPowerOfTwo(K) = 524288 , c'est 2^19.
Votre prochain curseur est 14509 en décimal =000011100010101101 en binaire. Comme la taille de la table est 2^19, nous la représentons avec 18 bits.
Vous inversez les bits et obtenez 101101010001110000 en binaire =185456 en décimal. Cela signifie que nous avons couvert 185456 sur 524288. Et :
RP = 1 - ReversedCursor/NextPowerOfTwo(K) = 1 - 185456 / 524288 = 0.65 or 65%
Il faut donc ajuster :
COUNT = K*RP/N = 281569 * 0.65 / 30 = 6100
Donc dans votre prochain SCAN appelez-vous utilisez 6100 . Il est logique qu'il ait augmenté car :
- Le nombre de clés est passé de 200032 à 281569.
- Bien que nous n'ayons plus que 60 % de notre estimation initiale des appels restants, les progrès sont en retard, car 65 % de l'espace de clés est en attente d'analyse.
Tout cela supposait que vous obteniez toutes les clés. Si vous faites correspondre des motifs , vous devez utiliser le passé pour estimer le nombre restant de clés à trouver. On ajoute comme facteur PM (pourcentage de correspondances) au COUNT calcul.
COUNT = PM * K*RP/N
PM = keysFound / ( K * ReversedCursor/NextPowerOfTwo(K))
Si après 20 appels, vous n'avez trouvé que keysFound = 2000 touches, puis :
PM = 2000 / ( 281569 * 185456 / 524288) = 0.02
Cela signifie que seulement 2 % des clés correspondent à notre modèle jusqu'à présent, donc
COUNT = PM * K*RP/N = 0.02 * 6100 = 122
Cet algorithme peut probablement être amélioré, mais vous voyez l'idée.
Assurez-vous d'exécuter des benchmarks sur le COUNT nombre que vous utiliserez pour commencer, pour mesurer combien de millisecondes est votre SCAN prendre, car vous devrez peut-être modérer vos attentes concernant le nombre d'appels dont vous avez besoin (N ) pour le faire dans un délai raisonnable sans bloquer le serveur, et ajustez votre F et T en conséquence.
