Hız
Limit Algoritmaları(Rate Limit Algorithms)
Çatlak
kova(Leaky Bucket) algoritması:
public abstract class RateLimiter {
protected final int maxRequestPerSec;
protected RateLimiter(int maxRequestPerSec) {
this.maxRequestPerSec = maxRequestPerSec;
}
abstract boolean allow();
}
public class LeakyBucket extends RateLimiter {
private long nextAllowedTime;
private final long REQUEST_INTERVAL_MILLIS;
protected LeakyBucket(int maxRequestPerSec) {
super(maxRequestPerSec);
/*Bir saniyeyi, max request sayisine bolerek,
saniyedeki bir request in zaman araligini buluyoruz*/
REQUEST_INTERVAL_MILLIS = 1000 / maxRequestPerSec;
/*Sonraki izin verilen zamanin ilk degerini
belirliyoruz*/
nextAllowedTime = System.currentTimeMillis();
}
@Override
boolean allow() {
long curTime = System.currentTimeMillis();
synchronized (this) {
/*Thread safe olarak, izin verilen sonraki zaman
dilimi degeri; su anki zaman diliminden kucuk veya esit ise, request e izin
veriyoruz.
* Eger yuk cok fazla ise,
sonraki izin verilen zaman dilimi degeri artıp tasacagindan, su andaki zaman
degerinden buyuk olacagindan, max request sayisindan fazlasina izin vermemis
olacagiz */
if (nextAllowedTime <= curTime) {
/*Requeste izin verdigimizde , izin verilen
sonraki zaman dilimi degerini; belirledigimiz saniyedeki bir requestin zaman
araligi kadar artiriyoruz.*/
nextAllowedTime = curTime + REQUEST_INTERVAL_MILLIS;
return true;
}
return false;
}
}
}
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.TimeUnit;
public class Main {
public static void main(String[] args) throws InterruptedException {
final int MAX_REQUESTS_PER_SEC = 10;
/*Kova nin bir saniyedeki max boyutunu tanimliyoruz;*/
RateLimiter rateLimiter = new LeakyBucket(MAX_REQUESTS_PER_SEC);
Thread requestThread = new Thread(() -> {
/*10 requesti 1 saniyede calistirmak istiyoruz;*/
sendRequest(rateLimiter, 10, 1);
});
requestThread.start();
requestThread.join();
}
private static void sendRequest(RateLimiter rateLimiter, int totalRequest, int requestPerSec) {
long startTime = System.currentTimeMillis();
/*totalCount kadar thread counter i baslatiyoruz;*/
CountDownLatch threadCounter = new CountDownLatch(totalRequest);
for (int i = 0; i < totalRequest; i++) {
try {
new Thread(() -> {
while (!rateLimiter.allow()) {
try {
TimeUnit.MILLISECONDS.sleep(10);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
threadCounter.countDown();
}).start();
TimeUnit.MILLISECONDS.sleep(1000 / requestPerSec);
} catch (Exception e) {
e.printStackTrace();
}
}
try {
threadCounter.await();
} catch (InterruptedException e) {
e.printStackTrace();
}
double duration = (System.currentTimeMillis() - startTime) / 1000.0;
System.out.println("-------------------------------------------------------------------------------------");
System.out.println(totalRequest + " adet request " + duration + " saniye icerisinde islendi. ");
System.out.println("Hız: Saniyede ; " + (double) totalRequest / duration + " adet request islendi.");
System.out.println("-------------------------------------------------------------------------------------");
}
}
10
adet requestin 1 saniyede işlenmesini istiyoruz;
Hız
limiti vermeden önce ki sonuç:
-------------------------------------------------------------------------------------
10
adet request 0.003 saniye icerisinde islendi.
Hız: Saniyede ; 3333.3333333333335 adet
request islendi.
Hız
limiti verdikten sonraki sonuç;
-------------------------------------------------------------------------------------
10
adet request 10.048 saniye icerisinde islendi.
Hız: Saniyede ; 0.9952229299363057 adet
request islendi.
Jeton
Kovası(Token Bucket) Algoritması:
Bu algoritmayı gerçek hayata uyarlayarak
ifade etmek istersek; bir jeton kovası içine jeton(token) attığımızı düşünelim.
Birim zamanda kova içindeki jeton sayısı kadar request e izin verilmektedir. Kovadaki
birim zamandaki jeton lar bittiğinde gelen request ler reject edilmektedir.
import java.util.concurrent.TimeUnit;
public class TokenBucket extends RateLimiter {
private int tokens;
public TokenBucket(int maxRequestsPerSec) {
super(maxRequestsPerSec);
this.tokens = maxRequestsPerSec;
new Thread(() -> {
while (true) {
try {
TimeUnit.SECONDS.sleep(1);
} catch (InterruptedException
e) {
e.printStackTrace();
}
refillTokens(maxRequestsPerSec);
}
}).start();
}
@Override
public boolean allow() {
synchronized (this) {
if (tokens == 0) {
return false;
}
tokens--;
return true;
}
}
private void refillTokens(int cnt) {
synchronized (this) {
tokens = Math.min(tokens + cnt, maxRequestPerSec);
notifyAll();
}
}
}
Request:
sendRequest(tokenBucketLimiter, 10, 1);
Output:
-------------------------------------------------------------------------------------
10
adet request 10.052 saniye icerisinde islendi.
Hız:
Saniyede ; 0.9948269001193792 adet request islendi.
-------------------------------------------------------------------------------------
Bu
örnek kodda iki thread var. Birisi token ları verilen saniyedeki request
sayısına göre sürekli dolduruyor(yeniliyor). Diğeri request thread lerini
başlatıyor. Burada aynı anda gelecek thread leri sınırlandırmak için; sürekli
olarak saniyedeki max request sayısı kadar token ilave ediliyor. İzin verilmiş
saniyedeki request sayısından fazlası gelirse reject ediliyor. Yani bir
saniyede aynı anda gelen requestlerin sayısı, parametre olarak verdiğimiz max
request sayısını geçmeyen istekler allow ediliyor(izin veriliyor).
Yukarıdaki kodda kovaya doldurulan
jetonları sabit doldurmak yerine, gelen request lere bağlı olarak, biraz
gecikmeli şekilde, tembel(lazy) olarak da doldurabiliriz;
public class TokenBucketLazyRefill extends RateLimiter {
private int tokens;
private long lastRefillTime;
public TokenBucketLazyRefill(int maxRequestPerSec) {
super(maxRequestPerSec);
this.tokens = maxRequestPerSec;
this.lastRefillTime = System.currentTimeMillis();
}
@Override
public boolean allow() {
synchronized (this) {
refillTokens();
if (tokens == 0) {
return false;
}
tokens--;
return true;
}
}
private void refillTokens() {
long curTime = System.currentTimeMillis();
double secSinceLastRefill = (curTime - lastRefillTime) / 1000.0;
int cnt = (int) (secSinceLastRefill * maxRequestPerSec);
if (cnt > 0) {
tokens = Math.min(tokens + cnt, maxRequestPerSec);
lastRefillTime = curTime;
}
}
}
Request:
sendRequest(tokenBucketLazyLimiter, 10, 1);
Output:
-------------------------------------------------------------------------------------
10 adet request 10.048 saniye icerisinde
islendi.
Hız: Saniyede ; 0.9952229299363057 adet
request islendi.
-------------------------------------------------------------------------------------
Bu örnek kod da da, TokenBucket algoritmasına
benzer şekilde saniyede izin verilen token sayısı kadar requestin çalışması
sağlanmaktadır. Ancak tokenların doldurulma, yenilenme süresi gelen requestlere
göre biraz geciktirilmektedir.Token doldurma süresi ve doldurulacak token
miktarı; son token doldurulma(yenilenme) süresi nin saniye cinsinden değerinin,
saniyede izin verilen max request sayısı ile çarpımının sıfırdan büyük olması
şartına göre değişkenlik göstermektedir. (Yeniden doldurulacak token sayısı =
(milisaniye olarak şu an - milisaniye olarak son tekrar token doldurma zamanı)
* birim zamanda çalışmasına izin verilen max token sayısı) Bu işlem de token
ların dolma süresini biraz geciktirmektedir.
Sabit
Pencere Sayacı(Fixed Window Counter) Algoritması:
Bu algoritmada anlık requestler, izin verilen
istek sayısı kadar pencereye “ConcurrentHashMap” nesnesi yardımıyla bölünür.
Her penceredeki sayaç limit i dolduğunda,
gelen istekler reddedilmektedir.
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.atomic.AtomicInteger;
public class FixedWindowCounter extends RateLimiter {
// TODO: Burada onceki gunden kalan eski pencerelerin silinmesi
islemi yapilabilir
private final ConcurrentMap<Long, AtomicInteger> windows = new ConcurrentHashMap<>();
protected FixedWindowCounter(int maxRequestPerSec) {
super(maxRequestPerSec);
}
@Override
boolean allow() {
long windowKey = System.currentTimeMillis()
/ 1000 * 1000;
windows.putIfAbsent(windowKey, new AtomicInteger(0));
return windows.get(windowKey).incrementAndGet() <= maxRequestPerSec;
}
}
Request:
sendRequest(fixedWindowCounterLimiter, 10, 1);
Output:
-----------------------------FixedWindowCounter---------------------------------
10
adet request 10.054 saniye icerisinde islendi.
Hız:
Saniyede ; 0.9946290033817385 adet request islendi.
-------------------------------------------------------------------------------------
Yukarıdaki kodda, t anındaki zaman
sayacı(windows nesnesi) sabit pencerelere bölünmektedir. Yani, her allow isteği
geldiğinde bir concurrent hash map e, request timestamp(zaman damgası) flag i
key olarak, sabit şekilde atılıp, bu key değerine ait olan counter, o an için
AtomicInteger nesnesi ile incremental olarak artırılıyor. N inci kez aynı zaman
diliminde gelen thread e ait request in değeri, parametre olarak verilmiş olan
max request size ından fazla olduğu zaman, allow değeri reject edilerek false
dönüyor. Yani aynı anda fix olarak sınırları kesin belirlenmiş bir pencere gibi
max request sınırı ConcurrentHashMap nesnesi içinde kısıtlanmış olmaktadır.
Sürgülü
Pencere Günlüğü(Sliding Window Log) Algoritması:
Bu algoritmada her allow isteği geldiğinde, t
anı ve bir önceki saniye aralığının log u tutulur.
import java.util.Queue;
public class SlidingWindowLog extends RateLimiter {
private final Queue<Long> log = new LinkedList<>();
protected SlidingWindowLog(int maxRequestPerSec) {
super(maxRequestPerSec);
}
@Override
boolean allow() {
long curTime = System.currentTimeMillis();
long boundary = curTime - 1000;
synchronized (log) {
while (!log.isEmpty() && log.element() <= boundary) {
log.poll();
}
log.add(curTime);
return log.size() <= maxRequestPerSec;
}
}
}
Request:
endRequest(slidingWindowLogLimiter, 10, 1);
Output:
-----------------------------SlidingWindowLog---------------------------------
10
adet request 10.055 saniye icerisinde islendi.
Hız:
Saniyede ; 0.9945300845350572 adet request islendi.
-------------------------------------------------------------------------------------
Yukarıdaki kodda; log isimli LinkedList
nesnesinin içinde daima şu an ve bir saniye öncesi zaman diliminin logu
tutulmaktadır. Fixed window dan farkı, bir önceki saniye yi de kapsayacak
şekilde, t anındaki zaman sayacının pencerelere bölünmesidir. T anı ve bir
saniye öncesindeki tutulan log, linked list içerisinde tutulur, bir saniye
öncesindeki loglar ise log listesinden çıkarılır. T anı ve bir saniye
öncesindeki gelen toplam request sayısı, max request sayısından fazla ise gelen
requestler reject edilir.
Sürgülü
Pencere(Sliding Window) Algoritması:
Bu algoritma da Sabit Pencere Sayacı(Fixed
Window Counter) na benzer. Bir pencerenin kendinden önceki requestlerinin %75
ile aktif pencerenin isteklerinin toplamı max request sayısını aşmadıysa allow
edilir.
Yani üstteki örneğe göre İstek sayısı = 9*(1
- %25) + 5 = 11.75 tir. Bu sayı max istek sayısını aştığı için(11.75 > 10 olduğu için) 5 request gelen ikinci pencere nin %25 lik zaman
diliminde gelen request ler reject edilmektedir. Her bölümlenmiş pencere
arasında böyle bir tolerans bırakmak daha pratik bulunmuştur.
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.atomic.AtomicInteger;
public class SlidingWindow extends RateLimiter {
// TODO: Burada onceki
zamandan kalan eski pencerelerin silinmesi islemi yapilabilir
private final ConcurrentMap<Long, AtomicInteger> windows = new ConcurrentHashMap<>();
protected SlidingWindow(int maxRequestPerSec) {
super(maxRequestPerSec);
}
@Override
boolean allow() {
long curTime = System.currentTimeMillis();
long curWindowKey = curTime / 1000 * 1000;
windows.putIfAbsent(curWindowKey, new AtomicInteger(0));
long preWindowKey = curWindowKey - 1000;
AtomicInteger preCount = windows.get(preWindowKey);
if (preCount == null) {
return windows.get(curWindowKey).incrementAndGet() <= maxRequestPerSec;
}
double preWeight = 1 - (curTime - curWindowKey) / 1000.0;
long count = (long) (preCount.get() * preWeight
+ windows.get(curWindowKey).incrementAndGet());
return count <= maxRequestPerSec;
}
}
Request:
sendRequest(slidingWindowLimiter, 10, 1);
Output:
-----------------------------SlidingWindow---------------------------------
10 adet request 10.056 saniye
icerisinde islendi.
Hız: Saniyede ; 0.9944311853619731
adet request islendi.
-------------------------------------------------------------------------------------
Yukarıdaki kodda, sabit pencere sayacında olduğu gibi, ConcurrentHashMap
içinde gene her pencere içindeki request tutulmakta. Ancak kendinden önceki
penceredeki requestlerin %75 i ile kendi penceresindeki requestin toplamı max
izin verilen request ten küçük eşit ise allow methodunda requestin çalışmasına
izin verilmektedir. Bu da her pencerede izin verilen request sayısının değerini
azaltmış bulunmaktadır.
Guava
Limiter API:
Google
ın Rate Limit API olarak sunmuş olduğu Guava library ile de hız limit
sınırlarını kontrol altında tutmak mümkündür.
Aşağıdaki
örnekte, Guava API de, bir saniyede bir requeste izin verecek şekilde limit
veriliyor. 10 request multi thread olarak, saniyede dörderli request çalışacak
şekilde istekte bulunuluyor. Sonuçta 10 request ten 2 si başarılı olarak kabul
edilip, kalanlar reject ediliyor.
Eklenen
Dependency:
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>29.0-jre</version>
</dependency>
Source
Code:
import java.time.Duration;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.TimeUnit;
public class GuavaTest {
private static int successCount;
public static void main(String[] args) throws InterruptedException {
final int MAX_REQUESTS_PER_SEC = 100;
/** Google un Guava Rate Limit API sinin
örneğidir;
* Örnek olarak, Bir saniyede 1
request çalışsın diye tanımlıyoruz
* */
com.google.common.util.concurrent.RateLimiter
guavaLimiter =
com.google.common.util.concurrent.RateLimiter
.create(1d, Duration.ofSeconds(1));
Thread requestThread = new Thread(() -> {
/*10 requesti 1 saniyede calistiralım;*/
sendRequestGuava(guavaLimiter, 10, 1);
});
requestThread.start();
requestThread.join();
}
private static void sendRequestGuava(com.google.common.util.concurrent.RateLimiter
rateLimiter, int totalRequest, int requestPerSec) {
long startTime = System.currentTimeMillis();
/*totalCount kadar thread counter i
baslatiyoruz;*/
CountDownLatch threadCounter = new CountDownLatch(totalRequest);
for (int i = 0; i < totalRequest; i++) {
try {
new Thread(() -> {
boolean allow = rateLimiter.tryAcquire();
System.out.println("guavaLimiter.tryAcquire() is " + allow);
if (allow) {
try {
successCount++;
System.out.println(" -> request calisti");
} catch (Exception e) {
e.printStackTrace();
}
}
threadCounter.countDown();
}).start();
/**
* Thread leri bir saniyenin 4 te biri kadar bekletip, saneyide yaklaşık 3
request çalışmasını sağlıyoruz.
* */
TimeUnit.MILLISECONDS.sleep(250);
} catch (Exception e) {
e.printStackTrace();
}
}
try {
threadCounter.await();
} catch (InterruptedException
e) {
e.printStackTrace();
}
double duration = (System.currentTimeMillis()
- startTime) / 1000.0;
System.out.println("-------------------------------------------------------------------------------------");
System.out.println("Bir Saniyede ; " + (double) totalRequest / duration + " adet request istegi gonderildi.");
System.out.println(totalRequest + " adet request " + duration + " saniye icerisinde islendi. ");
System.out.println("Rate limit olarak; 1 sn de 1 requeste
izin verildigi icin; "+totalRequest +" adet request ten " + successCount + " tanesi basarili
oldu. Gerisi reject edildi.");
System.out.println("-------------------------------------------------------------------------------------");
}
}
Output:
guavaLimiter.tryAcquire()
is true
-> request calisti
guavaLimiter.tryAcquire()
is false
guavaLimiter.tryAcquire()
is false
guavaLimiter.tryAcquire()
is false
guavaLimiter.tryAcquire()
is false
guavaLimiter.tryAcquire()
is false
guavaLimiter.tryAcquire()
is true
-> request calisti
guavaLimiter.tryAcquire()
is false
guavaLimiter.tryAcquire()
is false
guavaLimiter.tryAcquire()
is false
----------------------------------------------------------------------------------------
Bir
Saniyede ; 3.9277297721916735 adet request istegi gonderildi.
10
adet request 2.546 saniye icerisinde islendi.
Rate
limit olarak; 1 sn de 1 requeste izin verildigi icin; 10 adet request ten 2
tanesi basarili oldu. Gerisi reject edildi.
-------------------------------------------------------------------------------------------
Sonuç :
Hız sınırlama algoritmaları; saniye başına
transaction lisanslama kısıtı için, web servislerde aşırı yüklenme yi kontrol
altına alabilmek için, her hangi bir uygulamanın kaynaklarını kullanıcılara
adil olarak dağıtabilmek için, yada bir uygulamayı DDOS(Distributed Denial Of
Services) saldırılarına karşı korumak için kullanılabilir. Örneğin REST web
servislerinde ki requestleri kontrol altına almak için yukarıdaki basit kod
örnekleri verilen algoritma ve API ler; yazılacak bir request filter classı
içerisinde yada, bir RestController layer da kullanılabilir. Bu sayede hizmet
veren web servislerin bottleneck e düşmesi, hang olması, kilitlenmesi, hizmet
veremez hale gelmesi önlenmiş olur. Tabi yukarıda bahsettiğim hız limiti
algoritma ve API si dışında da; Resilience4j API, Bucket4j API, open source API
Gateway librarylerinden biri olan Kong Gateway, bunların dışında harici
kullanılacak API Gateway ler, …vs. gibi hız limiti için çözüm yolları tercih
edilebilir.
Kaynaklar:
·
https://medium.com/@aayushbhatnagar_10462/rate-limiting-implementation-example-in-java-7831923e5de3
·
https://konghq.com/blog/how-to-design-a-scalable-rate-limiting-algorithm/
·
https://hechao.li/2018/06/25/Rate-Limiter-Part1/
·
https://hechao.li/2018/06/27/Rate-Limiter-Part2/
·
https://www.figma.com/blog/an-alternative-approach-to-rate-limiting/
·
https://www.baeldung.com/spring-bucket4j
·
https://www.baeldung.com/guava-rate-limiter
·
https://github.com/google/guava
·
https://medium.com/teamarimac/implementing-throttling-in-java-spring-boot-ec4723cfce9f
