The fixed window rate limiter re-sets the available tokens when the next window is reached, which is also the same length.
Tokens are taken from the window and once exhausted, taking is no longer possible.
This algorithm could be used when dealing with APIs that rate-limit you, and you don't want to exceed their rate limits
Test cases in Scala
assert( sampleFixedWindow.take1.nonEmpty, "One last remaining item can be taken" ) assert( sampleFixedWindow.take1.flatMap(_.take1).isEmpty, "Cannot take 2 before a refresh" ) assert( sampleFixedWindow.updateTime(sampleInstant.plusSeconds(4)).remaining == sampleFixedWindow.remaining, "4 second refresh has no effect" ) assert( sampleFixedWindow.updateTime(sampleInstant.plusSeconds(5)).remaining == sampleFixedWindow.remaining, "5 second refresh, does not yet re-set it" ) assert( sampleFixedWindow .updateTime(sampleInstant.plusSeconds(5).plusMillis(1)) .remaining == 5, "5 second & a bit refresh, resets it back to 5" ) assert( sampleFixedWindow.updateTime(sampleInstant.plusSeconds(500)).remaining == 5, "500 second refresh, resets it back to 5" )
Algorithm in Scala
28 lines of Scala (compatible versions 2.13 & 3.0), showing how concise Scala can be!
The key part here is the 'updateTime' function, which checks for whether we are after the end of the current window. If we are, then we re-set the 'remaining' token counter.
We also want to make sure that the last window is updated, which is why we update the 'startOfWindow' value as well. (this is © from www.scala-algorithms.com)
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!
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.