Najpierw trochę kontekstu, rozwiązanie na końcu :
Z polecenia SKANUJ> Gwarancja zakończenia
Algorytm SCAN gwarantuje zakończenie tylko wtedy, gdy rozmiar iterowanej kolekcji pozostaje ograniczony do określonego maksymalnego rozmiaru, w przeciwnym razie iteracja kolekcji, która zawsze rośnie, może skutkować w SCAN, który nigdy nie zakończy pełnej iteracji.
Łatwo to zauważyć intuicyjnie:w miarę powiększania się kolekcji jest coraz więcej pracy, aby odwiedzić wszystkie możliwe elementy, a możliwość zakończenia iteracji zależy od liczby wezwań do SCAN i wartości jej opcji COUNT w porównaniu ze stawką przy które kolekcja rośnie.
Ale w opcji LICZBA jest napisane:
Ważne:nie ma potrzeby używania tej samej wartości COUNT dla każdego iteracji. Wywołujący może dowolnie zmieniać licznik z jednej iteracji na drugą, jeśli jest to wymagane, o ile kursor przekazany w następnym wywołaniu jest tym, który został uzyskany w poprzednim wywołaniu polecenia.
Ważne, aby pamiętać, z gwarancji skanowania:
- Dany element może być zwracany wielokrotnie. Do aplikacji należy zajęcie się przypadkiem zduplikowanych elementów, na przykład wykorzystanie tylko zwróconych elementów w celu wykonania operacji, które są bezpieczne przy wielokrotnym zastosowaniu.
- Elementy, które nie były stale obecne w kolekcji podczas pełnej iteracji, mogą zostać zwrócone lub nie:jest to nieokreślone.
Klucz do rozwiązania znajduje się w samym kursorze. Zobacz Rozumienie kursora SKAN Redisa. Można wywnioskować procent postępu skanowania, ponieważ kursor jest w rzeczywistości odwróconymi bitami indeksu do rozmiaru tabeli.
Korzystanie z DBSIZE lub INFO keyspace poleceniem możesz sprawdzić, ile masz kluczy w dowolnym momencie:
> DBSIZE
(integer) 200032
> info keyspace
# Keyspace
db0:keys=200032,expires=0,avg_ttl=0
Innym źródłem informacji jest nieudokumentowany DEBUG htstats index , żeby się poczuć:
> 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
Rozmiar tabeli to potęga 2 po liczbie klawiszy:Klawisze:200032 => Rozmiar tabeli:262144
Rozwiązanie:
Obliczymy żądane COUNT argument dla każdego skanu.
Załóżmy, że będziesz dzwonić do SCAN z częstotliwością (F w Hz) 10 Hz (co 100 ms) i chcesz to zrobić w 5 sekund (T w s). Więc chcesz to zakończyć w N = F*T połączeń, N = 50 w tym przykładzie.
Przed pierwszym skanowaniem wiesz, że twój obecny postęp wynosi 0, więc pozostały procent to RP = 1 (100%).
Przed każdym SCAN połączenie (lub każdą podaną liczbę połączeń, które chcesz dostosować COUNT, jeśli chcesz zaoszczędzić czas podróży w obie strony (RTT) DBSIZE dzwonisz), dzwonisz do DBSIZE aby uzyskać liczbę kluczy K .
Użyjesz COUNT = K*RP/N
Dla pierwszego wywołania jest to COUNT = 200032*1/50 = 4000 .
Dla każdego innego wywołania musisz obliczyć RP = 1 - ReversedCursor/NextPowerOfTwo(K) .
Załóżmy na przykład, że wykonałeś już 20 połączeń, więc teraz N = 30 (pozostała liczba połączeń). Nazwałeś DBSIZE i otrzymałem K = 281569 . Oznacza to NextPowerOfTwo(K) = 524288 , to jest 2^19.
Następny kursor to 14509 w postaci dziesiętnej =000011100010101101 w formacie binarnym. Ponieważ rozmiar tabeli wynosi 2^19, przedstawiamy go za pomocą 18 bitów.
Odwracasz bity i otrzymujesz 101101010001110000 binarnie =185456 dziesiętnie. Oznacza to, że uwzględniliśmy 185456 z 524288. Oraz:
RP = 1 - ReversedCursor/NextPowerOfTwo(K) = 1 - 185456 / 524288 = 0.65 or 65%
Musisz więc dostosować:
COUNT = K*RP/N = 281569 * 0.65 / 30 = 6100
Więc w następnym SCAN dzwonisz używasz 6100 . Ma to sens, ponieważ:
- Liczba kluczy wzrosła z 200032 do 281569.
- Chociaż pozostało tylko 60% naszych wstępnych szacunków połączeń, postęp jest opóźniony, ponieważ 65% przestrzeni klawiszy oczekuje na skanowanie.
Wszystko to przy założeniu, że zdobędziesz wszystkie klucze. Jeśli dopasowujesz wzór , musisz użyć przeszłości, aby oszacować pozostałą liczbę kluczy do znalezienia. Dodajemy jako czynnik PM (procent dopasowań) do COUNT obliczenia.
COUNT = PM * K*RP/N
PM = keysFound / ( K * ReversedCursor/NextPowerOfTwo(K))
Jeśli po 20 wywołaniach znalazłeś tylko keysFound = 2000 klawisze, a następnie:
PM = 2000 / ( 281569 * 185456 / 524288) = 0.02
Oznacza to, że jak dotąd tylko 2% kluczy pasuje do naszego wzorca, więc
COUNT = PM * K*RP/N = 0.02 * 6100 = 122
Ten algorytm można prawdopodobnie ulepszyć, ale masz pomysł.
Upewnij się, że uruchomiłeś testy porównawcze na COUNT liczba, której użyjesz na początku, aby zmierzyć, ile milisekund zajmuje Twoje SCAN biorąc, ponieważ może być konieczne złagodzenie oczekiwań dotyczących liczby potrzebnych połączeń (N ), aby zrobić to w rozsądnym czasie bez blokowania serwera i dostosować swoje F i T odpowiednio.
