Eerst wat context, oplossing aan het einde :
Van SCAN-opdracht> Garantie van beëindiging
Het SCAN-algoritme wordt gegarandeerd alleen beëindigd als de grootte van de herhaalde verzameling beperkt blijft tot een bepaalde maximale grootte, anders kan het herhalen van een verzameling die altijd groeit, ertoe leiden dat SCAN nooit een volledige herhaling beëindigt.
Dit is intuïtief gemakkelijk te zien:als de verzameling groeit, is er meer en meer werk te doen om alle mogelijke elementen te bezoeken, en de mogelijkheid om de iteratie te beëindigen hangt af van het aantal aanroepen naar SCAN en de COUNT-optiewaarde vergeleken met het tarief bij welke de collectie groeit.
Maar in de optie AANTAL staat:
Belangrijk:het is niet nodig om dezelfde COUNT-waarde te gebruiken voor elke iteratie. Het staat de beller vrij om de telling van de ene iteratie naar de andere naar wens te wijzigen, zolang de cursor die bij de volgende oproep wordt doorgegeven, de cursor is die is verkregen bij de vorige oproep voor het commando.
Belangrijk om in gedachten te houden, van Scan garanties:
- Een bepaald element kan meerdere keren worden geretourneerd. Het is aan de applicatie om het geval van gedupliceerde elementen af te handelen, bijvoorbeeld alleen de geretourneerde elementen gebruiken om operaties uit te voeren die veilig zijn wanneer ze meerdere keren opnieuw worden toegepast.
- Elementen die tijdens een volledige iteratie niet constant in de collectie aanwezig waren, kunnen al dan niet worden geretourneerd:het is niet gedefinieerd.
De sleutel tot een oplossing zit in de cursor zelf. Zie De SCAN-cursor van Redis begrijpen. Het is mogelijk om het percentage van de voortgang van uw scan af te leiden, omdat de cursor in werkelijkheid de bits omgekeerd is van een index ten opzichte van de tabelgrootte.
DBSIZE gebruiken of INFO keyspace commando kunt u op elk moment zien hoeveel sleutels u heeft:
> DBSIZE
(integer) 200032
> info keyspace
# Keyspace
db0:keys=200032,expires=0,avg_ttl=0
Een andere bron van informatie is de ongedocumenteerde DEBUG htstats index , om een gevoel te krijgen:
> 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
De tabelgrootte is de macht van 2 volgens uw aantal sleutels:Toetsen:200032 => Tabelgrootte:262144
De oplossing:
We berekenen een gewenste COUNT argument voor elke scan.
Stel dat u SCAN belt met een frequentie (F in Hz) van 10 Hz (elke 100 ms) en u wilt dat het binnen 5 seconden wordt gedaan (T in s). Dus je wilt dat dit klaar is in N = F*T oproepen, N = 50 in dit voorbeeld.
Voor uw eerste scan weet u dat uw huidige voortgang 0 is, dus uw resterende percentage is RP = 1 (100%).
Voor elke SCAN oproep (of elk bepaald aantal oproepen waarvan u uw COUNT wilt aanpassen als u de Round Trip Time (RTT) van een DBSIZE wilt opslaan oproep), bel je DBSIZE om het aantal sleutels K . te krijgen .
U gebruikt COUNT = K*RP/N
Voor de eerste oproep is dit COUNT = 200032*1/50 = 4000 .
Voor elke andere aanroep moet u RP = 1 - ReversedCursor/NextPowerOfTwo(K) berekenen .
Stel bijvoorbeeld dat u al 20 oproepen hebt gedaan, dus nu N = 30 (resterend aantal oproepen). Je hebt DBSIZE . gebeld en kreeg K = 281569 . Dit betekent NextPowerOfTwo(K) = 524288 , dit is 2^19.
Uw volgende cursor is 14509 in decimaal =000011100010101101 in binair. Aangezien de tabelgrootte 2^19 is, geven we deze weer met 18 bits.
Je draait de bits om en krijgt 101101010001110000 in binair =185456 in decimaal. Dit betekent dat we 185456 van de 524288 hebben gedekt. En:
RP = 1 - ReversedCursor/NextPowerOfTwo(K) = 1 - 185456 / 524288 = 0.65 or 65%
Dus je moet aanpassen:
COUNT = K*RP/N = 281569 * 0.65 / 30 = 6100
Dus in je volgende SCAN bel je gebruikt 6100 . Logisch dat het toenam omdat:
- Het aantal sleutels is toegenomen van 200032 naar 281569.
- Hoewel we nog maar 60% van onze aanvankelijke schatting van het aantal oproepen hebben, loopt de voortgang achter, aangezien 65% van de keyspace nog moet worden gescand.
Dit alles ging ervan uit dat je alle sleutels krijgt. Als je patronen zoekt , moet u het verleden gebruiken om het resterende aantal te vinden sleutels in te schatten. We voegen als factor PM . toe (percentage overeenkomsten) met de COUNT berekening.
COUNT = PM * K*RP/N
PM = keysFound / ( K * ReversedCursor/NextPowerOfTwo(K))
Als u na 20 oproepen alleen keysFound = 2000 . heeft gevonden toetsen, dan:
PM = 2000 / ( 281569 * 185456 / 524288) = 0.02
Dit betekent dat tot nu toe slechts 2% van de sleutels overeenkomt met ons patroon, dus
COUNT = PM * K*RP/N = 0.02 * 6100 = 122
Dit algoritme kan waarschijnlijk worden verbeterd, maar je snapt het idee.
Zorg ervoor dat u enkele benchmarks uitvoert op de COUNT nummer dat u gebruikt om mee te beginnen, om te meten hoeveel milliseconden uw SCAN is neemt, aangezien u wellicht uw verwachtingen over het aantal oproepen dat u nodig heeft, moet bijstellen (N ) om dit binnen een redelijke tijd te doen zonder de server te blokkeren, en pas uw F . aan en T dienovereenkomstig.