클라이언트 상태 노드 구조

각 클라이언트의 상태를 추적하는 핵심 자료구조에 대해 알아보자.

구조체 정의

src/http/modules/ngx_http_limit_req_module.c


typedef struct {
    u_char                       color;
    u_char                       dummy;
    u_short                      len;
    ngx_queue_t                  queue;
    ngx_msec_t                   last;
    /* integer value, 1 corresponds to 0.001 r/s */
    ngx_uint_t                   excess;
    ngx_uint_t                   count;
    u_char                       data[1];
} ngx_http_limit_req_node_t;

각 필드의 역할 상세 분석

1. color와 dummy: Red-Black Tree 관리


u_char color;  // Red-Black Tree의 색상 정보 (0=Black, 1=Red)
u_char dummy;  // 메모리 정렬을 위한 패딩

Red-Black Tree는 균형 이진 탐색 트리로, 각 노드는 Red 또는 Black 색상을 가진다. 이 색상 정보를 사용해 트리의 균형을 유지하며, 최악의 경우에도 O(log n) 성능을 보장한다.

2. len과 data: 클라이언트 식별


u_short len;      // 키의 길이
u_char data[1];   // 실제 클라이언트 식별자 데이터

가변 길이 배열 기법을 사용한다. data[1]로 선언되어 있지만, 실제로는 구조체 고정 영역에 더해 키 길이(len)만큼의 가변 영역을 한 덩어리로 할당하고, 키 바이트를 data 바로 뒤에 연속 배치한다. 이를 통해 IPv4, IPv6, 세션 ID 등 다양한 길이의 식별자를 효율적으로 저장한다.

3. queue: LRU Queue 연결


ngx_queue_t queue;  // 이전 노드와 다음 노드를 가리키는 포인터 (prev, next)

이 필드를 통해 노드가 LRU Queue에 연결된다. Queue는 이중 연결 리스트(doubly linked list) 형태로, 각 노드는 이전과 다음 노드를 가리키며, 메모리 부족 시 가장 오랫동안 사용하지 않은 Queue의 맨 뒤 노드부터 제거된다.

4. last와 excess: Leaky Bucket 계산


ngx_msec_t last;    // 마지막 요청 시간 (밀리초 단위의 timestamp)
ngx_uint_t excess;  // 누적된 초과 요청량

last: 시간 경과 계산에 사용된다.


ms = (ngx_msec_int_t) (now - lr->last);  // 얼마나 시간이 흘렀는지

excess: Leaky Bucket의 “양동이에 담긴 물의 양”을 나타낸다.


excess = lr->excess - ctx->rate * ms / 1000 + 1000;
         └─이전 값──┘   └───시간에 따른 누출────┘    └─현재 요청

5. count: 참조 카운트


ngx_uint_t count;  // 현재 이 노드를 참조하는 횟수

여러 limit zone을 체크하는 동안 노드가 삭제되지 않도록 보호한다. ngx_http_limit_req_lookup 함수에서 증가시키고, ngx_http_limit_req_account 함수에서 감소시킨다. count > 0인 노드는 메모리 부족 시에도 제거되지 않는다.