← 목록으로

문제는 메모리 지연 시간이라고, 바보야

요약
  • CPU 사용률이 100%여도 실제 연산이 빠른 RAM 접근 속도를 따라가지 못해 메모리 대기 현상이 발생할 수 있다.
  • 수백만 개의 고유 키를 처리하는 GROUP BY 집계 실험에서, 데이터를 작은 파티션으로 나눠 캐시 활용도를 높이는 기수 분할 방식을 적용하자 메모리 대기 지표가 줄어들고 실행 시간이 단축됐다.
  • CPU 사용률 100% 가 실제 연산 자원의 완전한 활용을 뜻하지는 않음. 실행할 작업이 있어도 메모리를 기다리느라 연산을 진행하지 못할 수 있음
  • RAM 접근은 약 50~100ns가 걸리는 반면, 현대 CPU는 1ns에 약 4~8개 명령을 처리할 수 있어 데이터베이스 성능에서 캐시 활용이 중요함
  • 약 1,700만 개의 고유 키를 하나의 해시 테이블로 집계한 단일 코어 실험에서는 메모리 대기 지표가 50.1% 에 달했고, 페이지 캐시에 데이터가 있는 재실행도 3.6초가 걸림
  • 키를 4,096개 파티션으로 나눠 작은 해시 테이블에서 집계하자 연산량은 늘었지만, 재실행 시간은 2.7초로 줄고 메모리 대기 지표도 23.5%로 낮아짐
  • 이 실험에서는 캐시에 없는 데이터에 대한 DRAM 접근을 추가 CPU 연산으로 바꾸는 방식이 효과적이었음. 캐시 활용 외에도 프리페칭과 메모리 처리량을 극대화하는 알고리듬으로 DRAM 지연을 숨길 수 있음
CPU 사용률과 실제 연산량은 다름
  • CPU 사용률 100% 인 두 프로세서가 같은 양의 작업을 처리하는 것은 아님. CPU는 여러 명령을 동시에 수행할 수도 있고, 사용률이 100%여도 명령을 전혀 진행하지 못할 수도 있음
  • Linux에서 CPU가 유휴 상태라는 것은 CPU 시간이 필요한 작업이 없다는 뜻임. 반대로 실행할 작업이 있다는 사실만으로 CPU 내부 자원이 완전히 활용된다고 볼 수는 없음
  • 이러한 차이의 원인은 보통 메모리에 있음. 내부 연산보다 메모리 접근이 훨씬 느려 CPU가 데이터를 기다리게 됨
메모리 계층과 캐시 활용
  • 현대 CPU는 대략 1ns당 4~8개 명령을 처리하며, DRAM 접근에는 약 50~100ns가 걸림
    • 대략적인 비교로는 RAM 접근 한 번을 기다리는 동안 약 400~800개 명령을 처리할 수 있음
  • CPU 캐시는 칩 내부에 데이터를 가까이 두어 접근 지연을 줄이지만 용량이 작음
    • L1은 약 64KB이며, 접근 시간은 약 1ns로 RAM보다 약 50~100배 빠름
    • L2는 약 1MB이며, 접근 시간은 약 3~4ns임
    • L3는 고급 프로세서에서 최대 수백 MB이며, 접근 시간은 약 10~15ns임
    • DRAM은 GB 단위 용량이며, 접근 시간은 약 50~100ns임
  • 데이터베이스는 데이터를 작은 덩어리로 처리해 캐시를 활용하려 하며, 캐시 활용도는 성능 엔지니어링의 중요한 관심사임
단순한 GROUP BY 구현의 병목
  • 단순한 GROUP BY는 그룹 키를 키로 삼는 해시 테이블을 만들고, 각 행마다 해당 키를 찾아 집계 값을 갱신함
    • 키가 없으면 새 항목을 만들고, 있으면 개수나 합계 등을 갱신함
  • 고유 그룹이 수백만 개로 늘어나면 해시 테이블이 커져 거의 모든 접근이 캐시에 없는 데이터에 대한 DRAM 접근이 될 수 있음
    • CPU 사용률은 100%로 보이더라도 실제로는 메모리를 계속 기다리게 됨
  • 실험에서는 Pivot의 복잡한 집계 로직을 제거하고, 각 키에 대해 *self.counts.entry(key).or_insert(0) += 1을 수행하는 단순 구현으로 교체함
실험 환경과 최초 측정
  • ClickBench의 hits 데이터셋 약 9,900만 행에 SELECT count(*), UserID FROM hits GROUP BY UserID를 실행함
    • 고유 UserID가 약 1,700만 개이므로 해시맵에도 그만큼의 항목이 필요함
    • 실제 측정 명령은 집계 쿼리를 바깥쪽 SELECT count(*)로 감싼 형태를 사용함
  • CherryServers 베어메탈 서버의 AMD EPYC 9124 Genoa, 16코어, DDR5 128GB 환경에서 측정함
    • 일반적인 AWS/GCP 가상 머신에서는 보안상 노출되지 않는 하드웨어 카운터가 필요했음
    • 단순 집계 구현은 여러 코어에서 실행할 수 없어 단일 코어로 제한함
    • taskset으로 서버를 CPU 3에, 클라이언트를 CPU 7에 고정하고 서버 코어에서 perf stat을 측정함
  • 최초 실행은 3.9초, 서버를 재시작하지 않은 두 번째 실행은 3.6초가 걸림
    • 두 번째 실행은 데이터가 페이지 캐시에 있어 디스크 접근을 배제한 비교에 적합함
  • backend_bound_memory와 retiring 지표는 각각 50.1%, 16.1% 였음
    • 메모리 때문에 진행하지 못하는 CPU 슬롯 비율은 높고, 마이크로 연산을 완료하는 슬롯 비율은 낮았음
  • ls_dmnd_fills_from_sys.dram_io_near 카운터는 약 7,619만 회를 기록함
    • 캐시 라인당 64바이트를 적용하면 CPU의 요구 로드로 DRAM에서 가져온 데이터는 약 4.5GB임
    • 이 수치는 프리페칭으로 가져온 데이터는 포함하지 않음
기수 분할로 작업 집합 줄이기
  • 기수 분할(radix partitioning) 로 집계를 두 단계로 나눠, 각 단계에서 사용하는 해시맵이 캐시에 들어갈 가능성을 높임
  • 1단계는 키 분할이며, 키를 해시한 뒤 상위 12비트로 4,096개 파티션 중 하나를 선택함
    • 64비트 해시에 hash >> 52를 적용해 파티션 번호를 구하고, (hash, key)를 저장함
    • 같은 키는 같은 파티션에 들어가며, 서로 다른 키도 같은 파티션에 들어갈 수 있음
    • 파티션 저장소는 SlabVec의 Vec으로 구성함. SlabVec은 이미 페이지가 메모리에 올라온 영역을 사용하는 Vec 유사 자료구조임
    • Pivot은 원시 메모리에 일반 Vec을 사용하면 변동성이 커져 이를 피함
  • 2단계는 파티션별 집계이며, 모든 입력을 받은 뒤 파티션을 하나씩 처리함
    • 파티션마다 새 해시 테이블을 만들고, 1단계에서 계산한 해시를 재사용해 키별 개수를 집계함
    • 집계가 끝나면 (key, count)를 출력 결과에 추가함
  • 두 구현 모두 각 행을 해시하고 해시 테이블에서 처리하지만, 분할 구현에는 중간 저장 작업이 추가됨
    • 연산 수를 줄이는 대신 작업 해시맵의 크기를 줄여 조회가 CPU 캐시에서 처리될 가능성을 높임
연산량은 늘었지만 메모리 대기는 줄어듦
  • 분할 구현의 실행 시간은 최초 3.3초, 두 번째 2.7초로 단순 구현보다 짧아짐
  • perf 측정에서 메모리 대기 지표는 50.1%에서 23.5% 로 줄고, retiring은 16.1%에서 32.2% 로 늘어남
    • 완료된 연산 수를 나타내는 ex_ret_ops는 약 114억 회에서 약 194억 회로 증가함
    • 메모리 대기로 정체된 슬롯 카운터는 약 84억에서 약 38억으로 감소함
  • DRAM 요구 로드는 약 2,569만 회로 감소함
    • 데이터량으로는 4.5GB에서 1.5GB로 줄어듦
  • 이 실험에서는 추가 연산의 비용보다 DRAM 접근 감소의 이득이 컸음. 캐시에 없는 데이터에 대한 접근을 CPU 명령으로 바꾸는 것이 유리할 수 있음을 보여줌
추가 최적화와 Pivot의 실행 결과
  • GROUP BY의 캐시 활용 최적화는 이 분할 방식으로 끝나지 않음
  • DRAM 지연을 숨기는 다른 방법으로는 필요한 데이터를 미리 캐시에 가져오는 프리페칭, 메모리 처리량을 극대화하는 알고리듬이 있음
    • 구체적인 방법은 후속 JOIN 탐색 구현에서 설명할 예정임
  • 같은 쿼리에서 Pivot의 단일 코어 실행 시간은 1,848.353ms이며, 상세 구현은 별도로 설명하지 않음
    • DRAM 요구 로드는 14,917,958회로, 데이터량은 약 954MB임
  • 16코어 병렬 실행에서는 같은 쿼리가 171.773ms에 완료됨
그냥 목록으로
원문 보기 ↗