Red-Black Tree와 LRU Queue

Nginx의 ngx_http_limit_req_module 모듈은 클라이언트 요청 빈도를 제한하기 위해 Red-Black Tree와 LRU Queue 두 가지 자료구조를 함께 사용한다. 이 두 자료구조는 서로 다른 목적을 가지고 있으며, 하나의 공유 메모리 영역에서 공존한다.

공유 컨텍스트 구조체

src/http/modules/ngx_http_limit_req_module.c


typedef struct {
    ngx_rbtree_t                  rbtree;
    ngx_rbtree_node_t             sentinel;
    ngx_queue_t                   queue;
} ngx_http_limit_req_shctx_t;

하나의 구조체에 두 자료구조가 모두 포함되어 있다. rbtree는 클라이언트를 빠르게 찾기 위한 인덱스이고, queue는 메모리가 부족할 때 어떤 노드를 제거할지 결정한다.

역할 분담

Red-Black Tree: 빠른 검색

클라이언트를 O(log n) 시간에 찾기 위한 인덱스 역할을 한다. 해시값과 실제 키로 정확한 노드를 빠르게 찾는다.

src/http/modules/ngx_http_limit_req_module.c


static ngx_int_t ngx_http_limit_req_lookup(ngx_http_limit_req_limit_t *limit, ngx_uint_t hash, ngx_str_t *key, ngx_uint_t *ep, ngx_uint_t account) {
    // ...
 
    // Tree 검색 로직
    node = ctx->sh->rbtree.root;
    sentinel = ctx->sh->rbtree.sentinel;
 
    while (node != sentinel) {
        if (hash < node->key) {
            node = node->left;  // 왼쪽 서브트리로
            continue;
        }
 
        if (hash > node->key) {
            node = node->right;  // 오른쪽 서브트리로
            continue;
        }
 
        /* hash == node->key */
 
        // 해시가 같으면 실제 키 비교
        lr = (ngx_http_limit_req_node_t *) &node->color;
        rc = ngx_memn2cmp(key->data, lr->data, key->len, (size_t) lr->len);
 
        if (rc == 0) { // 정확히 일치
            // ...
        }
 
        node = (rc < 0) ? node->left : node->right; // 다른 후보 계속 탐색
    }
 
    // ...
}

LRU Queue: 메모리 관리

노드의 사용 시간 순서를 추적하여 메모리 부족 시 제거할 노드를 결정한다. 노드를 사용할 때마다 Queue 맨 앞으로 이동시켜 “최근 사용”을 표시하고, 메모리가 부족하면 맨 뒤(가장 오래 사용하지 않은 노드)부터 제거한다.

src/http/modules/ngx_http_limit_req_module.c


static ngx_int_t ngx_http_limit_req_lookup(ngx_http_limit_req_limit_t *limit, ngx_uint_t hash, ngx_str_t *key, ngx_uint_t *ep, ngx_uint_t account) {
    // ...
 
    if (rc == 0) { // 정확히 일치
        // Queue에서 노드를 맨 앞으로 이동 (최근 사용 표시)
        ngx_queue_remove(&lr->queue);
        ngx_queue_insert_head(&ctx->sh->queue, &lr->queue);
 
        // ...
    }
}

src/http/modules/ngx_http_limit_req_module.c


static void ngx_http_limit_req_expire(ngx_http_limit_req_ctx_t *ctx, ngx_uint_t n) {
    // ...
 
    while (n < 3) {
        // ...
 
        // LRU Queue 맨 뒤 노드 가져오기 (가장 오래 사용 안 함)
        q = ngx_queue_last(&ctx->sh->queue);
        lr = ngx_queue_data(q, ngx_http_limit_req_node_t, queue);
 
        // ...
 
        ngx_queue_remove(q); // LRU Queue에서 제거
 
        // ...
    }
}

Red-Black Tree와 LRU Queue

공유 컨텍스트 구조체

역할 분담

Red-Black Tree: 빠른 검색

LRU Queue: 메모리 관리

참고 자료