메모리 지연 시간이 문제다: Pivot의 Radix 분할 GROUP BY
CPU가 100% 사용률로 보고되더라도 실제로는 유용한 명령어를 실행하는 대신 대부분의 사이클을 메모리 대기로 보내고 있을 수 있습니다. Pivot의 블로그 게시물 '메모리 지연 시간이 문제다'는 9,900만 행의 ClickBench hits 데이터셋에서 단일 코어 GROUP BY 쿼리를 통해 이를 보여줍니다. 순진한 해시 테이블 버전은 CPU 슬롯의 50.1%를 메모리 대기로 소모했고 명령어 실행은 16.1%에 불과했지만, radix 분할 버전은 메모리 지연을 23.5%로 줄이고 DRAM 트래픽을 4.5GB에서 1.5GB로 줄였으며 실행 시간을 3.6초에서 2.7초로 단축했습니다.
100% CPU가 대부분 유휴 상태일 수 있는 이유
Linux는 작업이 CPU 시간을 필요로 할 때 CPU를 '사용 중'으로 표시합니다. 이는 코어가 매 사이클 명령어를 실행한다는 의미는 아닙니다. 코어가 100% 사용률을 보이면서도 대부분의 실행 슬롯이 메모리 접근으로 차단될 수 있습니다.
CPU와 메모리 사이의 규모 차이가 그 이유입니다. Pivot의 게시물은 최신 CPU가 나노초당 약 4-8개의 명령어를 처리할 수 있는 반면, DRAM 접근은 약 50-100ns가 걸린다고 추정합니다. 즉, CPU는 DRAM 접근 한 번이 걸리는 시간 동안 약 400-800개의 명령어를 실행할 수 있습니다.
| 레벨 | 대략적인 지연 시간 | 대략적인 크기 | 접근당 명령어 수 |
|---|---|---|---|
| L1 캐시 | ~1 ns | ~64 KB | ~4-8 |
| L2 캐시 | ~3-4 ns | ~1 MB | ~15-30 |
| L3 캐시 | ~10-15 ns | 최대 수백 MB | ~50-100 |
| DRAM | ~50-100 ns | GB 단위 | ~400-800 |
CPU 캐시는 이 격차를 숨기기 위해 존재하지만 실제 데이터셋에 비해 작습니다. 예측 가능한 성능을 원하는 데이터베이스는 CPU가 반복적인 콜드 DRAM 접근을 흡수하는 데 의존하지 말고 작업 세트를 코어 가까이 유지해야 합니다.
순진한 GROUP BY: 하나의 해시 테이블, 수백만 건의 콜드 미스
Pivot은 엔진을 단순한 해시 테이블 집계로 축소하여 캐시 지역성 부족의 비용을 보여주었습니다. 쿼리는 ClickBench의 hits 데이터셋(9,900만 행, 약 1,700만 개의 고유 UserID 값)에서 SELECT count(*), UserID FROM hits GROUP BY UserID였습니다.
순진한 구현은 단일 증가하는 해시 테이블에서 키당 하나의 항목을 삽입하거나 업데이트합니다:
fn consume(
&mut self,
batch: RecordBatch,
_sender: &mut dyn Sender<RecordBatch>,
) -> unary::Result<()> {
let group_keys = batch.column(self.key_column).as_primitive::<Int64Type>();
for &key in group_keys.values() {
*self.counts.entry(key).or_insert(0) += 1;
}
}
수백만 개의 고유 그룹이 있으면 거의 모든 해시 테이블 접근이 DRAM으로 가는 콜드 미스입니다. CPU는 바빠 보일 수 있지만 대부분 대기 중입니다.
측정은 AMD EPYC 9124 Genoa, 16코어, 128GB DDR5를 갖춘 CherryServers 베어메탈 서버에서 실행되었습니다. 순진한 GROUP BY는 여러 코어에서 실행할 수 없었기 때문에 프로세스는 단일 코어에 고정되었습니다. 첫 번째 실행은 3.9초, 두 번째 실행은 데이터가 이미 페이지 캐시에 있고 디스크 개입이 없어 3.6초가 걸렸습니다.
perf stat은 문제를 직접 보여주었습니다:
- 50.1%
backend_bound_memory - 16.1%
retiring - 8,364,109,137
ex_no_retire.load_not_complete - 11,431,618,219
ex_ret_ops
별도 카운터인 ls_dmnd_fills_from_sys.dram_io_near는 76,190,837 DRAM 채움을 기록했습니다. 캐시 라인당 64바이트로 계산하면 쿼리 중 DRAM에서 약 4.5GB를 가져온 것입니다(프리페치 제외).
Radix 분할: 더 많은 명령어, 더 적은 DRAM 왕복
Radix 분할은 집계를 두 단계로 나누어 작업 해시 테이블이 CPU 캐시에 맞을 만큼 작게 유지합니다.
1단계에서 Pivot은 각 키를 해시하고 해시의 상위 12비트를 사용하여 행을 4,096개의 파티션 중 하나로 라우팅합니다. 파티션은 이미 메모리에 페이지인된 메모리 위의 벡터형 구조인 SlabVec입니다. 2단계에서 Pivot은 한 번에 하나의 파티션을 처리하고 해당 파티션에 대한 작은 해시 테이블을 구축하여 집계하고 결과를 내보냅니다.
이 접근 방식은 더 많은 총 작업을 수행합니다: 모든 행이 해시되고 라우팅된 다음 집계 중에 다시 해시됩니다. 이 트레이드오프는 의도적입니다. 더 작은 해시 테이블은 L1, L2 또는 L3 캐시에 맞을 가능성이 높아 조회가 DRAM 대신 캐시에서 적중합니다. Pivot의 게시물은 콜드 DRAM 접근을 CPU 명령어로 변환하는 것이 일반적으로 좋은 트레이드오프라고 주장합니다.
동일한 단일 코어에서의 결과:
- 첫 번째 radix 분할 실행: 3.3초
- 두 번째 radix 분할 실행: 2.7초
backend_bound_memory: 23.5%retiring: 32.2%ex_ret_ops: 19,350,459,182 (순진한 버전의 11,431,618,219에서 증가)- DRAM 채움: 25,688,280 (채움당 64바이트로 약 1.5GB)
Radix 버전은 더 많은 작업을 실행했지만 메모리 지연에 소요된 시간은 훨씬 줄었습니다. 메모리 지연은 8,364,109,137 CPU 슬롯에서 3,790,955,223으로 줄었고 DRAM 트래픽은 약 4.5GB에서 약 1.5GB로 줄었습니다.
Pivot의 튜닝된 구현 및 병렬 결과
Pivot의 자체 구현은 데모 버전보다 더 발전했습니다. 단일 코어에서 게시물은 동일한 쿼리에 대해 1,848.353ms와 14,917,958 DRAM 채움(약 954MB DRAM 트래픽)을 보고합니다.
16코어에서 Pivot은 쿼리에 대해 171.773ms를 보고합니다. 게시물은 캐시 활용만이 DRAM 지연을 숨기는 유일한 방법이 아니라고 말하며, 프리페칭과 메모리 처리량을 최대화하는 알고리즘은 JOIN 프로빙에 대한 후속 게시물에서 다룰 것이라고 합니다.
Hacker News 댓글러들이 논의한 내용
Hacker News 게시물은 254점과 92개의 댓글을 받았습니다. 토론은 캐시 지역성 데모에 대한 찬사와 기술 또는 제품의 참신성에 대한 회의론으로 나뉘었습니다.
한 댓글러는 프로덕션 시스템에서 기계적 공감을 무시하는 것의 광범위한 비용을 설명했습니다:
저는 다른 팀과 함께 일하는데, 그 팀은 메시지 패싱, 깊게 중첩된 클래스 계층의 C++ 가상 메서드, 대형 DOM, 그리고 일반 C++ STL 컨테이너를 많이 사용합니다... STM32MP1에서 실행되는데, 이는 순차 실행 Cortex-A7과 적은 캐시를 가지고 있습니다. 반면, 제 팀에서는 인라인 할당하는 맞춤형 C++ STL 컨테이너, SAX 스타일 처리 라이브러리, 그리고 2000년대 비디오 게임처럼 인덱스+세대를 사용하는 링크가 있는 객체 풀을 작성했습니다... STM32H5에서 실행되는데 RAM이 1MB 미만입니다. 기계적 공감은 제가 시연하는 사람들에게 잃어버린 예술처럼 느껴집니다... 그리고 첫 번째 팀에게 벤치마크 수치로 제가 그들 사이에서 수십 배의 병목이 되지 않을 것임을 증명해야 했습니다.
또 다른 댓글러는 CPU 사용률 함정에 대한 직접적인 예를 들었습니다:
저는 함께 일했던 팀과 매우 긴 논쟁을 기억합니다. 그들은 CPU가 이미 100%라서 우리 서비스가 요청을 더 빨리 처리할 수 없다고 확신했습니다. 결국 서비스의 메모리 접근 패턴을 정리하여 초당 요청 수를 세 배로 늘렸습니다...
다른 댓글러들은 참신성에 의문을 제기했습니다. 한 명은 이렇게 썼습니다:
어, 이건 그냥 radix 분할 집계 아닌가요? 계층적(고정 2레벨) 집계는 오래된 것입니다. 여기서 새로운 것은 무엇인가요? Pivot 자체의 축소판이라고 생각합니다. DuckDB와 ClickHouse가 모두 존재하는데 이 프로젝트가 왜 존재하는지 이해가 안 됩니다.
또 다른 댓글러는 이 접근 방식을 클러스터형 해시 맵으로 설명했습니다:
제시된 솔루션은 그냥 클러스터형 해시맵 또는 원한다면 '지역성 민감' 해시맵인 것 같습니다. 그래도 수십 배 더 나은 것은 아닙니다.
게시물은 radix 분할을 발명했다고 주장하지 않습니다. 그 기여는 데이터베이스 쿼리가 메모리 지연으로 얼마나 많은 손실을 입을 수 있는지에 대한 측정된 데모와 Pivot이 자체 엔진에서 캐시 인식 집계를 적용하는 방법을 보여주는 것입니다. 댓글 스레드는 그러한 데모가 새로운 데이터베이스 프로젝트를 정당화하기에 충분한지에 대한 더 넓은 불일치를 반영합니다.
마지막 댓글은 깔끔한 코드와 빠른 코드 사이의 트레이드오프를 설명했습니다:
깔끔한 코드는 아름답습니다. 마치 편리한 거짓말이 우리를 즐겁게 하는 것처럼. 캐시 인식 코드는 추합니다. 마치 상처를 주는 진실처럼. 도덕성은 처음부터 정직하라고 제안합니다. 캐시 지역성을 목표로 하는 데 조기함은 없습니다.
실용적인 교훈은 제품 논쟁보다 더 좁습니다: 100% CPU는 CPU가 포화 상태라는 증거가 아닙니다. 데이터 집약적 워크로드의 경우 메모리 지연과 DRAM 트래픽이 더 나은 설명인 경우가 많으며, 데이터를 CPU 캐시에 맞게 분할하면 명령어 수가 증가하더라도 실행 시간을 줄일 수 있습니다.
Sources
관련
- Dispatch
- Dispatch
- Dispatch
- Dispatch
- Dispatch