Kim Geon Woo Unreal Client

전송 지연 시간 (Latency)

• 두 기기 간에 데이터를 최소량 전송할 때 걸리는 시간 (ms)
• 반응을 시작하기까지의 지연 시간
• 네트워크 품질을 결정하는 기준 3가지 중 하나
  • Packet Loss : 패킷을 잃어버린 것 (데이터 유실)
  • 전송 속도 : 두 기기간에 초당 전송될 수 있는 최대 데이터 양 (BitPerSecond, Bytes/Second)
  • 전송 지연 시간 (Latency)

Latency Vs Throughput

• Lateny : 1개의 요청/작업에 걸리는 시간 (ms)
• Throughput : 일정 시간동안 처리 가능한 요청의 수
  • 초당 100개의 요청 처리 가능

Latency Vs Response Time vs Processing Time

• Lateny : 반응이 시작되기까지의 지연
• Response Time : 요청 전체가 완료될 때까지의 시간 (Latency 포함)
• Processing Time : 실제 로직 수행에 걸린 시간 (I/O 제외)

Latency 종류

• Network : 네트워크를 통해 데이터가 왕복에 걸리는 시간
  • 클라이언트 ↔ 서버간의 Ping
• Input : 사용자 입력이 시스템 반응으로 이어지기까지의 시간
  • 마우스 클릭 후 반응 시간
• Render : GPU가 렌더링을 시작하고 끝낼 때까지의 걸리는 시간
  • 프레임 렌더링 시간
• Application : 어플리케이션에서 내부 로직 수행에 걸리는 시간
  • DB 쿼리, 알고리즘 실행 시간
• Disk : 디스크에서 데이터를 읽고 쓰는데 걸리는 시간
  • SSD vs HDD 응답 시간
• Audio : 입력 음성이 스피커로 출력되는데까지의 걸리는 시간
  • 보이스 채팅 딜레이

Latency 발생 원인

• 네트워크 : 거리, 라우터/스위치 수, DNS 지연, 방화벽 검사
• 하드웨어 : 디스크 접근, CPU 컨텍스트 스위칭, 캐시 미스
• 소프트웨어 : 알고리즘 복잡도, 동기화, 불필요한 I/O
• 스레드/락 : Mutex, Semaphore, Deadlock 대기 시간
• GC : 언어 런타임의 메모리 정리로 인한 멈춤]

측정 방법

• End - to - End
  • 클라이언트로부터 응답까지 전체 흐름 측정
  • Start Timer → 요청 전송 → 응답 수신 → Stop Timer
  • Latency - Stop - Start
• BreakDown (구간별)
  • 네트워크 전송 시간
    • Ping, Traceroute
  • 서버 처리 시간
    • 백엔드 로그, APM 툴 (New Relic, Datadog 등)
  • DB 지연
    • 쿼리 프로파일링 (EXPLAIN, QueryTime)
  • 렌더링 지연
    • GPU 프로파일러, 프레임 분석

메트릭 지표

• Average : 전체 요청의 평균 지연 시간
• P95/P99 : 95%, 99% 요청이 이 시간 이내에 응답됨
• Max : 가장 오래 걸린 요청 시간
• Jitter(지터) : Latency의 변동 폭 (불규칙성)

Latency 최적화 전략

• 네트워크 : CDN, 지역별 서버 배치, 압축
• 서버 처리 : 비동기 처리, 캐싱, 경량화
• DB : 쿼리 튜닝, 인덱싱, 메모리 캐시 (Redis)
• 멀티 스레딩 : 락 최소화, 스레드 풀 사용
• 게임/렌더링 : Prediction, Interpolation, Frame Delay 최소화
• 분산 시스템 : RPC 최적화, 데이터 파티셔닝, Circuit Breaker 패턴 등

Latency 공식

• L = λ × W
• L : 시스템 내 평균 요청 수 (Queue 길이)
• λ : 요청 도착률 (Throughput)
• W : 평균 응답 시간 (Latency)

Latency 측정법 : 라운드 트립 레이턴시 (Round Trip Latency)

1. 기기 A에서 기기 B에 패킷 전송
2. 기기 B는 이를 수신, A에 패킷 전송
3. A에서 1번과정의 시간과 현재 시간의 차이를 구하여 2로 나눈다.
   1. 현재시간 - (A →B전송시간 / B→A 전송시간)

IOCP 내 패킷 유실시 UDP 및 TPC에서의 현상

• UDP : 패킷 유실 발생시 데이터 그램 자체가 유실
  • Ex) 1만 바이트의 데이터그램을 UDP로 전송시 1300바이트의 패킷으로 분할하여 전송
  • 해당 패킷 1개를 유실시 1만바이트 데이터그램 전체 유실
  • 레이턴시 : 네트워크 기기의 레이턴시
• TCP 패킷 유실 발생시 유실된 패킷에 대한 Ack가 도착하지 않는다.
  • Ack가 올때까지 대기 후 오지않으면 다시 패킷을 전송
  • 3Hand - 4Hand Shake
  • 지연시간이 발생하지만, 데이터를 송/수신 처리한다. (신뢰성)
  • 레이턴시 : 네트워크 기기(라우터,스위치 등) 레이턴시 + 패킷 유실률 * 재전송 대기 시간

언리얼내의 추측항법을 통한 레이턴시

• 추측항법
  • 다른 캐릭터의 위치 정보를 이미 지난 약간의 시간만큼 예측 하는 것
  • 상대방 움직임을 어느정도 예상해서 그 위치로 갈 수 있게 보정시키는 방법
  • 두 기기간의 레이턴시를 파악하는 것
  • 언리얼의 CharacterMovementComponent는 이동 예측 + 보정을 자동으로 수행한다. (추측 항법)
    • 높은 핑 환경에서의 예측이 어긋나고 서버 보정시 순간이동처럼 보이는 현상

RPC (Remote Procedure Call)의 레이턴시 특성

• Client → Server (RPC Server)
  • 입력 전달, 행동 요청
  • 클라이언트 → 서버 RTT만큼 지연
• Server → Client (RPC Client)
  • 피드백, 애니메이션 트리거
  • 지연 + 클라이언트 처리 순서 문제
• Multicast (RPC Multicast)
  • 모든 클라이언트에 일괄 동기화
  • RTT * N, 부하 높음

레이턴시 최소화 방법

1. 불필요한 TCP 대신 UDP로 통신하기
   1. 언리얼 엔진은 이미 다른 방식의 IOCP 형태로 통신중 (엔진 내부적으로 최적화가 진행되어 있음)
   2. 언리얼의 Reliable → UnReliable 리팩토링
2. 가급적 적은 수의 패킷 전송
3. 클라이언트와 서버 간 통신과 클라이언트끼리 직접 통신을 섞어쓰기
   1. C/S네트워킹 + P2P 네트워킹

출처 및 참고내역

멀티플레이어 게임 프로그래밍(도서) - https://www.yes24.com/product/goods/38868446

게임 서버 프로그래밍 교과서(도서) - https://www.yes24.com/Product/Goods/71768958

개요

코딩테스트 집중 시간 중 튜터님께서 언급하셨던 네트워크 효율적인 트래픽 관리를 위해 사용하는 알고리즘 중 하나입니다.

Rate Limiting 방식을 사용하여 클라이언트의 요청에 대한 서버의 트래픽 제어 방법이 있으며,

이번 포스팅에서는 Rate Limiting 관련 알고리즘 중 Token Bucket 알고리즘에 대해 알아보겠습니다.

Rate Limiting / Limiter

• Rate Limit
  • 일정 시간동안 허용되는 요청의 수 (1분에 100개 요청 가능 등.)
• Rate Limiter
  • 실제로 적용하고 감시하는 소프트웨어 또는 기능 (알고리즘 등)
• Rate Limiting
  • 클라이언트의 요청 빈도를 제한하는 행위.
  • 개념, 정책 및 적용 등까지 포함된 언어

정의

• API의 요청 제한 혹은 트래픽 제어를 위해 나온 개념
• 네트워크 또는 서비스의 자원을 보호, 안정성을 유지하기위한 메커니즘

특징

• 서버 API가 과도한 요청으로부터 다운되거나 성능이 저하되는것을 방지
• 악의적인 공격 (DDos, API Abuse) 차단
• 서비스 자원을 공평하게 분배
• 사용량 기반 요금제 또는 제한을 관리하기 위함 (OpenAI API, TwitterAPI 등)

장점

• 백엔드 서버의 부하를 방지함으로써 자원을 보호한다.
• DDos 또는 Abuse User등에 대한 차단 가능. 보안 강화
• 고정 사용량 유저의 성능 안정화 (Qos 유지)
• 유료/무료 사용자 제한 구현 가능 (요금제 차별화)
• Token Bucket 등으로 일시적인 과부화 흡수 가능

단점

• 한계 도달시 정당한 사용자도 차단될 가능성이 있음.
• 슬라이딩 윈도우, 토큰 버킷등의 구현복잡성 존재
• 다중 서버 환경에서는 상태 공유가 필요하다.
  • 분산 환경에서의 동기화 어려움
• IP변경, API Key 재발급 등을 통한 우회
  • 별도의 IP 또는 API Key재발급시 검증을 통한 시간당 요청 횟수 제한 설정 필요

게임 서버에서의 Rate Limit 적용 예시

• 로그인 서버
  • DDos 및 접속 폭주 방지
  • 우선순위 기반 대기열 (Queue)를 사용
  • IP/계정별 로그인 시도 횟수 제한
  • 토큰 발급 지연
    • 요청이 허용된 경우에만 세션 토큰 발급
    • Ex) ID, PW등의 DB내 데이터 비교를 통한 요청
• 매치메이킹 요청
  • 유저가 자주 매칭을 요청하거나 취소하는 경우
  • 일정시간 내 매칭 요청/취소 횟수 제한시 패널티 부여
  • 매칭 서버 부하 감소 및 매칭 시스템 안정화 가능

Token Bocket

정의

• 일정한 속도로 토큰을 생성하여 버킷에 저장
• 요청마다 해당 토큰을 소비하여 요청을 허용하거나 제한하는 방식
  • 토큰이 있는 경우 - 응답시 요청 수락 응답
  • 토큰이 없는 경우 - 응답시 요청 거절 또는 지연 응답

Bucket (Structure)

• 일정 개수의 토큰을 담는 저장소 (Bucket)
• 버킷이 담을 수 있는 최대 토큰수 보유 (BucketCapacity)
• 일정 주기로 토큰이 생성되는 속도 보유 (TokenRate)
• 요청을 처리할 수 있는 권한 단위 (Token)

동작 원리

1. 시스템이 실행되는 경우, 토큰이 일정 속도로 버킷에 추가된다.
2. 요청이 들어오는 경우
   1. 토큰이 있는 경우 - 토큰을 1개 소비, 요청 허용
   2. 토큰이 없는 경우 - 요청을 거절 또는 큐에 삽입하여 지연 처리
3. 버킷은 최대 용량 이상의 토큰을 저장하지 못한다.
   1. 넘치는 토큰은 버려진다.
4. 토큰은 시간에 따라 누적이 가능하여 버스트 트래픽에도 일정량 허용이 가능하다.

특징

• 시간 기반 제어 : 초당 몇개 요청 허용 등 시간 단위로 요청 제어
• 버스트 허용 가능 : 짧은 시간동안 요청이 들어와도 처리 가능
• 유연성 : 속도제한 + 버스트 처리 모두 지원 가능
• 간단한 구조 : 상태는 현재 토큰수를 통한 관리 가능

장점

• 버스트 처리 지원 : 갑작스러운 트래픽에도 탄력적
• 정상 유저 보호 : 어뷰징 유저 요청차단 가능
• Qos 제어 : 초당 요청 수 제한 설정으로 서비스 품질 유지
• 간단한 구현 : 알고리즘 자체가 직관적
• 유연한 정책 설정 : 시간, 사용자, IP 단위 등 적용 가능

단점

• 정확한 간격 제어 어려움
  • 일정 요청 간격 유지에는 부적합하다.
  • 이러한 경우에는 Leaky Bucket이 적합하다.
• 상태 관리 필요
  • 사용자별 토큰 상태 저장이 필요하다. (Redis, 메모리 등)
• 분산 시스템에서 복잡성 증가
  • 여러서버 간 토큰 상태 동기화 필요
• 토큰 생성 타이밍 중요
  • 정확한 생성 주기 관리가 되어있지 않은 경우 예상과 다른 결과 발생

기존 구조 - Login Sequence

1. 사용자가 로그인 요청 전송
2. API 서버는 요청을 바로 Auth Service로 전달
3. 인증 성공 여부를 클라이언트에 응답

• 요청이 몰릴 경우 서버가 모두 처리 시도 → CPU/RAM 과부화
• 특정 유저가 수백번 로그인 요청(ABuse)시 서버 자원 소모
• DDos 및 정상 사용자 구분 불가
• 비동기 큐 처리 시도시 모든 요청을 다 수신해야함

토큰 버킷 적용 - Login Sequence

1. 유저 로그인 요청
2. Rate Limiter 적용 - 유저 IP 기준 토큰 존재 여부 확인
   1. 있다 → 토큰 소비 → API 서버 전달
   2. 없다 → 대기열 안내
3. 로그인 성공/실패 응답

기존에 알고있던 Bearer Token과는 다름.

Bearer Token

• 인증 토큰
• 사용자 인정/인가 처리
• 클라이언트 → 서버 요청 헤더에서 사용
• Auth 서버 로그인 성공시 발급
• 클라이언트에서 보관
• 이 요청을 누가 보낸것인가? → Bearer Token

Token Bucket

• 요청 수 제어시 사용
• 요청 횟수 제한을 통한 서버 안정화
• 서버에 저장
• 요청을 지금 받아도 되는가? → Token Bucket

출처 및 참고내역

https://www.geeksforgeeks.org/token-bucket-algorithm/

A* Algorithm

• 다익스트라를 확장해 만든 경로 탐색 알고리즘
• 휴리스틱(Heuristic) 기반의 경로 탐색 알고리즘
• F(n) = H(n) + G(n) (최종 가중치 = 목적지까지의 거리 + 이동 비용)
  • F(n) : 출발 노드에서 도착 노드까지 경로의 전체 가중치 합
  • H(n) : 현재 노드에서 목적지 노드까지의 추정 경로 가중치 (휴리스틱 기반)
  • G(n) : 출발 노드에서 현재 노드까지의 경로 가중치
  • F(n)이 가장 최소가 되는 노드를 다음 탐색 노드로 지정한다. (우선순위 큐를 사용)
• 휴리스틱 함수를 통해 어떻게 설계하는지에 따라 알고리즘의 성능이 달라진다.
  • 유클리드 거리 (Euclidean Distance): 대각선 포함, 자유롭게 모든 방향으로 이동 가능
  • 맨해튼 거리 (Manhattan Distance) : 가로/세로 방향으로만 이동 가능
• 언리얼 에서는 NavMesh를 사용하지 못하는 경우 (점프, 사다리 등의 거리 계산)에 사용할 수 있다.
• 또는 NavMesh는 런타임 환경에서의 길찾기 거리 갱신이 어려운 경우 등에 사용할 수 있다.
• 게임 내 자동 길찾기의 경우 미니맵 UI에 보여지는 최단거리 표시 등

※ 휴리스틱 : 최선의 방향을 추정하는 방식 또는 기준.

유클리드 VS 맨해튼 VS BFS

BFS : 파란 선

맨해튼 : 녹색 선

유클리드 : 빨간 선

다익스트라(Dijkstra) Vs A* (A Star)

다익스트라 :

목표 지점까지의 모든 방향을 균일하게 탐색하며, 최단 경로를 보장하지만 비 효율적인 탐색 범위가 발생할 수 있습니다.

A*

목표까지의 거리를 계산하고, 그 거리를 노드의 전체 가중치에 더하여 F(n) = H(n) + G(n)으로 바꾸는 추가적인 휴리스틱 방식을 통해 이를 수행합니다.

실제 비용과 경험적 추측을 혼합하여 가장 낮은 F(n)값을 기준으로 노드를 탐색합니다.

출처 및 참고내역

https://devforum.roblox.com/t/how-does-apathfinding-work/271356/2

https://www.geeksforgeeks.org/a-search-algorithm/