Как реализовать Rate-limiter на основе алгоритма Token Bucket c использованием Bucket4j на Java

Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті.

Меня зовут Максим Бартков, я Team Lead в компании RooX Solutions, и уже около 7 лет занимаюсь разработкой различных enterprise-проектов. За это время я несколько раз сталкивался с Rate limiting и я бы хотел рассказать об этом подробнее. Эта статья будет интересна Java-разработчикам.

Рано или поздно любой backend-разработчик сталкивается с вопросом, как ограничить количество запросов на сервер к тому или иному сервису. И не всегда мы можем реализовать это на уровне серверного оборудования (nginx, haproxy, и т. д.), да и не всегда это нужно!

Где это нужно

1. С точки зрения бизнес-логики, зачастую это используется для реализации «API Business Model».

Например, нужно внедрить тарификацию для API, и мы хотим создать несколько тарифов, таких как PREMIUM, BASIC, FREE. Для каждого из этих тарифов, мы предоставляем ограниченное количество вызовов в час (можно сделать ограничение в миллисекунду, секунду, минуту, час, а можем эти все ограничения использовать вместе — это называется Bandwidth management). PREMIUM — до 1000 запросов в час, BASIC до 200 запросов в час, FREE до 50 запросов в час.

2. Для защиты системы от ботов (Fraud Detection).

Например, у нас есть мессенджер и какой-то пользователь отправляет по 50 сообщений в секунду, соответственно мы понимаем, что это бот, и система выдает такому пользователю бан.

Для того чтобы реализовать логику выше, на помощь приходят два алгоритма: Token bucket и Leaky bucket. Но сегодня мы поговорим об Token bucket.

Объяснение работы алгоритма

Рассмотрим алгоритм на следующем примере.

Bucket имеет фиксированный объем количества Tokens (например, если мы указали, что Bucket не должен иметь 1000 Tokens, то это и является максимальным объемом Bucket).

Refiller заполняет Bucket недостающими Tokens согласно заданному Bandwidth management (вызывается каждый раз перед выполнением Consume),

Ниже пример работы Refiller с заданным Bandwidth на обновление Tokens раз в минуту.

Consume (действие) забирает необходимое количество Tokens из Bucket.

Bucket нужен для того, чтобы мы могли хранить в нём текущее количество токенов, максимально возможное количество токенов и время на генерацию одного токена.

У алгоритма Token Bucket выделено фиксированное количество памяти для хранения Bucket, в нем содержатся переменные:

  • Объем Bucket (максимально допустимое количество Tokens) — 8 байт.
  • Текущее число Tokens в ведре — 8 байт.
  • Число наносекунд на генерацию одного токена — 8 байт.
  • Заголовок объекта — 16 байт
    Итого: 40 байт

Т.е в одном гигабайте мы можем хранить 25 миллионов Bucket. Это очень важно, учитывая, что как правило, мы храним данную информацию в кэше, а соответственно в оперативной памяти.

Недостаток алгоритма

Но так ли всё хорошо в этом алгоритме? К сожалению, нет, в алгоритме Token bucket есть проблема, при которой мы не можем на 100% обеспечить точность работы (проблема «Burst»).

Проблема состоит в следующем:

  1. В определенный момент наш Bucket содержит 100 Tokens.
  2. В этот же момент происходит потребление 100 Tokens.
  3. Через одну секунду наш Bucket снова содержит 100 Tokens.
  4. В этот же момент происходит потребление 100 Tokens.

Т.е. за ~1 секунду мы потребили 200 Tokens, а соответственно превысили лимит в 2 раза.

Но проблема ли это? На самом деле, нет, потому что проблема полностью нивелируется использованием Bucket на более длительной дистанции.

Если мы используем Bucket одну секунду, то потребленное количество Tokens будет 200, но если 10 секунд, то потребленное количество Token будет 1100, так как burst случился единожды.

Чем дольше дистанция использования Bucket, тем меньше погрешность использования. Очень редко бывает такое, что в Rate Limiting требуется высокая точность. Куда важнее — потребление памяти, а именно из-за этого у нас и существует данная проблема. Так как для создания Bucket нам требуется, чтобы Bucket имел фиксированное количество памяти (в случае этого алгоритма это 40 килобайт), мы сталкиваемся с burst, из-за того что у нас для создания Bucket требуется 2 переменные: число наносекунд на генерацию одного токена (refill) и объем ведра (capacity).

Из-за этого мы не можем выразить точный контракт работы Token bucket.

Пример с Bucket4j

Давайте рассмотрим алгоритм на основе библиотеки Bucket4j. Это самая популярная библиотека, написанная на Java и реализующая алгоритм Token Bucket. Каждый месяц Bucket4j скачивается более 100 тысяч раз из Maven Central. В 3 тысячах зависимостей у различных проектов на Github. Используется в Kubernatess Java Client, JHipster, и. т. д.

Для начала рассмотрим несколько простых примеров.

Давайте в качестве сборщика проектов будем использовать Maven, и прежде всего, чтобы начать, нам нужно добавить зависимости в pom.xml:

<dependency>

   <groupId>com.github.vladimir-bukhtoyarov</groupId>
   <artifactId>bucket4j-core</artifactId>
   <version>6.2.0</version>
</dependency>

Создадим класс Example:

import io.github.bucket4j.Bandwidth;
import io.github.bucket4j.Bucket;
import io.github.bucket4j.Bucket4j;
import io.github.bucket4j.ConsumptionProbe;

import java.time.Duration;

public class Example {

   public static void main(String args[]) {
       //Создаём Bandwidth в котором указываем правило, что мы добавляем 1 токен раз в 1 минуту
       Bandwidth oneCosumePerMinuteLimit = Bandwidth.simple(1, Duration.ofMinutes(1));

       //Создаём Bucket в который мы добавляем наш ранее созданный Bandwidth
       Bucket bucket = Bucket4j.builder()
                               .addLimit(oneCosumePerMinuteLimit)
                               .build();

       //Вызываем метод tryConsume в котором мы указываем сколько Tokens мы хотим забрать из нашего Bucket,
       //Возвращает boolean, где true - означает что consume успешно выполнился и нам хватило Tokens внутри Bucket чтобы выполнить tryConsume
       System.out.println(bucket.tryConsume(1)); //Вернёт ответ true

       //Вызываем метод tryConsumeAndReturnRemaining в котором мы указываем сколько Tokens мы хотим забрать из нашего Bucket
       //Возвращает ConsumptionProbe, который в себе содержит намного больше информации чем tryConsume, а именно
       //isConsumed - успешно ли выполнился consume, там где true - означает успешно
       //getRemainingTokens - Количество оставшихся Tokens
       //getNanosToWaitForRefill - Время в наносекундах до восполнения Tokens в нашем Bucket
       ConsumptionProbe сonsumptionProbe = bucket.tryConsumeAndReturnRemaining(1);
       System.out.println(сonsumptionProbe.isConsumed()); //Вернёт ответ false т.к выше мы уже вызывали метод tryConsume, а Bandwidth у нас с лимитом 1 токен раз в 1 минуту
       System.out.println(сonsumptionProbe.getRemainingTokens()); //Вернёт 0, так как мы потребили все Tokens
       System.out.println(сonsumptionProbe.getNanosToWaitForRefill()); //Вернёт примерно 60000000000 наносекунд
   }

Думаю, выглядит всё очень просто и понятно.

Давайте теперь попробуем реализовать более сложный пример. Представьте, что на уровне кода нужно ограничить количество запросов к конкретному методу для пользователя (мы хотим, чтобы какой-то пользователь не мог делать вызов нашего контроллера больше чем X раз в Y время). Но наша система распределенная, мы имеет много нод в кластере и при этом используем Hazelcast (для работы с Bucket4j мы можем использовать любой кэш, реализующий стандарт JSR 107).

Давайте реализуем наш следующий пример с использованием Spring.

Для начала добавим ещё несколько зависимостей в pom.xml:

<dependency>
   <groupId>com.github.vladimir-bukhtoyarov</groupId>
   <artifactId>bucket4j-hazelcast</artifactId>
   <version>6.2.0</version>
</dependency>
<dependency>
   <groupId>javax.cache</groupId>
   <artifactId>cache-api</artifactId>
   <version>1.0.0</version>
</dependency>
<dependency>
   <groupId>com.hazelcast</groupId>
   <artifactId>hazelcast</artifactId>
   <version>4.0.2</version>
</dependency>
<dependency>
   <groupId>org.projectlombok</groupId>
   <artifactId>lombok</artifactId>
   <version>1.18.20</version>
   <scope>provided</scope>
</dependency>

Далее реализуем аннотации, которые будем использовать на уровне методов контроллера в будущем:

@Retention(RetentionPolicy.RUNTIME)
@Target(ElementType.METHOD)
@Documented
public @interface RateLimiter {

   TimeUnit timeUnit() default TimeUnit.MINUTES;

   long timeValue();

   long restriction();

}

А также аннотацию, которая будет объединять аннотации RateLimiter (если потребуется использовать одновременно несколько Bandwidth):

import java.lang.annotation.*;

@Retention(RetentionPolicy.RUNTIME)
@Target(ElementType.METHOD)
@Documented
public @interface RateLimiters {

   RateLimiter[] value();

}

Также следует добавить TimeUnit:

public enum TimeUnit {
   MINUTES, HOURS
}

Теперь нужно создать класс, который будет отвечать непосредственно за обработку аннотации. Поскольку аннотация должна будет находится на уровне работы с контроллером, класс должен быть унаследован от HandlerInterceptorAdapter

Создаем класс RateLimiterAnnotationHandlerInterceptorAdapter:

public class RateLimiterAnnotationHandlerInterceptorAdapter extends HandlerInterceptorAdapter {

   //У вас должен быть реализован свой класс, который будет возвращать контекст по которому можно будет получить userId
   private AuthenticationUtil authenticationUtil;

   private final ProxyManager<RateLimiterKey> proxyManager;

   @Autowired
   public RateLimiterAnnotationHandlerInterceptorAdapter(AuthenticationUtil authenticationUtil, HazelcastInstance hazelcastInstance) {
       this.authenticationUtil = authenticationUtil;
       //Для работы с Hazelcast, вам так же нужно будет создать bean HazelcastInstance
       IMap<RateLimiterKey, GridBucketState> bucketsMap = hazelcastInstance.getMap(HazelcastFrontConfiguration.RATE_LIMITER_BUCKET);
       proxyManager = Bucket4j.extension(Hazelcast.class).proxyManagerForMap(bucketsMap);
   }

   @Override
   public boolean preHandle(HttpServletRequest request,
                            HttpServletResponse response,
                            Object handler) throws Exception {

       if (handler instanceof HandlerMethod) {
           HandlerMethod handlerMethod = (HandlerMethod) handler;
           //Если в handlerMethod присутствует аннотация RateLimiter или RateLimiters, то мы её получим, если нет то наш Optional будет пуст.
           Optional<List<RateLimiter>> rateLimiters = RateLimiterUtils.getRateLimiters(handlerMethod);

           if (rateLimiters.isPresent()) {
               //Получаем path из аннотации RequestMapping (соответственно мы получим все аннотации типа: GetMapping, PostMapping и. т. д.)
               RequestMapping requestMapping = handlerMethod.getMethodAnnotation(RequestMapping.class);
               //Для получения уникального ключа мы используем связку из 2-х значений: path из RequestMapping и id пользователя
               RateLimiterKey key = new RateLimiterKey(authenticationUtil.getPersonId(), requestMapping.value());
               //Далее мы передаём в прокси ключ и значение которое будет для этого ключа в случае отсутствия значения
               Bucket bucket = proxyManager.getProxy(key, () -> RateLimiterUtils.rateLimiterAnnotationsToBucketConfiguration(rateLimiters.get()));
               //Пробуем потребить токен, если не смогли этого сделать, то выкидываем 429 ошибку
               if (!bucket.tryConsume(1)) {
                   response.setStatus(429);
                   return false;
               }
           }
       }
       return true;
   }

Также для работы с Hazelcast надо создать класс, который будем использовать в качестве ключа — RateLimiterKey:

@Data
@AllArgsConstructor
public class RateLimiterKey implements Serializable {

   private String userId;
   private String[] uri;

}

И реализовать RateLimiterUtils класс для работы с RateLimiterAnnotationHandlerInterceptorAdapter:

public final class RateLimiterUtils {

   public static BucketConfiguration rateLimiterAnnotationsToBucketConfiguration(List<RateLimiter> rateLimiters) {
       ConfigurationBuilder configBuilder = Bucket4j.configurationBuilder();
       rateLimiters.stream().forEach(limiter -> configBuilder.addLimit(buildBandwidth(limiter)));
       return configBuilder.build();
   }

   public static Optional<List<RateLimiter>> getRateLimiters(HandlerMethod handlerMethod) {
       RateLimiters rateLimitersAnnotation = handlerMethod.getMethodAnnotation(RateLimiters.class);
       if(rateLimitersAnnotation != null) {
           return Optional.of(Arrays.asList(rateLimitersAnnotation.value()));
       }
       RateLimiter rateLimiterAnnotation = handlerMethod.getMethodAnnotation(RateLimiter.class);
       if(rateLimiterAnnotation != null) {
           return Optional.of(Arrays.asList(rateLimiterAnnotation));
       }
       return Optional.empty();
   }

   private static final Bandwidth buildBandwidth(RateLimiter rateLimiter) {
       TimeUnit timeUnit = rateLimiter.timeUnit();
       long timeValue = rateLimiter.timeValue();
       long restriction = rateLimiter.restriction();
       if (TimeUnit.MINUTES.equals(timeUnit)) {
           return Bandwidth.simple(restriction, Duration.ofMinutes(timeValue));
       } else if (TimeUnit.HOURS.equals(timeUnit)) {
           return Bandwidth.simple(restriction, Duration.ofHours(timeValue));
       } else {
           return Bandwidth.simple(5000, Duration.ofHours(1));
       }
   }
}

Чуть не забыл... Нам ведь ещё нужно зарегистрировать наш интерсептор в WebMvcConfigurerAdapter:

import org.springframework.context.annotation.Configuration;
import org.springframework.web.servlet.config.annotation.InterceptorRegistry;
import org.springframework.web.servlet.config.annotation.WebMvcConfigurerAdapter;

@Configuration
public class ContextConfig extends WebMvcConfigurerAdapter {

   @Override
   public void addInterceptors(InterceptorRegistry registry) {
       registry.addInterceptor(new RateLimiterAnnotationHandlerInterceptorAdapter());
   }
}

Теперь создадим ExampleController, в котором сможем указать аннотации RateLimiter и проверить правильность работы реализации:

import com.nibado.example.customargumentspring.component.RateLimiter;
import com.nibado.example.customargumentspring.component.RateLimiters;
import com.nibado.example.customargumentspring.component.TimeUnit;
import org.springframework.web.bind.annotation.GetMapping;
import org.springframework.web.bind.annotation.PathVariable;
import org.springframework.web.bind.annotation.RestController;

@RestController
public class ExampleController {

   @RateLimiters({@RateLimiter(timeUnit = TimeUnit.MINUTES, timeValue = 1, restriction = 2), @RateLimiter(timeUnit = TimeUnit.HOURS, timeValue = 1, restriction = 5)})
   @GetMapping("/example/{id}")
   public String example(@PathVariable("id") String id) {
       return "ok";
   }
}

Мы в @RateLimiters  указали 2 ограничения:
1) @RateLimiter(timeUnit = TimeUnit.MINUTES, timeValue = 1, restriction = 2) — не можем отправлять больше 2 запросов в минуту.
2) @RateLimiter(timeUnit = TimeUnit.HOURS, timeValue = 1, restriction = 5) — не можем отправлять больше 5 запросов в час.
Это только малая часть возможностей библиотеки Bucket4j, детальнее вы можете ознакомиться тут.

За рецензию материала благодарю создателя Bucket4j Владимира Бухтоярова.

👍НравитсяПонравилось13
В избранноеВ избранном8
LinkedIn
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

Проще юзать Апи менеджер поверх или сервис меш. реализовывать такие вещи в софте крайне плохая практика.

Ти би уважніше статтю прочитав перед коментуванням

и что я должен был внимательней прочитать?
Это?

За это время я несколько раз сталкивался с Rate limiting и я бы хотел рассказать об этом подробнее. Эта статья будет интересна Java-разработчикам.

тоесть пару раз была задача, и вместо норм решения писались какието грабли в коде фиг пойми зачем. вместо того что бы вынести это на уровень вне кода.

И я уже молчу что рейти лимитинг динамическое, по ключу клиента, должно учитывать авто повторы и кучу еще всего. И вот есть сервис который берешь и юзаешь.. но вместо этого люди тратят время на написание велосипеда.

В чем резон этого?

Я понимаю если бы вы написали «пример как реализовываается рейт лимитинг в системах апи менеджмента».. было бы ок. мол просто обьяснили как работает. Но вы же говорите напротив — пишите вот так. и это не норм.

Например, нужно внедрить тарификацию для API, и мы хотим создать несколько тарифов, таких как PREMIUM, BASIC, FREE. Для каждого из этих тарифов, мы предоставляем ограниченное количество вызовов в час (можно сделать ограничение в миллисекунду, секунду, минуту, час, а можем эти все ограничения использовать вместе — это называется Bandwidth management). PREMIUM — до 1000 запросов в час, BASIC до 200 запросов в час, FREE до 50 запросов в час.

Правильно, давай таке будемо реалізовувати в якомусь апі-менеджері чи гейтвеї який не в курсі ні про які тарифи

а в нем это и реализуется) вот например cloud.google.com/apigee
А все потому что монетизация продукта никак не связана с самим продуктом.

Спасибо за интересную статью и отдельно за использование хазлкаста.

На вході в бакет треба якийсь congestion-avoidance прикручувать.

Колись давно все це саме реалізував десятьма строчками конфігу IPFW — на п’ять рівнів QoS + fair-share полоси.

в простом случае да.

Но вот мы работаем с сервисами, у которых даже разная стоимость/лимит по вызовам эндпойнтов с конкретными параметрами.

Ну типа, представьте
запросить курс валют доллара к гривне — лимит 100 в ед времени
запросить курс валют евро к гривне — лимит 200 в ед времени

запросить курс валют тугрика, тенге, ..., .., к гривне — лимит 1000 в ед времени
то есть эти 1000 делятся между всей этой группой. И групп таких может быть больше одной.

другими словами — когда лимит устанавливается согласно бизнес логике на вид данных — то на транспортном уровне вы ничего не сможете сделать, только в самом приложении придется

Ну да, я скористався тим, що в тцп вже є свій вбудований механізм, який реалізований і працює на стороні кожного клієнта. А все інше, несподівано, дуже просто реалізувалося за рахунок 2-3 рівнів ієрархії буферів з тупим раунд-робіном проштовхування пакетів.

Про всяк випадок додам, що я зовсім не пропоную вирішувати проблему прикладного рівня на транспортному. Я лиш натякаю, що задача шейпінгу трафіку є ізоморфною задачі шейпінгу запитів. І що в моєму випадку, коли цю задачу треба було вирішити для тцп-пакетів, рішення знайшлося у поєднанні буферизації із механізмом «slow start».

що задача шейпінгу трафіку

стаття починається з

Рано или поздно любой backend-разработчик сталкивается с вопросом, как ограничить количество запросов на сервер к тому или иному сервису. И не всегда мы можем реализовать это на уровне серверного оборудования (nginx, haproxy, и т. д.),
І що в моєму випадку

випадків буває повно всяких

бачив рішення коли й на рівні веб серверу вирішується

it depends ...

Але стаття, мені так здалося, чітко не про «різання трафіку»

стаття, мені так здалося, чітко не про «різання трафіку»

Ви впевнені? Ви дійсно вважаєте, що логіка лімітування темпу обробки тцп-пакетів буде сильно відрізнятися від логікі лімітування темпу обробки запитів?

Трафік я згадав лиш тому, що обидві задачі ідентичні, відрізняються лиш сутності, що утворюють трафік (пакети/запити). А в однакових задач і рішення однакові.

Ви дійсно вважаєте, що логіка лімітування темпу обробки тцп-пакетів

ви дійсно не розумієте російську мову, у:
запросить курс валют тугрика, тенге, ..., .., к гривне — лимит 1000 в ед времени
то есть эти 1000 делятся между всей этой группой. И групп таких может быть больше одной.

де тут мова про тцп-пакети?

а в статті не побачили:
Где это нужно
1. С точки зрения бизнес-логики, зачастую это используется для реализации «API Business Model».

чи не розумієте що воно такє ота бізнес-логіка?

Трафік я згадав лиш тому, що обидві задачі ідентичні

як солоне та червоне.

Як не дивно знову технічна стаття. Корисно було прочитати.

Объем Bucket (максимально допустимое количество Tokens) — 8 байт.
Текущее число Tokens в ведре — 8 байт.
Число наносекунд на генерацию одного токена — 8 байт.
Заголовок объекта — 16 байт
Итого: 40 байт

Если загрубить до 1 сек, и заменить «Число наносекунд на генерацию одного токена» на «Время последнего выделения токенов в сек», или «Разница между тек временем и последним»
то интересно насколько хуже эффективность у

1. Выделяем токены — запоминаем время
2. Если меньше нуля — смотрим на время последнего выделения токена, и сравниваем с допустимым.
если исчерпал раньше этого тайм лимита — досвидос. Если ок то п1
3. Минус 1 токен при каждом запросе

можно рискнуть и вообще не лочить это количество, между запросами от сети обычно будет ого времени, в наносекундах(какой бы там DDOS бот не устраивал). да еще и в многопоточной нагруженной среде — вероятность обращения к одному количеству — будет низкой

можно и «Текущее число Tokens в ведре» с 8 байт заменить на 4 байта, врядли когда интервал в секундах понадобится выделять больше токенов чем 2^31

Если загрубить до 1 сек — то сам опрос времени у операционки не делать, а пусть бежит поток-таймер и меняет этот общий для модуля таймер. и тоже — не лочить его.

и вот этого:

Т.е. за ~1 секунду мы потребили 200 Tokens, а соответственно превысили лимит в 2 раза.

точно не будет. Сеть и оверхед управления потоками не дадут так круто выдать больше разрешений, и получить −100 токенов
ну, пара-тройка, в штуках, лишних может быть, да

P.S.
вариант улучшения — если частая история с пиковыми нагрузками от клиента, то он ничего не запрашивает, то вот прям всю тыщу запросов ему сразу надо
на каждом X запросе — делать пункт 2, и если время ок — то докидывать неиспользованные токены или какое фикс число, и т.п.

Неочевидный вопрос — зачем всё хранить в оперативе?
Неочевидный вопрос — зачем взяли Java, то есть JWM для нагруженной примитивной задачи?

Ну и крайне серьёзный баг, которого вы подобными примитивизмом НИКАК не избежите: когда для одной задачи клиентской части требуется выполнить несколько запросов, или несколько десятков. И если их НЕ выполнить хоть один, потребуется повторять запрос. В лучшем случае автоматикой, в худшем — человеком. ИТОГ: Однажды заполнив пул ты получишь dead lock, когда ни один блок запросов не выполняется, но запросы продолжают выжираться, продолжая заполнять пул.

Откуда знаю: 2006 год, именно так Яндекс массово потерял клиентов своей почты. Защитившись даже не от ботов, а от собственной жадности растить сервера вместе с ростом числа клиентов и объёмов почты, в результате потеряли всех и массово, оставив только тех, кто мылом пользуется редко.

Добро пожаловать в мир многопоточности. Если бы не эти «мелочи», в многопоточность бы умела каждая обезьяна.

PS. А что по быстродействию? Как по мне, то тот запрос, который собираются выполнить, кушает куда меньше, чем его лимитер. Тебя точно Corezoid не кусал, вспоминай. Это местное поделие, рождённое «работать в нашем банке большая честь» буквально эталон как делать не надо.

А вы пример не смотрели? Алгоритм реализуется «поверх» бизнес-логики и если мой апп поднимается на JVM и для реализации большого ентерпрайза я использую Java, то логично что в этом же апп я буду внедрять этот алгоритм, а не писать отдельный апп.
Зачем всё хранить в оперативе? — Сотни тысяч запросов в секунду может идти на запись и чтение и нам важно использовать малое количество времени для этого, под капотом Bucket4j для работы с распределенными на основе JSR 107 использует EntryProcessor который позволяет сократить количество запросов для работы с распределенным кэшом.
Насчёт многопоточности я советую посмотреть устройство JCache и то как реализована многопоточность в распределенных кэшах, таких как: Apache Ignite, Hazelcast, и т д и думаю вопрос у Вас отпадёт. Насчёт быстродействия пожалуй не буду отвечать, опять скажу что Вам надо посмотреть что такое кэш, почему данные хранятся с оперативной памяти и прочитать устройство Bucket
Вот Вам доклад: www.youtube.com/watch?v=Yw7A1rIX87A&t=8s

Я же так и сказал что не в многопоточности дело как таковой, а в атомарности. При квантовании запросами появляется неразрешимая проблема — у клиента операции квантуются иначе, и то что для клиента одна операция, с точки зрения запросов будет десятки.

Многопоточность привёл как пример схожей проблемы: там блокировки потоков нужно брать строго по очереди, не допуская перекрёстного блокирования. Иначе dead lock не заставит себя ждать. В данном случае под dead lock попадают операции клиента.

Другими словами, эффективного лимитера с жёстким обрубом по границе в момент запроса — не существует даже в теории. Единственный эффективный механизм — мягкий лимит, шейпинг по сути, когда запросы попадают в очередь. И вот уже по мере снижения скорости работы клиент будет видеть, когда надо бы подкинуть денежек на более быстрый тариф. Но не так что моментально всё встало, с 10-кратным и выше перерасходом, и ничего не работает до конца дня.

По поводу сотен тысяч запросов в секунду — это понятно. Вопрос был зачем ВСЁ хранить в оперативе. Ежу ж понятно, что запросы массово идут от одних и тех же источников, соответственно эффективной структурой является кеш поверх SSD, и это позволяет хорошо так сэкономить оперативу.

А по поводу джавы — я ж не предлагаю писать всё на других языках. Лишь самую нагруженную часть. Потому как ресурсов тратится много, а сам ресурс крохотный, виртуальная машина крайне сильно проигрывает в таких задачах. Гораздо эффективнее эта задача решилась бы на нативном приложении/либе, а вот уже вся обёртка для редко используемых запросов была бы на Java.

Как по мне, так вы вообще пытаетесь изобрести велосипед, который давно умеют базы данных. Может оно и правильно, но тогда это должен быть более быстрый велосипед. А быстрый — я сказал как, на основе очереди. Когда запросы пролетают все, но в момент перегрузки лимита становятся в очередь. А уже при перегрузке очереди тупо дропаются. Этим сильно разгружается лимитер: его можно обновлять скажем раз в минуту или в 30 секунд. По сути он просто счётчик.

Пойми, задачи жёстко зарезать трафик запросов нет вообще. Есть задачи две: принудить клиента платить по потребностям; лимитнуть левый трафик. Грубо говоря, нужен не таможенный пункт контроля, а обычный светофор.

когда для одной задачи клиентской части требуется выполнить несколько запросов, или несколько десятков. И если их НЕ выполнить хоть один, потребуется повторять запрос

Кроме рейт лимитера (который скорее стандарт чем исключение) есть хуллиард причин по которым запрос может упасть (заэкспайрилась аутентификация, сеть отвалилась, еще хуллиард минус 2 причины на ваш выбор...). Так что если ты задизайнил приложение так, что у тебя отлуп от рейт лимитера вызывает серьезные проблемы, то ты просто сам себе злобный буратин, и рейт лимитер тут не при делах.

Точно не в Hewlett Packard работаешь? Делать нормально бэкенд — не наш метод! Когда можно тупо перевести стрелки.

Я же не говорю, что приложение вылетит. Как раз наоборот, оно будет пытаться снова и снова. Накручивая рейт лимитер. Или ты предлагаешь перенести логику на приложение, которое уже само должно понимать, как рейт лимитер пашет, опрашивать его состояние и пытаться прорваться?

Понимаешь ли, в современных приложениях запросы-то маленькие. Но их много. Так что приложение писать под говённый бэкенд придётся сильно дороже. И всё равно говно получится.

Ну и на вопрос так и не ответили — как быть с проблемой, что исполнение самого запроса стоит дешевле, чем его ограничение? В конце концов, этот лимитер можно тупо ДДОСом уронить вообще не заморачиваясь. Он сожрёт сам себя. А можно самым обычным говнокодом, когда клиент будет пытаться дёргать то, что не дёргается. Ведь я правильно понимаю, ответ клиенту не идёт, тупо дроп запроса и вуаля?

А если бы такие как ты писали IP протокол, сейчас бы всё через UDP работало. Ну а чё, лимитеры зато прекрасно бы отрабатывали, вообще не заморачиваясь.

PS. А по поводу злобного буратины — я же назвал прецедент, обычные почтовые клиенты, даже не IMAP зачастую, а POP3. Яндекс решил, что вот вам столько-то лимит, и пусть весь мир подождёт. Весь мир и подождал. А не дождавшись, свалил. И это не один день продолжалось, их технари тупо голову в песок аки страусы и втирали что так и должно быть, зато посмотрите как сервера освободились.

ИТОГ: Однажды заполнив пул ты получишь dead lock, когда ни один блок запросов не выполняется, но запросы продолжают выжираться, продолжая заполнять пул.

Во-первых, по описанию, это livelock, а не deadlock, раз «запросы продолжают выжираться».
Во-вторых, а почему он вдруг возникнет? Ты предполагаешь клиент, который делает 10 запросов, но на отказ например сделать 10-й по рейту — не спит несколько секунд, а начинает всё сначала? Судя по следующим сообщениям — так оно и есть, но сам этот подход по себе как-то не очень, надо пытаться повторять отдельный запрос, если был отказ.

(На самом деле я тут, конечно, та сова, которая «мышки, станьте ёжиками». Отловить такой код отказа и сделать повтор — а в общем случае нарисовать какой-то слой у клиента, который будет делать эти повторы автоматически — это ещё кусок работы, а если фреймворк на это не рассчитан, начнётся адъ и сектор газа. Увы.

Но защита подобного рода в общем случае таки нужна. Возможно, лучше лимитировать где-то раньше, а клиентам выдавать токены на полное выполнение операции... это уже по вкусу и обстановке.

Лимит торможением, конечно, лучше. Но на это тоже идёт затрата ресурсов сервера.)

Интересная инфа, спасибо.

Текущее число Bucket в ведре — 8 байт.

Наверное текущее число токенов в ведре?

RateLimiterAnnotationHandlerInterceptorAdapter

Ох уж этот Спринг. Напомнило www.javadoc.io/...​StuffAnywhereVisitor.html

Спасибо за внимательность! Исправил. P.S Ух, и правда длинное название HasThisTypePatternTriedToSneakInSomeGenericOrParameterizedTypePatternMatchingStuffAnywhereVisitor

Спасибо большое автору, очень крутая статья и доходчиво все написано.

Подписаться на комментарии