Ограничение количества выполнений метода в секунду
Комментарии (22)
25 июня 2017 в 17:51
0↑
↓
Количество операций в секунду — 6, количество потоков — 4, количество запросов — 50.
6×4 = 20, должно выполниться за 2.5 секунды же? У вас вышло 5+.25 июня 2017 в 18:20
+1↑
↓
Что? Нет. Эти две величины вообще между собой не связаны. Количество операций в секунду это ограничение, выставленное мной для барьера, а количество потоков относится к тестовому методу. Метод запускает проверку на 4х потоках.
И да, 6×4=24:)
25 июня 2017 в 18:38
0↑
↓
на какой диапазон допустимых значений для «количества операций в секунду» вы ориентировались, разрабатывая этот алгоритм? вы уверены что вам нужно именно точное решение этой задачи и не достаточно приближенного?25 июня 2017 в 18:48
0↑
↓
Я ориентировался на небольшие (меньше 100). Но в целом можно использовать и для бОльших значений. Тут все будет зависеть от конкретной задачи.
А почему Вы спросили про приближенное? Вообще мне нужно ограничить количество определенных запросов от пользователя конкретной цифрой.25 июня 2017 в 18:54 (комментарий был изменён)
0↑
↓
основной вопрос — зачем вам хранить все таймстемпы запросов за последнюю секунду? почему бы не использовать leaky bucket?25 июня 2017 в 19:05
0↑
↓
Потому что я не вижу способа использовать здесь данный алгоритм. Но если вы знаете, подскажите.25 июня 2017 в 19:17
0↑
↓
Берете счетчик, устанавливаете его в число rps. Допустим 10 — для 10 rps. Допустим последний запрос был в таймстемп t_last. Счетчик будет пополняться со скоростью 10 единиц в секунду (до максимального значения равного 10).Когда приходит новый запрос в таймстемп t_current — увеличиваете счетчик на (t_current-t_last) * 10 и уменьшаете на 1. если получилось меньше 0 — значит количество запросов превышено. Если больше — то ок, сохраняете t_last = t_current.
25 июня 2017 в 19:27
0↑
↓
Я не понимаю. Устанавливаю счетчик на значение 10 (для 10 rps). Счетчик будет пополняться со скоростью 10 единиц в секунду до максимального значения равного 10. Он же уже 10. И зачем его дергать каждую секунду без надобности?И как t_current (t_current-t_last) * 10 может получиться меньше 0?
Не понимаю короче.
25 июня 2017 в 19:31
0↑
↓
Дергаете только когда новый запрос приходит. C_current = C_last-1+(t_current-t_last)*10. Достаточно хранить только t_last (таймстемп последнего запроса) и С_last (последний счетчик)25 июня 2017 в 19:44
0↑
↓
Что такое t_current и t_last? Если это отпечатки времени в миллисекундах, то
(t_current-t_last)*10 при разнице в полсекунды будет равно 5000.Извините, может мне уже пора спать.
25 июня 2017 в 19:49
0↑
↓
Вещественное число, в секундах. Ну если хотите чтобы было целое и в миллисекундах — то счетчик должен будет прирастать за 1000 мс на 10 единиц, т.е. на 0.01 единиц за 1 мс. Формула преобразуется в C_current = C_last-1+(t_current-t_last)*0.0125 июня 2017 в 20:06
–2↑
↓
Не должен метод дергаться по таймеру. Да и с расчетами беда у вас., но общий смысл вроде уловил. Подумаю над этим завтра. Сегодня голова уже не варит.25 июня 2017 в 20:36
0↑
↓
хм. whatever… ключевые слова в гугле: leaky bucket, token bucket. в качестве примера можно взять исходники модуля limit_req в nginx’е.26 июня 2017 в 04:45
0↑
↓
Все, я вас понял. Я попробовал сделать через ведро размером rps. Каждый запрос добавлял в ведро 1 и вычитал дельту времени, поделенную на rps и умноженную на 1000.
c_count = l_count + 1 — (c_time-l_time) / rps * 1000Плюс данного метода в том, что нет пула, то есть нет расхода оперативной памяти и сложность инициализации О (1).
А вот минусы:- (c_time-l_time) / rps * 1000 — теряет точность при rps кратному простому числу начиная с 3.
- Количество математических операций больше (то есть расчеты выполняются дольше чем в моем способе)
Так вот для моей задачи эти минусы критичны, а лишняя оперативка — нет.
26 июня 2017 в 04:51
0↑
↓
Конечно же, я напутал здесь в формуле. Но смысл не меняется
26 июня 2017 в 08:29
0↑
↓
Блин, как тут удалять комменты? :)Конечно же, формула будет такой
c_count = Math.Max (l_count + 1 — (c_time — l_time) /1000 * rps, 0)Минуса с неточностью, следовательно, не будет. Но вот по производительности надо будет проверить. К ней требования выше, чем к жору оперативной памяти.
25 июня 2017 в 18:48
+1↑
↓
Есть коллекция отпечатков DateTime
А теперь подумайте, что случится при смене системного времени по тем или иным причинам. Для таких целей следует использовать монотонный таймер. В .NET таковым является
Stopwatch
.25 июня 2017 в 18:53
0↑
↓
Да, ценное замечание. Сейчас подправлю под него :)
25 июня 2017 в 20:22
+1↑
↓
Как то усложнено, не так ли?
Достаточно хранить круговой массив из N дат последних запусков задач, если дата последнего больше периода — запускаете задачу, иначе ждете паузу в разницу между этим периодом и текущим временем.26 июня 2017 в 04:48
0↑
↓
Да, если вы посмотрите предыдущие ревизии на гитхабе, то увидите, что до этого использовался как раз круговой массив из дат :)
Но мне еще важна сложность поддержки. Поэтому я сделал очевидный круговой набор данных.26 июня 2017 в 04:52
0↑
↓
Кстати, ничего ждать мне не нужно. Вместо ожидания функция просто возвращает false
25 июня 2017 в 21:16
0↑
↓
А задача всего проекта какая?
Похоже на сценарий для НТ :)