나는 몰랐던, 고성능 멀티쓰레드 동기화 기법 - CAS (Compare And Swap)

주싱·2024년 3월 22일

더 나은 도구

목록 보기

13/13

난 배운적이 없는데

멀티쓰레드 환경에서 발생하는 동기화 문제를 해결하는 가장 확실한 방법은 락(lock)을 통해 크리티컬 섹션(critical section)이 원자적(atomic)으로 실행되도록 보장하는 것이다. 다시 말해 특정 코드 영역의 시작 부분에 문을 걸어 잠그고 반드시 한 번에 한 쓰레드만이 해당 코드를 실행할 수 있도록 하는 것이다. 내가 주의를 기울이지 않았던 것인지 실제로 학교에서 그것만 가르쳤던 것인지 정확히 기억할 수 없지만 대학 운영체제 수업에서와 이후 실무에서 찾아본 몇몇 책에서도 이런 방법만 접했던 것으로 기억한다. 어쨋든 온전하지 않은 지식을 가졌지만 개발자로 잘 일해 왔던 어느날 ‘스프링캠프 2023’라는 컨퍼런스에 참석하게 되었다. 그리고 한 세션에서 처음 들어보는 쓰레드 동기화 기법에 대해 듣게 된다. 이름하여 CAS(Compare And Swap)라는 것이었다. 발표자께서 대규모 트래픽을 다루는 시스템에서 락킹으로만 동기화 문제를 해결하면 성능상 문제를 겪게 될 수 있다고 했다. 그리고 코드에 ‘synchronized’ 키워드를 덕지덕지 발라두면 선배에게 혼날거라며 농담반 진담반 설명해 주셨는데 진짜 그런지 왜 그런지 정확히 이해할 수 없었다. 네이버라는 이름있는 회사에 다니시는 분이셨지만 그의 말이 맞는지 확인하고 싶은 욕구가 솟아났다. 그래서 집에 돌아가서 나 보다 뛰어나고 신뢰할 만한 코드인 자바 구현부를 살펴보기로 했다. 자바는 과연 쓰레드 동기화를 어떻게 구현하고 있는지 살펴봄으로 그의 말이 사실인지 확인해 보기로 한 것이다. 그래서 자바에서 제공하는 대표적인 Thread-Safe 한 클래스인 AtomicLong 클래스를 선택하고 멀티쓰레드 환경에서 동기화를 요구하는 i++ 같은 연산의 구현부인 incrementAndGet() 메서드를 살펴보기 시작했다. 그때까지만 해도 자바는 대략 다음과 같이 synchronized 키워드를 사용한 락킹을 통해 동기화를 구현했을 것이라 기대했다. CAS라는 기법은 특별한 경우에 사용하는 방법이지 않을까 내심 기대했다

public class AtomicLong {
		private long value;

		public synchronized long incrementAndGet() {
			value = value + 1;
			return  value; 
		}
		
		... 
}

그런데 실제 자바 구현은 내가 기대했던 것과 완전히 달랐다. 다짜고짜 synchronized 키워드를 검색해 봤지만 해당 키워드는 아무리 검색해도 찾을 수 없었다. 그때 당시 나를 당황하게 했던 자바의 AtomicLong 클래스의 incrementAndGet() 메서드 구현부와 함께 공부하며 이해한 내용들을 정리해 보려고 한다.

Volatile 키워드가 하는 일

먼저 AtomicLong 클래스가 안전하게 캡슐화한 long 타입 값은 volatile 이라는 키워드로 선언되어 있는 것을 볼 수 있다. 그럼 이 volatile 키워드는 도대체 나의 코드에 어떤 영향을 미치는 것인지 정리해 본다. volatile 키워드가 하는 일은 크게 세 가지로 나누어 볼 수 있다.

public class AtomicLong {
		
    private volatile long value; 
		... 
}

1. 각자의 캐시 대신, 공유 메모리를 통해

먼저 volatile 키워드는 멀티쓰레드 환경에서 공유변수에 대한 접근(읽기, 쓰기)이 캐시 메모리가 아닌 메인 메모리를 통해 이루어 지도록 보장한다. 이게 왜 필요한지 이해하기 위해 현대의 멀티코어 프로세서의 구조에 대한 약간의 이해가 필요하다. 우리가 작성한 멀티쓰레드 프로그램을 실행하는 각 쓰레드는 물리적으로 서로 다른 CPU 코어에 할당되어 동시에 병렬로 실행될 수 있다. 이때 각각의 CPU는 자기만의 캐시 메모리를 유지하며 프로그램의 메모리에 대한 접근 성능을 높인다. 원리는 간단하다. 캐시 메모리는 메인 메모리로부터 프로그램이 자주 접근하는 또는 자주 접근할 것으로 예상되는 메모리 영역을 CPU와 가깝고 독립적인 영역에 복사해서 관리함으로 공유되는 메인 메모리에 대한 병목으로부터 벗어나고 물리적으로도 더 빠른 매체로 부터 데이터에 접근하게 된다. 이 캐시 구조로 인해 프로그램의 메모리 접근 성능이 높아지고 궁극적으로 프로그램 실행 성능이 향상된다. 그러나 이 캐시 구조는 치명적인 단점을 가지고 온다. 만약 두 쓰레드가 서로 다른 CPU에 의해 실행되고 두 쓰레드가 공유하는 변수가 각각의 CPU 캐시에서 관리된다면 한 쓰레드에서 특정 변수에 쓴 값이 다른 쓰레드에는 적용되지 않을 수 있는 일관되지 않는 동작을 유발하게 된다. 컴퓨터 공학에서 이와 같은 문제를 캐시 일관성(Cache Coherence) 문제 또는 메모리 가시성(Memory Visibility) 문제라고 한다. 이 문제를 해결하기 위해 volatile 키워드를 사용할 수 있다. volatile 키워드로 공유 변수를 선언하면 변수에 대한 접근이 모든 CPU 코어가 공유하는 메인 메모리를 통해 이루어 지게 한다. 따라서 앞서 설명한 캐시 일관성 문제, 메모리 가시성 문제를 해결할 수 있다. 다만 캐시를 통한 접근보다 데이터에 접근하는 속도는 떨어지게 된다. Java 언어에서는 volatile 키워드에 의해 부여된 공유 변수에 대한 쓰기와 읽기 동작 사이의 관계를 ‘happens-before’ 관계에 있다고 표현한다. Java 공식 문서를 보면 이렇게 한 문장으로 표현되어 있다. “A write to a volatile field happens-before every subsequent read of that field.” (17.4.5. Happens-before Order) volatile 변수에 대한 쓰기는 뒤이은 모든 읽기(해당 변수에 대한) 전에 발생한다. Java 언어 스펙에서는 CPU 아키텍처에 대한 내용은 생략하고 위와 같이 선언적으로 결과만을 기술하는 것으로 보인다. 위 내용을 멀티쓰레드 관점으로 재해석한다면 한 쓰레드에서 수행한 공유 변수에 대한 쓰기 결과는 다른 모든 쓰레드에 일관되게 보여진다로 의역할 수 있겠다. 이처럼 volatile 키워드를 사용하면 메모리 일관성 문제 또는 메모리 가시성 문제를 해결할 수 있다.

2. 나눠질 수 있는 8바이트 변수 접근을 원자적으로

long value;
...
value = 100;

우리가 고급 프로그래밍 언어로 작성한 아주 단순한 변수 할당 구문을 생각해 보자. 사람이 보기에 이 명령어 한 줄은 반드시 하나라 동기화 문제가 발생할 것 같지 않다. 그러나 그렇지 않다. CPU 레벨로 내려가면 고급 프로그래밍 언어로 작성된 명령어 한 줄은 두 개 이상의 기계어 코드로 나누어 질 수 있다. 예를 들면 4바이트 크기의 CPU 레지스터를 사용해 변수 i의 상위 메모리 영역에 값을 쓰고 그 다음에 하위 4바이트 영역에 값을 쓰도록 기계어 코드가 나누어 질 수 있다. 따라서 우리가 value에 어떤 값을 읽으려는 시점이 때마침 다른 쓰레드에서 상위 4바이트에만 값을 기록한 상태이고 마침 그때 쓰레드 스위칭이 발생했다면 우리는 이전의 하위 4바이트 값과 새로 작성한 상위 4바이트 값이 섞여 있는 유효하지 않은 값을 읽게 된다. volatile 키워드는 나누어 질 수 있는 이 연산을 원자적으로 수행되도록 보장해줌으로 이 문제를 해결한다.

3. 컴파일러의 최적화로 인한 오동작 방지

volatile 키워드가 하는 마지막 기능은 컴파일러의 최적화 기능이 해당 변수를 다루는 코드에 적용되지 않도록 하는 것이다. 최적화라는 좋은 것을 왜 끄는지 의아할 수 있지만 때때로 프로그래머가 의도하지 않은 컴파일러의 최적화 동작으로 인해 프로그램이 오동작하는 일이 발생할 수 있다. 예를 들면 명령어의 순서를 임의로 바꾸는 것 등의 최적화 행위를 컴파일러가 수행할 수 있고 이로 인해 멀티쓰레드 프로그램에서 문제가 발생할 수 있다. 이 부분은 충분히 설명할 만큼 공부를 하지 못해 이 정도로 생략한다.

volatile 키워드의 이점

지금까지 volatile 키워드를 통한 동기화 기법을 정리해 보았다. 앞서 volatile 키워드로 변수를 선언하면 캐시 대신 항상 메모리를 통해 데이터 접근이 이루어짐으로 성능이 떨어진다고 설명했다. 그러나 이것은 synchnonized 키워드를 사용하는 락킹 기법 보다는 나은 성능을 제공한다. 락킹은 운영체제 수준에서 쓰레드 컨텍스트를 유발한다. 락을 걸어 잠근 쓰레드 외에 다른 쓰레드가 크리티컬 섹션에 진입하게 되면 해당 쓰레드는 대기 상태에 들어가고 CPU 스케줄링 작업이 운영체제 수준에서 다시 일어나게 된다. 이는 volatile 키워드로 인해 캐시 대신 메인 메모리를 참조하는 것 보다 훨씬 큰 비용이다. 그러나 synchronized 키워드는 volatile 키워드가 제공하는 모든 기능을 제공하면서 volatile 키워드로는 해결할 수 없는 총체적인 동기화 해법을 제공한다.

volatile 키워드로 할 수 없는 일

다음 코드를 살펴보자. 이 코드는 멀티쓰레드에 의해 동시에 실행된다면 안전하게 동작함을 보장해 주지 못한다.

long value = 100;
value++;

왜냐하면 value++ 구문은 실제로 CPU 기계어 수준에서는 아래와 같은 세 개의 동작으로 나누어 질 수 있기 때문이다. 익숙하지 않은 어셈블리 코드 대신 상황을 묘사할 수 있게 간단한 평문으로 표현해 보았다. 이렇게 나누어진 기계어 코드는 앞서 단순한 변수 할당문에서 발생할 수 있는 문제를 설명한 것 처럼 어느 시점에 컨텍스트 스위칭이 일어날지 예측할 수 없다. value ++ 과 같은 상황이라면 A 쓰레드에서 레지스터에 1을 더한 상태(메모리에 아직 결과를 쓰기 전)에서 B 쓰레드로 스위칭이 되고 B 쓰레드에서 value 값을 1증가 시키고 결과 값을 메모리에 써버린다면 문제가 발생한다. 이후 다시 A 쓰레드로 스위치되어 최종 결과 값을 메모리에 쓰게 되면 B쓰레드가 증가시킨 1 값은 결과적으로 무시되는 상황이 된다. volatile 키워드로는 이 문제를 해결할 수 없다.

1. 메모리에서 value 값을 CPU 레지스터로 가져온다.
2. 레지스터에 값을 1 더한다.
3. 레지스터에 계산된 결과를 다시 메모리 value에 쓴다.

Synchronized 전략

이 문제를 해결하는 가장 단순하고 확실한 방법은 역시 락킹(synchronized)을 활용하는 것이다. 그러나 락킹은 앞서 잠시 설명했지만 비용이 많이 든다. 대용량 트래픽을 다루는 애플리케이션이라면 이 비용이 문제가 되는 상황이 생길 수 있다.

CAS(Compare And Swap) 전략

이제 오늘의 주제였던 CAS(Compare And Swap)라는 전략을 설명할 때가 된 것 같다. 원래는 Java AtomicLong 클래스의 incrementAndGet() 메서드의 구현부로 설명을 정리하고 싶었는데 설명의 예제로 쓰기에는 부차적으로 설명할 내용이 너무 많다. 그래서 간결한 설명을 위해 ‘Java Concurrecy in Practice’ 책의 예제를 빌려왔다. 아래 모든 예제는 책에 나오는 내용임을 미리 밝혀 둔다. 먼저 CAS 연산은 하드웨어적으로 CPU에서 기계 명령어로 제공하는 하나의 명령어이다. 물론 이런 명령을 지원하지 않는 CPU라면 CAS 연산은 JVM에 의해 소프트웨어적으로 처리될 것이다. 아래 예제는 하드웨어적 CAS 연산과 동일한 기능을 하는 CAS 명령을 시뮬레이션 하는 클래스를 소프트웨어적으로 구현한 것이다. 이제 코드와 함께 CAS 연산에 대해 하나씩 뜯어보자.

@ThreadSafe
public class SimulatedCAS {
		@GuardedBy("this") private int value;
		
		public synchronized int get() { return value; }
		
		public synchronized int compareAndSwap( int expectedValue, int newValue ) {
				int oldValue = value;
				if (oldValue == expectedValue)
						value = newValue;
				return oldValue;
		}
}

CAS 연산은 어떤 계산(어떤 계산이든)을 수행한 결과 값(newValue)과 계산을 수행하기 이전의 값(expectedValue)을 요구한다. 그리고 계산된 결과를 메모리에 저장하기 전에 계산 이전의 값이 현재 메모리에 값과 동일하게 유지되고 있는지 비교한다. 이는 다른 쓰레드에 의해 변수 값이 변경된 경쟁 상태(Race Condition)에 놓여있는지 확인하는 과정이라고 볼 수 있겠다. 나는 i 변수 값이 0일 떄 i++ 연산을 해서 1이라는 값을 만들었는데 메모리에 계산 결과 값을 쓰려고 보니 누가 값을 0에서 1로 먼저 바꾸어 놓은 것이다. 이 상황에서 나의 계산 결과 1을 써버리면 value 값은 더 이상 유효한 값이 아니다. CAS는 이런 충돌 상황이 없을 때만 메모리 변수에 계산 결과를 쓴다. 그리고 메모리에 저장된 현재 값을 반환해 준다. 이렇게 되면 외부에서는 루프를 돌며 계산을 수행하고 계산 결과와 계산 이전의 값과 함께 compareAndSwap() 메서드를 호출한 후 계산 이전의 값과 메서드가 반환하는 값이 같은지 비교하면 Race Condition에 놓여있어 쓰기가 실패했는지 알 수 있다. 그리고 만약 실패했다면 새로운 이전 값을 읽어 다시 계산을 시도할 수 있다. 이로써 락킹 없이 성능의 이점은 살리면서 synchronized 키워드를 사용하는 것과 동일한 수준의 동기화를 달성할 수 있다. 일단 락 때문에 운영체제 수준의 컨텍스트 스위칭이 발생하지 않는다. 그리고 대부분은 충돌이 일어나지 않거나 몇 번의 재시도로 원하는 결과를 달성할 수 있다. 대규모 트래픽을 다루는 서비스라면 CAS 전략을 사용해야 한다는 발표자 분의 말이 이제 이해된다.

@ThreadSafe
public class CasCounter {
		private SimulatedCAS value;
		
		public int increment() {
				int v;
				do {
						v = value.get();
				} while(v != value.compareAndSwap(v, v + 1));
				return v + 1;
		}
}

멀티쓰레드 동기화 어려운 이유

내가 이 글을 쓰기 시작한 이유는 일단 내가 멀티쓰레드 환경에서의 동기화 개념을 어려워 해서 누군가에게 쉽게 설명하지 못하기 때문이었다. 이 문제는 어렵다고 대충 덮어둘 수 없는데, 이 문제를 제대로 다루지 못하면 1,000번에 1번, 10,000번에 1번 (또는 그 이상의 적은 확률로) 간헐적으로 발생하는 아주 해결하기 어려운 문제를 만난게 될 수도 있다. 따라서 현 시대를 살아가는 프로그래머라면 이 문제를 가볍게 넘겨 볼 수는 없다. 개인적으로 동기화 문제를 어렵게 만드는 이유를 꼽아보라면 문제를 일관되게 재현해서 눈으로 보고 직관적으로 파악하기 어렵기 때문인 것 같다. 일명 타이밍이 기가 막히게 들어 맞아야 발생하는 문제인 것이다. 그리고 이 타이밍은 내가 제어할 수 없는 CPU, 운영체제, 컴파일러의 동작 특성과 결합하여 발생하기 때문에 이 문제를 해결하려면 내가 제어할 수 없는 그들의(CPU, 운영체제, 컴파일러) 원리를 정확히 이해해야 한다. 그리고 나서 그 원리에 입각해서 문제에 확실하게 대처해야 한다. 내가 제대로 코드를 작성했는지 테스트하기 어려움으로 원리를 제대로 이해하고 대처해야 하는 것은 여러번 강조해도 무방한 듯하다. 나 스스로 이 글을 쓰며 많은 공부가 된 것 같다. 혹시 이 글을 읽는 분들에게도 도움이 되었으면 좋겠다.

마치며

시작은 거의 강의 하나를 만들 수준으로 글을 쓰려고 했으나 컴퓨터 공학의 여러 개념이 맞물려서 설명이 되어야 해서 정리가 쉽지 않았던 것 같다. 혹시 틀린 내용이 있으면 누구나 교정해 준다면 정말 좋을 것 같다.

Reference

주싱

소프트웨어 엔지니어, 일상

이전 포스트