ConcurrentSkipListMap의 핵심 아키텍처

Java의 ConcurrentSkipListMap은 키의 정렬 상태를 유지하면서 높은 수준의 동시성을 보장하는 Map 구현체입니다. 이 클래스는 SkipList(도약 목록) 자료구조를 기반으로 하며, TreeMap과 유사하게 자연 순서 또는 사용자 정의 비교자를 통한 정렬을 지원합니다. 가장 큰 특징은 synchronized나 ReentrantLock 같은 배타적 락을 사용하지 않고, CAS(Compare-And-Swap)와 스핀(Spin) 루프를 통한 락 프리(Lock-Free) 방식으로 동시성을 제어한다는 점입니다.

기반 자료구조: SkipList(도약 목록)

동시성 제어 방식을 이해하기 위해서는 SkipList의 구조를 먼저 파악해야 합니다. SkipList는 여러 계층으로 구성된 연결 리스트로, 일반 단일 연결 리스트에 '인덱스' 개념을 도입하여 탐색, 삽입, 삭제의 시간 복잡도를 O(log n)으로 최적화한 구조입니다.

SkipList의 계층적 구조

• 최하위 계층 (Level 1): 모든 데이터 노드를 포함하는 기본적인 정렬된 단일 연결 리스트입니다.
• 상위 계층 (Level 2 이상): 하위 계층 노드 중 일부를 확률적으로 선별하여 연결한 인덱스 역할을 수행합니다. 계층이 올라갈수록 노드의 수는 기하급수적으로 줄어듭니다.
• 헤드 노드 (Head): 각 계층의 시작점을 나타내며, 전체 구조의 진입점 역할을 합니다.

트리 기반 구조(예: 레드-블랙 트리)와 비교할 때, SkipList는 노드의 삽입 및 삭제 시 포인터 변경 작업이 상대적으로 단순합니다. 레드-블랙 트리의 회전(Rotation) 연산은 동시 환경에서 원자성을 보장하기 어렵지만, SkipList는 인접 노드의 참조값만 CAS로 교체하면 되므로 락 프리 구현에 매우 유리합니다.

Lock-Free 동시성 제어 메커니즘

ConcurrentSkipListMap은 모든 상태 변경 작업을 CAS 연산과 스핀 루프로 처리합니다. 이를 통해 스레드 블로킹을 최소화하고 컨텍스트 스위칭 오버헤드를 줄입니다.

1. 노드 삽입 프로세스와 동시성 보장

데이터 삽입 시 다음과 같은 단계를 거치며, 각 단계에서 동시성 충돌을 해결합니다.

1. 위치 탐색: 최상위 계층의 헤드 노드부터 시작하여 아래로 내려가며 목표 키가 위치할 정확한 하위 계층의 선행 노드(Predecessor)를 찾습니다. 이 과정에서 락을 획득하지 않으며, 다른 스레드에 의해 구조가 변경되었음이 감지되면 처음부터 다시 탐색합니다.
2. CAS를 통한 노드 연결: 새로운 노드를 생성한 후, 선행 노드의 next 포인터를 CAS 연산으로 원자적으로 업데이트하여 새 노드를 연결합니다.
3. 계층 승격 (Promotion): 삽입된 노드는 확률에 따라 상위 계층으로 승격됩니다. 이 과정 역시 각 계층별로 CAS를 통해 포인터를 연결하며, 중간에 CAS가 실패하더라도 최하위 계층의 데이터 무결성은 유지되므로 전체 작업을 중단하지 않습니다.

// 삽입 연산의 내부 로직 단순화 (개념적 구현)
private V executePut(K targetKey, V newValue, boolean replaceOnly) {
    int keyHash = targetKey.hashCode();
    Node<K, V> predecessor, successor;
    
    for (;;) { // CAS 성공 시까지 스핀 루프
        // 선행 노드와 후행 노드 탐색
        if (locatePredecessor(targetKey, keyHash, predecessor, successor)) {
            // 이미 존재하는 키인 경우: 값 원자적 업데이트
            if (successor.compareAndSetValue(successor.val, newValue)) {
                return successor.val;
            }
        } else {
            // 새로운 키인 경우: 노드 생성 및 연결
            Node<K, V> freshNode = new Node<>(keyHash, targetKey, newValue);
            // 선행 노드의 next 참조를 CAS로 변경
            if (predecessor.compareAndSetNext(successor, freshNode)) {
                // 확률적 계층 승격 처리
                elevateNodeLevel(freshNode);
                return null;
            }
        }
        // CAS 실패 시 다른 스레드가 구조를 변경한 것이므로 루프 재진입
    }
}

2. 삭제 연산과 논리적 삭제(Logical Deletion)

동시 환경에서 물리적으로 노드를 즉시 제거하면 연결 리스트가 끊어지는 문제가 발생할 수 있습니다. 이를 방지하기 위해 ConcurrentSkipListMap은 '마크 포 데스(Mark-for-Death)' 방식을 사용합니다. 삭제 요청이 들어오면 노드의 값을 null로 변경하거나 삭제 플래그를 설정하는 CAS 연산을 수행합니다. 이후 탐색 작업에서는 이 플래그가 설정된 노드를 건너뛰며, 백그라운드 또는 후속 작업에서 물리적으로 연결을 해제합니다.

3. 읽기 연산과 약한 일관성(Weak Consistency)

get() 메서드나 반복자(Iterator)를 통한 읽기 작업은 완전히 락 프리로 동작합니다. 노드의 참조와 값은 volatile로 선언되어 있어 최신 가시성을 보장합니다. 다만, 읽기 작업 도중 다른 스레드가 데이터를 수정할 수 있으므로, 반복자는 생성 시점의 스냅샷이 아닌 실시간 상태를 반영하되 예외를 발생시키지 않는 약한 일관성을 제공합니다.

ConcurrentHashMap과의 특성 비교

동시성 환경에서의 동작 검증

다중 스레드 환경에서 데이터의 무결성과 정렬 상태가 올바르게 유지되는지 확인하기 위한 테스트 코드입니다.

import java.util.concurrent.ConcurrentSkipListMap;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicInteger;

public class SkipListConcurrencyTest {
    private static final int WORKER_THREADS = 16;
    private static final int TASKS_PER_THREAD = 5000;

    public static void main(String[] args) throws InterruptedException {
        ConcurrentSkipListMap<Integer, String> concurrentMap = new ConcurrentSkipListMap<>();
        ExecutorService executor = Executors.newFixedThreadPool(WORKER_THREADS);
        AtomicInteger successCount = new AtomicInteger(0);

        long startTime = System.nanoTime();

        for (int t = 0; t < WORKER_THREADS; t++) {
            final int threadOffset = t;
            executor.submit(() -> {
                for (int i = 0; i < TASKS_PER_THREAD; i++) {
                    int key = threadOffset * TASKS_PER_THREAD + i;
                    concurrentMap.put(key, "data-" + key);
                    successCount.incrementAndGet();
                }
            });
        }

        executor.shutdown();
        executor.awaitTermination(10, TimeUnit.SECONDS);
        long durationMs = (System.nanoTime() - startTime) / 1_000_000;

        System.out.println("총 삽입된 엔트리 수: " + concurrentMap.size());
        System.out.println("성공한 작업 수: " + successCount.get());
        System.out.println("최소 키 값: " + concurrentMap.firstKey());
        System.out.println("최대 키 값: " + concurrentMap.lastKey());
        System.out.println("총 소요 시간: " + durationMs + " ms");
    }
}

위 코드는 16개의 스레드가 동시에 80,000개의 데이터를 삽입하며, 완료 후 Map의 크기와 키의 정렬 상태(최소/최대 값)를 검증합니다. 배타적 락을 사용하지 않음에도 불구하고 CAS 기반의 구조 덕분에 데이터 유실 없이 완벽한 정렬 상태를 유지하는 것을 확인할 수 있습니다.