30. 순서 보장 채널 재정렬 버퍼: 무제한 버퍼링과 갭 정지 (C#)

난이도 상

내 리뷰 · C#

내 리뷰 · C++

해설 · C#

해설 — 순서 보장 채널 재정렬 버퍼: 무제한 버퍼링과 갭 정지 (C#)

난이도: 상

요약

재정렬 버퍼에 상한이 없어서, 큰 seq 를 가진 순서-밖 프레임을 계속 받으면 버퍼가 무한정 커진다(메모리 증폭 DoS). 또한 NextExpected 프레임 하나가 오래(혹은 영영) 오지 않으면 그 뒤의 모든 프레임이 버퍼에 쌓인 채 채널이 무기한 정지(head-of-line 블로킹) 되고, 재전송 요청(NAK)·갭 타임아웃이 없어 스스로 회복하지 못한다.

문제점

분류 태그: 자원 상한 부재(무제한 버퍼 → 메모리 증폭 DoS) · head-of-line 정지(갭 타임아웃/재전송 부재) · 중복 시퀀스 무점검 덮어쓰기.
증상: 정상 트래픽에서도 순서가 조금만 뒤섞이면 메모리가 출렁이고, 악성 피어가 nextExpected 만 빼고 큰 seq 들을 흘리면 서버 RAM 이 급증해 OOM/GC 폭주. 중간 프레임 유실 시 이후 데이터가 상위로 영영 전달되지 않아 해당 연결이 "먹통".
재현 조건:
1. 메모리 증폭: nextExpected = 0 인데 공격자가 seq = 1,000,000 … 처럼 절대 채워지지 않을 큰 값들의 프레임을 계속 전송 → (A) 에서 모두 _reorder 에 적재, 상한이 없어 무한 증가.
2. HoL 정지: seq 5 가 유실. seq 6,7,8… 은 계속 도착 → _reorder 에 쌓이지만 (B) 의 while 은 nextExpected(=5) 를 못 찾아 한 건도 전달 못 함. 재전송 유도가 없어 5 가 다시 오지 않으면 영구 정지.
근본 원인:
- (A) _reorder 에 담기 전에 "이 seq 가 수신 윈도우 안(가까운 미래)인가", "버퍼 항목 수·총바이트가 상한 이내인가"를 검사하지 않는다. 순서-밖이면 무조건 저장 → 무제한. 같은 seq 재수신 시 조용히 덮어써(중복 처리) 원본 손실 가능.
- (B) 갭이 생겼을 때 이를 감지해 재전송을 요청하거나(NAK), 일정 시간 뒤 채널을 리셋/끊는 타임아웃이 없다. 그래서 유실 하나가 채널 전체를 막고 버퍼는 계속 쌓인다.

수정안

수신 윈도우로 미래 범위를 제한하고, 버퍼 크기(항목·바이트) 상한과 갭 타임아웃/재전송을 둔다.

class OrderedChannel
{
    private const int Window = 1024;            // nextExpected 기준 허용 미래 범위
    private const int MaxBufferedBytes = 1 << 20;

    private int _nextExpected;
    private int _bufferedBytes;
    private readonly Dictionary<int, byte[]> _reorder = new();
    private readonly IAppSink _app;
    private long _gapSinceTicks;                 // 갭이 처음 생긴 시각

    public bool OnReceive(int seq, byte[] payload)
    {
        // 과거이거나 윈도우 밖(너무 먼 미래)이면 거절
        if (seq < _nextExpected || seq - _nextExpected >= Window)
            return false;
        if (_reorder.ContainsKey(seq)) return true;           // 중복은 무시(덮어쓰기 금지)
        if (_bufferedBytes + payload.Length > MaxBufferedBytes)
            return false;                                     // 총량 상한 초과 → 거절

        _reorder[seq] = payload;
        _bufferedBytes += payload.Length;
        if (_reorder.Count == 1) _gapSinceTicks = Environment.TickCount64;

        while (_reorder.TryGetValue(_nextExpected, out byte[] next))
        {
            _app.Deliver(_nextExpected, next);
            _reorder.Remove(_nextExpected);
            _bufferedBytes -= next.Length;
            _nextExpected++;
        }
        return true;
    }

    // 주기 타이머에서: 갭이 오래 지속되면 재전송 요청 또는 리셋
    public void OnTick(long nowTicks, Action<int> requestResend)
    {
        if (_reorder.Count > 0 && nowTicks - _gapSinceTicks > 200 /*ms*/)
            requestResend(_nextExpected);        // 누락 seq 재전송 유도(NAK). 한도 초과 시 연결 종료.
    }
}

핵심: (1) seq - nextExpected >= Window 로 먼 미래를 거절, (2) 항목/바이트 상한으로 메모리 증폭 차단, (3) 중복 seq 는 덮어쓰지 않음, (4) 갭 타임아웃에서 재전송 요청 또는 채널 리셋으로 HoL 정지를 회복. seq 랩어라운드가 있는 장수명 채널이면 비교를 시리얼 넘버 산술로 바꾼다(별도 주제).

더 나은 설계 (트레이드오프)

고정 크기 링 버퍼(슬롯 = seq % Window) + 존재 비트맵: 해시맵 대신 Window 크기 배열과 비트마스크로 O(1) 삽입/조회, 메모리는 상한 고정. 대신 윈도우보다 먼 재정렬은 못 담으므로 재전송에 의존. RUDP 수신 윈도우의 표준형.
selective ACK/NAK: 수신 상태(받은 seq 비트맵)를 주기적으로 알려 송신 측이 빠진 것만 재전송하게 하면 정지·낭비를 함께 줄인다. 프로토콜 복잡도 증가.
순서 완화: 실제로 순서가 필요 없는 데이터(스냅샷 등)는 순서 보장 채널에서 빼 비순서 채널로 보내면 HoL 자체가 사라진다.

면접 포인트

재정렬 버퍼는 반드시 수신 윈도우로 미래를 제한하고 항목·바이트 상한을 둬야 하는 이유(무제한이면 곧 DoS 벡터).
head-of-line 블로킹의 정체와, 재전송(NAK)/갭 타임아웃 없이는 유실 하나가 채널 전체를 멈추는 메커니즘.
링 버퍼+비트맵 vs 해시맵 재정렬의 트레이드오프, 그리고 "순서가 정말 필요한 데이터만 순서 채널로" 라는 설계 원칙.

해설 · C++

해설 — 순서 보장 채널 재정렬 버퍼: 무제한 버퍼링과 갭 정지 (C++)

난이도: 상

요약

std::map 재정렬 버퍼에 상한이 없어, 큰 seq 를 가진 순서-밖 프레임이 계속 들어오면 노드가 무한히 할당돼 메모리가 폭증한다(증폭 DoS, OOM). 또한 nextExpected 프레임 하나가 오래/영영 오지 않으면 이후 프레임이 전부 버퍼에 쌓인 채 채널이 무기한 정지(head-of-line) 되고, 재전송 요청·갭 타임아웃이 없어 스스로 못 벗어난다.

문제점

분류 태그: 자원 상한 부재(무제한 버퍼 → 메모리 증폭 DoS) · head-of-line 정지(갭 타임아웃/재전송 부재) · 중복 시퀀스 덮어쓰기.
증상: 순서가 조금 뒤섞여도 std::map 이 커졌다 줄었다 하며 노드 할당 비용이 튀고, 공격자가 nextExpected 만 빼고 먼 seq 들을 흘리면 reorder_ 가 끝없이 자라 OOM. 중간 유실 시 이후 데이터가 상위로 영영 안 감(연결 먹통).
재현 조건:
1. 증폭: nextExpected_ = 0 인데 공격자가 seq = 2^20, 2^20+1 … 을 계속 전송 → (A) 에서 모두 reorder_ 에 삽입, 상한 없어 무한 증가.
2. HoL 정지: seq 5 유실, 6,7,8… 계속 도착 → (B) 의 while 이 find(nextExpected_=5) 실패로 아무것도 못 꺼냄. 재전송 유도 없으면 영구 정지.
근본 원인:
- (A) 저장 전에 "seq 가 수신 윈도우 이내인가", "버퍼 노드 수·총바이트가 상한 이내인가" 를 검사하지 않는다. 순서-밖이면 무조건 reorder_[seq] = ... → 무제한. 같은 seq 재수신 시 operator[] 가 조용히 덮어써 원본 유실.
- (B) 갭 발생 시 재전송 요청(NAK)이나 타임아웃 후 리셋/종료가 없다. 유실 하나가 채널 전체를 막고 버퍼는 계속 쌓인다. (uint32_t seq 의 랩어라운드는 별도 주제이나 장수명 채널에선 함께 고려.)

수정안

수신 윈도우로 미래 범위를 제한하고, 고정 크기 링 버퍼 + 존재 표시로 메모리를 상한 고정한다. 갭 타임아웃에서 재전송을 유도한다.

#include <vector>
#include <cstdint>
#include <chrono>

class OrderedChannel {
    static constexpr uint32_t kWindow = 1024;          // 2의 거듭제곱
    uint32_t nextExpected_ = 0;
    std::vector<std::vector<uint8_t>> slots_{kWindow};  // seq & (kWindow-1)
    std::vector<uint8_t> present_ = std::vector<uint8_t>(kWindow, 0);
    size_t bufferedBytes_ = 0;
    static constexpr size_t kMaxBytes = 1u << 20;
    std::chrono::steady_clock::time_point gapSince_{};

    void deliver(uint32_t, const std::vector<uint8_t>&) {}
public:
    bool onReceive(uint32_t seq, std::vector<uint8_t> payload) {
        // 과거이거나 윈도우 밖(너무 먼 미래)이면 거절
        if (seq < nextExpected_ || seq - nextExpected_ >= kWindow) return false;
        uint32_t idx = seq & (kWindow - 1);
        if (present_[idx]) return true;                          // 중복 무시
        if (bufferedBytes_ + payload.size() > kMaxBytes) return false;

        bufferedBytes_ += payload.size();
        slots_[idx] = std::move(payload);
        present_[idx] = 1;
        if (gapSince_.time_since_epoch().count() == 0)
            gapSince_ = std::chrono::steady_clock::now();

        // 연속 구간 전달
        for (uint32_t i = nextExpected_ & (kWindow - 1); present_[i]; i = nextExpected_ & (kWindow - 1)) {
            deliver(nextExpected_, slots_[i]);
            bufferedBytes_ -= slots_[i].size();
            slots_[i].clear();
            present_[i] = 0;
            ++nextExpected_;
        }
        return true;
    }

    // 주기 타이머: 갭이 오래면 재전송 요청 또는 리셋
    template <class ResendFn>
    void onTick(std::chrono::steady_clock::time_point now, ResendFn requestResend) {
        if (bufferedBytes_ > 0 && now - gapSince_ > std::chrono::milliseconds(200))
            requestResend(nextExpected_);   // NAK. 한도 초과 시 연결 종료.
    }
};

핵심: 링 버퍼 크기가 곧 수신 윈도우이므로 메모리가 kWindow 로 상한 고정되고, seq - nextExpected_ >= kWindow 로 먼 미래를 거절해 증폭을 원천 차단한다. present_ 비트로 중복 덮어쓰기를 막고, 갭 타임아웃에서 재전송/리셋으로 HoL 을 회복한다.

더 나은 설계 (트레이드오프)

링 버퍼 + 비트맵(위 방식): O(1) 삽입/전달, 메모리 상한 고정. 단 윈도우보다 먼 재정렬은 못 담으니 재전송 의존. RUDP 수신 윈도우의 정석.
selective NAK / SACK: 받은 seq 를 비트맵으로 송신 측에 알려 빠진 것만 재전송. 정지와 낭비를 함께 줄이지만 프로토콜·상태 복잡도 증가.
비순서 채널 분리: 순서가 불필요한 스냅샷·텔레메트리는 별도 비순서 채널로 보내 HoL 자체를 없앤다.

면접 포인트

std::map/unordered_map 재정렬 버퍼는 반드시 수신 윈도우와 바이트 상한을 둬야 함(무제한 = 원격 OOM 벡터), 그리고 링 버퍼+비트맵으로 상한을 구조적으로 고정하는 법.
head-of-line 정지의 메커니즘과, 갭 타임아웃/재전송(NAK) 없이는 유실 하나가 채널 전체를 멈추는 이유.
operator[] 의 조용한 덮어쓰기 함정과 중복 seq 방어, uint32_t seq 비교의 랩어라운드 주의(장수명 채널).

← 문제로 돌아가기