거짓 공유

거짓 공유는 스레드 둘이 서로 다른 데이터를 고치는데도 서로를 기다리게 되는 일입니다. 카운터 둘을 나란히 두고 스레드가 하나씩 세는 경우가 그렇습니다. 프로그램은 두 데이터를 따로 나눠 두었는데 하드웨어는 그 둘을 한 덩이로 묶어 다루기 때문입니다. 그래서 일을 스레드 둘로 나눠 놓고도 속도가 안 오릅니다.

상세

거짓 공유는 하드웨어가 메모리를 덩이로 다루는 데서 시작합니다.

캐시 라인이라는 덩이

CPU(Central Processing Unit, 중앙처리장치)는 메모리에서 값을 한 바이트씩 가져오지 않습니다. 정해진 크기의 덩이를 한 번에 가져옵니다. 이 덩이를 캐시 라인이라고 합니다. 흔히 쓰는 프로세서에서 64바이트입니다.

덩이로 가져오는 까닭은 둘입니다. 메모리는 프로세서보다 훨씬 느려서, 한 바이트를 청하든 덩이째 청하든 한 번 다녀오는 시간이 비슷합니다. 그리고 방금 읽은 값의 이웃은 곧 이어서 읽힐 때가 많습니다. 그래서 프로세서는 가져온 덩이를 CPU 캐시라는 작은 메모리에 담아 두고 다시 씁니다.

요즘 프로세서는 명령을 실제로 실행하는 코어를 여럿 답니다. 코어마다 자기 캐시를 따로 들고 있습니다. 그래서 같은 라인의 사본이 여러 코어에 동시에 있을 수 있습니다.

문제는 그 덩이에 무엇이 같이 실릴지를 프로그램이 고르지 않는다는 것입니다. 나란히 선언한 변수 둘, 배열의 이웃한 두 칸, 한 구조체 안의 두 필드는 대개 같은 라인에 앉습니다. 코드에서는 남남인데 하드웨어에서는 한 덩이입니다. 아래 그림의 x 와 y 가 그런 짝입니다.

flowchart TD
    subgraph 라인["캐시 라인 하나 · 64바이트"]
        X["변수 x · 코어 A 만 고친다"]
        Y["변수 y · 코어 B 만 고친다"]
    end
    라인 -->|사본을 받아 간다| CA["코어 A 의 사본 · x 와 y 가 함께 실린다"]
    라인 -->|사본을 받아 간다| CB["코어 B 의 사본 · x 와 y 가 함께 실린다"]

코어가 받아 가는 것은 변수 하나가 아니라 라인 한 줄입니다. x 만 쓰는 코어도 y 를 같이 들고 있게 됩니다.

라인이 코어 사이를 오가는 과정

사본이 여럿이면 한쪽에서 고친 값이 다른 쪽에 안 보이는 문제가 생깁니다. 코어 A 가 자기 사본의 값을 바꿔도 코어 B 가 든 사본은 옛 값 그대로이기 때문입니다.

그래서 코어들은 서로의 사본 상태를 주고받으며 맞춥니다. 이 맞추는 규칙이 캐시 일관성입니다. 뼈대는 한 줄입니다. 어떤 코어가 라인을 고치려면 그 라인을 혼자 쥐어야 하고, 같은 라인을 들고 있던 다른 코어의 사본은 무효가 됩니다.

라인 한 줄은 두 자리 사이를 오갑니다. 읽기만 하는 동안에는 여러 코어가 사본을 나눠 가져도 됩니다. 고치는 순간부터는 고친 코어 하나만 그 라인을 쥡니다.

stateDiagram-v2
    state "여러 코어가 읽기 사본을 나눠 갖는다" as 공유
    state "코어 A 가 혼자 쥔다 · 나머지 사본은 무효" as A독점
    state "코어 B 가 혼자 쥔다 · 나머지 사본은 무효" as B독점
    공유 --> A독점: 코어 A 가 고친다
    A독점 --> B독점: 코어 B 가 고친다
    B독점 --> A독점: 코어 A 가 고친다

여기까지는 같은 데이터를 실제로 나눠 쓰는 코어들이 치르는 비용입니다. 거짓 공유는 나눠 쓰는 데이터가 하나도 없는데 같은 비용을 치르는 것입니다. 코어 둘이 각자 자기 변수만 고쳐도, 그 변수들이 한 라인에 앉아 있으면 라인은 한 번에 한 코어만 쥘 수 있습니다.

flowchart TD
    A["코어 A 가 x 를 고친다"] --> B["라인 전체를 A 가 혼자 쥔다"]
    B --> C["코어 B 의 사본이 무효가 된다"]
    C --> D["코어 B 가 y 를 고치려 한다"]
    D --> E["라인을 B 가 도로 가져온다"]
    E --> F["코어 A 의 사본이 무효가 된다"]
    F --> A

그림의 고리가 반복문이 도는 내내 이어집니다. 한 번 고칠 때마다 상대는 자기 사본을 버리고 라인을 다시 받아 옵니다. 계산량은 그대로인데 기다리는 시간만 붙습니다. 이 왕복을 캐시 핑퐁이라고도 부릅니다.

거짓 공유가 나는 조건

셋이 겹칠 때 납니다. 하나라도 빠지면 안 납니다.

• 스레드 둘 이상이 서로 다른 코어에서 돕니다
• 그 스레드들이 건드리는 데이터가 같은 캐시 라인 안에 들어 있습니다
• 그중 적어도 하나가 쓰기입니다

셋째 조건이 판정에 쓸 만합니다. 읽기만 하는 코어들은 같은 라인의 사본을 나눠 가져도 되므로 아무 일도 안 납니다. 같은 배열을 여러 스레드가 읽기만 하는 반복문은 이웃한 칸을 나눠 맡아도 거짓 공유가 아닙니다.

거짓 공유를 만드는 코드

가장 흔한 꼴은 스레드마다 카운터를 하나씩 주는 것입니다. 배열 한 개를 만들어 놓고 스레드 i 는 i 번 칸만 올리게 하면, 변수를 나눠 준 것처럼 보입니다.

long count[4]; // 8바이트짜리 넷 = 32바이트
count[i]++;    // 스레드 i 는 제 칸만

네 칸을 합쳐 32바이트라 64바이트 라인 하나에 통째로 들어갑니다. 스레드 넷이 각자 다른 칸만 올리는데도 라인 하나를 넷이 두고 다툽니다. 스레드를 늘릴수록 오히려 시간이 더 걸립니다.

이 꼴이 눈에 안 띄는 까닭은 코드가 멀쩡해 보이기 때문입니다. 데이터 경합도 없고 락도 안 걸었고 결과도 맞습니다. 프로파일링으로 어느 명령어에서 시간이 새는지 재 보기 전까지는 원인이 안 드러납니다.

변수를 벌려 놓는 해법

고치는 방법은 하나로 모입니다. 같이 고쳐지는 변수들을 서로 다른 라인에 앉히는 것입니다.

가장 곧은 방법이 패딩입니다. 변수 뒤에 쓰지 않는 공간을 붙여 다음 변수를 다음 라인으로 밀어냅니다.

struct counter {
    long value;    // 8바이트
    char pad[56];  // 56바이트를 비운다
};                 // 합 64 · 라인 하나

value 하나가 라인 하나를 통째로 차지합니다. 카운터를 이렇게 나란히 놓으면 다음 카운터는 다음 라인에서 시작하므로 둘이 같은 라인에 앉을 일이 없습니다. 라인 안의 배치가 이렇게 달라집니다.

block-beta
columns 8
  t1["패딩 전 · 캐시 라인 하나"]:8
  c0["count 0"] c1["count 1"] c2["count 2"] c3["count 3"] rest["남은 32바이트"]:4
  t2["패딩 후 · 캐시 라인 1"]:8
  v1["value"] p1["pad 56바이트"]:7
  t3["패딩 후 · 캐시 라인 2"]:8
  v2["value"] p2["pad 56바이트"]:7

윗줄이 패딩 전입니다. 8바이트짜리 칸 넷이 한 라인 안에 나란히 앉고 32바이트가 남습니다. 아랫줄 둘이 패딩 후이고, 카운터 하나가 라인 하나를 다 쓰므로 다음 카운터는 다음 라인에서 시작합니다.

다른 방법은 스레드가 도는 동안에는 공유 변수를 아예 안 건드리는 것입니다. 각자 자기 지역 변수에 세었다가 끝에 한 번만 합칩니다. 그러면 도는 내내 라인을 두고 다툴 일이 없고, 공유 비용은 마지막 한 번으로 줄어듭니다.

대가는 메모리입니다. 패딩은 값 하나마다 라인 하나를 차지하므로 카운터가 많으면 그만큼 메모리를 더 씁니다. 라인 크기는 하드웨어마다 다릅니다. 64바이트를 가정하고 박아 둔 패딩은 라인이 더 큰 기계에서 헛일이 됩니다.

진짜 공유와의 경계

같은 변수를 여러 스레드가 고치는 것은 거짓 공유가 아닙니다. 그것은 진짜로 나눠 쓰는 것이라, 라인이 코어 사이를 오가는 것도 데이터를 나눠 쓴 대가입니다.

가르는 물음은 하나입니다. 변수를 서로 다른 라인으로 떼어 놓았을 때 속도가 돌아오는지 보면 됩니다. 돌아오면 거짓 공유이고, 그대로면 진짜 공유입니다.

진짜 공유는 배치를 바꿔서는 못 줄이고 데이터 구조를 바꿔야 줄어듭니다. 카운터 하나를 여럿으로 쪼개 스레드마다 맡기고 읽을 때 더하는 샤딩이 그런 수단입니다. 거짓 공유는 계산을 하나도 안 바꾸고 변수를 어디에 두느냐만 바꿔 없앨 수 있다는 점이 다릅니다.

앞 절의 조건 셋과 이 물음을 이어 붙이면 판정이 이렇게 됩니다.

flowchart TD
    A["스레드들이 다른 코어에서 도나"] -->|아니다| N["거짓 공유가 아니다"]
    A -->|그렇다| B["건드리는 데이터가 같은 라인에 있나"]
    B -->|아니다| N
    B -->|그렇다| C["그중 하나라도 쓰나"]
    C -->|아니다| N
    C -->|그렇다| D["떼어 놓으면 속도가 돌아오나"]
    D -->|그렇다| E["거짓 공유"]
    D -->|아니다| F["진짜 공유"]

같은 이름을 쓰는 다른 분야

프로세서 밖에서도 같은 말을 씁니다. 나눠 쓰는 단위가 데이터의 단위보다 굵은 곳이면 어디서나 같은 일이 벌어지기 때문입니다.

캐시 라인이 파일로, 코어가 클라이언트로 바뀐다고 보면 됩니다. 분산 파일 시스템에서 클라이언트는 일정 기간 그 파일을 자기가 쥐어도 된다는 약속을 서버에게서 받습니다. 이 약속이 리스입니다.

어떤 클라이언트가 리스를 쥔 파일에 다른 클라이언트가 쓰려 하면 서버는 리스를 거둬들여야 합니다. 그런데 리스를 쥔 쪽이 그 파일을 지금 쓰고 있지 않았다면, 파일 접근에 진짜 충돌이 없는데도 충돌이 난 것입니다. 이것을 거짓 공유라고 부릅니다.

데이터베이스의 잠금 단위에서도 같은 말을 씁니다. 행 하나만 고치면 되는데 잠금이 페이지 단위로 걸리면, 같은 페이지의 다른 행을 건드리려는 트랜잭션까지 기다립니다. 고치려는 행은 서로 남남입니다.

세 분야를 같은 축으로 늘어놓으면 이렇습니다.

단위를 잘게 쪼개면 거짓 공유는 줄고 관리 비용은 늘어납니다. 리스 기간을 짧게 잡는 것도, 잠금을 행 단위로 내리는 것도, 변수 사이에 패딩을 넣는 것도 같은 맞바꿈의 서로 다른 얼굴입니다.

관련 항목

거짓 공유가 일어나는 하드웨어 구조

CPU 캐시 · 캐시 라인 · 캐시 일관성 · MESI · 코어 · 메인 메모리 · NUMA · 무효화 · 캐시 핑퐁

거짓 공유를 없애는 수단

패딩 · 메모리 정렬 · 스레드 로컬 저장소 · 샤딩 · 캐시 정렬

변수를 한 라인에 앉히는 데이터 모양

배열 · 구조체 · 지역성 · 메모리 레이아웃

여러 스레드가 같은 메모리를 건드릴 때 생기는 문제

데이터 경합 · 락 경합 · 스핀락 · 원자적 연산 · 컴페어 앤 스왑 · 메모리 장벽 · 메모리 모델 · 락

거짓 공유가 깎아 먹는 지표

처리량 · 지연 · 확장성 · 암달의 법칙 · 캐시 미스

거짓 공유를 찾아내는 도구

프로파일링 · 프로파일러 · perf · 벤치마크 · 성능 카운터

잠금 단위가 굵어 같은 이름을 쓰는 분야

리스 · 잠금 단위 · 파일 잠금 · 페이지 · 트랜잭션 · 데이터베이스