Created
July 27, 2023 21:14
-
-
Save GordPavel/464a2792b82744ad7ceaca8d6910ee58 to your computer and use it in GitHub Desktop.
Comparison of rate limiters
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Scratch { | |
| public static void main(String[] args) { | |
| System.out.println("Counter based rate limiter"); | |
| testLimiter(new CounterBasedSlidingWindowRateLimiter( | |
| 3L, | |
| 60L | |
| )); | |
| System.out.println("=============================="); | |
| System.out.println("Queue based rate limiter"); | |
| testLimiter(new QueueBaseSlidingWindowRateLimiter( | |
| 3L, | |
| 60L | |
| )); | |
| } | |
| private static void testLimiter(RateLimiter rateLimiter) { | |
| System.out.printf("Try acquire 50, should be true: %b%n", rateLimiter.canExecute(50L)); | |
| System.out.printf("Try acquire 54, should be true: %b%n", rateLimiter.canExecute(54L)); | |
| System.out.printf("Try acquire 57, should be true: %b%n", rateLimiter.canExecute(57L)); | |
| System.out.printf("Try acquire 99, should be false: %b%n", rateLimiter.canExecute(99L)); | |
| System.out.printf("Try acquire 100, should be false: %b%n", rateLimiter.canExecute(100L)); | |
| System.out.printf("Try acquire 105, should be false: %b%n", rateLimiter.canExecute(105L)); | |
| System.out.printf("Try acquire 110, should be true: %b%n", rateLimiter.canExecute(110L)); | |
| System.out.printf("Try acquire 111, should be false: %b%n", rateLimiter.canExecute(111L)); | |
| System.out.printf("Try acquire 112, should be false: %b%n", rateLimiter.canExecute(112L)); | |
| System.out.printf("Try acquire 115, should be true: %b%n", rateLimiter.canExecute(115L)); | |
| System.out.printf("Try acquire 116, should be false: %b%n", rateLimiter.canExecute(116L)); | |
| System.out.printf("Try acquire 118, should be true: %b%n", rateLimiter.canExecute(118L)); | |
| } | |
| public interface RateLimiter { | |
| boolean canExecute(Long time); | |
| } | |
| private static class QueueBaseSlidingWindowRateLimiter implements RateLimiter { | |
| private final Long capacity; | |
| private final Long window; | |
| private Node head; | |
| private QueueBaseSlidingWindowRateLimiter( | |
| Long capacity, | |
| Long window | |
| ) { | |
| this.capacity = capacity; | |
| this.window = window; | |
| this.head = new Node(null); | |
| this.head.next = head; | |
| this.head.prev = head; | |
| } | |
| @Override | |
| public boolean canExecute(Long time) { | |
| if (this.head.value == null) { | |
| this.head.value = time; | |
| return true; | |
| } | |
| Node tail = this.head.prev; | |
| long counter = 0L; | |
| while (tail != this.head && counter < this.capacity) { | |
| counter++; | |
| tail = tail.prev; | |
| } | |
| if (counter + 1 < this.capacity) { | |
| addToTail(time); | |
| return true; | |
| } | |
| boolean canHandle = (time - tail.value) >= this.window; | |
| tail = tail.next; | |
| if (!canHandle) { | |
| return false; | |
| } else { | |
| addToTail(time); | |
| Node curTail = this.head.prev; | |
| tail.prev = curTail; | |
| curTail.next = tail; | |
| this.head = tail; | |
| return true; | |
| } | |
| } | |
| private void addToTail(long value) { | |
| Node oldTail = this.head.prev; | |
| Node newTail = new Node(value); | |
| oldTail.next = newTail; | |
| newTail.prev = oldTail; | |
| head.prev = newTail; | |
| newTail.next = head; | |
| } | |
| private static class Node { | |
| Long value; | |
| Node prev; | |
| Node next; | |
| public Node(Long value) { | |
| this.value = value; | |
| } | |
| } | |
| } | |
| /** | |
| * Copy of <a href="https://dev.to/satrobit/rate-limiting-using-the-sliding-window-algorithm-5fjn">limiter.</a> | |
| */ | |
| private static class CounterBasedSlidingWindowRateLimiter implements RateLimiter { | |
| private final Long capacity; | |
| private Long curTime; | |
| private Long prevCounter; | |
| private Long curCounter; | |
| private final Long window; | |
| private CounterBasedSlidingWindowRateLimiter( | |
| Long capacity, | |
| Long window | |
| ) { | |
| this.capacity = capacity; | |
| this.curTime = 0L; | |
| this.prevCounter = capacity; | |
| this.curCounter = 0L; | |
| this.window = window; | |
| } | |
| @Override | |
| public boolean canExecute(Long time) { | |
| if ((time - this.curTime) > this.window) { | |
| this.curTime = time; | |
| this.prevCounter = this.curCounter; | |
| this.curCounter = 0L; | |
| } | |
| var ec = (this.prevCounter * (this.window - (time - this.curTime) * 1.0) / this.window) + this.curCounter; | |
| if (ec >= this.capacity) { | |
| return false; | |
| } | |
| this.curCounter++; | |
| return true; | |
| } | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment