ConcurrentHashMap 1.7의 설계 핵심: Segment

JDK 1.7 버전의 ConcurrentHashMap은 고가용성과 동시성을 확보하기 위해 '세그먼트(Segment)'라는 개념을 도입했습니다. 이는 데이터 영역을 여러 개의 작은 단위로 쪼개고, 각 단위마다 독립적인 잠금을 적용하는 분할 잠금(Lock Striping) 기법을 기반으로 합니다.

• Segment: ReentrantLock을 상속받아 구현된 객체로, 내부적으로 해시 테이블의 일부를 관리하며 해당 영역에 대한 잠금 역할을 수행합니다.
• HashEntry: 실제 키-값 쌍을 저장하는 노드이며, 체이닝(Chaining) 방식을 통해 충돌을 해결합니다.
• 이중 해싱: 데이터를 찾기 위해 두 번의 해시 연산을 수행합니다. 첫 번째 해시는 어떤 Segment에 속할지 결정하고, 두 번째 해시는 해당 Segment 내부의 어떤 버킷에 위치할지 결정합니다.

주요 내부 구성 요소

ConcurrentHashMap의 핵심은 전체 맵을 작은 테이블인 Segment들로 나누는 것입니다. 이를 통해 쓰기 작업 시 전체 맵을 잠그지 않고 특정 Segment만 잠금으로써 병렬 처리 효율을 극대화합니다.

static final class MapEntry<K,V> {
    final int hash;
    final K key;
    volatile V val;
    volatile MapEntry<K,V> next;

    MapEntry(int hash, K key, V val, MapEntry<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.val = val;
        this.next = next;
    }
}

static final class Partition<K,V> extends ReentrantLock implements Serializable {
    transient volatile MapEntry<K,V>[] bucketTable;
    transient int entryCount;
    transient int modificationCount;
    transient int resizeThreshold;
    final float fillFactor;

    Partition(float lf, int threshold, MapEntry<K,V>[] tab) {
        this.fillFactor = lf;
        this.resizeThreshold = threshold;
        this.bucketTable = tab;
    }
}

데이터 삽입 과정 (Put Operation)

데이터 삽입 시에는 대상이 되는 Segment를 찾아 잠금을 획득한 후 작업을 수행합니다. 다른 Segment에 대한 접근은 잠금에 영향을 받지 않으므로 동시 쓰기가 가능합니다.

final V putData(K key, int hash, V value, boolean onlyIfAbsent) {
    // 잠금 획득 시도 또는 스캔 후 잠금
    MapEntry<K,V> node = tryLock() ? null : scanAndLockForPut(key, hash, value);
    V previousValue = null;
    try {
        MapEntry<K,V>[] table = bucketTable;
        int targetIdx = (table.length - 1) & hash;
        MapEntry<K,V> firstNode = table[targetIdx];
        
        for (MapEntry<K,V> e = firstNode; ; ) {
            if (e != null) {
                K k;
                if ((k = e.key) == key || (e.hash == hash && key.equals(k))) {
                    previousValue = e.val;
                    if (!onlyIfAbsent) {
                        e.val = value;
                        ++modificationCount;
                    }
                    break;
                }
                e = e.next;
            } else {
                if (node != null) {
                    node.next = firstNode;
                } else {
                    node = new MapEntry<K,V>(hash, key, value, firstNode);
                }
                int newSize = entryCount + 1;
                if (newSize > resizeThreshold && table.length < MAXIMUM_CAPACITY) {
                    rehash(node);
                } else {
                    table[targetIdx] = node;
                }
                ++modificationCount;
                entryCount = newSize;
                break;
            }
        }
    } finally {
        unlock();
    }
    return previousValue;
}

리해싱(Rehash) 및 확장

Segment 내부의 테이블이 일정 부하 수준(Load Factor)을 초과하면 리해싱이 발생합니다. 이는 해당 Segment 내부에서만 독립적으로 이루어집니다.

• 노드 이동: 버킷 내에 단일 노드만 존재하는 경우 새로운 인덱스로 즉시 이동시킵니다.
• 최적화된 전송(LastRun): 체인 내에서 같은 새로운 인덱스로 이동하게 될 연속된 후속 노드들을 찾아 한꺼번에 이동시킴으로써 불필요한 노드 생성을 최소화합니다.
• 불변성 활용: HashEntry의 일부 필드(key, hash, next 등)가 final로 설계된 버전의 경우, 삭제 시 해당 노드 이전의 노드들을 복제하여 다시 연결하는 방식을 취하기도 합니다.

private void transfer(MapEntry<K,V> newNode) {
    MapEntry<K,V>[] oldTab = bucketTable;
    int oldLen = oldTab.length;
    int newLen = oldLen << 1;
    resizeThreshold = (int)(newLen * fillFactor);
    MapEntry<K,V>[] newTab = (MapEntry<K,V>[]) new MapEntry[newLen];
    int mask = newLen - 1;

    for (int i = 0; i < oldLen; i++) {
        MapEntry<K,V> head = oldTab[i];
        if (head != null) {
            MapEntry<K,V> nextNode = head.next;
            int idx = head.hash & mask;
            if (nextNode == null) {
                newTab[idx] = head;
            } else {
                MapEntry<K,V> lastRun = head;
                int lastIdx = idx;
                for (MapEntry<K,V> last = nextNode; last != null; last = last.next) {
                    int k = last.hash & mask;
                    if (k != lastIdx) {
                        lastIdx = k;
                        lastRun = last;
                    }
                }
                newTab[lastIdx] = lastRun;
                for (MapEntry<K,V> p = head; p != lastRun; p = p.next) {
                    int h = p.hash;
                    int k = h & mask;
                    newTab[k] = new MapEntry<K,V>(h, p.key, p.val, newTab[k]);
                }
            }
        }
    }
    int newNodeIdx = newNode.hash & mask;
    newNode.next = newTab[newNodeIdx];
    newTab[newNodeIdx] = newNode;
    bucketTable = newTab;
}

조회 작업 (Get Operation)

get 연산은 잠금을 사용하지 않습니다. HashEntry의 value와 next 필드가 volatile로 선언되어 있어 최신 데이터를 안전하게 읽을 수 있기 때문입니다. 이는 읽기 성능이 매우 중요한 고병렬 환경에서 큰 장점으로 작용합니다.