In some systems, you may want to limit the number of requests per a certain time unit. While some rate limiting algorithms would focus on not exceeding a certain number of requests in flight, there may be cases where eg your application may be reaching out to another application which has a certain limiting of number of requests in any one hour, for example. We wish to limit that by possibly pushing back our clients.
Test cases in Scala
Algorithm in Scala
44 lines of Scala (compatible versions 2.13 & 3.0).
This rate limiter uses an immutable Scala queue and stores the timestamp of each incoming request.
When the number in the rate is exceeded, the 'processItem' method will return None, to indicate that we cannot accept a request; if we can, then we return the updated limiter/queue that now contains this selected request. (this is © from www.scala-algorithms.com)
Everything is covered deeply with unit tests.
Scala concepts & Hints
The 'Option' type is used to describe a computation that either has a result or does not. In Scala, you can 'chain' Option processing, combine with lists and other data structures. For example, you can also turn a pattern-match into a function that return an Option, and vice-versa!
Pattern matching in Scala lets you quickly identify what you are looking for in a data, and also extract it.
Stack safety is present where a function cannot crash due to overflowing the limit of number of recursive calls.
This function will work for n = 5, but will not work for n = 2000 (crash with java.lang.StackOverflowError) - however there is a way to fix it :-)
In Scala Algorithms, we try to write the algorithms in a stack-safe way, where possible, so that when you use the algorithms, they will not crash on large inputs. However, stack-safe implementations are often more complex, and in some cases, overly complex, for the task at hand.
In Scala, tail recursion enables you to rewrite a mutable structure such as a while-loop, into an immutable algorithm.