동시 데이터 구조를 제대로 테스트하는 법

 (matklad.github.io)
2P by GN⁺ | ★ favorite | 댓글 1개
  • 깨진 Rust 동시 카운터를 예제로, 일반 스레드 부하 테스트가 놓치는 문제를 재현 가능하고 최소화 가능한 실행 순서 제어로 드러냄
  • 테스트용 AtomicU32 래퍼가 pause()를 삽입하고, managed thread가 원자 연산 전후에서 멈췄다가 테스트가 고른 순서로 다시 진행됨
  • 단순 테스트는 100개 스레드가 각각 100번 증가시켜 기대값 10000 대신 9598 같은 실패를 만들 수 있지만, 타이밍 의존이라 재현·디버깅·축소가 어려움
  • arbtest 기반 속성 테스트는 같은 seed로 같은 인터리빙을 재현하고, 실패 사례를 0: increment, 1: increment, 0: unpause, 1: unpause까지 최소화함
  • 같은 구조를 exhaustigen으로 확장하면 최대 5번 증가까지 모든 인터리빙을 열거할 수 있고, fetch_add 수정 뒤 81133개 인터리빙이 통과함

원자적이지 않은 동시 카운터

  • 예제는 Rust의 AtomicU32를 쓰지만, increment()가 load 후 store(value + 1)를 수행해 증가 연산 자체는 원자적이지 않음
  • Counter 구조는 단순함
    • value: AtomicU32
    • increment()는 SeqCst로 값을 읽고, 읽은 값에 1을 더해 다시 저장함
    • get()은 현재 값을 SeqCst로 읽음
  • 두 스레드가 같은 값을 읽은 뒤 같은 증가 결과를 저장할 수 있어 업데이트가 사라짐

일반 스레드 테스트가 부족한 이유

  • 가장 단순한 검증은 여러 스레드가 같은 카운터를 반복 증가시키고 마지막 값을 확인하는 방식임
    • thread_count = 100
    • increment_count = 100
    • 기대값은 10000
  • 예시 실행은 left: 9598, right: 10000으로 실패함
  • 이 방식은 스케줄링 타이밍에 크게 의존함
    • 같은 실패를 결정적으로 재현하기 어려움
    • 디버깅하기 어려움
    • 스레드 수나 증가 횟수를 줄이면 운 좋게 통과할 수 있어 실패 사례를 최소화하기 어려움

속성 기반 테스트로 인터리빙 다루기

  • 속성 기반 테스트(PBT)는 상태 머신 테스트와 잘 맞음
    • 임의 입력을 생성하기 쉬움
    • 동시 실행 결과가 순차 실행 모델과 같아야 한다는 속성을 둘 수 있음
    • 실패 입력을 최소화하려는 요구와도 맞음
  • 난점은 실제 OS 스레드를 원하는 시점에 한 단계씩 진행시키기 어렵다는 데 있음
  • 해결책은 각 반복에서 임의의 스레드를 골라 한 단계 진행시키는 구조임
    • 한 스레드의 load와 store 사이에 다른 스레드를 끼워 넣을 수 있어야 함
    • 이를 위해 스레드를 직접 제어하는 managed thread API를 구성함

테스트용 AtomicU32와 pause 삽입

  • 테스트 빌드에서는 std::sync::atomic::AtomicU32 대신 자체 managed_thread::AtomicU32를 사용함
    • #[cfg(test)] use managed_thread::AtomicU32
    • #[cfg(not(test))] use std::sync::atomic::AtomicU32
  • 래퍼 AtomicU32는 load()와 store() 전후에 pause()를 호출함
    • load: pause() → 실제 load → pause()
    • store: pause() → 실제 store → pause()
  • 이 삽입점 덕분에 테스트가 원자 연산 주변에서 스레드를 멈추고 다시 진행시키며 실행 순서를 제어할 수 있음

managed thread API의 형태

  • 테스트는 std::thread::scope 안에서 두 개의 managed thread를 생성함
    • scoped thread를 사용하므로 스택 지역 데이터를 빌릴 수 있음
    • spawn(scope, &counter)처럼 카운터 참조를 상태로 전달함
  • managed thread는 처음부터 특정 main 함수를 실행하지 않고, 제어 스레드가 submit()으로 보낸 클로저를 실행함
    • t.submit(|c| c.increment())
    • 스레드는 자신의 상태 T에 대해 클로저를 실행함
  • 테스트 루프는 엔트로피가 남아 있는 동안 각 스레드에 대해 무작위로 행동함
    • 스레드가 멈춰 있으면 unpause()
    • 멈춰 있지 않으면 submit()으로 increment()를 실행함
    • 순차 모델 counter_model도 같은 횟수만큼 증가시킴
  • 마지막에는 모든 스레드를 join()하고 counter_model과 실제 counter.get()을 비교함

pause와 unpause 구현

  • pause()는 테스트 대상 Counter API를 바꾸지 않기 위해 thread_local!로 현재 managed thread의 컨텍스트를 찾음
    • 컨텍스트는 Arc<SharedContext>로 공유됨
    • SharedContext는 Mutex<State>와 Condvar를 가짐
  • 상태는 Ready, Running, Paused로 나뉨
    • Ready: 다음 클로저를 기다리는 상태
    • Running: managed thread가 실행 중인 상태
    • Paused: pause() 지점에서 멈춘 상태
  • managed thread가 pause()에 도달하면 상태를 Running에서 Paused로 바꾸고 condition variable로 제어 스레드에 알림
  • unpause()는 상태를 Paused에서 Running으로 바꾸고 managed thread를 깨운 뒤, 다시 Running이 아닐 때까지 기다림
    • 제어 스레드와 managed thread가 동시에 계속 실행되는 상황을 막음
    • 어느 시점에도 둘 중 하나만 실행되도록 만들어 비결정성을 줄임

실패 재현과 최소화

  • arbtest 실행은 깨진 카운터에서 실패를 찾음
    • 예시 실패는 모델 값 4, 실제 값 3
    • 실패 seed는 0x4fd7ddff00000020
  • 같은 seed를 지정하면 같은 인터리빙을 다시 얻을 수 있어 실패 재현이 쉬워짐
  • .minimize()를 사용하면 실패 사례가 더 짧은 실행으로 줄어듦
    • 최종 최소 사례 seed는 0x9c2a13a600000001
    • 최소 trace는 네 단계임
      • 0: increment
      • 1: increment
      • 0: unpause
      • 1: unpause
  • 이 최소 사례에서는 기대값이 2인데 실제 값이 1이 되어 load/store 기반 증가의 결함이 드러남

모든 인터리빙 열거로 확장

  • 같은 구조를 무작위 인터리빙 대신 열거 기반으로 바꿀 수 있음
  • exhaustigen을 사용해 최대 5번 증가까지 모든 인터리빙을 탐색하는 테스트를 작성함
    • 테스트는 더미 반복을 피하고, 항상 스레드를 unpause하거나 increment를 제출하도록 구성됨
  • 깨진 구현은 같은 버그를 찾음
    • 예시 실패는 left: 2, right: 1
  • Counter::increment()를 fetch_add(1, SeqCst)로 고치면 테스트가 통과함
    • AtomicU32 래퍼에도 fetch_add() 전후 pause()를 추가함
    • 실행 결과는 all 81133 interleavings are fine!
    • 실행 시간은 real 8.65s, CPU는 8.16s, RSS는 63.91mb

약한 메모리 모델과 모델 체킹으로의 확장

  • 현재 장난감 구현의 AtomicU32는 실제 atomic에 위임함
  • 확장 아이디어는 각 atomic마다 쓰인 값들의 집합을 유지하고, 읽기 시 약한 메모리 모델과 일관되는 임의의 값을 반환하는 방식임
  • 인터리빙 탐색도 무작위보다 더 똑똑하게 만들 수 있음
    • 모델 체킹 접근으로 의미 있게 다른 인터리빙을 모두 고려했는지 확인할 수 있음
    • Generate All The Things 방식처럼 작은 범위의 모든 인터리빙을 열거할 수 있음

shrinking 없이 최소화가 가능한 이유

  • 사용한 arbtest는 익숙한 PRNG 인터페이스처럼 보이지만 유한 PRNG를 사용함
    • 랜덤 값을 계속 요청하면 어느 시점에 Err(OutOfEntropy)를 반환함
    • 그래서 테스트 코드에 ?와 while !rng.is_empty()가 등장함
  • 테스트가 엔트로피를 다 쓰면 짧게 종료되므로, 사용 가능한 엔트로피를 줄이면 테스트 실행도 짧아짐
  • 내부 구현은 개념적으로 &mut &[u8]에 가까움
    • 랜덤 숫자를 요청할 때마다 바이트 슬라이스가 줄어듦
    • 초기 슬라이스가 짧을수록 더 단순한 테스트가 됨
  • 이 방식 덕분에 별도의 shrinking 로직을 직접 구현하지 않아도 실패 사례가 짧아질 수 있음
  • 예제 소스 코드는 properly-concurrent에 있음

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • Rust에서 비슷한 접근으로 Temper라는 라이브러리를 만들고 있음: https://github.com/reitzensteinm/temper/tree/main
    다만 Rust의 전체 메모리 모델이 만드는 기묘한 함의를 모델링하려면 훨씬 더 나아가야 해서, 각 스레드가 어떤 쓰기를 인지했는지 추적하는 장부가 필요함. 원자적 메모리 순서, 읽기/쓰기 펜스 등에 따라 쓰기 X를 인지하면 쓰기 Y도 반드시 인지해야 하는 식의 보장이 생길 수 있음
    C++/Rust 메모리 모델 테스트 사례를 가장 많이 모아둔 편이라고 생각하며, 책, C++ 표준, Stack Overflow, 블로그 등에서 찾을 수 있는 것을 거의 다 모았음. 예를 들어 Mara Bos의 Rust Atomics and Locks용 파일은 여기 있음: https://github.com/reitzensteinm/temper/blob/main/memlog/tes...
    글에서 언급된 Loom은 비슷하지만 훨씬 완성도 높은 라이브러리로, 뮤텍스나 큐 같은 더 높은 수준의 구성요소를 철저히 테스트할 수 있게 해줌: https://github.com/tokio-rs/loom 다만 메모리 모델 자체는 Temper만큼 촘촘히 모델링하지는 않으며, 테스트 사례를 Loom으로 옮기려는 생각은 하고 있었음
    Will Wilson의 FoundationDB 테스트 발표에서 영감을 받았고, 그는 지금 Antithesis에서 임의의 Docker 컨테이너에 이런 방식의 테스트를 수행하는 하이퍼바이저 기반 솔루션을 만들고 있음: https://www.youtube.com/watch?v=4fFDFbi3toc, https://antithesis.com/
    앞으로 10년간 이 영역이 훨씬 커질 것이라고 강하게 믿음. WebAssembly는 임의의 소프트웨어를 컴파일할 만큼 충분히 완전하면서도, Antithesis 같은 것을 만드는 일이 데이터베이스를 이미 출시해본 정예 팀의 5년짜리 프로젝트가 되지 않을 만큼 단순한 절묘한 지점에 있음

  • Rust로 공유 메모리 원자적 스냅샷을 구현했고, 자동화 테스트도 최대한 진지하게 다뤘음: https://github.com/kaymanb/todc/tree/main/todc-mem
    처음에는 글에 나온 Loom을 썼지만 나중에는 shuttle로 바꿨음: https://github.com/tokio-rs/loom, https://github.com/awslabs/shuttle
    shuttle은 Loom처럼 전수 탐색을 하는 대신 무작위화된 접근을 쓰지만, 스케줄러가 버그 발견에 대한 확률적 보장은 여전히 제공함. 써보니 shuttle이 더 빠르고 더 복잡한 테스트 시나리오까지 확장됐음
    글의 방식과 비슷하게, 특정 스케줄이 테스트 실패를 일으키면 난수 시드를 저장할 수 있음. 실패 테스트를 빠르게 재현할 수 있는 능력은 매우 중요하고, 이전에 잡아서 고친 버그에 대해 명시적인 테스트 케이스를 작성할 수 있게 해줌: https://github.com/kaymanb/todc/blob/0e2874a70ec8beed8fae773...

  • Kotlin/Java 쪽에서는 JetBrains의 Lincheck가 이런 작업에 좋은 라이브러리임: https://github.com/JetBrains/lincheck
    특히 선언형이라는 점과 선형화 가능성 결과를 출력하는 방식이 마음에 듦

  • C++에도 Loom 같은 라이브러리가 있는지 궁금함. 테스트하고 싶은 잠금 없는 자료구조들이 있음

  • 제대로 이해했다면, 이 접근은 약한 전진 진행 보장과 관련해 한계가 있음
    본문 계산이 아주 사소하지는 않지만 실제 하드웨어와 실제 스케줄러에서는 특정 CPU에서 중단될 가능성이 극히 낮은 cmpxchg 루프를 생각해볼 수 있음. CPU 수가 n이면 최악의 경우 진행할 확률은 1/n인데, 이 테스트 방식에서는 1/t^p가 됨. 여기서 t는 작업 수로 CPU 수보다 훨씬 클 수 있고, p는 그 루프 본문 안의 일시정지 횟수로 쉽게 3 이상이 됨. 이 정도면 실제로는 동작하는 알고리즘을 깨진 것처럼 만들기에 충분함
    반대로 약한 전진 진행을 버그로 잡고 싶어서 강한 전진 진행을 요구하는 경우에도, 이 방식이 유용한 도구를 제공하는 것 같지는 않음
    그래도 많은 동시성 문제에는 분명 유용함

    • 1/t^p는 맞지 않는 것 같고 그냥 1/t라고 봄. 결국 t 시간이 지나면 어떤 작업 하나는 반드시 진행했을 것이고, 작업이 t개라면 내가 진행한 작업일 확률은 1/t임
      핵심 혼동은 중단됐다고 해서 반드시 CAS에서 진다는 뜻은 아니라는 데 있는 것 같음

  • “솔직히 말하면 여기에는 약간의 사전 지식이 있다. 인라인 어셈블리로 아주 저주받은 짓을 하지 않는 한 실제 스레드 생성을 피할 수 있을 것 같지 않다. 어떤 것이 pause() 함수를 호출하고, 우리가 추후 지시가 있을 때까지 멈춰 있게 만들고 싶다면, 그 일은 테스트의 스택과 별도 스택을 유지하는 스레드 안에서 일어나야 한다”는 부분에 대해, 어떤 종류의 비동기 런타임을 쓸 수는 없는지 궁금함
    원자 연산을 계측해서 협력적 멀티태스킹을 달성하는 것처럼 보임. 커피를 더 마셔야 할 수도 있지만, 스레드 없이 하는 편이 더 단순해 보임

    • 비동기를 쓰면 편하겠지만, 또 다른 요구사항은 테스트 대상 소프트웨어의 외부에서 관찰되는 API를 바꾸고 싶지 않다는 것임. 비동기는 “전염성”이 있으므로, 동기 API에는 동기 구현을 써야 함

  • 이 접근의 단점 하나는 테스트 대상 코드 자체를 테스트 코드에 맞춰 수정해야 한다는 점임
    두 스레드를 띄우고 ptrace로 단일 단계 실행하면서 명령어 실행을 “무작위로” 끼워 넣어도 같은 일을 할 수 있을 것 같음. rr의 chaos 모드 같은 방식임
    다만 어떤 명령어는 원자적이지 않을 수 있으므로, 에뮬레이션 없이 가능하기나 하다면 “원자적 마이크로코드” 단위로 단일 단계 실행하는 방법이 필요할 것 같음

    • Antithesis의 하이퍼바이저처럼 들림

  • Loom을 쓰려면 조건부 컴파일이 필요한 것 같고, 라이브러리 하나를 테스트할 때는 괜찮겠지만 꽤 침습적임
    #[cfg(loom)]
    pub(crate) use loom::sync::atomic::AtomicUsize;
    #[cfg(not(loom))]
    pub(crate) use std::sync::atomic::AtomicUsize;
    자체 스케줄러를 더 잘 쓸 수 있게 해주는 언어가 있는지 궁금함

  • 정말 철저하게 하려면 ptrace로 테스트를 실행하고 스레드를 단일 단계로 진행시켜 명령어 수준에서 서로 다른 인터리빙을 만들 수 있을 것 같음. 실제로 그런 방식을 본 적이 있는지 궁금함
    여기처럼 코드를 계측할 수 없는 경우, 블랙박스 테스트를 위한 대안이 있을까?

    • 비동기 신호 처리기 테스트에는 그런 방식을 써봤지만, 그쪽은 조합 수가 훨씬 유리함. 기본 스레드가 n개의 명령어를 실행한다면, 신호를 끼워 넣기 전에 0부터 n개 명령어까지 실행하는 n번의 실행만 필요하고, 그 뒤 신호 처리기가 끝까지 실행된 다음 기본 스레드도 끝까지 실행됨. 전체 시간은 O(n^2)임
      하지만 각각 n개 명령어를 실행하는 스레드가 t개 있고, 모든 경계에서 서로를 중단할 수 있다면 현실적인 n 값에서는 접근하기 어려움. 흥미로운 동작을 하는 연산만 골라내고 시뮬레이션하는 식으로 줄여야 할 것 같음

  • 꽤 멋져 보여서 한번 써봐야겠음. 다만 모든 종류의 오류를 잡지는 못할 것임. pause() 호출마다 스레드 사이에 동기화가 생겨서 일부 데이터 경쟁 문제가 가려지지 않을까? Rust에서는 문제가 아닐 수도 있음

답변달기