시계열 데이터 집계, 2배 빨라진 비결은?
시계열 데이터(Timeseries Data) 처리 엔진의 성능 개선을 위해 쿼리 실행 엔진(Query Execution Engine)을 재설계함
캐시 친화적(Cache-Friendly)인 타일 기반 열(Columnar) 실행 방식을 도입하여 실제 환경에서 2배의 성능 향상을 달성
초기 구현(Naive Implementation)의 문제점과 CPU 캐시(CPU Cache) 효율성을 개선하기 위한 열 기반 변환(Columnar Transpose)의 필요성을 강조
메모리 효율성(Memory Efficiency)을 위해 전체 행렬(Matrix)을 한 번에 변환하는 대신, 타일링(Tiling) 기법을 사용하여 L2 캐시(L2 Cache)에 맞는 크기로 데이터를 처리
초기 구현(Naive Implementation)의 문제점과 성능 개선
게시물에서는 초기 시계열 데이터 집계 알고리즘의 성능 병목(Performance Bottleneck)을 분석하고, 이를 개선하기 위한 방법을 제시한다. 특히, 각 단계(step)마다 모든 시계열 데이터(series)에 대해 집계를 수행하는 무식한(Naive) 방식은 병렬 처리(Parallelism)의 이점을 활용하기 어렵다고 지적한다. find_sample 함수에서 상태ful 커서(Stateful Cursors)를 사용하여 O(T x S x log N)에서 O(T x S)로 복잡도를 줄이는 방법을 제안한다.
CPU 캐시(CPU Cache) 효율성을 위한 열 기반 변환(Columnar Transpose)
저자는 CPU 캐시의 효율성을 높이기 위해 열 기반(Columnar) 데이터 구조로의 변환을 제안한다. 기존의 행 기반(Row-based) 데이터 구조에서는 각 단계(step)에서 여러 시계열 데이터(series)의 샘플을 읽어오면서 캐시 미스(Cache Miss)가 발생하여 성능 저하를 야기한다. 열 기반 변환(Columnar Transpose)을 통해 시간(time)별로 데이터를 정렬함으로써, 캐시 라인(Cache Line)에 데이터를 효율적으로 저장하고, 캐시 적중률(Cache Hit Rate)을 높여 성능을 개선한다.
메모리 효율성을 위한 타일링(Tiling) 기법
게시물에서는 타일링(Tiling) 기법을 사용하여 메모리 사용량을 최적화하는 방법을 설명한다. 열 기반 변환(Columnar Transpose)을 통해 L1 캐시(L1 Cache) 효율성은 개선되었지만, 전체 데이터를 한 번에 변환하는 방식은 L2, L3 캐시(L2, L3 Cache)를 초과하는 메모리 사용량을 야기할 수 있다. 이를 해결하기 위해 데이터를 작은 타일(tile) 단위로 나누어 처리함으로써, 메모리 사용량(Memory Usage)을 줄이고 캐시 효율성(Cache Efficiency)을 높인다.
열 기반 저장소(Columnar Storage)의 설계 고려 사항
게시물에서는 열 기반 실행(Columnar Execution)의 장점을 설명하면서, 왜 데이터를 열 기반으로 저장하지 않는지에 대한 의문을 제기한다. 열 기반 저장소(Columnar Storage)는 각 시계열 데이터(series)에 대한 별도의 열(column)을 필요로 하므로, 인덱스 관리의 어려움이 있다. 대신, 타임스탬프(timestamp)와 값(value)을 분리하여 저장하는 방식을 사용하며, 쿼리 실행 시 필요한 열 기반 레이아웃을 동적으로 생성하여 쿼리 성능(Query Performance)을 최적화한다.
