▲

GN⁺: 동시 데이터 구조의 적절한 테스트

 (matklad.github.io)
2P by neo 5달전 | favorite | 댓글 1개

동시성 데이터 구조의 적절한 테스트

하나, 둘, 셋, 둘

  • Rust 라이브러리인 loom을 사용하여 락-프리 데이터 구조를 철저히 테스트할 수 있음
  • 간단한 동시성 카운터 예제 코드 제공
  • 코드의 버그는 증가 연산이 원자적이지 않다는 것임
use std::sync::atomic::{AtomicU32, Ordering::SeqCst};

#[derive(Default)]
pub struct Counter {
    value: AtomicU32,
}

impl Counter {
    pub fn increment(&self) {
        let value = self.value.load(SeqCst);
        self.value.store(value + 1, SeqCst);
    }

    pub fn get(&self) -> u32 {
        self.value.load(SeqCst)
    }
}

간단한 테스트

  • 여러 스레드에서 같은 카운터를 반복적으로 증가시키고 결과를 확인하는 테스트
  • 테스트는 성공적으로 실패하지만, 타이밍에 의존하여 재현이 어려움
#[test]
fn threaded_test() {
    let counter = Counter::default();
    let thread_count = 100;
    let increment_count = 100;

    std::thread::scope(|scope| {
        for _ in 0..thread_count {
            scope.spawn(|| {
                for _ in 0..increment_count {
                    counter.increment()
                }
            });
        }
    });

    assert_eq!(counter.get(), thread_count * increment_count);
}

속성 기반 테스트 (PBT)

  • 상태 기계를 테스트하는 데 적합한 속성 기반 테스트 적용 시도
  • 스레드를 수동으로 단계별로 실행할 수 있다면, 다른 스레드의 load&store 사이에 끼워 넣기 쉬움
#[test]
fn state_machine_test() {
    arbtest::arbtest(|rng| {
        let mut state: i32 = 0;
        let step_count: usize = rng.int_in_range(0..=100)?;

        for _ in 0..step_count {
            match *rng.choose(&["inc", "dec"])? {
                "inc" => state += 1,
                "dec" => state -= 1,
                _ => unreachable!(),
            }
        }
        Ok(())
    });
}

간단한 계측

  • 스레드가 원자적 연산 사이에서 "일시 정지"할 수 있도록 하는 방법
pub fn increment(&self) {
    pause();
    let value = self.value.load(SeqCst);
    pause();
    self.value.store(value + 1, SeqCst);
    pause();
}

fn pause() {
    // ¯\_(ツ)_/¯
}

관리된 스레드 API

  • API 디자인의 한 규칙은 단일 사용자부터 시작하여 API의 느낌을 이해한 후 실제 구현을 진행하는 것
  • 관리된 스레드를 사용하여 속성 기반 테스트 작성
let counter = Counter::default();
let t1 = managed_thread::spawn(&counter);
let t2 = managed_thread::spawn(&counter);

while !rng.is_empty() {
    let coin_flip: bool = rng.arbitrary()?;
    if t1.is_paused() {
        if coin_flip {
            t1.unpause();
        }
    } else if t2.is_paused() {
        if coin_flip {
            t2.unpause();
        }
    }
}

관리된 스레드 구현

  • 제어 스레드와 관리된 스레드 간의 통신 필요
  • 상태를 보호하는 뮤텍스와 조건 변수를 사용하여 구현
struct SharedContext {
    state: Mutex<State>,
    cv: Condvar,
}

#[derive(PartialEq, Eq, Default)]
enum State {
    #[default]
    Running,
    Paused,
}

impl SharedContext {
    fn pause(&self) {
        let mut guard = self.state.lock().unwrap();
        assert_eq!(*guard, State::Running);
        *guard = State::Paused;
        self.cv.notify_all();
        guard = self.cv.wait_while(guard, |state| *state == State::Paused).unwrap();
        assert_eq!(*guard, State::Running);
    }
}

전체 코드 통합

  • 관리된 스레드와 테스트 코드 통합
#[test]
fn test_counter() {
    arbtest::arbtest(|rng| {
        eprintln!("begin trace");
        let counter = Counter::default();
        let mut counter_model: u32 = 0;

        std::thread::scope(|scope| {
            let t1 = managed_thread::spawn(scope, &counter);
            let t2 = managed_thread::spawn(scope, &counter);
            let mut threads = [t1, t2];

            while !rng.is_empty() {
                for (tid, t) in threads.iter_mut().enumerate() {
                    if rng.arbitrary()? {
                        if t.is_paused() {
                            eprintln!("{tid}: unpause");
                            t.unpause()
                        } else {
                            eprintln!("{tid}: increment");
                            t.submit(|c| c.increment());
                            counter_model += 1;
                        }
                    }
                }
            }

            for t in threads {
                t.join();
            }
            assert_eq!(counter_model, counter.get());

            Ok(())
        })
    });
}

GN⁺의 정리

  • 이 글은 동시성 데이터 구조를 테스트하는 방법을 설명함
  • Rust의 loom 라이브러리를 사용하여 원자적이지 않은 연산을 테스트하는 방법을 탐구함
  • 관리된 스레드를 사용하여 동시성 문제를 재현 가능하고 디버깅 가능한 방식으로 테스트함
  • 이 글은 동시성 프로그래밍에 관심이 있는 개발자에게 유용할 것임
  • 비슷한 기능을 가진 프로젝트로는 Java의 JCStress가 있음
▲
neo 5달전  [-]
Hacker News 의견

  • Rust로 Temper라는 라이브러리를 개발 중이며, Rust 메모리 모델의 복잡한 부분을 다루기 위해 많은 노력이 필요함

    • C++/Rust 메모리 모델의 가장 큰 테스트 케이스 모음을 포함하고 있음
    • Loom은 더 완전한 라이브러리로, 뮤텍스와 큐 같은 고수준 구조를 철저히 테스트할 수 있게 해줌
    • Foundation DB 테스트 강연에서 영감을 받았으며, WebAssembly가 이 분야에서 중요한 역할을 할 것이라고 믿음

  • Rust에서 공유 메모리 원자 스냅샷을 구현했으며, 자동화된 테스트를 매우 중요하게 생각함

    • 처음에는 Loom을 사용했지만 나중에 Shuttle로 전환함
    • Shuttle은 무작위화된 접근 방식을 사용하며, 버그를 찾는 확률적 보장을 제공함
    • Shuttle은 더 빠르고 복잡한 테스트 시나리오에 잘 확장됨
    • 실패한 테스트를 재현할 수 있는 기능이 매우 중요함

  • 이 접근 방식의 단점은 테스트 코드에 맞게 코드 자체를 수정해야 한다는 점임

    • 두 스레드를 실행하고 ptrace로 단일 스텝을 통해 명령어 실행을 무작위로 섞는 방법으로도 가능할 것임

  • JetBrains의 Lincheck은 Kotlin/Java 세계에서 좋은 라이브러리임

    • 선언적이며 선형화 결과를 출력하는 방식이 마음에 듦

  • C++용 "Loom" 같은 라이브러리가 있는지 궁금함

    • 잠금 없는 데이터 구조를 테스트하고 싶음

  • 이 접근 방식은 소프트 전진 보장에 한계가 있을 수 있음

    • cmpxchg 루프에서 실제 하드웨어와 스케줄러에서는 중단될 가능성이 매우 낮음
    • 그러나 이 테스트 접근 방식에서는 작업 수와 일시 중지 횟수에 따라 전진 확률이 달라짐

  • 실질적인 지식이 필요하며, 실제 스레드를 생성해야 함

    • 비동기 런타임을 사용할 수 있는지 궁금함

  • ptrace를 사용해 스레드를 단일 스텝으로 실행하여 명령어 수준에서 다른 인터리빙을 만들 수 있음

    • 블랙박스 테스트 대안이 있는지 궁금함

  • Loom을 사용하려면 조건부 컴파일을 사용해야 하며, 이는 다소 침입적임

    • 다른 언어가 자체 스케줄러를 사용하는 데 더 나은지 궁금함

  • Python에서 동일한 작업을 수행하는 방법을 알고 싶음

    • 이와 같은 테스트를 허용하는 스레드 클래스를 만들 수 있는지 궁금함
답변달기