클라이언트 조회와 요청 판단

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) {
    /* 변수 선언 */
    size_t                      size;            // 새 노드 할당 시 필요한 메모리 크기
    ngx_int_t                   rc, excess;      // rc: 키 비교 결과, excess: 스케일된 요청 잉여 (요청 수 × 1000)
    ngx_msec_t                  now;             // 현재 시간 (밀리초)
    ngx_msec_int_t              ms;              // 경과 시간 (밀리초)
    ngx_rbtree_node_t          *node, *sentinel; // node: 현재 탐색 중인 노드, sentinel: Tree의 끝을 나타내는 노드
    ngx_http_limit_req_ctx_t   *ctx;             // 공유 메모리 zone 컨텍스트
    ngx_http_limit_req_node_t  *lr;              // limit_req 노드 (클라이언트 정보)
 
    /* 1. 함수 시작 및 변수 초기화 */
    now = ngx_current_msec; // 현재 시간을 밀리초로 가져오기
 
    ctx = limit->shm_zone->data; // zone의 공유 메모리 컨텍스트 가져오기
 
    node = ctx->sh->rbtree.root; // Red-Black Tree의 루트 노드부터 시작
    sentinel = ctx->sh->rbtree.sentinel; // Tree의 끝을 나타내는 sentinel 노드
 
    /* 2. Red-Black Tree 탐색: hash 값으로 클라이언트 노드 찾기 */
    while (node != sentinel) { // sentinel에 도달할 때까지 (Tree 끝까지) 반복
        if (hash < node->key) { // 찾는 hash가 현재 노드보다 작은 경우
            node = node->left; // 왼쪽 서브트리로 이동
            continue; // 다음 반복
        }
 
        if (hash > node->key) { // 찾는 hash가 현재 노드보다 큰 경우
            node = node->right; // 오른쪽 서브트리로 이동
            continue; // 다음 반복
        }
 
        /* hash == node->key */
        /* 3. 클라이언트 발견: hash 값이 일치하는 노드를 찾음 */
 
        lr = (ngx_http_limit_req_node_t *) &node->color; // 노드의 color 필드 이후에 limit_req 데이터가 위치
 
        rc = ngx_memn2cmp(key->data, lr->data, key->len, (size_t) lr->len); // 키 데이터를 정확하게 비교
 
        if (rc == 0) { // 키가 완전히 일치하는 경우 (클라이언트를 찾음)
            /* 4. LRU 큐 업데이트: 가장 최근에 사용된 노드를 큐 맨 앞으로 */
            ngx_queue_remove(&lr->queue); // LRU 큐에서 현재 노드 제거
            ngx_queue_insert_head(&ctx->sh->queue, &lr->queue); // 큐의 맨 앞에 다시 삽입
 
            /* 5. 시간 경과 계산 */
            ms = (ngx_msec_int_t) (now - lr->last); // 마지막 요청 이후 경과 시간 계산
 
            if (ms < -60000) { // 시간이 60초 이상 역행한 경우 (시스템 시간 변경)
                ms = 1; // 1ms로 처리
 
            } else if (ms < 0) { // 시간이 약간 역행한 경우
                ms = 0; // 0ms로 처리 (경과 시간 없음)
            }
 
            /* 6. excess 계산: Leaky Bucket 알고리즘 */
            excess = lr->excess - ctx->rate * ms / 1000 + 1000; // 이전 excess - 누출된 양 + 현재 요청 (1000배 스케일)
 
            if (excess < 0) { // excess가 음수인 경우
                excess = 0; // 0으로 보정 (버킷이 비어있음)
            }
 
            *ep = excess; // 계산된 excess를 출력 파라미터에 저장
 
            /* 7. excess > burst 체크: 제한 초과 여부 판단 */
            if ((ngx_uint_t) excess > limit->burst) { // excess가 burst 한계를 초과한 경우
                return NGX_BUSY; // 요청 거부
            }
 
            /* 8. account 체크: 노드 업데이트 또는 참조 카운트 증가 */
            if (account) { // account가 true인 경우 (마지막 zone이거나 업데이트가 필요한 경우)
                /* 9. 노드 업데이트 */
                lr->excess = excess; // 노드의 excess 값 업데이트
 
                if (ms) { // 시간이 경과한 경우
                    lr->last = now; // 마지막 요청 시간 업데이트
                }
 
                return NGX_OK; // 요청 허용
            }
 
            /* 10. 참조 카운트 증가 */
            lr->count++; // 참조 카운트 증가 (다음 zone에서도 이 노드를 참조)
 
            ctx->node = lr; // 컨텍스트에 노드 포인터 저장
 
            return NGX_AGAIN; // 다음 zone 체크 필요
        }
 
        node = (rc < 0) ? node->left : node->right; // 키가 일치하지 않으면 좌우 서브트리로 이동
    }
 
    /* 클라이언트를 찾지 못함: 새 노드 생성 */
    *ep = 0; // excess를 0으로 초기화 (새 클라이언트)
 
    /* 11. 메모리 할당 */
    size = offsetof(ngx_rbtree_node_t, color) + offsetof(ngx_http_limit_req_node_t, data) + key->len; // 필요한 메모리 크기 계산
 
    ngx_http_limit_req_expire(ctx, 1); // 오래된 노드 1개를 제거하여 메모리 확보
 
    node = ngx_slab_alloc_locked(ctx->shpool, size); // 공유 메모리에서 메모리 할당
 
    if (node == NULL) { // 메모리 할당 실패 시
        ngx_http_limit_req_expire(ctx, 0); // 모든 만료된 노드를 제거하여 메모리 확보
 
        node = ngx_slab_alloc_locked(ctx->shpool, size); // 다시 메모리 할당 시도
        if (node == NULL) { // 여전히 메모리 할당 실패 시
            ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "could not allocate node%s", ctx->shpool->log_ctx); // 에러 로그 출력
            return NGX_ERROR; // 에러 반환
        }
    }
 
    /* 12. Tree & Queue 삽입: 새 노드 초기화 및 삽입 */
    node->key = hash; // 노드의 키를 hash 값으로 설정
 
    lr = (ngx_http_limit_req_node_t *) &node->color; // limit_req 데이터 영역 포인터
 
    lr->len = (u_short) key->len; // 키 길이 저장
    lr->excess = 0; // excess를 0으로 초기화 (새 클라이언트는 초과 없음)
 
    ngx_memcpy(lr->data, key->data, key->len); // 키 데이터를 노드에 복사
 
    ngx_rbtree_insert(&ctx->sh->rbtree, node); // Red-Black Tree에 새 노드 삽입
 
    ngx_queue_insert_head(&ctx->sh->queue, &lr->queue); // LRU 큐의 맨 앞에 삽입 (가장 최근 사용)
 
    if (account) { // account가 true인 경우 (마지막 zone)
        lr->last = now; // 마지막 요청 시간을 현재 시간으로 설정
        lr->count = 0; // 참조 카운트를 0으로 초기화
        return NGX_OK; // 요청 허용
    }
 
    lr->last = 0; // last를 0으로 초기화 (아직 처리하지 않음)
    lr->count = 1; // 참조 카운트를 1로 설정
 
    ctx->node = lr; // 컨텍스트에 노드 포인터 저장
 
    return NGX_AGAIN; // 다음 zone 체크 필요
}