Prima un po' di contesto, soluzione alla fine :
Dal comando SCAN> Garanzia di risoluzione
È garantito che l'algoritmo SCAN termini solo se la dimensione della raccolta iterata rimane limitata a una determinata dimensione massima, altrimenti l'iterazione di una raccolta che cresce sempre può comportare che SCAN non termini mai un'iterazione completa.
Questo è facile da vedere intuitivamente:se la collezione cresce c'è sempre più lavoro da fare per visitare tutti gli elementi possibili, e la possibilità di terminare l'iterazione dipende dal numero di chiamate a SCAN e dal suo valore dell'opzione COUNT rispetto alla tariffa a quale la collezione cresce.
Ma nell'opzione COUNT si dice:
Importante:non è necessario utilizzare lo stesso valore COUNT per ogni iterazione. Il chiamante è libero di modificare il conteggio da un'iterazione all'altra secondo necessità, purché il cursore passato nella chiamata successiva sia quello ottenuto nella precedente chiamata al comando.
Importante da tenere a mente, dalle garanzie Scan:
- Un dato elemento può essere restituito più volte. Spetta all'applicazione gestire il caso di elementi duplicati, ad esempio utilizzando solo gli elementi restituiti per eseguire operazioni sicure se riapplicate più volte.
- Gli elementi che non erano costantemente presenti nella raccolta durante un'iterazione completa, possono essere restituiti o meno:non è definito.
La chiave per una soluzione è nel cursore stesso. Vedere Dare un senso al cursore SCAN di Redis. È possibile dedurre la percentuale di avanzamento della scansione perché il cursore è in realtà i bit invertiti di un indice rispetto alle dimensioni della tabella.
Usando DBSIZE o INFO keyspace comando puoi ottenere quante chiavi hai in qualsiasi momento:
> DBSIZE
(integer) 200032
> info keyspace
# Keyspace
db0:keys=200032,expires=0,avg_ttl=0
Un'altra fonte di informazioni è l'DEBUG htstats index non documentato , giusto per avere un'idea:
> 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 dimensione del tavolo è la potenza di 2 in base al numero di chiavi:Chiavi:200032 => Dimensioni del tavolo:262144
La soluzione:
Calcoleremo un COUNT desiderato argomento per ogni scansione.
Supponiamo che chiamerai SCAN con una frequenza (F in Hz) di 10 Hz (ogni 100 ms) e vuoi che sia fatto in 5 secondi (T in s). Quindi vuoi che finisca in N = F*T chiamate, N = 50 in questo esempio.
Prima della tua prima scansione, sai che il tuo progresso attuale è 0, quindi la tua percentuale rimanente è RP = 1 (100%).
Prima di ogni SCAN chiamata (o ogni dato numero di chiamate di cui desideri modificare il tuo COUNT se desideri salvare il tempo di andata e ritorno (RTT) di un DBSIZE call), chiami DBSIZE per ottenere il numero di chiavi K .
Utilizzerai COUNT = K*RP/N
Per la prima chiamata, questo è COUNT = 200032*1/50 = 4000 .
Per qualsiasi altra chiamata, devi calcolare RP = 1 - ReversedCursor/NextPowerOfTwo(K) .
Ad esempio, supponiamo che tu abbia già effettuato 20 chiamate, quindi ora N = 30 (numero di chiamate rimanenti). Hai chiamato DBSIZE e ho ottenuto K = 281569 . Ciò significa NextPowerOfTwo(K) = 524288 , questo è 2^19.
Il tuo prossimo cursore è 14509 in decimale =000011100010101101 in binario. Poiché la dimensione della tabella è 2^19, la rappresentiamo con 18 bit.
Inverti i bit e ottieni 101101010001110000 in binario =185456 in decimale. Ciò significa che abbiamo coperto 185456 su 524288. E:
RP = 1 - ReversedCursor/NextPowerOfTwo(K) = 1 - 185456 / 524288 = 0.65 or 65%
Quindi devi adattarti:
COUNT = K*RP/N = 281569 * 0.65 / 30 = 6100
Quindi nel tuo prossimo SCAN chiama si usa 6100 . Ha senso che sia aumentato perché:
- La quantità di chiavi è aumentata da 200032 a 281569.
- Anche se abbiamo solo il 60% della nostra stima iniziale di chiamate rimanenti, i progressi sono in ritardo poiché il 65% dello spazio chiave è in attesa di essere scansionato.
Tutto questo presupponeva che tu avessi tutte le chiavi. Se stai rispettando i modelli , è necessario utilizzare il passato per stimare la quantità rimanente di chiavi da trovare. Aggiungiamo come fattore PM (percentuale di corrispondenze) al COUNT calcolo.
COUNT = PM * K*RP/N
PM = keysFound / ( K * ReversedCursor/NextPowerOfTwo(K))
Se dopo 20 chiamate hai trovato solo keysFound = 2000 chiavi, quindi:
PM = 2000 / ( 281569 * 185456 / 524288) = 0.02
Ciò significa che finora solo il 2% delle chiavi corrisponde al nostro modello, quindi
COUNT = PM * K*RP/N = 0.02 * 6100 = 122
Questo algoritmo può probabilmente essere migliorato, ma hai un'idea.
Assicurati di eseguire alcuni benchmark su COUNT numero che utilizzerai per iniziare, per misurare quanti millisecondi è il tuo SCAN prendendo, poiché potresti dover moderare le tue aspettative su quante chiamate hai bisogno (N ) per farlo in un tempo ragionevole senza bloccare il server e modificare il tuo F e T di conseguenza.
