스위스식 해시 테이블을 사용한 더 빠른 ES|QL 통계 처리

Elasticsearch를 직접 체험하려면 당사의 샘플 노트북을 살펴보거나, 무료 클라우드 체험판을 시작하거나, 지금 바로 로컬 기기에서 Elastic을 사용해 보세요.

최근 Elasticsearch의 해시 테이블 구현의 핵심적인 부분을 스위스식 설계로 교체하였으며, 균일하고 카디널리티가 높은 워크로드에서 빌드 및 반복 시간이 최대 2~3배 빨라지는 결과를 확인했습니다. 결과적으로 Elasticsearch 쿼리 언어(ES|QL) 통계 및 분석 작업에서 더 낮은 지연 시간, 더 나은 처리량 및 더 예측 가능한 성능을 구현할 수 있게 되었습니다.

이것이 중요한 이유

대부분의 일반적인 분석 워크플로우는 결국 데이터를 그룹화하는 작업으로 귀결됩니다. 호스팅당 평균 바이트 계산, 사용자당 이벤트 계산 또는 다양한 차원에 걸친 메트릭 집계 등의 작업을 수행하더라도 핵심 작업은 동일합니다. 키를 그룹에 맵핑하고 실행 중인 집계를 업데이트하는 것입니다.

작은 규모에서는 거의 모든 합리적인 해시 테이블이 잘 작동합니다. 대규모 환경(수억 건의 문서와 수백만 개의 개별 그룹)에서는 아주 작은 세부 사항들이 중요해지기 시작합니다. 로드 팩터, 탐색 전략, 메모리 레이아웃 및 캐시 동작이 선형적인 성능 향상을 이뤄내느냐, 혹은 캐시 미스의 장벽에 가로막히느냐를 결정짓는 차이를 만듭니다.

Elasticsearch는 수년간 이러한 워크로드를 지원해 왔지만, 핵심 알고리즘을 현대화할 수 있는 기회를 항상 모색하고 있습니다. 따라서 스위스 테이블에서 영감을 받은 새로운 접근 방식을 평가하고 이를 ES|QL의 통계 계산 방식에 적용했습니다.

스위스 테이블의 본질은 무엇인가요?

스위스 테이블은 Google의 SwissTable로 대중화되고 나중에 Abseil 및 기타 라이브러리에서 채택된 현대적인 해시 테이블의 한 계열입니다.

기존의 해시 테이블은 포인터를 쫓아가거나 키를 로드하는 데 많은 시간을 소비하지만, 그 결과가 일치하지 않는 경우가 많습니다. 스위스 테이블의 주요 특징은 키와 값과는 별도로 저장되는 제어 바이트라는 작은 캐시 상주 배열 구조를 사용하여 대부분의 탐색을 거부함으로써 메모리 트래픽을 획기적으로 줄일 수 있다는 점입니다.

각 제어 바이트는 하나의 슬롯을 나타내며, 저희의 경우에는 두 가지 정보를 인코딩합니다. 바로 해당 슬롯이 비어 있는지 여부와 해시값에서 추출한 짧은 지문입니다. 이러한 제어 바이트는 일반적으로 16개의 그룹으로 메모리에 연속적으로 배치되어 단일 명령, 다중 데이터(SIMD) 처리에 적합합니다.

스위스 테이블은 한 번에 하나의 슬롯을 탐색하는 대신 벡터 명령어를 사용하여 전체 제어 바이트 블록을 스캔합니다. CPU는 단 한 번의 연산으로 새로 들어온 키의 지문을 16개의 슬롯과 비교하고 비어 있는 항목들을 걸러냅니다. 이 빠른 경로에서 살아남은 소수의 후보만 실제 키를 로드하고 비교해야 합니다.

이 설계는 약간의 추가 메타데이터를 사용하는 대신, 훨씬 뛰어난 캐시 지역성을 확보하고 무작위 로드 횟수를 획기적으로 줄입니다. 테이블이 커지고 탐색 체인이 길어질수록 이러한 속성의 가치는 점점 더 중요해집니다.

핵심에 자리잡은 SIMD

이 모든 것의 진정한 주인공은 SIMD입니다.

제어 바이트는 단순히 컴팩트할 뿐만 아니라 벡터 명령어로 처리되도록 명시적으로 설계되었습니다. 단일 SIMD 비교를 통해 한 번에 16개의 지문을 확인할 수 있어, 일반적으로 루프로 처리되는 작업을 몇 가지 광범위한 작업으로 전환할 수 있습니다. 그 예는 다음과 같습니다.

실제로 이는 다음과 같은 의미를 지닙니다.

• 분기 명령 감소.
• 탐색 체인 단축.
• 키 및 값 메모리로부터의 데이터 로드 횟수 감소.
• CPU 실행 유닛의 활용도 대폭 향상.

대부분의 조회 작업은 제어 바이트 스캔 단계에서 마무리됩니다. 다음 단계로 넘어가는 경우, 남은 작업은 매우 집중적이며 예측 가능합니다. 최신 CPU가 잘 처리하는 워크로드는 바로 이런 종류의 워크로드입니다.

SIMD의 작동 원리 살펴보기

애플리케이션의 내부 작동 원리를 살펴보고 싶은 독자를 위해, 테이블에 새 키를 삽입할 때 어떤 일이 일어나는지 알려드리겠습니다. 128비트 벡터를 사용하는 파나마 벡터 API를 활용하여 16개의 제어 바이트를 병렬로 처리합니다.

다음 스니펫은 Intel Rocket Lake에서 AVX-512로 생성된 코드를 보여 줍니다. 명령어는 해당 환경을 반영하지만, 설계는 AVX-512에 의존하지 않습니다. 동일한 고수준 벡터 연산은 동등한 명령어(예: AVX2, SSE 또는 NEON)를 사용하여 다른 플랫폼에서도 실행됩니다.

각 명령어는 삽입 과정에서 명확한 역할을 수행합니다.

• vmovdqu: 128비트 xmm0 레지스터에 연속된 16개의 제어 바이트를 로드합니다.
• vpbroadcastb새로운 키의 7비트 지문을 xmm1 레지스터의 모든 레인에 복제합니다.
• vpcmpeqb: 각 제어 바이트를 브로드캐스트된 지문과 비교하여 일치할 가능성이 있는 마스크를 생성합니다.
• kmovq + test: 마스크를 범용 레지스터로 이동하고 일치하는 항목이 있는지 빠르게 확인합니다.

벤치마킹 결과에 따르면 더 넓은 레지스터를 사용하여 32바이트 또는 64바이트로 확장해도 측정 가능한 성능 이점을 얻을 수 없었기 때문에, 최종적으로 한 번에 16개의 제어 바이트로 구성된 프로빙 그룹을 사용하기로 결정했습니다.

ES|QL과의 통합

Elasticsearch에서 스위스식 해싱을 채택한 것은 단순히 기존 방식을 대체하는 것이 아니었습니다. ES|QL은 메모리 회계, 안정성, 및 나머지 연산 엔진과의 통합 측면에서 매우 엄격한 요구 사항을 가지고 있습니다.

새로운 해시 테이블을 페이지 리사이클러 및 서킷 브레이커 회계 기능을 포함한 Elasticsearch의 메모리 관리 기능과 긴밀하게 통합하여 할당이 가시적이고 제한된 범위 내에서 이루어지도록 했습니다. Elasticsearch의 집계는 밀집된 형태로 저장되고 그룹 ID로 색인되어 메모리 레이아웃을 컴팩트하게, 반복 작업 속도를 빠르게 유지할 뿐만 아니라 임의 접근을 허용함으로써 특정 성능 최적화를 가능하게 합니다.

가변 길이 바이트 키의 경우, 그룹 ID와 함께 전체 해시를 캐시합니다. 이렇게 하면 탐색 과정에서 비용이 많이 드는 해시 코드를 다시 계산하지 않아도 되고, 관련 메타데이터를 서로 가깝게 유지하여 캐시 로컬리티를 개선할 수 있습니다. 리해싱 시에 실제 값을 검사할 필요 없이, 캐싱된 해시 값과 제어 바이트에만 의존하여 처리할 수 있으므로 리사이징 비용을 낮게 유지할 수 있습니다.

구현에서 한 가지 중요한 단순화 포인트는 항목을 절대 삭제하지 않는다는 점입니다. 이를 통해 툼스톤(이전에 점유했던 슬롯을 식별하는 마커)이 필요 없으며, 빈 슬롯을 완전히 비어 있는 상태로 유지할 수 있게 되었습니다. 이는 탐색 동작을 더욱 개선하고 제어 바이트 스캔을 효율적으로 유지합니다.

그 결과, Elasticsearch의 실행 모델에 자연스럽게 녹아들면서도 스위스 테이블만의 매력적인 성능 특성을 유지하는 설계가 탄생했습니다.

성능은 어떻습니까?

작은 카디널리티에서 스위스 테이블은 기존 구현과 거의 동등한 성능을 발휘합니다. 이는 예상된 결과입니다. 테이블의 크기가 작을 때는 캐시 효과의 영향이 적고, 최적화할 만한 탐색 과정이 거의 없기 때문입니다.

카디널리티가 증가함에 따라 상황은 급격히 달라집니다.

위의 히트맵은 1,000개에서 최대 10,000,000개 그룹에 이르는 카디널리티 범위에 걸쳐, 다양한 키 크기(8, 32, 64, 128바이트)별 시간 개선 지수를 보여 줍니다. 카디널리티가 증가함에 따라 개선 지수는 꾸준히 증가하며, 균등 분포의 경우 최대 2~3배에 달합니다.

이러한 추세는 설계 단계에서 예측한 바와 정확히 일치합니다. 기존의 해시 테이블은 카디널리티가 높아질수록 탐색 체인이 길어지지만, 스위스식 탐색은 대부분의 조회를 SIMD 연산에 최적화된 제어 바이트 블록 내에서 해결합니다.

캐시 동작이 알려 주는 이야기

속도 향상이 가능했 이유를 더 잘 이해하기 위해, 동일한 JMH benchmarks를(을) Linux perf 환경에서 실행하여 캐시 및 TLB 통계를 캡처했습니다.

원본 구현과 비교할 때 스위스 버전은 전반적으로 약 60% 적은 캐시 참조를 수행합니다. 최종 레벨 캐시 로드가 4배 이상 감소하고, LLC 로드 미스는 6배 이상 감소합니다. LLC 미스는 보통 메인 메모리 접근으로 곧장 이어지기 때문에, 이러한 감소 만으로도 전체 성능 향상의 상당 부분을 설명할 수 있습니다.

CPU와 더 가까울수록 L1 데이터 캐시 미스가 감소하고, 데이터 TLB 미스는 거의 6배나 줄어어, 공간 지역성이 더 치밀해지고 메모리 접근 패턴이 더 예측 가능해졌음을 의미합니다.

이것이 바로 SIMD 친화적인 제어 바이트가 가져다주는 실질적인 이득입니다. 메모리에 흩어져 있는 키와 값을 반복해서 로드하는 대신, 대부분의 탐색 과정을 캐시에 상주하는 컴팩트한 구조를 스캔하여 해결합니다. 메모리 접근 횟수가 줄어들면 미스가 줄고, 미스가 적을수록 쿼리가 더 빨라집니다.

결론

스위스식 해시 테이블 설계를 채택하고 SIMD 친화적인 탐색을 적극적으로 활용함으로써, 카디널리티가 높은 ES|QL 통계 워크로드에서 2~3배의 속도 향상과 더불어 더욱 안정적이고 예측 가능한 성능을 달성했습니다.

이 연구는 최신 CPU 인식 데이터 구조가 해시 테이블과 같이 이미 잘 알려진 문제에서도 상당한 성능 향상을 가져올 수 있음을 보여줍니다. 여기에는 추가적인 기본 유형 특수화 및 조인과 같은 다른 고카디널리티 경로에서의 사용 등 탐구할 여지가 더 많습니다. 이 모든 것은 Elasticsearch 내부를 지속적으로 현대화하기 위해 광범위하세 진행 중인 노력의 일부일 뿐입니다.

자세한 내용이 궁금하시거나 작업 과정을 살펴보고 싶으시다면, 이 풀 리퀘스트 및 메타 이슈 추적 진행 상황을 Github에서 확인하세요.

해싱을 즐기십시오!