[Paper] 고효율 Concurrent Stacks를 위한 Sharded Elimination 및 Combining

Source: arXiv - 2601.04523v1

Overview

이 논문은 Sharded Elimination and Combining이라는 새로운 차단형(linearizable) 스택을 소개합니다. 이 스택은 샤딩과巧妙한 elimination‑and‑combining 방식을 결합합니다. 공유 데이터 구조에 대한 경쟁을 줄임으로써, 저자들은 특히 많은 스레드가 동시에 스택을 사용하려 할 때 기존 최고의 동시성 스택 대비 2× 속도 향상을 달성했습니다.

주요 기여

• Sharded Stack Layout – 스택이 독립적인 “샤드”로 분할되어 병렬 접근이 가능해져 핫스팟 경쟁을 감소시킵니다.
• Elimination Mechanism – 서로 직접 마주치는 push와 pop 연산은 중앙 스택을 우회하여 서로를 취소하고 공유 메모리에 접근하지 않습니다.
• Combining Technique – 가벼운 코디네이터가 여러 스레드의 대기 연산을 배치하여 하나의 샤드에 단일 원자 단계로 적용합니다.
• Hybrid Design – elimination과 combining 구성 요소가 매끄럽게 통합되어 시스템이 워크로드 특성에 따라 동적으로 적응합니다.
• Empirical Evaluation – 다중 코어 머신(최대 128 스레드)에서 광범위한 벤치마크를 수행한 결과, 최신 동시 스택(예: Treiber, Elimination‑Backoff, Flat‑Combining)에 비해 일관된 1.5‑2배 성능 향상을 보였습니다.

Methodology

1. Sharding – 스택을 k 개의 서브‑스택(샤드)으로 나눕니다. 각 스레드는 먼저 해시를 이용해 샤드에 매핑되므로 대부분의 연산이 로컬에서 이루어집니다.
2. Elimination Array – 스레드들은 고정 크기의 엘리미네이션 배열에 자신의 의도(푸시 또는 팝)를 게시합니다. 보완되는 연산이 발견되면 두 스레드는 값을 직접 교환하고 바로 반환하여 샤드에 대한 메모리 쓰기를 피합니다.
3. Combining Scheduler – 엘리미네이션이 실패하면 스레드가 자신의 샤드에 대한 combiner가 될 수 있습니다. 다른 스레드들의 대기 요청을(스레드별 요청 슬롯을 통해) 수집하고, 샤드의 top 포인터에 대해 단일 fetch_and_increment 를 사용해 배치 업데이트를 수행합니다.
4. Fallback Path – 엘리미네이션과 컴바이닝 모두 사용할 수 없을 때(예: 배열이 가득 차거나 대기 요청이 없을 경우) 스레드는 전통적인 락 기반 푸시/팝을 해당 샤드에서 수행합니다.
5. Correctness – 저자들은 성공적인 엘리미네이션 교환 시점이나 컴바이너가 수행한 원자적 업데이트 시점을 선형화 지점(linearization point)으로 정의함으로써 선형화 가능성을 증명합니다.

디자인은 의도적으로 단순합니다: 현대 CPU에서 보편적으로 제공되는 원자적 fetch_and_increment 와 compare_and_swap 프리미티브만을 사용합니다.

Results & Findings

• Scalability: 성능이 물리 코어 수까지 거의 선형적으로 확장되며, 그 이후에도 샤딩 + 결합 방식이 단일 구조 설계보다 여전히 우수합니다.
• Contention Reduction: 제거 경로가 전체 연산의 약 40 %까지 어떤 샤드에도 접근하지 않고 처리하여 캐시 라인 트래픽을 크게 감소시킵니다.
• Overhead: 추가적인 부가 관리(제거 배열, 요청 슬롯)는 최악의 경우 연산당 < 5 ns만큼만 증가하며, 얻는 이득에 비해 무시할 수 있습니다.

Practical Implications

• High‑Throughput Servers – 워크‑스틸링 큐나 작업 스택(예: 웹 서버, 비동기 런타임)을 사용하는 애플리케이션은 기존의 락 기반 스택을 이 설계로 교체함으로써 부하가 걸릴 때 처리량을 두 배로 늘릴 수 있습니다.
• Parallel Algorithms – 깊이 우선 탐색, 백트래킹 또는 공유 스택에 의존하는 모든 알고리즘은 동기화 병목 현상이 감소함으로써 이점을 얻을 수 있으며, 특히 다코어 머신에서 효과적입니다.
• Language Runtime Implementations – VM 개발자(예: Java, Go, Rust)들은 코루틴 스택이나 가비지 컬렉터 작업 리스트와 같은 내부 데이터 구조에 샤드형 elimination‑combining 패턴을 적용할 수 있습니다.
• Ease of Integration – 이 알고리즘은 표준 원자적 프리미티브만을 사용하므로 특별한 하드웨어 지원 없이 C/C++, Rust, 혹은 Java의 java.util.concurrent.atomic 패키지에 구현할 수 있습니다.

제한 사항 및 향후 작업

• 메모리 오버헤드 – 여러 샤드, 엘리미네이션 배열, 그리고 스레드당 요청 슬롯을 유지하면 단일 연결 리스트 스택에 비해 메모리 사용량이 증가합니다.
• 정적 샤딩 – 샤드 수가 초기화 시 고정됩니다; 경쟁 패턴이 변하는 동적 워크로드는 적응형 샤드 크기 조정의 이점을 얻을 수 있습니다.
• 블로킹 특성 – 구현이 블로킹 방식이며(폴백 경로에 락을 사용) 실시간 또는 락‑프리 전용 환경에는 부적합할 수 있습니다.
• 향후 방향 – 저자들은 락‑프리 결합, 적응형 엘리미네이션 배열 크기 조정, 그리고 샤딩‑엘리미네이션 개념을 다른 LIFO‑유사 구조(예: 우선순위 큐)에도 적용하는 것을 제안합니다.

저자

• Ajay Singh
• Nikos Metaxakis
• Panagiota Fatourou

논문 정보

• arXiv ID: 2601.04523v1
• 분류: cs.DC, cs.PL
• 출판일: 2026년 1월 8일
• PDF: Download PDF