뮤텍스가 느린 진짜 이유 - CPU 캐시 코히어런스로 이해하는 동시성 조정 비용과 거짓 공유

핵심 메시지

• 읽기만 수행하는 벤치마크에서도 스레드를 하나에서 둘로 늘리는 순간 처리량이 10분의 1 수준으로 떨어진다.
• 리더-라이터 락은 읽기 잠금을 잡을 때조차 내부 카운터를 증가시키므로, 읽기 스레드가 늘수록 오히려 뮤텍스보다 나빠진다.
• 비용의 근원은 잠금이 아니라 MESI 계열 캐시 일관성 프로토콜이며, 공유 캐시 라인에 쓰기를 하려면 다른 코어와 협의해야 한다.
• 코어 간 통신은 약 30나노초로, L1 캐시 접근 1나노초와 주메모리 100나노초 사이에서 결코 무시할 수 없는 비용이다.
• 락 프리는 경합 없음을 뜻하지 않는다. 서로 다른 카운터라도 같은 64바이트 캐시 라인에 놓이면 거짓 공유로 성능이 무너진다.

쉽게 이해하기

제인스트리트 강연에 선 존 옌셋은 '뮤텍스는 느린가'라는 제목으로 이야기를 시작한다. 헤드라인 법칙대로 답은 '아니오'지만, 우리 대부분은 뮤텍스 때문에 프로그램이 멈춰 선 경험을 갖고 있다. 그 모순을 풀기 위해 그는 아주 단순한 실험을 준비했다. 공유 카운터를 만들어 두고 쓰기는 전혀 하지 않은 채, 여러 스레드가 잠금을 잡아 값을 읽기만 하는 코드다.

결과는 직관을 배신한다. 스레드가 하나일 때는 초당 2억 5천만 번을 읽어 2.5GHz CPU 기준으로 잠금과 읽기를 합쳐 열 개 남짓한 명령어에 해당하는 성능이 나온다. 그런데 코어가 둘이 되는 순간 10분의 1인 2500만 번대로 떨어지고, 그 뒤로는 스레드를 더 넣어도 바닥에 붙어 거의 평평하다. 상호 배제라면 한 번에 하나씩 처리되니 성능이 유지될 것 같은데, 실제로는 스레드가 늘수록 더 나빠진다. 리더-라이터 락으로 바꿔도 사정은 비슷하고, 읽기 스레드가 많아질수록 오히려 뮤텍스보다 더 나빠지는 구간이 나온다.

설명은 CPU 캐시에서 시작된다. 주메모리는 물리적으로 멀어 접근에 수백 명령어가 걸리므로 CPU는 L1부터 L3까지 계층적인 캐시를 둔다. 여러 코어가 같은 메모리를 다룰 때는 누가 언제 쓸 수 있는지 협의하는 캐시 일관성 프로토콜이 필요한데, 그것이 MESI다. 캐시는 메모리를 64바이트 캐시 라인 단위로 관리하며, 각 라인은 수정됨·독점·공유·무효 네 상태 중 하나를 갖는다. 공유 상태의 라인에 쓰기를 하려면 다른 코어들이 그 라인을 더는 읽거나 쓰지 않도록 만들고 독점 상태로 옮겨야 한다. 즉 공유 데이터에 대한 쓰기는 코어 간 협의를 요구한다.

여기서 리더-라이터 락의 역설이 풀린다. 읽기 잠금을 잡는다는 것은 락 내부의 리더 수 카운터를 증가시키는 쓰기 동작이고, 해제할 때 또 한 번 감소시킨다. 스레드 백 개가 읽기 잠금을 잡으면 백 개의 코어가 차례로 같은 캐시 라인을 독점 상태로 가져갔다 넘겨주는 일이 반복된다. 잠금 한 번에 캐시 라인 전송이 두 번 필요하고 한 번에 30나노초가량 드니, 읽기 잠금만으로 이미 60나노초다. 주메모리 접근이 100나노초라는 점을 생각하면 절반을 넘긴 셈이다. 반대로 뮤텍스는 잠금을 쥔 동안 다른 스레드가 카운터를 건드릴 수 없어 이런 왕복이 덜하다.

대안으로 소개된 것이 그가 박사 연구에서 쓴 좌우(left-right) 자료구조다. 데이터의 복사본을 둘 두고, 원자적 포인터가 가리키는 쪽은 읽기 전용으로, 가리키지 않는 쪽은 쓰기용으로 쓴 뒤 포인터를 뒤집는 방식이다. 독자마다 자기 캐시 라인에 놓인 카운터를 갖고 포인터를 읽은 횟수만 올리므로 독자끼리는 서로 대화할 필요가 없고, 읽기는 잠금도 대기도 없는 wait-free가 된다. 그 결과 스레드 수에 따라 처리량이 선형으로 오르는 그래프가 나온다. 다만 벤치마크 도중 네 스레드 구간에서 성능이 10배 가까이 떨어지는 현상이 있었는데, 원인은 서로 다른 독자의 카운터가 같은 64바이트 라인에 얹힌 거짓 공유였고 정렬을 64바이트로 맞추는 한 줄로 해결됐다.

주요 인사이트

• 잠금이 느리다는 통념은 관측은 맞지만 원인 진단이 틀렸다. 값을 읽기만 해도 성능이 무너지는 이유는 상호 배제가 아니라 코어 사이에서 캐시 라인 소유권이 오가는 비용이다.
• 읽기가 많으면 리더-라이터 락을 쓰라는 조언은 임계 구역이 충분히 길 때만 성립한다. 해시맵 조회 한 번처럼 임계 구역이 짧으면 잠금 획득 비용이 실제 작업 시간을 넘어선다.
• 락이 필요할 만큼 경합이 심한 상황일수록 락의 상대적 오버헤드가 커진다는 역설이 있다. 즉 락이 가장 절실한 자리에서 락이 가장 불리하게 작동한다.
• 거짓 공유 사례는 락 프리가 곧 경합 없음이 아니라는 점을 보여 준다. 알고리즘 수준에서 공유가 없어도 메모리 배치가 어긋나면 하드웨어가 대신 경합을 만들어 낸다.
• 좌우 자료구조가 빠른 것은 쓰기가 드물다는 전제 덕분이다. 쓰기 비중이 커지면 이점이 사라지고, 복사본 두 벌 유지·오래된 값 읽기·단일 작성자 제약 같은 대가가 따라온다. 결국 가장 빠른 잠금 구현을 고르는 문제가 아니라, 워크로드의 읽기/쓰기 비율과 임계 구역 길이, 스레드 수, 감내할 수 있는 일관성 수준에 맞춰 알고리즘을 고르는 문제다.

자주 묻는 질문

관련 AI 소식