Først lidt kontekst, løsning til sidst :
Fra SCAN kommando> Garanti for ophør
SCAN-algoritmen er garanteret kun at afslutte, hvis størrelsen af den itererede samling forbliver begrænset til en given maksimal størrelse, ellers kan gentagelse af en samling, der altid vokser, resultere i, at SCAN aldrig afslutter en fuld iteration.
Dette er let at se intuitivt:Hvis samlingen vokser, er der mere og mere arbejde at gøre for at besøge alle de mulige elementer, og muligheden for at afslutte iterationen afhænger af antallet af opkald til SCAN og dens COUNT-optionsværdi sammenlignet med satsen på som samlingen vokser.
Men i indstillingen COUNT står der:
Vigtigt:der er ingen grund til at bruge den samme COUNT-værdi for hver iteration. Den, der ringer, kan frit ændre tælleren fra den ene iteration til den anden efter behov, så længe markøren, der passeres i det næste opkald, er den, der blev opnået i det forrige opkald til kommandoen.
Vigtigt at huske på, fra Scan-garantier:
- Et givet element kan returneres flere gange. Det er op til applikationen at håndtere tilfælde af duplikerede elementer, for eksempel kun at bruge de returnerede elementer for at udføre operationer, der er sikre, når de genanvendes flere gange.
- Elementer, der ikke konstant var til stede i samlingen under en fuld iteration, kan returneres eller ej:det er udefineret.
Nøglen til en løsning er i selve markøren. Se Få mening med Redis' SCAN-markør. Det er muligt at udlede procentdelen af fremskridt for din scanning, fordi markøren i virkeligheden er bits-omvendt af et indeks til tabelstørrelsen.
Bruger DBSIZE eller INFO keyspace kommando kan du til enhver tid få, hvor mange nøgler du har:
> DBSIZE
(integer) 200032
> info keyspace
# Keyspace
db0:keys=200032,expires=0,avg_ttl=0
En anden kilde til information er det udokumenterede DEBUG htstats index , bare for at få en fornemmelse:
> 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
Bordstørrelsen er magten af 2 efter dit antal nøgler:Nøgler:200032 => Bordstørrelse:262144
Løsningen:
Vi beregner en ønsket COUNT argument for hver scanning.
Lad os sige, at du ringer til SCAN med en frekvens (F i Hz) på 10 Hz (hver 100 ms), og du vil have det gjort på 5 sekunder (T i s). Så du vil have dette færdigt i N = F*T opkald, N = 50 i dette eksempel.
Før din første scanning ved du, at dit nuværende fremskridt er 0, så din resterende procent er RP = 1 (100%).
Før hver SCAN opkald (eller hvert givet antal opkald, som du vil justere dit ANTAL, hvis du vil gemme rundrejsetiden (RTT) for en DBSIZE opkald), ringer du til DBSIZE for at få antallet af nøgler K .
Du skal bruge COUNT = K*RP/N
For det første opkald er dette COUNT = 200032*1/50 = 4000 .
For ethvert andet opkald skal du beregne RP = 1 - ReversedCursor/NextPowerOfTwo(K) .
Lad os f.eks. sige, at du allerede har foretaget 20 opkald, så nu N = 30 (resterende antal opkald). Du ringede til DBSIZE og fik K = 281569 . Dette betyder NextPowerOfTwo(K) = 524288 , dette er 2^19.
Din næste markør er 14509 i decimal =000011100010101101 i binær. Da tabelstørrelsen er 2^19, repræsenterer vi den med 18 bit.
Du vender bits og får 101101010001110000 i binær =185456 i decimal. Det betyder, at vi har dækket 185456 ud af 524288. Og:
RP = 1 - ReversedCursor/NextPowerOfTwo(K) = 1 - 185456 / 524288 = 0.65 or 65%
Så du skal justere:
COUNT = K*RP/N = 281569 * 0.65 / 30 = 6100
Så i din næste SCAN ringer du bruger 6100 . Giver mening, at det øges, fordi:
- Mængden af nøgler er steget fra 200032 til 281569.
- Selvom vi kun har 60 % af vores oprindelige estimat af opkald tilbage, er fremskridtet bagud, da 65 % af tasterummet mangler at blive scannet.
Alt dette var forudsat at du fik alle nøgler. Hvis du matcher mønsteret , skal du bruge fortiden til at estimere det resterende antal nøgler, der skal findes. Vi tilføjer som en faktor PM (procent af matches) til COUNT udregning.
COUNT = PM * K*RP/N
PM = keysFound / ( K * ReversedCursor/NextPowerOfTwo(K))
Hvis du efter 20 opkald kun har fundet keysFound = 2000 nøgler, så:
PM = 2000 / ( 281569 * 185456 / 524288) = 0.02
Det betyder, at kun 2 % af nøglerne matcher vores mønster indtil videre, så
COUNT = PM * K*RP/N = 0.02 * 6100 = 122
Denne algoritme kan sikkert forbedres, men du forstår.
Sørg for at køre nogle benchmarks på COUNT tal, du vil bruge til at starte med, for at måle, hvor mange millisekunder er din SCAN tager, da du muligvis skal moderere dine forventninger til, hvor mange opkald du har brug for (N ) for at gøre dette inden for rimelig tid uden at blokere serveren, og juster din F og T tilsvarende.