Implement suspendable RateLimiter

[qwwdfsad]

Primitive, which distributes permits at the fixed rate or suspends current coroutine until it's available. Such primitive is useful in a lot of server-side application to throttle requests to external services or other subsystem.

One of the first consumers of such feature may be Ktor (see https://github.com/ktorio/ktor/pull/473) UPD: https://stackoverflow.com/questions/52995552/how-to-implement-a-ratelimit-across-mutiple-coroutines-efficently

[vladimir-bukhtoyarov]

Bucket4j already covers this functionality.

[tnleeuw]

Bucket4j already covers this functionality.

And so does Guava rate limiting, but neither does it with suspending functions and both seem to handle their blocking within their API, so you still have to wrap it.

[IRus]

Primitive, which distributes permits at the fixed rate or suspends current coroutine until it's available.

Or immediately returns (like offer in channels), to respond on current request, that it was rate limited (for example).

[tnleeuw]

Primitive, which distributes permits at the fixed rate or suspends current coroutine until it's available.

Or immediately returns (like offer in channels), to respond on current request, that it was rate limited (for example).

If we want to implement rate-limiting in our own software, the most transparent way to do that is not to return until the ratelimit-interval has been reached. Returning with a special code doesn't provide any convenience, because then you have to know when you can retry the operation -- the point of a suspending rate-limiter is to transparently handle this for you.

The situation here is not that you want to know that an API which you are calling returned a status that request-rate-limit was exceeded, but that internally you want to limit rate at which some events / requests / whatever are firing.

[IRus]

If we want to implement rate-limiting in our own software, the most transparent way to do that is not to return until the ratelimit-interval has been reached.

Yes, it can be better in case when retry expected, but in case of overload (like you setup hard limit) you should drop request asap.

[tnleeuw]

If we want to implement rate-limiting in our own software, the most transparent way to do that is not to return until the ratelimit-interval has been reached.

Yes, it can be better in case when retry expected, but in case of overload (like you setup hard limit) you should drop request asap.

But this is not something which you can handle in a general-purpose rate limiter, because it depends on the actual call you make. The rate-limiter doesn't make the call, it only allows your co-routine to make calls at given max rate. So in your own code, you should look at the return of whatever call you are making, to see if it makes sense to continue, retry, or abort.

[IRus]

But this is not something which you can handle in a general-purpose rate limiter, because it depends on the actual call you make. The rate-limiter doesn't make the call, it only allows your co-routine to make calls at given max rate.

It depends on design of RateLimiter, so currently idk is it will be possible or not.

[czp3009]

val requestPerSecond = 20L
val rateLimiter = produce {
   while (true) {
        send(Unit)
        delay(1_000 / requestPerSecond)
    }
}

Use rateLimiter.receive() in the place needed.

Don't forget to cancel it.

[jensim]

I made a PR here #2799 And a tiny CI-pipe to test it here

[jensim]

My PR (#2799) now include both a RateLimiter and a IntervalLimiter, in case some more poeple are interested in taking a peek 🙂

Ive gotten tons of great feedback, and would appreciate more

[vlsi]

@jensim , hi, it is great you implemented a limiter, however, have you considered https://github.com/bucket4j/bucket4j?

It looks like they have well-thought API, and they cover many cases like bursts, etc.

[vlsi]

@qwwdfsad , I'm not sure what is your view, however, I just asked what bucket4j maintaners think of writing the core in Kotlin.

[jensim]

That's a good suggestion @vlsi

This would however bring rate limiting capabilities to all platforms without additional dependencies. And to me asynchronous execution often brings the need for setting a reasonable pace through some means. That's why I think it's a good thing to have a basic implementation available in the core. And if someone needs something more exact or has some other requirements, then other libs might satisfy the needs of that user on that platform.

[vlsi]

@jensim , my idea was to convince bucket4j to move to Kotlin, so bucket4j automatically becomes available on all the platforms. In that regard, "minimal impl" does not sound to be that needed (especially, it would be sad to have slightly incompatible interfaces in-core and in the library)

The challenge is that the current bucket4j has no dependencies, which sounds like a plus for JVM consumers. When migrating to Kotlin, it could probably avoid kotlin-stdlib, however, it would probably be hard to avoid kotlinx-datetime since client APIs should probably have something like Duration in the API.

[qwwdfsad]

It would be nice to have suspend capabilities in bucket4j even without multiplatform support. We probably can assist with reviewing coroutine-specific parts as well. I believe that they don't need to depend on kotlinx-datetime (i.e. Duration is part of the standard library) and cannot avoid standard library dependency anyway (e.g. the kotlinc puts enhanced null-checks on arguments of all public methods, and these checks are located in stdlib).

The biggest problem with getting rate limited in kotlinx-coroutines is its specificity and a huge space of possible configuration choices, which basically can be boiled down to two scenarios:

• We'll decide to develop a variety of operational modes, configurable parameters and extension points. In such a case, we are going to reinvent the whole bucket4j, and it's definitely not our goal
• We'll decide that we want to provide the simplest possible solution that suffices 90%+ of uses, something similar to Guava's rate limiter. It is much more realistic, but has its own problems: it requires a significant effort to research the design space and use-cases, and at this point, we can start questioning ourselves why it should be part of kotlinx-coroutines at all.

Anyway, it is out of our focus right now; IMO the best possible outcome is to have something like bucket4j-kotlin that is properly integrated with suspend API and recommend people using it

[vlsi]

cannot avoid standard library dependency anyway (e.g. the kotlinc puts enhanced null-checks on arguments of all public methods, and these checks are located in stdlib).

Fair point. I missed that indeed. So the possibilities are: a) Just depend on kotlin-stdlib (which might be not that bad in fact) b) Shade the needed bits of kotlin-stdlib like in https://jakewharton.com/shrinking-a-kotlin-binary/ (the shaded module might come as a separate group:artifact id)

---

Let me see if bucket4j-kotlin-coroutines could be added to bucket4j. @jensim WDYT? I think it might be worth trying adding bucket4j-kotlin (e.g. to make APIs more Kotlin-friendnly) and bucket4j-kotlin-coroutines (with suspension support and extra dependency on -coroutines)

[qwwdfsad]

I don't think that shading standard library is a way to go; it may work for a while, but it definitely won't be future-proof

[jensim]

@vlsi 🤷🏼

My oppinion is that anything is better than nothing.

When I started looking at this, I hadn't found bucket4j, which would probably fit the use case I had back then. (A suspending rate limiter that would work with Kotlin coroutines, with very few dependencies)

In most JVM cases, a simple long var holding the last execution epoch time, and maybe a mutex, to delay any concurrent execution.. That neatly covers the RateLimiter in my oppinion. So I tend to reimplantat it every time, and tweak it to the needs of that case 🙈🥳 The interval limiter is more tricky, allowing a bucket of events per interval.

[ksletmoe]

Sorry to necro this thread, but if others found this because they were looking for a suspending / non-coroutine-blocking rate limiter (like I originally did), I wrote a Kotlin wrapper around bucket4j which suspends: https://github.com/ksletmoe/Bucket4k

It'd be great if the bucket4j folks rewrite the core in Kotlin, but in the mean time this should be useful.