토큰 버킷
public class TokenBucket {
private long capacity; //수용가능한
private long tokens;
private long lastRefillTimestamp;
private long refillCountPerSecond;
public TokenBucket(long tokens, long refillCountPerSecond) {
this.capacity = tokens;
this.tokens = tokens;
this.refillCountPerSecond = refillCountPerSecond;
this.lastRefillTimestamp = System.currentTimeMillis();
}
public synchronized boolean tryConsume() { // 토큰값은 멀티스레드환경에서도 원자성을 유지해야함,
refill();
if (tokens > 0) {
tokens--;
return true;
}
return false;
}
private void refill() {
long now = System.currentTimeMillis();
//refillCountPerSecond 마다 토큰이 채워진다.
//마지막으로 채워졌을 때와 비교하여 경과된 시간만큼 추가되어야할 토큰 양을 정함
long tokensToAdd = (now - lastRefillTimestamp) / 1000 * refillCountPerSecond;
if (tokensToAdd > 0) {
// 버킷의 전체 수용가능한 토큰 수와 추가된 토큰을 더한 기존 토큰 중 더 작은 값으로 채택
tokens = Math.min(capacity, tokens + tokensToAdd);
lastRefillTimestamp = now; // 시간 업데이트
}
}
public static void main(String[] args) throws InterruptedException {
TokenBucket bucket = new TokenBucket(5, 1); // 1초마다 5개 토큰이 생성된다.
for (int i = 0; i < 10; i++) {
if (bucket.tryConsume()) {
System.out.println("허용된 요청 수 " + (i + 1));
} else {
System.out.println("실패 요청 수 " + (i + 1));
}
Thread.sleep(200); //200ms 마다 보낸다고 가정
}
}
}
누출 버킷
고정윈도카운터 알고리즘
원리
import java.util.HashMap;
import java.util.Map;
public class FixedWindowCounter {
private final Map<Long, Integer> requestCounts = new HashMap<>();
private final int maxRequests;
private final long windowSizeInMillis;
public FixedWindowCounter(int maxRequests, long windowSizeInMillis) {
this.maxRequests = maxRequests;
this.windowSizeInMillis = windowSizeInMillis;
}
public synchronized boolean allowRequest() {
long currentTimeMillis = System.currentTimeMillis();
// 나누는 수 windowSizeInMillis(윈도우사이즈1시간)은 항상 고정이며,
// 나누어지는 수 currentTimeMills는 유닉스 타임스탬프에 의해 항상 증가되기때문에
// 나눗셈 연산의 몫이 항상 다른 값을 보장 -> 키값이 될 수 있음.
long windowKey = currentTimeMillis / windowSizeInMillis;
requestCounts.putIfAbsent(windowKey, 0);
int requests = requestCounts.get(windowKey);
if (requests < maxRequests) {
//해시맵에 저장된 요청 수가 threshold보다 높다면 요청 거절
requestCounts.put(windowKey, requests + 1);
return true;
} else {
return false;
}
}
public static void main(String[] args) {
// 예제: 1시간(3600000 밀리초) 윈도우에 100개의 요청 제한
FixedWindowCounter counter = new FixedWindowCounter(100, 3600000);
// 요청 테스트
for (int i = 0; i < 120; i++) {
if (counter.allowRequest()) {
System.out.println("요청 #" + (i + 1) + ": 허용됨");
} else {
System.out.println("요청 #" + (i + 1) + ": 거부됨");
}
}
}
}
장점
단점
이동윈도로깅(sliding window logging) 알고리즘
import java.util.LinkedList;
import java.util.Queue;
public class SlidingWindowLog {
private final Queue<Long> logQueue;
private final long windowSizeInMillis;
public SlidingWindowLog(long windowSizeInMillis) {
this.logQueue = new LinkedList<>();
this.windowSizeInMillis = windowSizeInMillis;
}
public void recordEvent() {
long currentTime = System.currentTimeMillis();
logQueue.add(currentTime);
removeOldEvents(currentTime);
}
private void removeOldEvents(long currentTime) {
// 큐에 들어간 로그 중 가장 오래된 것이 윈도우사이즈보다 더 경과된 요청일 경우 만료
while (!logQueue.isEmpty() && (currentTime - logQueue.peek() > windowSizeInMillis)) {
logQueue.poll();
}
}
public int getEventCount() {
return logQueue.size();
}
public static void main(String[] args) throws InterruptedException {
// 예제: 1분 동안의 로그를 유지하는 슬라이딩 윈도우 로그
SlidingWindowLog log = new SlidingWindowLog(60000); // 60,000 밀리초 = 1분
// 로그 이벤트 테스트
log.recordEvent();
Thread.sleep(1000); // 1초 대기
log.recordEvent();
Thread.sleep(50000); // 50초 대기
log.recordEvent();
System.out.println("현재 이벤트 수: " + log.getEventCount());
}
}
이동윈도카운터 알고리즘