The sliding window mechanism monitors the timestamps of all requests occurring within a defined time interval, ensuring that the request rate remains within a specified limit.
Complete drill down of this algorithm is covered at this post, I would recommend to read this. This post, I am going to walk through how can we implement Sliding Window Log Algorithm using Java SortedSet.
SortedSet
The SortedSet interface in Java extends the Set interface, providing a total ordering on its elements. Elements are ordered either by their natural ordering or by a Comparator provided at set creation. The set’s iterator traverses elements in ascending order. Additional operations leverage this ordering.
To be used in a SortedSet, all elements must implement Comparable or be compatible with the provided comparator, ensuring mutual comparability. Violations will result in a ClassCastException. The ordering of a SortedSet must be consistent with equals to correctly implement the Set interface, though the set's behavior is well-defined even if this is not the case.
Standard SortedSet implementations typically offer four constructors:
1. A no-argument constructor for an empty set with natural ordering.
2. A constructor accepting a Comparator for an empty set with custom ordering.
3. A constructor accepting a Collection, creating a set with natural ordering of the collection's elements.
4. A constructor accepting another SortedSet, creating a set with the same elements and ordering.
Methods returning subsets produce half-open ranges (including the low endpoint but excluding the high endpoint).
headSet and tailSet methods
The headSet(E toElement) method in the SortedSet interface returns a view of the portion of the set whose elements are strictly less than toElement. This subset is backed by the original set, meaning that changes in the subset are reflected in the original set and vice-versa. The subset supports all the optional set operations of the original set. Attempting to insert an element outside the range of the subset will result in an IllegalArgumentException.
Given a SortedSet with elements [1, 2, 4, 13, 14, 65, 91], sortedSet.headSet(4) returns a view of the portion of the set whose elements are strictly less than 4. Therefore, sortedSet.headSet(4) will be [1, 2].
The tailSet(E fromElement) method in the SortedSet interface returns a view of the portion of the set whose elements are greater than or equal to fromElement. This subset is backed by the original set, so changes in the subset are reflected in the original set and vice-versa. The subset supports all optional set operations of the original set. Attempting to insert an element outside the range of the subset will result in an IllegalArgumentException.
Given a SortedSet with elements [1, 2, 4, 13, 14, 65, 91], sortedSet.tailSet(4) returns a view of the portion of the set whose elements are greater than or equal to 4. Therefore, sortedSet.tailSet(4) will be [4, 13, 14, 65, 91].
SortedSetDemo.java
package com.sample.app.collections;
import java.util.SortedSet;
import java.util.TreeSet;
public class SortedSetDemo {
public static void main(String[] args) throws InterruptedException {
SortedSet<Integer> sortedSet = new TreeSet<>();
sortedSet.add(1);
sortedSet.add(13);
sortedSet.add(2);
sortedSet.add(14);
sortedSet.add(4);
sortedSet.add(65);
sortedSet.add(91);
sortedSet.add(4);
System.out.println("sortedSet : " + sortedSet);
SortedSet<Integer> headSet = sortedSet.headSet(4);
System.out.println("headSet : " + headSet);
SortedSet<Integer> tailSet = sortedSet.tailSet(4);
System.out.println("tailSet : " + tailSet);
headSet.clear();
System.out.println("Clearnig all the headSet elements");
System.out.println("sortedSet : " + sortedSet);
}
}
Output
sortedSet : [1, 2, 4, 13, 14, 65, 91] headSet : [1, 2] tailSet : [4, 13, 14, 65, 91] Clearnig all the headSet elements sortedSet : [4, 13, 14, 65, 91]
How can we implement Sliding Window Log Ratelimter using SortedSet?
SortedSet ensures that elements are stored in sorted order, which is crucial for managing the sliding window efficiently. When timestamps are added to the set, they are automatically sorted, making it easy to identify the oldest and newest timestamps.
How to idenitfy oldest timestamps and remove them from the SortedSet?
The headSet method of SortedSet returns a view of all elements strictly less than a specified element. In the Sliding Window Log, this feature is used to obtain a subset of timestamps that fall within the time window. By specifying the end timestamp of the window, headSet efficiently retrieves all timestamps older than the end of the window. These old timestamps can then be removed from the set using the clear method, effectively maintaining only the timestamps within the window.
Example
public boolean addEvent(long currentTimestamp) {
int eventCount = getEventCount(currentTimestamp);
if (eventCount < windowSize) {
timestampsSortedSet.add(currentTimestamp);
return true;
}
return false;
}
// Method to get the number of events within the time window
private int getEventCount(long currentTimestamp) {
removeOldEvents(currentTimestamp);
return timestampsSortedSet.size();
}
private void removeOldEvents(long currentTimestamp) {
long startWindow = currentTimestamp - windowDurationInMillis;
timestampsSortedSet.headSet(startWindow).clear();
}
Find the below working application.
SlidingWindowLog.java
package com.sample.app.ratelimiter;
import java.util.SortedSet;
import java.util.TreeSet;
public class SlidingWindowLog {
private final SortedSet<Long> timestampsSortedSet;
private final long windowDurationInMillis;
private final long windowSize;
public SlidingWindowLog(long windowDurationInMillis, long windowSize) {
this.timestampsSortedSet = new TreeSet<>();
this.windowDurationInMillis = windowDurationInMillis;
this.windowSize = windowSize;
}
public boolean addEvent(long currentTimestamp) {
int eventCount = getEventCount(currentTimestamp);
if (eventCount < windowSize) {
timestampsSortedSet.add(currentTimestamp);
return true;
}
return false;
}
// Method to get the number of events within the time window
private int getEventCount(long currentTimestamp) {
removeOldEvents(currentTimestamp);
return timestampsSortedSet.size();
}
private void removeOldEvents(long currentTimestamp) {
long startWindow = currentTimestamp - windowDurationInMillis;
timestampsSortedSet.headSet(startWindow).clear();
}
}
SlidingWindowLogDemo.java
package com.sample.app.ratelimiter;
public class SlidingWindowLogDemo {
public static void main(String[] args) throws InterruptedException {
long windowDuration = 5000; // 5 seconds window
long windoSize = 4;
SlidingWindowLog log = new SlidingWindowLog(windowDuration, windoSize);
for (int i = 0; i < 15; i++) {
// Simulate adding events
boolean eventAdded = log.addEvent(System.currentTimeMillis());
System.out.println("eventAdded : " + eventAdded);
Thread.sleep(800);
}
}
}
Output
eventAdded : true eventAdded : true eventAdded : true eventAdded : true eventAdded : false eventAdded : false eventAdded : false eventAdded : true eventAdded : true eventAdded : true eventAdded : true eventAdded : false eventAdded : false eventAdded : false eventAdded : true
Drawbacks of this application
1. Can’t handle concurrent modifications
Since SortedSet implementations like TreeSet are not thread-safe, additional synchronization mechanisms is needed to ensure thread safety in concurrent environments.
2. No Persistence
The implementation is purely in-memory and does not provide persistence. If the application requires persisting the sliding window log between application restarts or across different instances, additional mechanisms for serialization and storage would be necessary.
3. Do not support Distributed application
In a distributed environment, each instance of the application would maintain its own local copy of the SortedSet, and updates made to one instance would not be reflected in the SortedSet instances on other servers. This limitation prevents the sliding window log from being used effectively in distributed applications where consistency and coordination between instances are crucial.
To address this problem, we can use Redis Sorted Sets. Redis is a powerful in-memory data store that provides efficient data structures and operations for building distributed systems. You can refer this article for more details https://engineering.classdojo.com/blog/2015/02/06/rolling-rate-limiter/
No comments:
Post a Comment