Först lite sammanhang, lösning i slutet :
Från kommandot SCAN> Garanti för uppsägning
SCAN-algoritmen kommer garanterat att avslutas endast om storleken på den upprepade samlingen förblir begränsad till en given maximistorlek, annars kan det att upprepa en samling som alltid växer resultera i att SCAN aldrig avslutar en fullständig iteration.
Detta är lätt att se intuitivt:om samlingen växer finns det mer och mer arbete att göra för att besöka alla möjliga element, och möjligheten att avsluta iterationen beror på antalet samtal till SCAN och dess COUNT-alternativvärde jämfört med hastigheten vid som samlingen växer.
Men i alternativet COUNT står det:
Viktigt:det finns inget behov av att använda samma COUNT-värde för varje iterering. Den som ringer är fri att ändra räkningen från en iteration till en annan efter behov, så länge som markören som passerade i nästa anrop är den som erhölls i föregående anrop till kommandot.
Viktigt att tänka på, från Scan garantier:
- Ett givet element kan returneras flera gånger. Det är upp till applikationen att hantera fallet med duplicerade element, till exempel att endast använda de returnerade elementen för att utföra operationer som är säkra när de återappliceras flera gånger.
- Element som inte ständigt fanns i samlingen under en fullständig iteration, kan återlämnas eller inte:det är odefinierat.
Nyckeln till en lösning finns i själva markören. Se Att förstå Redis SCAN-markör. Det är möjligt att härleda procentandelen av framstegen för din skanning eftersom markören verkligen är bitarna omvända av ett index till tabellstorleken.
Använder DBSIZE eller INFO keyspace kommando du kan få hur många nycklar du har när som helst:
> DBSIZE
(integer) 200032
> info keyspace
# Keyspace
db0:keys=200032,expires=0,avg_ttl=0
En annan informationskälla är det odokumenterade DEBUG htstats index , bara för att få en känsla:
> 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
Tabellstorleken är styrkan av 2 efter ditt antal nycklar:Nycklar:200032 => Bordsstorlek:262144
Lösningen:
Vi kommer att beräkna en önskad COUNT argument för varje skanning.
Säg att du kommer att ringa SCAN med en frekvens (F i Hz) på 10 Hz (var 100:e ms) och du vill att det ska göras på 5 sekunder (T i s). Så du vill att detta ska vara klart i N = F*T samtal, N = 50 i det här exemplet.
Innan din första skanning vet du att ditt nuvarande framsteg är 0, så din återstående procent är RP = 1 (100%).
Före varje SCAN samtal (eller varje givet antal samtal som du vill justera ditt ANTAL om du vill spara RTT (Round Trip Time) för en DBSIZE samtal), anropar du DBSIZE för att få antalet nycklar K .
Du kommer att använda COUNT = K*RP/N
För det första samtalet är detta COUNT = 200032*1/50 = 4000 .
För alla andra samtal måste du beräkna RP = 1 - ReversedCursor/NextPowerOfTwo(K) .
Låt oss till exempel säga att du redan har gjort 20 samtal, så nu N = 30 (återstående antal samtal). Du ringde DBSIZE och fick K = 281569 . Detta betyder NextPowerOfTwo(K) = 524288 , det här är 2^19.
Din nästa markör är 14509 i decimal =000011100010101101 i binärt. Eftersom tabellstorleken är 2^19 representerar vi den med 18 bitar.
Du vänder på bitarna och får 101101010001110000 i binär =185456 i decimal. Det betyder att vi har täckt 185456 av 524288. Och:
RP = 1 - ReversedCursor/NextPowerOfTwo(K) = 1 - 185456 / 524288 = 0.65 or 65%
Så du måste justera:
COUNT = K*RP/N = 281569 * 0.65 / 30 = 6100
Så i din nästa SCAN samtal du använder 6100 . Förnuftigt att det ökade eftersom:
- Mängden nycklar har ökat från 200032 till 281569.
- Även om vi bara har 60 % av vår initiala uppskattning av samtal kvar, ligger framstegen efter eftersom 65 % av tangentutrymmet väntar på att skannas.
Allt detta var förutsatt att du får alla nycklar. Om du matchar mönster , måste du använda det förflutna för att uppskatta det återstående antalet nycklar som ska hittas. Vi lägger till som en faktor PM (procent av matchningar) till COUNT beräkning.
COUNT = PM * K*RP/N
PM = keysFound / ( K * ReversedCursor/NextPowerOfTwo(K))
Om du efter 20 samtal bara har hittat keysFound = 2000 tangenter, sedan:
PM = 2000 / ( 281569 * 185456 / 524288) = 0.02
Det betyder att bara 2 % av nycklarna matchar vårt mönster hittills, så
COUNT = PM * K*RP/N = 0.02 * 6100 = 122
Denna algoritm kan förmodligen förbättras, men du förstår.
Se till att köra några riktmärken på COUNT nummer du använder till att börja med, för att mäta hur många millisekunder som är din SCAN tar, eftersom du kan behöva moderera dina förväntningar på hur många samtal du behöver (N ) för att göra detta inom rimlig tid utan att blockera servern, och justera din F och T i enlighet därmed.