iddqd, 또는 가장 어려운 종류의 unsafe Rust

GAT 기반 값-키 결합 구조로 Unsafe Rust의 Soundness 확보

neo2026년 6월 3일16분advanced

AI 요약

Context

기존 BTreeMap은 키와 값을 별도로 저장하여 데이터 중복과 정합성 불일치 위험을 초래함. Oxide의 Omicron 제어 평면과 같은 대규모 레코드 인덱싱 환경에서 키 복제 비용과 관리 복잡도를 해결할 고효율 구조가 필요함.

IdOrdItem trait 및 GAT(Generic Associated Types) 도입을 통한 값 내부 필드 기반 키 빌림 구조 설계
ItemSet(Vec 기반 슬롯 관리)과 인덱스 테이블(B-tree/Hash table)을 분리하여 메모리 레이아웃 최적화
transmute를 이용한 수명 확장 및 인덱스 유일성 불변식을 통한 Mutable Iteration 구현
Pathological Ord 구현으로 인한 중복 인덱스 생성 방지를 위해 Key와 Index를 동시 비교하는 Tie-breaker 로직 적용
Tree Search 실패 시 Linear Scan으로 전환하는 Fallback 메커니즘을 통해 사용자 코드의 비정상 동작에도 Soundness 유지
Miri, 모델 기반 테스트, Panic Fault Injection을 통한 Unsafe Block의 UB(Undefined Behavior) 정밀 검증

실천 포인트

1. Unsafe Block 상단에 // SAFETY: 주석을 통한 명시적 근거 기록 및 Linter 강제화

2. 사용자 구현 Trait에 의존하는 로직 설계 시 최악의 입력(Buggy/Malicious) 상황에 대한 Fallback 전략 수립

3. Miri를 CI 파이프라인에 통합하여 메모리 안전성 및 UB 상시 탐지

4. 복잡한 수명 확장 필요 시 데이터 구조의 불변식(Invariant)을 명확히 정의하고 이를 검증하는 테스트 케이스 확보

태그