Първо малко контекст, решение накрая :
От команда SCAN> Гаранция за прекратяване
Алгоритъмът SCAN е гарантиран, че ще приключи само ако размерът на итерираната колекция остане ограничен до даден максимален размер, в противен случай итерацията на колекция, която винаги нараства, може да доведе до SCAN, за да не прекрати пълната итерация.
Това е лесно да се види интуитивно:ако колекцията нараства, има все повече и повече работа за вършене, за да се посетят всички възможни елементи, а възможността за прекратяване на итерацията зависи от броя на извикванията за SCAN и стойността на нейната опция COUNT в сравнение със скоростта при която колекцията нараства.
Но в опцията COUNT пише:
Важно:няма нужда да използвате една и съща стойност COUNT за всяка итерация. Обаждащият се е свободен да промени броя от една итерация на друга, както е необходимо, стига курсорът, прехвърлен при следващото извикване, да е този, получен при предишното извикване на командата.
Важно е да имате предвид, от гаранции за сканиране:
- Даден елемент може да бъде върнат няколко пъти. От приложението зависи да се справи със случая на дублирани елементи, например да използва само върнатите елементи, за да изпълни операции, които са безопасни, когато се прилагат многократно.
- Елементи, които не са присъствали постоянно в колекцията по време на пълна итерация, могат да бъдат върнати или не:не е дефинирано.
Ключът към решението е в самия курсор. Вижте Осмисляне на курсора SCAN на Redis. Възможно е да се изведе процентът на напредъка на вашето сканиране, защото курсорът наистина е битовете, обърнати на индекс към размера на таблицата.
Използване на DBSIZE или INFO keyspace команда можете да получите колко ключа имате по всяко време:
> DBSIZE
(integer) 200032
> info keyspace
# Keyspace
db0:keys=200032,expires=0,avg_ttl=0
Друг източник на информация е недокументираният DEBUG htstats index , само за да усетите:
> 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
Размерът на таблицата е степента на 2 след вашия брой ключове:Ключове:200032 => Размер на таблицата:262144
Решението:
Ще изчислим желания COUNT аргумент за всяко сканиране.
Да речем, че ще се обаждате на SCAN с честота (F в Hz) от 10 Hz (на всеки 100 ms) и искате да стане за 5 секунди (T в s). Така че искате това да завърши в N = F*T повиквания, N = 50 в този пример.
Преди първото ви сканиране знаете, че текущият ви напредък е 0, така че оставащият ви процент е RP = 1 (100%).
Преди всяко SCAN обаждане (или всеки даден брой обаждания, които искате да коригирате своя COUNT, ако искате да запазите времето за двупосочно пътуване (RTT) на DBSIZE call), извиквате DBSIZE за да получите броя на клавишите K .
Ще използвате COUNT = K*RP/N
За първото обаждане това е COUNT = 200032*1/50 = 4000 .
За всяко друго обаждане трябва да изчислите RP = 1 - ReversedCursor/NextPowerOfTwo(K) .
Например, да кажем, че вече сте извършили 20 обаждания, така че сега N = 30 (оставащ брой обаждания). Обадихте се на DBSIZE и получи K = 281569 . Това означава NextPowerOfTwo(K) = 524288 , това е 2^19.
Следващият ви курсор е 14509 в десетичен знак =000011100010101101 в двоичен. Тъй като размерът на таблицата е 2^19, ние я представяме с 18 бита.
Обръщате битовете и получавате 101101010001110000 в двоичен код =185456 в десетичен. Това означава, че сме покрили 185456 от 524288. И:
RP = 1 - ReversedCursor/NextPowerOfTwo(K) = 1 - 185456 / 524288 = 0.65 or 65%
Така че трябва да коригирате:
COUNT = K*RP/N = 281569 * 0.65 / 30 = 6100
Така че във вашето следващо SCAN обадете се, използвайте 6100 . Има смисъл да се увеличи, защото:
- Количеството ключове се е увеличило от 200032 на 281569.
- Въпреки че имаме само 60% от първоначалната ни оценка на оставащите обаждания, напредъкът изостава, тъй като 65% от ключовото пространство предстои да бъде сканирано.
Всичко това предполагаше, че получавате всички ключове. Ако съвпадате с модел , трябва да използвате миналото, за да оцените оставащото количество ключове, които трябва да бъдат намерени. Добавяме като фактор PM (процент на съвпаденията) към COUNT изчисление.
COUNT = PM * K*RP/N
PM = keysFound / ( K * ReversedCursor/NextPowerOfTwo(K))
Ако след 20 обаждания сте намерили само keysFound = 2000 клавиши, след това:
PM = 2000 / ( 281569 * 185456 / 524288) = 0.02
Това означава, че само 2% от ключовете отговарят на нашия модел досега, така че
COUNT = PM * K*RP/N = 0.02 * 6100 = 122
Този алгоритъм вероятно може да бъде подобрен, но разбирате идеята.
Уверете се, че сте изпълнили някои сравнителни показатели за COUNT номер, който ще използвате за начало, за да измерите колко милисекунди е вашето SCAN приемате, тъй като може да се наложи да намалите очакванията си за това колко обаждания са ви необходими (N ), за да направите това в разумно време, без да блокирате сървъра, и коригирайте своя F и T съответно.
