16. 채팅 스팸/도배 레이트리밋과 정상 메시지의 경합

난이도 중

내 리뷰 · C#

내 리뷰 · C++

해설 · C#

해설 — 채팅 스팸/도배 레이트리밋과 정상 메시지의 경합

난이도: 중

답변 프레임워크: 요약 → 문제 분류 → 원인 → 수정안 → 더 나은 설계

요약

Allow 전체가 락 없는 check-then-act 다. (C) if (b.Count >= Limit) return false; b.Count++; 는 비원자라, 같은 세션 패킷이 여러 IO 스레드에서 동시에 들어오면 둘 다 Count < Limit 을 보고 각각 ++ → 한도 초과(도배가 새어 나감). (B) 윈도 리셋도 검사–대입이 분리돼, 두 스레드가 동시에 리셋하면 한쪽의 카운트가 날아가 과도 허용되거나, 리셋과 ++ 가 겹쳐 유실 갱신된다. (A) GetOrCreate 가 락 없이 Dictionary 에 삽입해 동시 생성 시 컬렉션 손상/예외. 시각 기준이 벽시계라 NTP 점프 시 윈도가 잘못 판정된다. 정답 한 줄: 세션 버킷에 대한 검사+증가+윈도리셋을 원자적으로(세션별 락 또는 Interlocked/ 원자 토큰버킷) 수행하고, 시간은 단조 시계로 잰다.

문제점

(C) 한도 검사–증가 비원자 — 도배 통과 (동시성) ★간판

증상: Count==4(Limit=5) 인 상태에서 두 패킷이 동시에 Count >= 5 를 false 로 보고 각각 Count++ → 6. 도배 클라이언트가 패킷을 몰아 보내면 한도를 초과해 허용된다.
재현조건: 같은 세션의 채팅 패킷이 서로 다른 스레드에서 거의 동시 처리(매크로/도배).
근본 원인: read→compare→write 가 하나의 원자 연산이 아니다.

(B) 윈도 리셋 경합 — 카운트 유실/과도 허용 (동시성) ★간판

증상: 윈도가 막 지난 시점에 두 스레드가 동시에 now - WindowStartMs >= 1000 을 보고 둘 다 WindowStartMs=now; Count=0 실행 → 한 번의 윈도가 두 번 리셋되거나, 리셋과 다른 스레드의 Count++ 가 인터리빙돼 방금 증가분이 사라진다. 결과적으로 한 윈도에 N 보다 많이 허용되거나, 반대로 정상 메시지가 잘못 드롭될 수 있다.
근본 원인: 윈도 전이와 카운트 변경이 분리·비원자.

(A) GetOrCreate 의 락 없는 Dictionary 삽입 — 손상/예외 (동시성)

증상: 같은(또는 다른) 세션의 첫 메시지가 동시에 오면 _buckets[id]=b 동시 쓰기로 Dictionary 내부 손상/InvalidOperationException. 같은 세션이면 버킷이 둘 생겨 카운팅이 분열되기도 한다.
근본 원인: 공유 Dictionary 에 동기화 없음.

(정확성) 벽시계(UnixTimeMilliseconds) 윈도 — 시간 점프 (정확성)

증상: NTP 보정/수동 변경으로 시계가 뒤로 점프하면 now - WindowStartMs 가 음수가 돼 윈도가 영원히 리셋 안 되거나(차단 고착), 앞으로 점프하면 즉시 리셋(도배 통과).
근본 원인: 경과시간은 단조 시계로 재야 한다(Environment.TickCount64/Stopwatch).

수정안

핵심: 세션별 락으로 검사+증가+윈도전이를 원자화, 시간은 단조 시계. 동시 생성은 ConcurrentDictionary.GetOrAdd 로.

public class ChatRateLimiter
{
    private const int LimitPerSec = 5;

    private sealed class Bucket
    {
        public readonly object Gate = new();
        public int  Count;
        public long WindowStartMs;
    }

    private readonly System.Collections.Concurrent.ConcurrentDictionary<long, Bucket> _buckets = new();

    public bool Allow(long sessionId)
    {
        var b = _buckets.GetOrAdd(sessionId, _ => new Bucket { WindowStartMs = NowMs() });
        lock (b.Gate)                       // 세션 단위 임계구역(전역 경합 회피)
        {
            long now = NowMs();
            if (now - b.WindowStartMs >= 1000) { b.WindowStartMs = now; b.Count = 0; }
            if (b.Count >= LimitPerSec) return false;
            b.Count++;
            return true;
        }
    }

    private static long NowMs() => Environment.TickCount64;   // 단조 시계
}

포인트

ConcurrentDictionary.GetOrAdd → 동시 생성에도 버킷은 하나.
버킷별 락으로 검사+증가+윈도전이를 원자화하면서 세션 간 경합은 분리(전역 락보다 확장성↑).
Environment.TickCount64(단조)로 시계 점프 무력화.

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

원자 토큰 버킷(lock-free): 토큰 수/마지막 보충 시각을 하나의 64비트 상태로 묶어 CAS 루프로 갱신하면 락 없이 정확. 트레이드오프: 구현/검증 난이도↑.
슬라이딩 윈도 로그/카운터: 고정 1초 윈도는 경계에서 버스트(윈도 끝+다음 시작에 2N)를 허용. 슬라이딩 윈도/누수 버킷이 더 매끄럽다. 트레이드오프: 메모리/계산 비용.
버킷 GC: 오래된 세션 버킷을 만료 정리(메모리 누수 방지). 끊긴 세션 버킷 제거.
분산 환경: 여러 게이트웨이가 같은 플레이어를 처리하면 Redis 등 공유 카운터(원자 INCR+EXPIRE)나 게이트웨이 고정(sticky)으로. 트레이드오프: 네트워크 왕복/일관성.

면접 포인트 (예상 질문)

if(Count>=Limit) Count++ 가 왜 도배를 통과시키는지 두 스레드 인터리빙으로 설명하라.
전역 락 하나 vs 버킷별 락 vs lock-free 토큰버킷의 장단점은?
고정 윈도(1초 리셋) 방식의 경계 버스트 문제와 슬라이딩 윈도의 차이는?
레이트리밋에 벽시계를 쓰면 왜 위험한가? (시계 점프)

해설 · C++

해설 (C++) — 채팅 스팸/도배 레이트리밋과 정상 메시지의 경합

난이도: 중

답변 프레임워크: 요약 → 문제 분류 → 원인 → 수정안 → 더 나은 설계

요약

C# 판과 동일하게 Allow 전체가 락 없는 check-then-act 다. (C) count 검사–증가 비원자로 동시 패킷이 한도를 초과해 통과한다(도배 누출). (B) 윈도 리셋도 비원자라 유실 갱신/과도 허용. C++ 판에서 특히 위험한 것은 (A) GetOrCreate 가 락 없이 unordered_map 에 emplace 하는 것으로, 동시 삽입이 리해시와 겹치면 컨테이너 UB(C# 의 예외와 달리 조용한 메모리 오염)이며, 반환한 Bucket& 참조가 다른 스레드의 삽입으로 무효화될 수도 있다. 정답 한 줄: 버킷별 뮤텍스(또는 원자 토큰버킷)로 검사+증가+윈도전이를 원자화하고, 맵 접근을 동기화하며, 시간은 steady_clock 으로 잰다.

문제점

(C) 한도 검사–증가 비원자 — 도배 통과 (동시성) ★간판

증상: count==4(limit=5) 에서 두 스레드가 동시에 count >= 5 false → 각각 count++ → 6. 한도 초과 허용.
근본 원인: read-compare-write 가 원자가 아니다.

(B) 윈도 리셋 경합 — 유실 갱신/과도 허용 (동시성)

증상: 동시 리셋으로 카운트가 두 번 0이 되거나, 리셋과 count++ 인터리빙으로 증가분 유실. 한 윈도에 N 초과 허용 또는 정상 메시지 오드롭.

(A) GetOrCreate 무락 + 반환 참조 무효화 — UB (동시성/수명) ★간판

증상: 락 없는 unordered_map::emplace 동시 실행 → 리해시 중 UB. 또한 Bucket& 를 반환해 들고 있는 사이 다른 스레드 삽입이 리해시를 일으키면 그 참조가 댕글링 (unordered_map 은 리해시 시 참조/포인터 무효화 — 단, 노드는 유지되므로 값 참조는 보존되지만 이는 구현 세부에 의존, 동시 접근 자체가 이미 UB).
근본 원인: 공유 컨테이너 무동기 접근 + 내부 참조 노출.

(정확성) system_clock 윈도 — 시계 점프 (정확성)

증상: system_clock 은 벽시계라 NTP 보정 시 뒤로/앞으로 점프. 뒤로 점프 시 now - windowStartMs 음수 → 윈도 고착(차단), 앞 점프 시 즉시 리셋(도배 통과).
근본 원인: 경과시간은 std::chrono::steady_clock(단조)로.

수정안

#include <mutex>
#include <memory>

class ChatRateLimiter {
public:
    static constexpr int kLimitPerSec = 5;

    bool Allow(std::int64_t sessionId) {
        std::shared_ptr<Bucket> b;
        {
            std::lock_guard<std::mutex> lk(mapMtx_);
            auto it = buckets_.find(sessionId);
            if (it == buckets_.end()) {
                auto sp = std::make_shared<Bucket>();   // 제자리 생성(mutex 는 복사/이동 불가)
                sp->windowStartMs = NowMs();
                it = buckets_.emplace(sessionId, std::move(sp)).first;
            }
            b = it->second;                  // shared_ptr 복사 → 참조 무효화 무관
        }
        std::lock_guard<std::mutex> lk(b->mtx);   // 버킷별 임계구역
        std::int64_t now = NowMs();
        if (now - b->windowStartMs >= 1000) { b->windowStartMs = now; b->count = 0; }
        if (b->count >= kLimitPerSec) return false;
        b->count++;
        return true;
    }

private:
    struct Bucket {
        int          count = 0;
        std::int64_t windowStartMs = 0;
        std::mutex   mtx;
    };
    static std::int64_t NowMs() {
        using namespace std::chrono;
        return duration_cast<milliseconds>(steady_clock::now().time_since_epoch()).count();
    }
    std::mutex mapMtx_;
    std::unordered_map<std::int64_t, std::shared_ptr<Bucket>> buckets_;
};

포인트

맵은 짧은 락으로 보호하고 shared_ptr<Bucket> 을 꺼내 참조 무효화/수명 문제 제거.
버킷별 뮤텍스로 검사+증가+윈도전이 원자화(세션 간 경합 분리).
steady_clock 으로 시계 점프 무력화. (Bucket 에 mutex 가 있어 복사 불가 → shared_ptr/ emplace 로 관리)

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

lock-free 토큰 버킷: std::atomic<std::int64_t> 에 (토큰<<32 | lastRefill) 같이 상태를 묶어 CAS 갱신. 락 제거, 검증 난이도↑.
슬라이딩 윈도: 고정 윈도 경계 버스트(2N) 회피. 메모리/계산 비용.
버킷 만료 GC: 끊긴 세션 버킷 정리(누수 방지).
분산: 멀티 게이트웨이면 Redis 원자 INCR+TTL 또는 sticky 라우팅.

면접 포인트 (예상 질문)

unordered_map 에서 Bucket& 를 반환해 들고 있는 게 왜 위험한가? (동시 삽입/리해시, 무효화)
system_clock vs steady_clock — 레이트리밋엔 무엇을, 왜?
lock-free 토큰버킷을 CAS 로 구현할 때 ABA/보충 계산을 어떻게 처리하나?

구문 검증: g++ -std=c++17 -fsyntax-only problem.cpp 통과(문제 코드/수정안 모두).

← 문제로 돌아가기