#460 Create a suspending rate limiter

[jensim]

trafficstars

Create a simple suspending rate limiter that delays incoming requests if the limit is reached.

The time of delay is calculated on request, and no queue or other synchronization is required.

On creation of the rate limiter an infinite sequence of delay times is generated. This sequence is cycled at the same size as the number of events per second. These delays never diverge more than one from each other. The sum of one cycle of delays is always exactly 1000 ms.

An newly created rate limiter passes the first event instantly. A rate limiter that has been unused for enough time will pass it's next event instantly.

[ghost]

This implementation doesn't allow bursts and lacks tryAcquire function, which is unacceptable in my opinion. Also, you should probably move it to kotlinx.coroutines.sync so that it can be used on all platforms just like Mutex and Semaphore.

[jensim]

Hi @nordiauwu , and thank you for that warm welcome. It's always so nice when strangers on the internet give short and to the point feedback without saying hello :-D

I interpret your feedback like this:

Wow! Great job @jensim ! This is a feature I would really like to see myself, just with the adition of a tryAquire function that allows you to fail instead of delaying. Do you think you could implement that as well? Pretty please? It would really make my day. On another point, I think that the packaging should maybe be kotlinx.coroutines.sync

[ghost]

I'm really sorry if you found my comment rude, I didn't mean to offend you in any way.

[jensim]

On the topic of not allowing bursts.. It's not supposed to allow bursts. It's a rate limiter, not aOnEveryTimeTheClockMovesOneSecondRefreshNumberOfAllowedSuspensionsToPass

I've reflected a lot on this, and found that if a rate limiter allows bursts it's kind of counter to what a rate limiter is protecting from. It's there to create an even load. The opposite of a burst. But thank you @nordiauwu for contributing to the discussion.

If i had time to create a PR that was 2 or even 10 times larger, maybe I would make it include things like allowBurstingForTimeInterval or tryAcquire, but that is just not something I need. I've waited for long enough for #460 to be Implemented, or even put up on the backlog, so I made what I think is a MVP of a Rate Limiter. I don't expect it to be merged, I just added the code that I use myself whenever I want a suspending Rate Limiter

[jensim]

I'm really sorry if you found my comment rude, I didn't mean to offend you in any way.

It's ok, I'm just used to the warm welcomes in the Rust-part of github.com

[ghost]

Consider an API endpoint that sends a message to the user. Without a rate limit, some bad person surely will abuse that, but at the same time, we want to let our users send a few messages in a row. That's why the support of bursts is a necessity.

[ghost]

It's there to create an even load. The opposite of a burst.

Your implementation has nothing to do with that, especially because there's no tryAcquire. For example if you want to limit the number of requests handled by your server, it shouldn't suspend but call tryAcquire and immediately respond with 429 Too Many Requests if there are no permits available.

[tnleeuw]

On the topic of not allowing bursts.. It's not supposed to allow bursts. It's a rate limiter, not aOnEveryTimeTheClockMovesOneSecondRefreshNumberOfAllowedSuspensionsToPass

I've reflected a lot on this, and found that if a rate limiter allows bursts it's kind of counter to what a rate limiter is protecting from. It's there to create an even load. The opposite of a burst. But thank you @nordiauwu for contributing to the discussion.

If i had time to create a PR that was 2 or even 10 times larger, maybe I would make it include things like allowBurstingForTimeInterval or tryAcquire, but that is just not something I need. I've waited for long enough for #460 to be Implemented, or even put up on the backlog, so I made what I think is a MVP of a Rate Limiter. I don't expect it to be merged, I just added the code that I use myself whenever I want a suspending Rate Limiter

Hi Jens,

I commented on your PR before seeing these comments, and I did make a comment on bursting behaviour as well. Apologies for that.

I needed rate-limiting not to even out a load, but to avoid requests to external APIs failing by exceeding their assigned rate-limit. From this perspective, burst behaviour was fine.

Not allowing bursts will unnecessarily slow down some activities. Ideally, both kinds of behaviour would be allowed.

I do have my own implementation of a rate limiter which I wrote a few years ago and which also uses Kotlin coroutines -- perhaps something can be worked out to have 2 implementations of the same interface depending on a flag?

[tnleeuw]

It's there to create an even load. The opposite of a burst.

Your implementation has nothing to do with that, especially because there's no tryAcquire. For example if you want to limit the number of requests handled by your server, it shouldn't suspend but call tryAcquire and immediately respond with 429 Too Many Requests if there are no permits available.

If the point of the rate limiter is, to limit the number of requests made to an external resource, then you need to acquire() with delay.

I agree that when you want to implement the per-user server-side rate limiter you need a tryAcquire(), this is a requirement that I had not yet considered myself for my own implementations. I don't think it is easy to do this with the current design of this PR, because it doesn't actually hand out permits.

The design I have, which does allow bursts, is based on a bucket (Channel) the size of allowed events per second so it does work around the idea of "permits" and should allow for a tryAcquire() behaviour.

[lowasser]

We've been thinking about this some at Google, especially based on Guava's experience with RateLimiters, which has gotten some negative feedback for its inability to burst or to manage bursts. Here are some things we've been thinking about:

• Many permits per operation -- e.g. consider a bytes-per-second rate limit, where limits might be e.g. 10MB/s, and you want to measure one byte per permit. Such a thing is useful, but you definitely don't want to be doing one million separate permit emits per second, you want to calculate when the right number of permits are available and take them then.
• Relatedly: use proper time types for everything. kotlin.time is adequate for this purpose; don't juggle ms yourself.
• A distinction between "hertz" rate limits, where permits are released at a specified rate, versus "N per Duration" rate limits with no burstiness constraints.
• Burstiness can be expressed and controlled as an intersection of rate limits -- "release 100 permits per second, never acquire more than 10 per millisecond".
• some use cases find warmups and cooldowns useful; these can be integrated too

We've got some draft implementations that support all of these, though they're still somewhat messy. tryAcquire should be doable, too, though we haven't got that in there yet.

[tnleeuw]

Hi @nordiauwu , and thank you for that warm welcome. It's always so nice when strangers on the internet give short and to the point feedback without saying hello :-D

Hi Jens,

As random strangers on the internet among each other, I have to admit that when I saw that a PR was created for this issue I expected it to be created by a JetBrains employee. 😳

[jensim]

It's there to create an even load. The opposite of a burst.

Your implementation has nothing to do with that, especially because there's no tryAcquire. For example if you want to limit the number of requests handled by your server, it shouldn't suspend but call tryAcquire and immediately respond with 429 Too Many Requests if there are no permits available.

My implementation has everything to do with that (Creating even load). Just not for the specific ways you want it to. What you are describing may be a IntervalLimiter? I've started creating a RateLimiter like the Guava kind, I'm not payed to do this, so I'm not beholden to implement all features for you or this project. I do not intend to create everything for all possible scenarios. It's not my intend to be rude, just stating again that I'm making this PR to kick the #460 issue that I've been wanting fixed for a long time.

Creating a IntervalLimiter should not be very diffifcult using the same mathematical-suspension approach, please join me @nordiauwu fork and add some commits for a IntervalLimiter, the way you want it. :-)

[jensim]

Hi @nordiauwu , and thank you for that warm welcome. It's always so nice when strangers on the internet give short and to the point feedback without saying hello :-D

Hi Jens,

As random strangers on the internet among each other, I have to admit that when I saw that a PR was created for this issue I expected it to be created by a JetBrains employee. 😳

I'm glad I got to surprise you (and maybe others) :-) Talking about making changes and writing on the issue tracker is good stuff. But a working MVP is something tangible. So I went for the later in hopes of creating momentum.

[tnleeuw]

Hi @nordiauwu , and thank you for that warm welcome. It's always so nice when strangers on the internet give short and to the point feedback without saying hello :-D

Hi Jens, As random strangers on the internet among each other, I have to admit that when I saw that a PR was created for this issue I expected it to be created by a JetBrains employee. 😳

I'm glad I got to surprise you (and maybe others) :-) Talking about making changes and writing on the issue tracker is good stuff. But a working MVP is something tangible. So I went for the later in hopes of creating momentum.

You certainly seemed to have spurred more people into action. :)

I did write my own rate-limiter, but never thought to create a PR and add it to this ticket. (In all honesty, I had already forgotten about this ticket by now!)

[jensim]

We've been thinking about this some at Google, especially based on Guava's experience with RateLimiters, which has gotten some negative feedback for its inability to burst or to manage bursts. Here are some things we've been thinking about:

* Many permits per operation -- e.g. consider a bytes-per-second rate limit, where limits might be e.g. 10MB/s, and you want to measure one byte per permit.  Such a thing is useful, but you definitely don't want to be doing one million separate permit emits per second, you want to calculate when the right number of permits are available and take them then.

* Relatedly: use proper time types for everything.  kotlin.time is adequate for this purpose; don't juggle ms yourself.

* A distinction between "hertz" rate limits, where permits are released at a specified rate, versus "N per Duration" rate limits with no burstiness constraints.

* Burstiness can be expressed and controlled as an intersection of rate limits -- "release 100 permits per second, never acquire more than 10 per millisecond".

* some use cases find warmups and cooldowns useful; these can be integrated too

We've got some draft implementations that support all of these, though they're still somewhat messy. tryAcquire should be doable, too, though we haven't got that in there yet.

Hi @lowasser ! I'm glad you joined the discussion :-D I thanks for the pointers On the topic of semantics I call the "herts"-limiter RateLimiter, and the "N per Duration" an IntervalLimiter. If you have some "messy" code, please share it!

[jensim]

Hi @nordiauwu , and thank you for that warm welcome. It's always so nice when strangers on the internet give short and to the point feedback without saying hello :-D

Hi Jens, As random strangers on the internet among each other, I have to admit that when I saw that a PR was created for this issue I expected it to be created by a JetBrains employee. 😳

I'm glad I got to surprise you (and maybe others) :-) Talking about making changes and writing on the issue tracker is good stuff. But a working MVP is something tangible. So I went for the later in hopes of creating momentum.

You certainly seemed to have spurred more people into action. :)

I did write my own rate-limiter, but never thought to create a PR and add it to this ticket. (In all honesty, I had already forgotten about this ticket by now!)

:-D I'm really glad I got all of us talking about this here!

I've been using Guava rateLimiter.. And every few months, I come back to look awkwardly at #460 to see if there's any progress..

[jensim]

I've looked at the kotlin.time api now @lowasser, and it looks really nice. BUT this looks like it might make the delays sum up to more than what they ought to (1000 ms on one second)

public suspend fun delay(duration: Duration): Unit = delay(duration.toDelayMillis())
internal fun Duration.toDelayMillis(): Long = if (this > Duration.ZERO) toLongMilliseconds().coerceAtLeast(1) else 0

Another thing was the inability to get diff between two TimeMarks

public inline operator fun TimeMark.minus(other: TimeMark): Duration = throw Error("Operation is disallowed.")

Without that, how do you suggest i avoid "juggling" raw ms myself?

[jensim]

I wrote up a tiny test to poke at the kotlin time api, and see how it would do for sub ms scheduling - rather than read all code in existence and learn everything.

    @org.junit.jupiter.api.Test
    @org.junit.jupiter.api.Timeout(value = 2, unit = java.util.concurrent.TimeUnit.SECONDS)
    @kotlin.OptIn(kotlin.time.ExperimentalTime::class)
    internal fun `test kotlin time`():Unit = runBlocking {
        val eventsPerSecond = 1_000_000
        val delayNanos: kotlin.time.Duration = kotlin.time.Duration.nanoseconds(1_000_000_000L / eventsPerSecond)
        (1..eventsPerSecond).forEach { kotlinx.coroutines.delay(delayNanos) }
    }

This fails ofc, for the reason I stated above.. the delay function that takes a kotlin.time.Duration as argument always suspends at least 1 ms. :-/ I could handle that in the calculation of permit-suspension.. But with the kotlin.time api not helping be very much with comparative time arithmatics, I don't see how I would use it in order to get around juggling the time as numbers.

A valid point made by @tnleeuw is to keep nanotime instead of wall time millis..

[jensim]

@lowasser - I think I've managed to work around the time types in a multi platform way now. Thank you for the consice, and great feedback. What I'm still lacking is warm ups. But as I'm just a lowly hobbyist, I think what I have here goes somewhat beyond MVP.

[ghost]

Looks good to me, thank you for the contribution. Hope someone at JetBrains will review this soon :)

[qwwdfsad]

In the future, to avoid doing work in vain, I strongly suggest initiating the discussion as our contribution guide suggests

[jensim]

In the future, to avoid doing work in vain, I strongly suggest initiating the discussion as our contribution guide suggests

It was not in vain, I needed a rate limiter for a project, and I wanted to experiment a bit. Would not have done the work if it was not selfRewarding ☺️

Also, I think the discussion had been started already, and sometimes an external force or code example might help drive the discussion forward 😅

[tnleeuw]

The same for me -- I need a rate limiter for my own projects some years ago and thus built one that suits my use-cases.

​

​I then commented on these changes to see that my own use-cases can still be implemented. 🙂

​

On Sep 20 2022, at 6:33 PM, Jens Brimfors @.***> wrote:

In the future, to avoid doing work in vain, I strongly suggest initiating the discussion as our contribution guide (https://github.com/Kotlin/kotlinx.coroutines/blob/master/CONTRIBUTING.md) suggests

It was not in vain, I needed a rate limiter for a project, and I wanted to experiment a bit. Would not have done the work if it was not selfRewarding ☺️

—

Reply to this email directly, view it on GitHub (https://github.com/Kotlin/kotlinx.coroutines/pull/2799#issuecomment-1252608581), or unsubscribe (https://github.com/notifications/unsubscribe-auth/AA4K2DLKCETKIXUHYCKGPLLV7HRMLANCNFSM47R27VZA).

You are receiving this because you were mentioned.

[jensim]

Closing for inactivity.