| Scalable Address Spaces using Concurrent Interval Skiplist | |
|---|---|
| Author | Tae Woo Kim, Youngjin Kwon, Jeehoon Kang |
| Conference | ACM SIGOPS Symposium on Operating Systems Principles (SOSP) |
| Year | 2025 |
개요
이 논문은 멀티스레드 프로세스의 가상 주소 공간에서 mmap()·munmap() 등 갱신 작업이 mmap_lock에 의해 직렬화되는 문제를, mapping과 interval locking을 결합한 concurrent interval skiplist 및 주소 공간 설계로 해결하였다.
Motivation
Linux 6.8.0은 per-VMA locking으로 많은 page fault를 갱신과 병렬 실행할 수 있지만, 주소 공간을 할당하는 Alloc과 기존 mapping을 바꾸는 Modify는 여전히 mmap_lock을 write mode로 잡는다. 다중 arena를 사용하는 Memory allocator와 file-backed mapping을 많이 여닫는 응용에서는 이 직렬화가 커진다. 논문의 lockstat 측정에서 높은 thread 수의 mmap_lock 대기 시간 비율은 Apache 최대 90%, Metis 60%, Psearchy 41%, LevelDB 40%에 이른다(Fig. 1).
단순한 range lock 교체도 어렵다. 작업 대상 구간과 VMA 또는 page table의 경계가 일치하지 않아 실제 잠글 범위가 현재 mapping 상태에 따라 바뀐다. 예를 들어 munmap()은 빈 page table을 안전하게 해제하려면 이웃한 gap까지 보호해야 한다(Fig. 3–4). 먼저 map을 탐색하고 나중에 range를 잠그면 그 사이의 갱신으로 탐색 결과가 낡을 수 있다.
Main Idea
핵심은 주소 구간의 검색과 잠금 획득을 한 자료구조의 연속된 동작으로 통합하는 것이다. Concurrent interval skiplist는 각 node와 뒤따르는 gap을 잠그면서 필요한 구간을 찾아가므로, map을 먼저 읽고 별도의 range lock을 나중에 잡는 사이의 race를 피한다. 겹치지 않는 구간의 갱신은 병렬로 진행하고, lock-free Query를 위해 여러 node의 교체는 RCU 방식으로 한 번에 commit한다(§4).
이를 실제 kernel 주소 공간으로 확장하려면 전역 작업에는 별도의 per-core lock 층을 쓰고, Alloc은 core별 arena로 분산하며, 엄격한 resource limit을 유지하는 counter도 분산해야 한다(§5). 즉 skiplist가 핵심이지만, 성능 개선은 이 주변 메커니즘을 함께 적용한 결과다.
Design
- Concurrent interval skiplist (§4): 기존 interval map의 Query·Map·Alloc에 Lock·Unlock·Swap을 더한다. Lock은 predecessor부터 대상 node와 gap을 순차적으로 잠근다. level-0 link의
LOCKED표시가 node와 뒤따르는 gap을 보호하므로, 인접한 VMA나 빈 구간을 함께 다뤄야 하는 Modify에도 적용된다. Skip link는 탐색을 빠르게 하되 잠금은 level 0에서만 수행한다. - 원자적 다중 node 갱신과 Query (§4): Map/Swap은 새 node들을 준비한 후 predecessor link를 CAS로 바꾸어 교체를 commit하고, 옛 node를
INVALIDATED로 표시한다. Query는 잠금 없이 전·후 상태 중 하나를 읽도록 설계한다. 높은 skiplist level의 link는 교체 전후에 묶어서 정리·삽입한다. 이 방식은 구간 전체를 잠그지 않고도 여러 VMA에 걸친 갱신을 처리하지만, tree보다 Query의 cache locality가 나쁠 수 있다. - 전역/국소 2단계 잠금 (§5.1): global read/write(GR/GW)는 모든 per-core RW lock을 잡고, local read/write(LR/LW)는 실행 core의 lock과 해당 skiplist interval lock을 잡는다. 따라서
fork()·exit()같은 전역 작업에서 모든 VMA lock을 열거할 필요가 없고, 겹치지 않는 국소 작업은 병렬 실행된다. 지원하지 않는 일부 경로는 전역 lock으로 fallback한다. - Fault·Alloc·Modify 경로 (§5.2–5.4): Fault는 가능한 경우 주소 공간 lock 없이 시도하고, page table 생성·VMA 초기화 등 동기화가 필요하면 LR, 예외적 file-backed 경로에서는 GR로 진행한다. Alloc은 새 VMA를 삽입 전에 준비하고 CAS 삽입으로 commit한다.
munmap()·mprotect()등의 Modify는 동적으로 확인한 구간을 LW로 잠그며, 미적응 경로에서는 GW를 사용한다. - 분산 Alloc과 제한 계수 (§5.3): 각 core는 우선 자기 64 GiB arena에서 빈 공간을 찾는다. Separator node와 계층화한 skiplist level이 arena 간 skip-link 간섭을 줄이고, arena hint는 해제된 공간의 재사용을 돕는다. Resource counter는 per-core batch를 사용하다가 limit에 가까워지면 global counter 직접 갱신으로 전환하여 strict limit을 지킨다. 구현에서 최대 128개 arena는 256 TiB 주소 공간의 4% 미만을 차지한다.
Result
| 실험 | Linux 6.8.0 대비 IntervalVM | 의미 |
|---|---|---|
mmap() Alloc microbenchmark |
peak throughput 13.1× | Alloc 병렬화의 효과. Arena 또는 per-core statistics를 끄면 확장성이 크게 떨어져 여러 병목을 함께 해결해야 함(Fig. 14). |
| Alloc + Fault + Modify microbenchmark | peak throughput 10.4× | 실제 mapping 수명 주기에 가까운 반복 작업에서도 효과가 유지됨(Fig. 14). |
| Apache | 단일 프로세스 4.53×; 기본 다중 프로세스 설정 3.19× | Fault·Alloc·Modify 중 하나의 병렬화를 끄면 처리량이 감소함(Fig. 15–16). |
| LevelDB / Metis / Psearchy | 각각 4.49× / 1.47× / 1.27× | workload가 VM 작업을 많이 할수록 mmap_lock 제거의 이득이 나타남(Fig. 15).
|
Contribution
- 실제 kernel 주소 공간의 병렬화를 막는 다섯 병목을 분해하고, 동적 잠금 구간이 mapping 상태에 의존한다는 점을 명확히 했다.
- 잠금과 interval map을 결합한 concurrent interval skiplist로 겹치지 않는 구간의 갱신 및 RCU-safe lock-free 조회를 함께 지원했다.
- 전역/국소 잠금, per-core arena, adaptive counter를 결합해 POSIX 응용 수정 없이 Linux에서 Fault·Alloc·Modify의 주요 경로를 병렬화했다.
- Microbenchmark, 서버·DB·MapReduce·색인 workload 및 PARSEC로 이득과 단일 연산 비용을 함께 측정했다.