Scala algorithm: Token Bucket Rate Limiter
Published
Algorithm goal
While similar to LeakyBucketRateLimiter, it works a bit differently, and is specifically useful as a network layer algorithm in order rate-limit packets:
Each packet consumes a number of tokens; tokens are added to the bucket at a particular rate, up to a limit and any overflow is discarded.If there are not enough tokens for a packet to consume, then the packet is discarded; otherwise it is passed on.
Design an algorithm to model this, in pure-functional immutable Scala.
Test cases in Scala
This algorithm comes with test cases.
To see the free test cases for all our algos, as well as run them in our TDD IDE, Register (free).
Algorithm in Scala
41 lines of Scala (compatible versions 2.13 & 3.0).
Get the full algorithm !
or
'Unlimited Scala Algorithms' gives you access to all the 89 published Scala Algorithms! Plenty to master your Scala algos skills!
Upon purchase, you will be able to Register an account to access all the algorithms on multiple devices.
Explanation
This solution was developed through test-driven development (TDD).
The token bucket is fully described by a combination of the rate, capacity and the time there was a last refill. (this is © from www.scala-algorithms.com)
Using immutable programming, it is even possible to have the rate and capacities vary across time very easily.
Scala concepts & Hints
Drop, Take, dropRight, takeRight
Scala's `drop` and `take` methods typically remove or select `n` items from a collection.
Option Type
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!