정보 검색 시스템 구축의 도전과제

[YeonwooSung]

[2009 WSDM] 대규모 정보 검색 시스템 구축의 과제

1. 정보 검색 시스템의 기본 원리

• 정보 검색 시스템은 과학과 공학의 결합으로, 다양한 컴퓨터 과학 분야(아키텍처, 분산 시스템, 알고리즘, 압축, 정보 검색, 기계 학습, UI 등)를 포괄함
• 소규모 팀으로도 수억 명이 사용하는 시스템을 만들 수 있음

2. 검색 시스템의 중요 차원

• 여러 엔지니어링 트레이드오프를 고려해야 함: 색인된 문서 수, 초당 쿼리 처리량, 색인 갱신 주기, 쿼리 지연 시간, 문서별 정보량, 점수 계산/검색 알고리즘의 복잡성
• 1999년부터 2009년까지 Google의 발전: 문서 수(~100배 증가), 쿼리 처리량(~1000배 증가), 문서별 정보(~3배 증가), 갱신 지연 시간(월 단위에서 분 단위로, ~10000배 향상), 쿼리 지연 시간(~5배 감소), 컴퓨팅 리소스(~1000배 증가)

3. 색인 분할 방식

• 문서 기반 분할: 각 샤드가 문서 하위 집합의 색인을 보유
  • 장점: 독립적 쿼리 처리, 문서별 정보 관리 용이, 네트워크 트래픽 적음
  • 단점: 모든 샤드가 쿼리 처리 필요, 다수 디스크 접근 필요
• 단어 기반 분할: 샤드가 모든 문서의 단어 하위 집합 보유
  • 장점: K 단어 쿼리는 최대 K개 샤드만 처리, 디스크 접근 감소
  • 단점: 네트워크 대역폭 요구 증가, 문서별 정보 관리 어려움

4. 색인 인코딩 및 최적화

• 1997-1999년: 단순한 바이트 정렬 형식 사용
• 개선된 블록 기반 가변 길이 형식 도입으로 공간 및 CPU 사용 최적화
• 그룹 Varint 인코딩 같은 효율적인 인코딩 기술 개발로 디코딩 속도 개선

5. 분산 시스템 인프라

• GFS(Google File System): 대규모 분산 파일 시스템
• MapReduce: 대규모 작업 작성/실행 간소화
• BigTable: 반구조화된 저장 시스템으로 문서 정보 온라인 관리

6. 실험적 접근

• 랭킹 아이디어 테스트를 위한 오프라인 실험 → 작은 트래픽 비율로 라이브 실험 → 성공 시 출시
• 성능 튜닝과 재구현을 통해 전체 부하에서 실현 가능하도록 함

7. 미래 방향 및 도전과제

• 다국어 정보 검색: 모든 문서를 모든 언어로 번역
• 액세스 제어 목록(ACL)이 있는 검색 시스템: 개인, 반개인, 공유, 공개 문서 혼합 효율적 관리
• 효율적인 IR 시스템 자동 구성
• 반구조화된 데이터에서 정보 추출 개선

문서는 검색 시스템이 끊임없이 진화하며, 사용자 증가, 데이터 증가, 새로운 요구사항에 맞춰 지속적인 개선이 필요함을 강조합니다.