Thread-Safe 함을 보장하면서도 높은 성능을 보장하는 HashMap 이다.
즉 해쉬맵을 쓰레드 세이프하도록 만든 클래스.
하지만 HashMap과는 다르게 key, value에 null을 허용하지 않는다.
ConcurrentHashMap은 concurrent multi-trhead환경에서 안정적으로 동작하고, HashTable과 synchorined map보다 더 나은 성능을 가지고 있다.
이유는 ConcurrentHashmap은 map의 일부에만 lock을 거는 반면 앞의 두가지는 map 전체에 lock을 건다
HashMap, Hashtable과 동일한 스펙을 제공한다.
그러나 차이점은 모든 작업이 쓰레드 세이프 임에도 불구하고 검색 작업에는 Lock이 수반되지 않으며 전체 테이블을 잠궈야 하는 액션도 없다.
ConcurrentHashMap의 검색 작업이 Lock이 이뤄지지 않으며 갱신 작업과 동시에 수행될 수 있다.
Concurrent(동시성, 가능한 많이 클라이언트의 요청을 처리할 수 있도록 하는 것.)
method 레벨에서 쓰레드세이프를 보장한다.
그러나 메소드 레벨에서 synchornized 키워드를 이용하면 Lock의 매개로 활용객체가 바로 객체 바로 자신이 된다.(this)
이는 전체적인 성능 저하를 가져온다. 어느 한 순간에 Lock이 설정된 어떤 메소드가 하나의 쓰레드만이 진입할 수 있게 된다.
누군가 get으로 Lock을 획득 중이면, put도 진입할 수가 없다.
ConcurrentHashmap은 이미 노드가 존재하는 경우에 서로 다른 스레드가 해시 버킷에 접근할 때만 해당 블록이 잠긴다.
해쉬 테이블과 다르게 메소드에 synchronized 키워드가 선언되어 있지 않다.
put 함수는 크게 2가지 경우로 나눌 수 있다.
새로운 노드가 들어갈 배열의 1)인덱스가 비어있는 경우와, 2)이미 기존 노드가 있는 경우
/**
* Returns the value to which the specified key is mapped,
* or {@code null} if this map contains no mapping for the key.
*
* <p>More formally, if this map contains a mapping from a key
* {@code k} to a value {@code v} such that {@code key.equals(k)},
* then this method returns {@code v}; otherwise it returns
* {@code null}. (There can be at most one such mapping.)
*
* @throws NullPointerException if the specified key is null
*/
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
int h = spread(key.hashCode());
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
} /**
* Maps the specified key to the specified value in this table.
* Neither the key nor the value can be null.
*
* <p>The value can be retrieved by calling the {@code get} method
* with a key that is equal to the original key.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with {@code key}, or
* {@code null} if there was no mapping for {@code key}
* @throws NullPointerException if the specified key or value is null
*/
public V put(K key, V value) {
return putVal(key, value, false);
}
/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
// 빈 버킷에 노드를 삽입하는 경우 lock을 사용하지 않고 Compare and Swap을 이용해 새로운 노드를 해시 버킷에 삽입한다.
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
tab = initTable();
// 1) 새로운 노드가 들어갈 배열의 인덱스가 비어있는 경우
// 새로운 노드를 삽입하기 위해, 해당 버킷을 가져와 비어있는지 확인한다.
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
// 비어있다면 다시 Node를 담고 있는 volatile 변수에 접근하여 Node와 기댓값을 비교하여 같으면
// 새로운 노드를 생성하고 아니면 다시 for문으로 돌아간다.
// 여러 쓰레드에서 쓰기 작업을 할 수 있기 때문에 CAS알고리즘으로 한번더 안전장치를 거친다.
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
// 이미 노드가 존재하는 경우는 노드가 존재하는 버킷 객체를 이용해 하나의 스레드만 접근할 수 있도록 한다.
// 서로 다른 스레드가 같은 해시 버킷에 접근할 때만 해당 블록이 잠기게 된다.
// synchorinzed 안의 로직은 HashMap과 비슷한 로직이다. 동일한 키면 노드를 새로 바꾸고
// 해시충돌인 경우 SEperate Chaning에 추가 하거나 TreeNode에 추가하고, TREEFITY_THRESHOLD값에 따라
// 링크드리스트를 트리로 바꾼다.
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
// 새로운 노드로 교체된다.
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
// Seperate Chaining에 추가도니다.
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
// 트리에 추가한다.
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}
놀랍게도 Compare and Swap을 위한 코드가 한줄로 끝난다.
원자성을 보장하기 위해 가시성문제를 막기 위해 CAS를 이용하여 비교하여 맞는 경우에만 새로운 노드를 넣는다.
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> boolean casTabAt(Node<K,V>[] tab, int i,
Node<K,V> c, Node<K,V> v) {
return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}위 두 함수에서 발러틀 변수에 두번 접근하는 동안 원자성을 보장하기 위해 기대되는 값과 비교하여 일치하는 경우에만 새로운 노드를 넣는다.
(진짜 비어있을 때만 변수를 넣는다. (한 쓰레드가 Read만 하니까, )
Atomic 변수란
원자성 : 소스코드가 한번에 실행된다는 것을 보장해주는 것
원자성을 보장하는 변수
멀티스레드 환경에서 동기화 문제를 synchronized 키워드를 이용하거나, Atomic, volatile 이 세가지 키워드로 해결한다.
syncrhonized는 특정 Thread가 해당 블럭 전체를 락을 걸기 때문에 다른 쓰레드는 아무런 작업을 하지 못하여 비효율적이다.
그래서 nonblocking하면서 동기화 문제를 해결하기 위한 방법이다.
Compare and Swap
변수의 값을 변경하기 전에 기존값이 내가 예상하던 값인지 비교하여 같을 경우에만 할당하는 방법
자바에서 제공하는 Atomic 타입은 CAS를 하드웨어의 도움을 받아 한번에 단 하나의 쓰레드만 변수의 값을 변경할 수 있도록 제공하고 있다.
멀티쓰레드 환경에서 CPU는 메인 메모리에서 변수를 참조하지 않고 CPU의 캐시 영역에서 메모리를 참조하게 된다. 이 때 메인 메모리에 저자된 값과 CPU 캐시에 저장된 값이 다른 경우가 있는데 이럴떄 사용하는 알고리즘이다.
현재 쓰레드에 저장된 값과, 메인 쓰레드에 저장된 값을 비교하여, 일치하면 새로운 값으로 교체되고, 일치하지 않으면 실패하고 재시도를 함.
volatile이란
자바의 변수를 메인 메모리에 저장하겠다고 명시하는것
CPU의 캐쉬에 저장하는 것이 아니라 메인 메모리에 작성하는 것이다.
볼라타일 변수를 사용하지 않는 멀티쓰레드 앱에서는 태스크를 수행하는 동안 성능 향상을 위해 메인메모리에서 읽은 변수값을
CPU Cache에 저장하게 된다.
만약에 멀티 쓰레드 환경에서 쓰레드가 변수 값을 읽어올 때 CPU Cache에 저장된 값이 다르기 때문에 변수 값 불일치 문제 발생함
volatile은 변수의 가시성 문제를 해결하기 위함이다. CPU 캐시가 아닌 메모리에서 값을 참조함.
volatile 키워드는 오직 한개의 쓰레드에서 쓰기 읽기 작업을 할 때 그리고 다른 쓰레드는 읽기 작업만 할 때 안정성을 보장함
여러 쓰레드가 read, write 하는 상황이면 synchorinzed를 통해 변수의 원자성을 보장해야함
메인 메모리의 비용이 더 크기 때문에 변수 값 일치를 보장해야만 하는 경우에 볼라타일을 사용하는 것이 좋음
원자 단위 연산의 이해
이 원자단위의 연산이 수행중에는 다른 Thread에 의해 컨트롤 되는 타 CPU의 개입이 있을 수 없는 최소 단위의 연산이라고 이해하면 된다.
여기에 멀티쓰레드를 개입시켜보면 각 명령어 수행 사이에는 다른 쓰레드의 공유메모리의 접근이 가능하여 값이 꼬이는 현상이 생긴다.
하나의 원자 연산이 이뤄지는 동안 이 연산은 다른 쓰레드의 간섭을 받을 수 없다.
최근의 CPU들은 atomic hardware primitives를 제공한다.
기존의 값과 다른 경우는 다른 쓰레드가 들어가서 값을 바꿔놨다는 것이다. 이럴 경우에는 false를 반환한다. 그 이후에는 개발자 보고 알아서 하라는 의미이다. 일반적으로 loop를 구성하여 다시 기존 값을 읽고 같은 시도를 한다.
Loop를 돌면서 내 값을 반영해주겠냐고 계속 물어본다고 해도 블락킹보다 성능적으로 우수하다. 이와 같은 연산을 CAS라고 한다.
모든 단일 연산의 변수의 핵심은 이부분이다. 이를 이용하여 자료구조를 안전하게 구현하는 것을 lock-free 알고리즘이라고 부른다.
ConcurrentHashMap 생성자
생성자에서는 초기 해시테이블 사이즈를 결정한다.
DEFAULT_CAPACITY는 16이다
생성자에서 직접 해시 테이블을 생성하지는 않는다.
해시테이블 생성은 첫번째 노드가 삽입될 때 생성된다. lailzy initailzed
생성자의 주요 파라미터 3가지가 있다.
initailCapactiy : 초기 용량 결정, 구현은 지정된 로드팩터가 주어지면 크기 조정을 수행한다.
loadFactor : Hashmap의 테이블 밀도와 동일하다. 하지만 ConcurrentHashMa에서는 초기 테이블의 크기를 설정하기 위한 용도로만 쓰인다.
volatile 키워드가 붙어 있는 객체는 CPU 캐시가 아닌 메인메모리에서 값을 참조해온다. 그렇다면 굳이 CAS알고리즘을 적용하지 않아도 된다고 생각할 수 있지만, volatile은 오직 한개의 쓰레드에서 쓰기 작업을 할때, 그리고 다른 쓰레드들은 읽기 작업만 할 때 안정성을 보장하는 것이다. 하지만 위에서는 여러 쓰레드에서 읽기/쓰기 작업을 병행하기 때문에 CAS알고리즘이라는 2중의 안정장치를 설치한 것이다.
(CAS는 여러 쓰레드가 쓰기 작업을 할 때 쓰레드세이프를 보장한다.)
요약 : ConcurrentHashmap은 Hashtable의 비효율을 개선하기 위해
트리에 새로운 노드를 넣을 때, 정말 그 값이 비어있는지 여부를 확인하는 경우 CAS 알고리즘을 통해 원자성을 보장하여 쓰레드세이프를 보장한다.
여러 쓰레드가 Read, Write하면 Synchorinzed를 쓰면 되지만, 한 쓰레드가 Read, Write를 하고, 다른 쓰레드가 Read만 하는 상황에서는 Synchroinzed를 할 필요 없이 volatile 변수를 통해 동기화 하는게 효율적이다 라는 아이디어를 통해 개선한 케이스.
'개발 > Spring' 카테고리의 다른 글
| 서블릿이란 (0) | 2021.04.11 |
|---|---|
| 데이터베이스 (0) | 2021.04.11 |
| 자바 Hashtable, HashMap (0) | 2021.04.11 |
| JSP의 동작 원리 (0) | 2021.04.11 |
| 프로세스, 쓰레드란(자바, OS) (0) | 2021.04.11 |
