AI Agent에게 RB 트리를 맡기기 전에: 코드가 놓일 환경부터

AI Agent에게 “C로 RB 트리를 구현해 주세요”라고 요청한다고 가정해 보겠습니다. 검색·삽입·삭제가 정상적으로 동작하고 테스트도 통과한 코드가 나왔습니다. 그 코드가 여러 프로세스가 사용하는 공유메모리 안에서도 적절하게 동작할까요?

요청에 그 조건이 없었다면, 노드를 추가할 때마다 malloc()을 호출하는 구현도 자연스러운 답입니다. 알고리즘의 동작을 확인하는 것과, 그 알고리즘이 놓일 환경의 요구사항을 확인하는 것은 별개의 일입니다.

예전에 HP-UX에서 C 거래 시스템을 개발하며 배열, 레드블랙 트리, 가용 목록을 결합한 적이 있습니다. 이 경험을 다시 살펴보면, AI Agent와 코딩할 때 함께 전달하고 검토해야 할 세 가지가 보입니다. 환경의 제약, 반드시 유지해야 하는 조건, 그 조건을 확인하는 검증 기준입니다.

자료구조 이름만으로는 전달되지 않는 조건

당시에는 여러 프로세스가 같은 거래 상태를 조회하고 갱신해야 했습니다. 상태 정보는 공유메모리에 두었습니다. 일반적인 malloc()은 호출한 프로세스의 힙에서 공간을 확보하므로, 이미 연결한 공유 영역 안에서 빈자리를 찾아주는 용도로 그대로 쓸 수는 없었습니다.

공유메모리에서도 별도의 할당기를 두면 동적 할당이 가능합니다. 당시에는 영역을 미리 확보하고 일정한 크기의 슬롯으로 나눈 뒤, 빈 슬롯을 가용 목록(free list)으로 연결했습니다. 슬롯을 꺼내 데이터를 저장하고, 삭제한 슬롯은 목록으로 돌려보냈습니다.

도구에도 제약이 있었습니다. GCC를 사용할 수 없었고 HP-UX C 컴파일러로 빌드해야 했습니다. 재사용할 라이브러리나 코드도 그 환경에서 검증할 수 있어야 했습니다.

“RB 트리 구현”이라는 짧은 요청에는 이런 조건이 들어 있지 않습니다. Agent가 저장소와 빌드 설정에서 일부를 찾아낼 수는 있어도, 빠진 조건을 모두 알아냈다고 가정할 수는 없습니다. 작업에 들어가기 전에 확인된 제약과 아직 확인하지 못한 가정을 구분할 필요가 있습니다.

저장 공간과 검색 방식은 따로 결정하기

공간을 확보한 다음에는 키로 데이터를 찾는 방법이 필요했습니다. 당시 구현에서는 RB 트리가 그 역할을 맡았습니다.

구성	맡은 일	별도로 정해야 하는 것
공유 영역의 배열 슬롯	일정한 크기의 저장 공간 제공	전체 용량과 주소 표현
가용 목록	빈 슬롯 확보와 반환	고갈 시 동작과 동기화
RB 트리	키로 검색·삽입·삭제	노드의 저장 공간과 참조 수명

배열을 키 순서대로 정렬한 것은 아닙니다. 키 40이 슬롯 0에, 키 20이 슬롯 3에 있을 수 있습니다. 트리는 키 사이의 관계를, 슬롯 번호는 저장 위치를 나타냅니다.

RB 트리는 균형을 유지해 검색·삽입·삭제를 O(log n)에 처리합니다. 가용 목록의 맨 앞에서 슬롯을 꺼내거나 반환하는 작업은 O(1)입니다. 풀을 붙여도 트리의 검색 복잡도가 바뀌지는 않습니다. 문자열 키의 비교 비용, 동기화와 데이터 복사 비용도 남습니다.

당시 RB 트리를 택한 정확한 비교 과정은 기억이 분명하지 않습니다. 구현에서는 주로 키로 상태를 찾고 갱신하며, 공유 영역의 슬롯을 재사용한 것을 확인할 수 있습니다. 입력에 따라 검색 비용이 크게 치우치지 않도록 하려는 선택으로 해석할 수 있지만, 해시 테이블보다 빨랐다고 단정할 근거는 없습니다.

이 구분은 Agent와 대안을 검토할 때도 중요합니다. 제약은 유지하되 해결 방법은 비교할 수 있어야 합니다. 공유메모리 안에서 공간을 관리해야 한다고 해서 검색 구조까지 RB 트리로 고정되는 것은 아닙니다. 정확한 키 조회만 필요하면 해시 테이블과 풀, 키가 조밀한 정수라면 직접 인덱싱, 갱신이 드물다면 정렬 배열도 비교 대상입니다.

“구현해 주세요”에 더할 것은 유지 조건입니다

“free list를 만들어 주세요”보다 더 구체적인 기준은 다음과 같습니다.

• 트리에 연결된 슬롯은 가용 목록에 들어가지 않습니다.
• 실패한 삽입은 예약한 슬롯을 남기지 않습니다.
• 삭제에서는 실제로 트리에서 분리된 슬롯을 반환합니다.
• 다른 작업이 사용하는 슬롯은 재사용하지 않습니다.
• 공간이 가득 차면 합의한 방식으로 실패하거나 대기합니다.

트리에 연결된 슬롯과 빈 슬롯이 겹치지 않는 것처럼, 계속 유지해야 하는 조건을 불변조건이라고 합니다. 이러한 조건과 실패 시 정책을 구현 요청에 포함하고 테스트·리뷰에서도 같은 기준으로 확인할 수 있습니다.

예를 들어 다음은 이 글을 위해 새로 작성한 슬롯 풀 예제의 반환 함수입니다. used는 사용 여부, next_free는 다음 빈 슬롯의 인덱스입니다.

static bool pool_release(Pool *p, size_t i)
{
    if (i >= CAPACITY || !p->slots[i].used) return false;
    Slot *s = &p->slots[i];
    s->used = false;
    s->links.next_free = p->free_head;
    p->free_head = i;
    --p->used_count;
    return true;
}

인덱스 범위를 확인하고 이미 반환한 슬롯도 거절합니다. 그러나 이 함수는 트리에서 분리됐는지, 다른 작업이 아직 참조하는지 확인하지 않습니다. 호출자가 그 조건을 보장해야 합니다. 함수 내부의 검사만으로 반환이 안전하다고 판단할 수 없는 이유입니다.

초기화·취득·반환과 검증을 포함한 전체 C 예제는 다음처럼 실행할 수 있습니다.

cc -std=c11 -Wall -Wextra -Werror -O2 slot_pool.c -o slot_pool
./slot_pool

full pool rejected; slot 1 reused
slot ownership checks passed

예제는 현재의 C11 컴파일러를 사용하는 단일 프로세스·단일 스레드 코드입니다. 네 슬롯의 고갈과 재사용, 잘못된 인덱스, 반환 직후의 중복 반환, 반복 작업 중 슬롯 소유 상태를 검사합니다. 이 테스트의 범위는 슬롯 관리까지입니다. RB 트리와 공유메모리 연결은 구현하지 않습니다.

함수 하나를 넘어 참조의 수명까지 보기

트리의 삭제에서는 요청한 키가 있던 노드와 실제로 분리되는 노드가 다를 수 있습니다. 자식이 둘인 노드를 삭제할 때 후속 노드의 데이터를 복사하는 구현이 한 예입니다. 풀은 해당 삭제 구현이 실제로 분리한 슬롯을 돌려받아야 합니다.

그 뒤에도 참조가 남아 있을 수 있습니다. 작업 A가 슬롯 3을 가리키는 포인터를 보관하는 동안 작업 B가 그 슬롯을 반환하고 재사용하면, A는 같은 주소에서 다른 거래를 읽게 됩니다. 메모리를 해제하지 않았어도 잘못된 접근입니다.

예제의 used는 이 문제를 막지 못합니다. 슬롯이 재사용되면 다시 참이 되기 때문입니다. 잠금으로 보호하는 범위, 참조가 끝난 뒤의 반환, 슬롯 번호와 세대 번호를 함께 쓰는 핸들 같은 수명 정책을 검토해야 합니다. 세대 번호도 검사와 접근 사이의 경쟁을 저절로 해결하지는 않습니다.

Agent에게 리뷰를 요청한다면 반환된 포인터의 보관 위치, 잠금 해제 시점, 슬롯 재사용 경로를 함께 추적하도록 범위를 정할 수 있습니다.

테스트 목록을 코드가 놓일 환경에서 도출하기

이 사례를 새로 만든다면 슬롯 풀의 단위 테스트 외에 다음 동작도 확인해야 합니다.

조건	확인할 동작
다른 주소에 연결되는 공유 영역	프로세스별 시작 주소가 달라도 같은 항목을 찾는가
동시 조회·삭제·재사용	참조가 유효한 동안 슬롯이 재사용되지 않는가
용량 고갈과 중간 실패	정한 실패 동작을 따르고 예약 슬롯이 누수되지 않는가
프로세스의 비정상 종료	초기화·갱신 중 중단됐을 때 정한 복구 정책이 동작하는가
대상 컴파일러	지원하는 문법·정렬·타입 규칙 안에서 빌드하고 실행되는가

첫 항목은 프로세스별 연결 주소가 다를 수 있기 때문입니다. 일반 포인터를 공유하려면 주소에 대한 전제가 필요하며, 오프셋이나 슬롯 인덱스를 쓰면 각 프로세스의 시작 주소를 기준으로 접근할 수 있습니다. 당시 구현은 포인터 기반이었고 설명용 예제는 인덱스 기반이므로, 둘의 주소 처리까지 같은 것으로 볼 수는 없습니다.

프로세스 간 동기화에서는 POSIX mutex의 기본 프로세스 내부용 속성과 PTHREAD_PROCESS_SHARED 같은 공유 속성을 구분해야 합니다. 이 설정만으로 중단된 갱신의 복구까지 해결되지는 않습니다.

성능은 같은 입력·점유율·동기화 조건에서 처리량, 지연 분포와 메모리를 별도로 비교해야 합니다. 배열에 저장해도 트리 탐색이 연속 접근이 되지는 않고, 슬롯을 재사용해도 예약 용량은 유지됩니다. 슬롯 풀 예제의 성공만으로 성능 개선율을 판단할 수는 없습니다.

Agent와 공유할 작업 명세로 바꾸기

앞의 사례를 바탕으로 새 작업을 가정하면, Agent에게 전달할 명세를 다음처럼 구성할 수 있습니다.

목적
여러 프로세스가 같은 상태 정보를 키로 조회하고 갱신한다.

확인된 제약
- 저장 공간은 미리 확보한 공유 영역 안에서 관리한다.
- 데이터와 내부 연결은 프로세스별 연결 주소를 고려한다.
- 지정된 컴파일러에서 지원하는 기능만 사용한다.

먼저 결정할 것
- 최대 항목 수, 키의 특성, 조회·갱신 비율
- 순서·범위 검색의 필요 여부
- 중복 키, 용량 고갈, 프로세스 중단 시 정책

검토 요청
- 검색 구조와 공간 관리 방식을 나누어 대안을 비교한다.
- 소유권과 동기화 범위, 반드시 유지할 조건을 정리한다.
- 조건별 검증 방법과 아직 확인하지 못한 가정을 제시한다.
- 합의된 범위부터 구현하고 검증 결과를 조건과 연결한다.

처음에는 빈 항목이 있어도 됩니다. Agent와 저장소를 살펴보며 채우고, 작은 실험으로 선택지를 좁히면 됩니다.

코드와 함께 선택 이유를 남기기

이번에 예전 코드를 다시 읽으며 RB 트리를 선택한 이유 일부를 역으로 추정해야 했습니다. 구현은 남았지만, 어떤 대안을 검토하고 왜 제외했는지는 충분히 남아 있지 않았습니다.

AI Agent와 작업할 때는 제약 → 선택 → 근거 → 검증 → 남은 가정을 코드와 함께 짧게 기록해 두면 좋겠습니다. 나중에 free list를 일반 할당기로 바꾸거나 잠금 범위를 줄이려 할 때, 다음 작업자는 무엇을 다시 확인해야 하는지 알 수 있습니다.

코드를 만드는 과정에 Agent가 참여하더라도, 변경이 원래의 조건을 지키는지 판단할 근거는 필요합니다. 그 근거까지 남겨야 다음 구현과 리뷰로 설계 의도가 이어집니다.

참고 자료

• Linux: Red-black Trees - 트리 노드의 배치, 검색과 삭제, 호출자가 맡는 잠금 책임을 설명합니다.
• Linux man-pages: shmat - 공유메모리 연결 주소와 영역 내부 참조를 다룹니다.
• 이 글의 슬롯 풀 C 예제 - 초기화, 취득·반환과 슬롯 소유 상태 검증을 포함합니다.

함께 읽기 좋은 글

• 수정하지 않을 YAML 로그를 왜 전부 객체로 만들까 - 익숙한 구현을 선택하기 전에 실제 접근 방식과 할당 필요를 확인하는 사례입니다.
• 로그가 병목이 될 때: Log4j2 Appender의 무거운 일을 요청 경로 밖으로 밀어내기 - 함수의 동작뿐 아니라 실행 위치와 용량 한계까지 함께 설계하는 기준을 연결합니다.