정적 할당, 일정한 작업량

2026년 9월 2일

다음 이메일에 대한 답변:

메모리 안전성의 가장 어려운 문제에서 제가 겪었지만 명확히 표현하지 못했던 무언가를 짚어 주셨습니다. 당신의 사례는 한 유니언 변형을 가리키는 포인터가 다른 변형의 쓰기 이후에도 살아남는 경우이므로, 살아 있는 타입 지정 포인터가 이제 다른 무언가에 속한 바이트를 읽게 됩니다.

작년에 저는 지정가 주문 매칭 엔진을 작성했고 use-after-free 버그를 배포했습니다. 취소된 주문이 여전히 가격 수준에 연결된 상태에서 풀로 반환되었고, 다음 할당이 그 메모리를 새 주문에 넘겨 주었으며, 오래된 연결은 계속 해석되었습니다. 저는 이를 “수명 관리를 부주의하게 했다”는 범주에 넣었습니다.

당신의 글을 읽은 뒤로는 그것이 맞는지 확신이 없습니다. 재활용 풀은 “현재 이 슬롯에 존재하는 객체의 어느 세대인가”라는 태그를 가진 태그드 유니언처럼 보이는데, 타입 시스템은 이를 전혀 추적하지 않습니다. 이것이 타당한 해석인가요? 아니면 세대 인덱스가 실제로 이를 해결하므로 풀 사례는 진정으로 더 쉬우며, 유니언 사례에는 이에 상응하는 방법이 없는 건가요?

그렇습니다. 객체 풀은 메모리 안전성과 더 일반적인 정확성의 관계를 명확히 해 주므로 생각해 볼 만한 흥미로운 사례입니다.

먼저, 객체 풀을 사용하지 않고 주문 객체를 malloc 및 free한다고 생각해 봅시다. 이 경우 use-after-free라는 논리적 오류는 물리적인 타입 혼동으로 바뀌며, 임의 코드 실행 등으로 쉽게 이어질 수 있습니다. 서로 다른 _타입_의 두 객체가 같은 메모리 위치를 공유한다면, 한 객체에서 사용자가 제어하는 정수가 다른 객체에서는 함수 포인터일 수 있습니다. 즉, 악용 가능한 goto 원시 기능입니다.

이제 타입 T의 “죽은” 객체 목록을 저장하는 객체 풀을 도입하면 어떻게 될까요? 논리적인 use-after-free는 여전히 가능하지만, 물리적 효과는 이제 다릅니다. 여전히 메모리 별칭은 발생하지만 타입 혼동은 없습니다. 추가로 해당 객체가 인라인 열거형을 저장하는 어려운 경우까지 맞닥뜨리지 않는 한, 정수를 조작하여 함수 포인터를 바꿀 수는 없습니다. 그런 일이 일어나지 않는다고 가정하면, 결과가 마음에 들지 않더라도 완전히 정의되고 결정적인 동작을 얻게 됩니다.

이는 코드 강화에 관한 흥미로운 해결책을 제시하며, 저는 이를 Fil에서 배웠습니다. 만약 할당 함수가 타입 지정 방식이라면(실행 시 타입 소거된 크기와 정렬이 아니라 T 컴파일타임 매개변수나 실행 시 타입 증거를 받는다면), 내부적으로 타입별로 분리된 풀을 사용하는 할당자를 작성할 수 있습니다. 이 방식은 할당자가 타입 U 객체에서 해제된 메모리를 타입 T 객체에 재사용할 수 없으므로 다소 메모리 효율이 떨어집니다. 하지만 메모리 오버헤드는 아마 작을 것입니다(드문 객체 타입은 중요하지 않고, 흔한 객체 타입은 같은 타입 내에서 재사용이 많이 일어납니다). 실제로 메모리 지역성은 좋아질 수 있고, 또한 대부분의 타입 혼동을 해결합니다. 다시 말해, 인라인 열거형은 이를 깨뜨리지만, 흥미롭게도 열거형 변형을 항상 힙에 할당한다면 다시 작동합니다. Fil-C는 C 할당자의 인터페이스가 타입 지정 방식이 아니므로 이를 사용할 수 없지만, 다른 누군가는 가능할 것입니다 :P

하지만 이것은 학술적인 이야기입니다. 버그를 어떻게 피할까요? 세대 인덱스는 널리 쓰이는 해결책이지만, 저는 이를 사용해 본 적이 없으므로 이 패턴에 관한 비상식적인 통찰은 없습니다. 대신 TigerStyle에서 얻은 또 다른 한 쌍의 요령을 공유하겠습니다. 저는 주문 매칭 엔진이 무엇인지 희미하게만 이해하고 있지만, 이 요령들이 그곳에서도 도움이 될 것이라 생각합니다.

정적 할당

첫 번째는 다음과 같습니다.

초기화 이후에는 동적 메모리 할당 금지

https://www.youtube.com/watch?v=GRJtYwneG2Q&t=1823s

이는 풀이라는 아이디어를 논리적 결론까지 밀고 간 것입니다. 시작할 때 처리할 의향이 있는 주문의 최대 개수를 지정하고, 절대 그 이상으로 가지 않습니다. 따라서 프로그램은 다음과 같이 시작할 수 있습니다.

$ order-engine --orders-max=1_000_000 그리고 main 함수의 첫 줄 중 하나는 다음과 같을 것입니다:

const orders: []Order = try gpa.alloc(Order, cli_args.orders_max); 실행 중 orders_max보다 많은 요청이 들어오면 초과 요청은 거절됩니다. 누군가는 이렇게 이의를 제기할 수 있습니다. “하지만 실제로 주문 하나를 더 담을 여유 메모리가 있다면요? 적어도 처리해 보는 것이 좋지 않을까요?”

제 대답은 “글쎄요, 없다면 어떡하죠?”일 것입니다. 엄격한 한계 없이 용량 한계에서 동작하는 시스템은 파국적으로 실패합니다. Order 하나를 더 할당하려는 시도는 커널의 OOM 킬러가 전체 주문 매칭 엔진을 종료하게 만들어 나머지 백만 건의 주문까지 잃게 할 수 있습니다. 더 나쁘게는, 재시작조차 할 수 없도록 감독 프로세스를 죽일 수도 있습니다.

정적 할당은 마음의 평화를 줍니다. 메모리가 충분하지 않으면 시스템이 시작하지 못할 수 있습니다. 하지만 일단 시작했다면, 더 강력한 장비를 준비하는 동안에도 서비스를 계속 제공하면서 과부하를 우아하게 처리할 것이라고 안심할 수 있습니다.

일정한 작업량

주문 슬라이스로 무엇을 하겠습니까? 한 가지 접근법은 @memset(orders, undefined)를 수행하고, 비트 집합으로 여유 객체를 추적하는 풀에 슬라이스를 넘기는 것입니다:

const OrderPool = struct {
    orders: []Order,
    free: DynamicBitSet,

    fn acquire(pool: *OrderPool) ?*Order { ... }
    fn release(pool: *OrderPool, order: *Order) { ... }
};

또는 자유 목록을 사용할 수 있습니다:

const OrderPool = struct {
    orders: []union {
        order: Order,
        next_free: ?u32,
    },
    first_free: ?u32,
};

하지만 다른 접근법도 있습니다. 주문 수의 한도를 생각하는 대신, 아무 작업도 하지 않는 중립 주문을 도입하여 시스템이 항상 고정된 양의 주문을 갖도록 설계할 수 있습니다:

const Order = {
    id: u128,
    price: u32,
    count: u32,

    tag: enum { bid, ask, reserved },

    pub const reserved: Order = .{
        .id = 0,
        .price = 0,
        .count = 0,
        .tag = .reserved,
    };
};

그러면 초기화는 @memset(orders, .reserved)가 됩니다.

여기에는 인지적인 이점이 하나 있습니다. 더는 주문을 생성하고 파괴한다는 관점으로 생각하지 않습니다. 대신 주문은 주문 수 보존 법칙에 따라 시스템 안을 순환할 뿐입니다. 주문이 어디로 가는지뿐 아니라 어디서 왔는지도 항상 신경 써야 하므로, 주문을 놓치기가 더 어려워집니다. 상태의 각 _쌍_마다 상태 전이 함수를 명시적으로 작성하며, 그 덕분에 모든 경우를 빠짐없이 열거하기 쉬워집니다. 그리고 모든 지점에서 상태가 예상한 것인지 단언하여 이를 이중으로 확인합니다(그런 다음 단언문을 DST합니다).

또 다른 이점은 코드 단순화와 예측 가능성입니다. 더는 “활성” 주문의 별도 컬렉션을 추적할 필요가 없습니다. 대신 항상 전체 집합을 순회하면서 예약된 주문에는 아무 작업도 하지 않습니다. 이는 낭비처럼 느껴집니다. 주문이 적을 때 코드를 더 빠르게 실행해야 하지 않을까요? 하지만 다음을 생각해 봅시다. 주문 한도를 미리 지정함으로써, 그만큼을 처리할 수 있음을 약속합니다. 만약 최대 수의 주문이 활성 상태라면 시스템의 성능은 허용 가능한가요? 그렇지 않다면 그것은 버그입니다! 한계에 도달했을 때 시스템이 쓸 수 없을 정도로 느려지는 회색 실패 역시 실패의 한 형태입니다.

인덱스를 피하면 최대 부하 상황에서 성능이 향상됩니다. 다음 코드는

for (orders) |order| {
    process(order)
}

다음 코드보다 컴파일러가 벡터화하기 쉽고 CPU 캐시가 미리 가져오기 쉽습니다:

for (orders_active) |order_index| {
    const order = orders[order_index];
    process(order);
}

정적 할당과 마찬가지로, 일정한 작업량 원칙은 성능 측면에서 마음의 평화를 줍니다. P100 지연 시간은 부하와 무관하게 평탄하게 유지됩니다. 성능 부족은 Black Friday 대기 근무 중이 아니라 시스템을 배포할 때 발견됩니다.

TigerBeetle에서는 이 패턴을 작은 단위로 적용합니다. 조기 반환을 하는 검색 루프를 작성하는 대신:

const item = for (items) |item| {
    if (predicate(item)) break item;
} else null;

때때로 루프가 자연스러운 전체 과정을 끝까지 실행하게 두고, 추가로 일치하는 항목이 _유일_하다고 단언합니다:

https://github.com/tigerbeetle/tigerbeetle/blob/0.17.9/src/vsr/grid.zig#L715-L725

---

늘 그렇듯, 이것은 여러분의 도구 상자에 넣어 두면 유용한 하나의 요령이지만, 프로그래밍의 모든 문제에 대한 보편적인 해결책은 아닙니다.