Redis
 sql >> Base de Dados >  >> NoSQL >> Redis

Redis `SCAN`:como manter um equilíbrio entre as chaves recém-chegadas que podem corresponder e garantir o resultado final em um tempo razoável?


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.