[Concurrency] ABA Problem

ABA 문제는 Lock-Free 알고리즘, 특히 Compare and Swap 기반의 구현체에서 발생할 수 있는 대표적인 동시성 버그 패턴이다.
이에 대한 충분한 이해 없이는 의도대로 동작하는 Lock-Free 자료구조를 만들 수 없다.

일반적으로 non-GC 언어에서만 발생한다.

기본 구현 (Linked Stack)

먼저 기본적인 Lock-Free Stack 구현체를 만들어보겠다. 언어는 Rust고, 단순한 형태로 구현했다.

use std::ptr;
use std::sync::atomic::{AtomicPtr, Ordering};
use std::sync::Arc;

struct Node {
    value: i32,
    next: *mut Node,
}

struct Stack {
    head: AtomicPtr<Node>,
}

unsafe impl Sync for Stack {}
unsafe impl Send for Stack {}

impl Stack {
    fn new() -> Self {
        Stack {
            head: AtomicPtr::new(ptr::null_mut()),
        }
    }

    fn push(&self, value: i32) {
        let new_node = Box::into_raw(Box::new(Node {
            value,
            next: ptr::null_mut(),
        }));

        let mut current_head = self.head.load(Ordering::Relaxed);

        loop {
            unsafe {
                (*new_node).next = current_head;
            }

            match self.head.compare_exchange(
                current_head,
                new_node,
                Ordering::Release,
                Ordering::Relaxed,
            ) {
                Ok(_) => break,                   // 성공적으로 교체됨
                Err(head) => current_head = head, // 실패, 새 head 사용해 재시도
            }
        }
    }

    fn pop(&self) -> Option<i32> {
        let mut current_head = self.head.load(Ordering::Relaxed);

        loop {
            if current_head.is_null() {
                return None; // 스택이 비어 있음
            }

            let next = unsafe { (*current_head).next };

            match self.head.compare_exchange(
                current_head,
                next,
                Ordering::Release,
                Ordering::Relaxed,
            ) {
                Ok(_) => {
                    let value = unsafe { (*current_head).value };
                    // 메모리 누수 방지를 위해 Box로 변환하여 소멸
                    let _ = unsafe { Box::from_raw(current_head) };
                    return Some(value);
                }
                Err(head) => current_head = head, // 실패, 새 head 사용해 재시도
            }
        }
    }
}

#[tokio::main]
async fn main() {
    let stack = Arc::new(Stack::new());

    // 초기 상태: [1, 2] (위에서부터)
    stack.push(2);
    stack.push(1);
    println!("초기 스택: [1, 2]");

    let a = stack.pop();
    println!("팝: {:?}", a); // 1
    let b = stack.pop();
    println!("팝: {:?}", b); // 2
}

일단은 싱글스레드에서 잘 동작한다.

구현도 간단히 한번 풀어보겠다.

사실 막 그렇게 특별할 것은 없다.
Stack이라서 Push할때는 맨 앞의 head에 새 노드를 할당하고, 새 노드가 (구) head를 가리키게 한다.

근데 Push/Pop은 동시적으로 들어올 수 있고 head가 언제든 바뀌어있을 수 있기 때문에, compare_exchange(compare and swap)으로 본인이 알던 정보가 최신일 때만 수정을 하도록 했다.
아니면 맞을때까지 뺑뺑이를 돈다. 그래서 data race가 심할 때는 루프 뺑뺑이돌면서 CPU를 혹사시킬 수 있다.

pop도 방법론은 비슷하다.

head를 넣고 밀어내는게 아니라, head를 빼고 끌어당기는게 다를 뿐이다.

ABA 문제

그럼 뭐가 문제일까? 그냥 봐서는 잘 동작할 것처럼 보인다.
하지만 이면에는 생각보다 난감한 그.. 뭐시기가 존재해서 꼬이는 상황이 발생할 수 있다.

시나리오는 이렇다.

1. 첫번째 스레드가 pop/push에 앞서 head 데이터를 Load한다. = A(v1)

2. 첫번째 스레드가 일을 끝내기 전에, 두번째 스레드가 head를 pop한다. = (없음)

3. 두번째 스레드가 B를 push한다. = B

4. 두번째 스레드가 A를 push한다. = A(v2)->B

5. 첫번째 스레드가 A(v1)을 A(v2)와 다르다는 것을 알지 못해(가정) A(v1)를 잘못된 형태로 CAS 처리해버린다.

6. 여기서 C를 push할 경우에는 C->A(v1)??, A(v2)->B 같은 형태로 연결이 꼬여버린다.

7. pop을 할 경우에는 없다고 생각하고 head를 비워버리나, A(v2)->B가 누수된 형태로 붕 떠버린다.

그림으로 나타내면 이렇다.

참고로 A -> B -> A 이런 설명이 유래가 되어서 ABA 문제라고 부른다.

근데
*첫번째 스레드가 A(v1)을 A(v2)와 다르다는 것을 알지 못해(가정) *

• 이 부분은 약간 혼란스럽게 느껴질 수 있다. 현재 구현 버전에서는 CAS 단위가 포인터이기 때문이다.

• 할당이 다른 시기에 되었다면 A(v1)와 A(v2)의 주소값이 다르다고 판단할 수 있을텐데, 이게 어떻게 가능할까?

**문제: 메모리 재사용 **

• 사실 메모리의 주소라는 것은 그다지 unique하지 않고, 재사용이 되기도 좋은 대상이다.

• 대부분의 메모리 allocator는 동일한 크기의 할당 요청을 받으면 최근에 사용되었다 해제된 메모리 블록을 다시 재사용하게 주기도 한다.

• 게다가 스레드 로컬 캐시를 적극 사용하는 allocator의 경우에는 동일 스레드에서 메모리를 재할당할 경우 같은 주소를 받을 가능성이 특히나 더 높다.

GC 언어

• GC 언어들은 의도한 것은 아니지만 이 문제를 에둘러서 회피한다.

• 메모리 재사용이 발생하려면 첫번째 A(v1)가 할당해제되어야 하는데, 애초에 Load해서 들고있는 시점에서는 참조가 존재해서 할당해제를 하지 않고, 그 동안에는 당연히 그 주소를 다시 쓰지도 않기 때문이다.

• 그래서 Java 등 GC 언어들에서는 고민을 별로 할 필요가 없는 문제다.

이 문제에 대한 해결책은 이것저것 있지만, 가장 대표적인 것은 2가지 정도다.

해결책 1: Tagged Pointer

일반적인 해결책 중 하나는, 아예 주소 공간에다가 추가적인 태그값을 넣어서 할당되거나 수정될때마다 값이 고유성을 가지게끔 만드는 것이다. 그러면 실제 주소 공간이 같더라도, 일부 비트가 달라서 CAS 연산이 실패할 것이다.
어차피 CAS는 주소 자체를 의미있게 보는게 아니라 주소라는 정수값을 기반으로 처리하는 것이기 때문이다.

64비트 환경에서는 비트 공간이 좀 남기 때문에 사용할 수 있는 꼼수다. 보통 10-20비트 정도는 메타데이터로 응용할 수 있다.

해결책 2: 메모리 할당 해제 지연시키기

ABA 문제가 발생하는 원인 중 하나는, 할당이 해제된 뒤에 그 주소를 다시 줄 수 있기 때문이다.

그러면... 해제를 안시키면 그 주소를 다시 안주니까 되는거 아닌가?

그래서 아예 객체의 삭제를 미뤄서 재사용을 방지하는 방법도 몇가지 존재한다.

**Hazard Pointer **

메모리 해제 지연의 대표적인 접근 방법이다.
현재 사용되고 있는, 해제되지 말아야 하는 주소 목록을 Hazard Pointer라고 해서 중앙화해서 관리한다.
그리고 Hazard Pointer 목록에 속해있는 주소는 할당해제를 하지 않게끔 하는 것이다.

https://chfhrqnfrhc.tistory.com/entry/ABA-Problem-1
근데 그냥 해제를 미루기만 하면 누수가 될테니, RetireList라는 해제용 풀을 또 스레드별로 만들어서 관리한다.
pop으로 인해서 메모리를 해제해야 한다면, 그걸 해제하는게 아니라 객체를 RetireList로 옮긴 다음에 Hazard Pointer 리스트와 비교해서 괜찮으면 lazy하게 제거하는 것이다.

추가적인 성능 소모가 좀 일어날 수 있지만, ABA와 메모리 재사용 문제는 회피할 수 있다.

참조
https://chfhrqnfrhc.tistory.com/m/entry/ABA-Problem-1
https://minikin.me/blog/solving-the-aba-problem-in-rust-tagged-pointers
https://en.wikipedia.org/wiki/ABA_problem
https://en.wikipedia.org/wiki/Hazard_pointer
https://chfhrqnfrhc.tistory.com/entry/ABA-Problem-1