컴파일 타임에 데드락을 방지하는 Rust용 deadlock-freedom 라이브러리 surelock 소개.
NOTE
안녕하세요
r/rust! 이 작업에 관심을 가져 주시고 즐거운 대화를 나눠 주셔서 감사합니다 ❤️
저는 데드락이 정말 싫습니다. 아마 여러분도 그럴 겁니다. Fission에서 일할 때 누군가 mutex를 제안하면 우리는 “내가 mutex라고 하면, 너는 deadlock이라고 해: Mutex! DEADLOCK! Mutex! DEADLOCK!”라고 외치곤 했습니다. 데드락은 숨어 있습니다 — 코드 리뷰에서는 완전히 보이지 않고, CI도 천 번쯤은 아무렇지 않게 통과하다가, 아무도 예상하지 못한 요청 패턴이 새벽 3시에 들어오면 시스템을 멈춰 세웁니다.
각자 나름의 트레이드오프가 있긴 하지만, 저는 Haskell의 TVars가 그립습니다. AFAICT 순수성을 강제할 방법이 없는 언어에서는 제대로 된 TVar를 구현할 방법이 없습니다. 우리는 “원래는” lock-free 프로그래밍을 선호해야겠지만, mutex는 Rust의 표준적인 스타일에서 매우 흔합니다. 종종 액터가 데드락을 없애 준다고들 말하지만, Elixir를 꽤 많이 써 본 사람으로서 말하자면 이건 100% 거짓말입니다 (물론 덜 자주 일어나기는 합니다).
Rust는 데이터 레이스를 컴파일 타임에 잡아내는 것으로 유명하지만, 데드락은 어떨까요? Mutex 하나를 쥐여 주고 등을 두드리며 “행운을 빌어, babe”라고 말하는 수준입니다. 코드를 분석하는 데 도움이 되는 꽤 괜찮은 도구들도 몇 가지 있지만, 저는 개발 중에 바로 피드백을 받고 싶습니다. 저는 한동안 이 문제에 대한 더 나은 접근법을 고민해 왔고, 여러 다른 시도들도 살펴본 끝에 Rust의 흔한 사용 사례를 많이 포괄하면서도 사용성이 적절히 균형 잡힌 해법을 만들었다고 생각합니다: 데드락 방지 라이브러리 surelock입니다. 코드가 컴파일되면 데드락이 없습니다. Result도 없고, Option도 없고, 락 경로에서 런타임 panic도 없습니다. 모든 획득은 컴파일러가 안전하다고 증명하거나, 아니면 빌드 타임에 거부됩니다1.
WARNING
이건 프리릴리스입니다. 핵심 설계는 탄탄하다고 생각하지만, 거친 부분이 남아 있어도 놀랍지는 않을 겁니다. 피드백과 기여를 환영합니다!
LockSet)Level<N>)unsafe는 raw mutex 내부 구현에만 한정됩니다no_std 호환, 필수 런타임 의존성 없음2솔직한 답은, 조심하는 것만으로는 확장성이 없다는 것입니다. 코드를 조합하는 과정에서 스스로 발등을 찍기 너무 쉽습니다. 그런데 잠깐, 이런 건 원래 Rust가 도와주기로 한 종류의 문제 아닌가요? borrow checker는 데이터 레이스를 컴파일 타임에 잡아내는데 — 데드락도 같은 수준을 기대하면 안 될 이유가 있을까요?
근본적인 문제는 잘 알려져 있습니다. Coffman 등은 이미 1971년에 데드락의 네 가지 필요 조건을 밝혔습니다:
| Condition | Meaning |
|---|---|
| Mutual exclusion | 적어도 하나의 자원이 독점적으로 점유됨 |
| Hold and wait | 스레드가 하나의 락을 쥔 채 다른 락을 기다림 |
| No preemption | 락을 강제로 빼앗을 수 없음 |
| Circular wait | 대기 그래프에 순환이 존재함 |
이 중 하나만 깨뜨려도 데드락은 불가능해집니다. 상호 배제는 mutex의 존재 이유 그 자체입니다. 선점은 또 다른 종류의 버그를 도입합니다. 그러면 남는 것은 hold-and-wait와 circular wait입니다.
QUOTE
프로그래밍에 대해 생각하는 방식을 바꾸지 않는 언어는 배울 가치가 없다.
― Alan Perlis
우리는 이미 50년도 더 전에 해결 공간을 규정했습니다(!). 이 문제는 충분히 까다로워서 아직도 단 하나의 합의된 해법이 없고, 그럼에도 mutex는 충분히 유용해서 계속 사용되고 있습니다. 이것은 mutex를 완전히 대체하는 무언가가 나타나기 전까지는, mutex를 안전하게 사용할 수 있도록 사용성을 개선하는 영역에 우리가 머물러 있음을 시사합니다.
안전 기법이 실제의 안전한 사용과 정확히 일치하는 경우는 드뭅니다. 타입 시스템은 꽤 유명하게도 때로는 일부 불건전한 동작을 허용하거나, 또는 정당한 사용을 배제합니다 (가끔은 둘 다 그렇습니다) — 그래서 안전하지 않은 사용은 배제하면서 안전한 사용을 더 직접적으로 포착할 수 있는 더 정교한 타입 시스템을 만들기 위한 노력이 계속되는 것입니다. 핵심은 그것들을 가능한 한 가깝게 맞추면서도 가장 다루기 쉬운 모델을 도입하는 데 있습니다: 의례적인 코드가 최소이거나, 추론하기 쉬워야 합니다. 저는 우리의 도구가 _문제에 대해 생각하는 데 도움을 줘야 한다_고 주장하고 싶습니다.
Surelock은 현실 세계의 비유를 중심으로 만들어졌습니다: 락과 상호작용하려면 열쇠가 필요합니다. 이 경우 우리는 mutex를 사용하는 동안 그 열쇠를 계속 들고 있게 됩니다. 락을 해제해야만 그 열쇠를 다시 돌려받을 수 있습니다.
우리는 이것을 MutexKey라고 부릅니다 — 선형3 스코프 토큰입니다. 락킹 스코프에 들어갈 때 하나를 받습니다. .lock()을 호출하면 그 키는 _소비_되고, guard와 함께 새로운 키가 반환됩니다. 이 새 키는 이미 무엇을 잠갔는지에 대한 타입 레벨 기록을 담고 있어서, 컴파일러가 아직 무엇을 획득할 수 있는지 알 수 있게 합니다. 거꾸로 가려고 하면 코드는 컴파일되지 않습니다.
💡 이것이 핵심 트릭입니다: 키를 각 획득 과정 전체를 따라 이동하는 move-only 값으로 만들면, 현재 락 상태에 대한 컴파일 타임 증인을 얻게 됩니다. 전역 분석도 없고, 런타임 추적도 없습니다 — 타입 체커가 가장 잘하는 일을 하게 두는 것뿐입니다.
이 비유는 여기까지만 맞아떨어집니다: MutexKey는 실제로 여러 mutex를 함께 원자적으로 잠글 수 있는 능력도 부여합니다. surelock의 락은 점진적 획득을 가능하게 하기 위해 레벨로 그룹화될 수 있으며, 락킹은 더 적은 레벨만 잠글 수 있는 약화된 키를 반환합니다.
기존 라이브러리 두 개가 이 설계에 영향을 주었고, 정당한 공을 돌리고 싶습니다.
happylockbotahamec의 happylock은 _capability token_과 정렬된 다중 락 획득을 결합하면 데드락을 방지할 수 있다는 핵심 통찰을 제시했습니다. Surelock은 이 패턴을 직접 차용했습니다.
접근 방식이 갈라지는 지점은 다음과 같습니다: happylock은 hold-and-wait 조건을 깨뜨립니다. 컬렉션을 통해 락을 잡으면 키가 소비되어, 해제될 때까지는 아예 더 많은 락을 획득하러 갈 수 없습니다. 이것은 안전하지만, 모든 락을 반드시 한 번에 획득해야 한다는 뜻입니다. “config를 잠그고, 어떤 account를 업데이트할지 읽은 다음, 그 account를 잠근다” 같은 일은 할 수 없습니다. 점진적 획득이 필요한 동시성 시스템에서는 이것이 실제 제약입니다 — 점진적 락이 필요할 때는 정말로 필요합니다.
happylock은 또한 락을 메모리 주소 기준으로 정렬하는데, 이 값은 Vec 재할당이나 move 이후에도 안정적이지 않습니다. 라이브러리는 unsafe (Box::leak, transmute)를 사용해 주소 안정성을 유지하려고 상당한 노력을 기울이고, 그 unsafe는 공개 API까지 전파됩니다.
lock_treeGoogle의 Fuchsia 프로젝트에서 나온 lock_tree는 LockAfter trait를 통한 컴파일 타임 락 순서를 도입했습니다. 레벨 A가 레벨 B보다 앞선다고 선언하면, 컴파일러는 잘못된 순서로 획득하려는 코드를 거부합니다.
Surelock은 이것을 몇 가지 방식으로 확장합니다: 같은 레벨의 다중 락 (lock_tree로는 표현 불가), new_higher를 통한 인스턴스별 레벨 할당, 그리고 스코프 고유성 강제입니다. Surelock은 또한 의도적으로 lock_tree의 DAG 기반 순서를 버리고 엄격한 전순서를 택합니다 — 이유는 아래에서 더 설명하겠습니다.
Surelock은 서로 보완적인 경우를 다루는 두 가지 메커니즘을 사용합니다. 둘은 서로 겹치지 않습니다:
| Mechanism | When | Acquisition | Enforcement |
|---|---|---|---|
LockSet | 같은 레벨 의 여러 락 | 원자적 (all-or-nothing) | 안정적인 ID 기준 런타임 정렬 |
Levels (Level<N>) | 다른 레벨의 락 | 점진적 | 컴파일 타임 trait bound |
LockSet모든 Mutex는 생성 시 전역 AtomicU64 카운터로부터 고유하고 단조 증가하는 LockId를 받습니다. 이 ID는 mutex 내부에 존재하며 mutex와 함께 이동합니다 — 주소 안정성이 필요 없습니다.
같은 레벨에서 여러 락이 필요할 때, LockSet은 생성 시점에 ID 기준으로 미리 정렬합니다. 반대 순서로 같은 락을 요청한 두 스레드도 결국 같은 획득 순서로 정렬됩니다. 순환은 형성될 수 없습니다.
let alice = Mutex::new("alice");
let bob = Mutex::new("bob");
// Regardless of argument order, acquisition order is deterministic
let set = LockSet::new((&alice, &bob));
key_handle.scope(|key| {
let (a, b) = set.lock(key);
// Both locked, no deadlock possible
});
Thread A Thread B
│ │
▼ ▼
LockSet::new((&acct_1, &acct_2)) LockSet::new((&acct_2, &acct_1))
│ │
▼ ▼
sorted: [acct_1, acct_2] sorted: [acct_1, acct_2]
│ │
├─ takes acct_1 lock │
│ ├─ waits for acct_1 lock
├─ takes acct_2 lock │
│ │
~~~~~~~~~~~~~~~~~~~~~~~TIME PASSES~~~~~~~~~~~~~~~~~~~~~~~
│ │
├─ release acct_2 │
│ │ (still waiting for lock 1 first)
├─ release acct_1 │
│ ├─ takes acct_1 lock
│ ├─ takes acct_2 lock
│ │
▼ ▼
OK OK (no cycle possible)
락이 서로 다른 종류의 자원 을 나타낼 때 — 예를 들어 config guard와 account별 락처럼 — 서로 다른 레벨을 할당합니다. Level<N> 타입과 LockAfter trait bound는 엄격히 증가하는 획득 순서를 강제합니다:
use surelock::level::{Level, lock_scope};
type Config = Level<1>;
type Account = Level<2>;
let config: Mutex<_, Config> = Mutex::new(AppConfig::default());
let account: Mutex<_, Account> = Mutex::new(Balance(0));
lock_scope(|key| {
let (cfg, key) = config.lock(key); // Level 1 -> ok
let (acct, key) = account.lock(key); // Level 2 after 1 -> ok
// account.lock(key) then config.lock(key) -> compile error
});
핵심은 바로 MutexKey입니다. 각 lock() 호출마다 소비되고 새 레벨에서 다시 방출됩니다. 거꾸로 가려고 하면 — 예를 들어 Level<3> 다음에 Level<1>을 획득하려 하면 — LockAfter bound를 만족하지 못하고 컴파일러가 도움이 되는 (사용자 정의된) 오류 메시지와 함께 이를 거부합니다.
이것은 의도적인 설계 결정입니다. lock_tree는 DAG를 사용하는데, 그러면 분기 A와 B가 서로 독립적 이라고 선언할 수 있습니다 — 어느 쪽도 다른 쪽보다 먼저일 필요가 없다는 뜻이죠. 좋아 보이지만 미묘한 문제가 있습니다: 스레드 1이 A 다음 B를 획득하고, 스레드 2가 B 다음 A를 획득하며, 두 순서가 모두 DAG에서 유효하다면, 컴파일러가 기쁘게 승인한 데드락이 생깁니다.
락은 (Level, LockId) 기준 전순서로 정렬됩니다. 전순서는 더 제한적이지만 실제로는 건전합니다. 두 락이 시스템에 조금이라도 참여한다면, 그 상대적 순서는 고정됩니다. 개념적으로는 DAG를 선형화할 수도 있습니다 (많은 op-based CRDT에서 하듯이), 하지만 그것은 추론하기 더 어렵고 추가적인 장치를 많이 요구합니다.
두 메커니즘 — LockSet과 레벨 — 모두 MutexKey를 사용합니다. 키를 일종의 스코프라고 생각해도 됩니다: 각 lock() 호출마다 소비되고 새 레벨에서 다시 방출됩니다. 불변 lifetime으로 브랜드되어 (std::thread::scope와 같은 기법) 클로저 밖으로 빠져나갈 수 없고, !Send이므로 생성된 스레드에 머뭅니다.
얻는 방법은 두 가지입니다: 암묵적 방식과 명시적 방식입니다.
lock_scope대부분의 사람은 아마 이것을 사용할 거라고 생각합니다. std에서는 lock_scope가 모든 설정을 내부적으로 처리하므로, 그냥 이렇게 쓰면 됩니다:
use surelock::{Mutex, lock_scope};
let data = Mutex::new(42);
lock_scope(|key| {
let (guard, key) = data.lock(key);
assert_eq!(*guard, 42);
});
내부적으로 lock_scope는 thread_local!``KeyHandle을 대신 관리해 줍니다. KeyHandle의 scope 메서드는 &mut self를 받으므로, borrow checker가 중첩 스코프를 막아 줍니다 — 이미 하나가 활성화된 상태에서는 새 락킹 스코프를 시작할 수 없습니다.
Locksmith와 KeyVoucherno_std, 임베디드, 또는 어떤 코어에 어떤 capability를 줄지 더 세밀하게 제어하고 싶은 경우에는 완전히 명시적인 체인이 있습니다:
Locksmith Program-wide singleton (!Send)
|
v
KeyVoucher Transferable to other threads (Send)
|
v
KeyHandle Per-thread / claimed once (!Send)
|
v
MutexKey<'scope> Branded lifetime, consumed-and-re-emitted
|
v
MutexGuard RAII access to the data
Locksmith는 싱글턴입니다 — 관례가 아니라 AtomicBool로 강제됩니다. !Clone, !Copy이고, 중요한 추가 안전 장치로 !Send이기도 해서 스레드 간에 복제되는 일을 막습니다. 이것은 Send 가능한 KeyVoucher를 발급하므로, 초기 설정 단계에서 스레드들에 키를 분배할 수 있습니다. voucher는 대상 스레드에서 KeyHandle로 교환되며, 이 KeyHandle은 !Send이고 그 자리에 고정됩니다.
이게 의식 절차가 많아 보일 수도 있지만, 대부분은 안전 불변식을 강제하기 위한 타입 장치입니다. thread_local!이 없는 bare metal에서는 오히려 이런 수준의 제어가 필요합니다 — 초기화 시점에 정확히 어떤 코어가 키를 갖는지 결정하고, 타입 시스템이 다른 누구도 공중에서 갑자기 하나를 만들어 낼 수 없게 해 줍니다.
다음은 예시를 도식화한 것입니다. 락 레벨은 엄격한 컴파일 타임 순서를 따르지만, 런타임에 할당되는 락 ID는 임의의 순서로 보인다는 점을 볼 수 있습니다. 이것은 완전히 괜찮습니다; 단지 모든 호출자에게 일관되게 유지되기만 하면 됩니다.
여기서는 어떤 레벨이든 잠글 수 있는 루트 키 (“레벨 0 위”)로 시작합니다. 두 개의 레벨에 걸쳐 락을 획득하고, ID 기준으로 정렬한 뒤 그 순서대로 획득합니다 (이유는 앞선 타임라인에서 설명했습니다). 이 과정에서 루트 키는 소비되고, 레벨 2보다 위를 잠글 수 있는 키가 방출됩니다. 이후에는 잠금을 해제하고 이전 키들을 회복할 때까지 레벨 3 이후를 잠글 수 있습니다.
Key{Level > 0}
│
│
┌─────────Level 1───────────┐ ▼
│ │ ┌─────────LockSet────────┐
│ │ │ │
│ lock_1 │ │ │
│ lock_3 ────┼─────────────┼────▶ lvl_1-lock_3 ─────┼────────▶ guard-3
│ │ │ │
│ lock_8 ────────────┼─────────────┼────▶ lvl_1-lock_8 ─────┼────────▶ guard-8
│ │ │ │
└───────────────────────────┘ │ │
│ │
┌─────────Level 2───────────┐ │ │
│ │ │ │
│ │ │ │
│ lock_5 ────┼─────────────┼────▶ lvl_2-lock_5 ─────┼────────▶ guard-5
│ │ │ │
│ lock_7 │ │ │
│ │ │ │
└───────────────────────────┘ └────────────────────────┘
│
│
▼
Key{Level > 2}
│
│
▼
┌─────────Level 3───────────┐ ┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─
│ │ │
│ │ │
│ lock_2 ─ ┼ ─ ─ ─ ─ ─ ─▶ │
│ lock_4 │ │
│ │ │
│ lock_6 │ │
│ │ │
└───────────────────────────┘ └ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─
no_std와 임베디드이 crate의 핵심은 #![no_std]이며, alloc만 필요합니다. std에서는 기본 백엔드로 StdMutex를, 편리한 진입점으로 lock_scope를 제공합니다. no_std에서는 백엔드를 직접 가져오면 됩니다 — 기능 플래그 뒤의 blanket impl을 통해 lock_api::RawMutex를 구현하는 무엇이든 동작합니다.
또한 portable-atomic과 critical-section 기능을 통해 native CAS가 없는 타깃(예: Cortex-M0)도 지원합니다. 저는 이것이 중요하다고 생각합니다. 데드락 방지가 가장 필요한 곳 — 디버거도 붙어 있지 않은 bare-metal 펌웨어 — 이야말로 현재 도구가 가장 덜 도움이 되는 곳이기 때문입니다.
현실의 코드에서는 가끔 규칙을 깨야 할 때가 있습니다. Surelock은 escape-hatch 기능 플래그 뒤에 Mutex::unchecked_lock()을 제공합니다. 기능 플래그로 감싸 두었기 때문에, 이것을 사용하면 Cargo.toml에 드러나고, grep으로 찾을 수 있으며, 코드 리뷰에서도 눈에 띕니다. 제 생각에는 이것이 대안보다 낫습니다: 개발자들이 조용히 surelock mutex 옆에서 parking_lot::Mutex를 꺼내 들고 전체 시스템을 무력화해 버리는 것보다 말이죠.
데드락은 이론적으로는 해결된 문제입니다 — 우리는 1971년부터 그것을 예방하는 방법을 알고 있었습니다. 과제는 사람들이 실제로 사용할 만큼 그 예방을 충분히 사용하기 쉽게 만드는 것입니다. Surelock은 그것을 향한 제 시도입니다: Rust의 타입 시스템을 적극 활용해 올바른 일을 쉬운 일로 만들고, 잘못된 일은 컴파일 오류로 만들자는 것입니다.
이 crate는 Codeberg에 있고 crates.io에도 배포되어 있습니다. MIT/Apache-2.0 이중 라이선스입니다. 특히 임베디드나 no_std 타깃에서 작업하는 분들의 피드백을 받고 싶습니다 — 지금까지는 그쪽이 실제 환경 테스트가 가장 부족한 영역이기 때문입니다.
예외가 하나 있습니다: 같은 mutex를 원자적으로 두 번 이상 획득하는 경우입니다. 이 엣지 케이스가 존재한다는 점이 마음에 들지는 않지만, 같은 mutex를 자기 자신과 함께 잡으려 하는 일은 흔하지도 않습니다. ↩
thiserror가 유일한 런타임 의존성이며, 런타임 비용은 0입니다. 기본 std 백엔드는 std::sync::Mutex를 직접 감쌉니다. ↩
엄밀히 말하면 Rust의 타입 시스템에서는 affine 입니다 (drop은 가능하지만 복제는 불가). 하지만 의도는 선형적입니다 — 실제로 사용하도록 기대되며, API도 일찍 drop하면 그저 스코프를 끝내는 방향으로 설계되어 있습니다. ↩