Java 코드로 보는 Lock Striping 과 ConcurrentHashMap, CAS (Compare-And-Swap)

 

Lock Striping

• 스레드 동기화는 공유하는 데이터에 대해 데이터 일관성을 보장하기 위해 사용된다.
• 그러나 스레드 동기화는 성능에 영향을 미치기 때문에 동기화를 최소한으로 유지하면서 스레드 안정성을 보장하는 것이 중요하다.
• Lock Striping 은 이를 위한 방법 중 하나로 여러 개의 락을 사용하는 대신, 락을 분할하여 동시에 여러 스레드가 접근할 수 있도록 한다.
  • e.g. ConcurrentHashMap에서 특정 노드에 잠금을 거는 것
• Lock Striping 은 스레드 경합을 줄이고 락의 사용 빈도를 줄이기 때문에 성능을 향상시킬 수 있다.
• ConcurrentHashMap 등에서 사용하고 있다.
• Cf. 락 분할 (Lock spilitting)은 하나의 클래스에서 기능적으로 락을 분리해서 사용하는 것으로 읽기 전용 락, 쓰기 전용 락으로 분리하는 것 처럼 사용하는 것을 말한다. 대표적으로 ReentrantLock 이 있다.

아래에서 ConcurrentHashMap 의 구현부를 보면서 자세히 설명한다.

 

ConcurrentHashMap

 

java 8 이전의 ConcurrentHashMap

• java 8 이전의 ConcurrentHashMap 은 Segment 배열과 ReentrantLock 을 사용한 락 스트라이핑 기법을 사용하여 구현되었다.

public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
    implements ConcurrentMap<K,V>, Serializable {
    // ...

    /**
     * 세그먼트는 해시 테이블의 특수 버전
     * 락킹을 쉽게 하기 위해 세그먼트 배열로 각개 노드에 대한 locking 을 하게 된다.
     */
    static final class Segment<K, V> extends ReentrantLock implements Serializable {
        
				// ...

        final V put(K key, int hash, V value, boolean onlyIfAbsent) {
            lock(); // lock을 획득
            try {
                // ...
            } finally {
                unlock(); // lock을 해제
            }
        }

        // ...

        final V remove(Object key, int hash, Object value) {
            lock(); // lock을 획득
            try {
                // ...
            } finally {
                unlock(); // lock을 해제
            }
        }
        // ...
    }
    // ...
}

• ConcurrentHashMap 은 내부에 이너클래스로 Segment를 가지고 있고, Segment는 Lock을 ReentrantLock을 사용하여 구현한다.
• Segment 는 ConcurrentHashMap의 각각의 해시 버킷을 담당하며 Segment 내부에는 HashEntry 라는 연결리스트로 구현된 배열을 가지고 있다.
• 따라서 put 메서드를 호출하면, Segment 내부의 HashEntry 에 새로운 요소를 추가하게 된다.
• 그러므로, Segment는 각 HashEntry 에 해당하는 Lock을 가지고 있고, 각 스레드(디폴트로 16개가 선언되어 있다.)는 동시성을 고려하여 접근할 수 있게 된다.

 

Java 8 부터의 ConcurrentHashMap

• Java 8 부터는 내부적으로 Segment 대신 Node 배열과 CAS(Compare And Swap) 연산을 사용한 구현체로 변경되었다.

public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
    implements ConcurrentMap<K,V>, Serializable {

    // ...

    /* ---------------- Nodes -------------- */
    static final class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        volatile V val;
        volatile Node<K,V> next;

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

        // ...
    }

    // ...

    /* ---------------- Table element access -------------- */
    @SuppressWarnings("unchecked")
    static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
        return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
    }
    
    static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
        U.putObjectRelease(tab, ((long)i << ASHIFT) + ABASE, v);
    }

    // ...
}

• 노드는 ConcurrentHashMap의 각 해시 버킷에 들어있게 되고, 키-벨류 쌍으로 저장한다.
• 마찬가지로 연결리스트로 들어가게 된다.
• 단 위의 ConcurrentHashMap 과 다른 점은 각 노드에 접근하게 될 때 CAS 연산에 성공하면 노드에 접근할 수 있게 된다.

 

CAS (Compare-And-Swap)

• CAS는 동시에 여러 스레드가 접근해도 안전하게 데이터를 수정할 수 있도록 하는 기술이다.
  • 하드웨어 레벨(기계어)로 지원된다.
• atomic operation 중 하나로, 변수의 값을 변경할 때 사용된다.
• CAS 연산은 변수의 주소, 변수의 기존값, 변수의 새로운 값을 설정하기 위한 값으로 인자를 갖는다.
• 다음과 같이 동작한다.

1. 변수의 현재 값을 읽어온다.
2. 읽어온 값과 파라미터로 전달된 기존값이 같은지 비교한다.
3. 값이 같다면 변수의 값을 파라미터로 전달된 새로운 값으로 설정한다.
4. 값이 다르다면, 아무 작업도 수행하지 않는다.

• 위의 과정은 원자적인 작업으로 수행되므로 스레드 간의 경합 없이 안전하게 수행되고 lock 을 사용하지 않아 lock의 비용이 들지 않기 때문에 때문에 빠르게 수행할 수 있다
• Atomic 클래스 (AtomicInteger, AtomicLong, AtomicReference 등) 에서도 사용된다.
• Cf. ConcurrentHashMap 의 해시 테이블은 volatile로 선언되어 있어 메인 메모리에 올라가 있다.