ABA 문제

ABA 문제는 값이 바뀌었다가 제자리로 돌아온 것을 안 바뀐 것으로 믿고 넘어가는 동시성 고장입니다. 값을 먼저 읽고 나중에 그 값이 그대로인지만 보고 고치는 코드에서 일어납니다. 그 사이 다른 쪽이 값을 바꿨다가 원래대로 돌려 놓는 일을 이 확인은 못 알아챕니다. 낡은 판단으로 고친 자료는 조용히 망가집니다.

상세

ABA 문제는 공유된 값이 A → B → A 로 바뀌는 동안 그 변화를 못 보고 지나치는 고장입니다. 이름은 값이 밟는 이 순서에서 왔습니다. 여러 스레드가 락 없이 같은 값을 고치는 코드에서 주로 일어납니다.

이 고장은 CAS(Compare-And-Swap, 비교 후 교체)라는 명령 하나에서 시작합니다. 아래에서는 그 명령이 놓치는 틈이 락 없는 스택을 망가뜨리는 순서를 따라갑니다.

비교 후 교체 명령

CAS는 값을 조건부로 바꾸는 명령입니다. 「지금 값이 내가 기대한 값과 같으면 새 값으로 바꾼다」를 한 번에 해냅니다. 같으면 바꾸고 성공을 알립니다. 다르면 아무것도 안 하고 실패를 알립니다.

「한 번에」가 핵심입니다. 비교와 교체 사이에 다른 스레드가 끼어들 틈이 없습니다. 이렇게 중간에 끊기지 않는 연산을 원자적 연산이라고 부릅니다.

CAS를 쓰는 까닭은 락을 피하려는 데 있습니다. 락을 쥔 스레드가 멈추면 그 락을 기다리는 스레드도 모두 멈춥니다. CAS로 짠 코드에서는 아무도 기다리지 않습니다. 실패한 스레드는 값을 다시 읽고 다시 시도합니다.

이렇게 락 없이 짠 자료구조를 락 프리 자료구조라고 합니다. 이런 코드는 대개 같은 네 단계로 돕니다.

1. 공유된 값을 읽어 둡니다
2. 읽은 값을 바탕으로 새 값을 계산합니다
3. CAS로 「읽어 둔 값이 그대로면 새 값으로」를 요청합니다
4. 실패하면 1로 돌아갑니다

비교가 놓치는 것

책상을 떠나기 전에 커피잔을 봐 둡니다. 돌아와 보니 같은 잔이 같은 높이로 차 있습니다. 그 사이 누가 마시고 새로 채워 두었어도 잔만 봐서는 알 수 없습니다.

CAS가 보는 것도 지금 값 하나뿐입니다. 값이 그동안 어떻게 바뀌어 왔는지는 보지 않습니다. 그래서 3단계의 CAS는 「1단계 뒤로 아무도 안 건드렸다」를 확인해 주지 못합니다. 「지금 값이 1단계에서 본 값과 같다」만 확인합니다.

두 확인이 갈리는 때는 값이 A → B → A 로 오갔을 때입니다. 2단계의 새 값을 읽은 값 하나로만 계산했다면 이때도 해가 없습니다. 새 값이 다른 데이터에도 기댔다면 그 데이터는 이미 바뀌었을 수 있습니다. 다음 소절의 스택이 그런 경우입니다.

스택에서 터지는 순서

스택은 나중에 넣은 것을 먼저 꺼내는 자료구조입니다. 락 없이 짤 때는 흔히 노드를 사슬로 잇습니다. 각 노드는 자기 바로 아래 노드를 가리킵니다. 공유 변수 top 은 맨 위 노드를 가리킵니다.

노드를 가리키는 값은 포인터, 곧 메모리 주소입니다. 그러니 top 에 거는 CAS는 주소가 같은지를 비교합니다.

꺼내기(pop)도 「비교 후 교체 명령」 소절의 네 단계를 밟습니다. 아래 의사 코드의 첫 줄이 1단계(읽기), 둘째 줄이 2단계(새 값 계산), 셋째 줄이 3단계(CAS)입니다. 4단계(실패하면 다시)는 이 코드에서 뺐습니다. 오른쪽 주석은 스택이 위에서부터 A · B · C 일 때의 값입니다.

Node old = top.get();          // 노드 A
Node next = old.next;          // 노드 B
top.compareAndSet(old, next);  // true

아무도 끼어들지 않으면 이 세 줄은 옳게 돕니다. A가 빠지고 B가 꼭대기가 됩니다. 고장은 둘째 줄과 셋째 줄 사이에 다른 스레드가 끼어들 때 납니다.

sequenceDiagram
    participant T1 as 스레드 1
    participant S as top
    participant T2 as 스레드 2
    T1->>S: 읽는다 · 꼭대기 A, 그 아래 B
    Note over T1: 셋째 줄 앞에서 멈춘다
    T2->>S: A를 꺼낸다
    T2->>S: B를 꺼낸다
    Note over T2: A의 메모리를 해제한다
    T2->>S: 새 노드를 넣는다 · 주소가 A와 같다
    T1->>S: CAS · 꼭대기가 A면 B로
    S-->>T1: 성공
    Note over S: 이제 top 은 B

스레드 1은 A와 B를 읽은 채 멈춥니다. 그 사이 스레드 2가 A와 B를 꺼내고 A의 메모리를 해제합니다. 스택에는 C만 남습니다.

스레드 2가 이어서 새 노드를 하나 넣습니다. 이때 새 노드가 A가 쓰던 메모리를 받는 일이 흔합니다. 메모리 할당기는 방금 돌려받은 메모리를 다음 요청에 먼저 내주곤 하기 때문입니다. 스택은 이제 위에서부터 A · C 입니다.

꼭대기 주소가 처음과 같은 A로 돌아왔습니다. 스레드 1이 깨어나 CAS를 부르면 비교가 통과합니다. top 은 B로 바뀝니다. B는 스레드 2가 이미 꺼내 간 노드입니다.

flowchart TD
    subgraph S0["처음"]
        P0["top"] --> A0["A"] --> B0["B"] --> C0["C"]
    end
    subgraph S1["스레드 2가 지나간 뒤"]
        P1["top"] --> A1["A · 같은 주소의 새 노드"] --> C1["C"]
    end
    subgraph S2["스레드 1의 CAS 뒤"]
        P2["top"] --> B2["B · 이미 꺼내 간 노드"]
        C2["C · 사슬에서 끊김"]
    end
    S0 ~~~ S1 ~~~ S2

맨 아래 그림에서 망가진 것이 둘 보입니다. 스택에 남아 있던 C는 사슬에서 끊겨 사라집니다. 이미 꺼내 간 B는 꼭대기에 다시 올라 한 번 더 꺼내질 수 있습니다. B의 메모리가 이미 해제됐다면 해제된 메모리를 읽게 됩니다.

재현되는 조건

셋이 다 서면 ABA 문제가 터집니다.

1. 스레드 하나가 공유 값을 읽어 둡니다. 나중에 「값이 같은지」만 보고 새 값을 씁니다
2. 그 틈에 다른 스레드가 값을 두 번 이상 바꿔 처음과 같은 값으로 돌려 놓습니다
3. 써 넣을 새 값이 읽어 둔 값 말고 다른 것에도 기댑니다. 스택에서는 꼭대기 노드의 「바로 아래 노드」가 그것입니다

셋째가 빠지면 A → B → A 가 일어나도 해가 없습니다. 카운터에 1을 더하는 코드가 그렇습니다. 5를 읽고 6을 쓰려는 사이 값이 5 → 7 → 5 로 오갔다고 해 봅시다. 6을 쓰는 것은 여전히 옳습니다. 값 자체 말고는 기댄 것이 없기 때문입니다.

둘째에서 값이 되돌아오는 길은 여럿입니다. 해제된 메모리가 새 노드에 다시 쓰이는 경우가 가장 흔합니다. 노드를 객체 풀에 모아 두고 다시 꺼내 쓰는 경우도 같습니다. 상태 값처럼 몇 가지 값만 오가는 칸에서도 되돌아옵니다.

가비지 컬렉션이 있는 언어

가비지 컬렉션(GC, Garbage Collection)은 아무도 가리키지 않는 메모리를 런타임이 알아서 회수하는 방식입니다. 자바나 Go 같은 언어가 이 방식을 씁니다.

GC가 있으면 스택 예의 가장 흔한 경로가 막힙니다. 스레드 1이 A를 쥐고 있는 동안 A의 메모리는 회수되지 않습니다. 그래서 새 노드가 A의 주소를 물려받지 못합니다.

그렇다고 ABA 문제가 없어지지는 않습니다. 노드를 풀에 모아 다시 쓰면 같은 객체가 다시 꼭대기에 오릅니다. 정수나 상태 값을 비교하는 코드도 셋째 조건까지 서면 언어와 상관없이 터집니다.

백엔드 코드에서 만나는 꼴

같은 모양이 데이터베이스에서도 나옵니다. 이런 코드는 먼저 행을 읽습니다. 나중에 「그 컬럼이 그대로면 고친다」는 조건을 붙여 씁니다. SQL(Structured Query Language, 구조화 질의 언어)의 WHERE 조건이 CAS의 비교 노릇을 합니다.

작업자 둘이 주문을 나눠 처리한다고 해 봅시다. 작업자 1이 상태가 READY 인 7번 주문을 읽습니다. 주문 내용으로 결제 금액 30000원을 계산합니다.

그 사이 작업자 2가 같은 7번 주문을 먼저 처리해 상태를 PAID 로 바꿉니다. 고객이 주문 내용을 바꾸자 같은 7번 행이 다시 READY 가 됩니다. 상태가 READY → PAID → READY 로 돌아왔습니다. 이제 작업자 1이 쓰기를 보냅니다.

UPDATE orders
SET status = 'PAID', amount = 30000
WHERE id = 7
  AND status = 'READY';   -- 1행 바뀜

조건이 통과해 한 행이 바뀝니다. 그런데 30000원은 바뀌기 전 주문 내용으로 계산한 금액입니다. 7번 행은 바뀐 주문 내용에 옛 금액을 단 채 결제 완료가 됐습니다.

막으려면 비교할 컬럼을 상태가 아니라 버전 번호로 바꿉니다. 버전은 행이 바뀔 때마다 하나씩 오릅니다. 한 번 지나간 번호로는 돌아오지 않습니다. 이 방식이 낙관적 잠금입니다.

UPDATE orders
SET status = 'PAID', amount = 30000,
    version = version + 1
WHERE id = 7
  AND version = 3;        -- 0행 바뀜

작업자 1이 읽을 때 버전은 3이었습니다. 작업자 2의 처리와 고객의 변경이 버전을 더 올렸으므로 한 행도 안 바뀝니다. 작업자 1은 0행을 보고 주문을 다시 읽습니다.

캐시에도 「키의 지금 값이 old 면 new 로 바꾼다」 꼴의 연산이 있습니다. 이 연산도 값만 비교하므로 같은 꼴에 걸릴 수 있습니다.

알아채기 어려운 까닭

ABA 문제는 오류를 내지 않습니다. CAS도 UPDATE 도 성공으로 끝납니다. 망가진 자료는 한참 뒤 다른 코드에서 드러납니다. 사라진 노드, 두 번 쓰인 노드, 옛 금액으로 끝난 주문 같은 모습입니다.

터지는 타이밍도 드뭅니다. 한 스레드가 읽고 쓰는 짧은 틈에 다른 스레드가 두 번 이상 끼어들어야 합니다. 로그를 넣거나 디버거를 붙이면 틈의 길이가 달라져 재현이 안 되기도 합니다.

막는 방법

방법은 넷입니다. 모두 「값이 같다」 대신 「그 사이 아무도 안 바꿨다」를 확인하게 만듭니다.

첫째가 가장 널리 쓰입니다. A → B → A 가 버전을 달고 (A, 1) → (B, 2) → (A, 3) 이 됩니다. 값은 돌아왔어도 버전은 안 돌아옵니다. 아래 의사 코드의 cas 는 값과 버전을 함께 비교합니다.

seen = ref.get();          // A · 버전 1
// 그 사이 다른 스레드가 A→B→A
ref.get();                 // A · 버전 3
ref.cas(seen, "D");        // false

버전이 1에서 3으로 올랐으므로 CAS는 실패합니다. 실패한 스레드는 값을 다시 읽고 처음부터 계산합니다.

값과 버전은 한 번에 비교해야 합니다. 따로 비교하면 두 비교 사이에 다시 틈이 생깁니다. 그래서 포인터 값 안에서 주소로 안 쓰는 비트에 버전을 함께 넣기도 합니다. 이렇게 버전을 붙인 포인터를 태그 포인터라고 부릅니다.

자바에서는 표준 라이브러리의 AtomicStampedReference 가 이 일을 합니다. 참조와 정수 버전을 한 번에 비교하고 한 번에 바꿉니다.

둘째는 스택 예의 뿌리를 끊습니다. 스레드 1이 A를 보고 있는 동안 A의 메모리가 새 노드에 넘어가지 않으면 주소가 되살아나지 않습니다. GC가 있는 언어에서는 런타임이 이 일을 맡습니다.

GC가 없는 언어에서 흔히 쓰는 방식이 둘 있습니다. 하나는 해저드 포인터입니다. 스레드가 지금 보고 있는 노드를 모두가 보는 목록에 올려 둡니다. 이 목록에 있는 노드는 해제를 미룹니다.

다른 하나는 에포크 기반 회수입니다. 시간을 세대(에포크)로 나눕니다. 꺼낸 노드는 곧바로 해제하지 않고 모아 둡니다. 그때 돌던 스레드가 모두 다음 세대로 넘어간 뒤에야 모은 노드를 해제합니다.

셋째는 일부 CPU가 갖춘 명령 한 쌍입니다. 읽는 쪽을 LL(Load Linked, 표시를 거는 읽기)이라고 부릅니다. LL은 값을 읽으면서 그 주소에 표시를 겁니다.

쓰는 쪽은 SC(Store Conditional, 조건부 쓰기)입니다. SC는 표시를 건 뒤로 누군가 그 주소에 썼으면 실패합니다. 값이 돌아왔는지는 따지지 않습니다. 그래서 ABA 문제가 끼어들 틈이 없습니다.

관련 항목

ABA 문제와 이름이 나란히 불리는 동시성 고장

경쟁 상태 · 데드락 · 라이브락 · 기아 · 우선순위 역전 · 갱신 손실

ABA 문제를 부르는 원자적 명령

CAS · 원자적 연산 · 원자성 · 메모리 배리어 · 메모리 모델

ABA 문제가 터지는 락 없는 자료구조

락 프리 · 논블로킹 알고리즘 · 락 프리 스택 · 락 프리 큐 · 스택 · 연결 리스트

ABA 문제에서 같은 주소를 되살리는 메모리 재사용

포인터 · 메모리 할당기 · 객체 풀 · 해제 후 사용 · 이중 해제 · 댕글링 포인터

ABA 문제를 막는 수단

태그 포인터 · 해저드 포인터 · 에포크 기반 회수 · 가비지 컬렉션 · 참조 카운팅 · 락 · 뮤텍스

ABA 문제가 일어나는 동시 실행 환경

동시성 · 스레드 · 멀티스레딩 · 문맥 교환 · 스케줄러

ABA 문제와 같은 비교 후 쓰기 꼴을 쓰는 백엔드 장치

낙관적 잠금 · 조건부 요청 · ETag · 캐시 · Ehcache · 트랜잭션 · 격리 수준