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

난이도: 상

1. 거친 잠금 vs 세밀한 잠금 vs 락 스트라이핑

• 거친 잠금: 자료구조 전체를 락 하나로 보호. 구현이 단순하고 정확하지만, 모든 연산이 그 락을 직렬화해 코어가 늘어도 확장되지 않는다(경합 지점 하나).
• 세밀한 잠금: 자료구조를 여러 부분(버킷/노드)으로 나눠 부분마다 락. 서로 다른 부분을 건드리는 연산은 병렬 진행. 대신 데드락(락 순서)·복잡도·락 객체 메모리 비용 증가.
• 락 스트라이핑: 세밀한 잠금의 실용적 형태. 버킷마다 락을 두는 대신 N개의 스트라이프 락을 두고 hash(key) % N 으로 매핑한다. 서로 다른 스트라이프에 속한 키는 병렬 처리.
  • 스트라이프 수: 대략 예상 동시 스레드 수의 몇 배(코어 수 기반) 정도. 너무 적으면 경합, 너무 많으면 메모리·리사이즈 비용. .NET ConcurrentDictionary 기본 동시성 수준도 이 아이디어다.

2. 동시 해시맵의 어려운 연산

• (a) 리사이즈/리해시: 부하율이 임계를 넘으면 버킷 배열을 키우고 모든 항목을 재배치 해야 하는데, 그 사이 다른 스레드의 읽기/쓰기와 충돌한다. 해법: 리사이즈 시 모든 스트라이프 락 획득(또는 협조적 점진 리사이즈, 예: Java CHM 의 forwarding node 로 옛/새 테이블을 함께 운영하며 조금씩 이전). 이 때문에 리사이즈는 비싸고, 초기 용량을 잘 잡으면 회피할 수 있다.
• (b) 원자적 size(): 전역 카운터 하나면 모든 쓰기가 그 카운터에서 경합한다. 그래서 스트라이프별 카운터로 쪼개고 Count 는 이들을 합산한다(순간적으로는 근사). 정확한 스냅샷 Count 는 모든 스트라이프를 잠가야 해서 비싸다 — 대개 "대략적"이 실용적.
• (c) 전체 순회: 순회 도중에도 삽입/삭제가 일어난다. 완전한 일관 스냅샷을 원하면 전체를 잠그거나(비쌈) COW 스냅샷을 떠야 한다. 대부분의 동시 맵 열거자는 약한 일관성 (weakly consistent): 순회 시작 시점 이후의 변경을 볼 수도/못 볼 수도 있고 예외는 안 던진다. "정확한 순간 스냅샷"이 필요하면 별도 비용을 지불해야 한다.

3. ConcurrentDictionary / ConcurrentHashMap

• .NET ConcurrentDictionary: 버킷을 여러 락(스트라이프)으로 보호. 읽기(TryGetValue) 는 대개 락 없이(볼라타일 읽기 + 불변 노드) 진행하고, 쓰기만 해당 스트라이프 락을 잡음.
• Java ConcurrentHashMap(8+): 버킷 헤드에 CAS 로 삽입, 충돌 체인/트리는 synchronized 로 버킷 단위 보호, 점진 리사이즈, 병렬 count.
• GetOrAdd 팩토리 중복 호출: 키가 없을 때 값 팩토리를 호출하는데, 두 스레드가 동시에 없음을 보고 각자 팩토리를 실행할 수 있다. 최종적으로 하나만 저장되지만 팩토리는 두 번 실행된다(부작용 있으면 위험). 대응: 팩토리를 부작용 없게 만들거나, 값에 Lazy<T> 를 넣어(GetOrAdd(key, k => new Lazy<T>(...)) 후 .Value) 실제 생성이 한 번만 일어나게 한다.

3-1. 동시 스킵리스트

• 스킵리스트는 확률적 다층 연결 리스트로 정렬을 유지한다. 회전(rebalancing)이 없고 삽입/삭제가 지역적 포인터 CAS 로 끝나 락프리/세밀 잠금 구현이 균형 트리보다 쉽다 (트리는 회전이 넓은 구조 변경이라 동시성이 어렵다). 그래서 정렬된 동시 자료구조(범위 질의·랭킹 스캔)에 적합하다(예: ConcurrentSkipListMap). Redis 의 Sorted Set 도 스킵 리스트 기반.

4. 동시 자료구조 사용의 함정

• 복합 연산 비원자성: if (!map.Contains(k)) map.Add(k, v); 는 각 호출이 원자적이어도 둘 사이가 원자적이지 않다. 원자적 의도는 GetOrAdd/AddOrUpdate/CAS 같은 단일 원자 연산으로 표현해야 한다.
• 스냅샷/열거자 시점: Count, Keys, 열거자는 특정 순간의 근사이거나 약한 일관성. 이를 기반으로 다시 판단하면 그새 상태가 바뀐다(TOCTOU).
• 조합의 비원자성: 스레드 안전 컬렉션 두 개를 함께 갱신한다고 두 갱신이 원자적이지 않다. 두 구조에 걸친 불변식은 별도 동기화가 필요하다.

5. 게임서버의 핫 자료구조(읽기 폭주/쓰기 드묾)

• RCU / COW(카피-온-라이트): 읽기는 원자적 스냅샷 포인터를 무락으로 읽고, 쓰기는 복사·수정 후 교체. 읽기 지연이 최소. 대신 쓰기 복사 비용·회수 유예(reclamation) 관리 필요(→ hazard pointer/epoch). 쓰기가 드물면 최적.
• 샤딩(파티셔닝): 키 공간을 샤드로 나눠 샤드별 독립 락/스레드. 존/플레이어ID 기반 샤딩이 게임서버에 자연스럽다. 크로스-샤드 연산은 비원자성 주의.
• 읽기 무락 동시 맵(ConcurrentDictionary 등): 구현이 쉽고 읽기 대부분 무락. 정확한 size/순회가 필요 없다면 실용적.
• 트레이드오프 요약: COW=읽기 최상·쓰기·메모리 비용, 샤딩=병렬성·크로스샤드 복잡성, 동시 맵=범용·정확 집계 약함. 접근 패턴(읽기/쓰기 비율, 정렬/범위 질의 필요, 순회 일관성 요구)으로 결정한다.

요약

전역 락은 정확하나 확장 불가. 락 스트라이핑/세밀 잠금으로 병렬성을 얻되 리사이즈·정확한 size·일관 순회는 비싸다는 점을 이해해야 한다. 동시 맵은 각 연산만 원자적이므로 복합 연산은 GetOrAdd 등 단일 원자 연산으로 표현하고, 읽기 폭주 핫 자료구조는 COW/샤딩/무락 읽기 중 접근 패턴에 맞춰 고른다.