[PonsWarp 개념 교실 9] 재정렬 버퍼 — Arena·free-list·BTreeMap·LRU

쉽게 말하면, **재정렬 버퍼는 "뒤섞여 도착한 파일 조각들을 순서대로 다시 맞추는 임시 보관함"**이다. 순서가 맞는 조각은 즉시 통과시키고, 아닌 조각은 보관했다가 순서가 이어질 때 꺼낸다.

이번 글에서는 그 보관함이 어떻게 만들어졌는지 — Arena 메모리 풀, free-list, BTreeMap 인덱스, LRU 퇴거까지 하나씩 뜯어본다.

이게 왜 필요한가 — "순서대로 온다"는 보장이 없다

WebRTC DataChannel은 ordered 채널이면 패킷 순서를 보장한다. 그런데 이 프로젝트는 재전송·재개·부분 실패가 일어나는 구조다.

• 복호화 실패로 특정 조각만 재요청되면, 그 뒤의 조각이 먼저 도착할 수 있다.
• 재개(resume) 후에는 이미 받은 위치와 새로 받는 위치가 섞인다.
• 멀티 스트림/하이브리드 경로를 쓰면 순서가 더 흐트러진다.

그래서 수신측은 "순서에 맞는 조각만 디스크에 쓰고, 나머지는 기다리는" 구조가 필요하다. 파일 중간에 구멍이 난 채로 쓰면 안 되기 때문이다. (파일깨짐 문제의 직접적인 원인이 이 순서 문제였다.)

두 갈래 길 — fast path와 buffered path

재정렬 버퍼의 핵심 동작은 push(chunk, offset) 하나로 두 갈래로 나뉜다.

rust
// pons-core-wasm/src/reordering_buffer.rs
pub fn push(&mut self, chunk: &[u8], offset: u64) -> Option<Vec<u8>> {
    // 이미 처리된 오프셋이나 중복은 무시
    if offset < self.next_expected { return None; }
    if self.index.contains_key(&offset) { return None; }

    // Fast Path: 정확히 기다리던 순서 → 즉시 통과
    if offset == self.next_expected {
        self.advance(chunk_len);
        let mut result = chunk.to_vec();
        self.drain_into(&mut result);   // 연속된 버퍼 청크까지 이어서 배출
        return Some(result);
    }

    // Buffered Path: Arena에 저장, 아직 배출 안 함
    self.store_chunk(chunk, offset);
    None
}

• Fast Path: offset == next_expected(정확히 다음에 올 위치)면 즉시 반환. 버퍼를 거치지 않는다.
• Buffered Path: 미래 오프셋이면 Arena에 보관하고, next_expected가 그 위치에 도달했을 때 drain한다.

drain_into가 중요한 이유는 한 조각이 도착하면 그 뒤로 연속된 버퍼 청크들까지 한 번에 배출하기 때문이다. 5번이 도착하면 6, 7, 8이 버퍼에 이미 있었다면 모두 이어서 나간다.

도착 순서:  2  5  3  4  6  ...
next_expected = 1

push(2) → 버퍼 [2]        (1이 아직 없음)
push(5) → 버퍼 [2, 5]
push(3) → 버퍼 [2, 3, 5]
push(4) → 버퍼 [2, 3, 4, 5]
push(1) → fast path! 1 반환 + drain → 2, 3, 4, 5 연속 배출

Arena + free-list — GC 없는 메모리 관리

Rust/WASM에서 매 조각마다 Vec을 새로 만들면 GC 압박이 생긴다. 그래서 **Arena(미리 할당한 큰 메모리 덩어리)**를 쓰고, 슬롯 단위로 빌려주고 돌려받는다.

rust
// pons-core-wasm/src/reordering_buffer.rs
struct Arena {
    data: Vec<u8>,              // 64KB × 2048 슬롯 = 128MB 단일 버퍼
    free_list: Vec<u16>,        // 비어 있는 슬롯 번호 목록
    slot_meta: Vec<Option<SlotMeta>>,  // 슬롯별 길이·타임스탬프
}

• allocate(): free_list에서 슬롯 번호를 pop — O(1)
• deallocate(): 슬롯 반환, free_list에 push — O(1)
• 슬롯 번호로 data의 오프셋을 계산해 읽고 쓴다 (64KB × slot_idx)

이 패턴은 "객체 풀"이라 불리며, 개념 29(객체 풀 + 상태 머신)에서 더 깊게 다룬다. 재정렬 버퍼는 이 풀을 인덱스와 함께 쓴다.

BTreeMap 인덱스 — "offset → 슬롯" 정렬 매핑

Arena는 데이터 저장소일 뿐이고, "어느 offset이 어느 슬롯에 있는지"는 BTreeMap이 관리한다.

rust
index: BTreeMap<u64, u16>,   // offset → slot_index

BTreeMap은 키(offset)가 정렬된 상태를 유지하므로, "next_expected 다음에 어떤 조각이 있는지"를 정렬 순서대로 찾기 쉽다. drain할 때도 오름차순으로 꺼내면 된다.

BTreeMap 상태:
  { 10 → slot 3, 12 → slot 7, 14 → slot 1 }

next_expected = 11이 되면 → 12를 찾아 배출 → 14를 찾아 배출

LRU 퇴거 — 128MiB 한도를 지키는 마지막 방어선

버퍼가 무한정 커질 수는 없다. Arena는 **최대 128MiB(64KB × 2048)**다. 꽉 찼을 때는 가장 오래된(LRU) 청크를 밀어낸다.

rust
// pons-core-wasm/src/reordering_buffer.rs
const MAX_BUFFER_SIZE: usize = 128 * 1024 * 1024;

fn evict_oldest(&mut self) -> bool {
    // timestamp가 가장 오래된 슬롯을 찾아 해제
}

타임스탬프로 "가장 오래 기다린 조각"을 골라 퇴거한다. 이 조각은 나중에 재요청되어야 하는데, 그 재요청 메커니즘은 "resume 커서" 편에서 다룬다. 버퍼는 무한정 기다리지 않는다 — 일정 시간이 지나면 "이 조각은 도착 안 하겠다"고 판단하고 보내는 쪽에 다시 달라고 한다.

JS 폴백 — WASM 없이도 동작하는 안전망

브라우저에서 WASM을 못 쓰는 경우를 위해 JS 버전 ReorderingBuffer도 있다. 동일한 개념(offset Map, 128MiB 한도)을 쓰되, TTL 30초와 5초 주기 스테일 청소를 추가했다.

typescript
// PonsWarp/src/services/reorderingBuffer.ts
private readonly MAX_BUFFER_SIZE = 128 * 1024 * 1024; // 128MB
private readonly CHUNK_TTL = 30000;  // 30초
private cleanupInterval = setInterval(() => this.checkStaleChunks(), 5000);

PonsWarp 적용 지점

항목	값	증거
슬롯 크기	64KB	reordering_buffer.rs:4
슬롯 수 / 용량	2048개 / 128MiB	reordering_buffer.rs:5-6
Arena 구조	data + free_list + slot_meta	reordering_buffer.rs:16-20
O(1) 할당/해제	free_list pop/push	reordering_buffer.rs:37-44
오프셋 인덱스	BTreeMap<u64, u16> (정렬 유지)	reordering_buffer.rs:75
fast path	offset == next_expected 즉시 통과	reordering_buffer.rs:117-126
연속 배출	drain_into (뒤따르는 버퍼 청크까지)	reordering_buffer.rs:171-195
LRU 퇴거	evict_oldest (timestamp 기준)	reordering_buffer.rs:197-223
JS 폴백	Map + TTL 30s + 5s 스테일 청소	reorderingBuffer.ts:26-35

지금 돌아보는 판단

세 가지를 정리한다.

첫째, "순서 보장"보다 "순서 복원"이 더 실용적이다. ordered DataChannel이 순서를 보장하지만, 재전송·재개·부분 실패가 있으면 보장이 깨진다. 그래서 애플리케이션 레벨에서 복원 계층을 두는 것이 안전하다. "하위 계층이 보장하니까 안심"보다 "보장이 깨져도 스스로 복원"이 파일 전송의 현실에 맞다.

둘째, 구조 선택이 속도와 메모리를 결정한다. Arena+free-list는 O(1) 할당·해제로 GC를 피하고, BTreeMap은 정렬된 인덱스를 유지해 drain을 단순하게 만든다. "버퍼"라는 단순한 개념도 내부는 데이터 구조의 조합이다.

셋째, LRU 퇴거는 "실패 전략"의 일부다. 버퍼가 가득 차면 그냥 거부하는 게 아니라 가장 오래된 것을 버리고 재요청으로 이어간다. "무한정 기다림"과 "즉시 실패" 사이의 절충이 이 프로젝트의 전반적인 설계 철학이다.

한 문장 정리

재정렬 버퍼는 순서가 맞는 조각은 즉시 통과(fast path)시키고, 아닌 조각은 Arena+free-list에 보관하며 BTreeMap으로 인덱스를 유지하고, 128MiB를 넘으면 LRU로 밀어내는 — 순서 복원 + 메모리 통제의 복합 구조다.

관련 개념: [개념 7 — 22바이트 패킷 헤더] (offset이 정렬 키) · [개념 29 — 객체 풀] (Arena 패턴)

다음 글: [개념 10 — ZIP64 스트리밍: LFH·CEN·EOCD64 구조]