Primeiro algum contexto, solução no final :
Do comando SCAN> Garantia de rescisão
O algoritmo SCAN é garantido para terminar apenas se o tamanho da coleção iterada permanecer limitado a um determinado tamanho máximo, caso contrário, iterar uma coleção que sempre cresce pode resultar em SCAN para nunca terminar uma iteração completa.
Isso é fácil de ver intuitivamente:se a coleção cresce, há mais e mais trabalho a ser feito para visitar todos os elementos possíveis, e a capacidade de encerrar a iteração depende do número de chamadas para SCAN e seu valor de opção COUNT em comparação com a taxa em qual a coleção cresce.
Mas na opção The COUNT diz:
Importante:não há necessidade de usar o mesmo valor COUNT para todas as iterações. O chamador é livre para alterar a contagem de uma iteração para outra conforme necessário, desde que o cursor passado na próxima chamada seja o obtido na chamada anterior ao comando.
Importante ter em mente, das garantias do Scan:
- Um determinado elemento pode ser retornado várias vezes. Cabe à aplicação tratar o caso de elementos duplicados, por exemplo, utilizando apenas os elementos retornados para realizar operações que são seguras quando reaplicadas várias vezes.
- Elementos que não estavam constantemente presentes na coleção durante uma iteração completa, podem ser retornados ou não:é indefinido.
A chave para uma solução está no próprio cursor. Consulte Entendendo o cursor SCAN do Redis. É possível deduzir a porcentagem de progresso de sua varredura porque o cursor é realmente os bits invertidos de um índice para o tamanho da tabela.
Usando
DBSIZE
ou INFO keyspace
comando você pode obter quantas chaves você tem a qualquer momento:> DBSIZE
(integer) 200032
> info keyspace
# Keyspace
db0:keys=200032,expires=0,avg_ttl=0
Outra fonte de informação é o não documentado
DEBUG htstats index
, só para ter uma ideia:> 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
O tamanho da tabela é a potência de 2 seguindo seu número de chaves:Chaves:200032 => Tamanho da tabela:262144
A solução:
Calcularemos um
COUNT
desejado argumento para cada varredura. Digamos que você esteja ligando para SCAN com uma frequência (
F
em Hz) de 10 Hz (a cada 100 ms) e você quer que seja feito em 5 segundos (T
em s). Então você quer que isso termine em N = F*T
chamadas, N = 50
neste exemplo. Antes de sua primeira varredura, você sabe que seu progresso atual é 0, então sua porcentagem restante é
RP = 1
(100%). Antes de cada
SCAN
chamada (ou cada número de chamadas que você deseja ajustar sua COUNT se quiser economizar o tempo de ida e volta (RTT) de um DBSIZE
call), você chama DBSIZE
para obter o número de chaves K
. Você usará
COUNT = K*RP/N
Para a primeira chamada, é
COUNT = 200032*1/50 = 4000
. Para qualquer outra chamada, você precisa calcular
RP = 1 - ReversedCursor/NextPowerOfTwo(K)
. Por exemplo, digamos que você já tenha feito 20 chamadas, então agora
N = 30
(número de chamadas restantes). Você chamou DBSIZE
e obtive K = 281569
. Isso significa NextPowerOfTwo(K) = 524288
, isso é 2^19. Seu próximo cursor é 14509 em decimal =
000011100010101101
em binário. Como o tamanho da tabela é 2^19, nós a representamos com 18 bits. Você inverte os bits e obtém
101101010001110000
em binário =185456 em decimal. Isso significa que cobrimos 185456 de 524288. E:RP = 1 - ReversedCursor/NextPowerOfTwo(K) = 1 - 185456 / 524288 = 0.65 or 65%
Então você tem que ajustar:
COUNT = K*RP/N = 281569 * 0.65 / 30 = 6100
Então, em seu próximo
SCAN
chamada você usa 6100
. Faz sentido que aumentou porque:- A quantidade de chaves aumentou de 200.032 para 281.569.
- Embora tenhamos apenas 60% de nossa estimativa inicial de chamadas restantes, o progresso está atrasado, pois 65% do keyspace está pendente para verificação.
Tudo isso foi assumindo que você está recebendo todas as chaves. Se você estiver combinando padrões , você precisa usar o passado para estimar a quantidade restante de chaves a serem encontradas. Adicionamos como fator
PM
(porcentagem de correspondências) para o COUNT
Cálculo. COUNT = PM * K*RP/N
PM = keysFound / ( K * ReversedCursor/NextPowerOfTwo(K))
Se após 20 chamadas, você encontrou apenas
keysFound = 2000
chaves, então:PM = 2000 / ( 281569 * 185456 / 524288) = 0.02
Isso significa que apenas 2% das chaves estão correspondendo ao nosso padrão até agora, então
COUNT = PM * K*RP/N = 0.02 * 6100 = 122
Este algoritmo provavelmente pode ser melhorado, mas você entendeu.
Certifique-se de executar alguns benchmarks no
COUNT
número que você usará para começar, para medir quantos milissegundos é o seu SCAN
atendendo, pois pode ser necessário moderar suas expectativas sobre quantas chamadas você precisa (N
) para fazer isso em um tempo razoável sem bloquear o servidor e ajuste seu F
e T
adequadamente.