Zuerst etwas Kontext, Lösung am Ende :
Vom SCAN-Befehl> Kündigungsgarantie
Der SCAN-Algorithmus wird garantiert nur beendet, wenn die Größe der iterierten Sammlung auf eine bestimmte maximale Größe beschränkt bleibt, andernfalls kann das Iterieren einer Sammlung, die immer größer wird, dazu führen, dass SCAN niemals eine vollständige Iteration beendet.
Dies ist intuitiv leicht zu erkennen:Wenn die Sammlung wächst, gibt es mehr und mehr Arbeit zu tun, um alle möglichen Elemente zu besuchen, und die Möglichkeit, die Iteration zu beenden, hängt von der Anzahl der Aufrufe von SCAN und seinem COUNT-Optionswert im Vergleich zu der Rate bei ab die thecollection wächst.
Aber in der COUNT-Option heißt es:
Wichtig:Es ist nicht erforderlich, für jede Iteration denselben COUNT-Wert zu verwenden. Dem Aufrufer steht es frei, die Zählung von einer Iteration zur anderen nach Bedarf zu ändern, solange der Cursor, der beim nächsten Aufruf übergeben wird, der ist, der beim vorherigen Aufruf des Befehls erhalten wurde.
Wichtig zu beachten, von Scan-Garantien:
- Ein bestimmtes Element kann mehrfach zurückgegeben werden. Es ist Sache der Anwendung, den Fall von duplizierten Elementen zu handhaben, beispielsweise nur die zurückgegebenen Elemente zu verwenden, um Operationen auszuführen, die sicher sind, wenn sie mehrmals erneut angewendet werden.
- Elemente, die während einer vollständigen Iteration nicht ständig in der Sammlung vorhanden waren, können zurückgegeben werden oder nicht:Sie sind undefiniert.
Der Schlüssel zur Lösung liegt im Cursor selbst. Siehe Den SCAN-Cursor von Redis verstehen. Es ist möglich, den prozentualen Fortschritt Ihres Scans abzuleiten, weil der Cursor wirklich die Bitumkehrung eines Index zur Tabellengröße ist.
Verwendung von DBSIZE oder INFO keyspace Befehl können Sie jederzeit abrufen, wie viele Schlüssel Sie haben:
> DBSIZE
(integer) 200032
> info keyspace
# Keyspace
db0:keys=200032,expires=0,avg_ttl=0
Eine weitere Informationsquelle ist der undokumentierte DEBUG htstats index , nur um ein Gefühl zu bekommen:
> 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
Die Tabellengröße ist die Potenz von 2 nach Ihrer Schlüsselanzahl:Schlüssel:200032 => Tabellengröße:262144
Die Lösung:
Wir berechnen einen gewünschten COUNT Argument für jeden Scan.
Angenommen, Sie rufen SCAN mit einer Frequenz an (F in Hz) von 10 Hz (alle 100 ms) und Sie möchten, dass es in 5 Sekunden erledigt ist (T in s). Sie möchten also, dass dies in N = F*T abgeschlossen wird Anrufe, N = 50 in diesem Beispiel.
Vor Ihrem ersten Scan wissen Sie, dass Ihr aktueller Fortschritt 0 ist, also ist Ihr verbleibender Prozentsatz RP = 1 (100 %).
Vor jedem SCAN Anruf (oder jede gegebene Anzahl von Anrufen, die Sie Ihren COUNT anpassen möchten, wenn Sie die Round Trip Time (RTT) einer DBSIZE speichern möchten call), rufen Sie DBSIZE auf um die Anzahl der Schlüssel K zu erhalten .
Sie verwenden COUNT = K*RP/N
Beim ersten Aufruf ist dies COUNT = 200032*1/50 = 4000 .
Für jeden anderen Aufruf müssen Sie RP = 1 - ReversedCursor/NextPowerOfTwo(K) berechnen .
Angenommen, Sie haben bereits 20 Anrufe getätigt, also jetzt N = 30 (verbleibende Anzahl Anrufe). Sie haben DBSIZE aufgerufen und bekam K = 281569 . Das bedeutet NextPowerOfTwo(K) = 524288 , das ist 2^19.
Ihr nächster Cursor ist 14509 dezimal =000011100010101101 binär. Da die Tabellengröße 2^19 ist, stellen wir sie mit 18 Bit dar.
Sie kehren die Bits um und erhalten 101101010001110000 binär =185456 dezimal. Das bedeutet, dass wir 185456 von 524288 abgedeckt haben. Und:
RP = 1 - ReversedCursor/NextPowerOfTwo(K) = 1 - 185456 / 524288 = 0.65 or 65%
Sie müssen also anpassen:
COUNT = K*RP/N = 281569 * 0.65 / 30 = 6100
Also bei Ihrem nächsten SCAN Anruf verwenden Sie 6100 . Es macht Sinn, dass es zugenommen hat, weil:
- Die Anzahl der Schlüssel ist von 200032 auf 281569 gestiegen.
- Obwohl wir nur noch 60 % unserer ursprünglichen Schätzung der verbleibenden Anrufe haben, hinken die Fortschritte hinterher, da 65 % des Schlüsselraums noch gescannt werden müssen.
All dies unter der Annahme, dass Sie alle Schlüssel bekommen. Wenn Sie Muster-Matching sind , müssen Sie die Vergangenheit verwenden, um die verbleibende Menge an zu findenden Schlüsseln abzuschätzen. Wir fügen als Faktor PM hinzu (Prozent der Übereinstimmungen) zu COUNT Berechnung.
COUNT = PM * K*RP/N
PM = keysFound / ( K * ReversedCursor/NextPowerOfTwo(K))
Wenn Sie nach 20 Aufrufen nur keysFound = 2000 gefunden haben Tasten, dann:
PM = 2000 / ( 281569 * 185456 / 524288) = 0.02
Das bedeutet, dass bisher nur 2 % der Schlüssel mit unserem Muster übereinstimmen, also
COUNT = PM * K*RP/N = 0.02 * 6100 = 122
Dieser Algorithmus kann wahrscheinlich verbessert werden, aber Sie verstehen schon.
Stellen Sie sicher, dass Sie einige Benchmarks auf COUNT ausführen Nummer, mit der Sie beginnen, um zu messen, wie viele Millisekunden Ihr SCAN dauert nehmen, da Sie möglicherweise Ihre Erwartungen hinsichtlich der Anzahl der benötigten Anrufe mäßigen müssen (N ), um dies in angemessener Zeit zu tun, ohne den Server zu blockieren, und passen Sie Ihren F an und T entsprechend.
