Nejprve nějaký kontext, řešení na závěr :
Z příkazu SCAN> Záruka ukončení
U algoritmu SCAN je zaručeno, že se ukončí pouze v případě, že velikost iterované kolekce zůstane omezena na danou maximální velikost, v opačném případě může opakování kolekce, která se neustále zvětšuje, vést ke SCAN, který nikdy neukončí celou iteraci.
To je snadno intuitivní vidět:pokud se kolekce rozrůstá, je potřeba udělat stále více práce, aby bylo možné navštívit všechny možné prvky, a schopnost ukončit iteraci závisí na počtu volání SCAN a hodnotě možnosti COUNT ve srovnání s rychlostí při které sbírka roste.
Ale ve volbě COUNT je napsáno:
Důležité:není nutné používat stejnou hodnotu COUNT pro každou iteraci. Volající může podle potřeby měnit počet z jedné iterace na druhou, pokud kurzor předaný v dalším volání je kurzor získaný v předchozím volání příkazu.
Důležité je mít na paměti, ze záruky skenování:
- Daný prvek může být vrácen vícekrát. Je na aplikaci, aby zvládla případ duplicitních prvků, například pouze pomocí vrácených prvků za účelem provádění operací, které jsou bezpečné při opakovaném opakovaném použití.
- Prvky, které nebyly trvale přítomny v kolekci během úplné iterace, mohou být vráceny nebo ne:není definováno.
Klíč k řešení je v samotném kurzoru. Viz Vysvětlení kurzoru SCAN společnosti Redis. Je možné odvodit procento průběhu skenování, protože kurzor je ve skutečnosti bity obrácené indexem k velikosti tabulky.
Pomocí DBSIZE nebo INFO keyspace můžete kdykoli získat kolik klíčů máte:
> DBSIZE
(integer) 200032
> info keyspace
# Keyspace
db0:keys=200032,expires=0,avg_ttl=0
Dalším zdrojem informací je nezdokumentovaný DEBUG htstats index , jen pro pocit:
> 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
Velikost tabulky je mocnina 2 podle vašeho počtu klíčů:Klíče:200032 => Velikost tabulky:262144
Řešení:
Vypočteme požadovaný COUNT argument pro každé skenování.
Řekněme, že budete volat SCAN s frekvencí (F v Hz) 10 Hz (každých 100 ms) a chcete, aby to bylo hotové za 5 sekund (T v s). Takže chcete, aby to skončilo v N = F*T volání, N = 50 v tomto příkladu.
Před prvním skenováním víte, že váš aktuální pokrok je 0, takže vaše zbývající procento je RP = 1 (100 %).
Před každým SCAN hovor (nebo každý daný počet hovorů, u kterých chcete upravit COUNT, pokud chcete ušetřit dobu zpáteční cesty (RTT) DBSIZE call), zavoláte DBSIZE získat počet klíčů K .
Budete používat COUNT = K*RP/N
Pro první volání je to COUNT = 200032*1/50 = 4000 .
Pro jakékoli další volání musíte vypočítat RP = 1 - ReversedCursor/NextPowerOfTwo(K) .
Řekněme například, že jste již provedli 20 hovorů, takže nyní N = 30 (zbývající počet hovorů). Zavolali jste DBSIZE a dostal K = 281569 . To znamená NextPowerOfTwo(K) = 524288 , to je 2^19.
Váš další kurzor je 14509 v desítkové soustavě =000011100010101101 v binárním. Protože velikost tabulky je 2^19, reprezentujeme ji 18 bity.
Obrátíte bity a získáte 101101010001110000 v binární =185456 v desítkové soustavě. To znamená, že jsme pokryli 185456 z 524288. A:
RP = 1 - ReversedCursor/NextPowerOfTwo(K) = 1 - 185456 / 524288 = 0.65 or 65%
Takže musíte upravit:
COUNT = K*RP/N = 281569 * 0.65 / 30 = 6100
Takže v dalším SCAN zavolejte, použijte 6100 . To dává smysl, protože:
- Počet klíčů se zvýšil z 200032 na 281569.
- Ačkoli máme pouze 60 % z našeho původního odhadu zbývajících hovorů, pokrok je pozadu, protože 65 % klíčového prostoru čeká na skenování.
To vše za předpokladu, že máte všechny klíče. Pokud porovnáváte vzory , musíte použít minulost k odhadu zbývajícího množství klíčů, které se mají najít. Jako faktor přidáme PM (procento shod) k COUNT výpočet.
COUNT = PM * K*RP/N
PM = keysFound / ( K * ReversedCursor/NextPowerOfTwo(K))
Pokud jste po 20 voláních našli pouze keysFound = 2000 klávesy a poté:
PM = 2000 / ( 281569 * 185456 / 524288) = 0.02
To znamená, že pouze 2 % kláves se zatím shodují s naším vzorem, takže
COUNT = PM * K*RP/N = 0.02 * 6100 = 122
Tento algoritmus lze pravděpodobně vylepšit, ale máte představu.
Ujistěte se, že spouštíte nějaké srovnávací testy na COUNT číslo, kterým začnete, abyste změřili, kolik milisekund je vaše SCAN přijímání, protože možná budete muset zmírnit svá očekávání ohledně počtu hovorů, které potřebujete (N ), abyste to udělali v rozumném čase bez blokování serveru, a upravte F a T podle toho.