compare-and-set

compare-and-set 은 여러 작업이 함께 고치는 값을 잠그지 않고 안전하게 바꾸는 연산입니다. 지금 값과 내가 아까 읽은 값을 견주어 둘이 같을 때만 새 값을 씁니다. 견주기와 쓰기가 한 동작으로 일어나서 그 틈에 다른 작업이 끼어들지 못합니다. 값이 그새 달라졌으면 아무것도 쓰지 않고 실패를 알려 줍니다.

상세

이 절은 compare-and-set 이 받는 값과 돌려주는 것, 실패 뒤 다시 시도하는 반복, 그리고 이 연산의 한계를 카운터 하나를 예로 들어 차례로 봅니다.

이 연산은 스레드 여럿이 같은 값을 고칠 때 씁니다. 스레드는 한 프로그램 안에서 따로 도는 실행 흐름입니다. 개요에서 「작업」이라고 부른 것이 대개 이것입니다.

이름은 줄여서 CAS(Compare-And-Set, 비교 후 설정)라고 부릅니다. compare-and-swap(비교 후 교체)도 같은 연산을 가리키고 줄임말도 똑같이 CAS 입니다.

두 이름을 굳이 가르기도 합니다. 성공했는지를 참·거짓으로 돌려주면 compare-and-set, 바꾸기 전의 값을 돌려주면 compare-and-swap 이라고 부르는 식입니다. 돌려받는 것만 다르고 하는 일은 같습니다.

세 값을 받는 한 동작

CAS 는 값 셋을 받습니다. 바꿀 메모리 위치, 그 위치에 있으리라 기대하는 값, 새로 쓸 값입니다. 위치의 지금 값이 기대한 값과 같으면 새 값을 쓰고 성공을 알립니다. 다르면 아무것도 쓰지 않고 실패를 알립니다.

아래는 그 동작을 의사 코드로 적은 것입니다. 함수 본문 전체가 한 번에 일어난다고 보면 됩니다.

cas(위치, 기대값, 새값):
    if *위치 != 기대값:
        return false   // 아무것도 안 씀
    *위치 = 새값
    return true        // 새 값을 씀

「한 번에」가 이 연산의 전부입니다. 견주는 순간과 쓰는 순간 사이에 다른 스레드가 값을 바꿀 수 없습니다. 밖에서 보기에 쪼개지지 않고 한 번에 일어나는 연산을 원자적 연산이라고 합니다.

이 보장은 CPU(Central Processing Unit, 중앙 처리 장치)가 줍니다. 대부분의 CPU 는 견주기와 쓰기를 한 번에 하는 명령을 갖고 있습니다. 프로그램은 이 명령을 언어의 라이브러리를 거쳐 부릅니다.

읽고 고치고 쓰는 사이의 틈

count++ 한 줄은 CPU 에게는 세 단계입니다. 값을 읽고, 1을 더하고, 다시 씁니다. 두 스레드가 동시에 이 줄을 돌리면 둘 다 10을 읽고 둘 다 11을 쓸 수 있습니다. 두 번 올렸는데 값은 한 번만 올라갑니다.

sequenceDiagram
    participant A as 스레드 A
    participant M as 메모리
    participant B as 스레드 B
    A->>M: 읽기
    M-->>A: 10
    B->>M: 읽기
    M-->>B: 10
    B->>M: 쓰기 11
    A->>M: 쓰기 11
    Note over A,B: 두 번 올렸는데 값은 11

그림에서 B 가 쓴 11 을 A 가 다시 11 로 덮어씁니다. 이렇게 남의 갱신을 덮어써서 잃는 일을 갱신 손실이라고 합니다.

흔한 해법은 락입니다. 락은 한 번에 한 스레드만 그 코드를 돌게 문을 잠그는 장치입니다. 대가는 기다림입니다. 락을 쥔 스레드가 느려지거나 멈추면 나머지가 모두 그 뒤에 섭니다.

CAS 는 다른 길을 갑니다. 미리 잠그지 않고 일단 계산한 뒤, 쓰는 순간에만 값이 바뀌었는지 봅니다. 바뀌었으면 쓰지 않으므로 남의 갱신을 덮어쓰지 않습니다.

실패하면 다시 읽는 반복

CAS 한 번으로 끝나는 일은 드뭅니다. 실패하면 값을 다시 읽고, 다시 계산하고, 다시 CAS 를 겁니다. 성공할 때까지 이 일을 되풀이하는 모양을 CAS 루프라고 부릅니다.

아래 그림은 두 스레드가 10을 동시에 1씩 올리는 장면입니다. B 가 먼저 성공하고, A 는 한 번 실패한 뒤 다시 읽어서 성공합니다.

sequenceDiagram
    participant A as 스레드 A
    participant M as 메모리
    participant B as 스레드 B
    A->>M: 읽기
    M-->>A: 10
    B->>M: 읽기
    M-->>B: 10
    B->>M: CAS(10 → 11)
    M-->>B: 성공 · 값은 11
    A->>M: CAS(10 → 11)
    M-->>A: 실패 · 값이 10이 아님
    A->>M: 다시 읽기
    M-->>A: 11
    A->>M: CAS(11 → 12)
    M-->>A: 성공 · 값은 12

끝난 값은 12입니다. 두 번 올린 것이 둘 다 남았습니다. A 는 실패를 보고 남이 먼저 바꾼 것을 알았습니다. 그래서 새 값 위에서 다시 계산했습니다.

언어들은 이 연산을 라이브러리로 줍니다. 아래는 Java 의 AtomicInteger 로 CAS 한 번의 성공과 실패를 본 것입니다. AtomicInteger 는 CAS 로 고치는 정수 하나를 담는 클래스입니다.

var n = new AtomicInteger(10);
n.compareAndSet(10, 11);  // true
n.get();                  // 11
n.compareAndSet(10, 12);  // false
n.get();                  // 11

두 번째 compareAndSet 은 기대한 값 10이 지금 값 11과 달라서 실패합니다. 값은 손대지 않은 11로 남습니다.

CAS 루프는 이렇게 생깁니다. 값을 두 배로 만드는 일을 락 없이 짠 것입니다.

int old, next;
do {
    old = n.get();
    next = old * 2;
} while (!n.compareAndSet(old, next));

old 는 이번에 읽은 값입니다. next 는 그걸로 계산한 새 값입니다. CAS 가 실패하면 old 가 낡은 값이라는 뜻이므로 처음부터 다시 읽습니다. AtomicInteger 의 updateAndGet 같은 메서드는 이 루프를 안에 감춰 둔 것입니다.

언어마다 다른 이름

같은 연산을 언어마다 다른 이름으로 줍니다. 돌려주는 것도 조금씩 다릅니다.

C++ 처럼 실패할 때 지금 값을 같이 돌려주면 루프에서 다시 읽는 단계를 아낄 수 있습니다.

되돌아온 값

CAS 는 값이 같은지만 봅니다. 중간에 아무도 건드리지 않았는지는 묻지 않습니다. 값이 10 에서 20 으로 바뀌었다가 다시 10 으로 돌아오면, CAS 는 아무 일도 없었던 것으로 보고 성공합니다.

카운터 같은 값에서는 대개 괜찮습니다. 10이 11이 됐다가 다시 10이 됐어도, 10 위에서 계산한 결과는 맞습니다.

탈이 나는 것은 값이 포인터일 때입니다. 포인터는 메모리 주소를 담은 값입니다. 같은 주소에 전혀 다른 데이터가 새로 놓였을 수 있습니다. 그때 CAS 가 성공하면 옛 데이터를 보고 계산한 새 값이 쓰여서, 자료구조가 이미 빠져나간 데이터를 가리키게 됩니다.

값이 처음 값, 다른 값, 처음 값 차례로 돈다고 해서 이 고장을 A-B-A 문제라고 부릅니다. 이름의 A 와 B 는 서로 다른 두 값을 가리키는 기호입니다.

흔한 처방은 값 옆에 버전 번호를 붙이고 바꿀 때마다 1씩 올리는 것입니다. 값이 돌아와도 번호는 안 돌아오므로 CAS 가 실패합니다. 아래 그림은 고장 장면과 이 처방을 한데 그린 것입니다.

sequenceDiagram
    participant T1 as 스레드 1
    participant M as 메모리
    participant T2 as 스레드 2
    T1->>M: 읽기
    M-->>T1: 10
    T2->>M: CAS(10 → 20)
    T2->>M: CAS(20 → 10)
    T1->>M: CAS(10 → 11)
    M-->>T1: 성공
    Note over T1,T2: 중간에 두 번 바뀐 것을 스레드 1 은 모른다
    Note over M: 버전을 붙이면 (10, 1) → (20, 2) → (10, 3) 이라 기대값 (10, 1) 은 실패

다투는 스레드가 많을 때

같은 값을 많은 스레드가 쉴 새 없이 고치면 CAS 가 자주 실패합니다. 실패한 스레드는 다시 읽고 다시 계산하므로 그만큼 CPU 시간이 버려집니다. 한 값을 두고 여러 스레드가 다투는 상황을 경합이라고 합니다.

경합을 줄이는 처방이 둘 있습니다. 하나는 실패한 뒤 잠깐 쉬었다 다시 시도하는 백오프입니다. 쉬는 동안 다른 스레드가 먼저 끝내므로 부딪히는 횟수가 줍니다.

다른 하나는 값 하나를 여러 칸으로 나누는 것입니다. 스레드마다 다른 칸을 고치게 하고, 합계가 필요할 때만 칸을 더합니다.

flowchart TD
    subgraph one["값 하나"]
        A1["스레드 A"] --> V["값"]
        B1["스레드 B"] --> V
        C1["스레드 C"] --> V
    end
    subgraph two["칸으로 나눔"]
        A2["스레드 A"] --> K1["칸 1"]
        B2["스레드 B"] --> K2["칸 2"]
        C2["스레드 C"] --> K3["칸 3"]
        K1 --> S["합계"]
        K2 --> S
        K3 --> S
    end
    one ~~~ two

위쪽은 세 스레드가 한 값을 두고 다투는 모양입니다. 아래쪽은 저마다 제 칸만 고치므로 서로 부딪히지 않습니다. Java 의 LongAdder 가 카운터를 이렇게 나눕니다.

메모리 순서

CAS 는 값을 바꾸는 일 말고 하나를 더 합니다. CAS 앞에서 한 쓰기가 CAS 뒤로 밀려나지 않게 막습니다. 이 소절은 그것이 왜 필요한지를 두 스레드가 데이터를 넘겨받는 장면으로 봅니다.

CPU 와 컴파일러는 빠르게 돌리려고 읽기와 쓰기의 순서를 바꿔 실행하기도 합니다. 한 스레드 안에서는 결과가 같아서 티가 나지 않습니다. 탈은 다른 스레드가 그 값들을 읽을 때 납니다.

스레드 A 가 데이터를 채운 뒤 「완성」 표시를 0 에서 1 로 바꾼다고 해 봅시다. 스레드 B 는 표시가 1 이면 데이터를 읽습니다. A 의 두 쓰기 순서가 뒤바뀌면, B 는 표시가 1 인 것을 보고도 아직 빈 데이터를 읽을 수 있습니다.

어떤 순서 바꿈을 허용하는지 정한 규칙이 메모리 모델입니다. 이 규칙은 한 스레드가 쓴 값이 다른 스레드에게 언제 보이는지를 정합니다. 「보인다」는 다른 스레드가 그 값을 읽으면 새 값이 나온다는 뜻입니다.

Java 의 compareAndSet 은 이 순서를 엄격하게 지킵니다. A 가 CAS 앞에서 채운 데이터는 CAS 뒤로 밀리지 않습니다. 그래서 B 가 표시에서 1 을 읽었다면, 그 뒤에 읽는 데이터는 A 가 채운 값입니다.

sequenceDiagram
    participant A as 스레드 A
    participant D as 데이터
    participant F as 완성 표시
    participant B as 스레드 B
    A->>D: 채운다
    A->>F: CAS(0 → 1)
    Note over A,D: CAS 앞의 쓰기는 CAS 뒤로 밀리지 않는다
    B->>F: 읽기
    F-->>B: 1
    B->>D: 읽기
    D-->>B: A 가 채운 값
    Note over D,B: 순서를 안 묶으면 빈 데이터가 나올 수 있다

락 없이 짠 자료구조가 데이터를 다 채운 뒤 CAS 로 「완성」을 알릴 수 있는 것이 이 덕분입니다.

데이터베이스와 분산 저장소의 compare-and-set

compare-and-set 의 생각은 메모리 밖에서도 씁니다. 데이터베이스 행에 버전 칸을 두고, 고칠 때 버전이 내가 읽은 값일 때만 쓰게 하는 방식이 그 예입니다. 이를 낙관적 잠금이라고 부릅니다.

이름에 잠금이 들어 있지만 실제로 잠그지는 않습니다. 남이 끼어들지 않으리라 낙관하고 일단 진행한 뒤, 쓸 때만 확인한다는 뜻입니다.

SQL(Structured Query Language, 데이터베이스 질의 언어)로 쓰면 이렇습니다.

UPDATE item
   SET stock = 9, version = 4
 WHERE id = 1
   AND version = 3;   -- 1행 또는 0행

버전이 3인 채로 남아 있으면 1행이 바뀌고 버전이 4가 됩니다. 다른 요청이 먼저 고쳤으면 버전이 이미 4라서 0행이 바뀝니다. 애플리케이션은 바뀐 행이 0인 것을 보고 실패를 알아챕니다.

etcd 는 여러 서버에 걸쳐 키와 값을 담는 저장소입니다. 키의 수정 번호가 기대한 값일 때만 쓰는 요청을 받습니다.

ETag(entity tag, 엔티티 태그)는 서버가 자원의 판마다 붙이는 꼬리표입니다. HTTP(HyperText Transfer Protocol) 요청의 If-Match 헤더에 ETag 를 실어 보내면, 서버는 자원이 그 판 그대로일 때만 고칩니다.

쓸 때와 안 쓸 때

CAS 는 락 프리 자료구조의 재료입니다. 락 프리는 어느 스레드가 도중에 멈춰도 나머지 중 누군가는 계속 일을 끝내 가는 성질입니다. 락을 쥔 스레드 하나가 멈추면 전부 서는 락과 갈리는 대목이 이것입니다.

어느 때 CAS 를 고르고 어느 때 다른 수단을 고르는지는 아래와 같습니다.

마지막 줄은 CAS 루프의 성질에서 나옵니다. 아래 그림처럼 CAS 가 실패하면 루프 몸통 전체가 다시 돕니다.

flowchart TD
    subgraph body["루프 몸통"]
        R["지금 값 읽기"] --> C["새 값 계산"] --> X["CAS"]
    end
    X --> Q{"성공?"}
    Q -->|예| E["끝"]
    Q -->|아니오| R

루프 몸통 안에서 메일을 보내거나 다른 서버를 부르면, CAS 가 실패한 횟수만큼 그 일이 되풀이됩니다. 루프 안에는 다시 해도 괜찮은 계산만 둡니다.

관련 항목

compare-and-set 이 속하는 상위 분류

동시성 · 동시성 제어 · 논블로킹 알고리즘

compare-and-set 이 지켜 주는 성질

원자성 · 선형화 가능성 · 메모리 모델 · happens-before · 메모리 배리어

compare-and-set 위에 짓는 구현

락 프리 · wait-free · 스핀락 · AtomicInteger · LongAdder · CAS 루프 · 트라이버 스택

compare-and-set 과 나란히 서는 원자적 명령

test-and-set · fetch-and-add · load-linked · cmpxchg · 원자적 교환

compare-and-set 대신 쓰는 동기화 수단

락 · 뮤텍스 · 세마포어 · 임계 구역 · 트랜잭셔널 메모리

compare-and-set 을 쓰다 부딪히는 고장

ABA 문제 · 경합 · 라이브락 · 기아 · 백오프 · 갱신 손실 · 경쟁 상태

compare-and-set 을 메모리 밖으로 넓힌 방식

낙관적 잠금 · ETag · If-Match · etcd · 조건부 쓰기 · 버전 번호

compare-and-set 을 내주는 하드웨어와 언어

CPU · x86 · Java · C++ · Go