ConcurrentHashMap

HashMap

• Map 인터페이스를 구현한 클래스 중 성능이 제일 좋음
• key, value에 null을 입력할 수 있음
• Multi-Thread 환경에서 동시에 수정을 시도하는 경우 예상치 못한 결과가 발생할 수 있음
• resize() 함수를 통해 새로운 배열(newTab)을 만들어 copy 하는 방식으로 리사이징

 

ConcurrentHashMap

• HashMap을 thread-safe 하도록 만든 클래스
• key, value에 null을 허용하지 않음
• Thread-safe 보장
• HashTable과 synchorined map보다 더 나은 성능을 내는데, 이는 map의 일부에만 Lock을 걸기 때문! 
  • 읽기(검색) 작업에는 여러 Thread가 동시에 읽을 수 있지만,
  • 쓰기 작업에는 특정 세그먼트 or 버킷에 대한 Lock을 사용
    → 버킷당 하나의 Lock을 가지고 있어, 같은 버킷만 아니라면 Lock을 기다릴 필요가 없음
    → 여러 Thread에서 ConcurrentHashMap 객체에 동시에 데이터를 삽입, 참조하더라도 그 데이터가 다른 세그먼트에 위치하면 서로 Lock을 얻기 위해 경쟁하지 않음
• 기존 배열(table) 새로운 배열(nextTable) 로 버킷을 하나씩 전송(transfer) 하는 방식으로 리사이징

 

 

ConcurrentHashMap의 쓰기 작업 동기화 처리 방식

1) 새로운 Node가 들어갈 배열의 인덱스가 비어있는 경우

• Lock을 사용하지 않고 `Compare and Swap`을 이용하여 새로운 Node를 해시 버킷에 삽입 (원자성 보장)
• Node를 담고 있는 volatile 변수에 접근(=tabAt)하여 해당 Node와 기대값(null)을 비교(Compare) 후 새로운 Node를 넣는다(Swap)(=casTabAt)

2) 이미 기존 Node가 있는 경우

• Node가 존재하는 해시 버킷 객체(f)에 `synchronized`(Lock)를 사용해 하나의 Thread만 접근할 수 있도록 제어
• 서로 다른 Thread가 같은 해시 버킷에 접근할 때만 해당 블록이 잠기게 된다
• synchorinzed 안의 로직은 HashMap과 비슷..!
  • 동일한 key면 Node를 새로 바꾸고,
  • 해시충돌인 경우 Seperate Chaning or TreeNode에 추가하고, 
  • `TREEFITY_THRESHOLD`값에 따라 (Separate Chaining에서 사용하는)LinkedList를 Tree로 바꾼다
• 부분적인 Lock을 사용함으로써 Thread 간 경합을 최소화하고 동시성을 보장하는 안전한 업데이트를 지원!

 

(+) Compare and Swap

Multi-Thread 환경에서 CPU는 메인 메모리에서 변수를 참조하지 않고 CPU의 캐시 영역에서 메모리를 참조하게 된다. 이 때 메인 메모리에 저장된 값(메인 Thread에 저장된 값)과 CPU 캐시에 저장된 값(현재 Thread에 저장된 값)을 비교하여 일치하면 새로운 값으로 교체되고, 일치하지 않으면 실패하고 재시도하는 알고리즘.

 

(+) volatile 변수

Java 변수를 Main Memory에 저장하겠다라는 것을 명시.

변수의 값을 Read할 때마다 CPU cache에 저장된 값이 아닌 Main Memory에서 읽고, 변수의 값을 Write할 때 또한 Main Memory에까지 작성한다. volatile 키워드는 오직 한개의 Thread에서 쓰기 읽기 작업을 할 때 그리고 다른 Thread는 읽기 작업만 할 때 안정성을 보장한다.

 

 

 

참고 링크 리스트

https://pplenty.tistory.com/17

[java] ConcurrentHashMap 동기화 방식

https://applefarm.tistory.com/100

자바 ConcurrentHashmap

https://nesoy.github.io/articles/2018-06/Java-volatile

Java volatile이란?

https://d2.naver.com/helloworld/831311