study_youth

슬라이딩윈도우로그란?

- 고정된 크기의 시간 구간(윈도우)을 일정 간격으로 이동시키며, 윈도우 안에 포함된 이벤트(데이터)를 기준으로 요청을 허용하거나 차단하는 알고리즘입니다.

즉 최근 N ms 동안 최대 M번만 허용같은 제약을 정밀하게 구현할 때 활용됩니다.

조건사항

• 모든 이벤트는 timestamp 형태로 기록
• ms까지 시간을 계산한다.
• 데이터는 데이터베이스에 저장된다고 가정하고, 동시 접근 시 락으로 경쟁상태를 방지

코드

동작과정

1. 일정한 윈도우 시간과 개수를 정해서 트래픽을 관리한다.
2. 시간이 흐르면 윈도우내에 해당 시간은 삭제한다.
3. limit시간을 초과해서 쌓지는 않는다.
4. 요청시 윈도우 내에 허용범위이면 deque에 담고, 없으면 거부하고 대기시간을 알려준다.

import time
import threading
from collections import defaultdict, deque

from rateLimiter import Result


class SlidingWindowLog:
    def __init__(self, limit: int, window_ms: int):
        self.limit = int(limit)
        self.window_ms = int(window_ms)
        self._queue_ms = defaultdict(deque)
        self._locks = defaultdict(threading.Lock)

    def allow(self, key: str) -> Result:
        dq = self._queue_ms[key]
        lock = self._locks[key]
        now_ms = int(time.time() * 1000)
        cutoff = now_ms - self.window_ms

        with lock:
            while dq and dq[0] < cutoff:
                dq.popleft()

            if len(dq) < self.limit:
                dq.append(now_ms)
                remaining = self.limit - len(dq)
                return Result(True, remaining, 0)
            else:
                oldest = dq[0]
                retry_ms = self.window_ms - (now_ms - oldest)
                return Result(False, 0, max(1, retry_ms))

• limit : 윈도우 내에 채울수 있는 개수
• window_ms : 윈도우 제한을 걸어줄 시간
• queue_ms : 각각 key 마다 dict로 구별하고 deque에 넣는다.
• locks : 여러 요청이 동시에 접근할 때 경쟁상태를 막기 위한 락

요약

• 시간은 timestamp로 기록해 데이터베이스에 저장할수 있도록 설계함

토큰버킷 알고리즘

토큰 버킷은 Rate Limiting 기법 중 하나로, 서버가 단위 시간 동안 처리할 수 있는 요청의 양을 제어하는 방식
과도한 요청이나 DDoS 공격으로 인한 부하를 막고, 안정적인 서비스를 제공하기 위해 주로 API Gateway나 프록시 서버에서 사용된다

조건사항

• 시간은 timestamp 형태로 기록
• 토큰은 초(second)를 기준으로 채워진다.
• 데이터는 데이터베이스에 저장된다고 가정하고, 동시 접근 시 락(lock) 으로 경쟁 상태를 방지

코드 사항

동작사항

1. 버킷에는 일정량의 토큰이 들어 있으며, 요청 1개를 처리하려면 토큰 1개가 필요
2. 시간이 흐르면 정해진 속도(rate)에 따라 버킷에 토큰이 채워진다.
3. 버킷의 크기(burst)를 초과해서는 토큰이 쌓이지 않는다.
4. 요청 시 토큰이 있으면 허용하고 하나를 소비하며, 토큰이 없으면 거부하고 대기 시간을 알려준다.

공통

from dataclasses import dataclass
from typing import Protocol

@dataclass(frozen=True)
class Result:
    allowed: bool
    remaining: int  
    retry_after_ms: int

class RateLimiter(Protocol):
    def allow(self, key: str) -> Result:
        pass

TokenBucket

import threading
import time
from collections import defaultdict
from rateLimiter import RateLimiter, Result


class TokenBucket(RateLimiter):
    def __init__(self, rate_per_sec: float, burst: float | None = None):
        self.rate = float(rate_per_sec)
        self.burst = float(burst if burst is not None else rate_per_sec)
        self._states = defaultdict(self._new_state)
        self._locks = defaultdict(threading.Lock)

    @staticmethod
    def _new_state():
        return {"tokens": 0.0, "last": time.time()}

    def allow(self, key: str) -> Result:
        st = self._states[key]
        lock = self._locks[key]
        with lock:
            now = time.time()
            elapsed = now - st["last"]
            if elapsed < 0:
                elapsed = 0

            if elapsed > 0:
                st["tokens"] = min(self.burst, st["tokens"] + elapsed * self.rate)
                st["last"] = now

            if st["tokens"] >= 1.0:
                st["tokens"] -= 1.0
                return Result(True, int(st["tokens"]), 0)
            else:
                need = 1.0 - st["tokens"]
                retry_ms = int((need / self.rate) * 1000 + 0.999)
                return Result(False, 0, max(1, retry_ms))

• rate : 초당 채워지는 토큰 개수
• burst : 버킷에 담을 수 있는 토큰의 최대값
• state : 현재 토큰 개수와 마지막 갱신 시각(timestamp)
• locks : 여러 요청이 동시에 접근할 때 경쟁 상태를 막기 위한 락

요약

• 시간은 timestamp로 기록해 데이터베이스에 저장할 수 있도록 설계함
• 시스템 시간이 조정될 수 있으므로, elapsed가 음수가 되는 경우는 0으로 처리
• 현재 시각과 마지막 갱신 시각을 비교해 토큰을 보충하고, 요청 허용 여부를 판단

Django의 특징

Django는 빠른 개발과 깔끔한 설계를 지원하는 강력한 웹 프레임워크이다.

웹 개발에서 반복되는 복잡한 과정을 해결하고, 개발자가 핵심 기능 구현에만 집중할 수 있도록 돕는 오픈소스 프로젝트이다.

Django의 가장 큰 특징은 재사용 가능한 앱을 지향한다는 점이다.

이는 전체 프로젝트를 하나의 거대한 덩어리로 만들지 않고, 특정 기능을 가진 작은 애플리케이션들로 나누는 것을 의미한다.

예를 들어, 블로그 기능, 회원가입 기능, 결제 기능을 각각 별개의 앱으로 만들어 관리하는 식이다.

이렇게 하면 하나의 앱을 개발한 뒤, 다른 프로젝트에서 필요할 때 그대로 가져다 쓸 수 있어 개발 효율이 극대화된다.

Django가 추천하는 구조의 장점

Django의 이러한 철학은 자연스럽게 다음과 같은 구조적 장점으로 이어진다.

• 높은 응집도: 각 앱이 자신의 기능과 관련된 모든 코드(모델, 뷰, URL 등)를 한곳에 모아두기 때문에 관리가 쉬움.
• 낮은 결합도: 각 앱은 다른 앱에 대한 의존성을 최소화하여 독립적으로 작동합니다. 특정 기능을 수정하거나 삭제해도 다른 부분에 영향을 주지 않음.
• 뛰어난 재사용성: 기능별로 모듈화된 앱은 다른 프로젝트에서도 쉽게 재사용 용이.

표준 Django 프로젝트 구조 살펴보기

아래는 Django가 권장하는 모범적인 프로젝트 구조이고 이 구조를 이해하면 Django의 철학을 더 잘 파악할 수 있다.

djangotutorial/
    manage.py
    mysite/
        __init__.py
        settings.py
        urls.py
        asgi.py
        wsgi.py
    polls/
        __init__.py
        admin.py
        apps.py
        migrations/
            __init__.py
            0001_initial.py
        models.py
        static/
            polls/
                images/
                    background.png
                style.css
        templates/
            polls/
                detail.html
                index.html
                results.html
        tests.py
        urls.py
        views.py
    templates/
        admin/
            base_site.html