[Algorithm] 리키버킷 알고리즘 구현 | Leaky Bucket

껄껄껄

코딩무새입니다.

 

---

Leaky Bucket?

Leaky Bucket 알고리즘은 네트워크 트래픽 관리, 속도 제한, Request 처리에 사용되는 알고리즘입니다.

그렇기 때문에 사용하게 된다면 트래픽의 안정성을 유지하고 과부하를 방지하는 데 유용합니다.

제가 올린 대표 이미지 처럼 양동이에서 물이새는 것처럼 조금씩 흘려보내는 느낌의 이미지로 생각해주시면 됩니다.

아래는 Leaky Bucket 알고리즘의 동작 방식과 구현 방법에 대한 설명입니다.

Leaky Bucket 알고리즘의 작동 원리

1. 버킷의 역할: 제한된 크기의 버킷이 있다고 가정합니다. 이 버킷은 요청 또는 패킷을 담습니다.
2. 버킷의 누수: 버킷은 일정한 속도로 누수됩니다. 이는 요청이 처리되거나 네트워크를 통해 전달되는 것을 의미합니다.
3. 요청 거부: 만약 누수의 양보다 요청량이 많아 버킷이 전부 차 있으면 새로운 요청(패킷)은 거부됩니다. 즉, 초과된 트래픽은 무시되는것이지요.

Leaky Bucket 장단점

장점

1. 트래픽 안정화: 한 번에 많은 요청이 몰려도 일정 속도로 처리되므로 안정적이게 되지요.
2. 단순함: 구현이 비교적 간단하며 효율적입니다..
3. 과부하 방지: 설정된 용량 초과 요청은 거부되므로 과부하를 방지합니다.

단점

1. 유연성 부족: 버킷의 누수는 고정적이기 때문에 갑작스러운 트래픽 증가에 유연하게 대응하기 어렵지요.
2. 정교한 처리 부족: 구현이 비교적 간단하기 때문에 디테일한 조건 설정에 대한 복잡도가 증가하게 됩니다.
3. 응답 지연: 고정된 처리 속도로, 응답 지연을 발생 시킬 수 있지요.

예제 코드

아래는 간단히 구현한 파이썬 코드입니다.

LeakyBucket 클래스를 호출하여 0.2초 sleep 을 주었습니다.

import time

class LeakyBucket:
    def __init__(self, capacity, leak_rate):
        self.capacity = capacity        # 버킷 용량
        self.leak_rate = leak_rate      # 초당 누수 속도
        self.current_water = 0          # 현재 버킷의 상태
        self.last_checked = time.time() # 마지막으로 확인한 시간

    def add_request(self):
        current_time = time.time()
        time_passed = current_time - self.last_checked

        # 버킷 누수 처리
        leaked_amount = time_passed * self.leak_rate
        self.current_water = max(0, self.current_water - leaked_amount)
        self.last_checked = current_time

        print(f"current_water: {bucket.current_water}")
        
        # 요청 처리
        if self.current_water < self.capacity:
            self.current_water += 1
            return True     # 요청 허용
        else:
            return False    # 요청 거부

# 버킷 용량: 10, 초당 누수 속도: 2
bucket = LeakyBucket(capacity=10, leak_rate=2)
for i in range(30):
    if bucket.add_request():
        print(f"Request {i} - Allowed")
    else:
        print(f"Request {i} - Denied")    
    time.sleep(0.2)

 

아래는 결과입니다.

current_water: 0
Request 0 - Allowed
current_water: 0.5974259376525879
Request 1 - Allowed
current_water: 1.1949706077575684
Request 2 - Allowed
current_water: 1.7934284210205078
Request 3 - Allowed
current_water: 2.3914785385131836
Request 4 - Allowed
current_water: 2.9893922805786133
Request 5 - Allowed
current_water: 3.587779998779297
Request 6 - Allowed
current_water: 4.185424327850342
Request 7 - Allowed
current_water: 4.784564018249512
Request 8 - Allowed
current_water: 5.383425235748291
Request 9 - Allowed
current_water: 5.982357978820801
Request 10 - Allowed
current_water: 6.580615520477295
Request 11 - Allowed
current_water: 7.178616046905518
Request 12 - Allowed
current_water: 7.77776575088501
Request 13 - Allowed
current_water: 8.374937057495117
Request 14 - Allowed
current_water: 8.972658157348633
Request 15 - Allowed
current_water: 9.570435523986816
Request 16 - Allowed
current_water: 10.168241024017334
Request 17 - Denied
current_water: 9.766720294952393
Request 18 - Allowed
current_water: 10.363881587982178
Request 19 - Denied
current_water: 9.962998390197754
Request 20 - Allowed
current_water: 10.56155776977539
Request 21 - Denied
current_water: 10.160623550415039
Request 22 - Denied
current_water: 9.759193420410156
Request 23 - Allowed
current_water: 10.357922077178955
Request 24 - Denied
current_water: 9.957176208496094
Request 25 - Allowed
current_water: 10.555946350097656
Request 26 - Denied
current_water: 10.155035972595215
Request 27 - Denied
current_water: 9.753283023834229
Request 28 - Allowed
current_water: 10.351673126220703
Request 29 - Denied

 

위의 결과를 보면 current_water가 10이하일 때 허용하고, 초과하면 거부하는 것을 볼 수 있지요.

---

 

Leaky Bucket 알고리즘에 대해서 알아봤습니다.

자주 사용하진 않을 수 있지만 알아두면 언젠간 써먹을 수 있는 알고리즘이죠.

껄껄껄