자바에서 구글 SwissTable 디자인 구현...고속·메모리 효율 해시 테이블 개발

벡터 API 활용해 SIMD 명령어 최적화, 기존 대비 50% 이상 메모리 절감 달성

[한국정보기술신문] 개발자 커뮤니티에서 자바 환경에 구글의 스위스테이블 디자인을 구현한 고성능 해시 테이블 프로젝트가 주목받고 있다. HashSmith라는 이름의 이 오픈소스 프로젝트는 자바의 벡터 API를 활용하여 기존 자바 HashMap 대비 50% 이상의 메모리 절감 효과를 보이는 것으로 나타났다.

스위스테이블은 구글이 개발한 오픈 어드레싱 해시 테이블 디자인으로, C++ 라이브러리 Abseil에 처음 도입된 이후 러스트와 Go 등 주요 프로그래밍 언어의 표준 라이브러리에 채택되며 현대적 해시 테이블 구현의 새로운 기준으로 자리잡았다. 러스트는 1.36.0 버전부터 표준 HashMap 구현을 스위스테이블 기반으로 전환했으며, Go는 최근 1.24 버전에서 스위스테이블을 도입해 맵 연산 속도가 최대 60% 향상되는 성과를 거뒀다.

스위스테이블의 핵심 혁신은 메타데이터와 실제 키-값 저장소를 분리한다는 점이다. 작은 제어 바이트 배열을 통해 값비싼 키 비교 연산을 대부분 피할 수 있으며, 이는 캐시 친화적이고 대량 비교가 용이한 구조다. 해시값을 h1과 h2 두 부분으로 나누어, h1은 탐색 시작 위치를 결정하고 h2는 제어 바이트에 저장되는 작은 지문으로 활용된다. 이를 통해 대부분의 조회 실패와 성공 케이스에서 실제 키 메모리를 건드리지 않고도 후보를 필터링할 수 있다.

자바 벡터 API로 SIMD 최적화 구현

이번 프로젝트의 핵심은 자바 25에서 인큐베이팅 단계인 벡터 API를 활용한 SIMD 연산 구현이다. 스위스테이블의 속도는 여러 제어 바이트를 한 번에 비교하는 광범위 비교에서 나오는데, 이는 SIMD가 특화된 작업이다. 기존에는 자바에서 이러한 저수준 최적화를 수행하기 위해 자동 벡터화에 의존하거나 Unsafe API를 사용하거나 JNI를 작성해야 했지만, 벡터 API는 안정적으로 우수한 SIMD 명령어로 컴파일되는 벡터 연산을 표현할 수 있게 해준다.

개발자는 16바이트의 제어 바이트를 비교하고 마스크를 생성한 뒤 설정된 비트에 대해 작업하는 방식을 순수 자바로 구현했다. 제어 바이트 스캔을 핫 패스로 인식하고 나머지 모든 것을 이 스캔이 저렴하고 예측 가능하도록 설계했다. 특히 로드된 제어 벡터를 재사용하여 h2 동등성 마스크와 EMPTY 및 DELETED 마스크를 모두 처리함으로써 추가 패스나 중복 작업을 제거했다.

높은 적재율과 효율적인 메모리 관리

SwissMap은 최대 87.5%의 높은 적재율을 지원한다. 일반적인 오픈 어드레싱 방식에서는 적재율을 높이면 평균 탐색 체인이 급격히 길어지지만, 스위스테이블 방식의 탐색은 캐시 친화적이고 대량 비교가 가능한 제어 바이트 스캔이 주를 이루기 때문에 하나의 추가 탐색 그룹이 많은 키 equals 호출이 아닌 단순히 하나의 제어 벡터 로드와 비교로 처리된다. 자바 HashMap의 기본 적재율 0.75와 비교할 때 상당히 높은 수치다.

제어 바이트는 슬롯의 상태와 비교 가치를 동시에 답하는 영리한 설계를 사용한다. h2에 7비트를 사용하고 나머지 제어 바이트 값은 EMPTY와 DELETED 같은 특수 상태로 남겨둔다. 대부분의 조회는 제어 평면에서 불일치를 거부하며, 탐색된 그룹에 EMPTY가 포함되어 있으면 그것이 확정적인 정지 신호가 된다.

삭제 작업에서는 툼스톤 메커니즘을 활용한다. 제거된 슬롯을 EMPTY로 표시하면 탐색 체인이 끊어질 수 있기 때문에, DELETED로 표시하여 조회가 계속 탐색하도록 한다. 삽입 시에는 첫 번째 DELETED 슬롯을 기억했다가 키를 찾지 못하면 나중의 빈 슬롯 대신 기억된 툼스톤에 삽입함으로써 탐색 체인 길이 증가를 방지한다. 툼스톤이 임계값을 넘으면 동일 용량 재해시를 수행하여 DELETED를 EMPTY로 되돌리고 짧은 탐색 체인을 복원한다.

벤치마크 결과와 실용적 성능

AMD Ryzen 5 5600 프로세서와 Eclipse Temurin JDK 21.0.9 환경에서 수행된 JMH 벤치마크 결과, SwissMap은 높은 적재율에서 다른 오픈 어드레싱 테이블과 경쟁력 있는 처리량을 유지하면서 JDK HashMap 성능에 근접하거나 일부 벤치마크에서는 큰 폭으로 앞서는 것으로 나타났다.

특히 메모리 측면에서 버킷이나 오버플로 노드가 없는 평면 레이아웃과 0.875 최대 적재율이 결합되어 작은 페이로드 시나리오에서 눈에 띄게 작은 유지 힙을 보였다. 프로젝트 측정에서 HashMap 대비 50% 이상 메모리를 절감하는 것으로 확인됐다.

개발자는 이터레이터 구현에서도 추가 버퍼 없이 모듈러 스테핑 순열을 사용하여 시작점과 홀수 스텝을 선택하고 반복적으로 인덱스를 방문하는 방식을 채택했다. 2의 거듭제곱 용량에서 모든 홀수 스텝은 서로소이므로 모든 슬롯을 정확히 한 번씩 방문하면서 테이블 전체에 액세스를 분산시킨다.

리사이즈 재해시에서는 중복 검사를 제거하여 효율성을 높였다. 기존 항목을 순회하며 새 테이블에 put을 호출하는 대신, 새로운 제어/키/값 배열을 할당하고 이전 테이블을 한 번 스캔하여 각 FULL 슬롯에 대해 새 용량으로 h1과 h2를 재계산한 뒤 동일한 제어 바이트 탐색 루프로 찾은 첫 번째 사용 가능한 슬롯에 삽입한다. 이미 존재하는지 확인하지 않는데, 고유한 키를 이동하는 것이므로 확인할 필요가 없다.

향후 전망과 과제

개발자는 이 프로젝트가 명시적으로 실험적이며 프로덕션 준비가 되지 않았다고 밝혔다. 벡터 API가 여전히 인큐베이팅 단계이고 테이블이 높은 적재율과 참조 키 워크로드에 최적화되어 있어, 원시 타입 특화 맵이나 낮은 적재율 구성에서는 다른 결과가 예상된다.

프로젝트는 깃허브에서 HashSmith라는 이름으로 공개되어 있으며, 스위스테이블에서 영감을 받은 SwissMap과 SwissSet 변형을 포함한다. JMH 벤치마크와 문서가 함께 제공되어 누구나 결과를 재현하고 구현 세부사항을 살펴볼 수 있다. 개발자는 또한 벡터 API에 의존하지 않고 오버헤드를 줄이기 위해 SWAR 스타일의 스위스테이블 변형도 개발 중이라고 밝혔다.

이번 프로젝트는 자바 생태계에서도 현대적인 해시 테이블 설계가 충분히 구현 가능하며, 벡터 API와 같은 새로운 기능을 활용하면 기존 구현 대비 상당한 성능 개선을 달성할 수 있음을 보여준다. 러스트와 Go가 이미 표준 라이브러리에 스위스테이블을 채택한 상황에서, 자바 커뮤니티에서도 이러한 접근 방식에 대한 논의가 활발해질 것으로 예상된다.

한국정보기술신문 정보기술분과 김지원 기자 news@kitpa.org