기업에서 요구했던 사항들 중 하나는 멀티 쓰레드로 운용되는 서비스에서 thread safety한 자료구조를 사용하는 것이었습니다. key value 형식으로 데이터를 저장할 때 java에서는 주로 HashMap을 많이 사용하게 되는데, 이 자료구조는 멀티 쓰레드 환경에서는 동시성 문제(concurrency issues) 가 발생할 수 있습니다.
실제로 java.util에 있는 HashMap으로 찾아가보면 위와 같은 주석 내용을 발견할 수 있습니다. 바로 해석할 수 있듯 synchronized가 되어있지 않기에, 멀티 쓰레드 환경에서 이 HashMap에 동시에 다수 쓰레드가 access하면 문제가 생길 수 있다는 내용입니다.
동시성 문제란?
동시성 문제는 여러 쓰레드가 동시에 같은 자원에 접근할 때 발생하는 문제로, 데이터 일관성이 깨지거나 예기치 않은 동작을 일으킬 수 있습니다.
예를 들어, 두 개 이상의 쓰레드가 동일한 데이터에 접근하여 다음과 같은 문제가 발생할 수 있습니다.
1. 두 개 이상 쓰레드가 하나의 데이터에 접근, 변경할 때 일관성이 유지되지 않아 원하지 않는 결과가 생긴다던지
2. 데이터가 수정되는 중 다른 쓰레드가 수정 전 데이터에 접근해 사용하는 문제가 생긴다던지
이러한 문제가 발생하지 않도록 하기 위해 똑똑한 개발자들은 동시성 문제를 해결할 방법을 생각해봅니다. 바로 JDK 1.0의 HashTable 입니다.
HashTable
HashTable은 synchronized를 사용해 동시성 문제가 발생하지 않도록 조치한 자료구조였습니다. 하지만 곧 문제가 생겼죠.
메서드 단위로 synchronzied 키워드가 붙은 것을 볼 수 있습니다. 위의 스크린샷 처럼 읽기만 하는 get 메서드 에도 달려있는 것을 볼 수 있습니다.
이런 경우 한 쓰레드가 HashTable에 get을 할 때 다른 쓰레드에 Map 단위로 lock 이 걸립니다.
즉 한 쓰레드가 get을 통해 데이터 access 하는 동안 다른 쓰레드들은 이 HashTable에 접근하는 경우 lock이 해제될 때 까지 기다려야합니다. 그래서 이 HashTable에 여러 쓰레드들이 자주 접근하는 경우 병목 현상으로 인해 성능 문제가 생기게 됩니다.
이렇게 너무 눈에 띄게 성능 문제가 보이니 결국 개발자들은 더 나아간 자료구조를 개발해냅니다. JDK 5 의 concurrentHashMap입니다.
ConcurrentHashMap
java.current 패키지 내부에 존재하는 ConcurrentHashMap은 동시성 문제를 해결하면서, 성능도 HashTable보다 높은 것으로 나타나는 것으로 알려져 있습니다. HashTable과 어떤 차이점이 있을까요?
HashTable에서 나타나는 성능 이슈는 메서드 단위로 지정된 synchronized 키워드로 인해 map자체에 lock이 걸리는 것이었습니다. ConcurrentHashMap의 경우 synchronized 키워드가 메서드 단위로 작성되어있지 않는다는 점이 가장 큰 차이점이라 할 수 있습니다.
위에 스크린샷을 보면 get 메서드에 synchronized키워드가 달려있지 않습니다. 즉, 읽기 작업을 할 때는 여러 쓰레드가 동시에 읽을 수 있게 되어있습니다.
그렇다면 put은 어떨까요? put메서드는 길이가 많이 길어 끊어서 이야기하도록 하겠습니다.
먼저 key, value를 받은 후 null체크를 기본적으로 해주고, spread라는 함수를 통해 해시코드를 생성하는 모습입니다. hashMap의 어느 인덱스에 값이 들어갈 지 결정하는 , HashMap의 put과 별 다를 게 없는 부분입니다.
그 다음, 해시 테이블 table의 내용을 루프를 돌기 시작합니다. tab가 null, 또는 길이가 0이라는 건 아직 초기화 되지 않은 테이블이니, initTable을 호출해 초기화를 시도합니다.
테이블이 존재한다면, tabAt 함수를 호출해 그 인덱스에 데이터가 존재하는지 확인합니다. 여기서 i = (n - 1) & hash 부분 연산을 통해 그 해시값에 맞는 인덱스를 추출합니다. (자세한 내용은 밑에 달아두었습니다.)
만약 데이터가 있다면 tabAt(tab, i = (n - 1) & hash) 를 호출하는데.. n은 처음에 table의 사이즈로 초기화되었고, 이 길이에 hash값과 & 비트 연산을 합니다. 둘 다 int 타입 변수이기 때문에 4바이트 -> 32비트 크기의 이진수로 변환해 계산될겁니다.
만약 테이블 크기가 16이라면, n - 1은 15이고 이진수로 변환하면 1111입니다. 이 값과 hash값을 & 비트연산해서 hash값 크기 상관없이 맨 뒤 4자리값만 0이 아니게 될 가능성이 존재하죠.
밑에 예시를 보면 이해가 쉬울 것 같습니다.
00000000 00000000 00000000 00000110 // 6
& 00000000 00000000 00000000 00001111 // 15
------------------------------------------
00000000 00000000 00000000 00000110 //6
이렇게 1 ~ 15 사이의 인덱스만 추출할 수 있는 연산이 되는 겁니다. 이렇게 hash값에 맞는 인덱스 위치에 접근하고, 그곳에 데이터가 있는 지 체크합니다.
만약 데이터가 없다면, casTabAt함수를 실행합니다. CAS라는 알고리즘을 사용해, 테이블에 비동기적으로 생성한 노드 데이터를 삽입합니다.
-- CAS 알고리즘에 대해서는 다른 포스팅 링크로 대체합니다.
만약 그 버킷에 데이터가 존재하는데 첫 번째 노드의 해시값이 MOVED라면, 테이블 확장 중이기에 helpTransfer함수를 통해 노드를 적절한 위치로 전송해 삽입하려 노력합니다.
만약 onlyIfAbsent를 true로 파라미터를 입력했다면, key값에 대한 데이터가 존재하지 않을 경우에만 put이 동작하도록 하고, 그렇지 않을 경우 그냥 저장된 데이터를 반환하는 연산을 수행합니다.
위 조건들에 걸리지 않았다면, 다음 코드가 수행됩니다.
드디어 synchronized가 등장했습니다. f는 hash값에 대한 인덱스에 위치한 데이터를 가리킵니다. f에 대해 lock 을 건 것으로 생각할 수 있습니다. 즉, ConcurrentHashMap은 put 메서드에서 버킷 단위로 lock을 거는 방법을 사용합니다.
하나에 버킷에 여러 데이터가 연결 리스트 형태로 연결되어있는 상태일 수 있기에, 반복문을 통해 한 버킷의 데이터들에 접근합니다.
만약 동일한 키값이 존재한다면, 두 가지 동작 중 하나를 선택합니다. (빨간 네모 부분)
1. onlyIfAbsent가 false일 경우 기존 value에 새 value로 덮어씌운다.
2. 기존 value를 그냥 반환한다.
만약 다 돌아봤는데 동일한 키 값이 없다면, 리스트의 맨 끝에 새 노드로 연결됩니다.
이건 동시성 문제와 연관되지는 않은 부분인데.. 추가로 데이터가 특정한 임계치 이상으로 저장된다면 내부적으로 최적화하는 작업을 진행합니다.
연결 리스트 구조에서 red - black tree 구조로 전환하는 함수도 이렇게 존재합니다. red - black tree는 탐색 복잡도가 O(log n)이라는 안정적인 속도를 가지고 있어, 해시 충돌이 자주 발생해 삽입, 삭제가 자주 일어나도 안정적입니다. (이건 hashMap을 파고들 때 만나겠네요)
get과 put만 봐도 상당히 이야기할 거리가 많았습니다. HashTable과 비교한다면, 다음과 같이 정리할 수 있을 것 같습니다.
1. 메서드 단위로 lock을 거는 HashTable VS 버킷 단위로 lock을 거는 ConcurrentHashMap
2. get 을 사용할 시, lock을 거는 HashTable VS get을 할 때는 lock을 걸지 않는 ConcurrentHashMap