ConcurrentHashMap은 어떻게 동시성 문제를 해결할까?

개요

현재 진행중인 프로젝트에서 유저의 정보를 저장하는 저장소를 In-Memory Database로 간단하게 구현해야 할 필요가 생겨 구현을 진행하던 도중 유저의 정보를 저장하기에 적합한 자료구조로 Map을 선정했습니다.

그 중 자바에서 제공해주는 Map 인터페이스의 구현체로 HashMap과 ConcurrentHashMap이 있습니다

그 중 저는 현재 진행중인 프로젝트는 웹 프로젝트이고, 동시성 문제가 발생할 수 있기 때문에, 이런 상황에 사용하기 적합하다고 알려져 있는 ConCurrentHashMap을 사용하기로 했습니다. 하지만 현재 ConCurrentHashMap이 어떤 방식으로 동작하는지, 어떤 장 단점이 있는지 제대로 알지 못하기에 이번 기회에 사용을 하기에 앞서 학습을 해보고자 글을 작성합니다.

 

ConcurrentHashMap VS Collections.synchronizedMap()

앞서 설명한 동시성 문제로 인한 데이터 불일치를 해결하기 위해서 선택할 수 있는 자료구조로 ConcurrentHashMap과 synchronizedMap()의 두가지가 있습니다.

public int size() {
            synchronized (mutex) {return m.size();}
        }
        public boolean isEmpty() {
            synchronized (mutex) {return m.isEmpty();}
        }
        public boolean containsKey(Object key) {
            synchronized (mutex) {return m.containsKey(key);}
        }
        public boolean containsValue(Object value) {
            synchronized (mutex) {return m.containsValue(value);}
        }
        public V get(Object key) {
            synchronized (mutex) {return m.get(key);}
        }

        public V put(K key, V value) {
            synchronized (mutex) {return m.put(key, value);}
        }
        public V remove(Object key) {
            synchronized (mutex) {return m.remove(key);}
        }
        public void putAll(Map<? extends K, ? extends V> map) {
            synchronized (mutex) {m.putAll(map);}
        }
        public void clear() {
            synchronized (mutex) {m.clear();}
        }

synchronizedMap의 내부 구현은 위와 같이 단순히 synchronized 키워드를 붙여주는 방식으로 처리되어 있습니다. 이러한 방식은 공유 자원에 접근할 수 있는 쓰레드를 한번에 한 쓰레드만 접근 가능하도록 제한합니다.

또한 순차적으로 연산을 실행하는 것과 다를게 없기 때문에, Thread-Safety를 보장하면서 동시 스레드가 공유 자원에서 작동할 수 있도록 하는 것이기 때문에 해당 자료구조를 사용하고자 하는 목적에 맞지 않습니다.

 

ConcurrentHashMap

ConcurrentHashMap의 내부 데이터 구조의 일부인 Segment는 Map에 데이터를 추가하거나 업데이트 하는 동안에만 lock을 실행합니다.

더 자세히 설명하자면 ConcurrentHashMap은 하나의 공유 자원을 여러개의 Segment로 나누고 각 Segment별로 다른 락을 거는 기법을 적용 했습니다. 이러한 기법을 lock striping이라고 합니다.

Lock Striping

Lock Striping은 여러 버킷 또는 Stripes에서 잠금이 발생하는 기술로, 버킷에 접근하면 해당 버킷만 lock을 하고 다른 전체 데이터 구조는 잠그지 않는 방식 입니다.

Lock Striping 방식의 예제 그림

Lock Striping 방식을 구현하기 위한 몇 가지 방법이 있습니다.

1. 작업당 잠금(lock per task)을 사용하여, 작업 간 동시성을 극대화할 수 있습니다. 이는 작업 당 잠금을 생성해야 하기 때문에 메모리 설치 공간이 더 많이 필요합니다.
2. 모든 작업에 단일 잠금(single lock)을 사용합니다. 이 방식을 사용하면 모든 작업에 단일 잠금을 사용함으로써, 메모리를 적게 사용할 수 있지만 동시성 상황에서 성능이 저하됩니다.

그럼 ConcurrentHashMap은 어떻게 동시성 문제를 해결하는지 그에 대해 좀 더 자세히 알아보기 전에 간략히 몇가지 주요 개념들을 알아보겠습니다.

 

ConcurrentHashMap : concurrentHashMap은 Map에 대한 동시 접근을 허용합니다. Segement(ConcurrentHashMap의 내부 데이터 구조 입니다)라는 맵의 일부는 맵을 추가하거나 업데이트하는 동안에만 lock을 겁니다. 그렇다는 것은 ConcurrentHashMap을 사용하면 읽기 연산시에는 불필요한 lock 연산이 실행되지 않기때문에 읽기 시 성능이 향상된다는 장점이 있습니다.

Concurrency-Level : 동시에 업데이트 될 가능성이 있는 스레드의 예상되는 갯수를 정의합니다. 이 Concurrency-Level을 정의함으로서, 더 많은 스레드를 수용할 수 있도록 만들어 줍니다.

Load-Factor : Map의 크기 조정을 제어하는 데 사용되는 임계값입니다.

 

ConcurrentHashMap은 Segment의 수로 나뉩니다. 현재 설명을 위해 사용할 예제에서는 초기화시 기본값을 32로 사용했다고 가정하겠습니다.

ConcurrentHashMap의 내부에는 Segment라는 final class가 있습니다. ConcurrentHashMap은 내부적으로 크기가 32인 세그먼트로 분할되어 있다고 말할 수 있습니다. 이 말은 한 번에 최대 32개의 스레드가 작동할 수 있다는 뜻이기도 합니다. 또한 각 스레드가 high-concurrency 상황 동안 각 세그먼트에서 작동할 수 있고 최대 32개의 스레드가 작동할 수 있음을 의미하며, 이말은 단순히 ConcurrentHashMap의 각각의 버킷을 보호하기 위해 32개의 개별적인 잠금(lock)을 유지한다는 뜻입니다.

/** ConcurrentHashMap 클래스 내부 Segment 클래스의 주요 역할 **/
protected static final class Segment {
  protected int count;

  protected synchronized int getCount() {
    return this.count;
  }

  protected synchronized void synch() {}
}

/** Segment 배열 선언 **/
public final Segment[] segments = new Segment[32];

ConcurrentHashMap 또한 Map 자료구조 입니다. Map은 내부에 Entry클래스를 가지며 Entry클래스는 키-값 쌍으로 이루어진 데이터를 저장하는 자료 구조입니다.

 

static class Entry implements Map.Entry {      
   protected final Object key;
   protected volatile Object value;
   protected final int hash;
   protected final Entry next;

   Entry(int hash, Object key, Object value, Entry next) {

     this.value = value;
     this.hash = hash;
     this.key = key;
     this.next = next;
   }

   //....
 }

ConcurrentHashMap 클래스는 아래와 같이 정의된 Entry 클래스 유형으로 정의된 배열을 가집니다.

protected transient Entry[] table; 이 Entry 배열은 ConcurrentHashMap 클래스의 인스턴스를 만들 때 다음과 같은 기분 생성자를 사용해 초기화 합니다.

 

public ConcurrentHashMap(int initialCapacity, float loadFactor) {

 
  int cap = getCapacity();
  this.table = newTable(cap); 
}

protected Entry[] newTable(int capacity) {
  this.threshold = ((int)(capacity * this.loadFactor / 32.0F) + 1);
  return new Entry[capacity];
}

threshold(임계값)은 위 코드에서 크기 조정을 위해 초기화 되고 있습니다.

 

ConcurrentHashMap의 Insert(Put) 연산

put 메소드는 다음과 같이 두개의 Object를 사용합니다.

put(Object key, Object value)

put 메소드는 처음으로 다음과 같은 해시 키를 계산하는 연산을 진행 합니다 :

int hashVal = hash(key);

static int hash(Object x) {
  int h = x.hashCode();
  return (h << 7) - h + (h >>> 9) + (h >>> 17);
}

hashVal을 얻은 후 다음과 같이 Segment를 결정할 수 있습니다 :

Segment seg = segments[(hash & 0x1F)];

현재 설명하는 모든것이 동시성에 관한 내용입니다. 그렇기 때문에 아래 코드와 같이 세그먼트에서 동기화된 블럭이 필요합니다.

synchronized (seg) {
  // 추가할 코드

  int index = hash & table.length - 1; 
  Entry first = table[index];
  for (Entry e = first; e != null; e = e.next) {
    if ((e.hash == hash) && (eq(key, e.key))) { // 이미 키가 존재하는 경우 값을 업데이트 합니다
      Object oldValue = e.value;
      e.value = value;
      return oldValue;
    }
  }

  Entry newEntry = new Entry(hash, key, value, first); // new entry, 다시 말해 이 키는 맵에 존재하지 않는 다는 것을 의미합니다.
  table[index] = newEntry; 
}

ConcurrentHashMap의 Read(Get) 연산

ConcurrentHashMap에서 Element를 가져올 때 키를 전달하고 키를 토대로 해시를 계산해 값을 리턴받습니다.

public Object get(Object key){
  //some  code..

  int index = hash & table.length - 1;  //키를 통해 인덱스를  얻어냅니다
  Entry first = table[index];         
  for (Entry e = first; e != null; e = e.next) {
    if ((e.hash == hash) && (eq(key, e.key))) {
      Object value = e.value;
      if (value == null) {
        break;
      }
      return value;
    }
  }
  //some  code here
}

위 코드에서 알 수 있듯이 ConcurrentHashMap에서는 요소를 가져올 때 잠금(lock)을 설정할 필요가 없어, 읽기 연산의 성능이 보장됩니다.

ConcurrentHashMap의 Delete(Remove)연산

remove 연산은 기본적으로 하나의 인수(key)를 받거나, 두개의 인수(key와 value)를 받습니다.

Object remove(Object key);

boolean remove(Object key, Object value);

그럼 이 remove 연산이 내부적으로 어떻게 동작하는지 알아보겠습니다. remove(Object key) 메소드는 null 을 remove(Object key, Object value) 의 value 값으로 전달해 remove(Object key) 메소드를 호출합니다. Segment에서 Element를 제거할 예정이므로 해당 Segment에 대한 잠금이 필요합니다.

Object remove(Object key, Object value) {

  Segment seg = segments[(hash & 0x1F)]; //key에 대해 계산한 hash값

  synchronized (seg) {
    Entry[] tab = this.table;    
    int index = hash & tab.length - 1; 
    Entry first = tab[index]; 

    Entry e = first;
    while(true) {
      if ((e.hash == hash) && (eq(key, e.key))) {
        break;
      }
      e = e.next;
    }
    Object oldValue = e.value;
    Entry head = e.next;
    for (Entry p = first; p != e; p = p.next) {
      head = new Entry(p.hash, p.key, p.value, head);
    }
    table[index] = head;
    seg.count -= 1;
  }
  return oldValue;
}