[Java, Concurrency] Compare and Swap 알고리즘 (CAS)

 
HashMap과 ConcurrentHashMap 차이점에 대해 공부하다가 ConcurrentHashMap의 코드를 확인해보니 Segment는 Java 8 부터는 사용되지 않아 하위호환성을 위해 남겨둔 것을 발견했다. 그러면 어떻게 안전하게 동시성 처리를 하는지 확인해보니 synchronized, 버켓(노드) 락, CAS 알고리즘을 사용하는데, CAS 알고리즘은 처음 들어봐서 정리하게 됐다.
 
 

1. synchronized

CAS 알고리즘에 대해 설명하기 전에 먼저 synchronized에 대해 알고 있어야한다.
자바의 락은 모니터 개념을 사용하고 있는데, 원하는 범위만큼 하나의 스레드만 락을 획득할 수 있는 방법이다. 인스턴스의 메서드에 synchronized를 적용하면 인스턴스 메서드에 락이 걸리고, synchronized(인스턴스)를 적용하면 인스턴스에 락이 걸린다. 쉽게 말해서 원하는 코드 블록에 적용할 수 있는 뮤텍스라고 생각하면 된다.
synchronized의 큰 단점은 blocking으로 동작한다는 점이다. A 스레드가 synchronized를 사용하고 있으면 B 스레드는 대기하고 있어야 한다. 만약 많은 스레드가 사용하는 로직에 synchronized가 적용되어 있다면 그만큼 성능 저하가 일어난다.

---

2. Compare and Swap 알고리즘 (CAS)

Compare and Swap은 synchronized와 다르게 자원에 락을 걸지 않는다. 대표적인 Non-blocking 알고리즘으로 불린다. lock-free이기 때문에 스레드가 락을 할당할/해제할 과정이 없어지므로 고성능을 보장해준다.
 
예시로 어떤 값을 x에서 y로 변경한다고 가정해보자
 
1. x가 저장된 메모리 값을 읽는다.
2-1. 메모리에 저장된 값이 x라면 y로 값을 변경한다. 
2-2. 메모리에 저장된 값이 x가 아니라면 값을 변경하지 않는다.
3. 메모리에 저장된 값을 반환한다.
 

 
Java 기준으로는 (CT arguments, expectedValue, newValue)로 이루어진다.
arguments에 있는 값이 expectedValue라면 newValue로 바꾼다는 것이다.
 
 
[Compare and Swap / Compare and Set]
Compare and Set은 Compare and Swap의 변형이다. 작동방식은 둘 다 똑같지만 반환값이 다른데, Compare and Swap은 메모리에 쓰여진 값을 반환한다. Compare and Set은 값이 바꾸고 싶은 값으로 바뀌었는지에 대한 boolean 값으로 나타낸다.
왜 Set으로 사용하는지 생각해보니 어차피 값이 수정될 수 있으면 수정되는게 똑같고, 메서드 호출 후 값 변경 여부를 확인하려면 Swap의 경우 [수정하려는 값] == [수정된 값]인지 추가적으로 비교해야하므로 Set으로 설정한 것 같다.

---

3. CAS 문제점 (ABA 문제)

[실생활 예시]
계좌에 100만원이 있을 때, 스레드 1에서는 10만원을 인출한다고 하자. 처음에는 CAS 연산을 위해 스레드 1에서 계좌의 금액을 확인하게 된다. 그리고 거래 한도 초과 정보도 읽어온다. 그리고 잠시 정지하게 된다.
이후 직후에 스레드 2에서 먼저 CAS 연산을 수행해 50만원을 인출하고, 다시 50만원을 입금한다고 해보자. 이러면 계좌는 100만원 그대로로 보인다.
잠깐 정지했던 스레드 1에서는 다시 진행해 계좌가 100만원으로 데이터가 변경되지 않았다고 생각하고, 10만원 인출을 진행하게 된다.
만약 거래 한도 초과 금액이 50만원이면 스레드 2를 거래한 뒤 멈춰야 하지만, 스레드 1에서는 거래하는데 문제가 없으므로 한도 초과 금액 이상인데도 거래를 진행하게 된다.
 
[스택 예시]
실생활 예시로 어떤 문제인지 대략적으로 알게 됐으면 이제 기술적인 예시로 이해해보자
스택에 [a, b, c]가 있다고 가정해보자. 여기서 top = a, next = b가 된다.
1. 스레드 1에서 pop을 수행하려고 top = a, next = b를 가지고 있게 된다.
2. 스레드 2가 먼저 pop을 두 번 수행한다. 그래서 실제 top = c, next = null을 가지게 된다. (스레드 1은 아직 과정 1 그대로인 상태)
3. 스레드 3에서 a를 push 한다. 실제 top = a, next = c인 상태이다. (스레드 1은 아직 과정 1 그대로인 상태)
4. 스레드 1에서 CAS 연산을 수행하는데 top = a이므로 문제가 없다. 그래서 top = b로 설정하는데, 이미 b는 스택에서 없는 값이다.
이렇게 되면 b는 없는 값인데, 스택의 top에 존재하게 되므로 ABA 문제가 발생하게 된다.
 
[자바에서는 ABA 문제가 거의 발생하지 않는 이유]
위의 스택을 예시로 든다면 실제 스택에 값 x가 저장되는건 Node(x)로 Node(...)와 같은 Wrapper 타입으로 저장이 된다.
그러면 스레드 1에서 top = Node(a), next = Node(b)가 된다. 이때의 Node(a)의 주소값을 0000이라고 하자
스레드 3에서 a를 삽입하면 Node(a)가 들어오게 되는데, 여기서 Node(a)의 주소값은 0001이다.
1) GC에 의해 0000인 Node(a)가 메모리 할당 해제가 되면 주소값 0000은 바로 재사용되지 않아 저장될 일이 없다.
2) GC가 돌아가지 않으면 애초에 주소값 0000에 Node(a)가 저장될 일이 없다.
서로 다른 주소값을 가지고 있기 때문에 CAS 연산에서 expectedValue는 다른 값을 가지게 되며 CAS 연산이 실패하게 된다.
그래서 ABA 문제가 거의 발생하지 않는다. (거의인 이유는 확실하게 다른 상황에서 ABA 문제가 없다고 말할 수 없기 때문임)

---

4. CAS를 사용하는 자료구조 예시

Atomic 대신 어떤 자료구조를 보면 이해하기 쉽나 살펴보다가 ConcurrentLinkedQueue를 발견했다. (코드)
큐에 데이터를 삽입할 때 add 메서드를 호출하면 큐가 삽입되는 로직이 있는 offer 메서드를 호출한다.
for (Node<E> t = tail, p = t ; ; )로 되어 있는 부분은 for문을 다 돌아도 값이 업데이트되는 것이 없다. (= 무한루프)
첫번째 if문을 보면 꼬리에 원소를 삽입하려고 하는데, CAS 연산을 해서 꼬리 다음의 원소가 null이면 newNode를 저장하는 로직이 있다. 이후 TAIL 노드도 업데이트를 진행한다. 여기에서 만약 두 스레드가 동시에 원소 삽입을 했지만, 먼저 삽입되는 원소가 있다면 하나는 if (NEXT.compareAndSet(p, null, newNode)를 통과하지 못하고, 다시 for문을 처음부터 돌릴 것이다. 이러면 락 없이 동시성 문제도 해결 가능하다.
 

---

 
단순히 ConcurrentHashMap이 락을 어떻게 획득하는지에 대한 궁금점을 찾아봤는데 정말 많은 내용이 연결되어 있는걸 알게 됐다. 운영체제 read-modify-write, 자바 synchronized, JPA 낙관적 락, 비관적 락, blocking과 non-blocking, ... 참 많다. CAS가 자바 뿐만 아니라 JVM 코드에서도 사용되고, CPU에서 CAS가 단일 명령어로 지원한다고하니 굉장히 많은 곳에서 사용할 것 같다.
거기다가 ConcurrentHashMap에 락을 거는 메서드가 MySQL InnoDB와 흡사하던데, 왜 개념을 잘 공부해두면 도움이 많이 된다는지 잘 알게 됐다.