Java 동시성 자료구조는 어떻게 락을 줄이는가

Java 동시성 컬렉션들은 저마다 다른 방식으로 같은 질문에 답한다 — “어떻게 하면 락을 덜 잡고도 스레드 안전성을 보장할 수 있는가?” ConcurrentHashMap은 버킷 단위 CAS로, CopyOnWriteArrayList는 불변 스냅샷으로, LinkedBlockingQueue는 락을 둘로 쪼개서 각자의 방식으로 이 문제를 푼다. 이 설계들이 공유하는 철학은 무엇인가?

전역 락에서 국소 락으로

Java 7의 ConcurrentHashMap은 16개 Segment를 두었다. 각 세그먼트가 독립적인 ReentrantLock을 가지므로, 서로 다른 세그먼트에 접근하는 스레드들은 병렬로 실행된다. 하지만 동시성 수준이 세그먼트 수에 묶여 있고, 균일하게 분산되지 않으면 특정 세그먼트에 경합이 몰린다.

Java 8은 세그먼트를 버렸다. 대신 버킷 레벨 synchronized와 CAS를 조합했다.

// 빈 버킷 삽입: CAS (락 없음)
if (CAS(table[hash], null, new Node(k, v))) {
    // 성공, 완료
}

// 기존 버킷 수정: 버킷 head에만 synchronized
synchronized (head) {
    // 연결 리스트 또는 TreeBin 조작
}

빈 버킷에 첫 노드를 삽입할 때는 락이 전혀 없다. 충돌이 없는 버킷들은 완전히 병렬로 동작한다. 동시성 수준의 상한이 세그먼트 수(16)에서 버킷 수(수천~수만)로 뛰어오른다.

volatile과 happens-before — 락 없는 읽기의 근거

ConcurrentHashMap.get()은 락을 잡지 않는다. 이게 어떻게 안전한가?

Node의 val과 next가 volatile로 선언되어 있다. 새 노드를 버킷에 연결하는 순간은 volatile 쓰기이고, get()이 버킷을 읽는 순간은 volatile 읽기다. Java 메모리 모델에서 volatile 쓰기는 이후의 모든 volatile 읽기와 happens-before 관계를 형성한다. 부분 초기화된 노드를 읽을 수 없는 이유가 여기 있다.

단, 삽입이 진행 중이라면 그 새 값은 아직 연결 전이므로 get()이 보지 못할 수 있다. 이것이 “weakly consistent”의 의미다 — 일관성은 보장하되, 최신성은 보장하지 않는다.

CopyOnWriteArrayList는 같은 원리를 다른 방식으로 구현한다. 쓰기 시 배열 전체를 복사해 새 참조를 volatile로 교체한다. 읽기 스레드가 volatile로 배열 참조를 읽는 순간, 그 배열 객체는 이미 완성된 상태다. 진행 중인 쓰기는 새 배열을 아직 교체하지 않았을 뿐, 기존 배열을 건드리지 않는다.

// COWAL.add() 핵심
lock.lock();
try {
    Object[] newElements = Arrays.copyOf(elements, len + 1);
    newElements[len] = e;
    setArray(newElements);  // volatile 쓰기 — 원자적 참조 교체
} finally { lock.unlock(); }

// 읽기 스레드: 락 없음
Object[] snapshot = getArray();  // volatile 읽기
return (E) snapshot[index];

iterator()가 생성 시점의 배열 참조를 저장한다. 이후 add()가 새 배열을 만들어도, 이전 배열 객체 자체는 변경되지 않는다. iterator가 들고 있는 스냅샷은 불변이다.

락을 쪼개는 두 번째 방법 — 분리 락

ArrayBlockingQueue는 put과 take가 하나의 ReentrantLock을 공유한다. 생산자와 소비자가 교대로 락을 잡는다. 고처리량 시나리오에서 병목이 된다.

LinkedBlockingQueue는 락을 둘로 쪼갠다.

final ReentrantLock putLock  = new ReentrantLock();
final ReentrantLock takeLock = new ReentrantLock();
private final AtomicInteger count = new AtomicInteger();

생산자들은 putLock으로, 소비자들은 takeLock으로 각자 직렬화된다. put과 take는 동시에 실행될 수 있다. 두 락에서 동시에 접근하는 count는 AtomicInteger로 처리한다.

Lock-Free 삭제 — 마커 노드

ConcurrentSkipListMap은 Red-Black Tree 대신 스킵 리스트를 선택했다. 이유는 구조적이다. 트리 삽입/삭제는 회전을 수반하고, 회전은 여러 포인터를 동시에 수정한다. CAS 한두 번으로 원자적으로 처리하기 어렵다. 스킵 리스트의 삽입/삭제는 연결 리스트 수준의 포인터 조작으로 귀결된다.

삭제에는 마커 노드 기법을 쓴다.

삭제 1단계 (논리적 삭제):
  ... → [node] → [successor] → ...
  CAS(node.next, successor, new MarkerNode(successor))
  ... → [node] → [MARKER] → [successor] → ...

삭제 2단계 (물리적 제거):
  CAS(predecessor.next, node, successor)
  ... → [predecessor] → [successor] → ...

마커 노드가 삽입된 이후에는 다른 스레드의 node.next CAS가 모두 실패한다. “이 노드는 삭제 중”이라는 신호가 마커 자체로 표현된다. 2단계가 실패해도 다른 스레드가 탐색 중 마커를 만나면 자동으로 물리 제거를 돕는다(Helping).

단일 스레드 환경에서는 TreeMap이 ConcurrentSkipListMap보다 약 20% 빠르다. 레이어 관리 오버헤드와 더 많은 메모리 때문이다. 그러나 8스레드 환경에서는 Collections.synchronizedMap(new TreeMap<>())이 단일 스레드 대비 처리량이 78% 감소하는 반면, ConcurrentSkipListMap은 거의 선형으로 확장된다.

정리

• ConcurrentHashMap Java 8은 빈 버킷 삽입에 CAS, 기존 버킷 수정에 버킷 단위 synchronized를 써서 동시성 수준을 버킷 수까지 끌어올렸다.
• 락 없는 읽기의 안전성은 volatile + happens-before가 보장한다. weakly consistent는 일관성을 포기하지 않되 최신성을 보장하지 않겠다는 선택이다.
• LinkedBlockingQueue는 putLock과 takeLock을 분리해 생산자-소비자를 동시에 실행한다. count는 AtomicInteger로 두 락 경계를 넘나든다.
• ConcurrentSkipListMap은 마커 노드로 Lock-Free 삭제를 구현한다. Red-Black Tree가 아닌 스킵 리스트를 선택한 이유는 CAS 친화적인 구조 때문이다.

다음 글에서는 Java 21의 Virtual Thread가 이 전통적인 동시성 모델과 어떻게 공존하는지, 그리고 BlockingQueue 기반 코드가 Virtual Thread 위에서 어떻게 동작하는지 추적한다.