문제 21 — 동시 자료구조 설계: 락 스트라이핑·세밀한 잠금과 동시 해시맵/스킵리스트

배경

게임서버는 "온라인 플레이어 맵", "존별 엔티티 인덱스", "세션 레지스트리" 같은 공유 자료구조를 매 틱 수많은 스레드가 동시에 읽고 쓴다. 전역 락 하나로 감싸면 정확하지만 확장되지 않는다. 아래 물음에 답하라.

질문

1. 거친 잠금(coarse-grained lock) vs 세밀한 잠금(fine-grained lock) vs 락 스트라이핑(lock striping) 을 설명하라. 락 스트라이핑이 동시 해시맵에서 어떻게 처리량을 올리는가? 스트라이프 수는 어떻게 정하는가?

2. 동시 해시맵을 설계할 때 발생하는 어려운 연산들을 설명하라: (a) 리사이즈/리해시(resize) 중의 동시 접근, (b) 원자적 size() 집계, (c) 전체 순회(iteration)와 일관성. 왜 정확한 Count/스냅샷 순회가 비싼가?

3. .NET 의 ConcurrentDictionary 와 Java 의 ConcurrentHashMap 이 쓰는 기법(버킷/스트라이프 락, CAS, 볼륨 있는 노드)을 개괄하고, GetOrAdd 의 팩토리가 중복 호출될 수 있는 이유와 대응을 설명하라.

3-1. 동시 스킵리스트(concurrent skip list) 가 균형 트리보다 락프리/동시성 친화적인 이유를 설명하라(정렬된 동시 자료구조가 필요한 랭킹/범위 질의 맥락에서).

4. 동시 자료구조를 쓸 때 흔한 함정을 설명하라: "각 연산은 원자적이지만 복합 연산 (check-then-act)은 원자적이지 않다", 반환된 스냅샷/열거자의 시점 문제, 개별 스레드 안전 컬렉션을 조합했을 때의 비원자성.

5. 게임서버 관점에서 "온라인 플레이어 맵" 같은 핫 자료구조를 설계할 때, 읽기 폭주/쓰기 드묾 패턴이라면 어떤 선택지(RCU/COW, 샤딩, 읽기 무락)가 있고 트레이드오프는 무엇인가?