Алгоритмическая задача на Rate Limiter

Question

Алгоритмическая задача на Rate Limiter

Рейтинг: 0Ответов: 1Опубликовано: 27.06.2023

Имеется задача, где есть отсортированный список UNIX дат (unix timestamp с точностью до миллисекунд - unsigned 64 bit integer). Вместе с датами так же присутствует и специальный пользовательский токен. Например:

1676217286199 RjY2NjM5NzA2OWJjuE7c 
1676217287012 RjY2NjM5NzA2OWJjuE7c 
1676217287612 RjY2NjM5NzA2OWJjuE7c

Задача состоит в том, чтобы описать функцию accept. Она должна вернуть true если количество запросов в диапазоне секунды не привысило N для пользователя (определяется по токену). Другими словами - не более N раз в секунду.

Вот пример тестовых данных

1679982033000 441079aa62dc3cd57df3 
1679982033998 441079aa62dc3cd57df3 
1679982033999 441079aa62dc3cd57df3 
1679982034000 441079aa62dc3cd57df3

Применяю функцию accept, на выходе должно остаться

1679982033000 441079aa62dc3cd57df3 
1679982033998 441079aa62dc3cd57df3 
1679982034000 441079aa62dc3cd57df3

Эту задачу я решал следующим алгоритмом:

Если в мапе нет по токену никакого времени, то кладу в мапу пару - текущее время и количество запрашиваемых запросов
если мы укладываемся в период 1 секунды и у нас еще не превышен лимит N, то мы пропускаем запрос (увеличиваем счетчик)
если мы находимся в другом "окне", то мы должны сбросить счётчик до 1 и обновляем время, чтобы считать окно с текущим интервалом (в задаче время отсортировано)

в обратном случае мы не пускаем запрос

Map<String, Long[]> lastRequestTimes = new HashMap<>();
 boolean accept(String token, long timestamp) {
     lastRequestTimes.putIfAbsent(token, new Long[]{timestamp, 1L});
     long lastRequestTime = lastRequestTimes.get(token)[0]; // Получаем последнее время запроса для текущего токена
     if (timestamp / 1000L - lastRequestTime / 1000 == 0 && lastRequestTimes.get(token)[1] <= n) {
         ++lastRequestTimes.get(token)[1];
         return true;
     } else if (timestamp / 1000L - lastRequestTime / 1000 != 0) {
         lastRequestTimes.get(token)[1] = 1L;
         lastRequestTimes.get(token)[0] = timestamp;
        return true;
     }

     return false;
 }

Данный код где-то содержит логическую ошибку. У меня есть предположение, что неверно обрабатывается edge-кейсы. Вероятно нужно класть в пустую мапу со счётчиком 0, дальше увеличивать счётчик через if-else и дальше проверять, не вышли ли мы за пределы N. Помогите найти логическую ошибку в алгоритме.

java алгоритм

Источник: Stack Overflow на русском

Answer 1

▲ 2

Думаю, "в диапазоне секунды" не означает промежутки по границам целых секунд, а любые отрезки длиной в секунду.

Держите в мапе пары токен:очередь с временами (Queue, если у вас в Java есть готовая, да и любой список подойдёт)

По приходу данных берете токен и время, и удаляете из начала соответствующей токену очереди времена, отстоящие более чем на 1000 мс.

Добавляете время в конец очереди

Если после этого длина очереди меньше или равна N, возвращаете true

Алгоритмическая задача на Rate Limiter

Ответы