기술 요약: 다중 프로브 제로 충돌 해시 (MPZCH)

1. 문제 제기

대규모 추천 시스템은 고카디널리티 범주형 특성 (예: 사용자 ID, 아이템 ID) 을 밀집 벡터 표현으로 매핑하기 위해 임베딩 테이블에 의존합니다. 그러나 고유 ID 의 양이 증가함에 따라 전통적인 해시 기반 인덱싱 방법은 두 가지 중요한 도전에 직면합니다:

1. 임베딩 충돌: 메모리 제약으로 인해 "해싱 트릭"은 여러 개의 서로 다른 ID 를 동일한 인덱스로 매핑합니다. 관련 없는 사용자나 아이템이 동일한 임베딩 벡터를 공유할 경우, 그 의미론이 혼재되어 모델 성능과 개인화 품질이 저하됩니다.
2. 모델 노후화 및 부정적 전이: 동적 환경에서 새로운 아이템은 종종 구식이고 노후화된 ID 가 차지하는 슬롯과 충돌합니다. 표준 해시 방법은 이러한 오래된 ID 를 퇴역시키는 메커니즘이 부족합니다. 결과적으로 새로운 아이템은 관련 없는 엔티티로부터 사전 훈련된 임베딩을 "상속"하게 되어, 모델이 유용한 신호에 수렴하기 전에 노이즈를 잊어버려야 하는 상황에 처하게 됩니다. 이러한 "부정적 전이"는 새로운 특성에 대한 정확한 표현 학습을 방해합니다.

테이블 크기를 늘리면 충돌 확률을 줄일 수 있지만, 메모리 제한으로 인해 충돌을 완전히 제거할 수는 없으며, 표준 해시 알고리즘은 큰 테이블을 사용하더라도 여전히 상당한 충돌을 발생시킬 수 있습니다.

2. 방법론: MPZCH

저자들은 고성능 CUDA 커널로 구현된 새로운 인덱싱 메커니즘인 **다중 프로브 제로 충돌 해시 (MPZCH)**를 제안합니다. 이는 충돌을 완화하고 ID 수명 주기를 능동적으로 관리하기 위해 선형 프로빙과 보조 상태 관리를 결합합니다.

2.1 핵심 구성 요소

• 보조 텐서: MPZCH 는 임베딩 테이블 alongside 두 개의 텐서를 유지합니다:
  • 식별자 (Identities) 텐서: 각 슬롯을 차지하는 특정 ID 를 기록합니다 (초기값 -1 로 설정). 이를 통해 커널은 점유된 슬롯과 사용 가능한 슬롯을 엄격하게 구분할 수 있습니다.
  • 메타데이터 텐서: 퇴거 결정을 안내하기 위해 시간 제한 (TTL) 값이나 타임스탬프와 같은 보조 정보를 저장합니다.
• 이중 패스 선형 프로빙: 일관성을 보장하고 중복 저장이나 조기 퇴거를 방지하기 위해 커널은 각 ID 에 대해 이중 패스 스캔을 실행합니다:
  1. 패스 1 (발견): ID 가 이미 존재하는지 확인하기 위해 프로브 범위를 스캔합니다. 쓰기 작업은 발생하지 않습니다.
  2. 패스 2 (작업): 패스 1 결과에 따라 다음을 수행합니다:
     • 업데이트: ID 가 존재하면 메타데이터 (예: 타임스탬프) 를 갱신합니다.
     • 할당: ID 가 새로운 경우, 커널은 빈 슬롯을 찾거나 만료된 항목을 퇴거시키려고 시도합니다.
     • 충돌 폴백: 프로브 범위 내에서 빈 슬롯이나 퇴거 가능한 슬롯을 찾지 못하면, 시스템은 초기 해시 슬롯을 기본값으로 사용합니다 (충분한 테이블 크기와 프로브 깊이를 가진 경우 이는 드뭅니다).

2.2 퇴거 및 신선도 전략

MPZCH 는 테이블 용량을 관리하고 신선도를 보장하기 위해 구성 가능한 퇴거 정책을 도입합니다:

• TTL (Time-To-Live) 정책: 메타데이터 타임스탬프가 현재 훈련 타임스탬프보다 낮으면 슬롯은 만료된 것으로 표시됩니다. 퇴거는 게으른 (lazy) 방식으로, 새로운 ID 가 할당을 필요로 할 때만 트리거됩니다.
• LRU (Least Recently Used) 정책: 커널은 가장 오래된 타임스탬프를 가진 항목을 퇴거하기 위해 프로브 범위를 스캔합니다.
• 옵티마이저 리셋: 중요하게는, 퇴거 시 임베딩 가중치와 옵티마이저 상태 (예: 모멘텀) 모두 리셋됩니다. 이는 새로운 아이템이 노후화된 임베딩을 상속받는 것을 방지하여 처음부터 학습하도록 보장합니다.

2.3 시스템 통합

• TorchRec 통합: MPZCH 는 메타의 TorchRec 라이브러리와 원활하게 통합되도록 설계되었습니다. 식별자 및 메타데이터 텐서는 임베딩 테이블과 일치하도록 랭크 간에 행 단위 (row-wise) 로 샤딩되어, 모든 연산이 복잡한 랭크 간 동기화 없이 샤드 내에서 로컬로 유지됩니다.
• 추론 최적화: 모델 발행 시 모델 크기를 줄이기 위해 메타데이터 텐서는 생략되고 식별자 텐서는 고정됩니다. 추론 서비스는 엄격히 읽기 전용이 되어 결정론적이고 효율적인 조회를 제공합니다.
• 스트리밍 업데이트: 시스템은 스트리밍 업데이트를 통한 온라인 훈련을 지원하여, 식별자 텐서가 임베딩 행 수정과 일관되게 유지되도록 합니다.

3. 주요 기여

1. 제로 충돌 보장: 충분한 테이블 크기와 구성 가능한 프로브 깊이를 결합함으로써, MPZCH 는 표준 해싱으로 달성하기 어려운 사용자 임베딩에 대한 임베딩 충돌을 효과적으로 제거합니다.
2. 능동적 수명 주기 관리: 정적 해시 테이블과 달리, MPZCH 는 노후화된 ID 를 능동적으로 퇴역시키고 옵티마이저 상태를 리셋하여 "부정적 전이" 문제를 직접 해결하고 모델 신선도를 향상시킵니다.
3. 고성능 구현: 이 알고리즘은 수만 개의 ID 를 병렬로 처리하는 맞춤형 CUDA 커널로 구현되었습니다. 벤치마크에 따르면 선형 프로빙 오버헤드는 무시할 수준이며 (프로브 깊이가 증가해도 지연 시간이 안정적으로 유지됨), 기존 방법과 비교 가능한 훈련 QPS 및 추론 지연 시간을 유지합니다.
4. 오픈소스 출시: 이 솔루션은 오픈소스 TorchRec 라이브러리 내에서 출시되었습니다.

4. 실험 결과

저자들은 엄격한 온라인 A/B 테스트와 오프라인 벤치마크를 통해 MPZCH 를 평가했습니다:

• 충돌률: 1 억 5 천만 개의 고유 사용자 ID 를 사용한 실험에서, MPZCH 는 2 억 개 (1.33 배 용량) 의 테이블 크기와 256 의 프로브 깊이로 제로 충돌을 달성했습니다. 반면, 기준선인 Sigrid 해시는 ID 카디널리티의 3 배인 테이블 크기를 사용하더라도 약 30% 의 충돌률을 유지했습니다.
• 사용자 임베딩 (동영상 순위 매기기): 월간 활성 사용자 30 억 명을 서비스하는 생산 환경의 동영상 순위 매기기 모델에 배포되었습니다. 충돌 제거는 17 개 예측 작업 중 14 개에서 정규화 엔트로피 (NE) 를 통계적으로 유의미하게 개선시켰으며, 공유 (+0.38%) 및 동영상 조회수 (+0.12%) 를 포함합니다.
• 아이템 임베딩 (동영상 검색): TTL 기반 퇴거 (게시물은 24 시간, 소유자는 72 시간) 를 적용한 HSTU 기반 검색 모델에 통합되었습니다.
  • 성능: 새로운 동영상 (48 시간 이내에 게시된) 은 노출수가 0.83% 증가했습니다.
  • 의미론적 품질: t-SNE 분석은 MPZCH 가 동일한 제작자의 동영상에 대한 임베딩 클러스터링을 크게 개선했음을 보여주었습니다. 동일일 게시물의 제작자 내 유사성은 0.66% 에서 0.91% 로 증가하여 (+38% 상대적 향상) 나타났습니다.
  • 학습 안정성: 임베딩 궤적이 더 매끄럽고 일관되게 되어, 해시 충돌로 인해 기준선 모델에서 관찰되었던 변동적인 급변이 제거되었습니다.

5. 의의

이 논문은 MPZCH 가 현대 추천 시스템을 위한 이중 우위 솔루션을 제공한다고 주장합니다. 첫째, 충돌 없는 환경을 보장함으로써 확률적 간섭을 제거하여 임베딩 품질과 예측 정확도를 높입니다. 둘째, 능동적 퇴거 및 옵티마이저 리셋 메커니즘을 도입하여 임베딩 신선도를 근본적으로 향상시켜, 무제한 메모리 증가 없이 모델이 변화하는 데이터 분포에 빠르게 적응할 수 있도록 합니다. 저자들은 모델 신선도와 품질 모두에서의 이러한 경험적 개선이 대규모 추천 시스템을 위한 견고한 솔루션으로서 MPZCH 를 검증한다고 결론지었습니다.