▲

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

(static.googleusercontent.com)
5P by lemonmint 2일전 | ★ favorite | 댓글과 토론

정보 검색 시스템의 주요 차원과 트레이드오프

  • 시스템 설계 시 다음과 같은 요소들 간의 엔지니어링 트레이드오프를 균형 있게 고려해야 합니다.
    • 인덱싱된 문서의 수
    • 초당 처리 쿼리 수 (QPS)
    • 인덱스 최신성/업데이트 속도
    • 쿼리 지연 시간 (Latency)
    • 각 문서에 대해 저장되는 정보의 양
    • 점수 계산/검색 알고리즘의 복잡성/비용
  • 엔지니어링 난이도는 이러한 매개변수들의 곱에 비례하는 경향이 있습니다.
  • 이 모든 요소는 전체 성능 및 비용 대비 성능($당 성능)에 영향을 미칩니다.

시스템 규모의 변화 (1999 vs 2009)

  • 지난 10년간 시스템 규모와 성능 요구사항이 극적으로 변화했습니다.
    • # 문서: ~7천만 개 → 수십억 개 (~100배 증가)
    • 일일 처리 쿼리 수: (~1000배 증가)
    • 문서당 인덱스 정보: (~3배 증가)
    • 업데이트 지연 시간: 수개월 → 수 분 (~10000배 감소)
    • 평균 쿼리 지연 시간: <1초 → <0.2초 (~5배 감소)
    • 시스템 자원: 더 많은 머신 * 더 빠른 머신 (~1000배 증가)
  • 이러한 매개변수는 지속적으로, 때로는 몇 자릿수씩 변화하므로 시스템 설계는 끊임없이 진화해야 합니다.
    • 특정 시점(X)에 적합했던 설계가 10배, 100배 규모에서는 매우 잘못된 설계일 수 있습니다. (따라서 약 10배 성장을 염두에 두고 설계하되, 100배가 되기 전에 재작성을 계획해야 함)
    • 지난 10년간 7번의 주요 개편이 있었습니다.

초기 시스템 아키텍처 (1997-1999)

  • 연구 프로젝트 단계 (1997):
    • 프론트엔드 웹 서버가 쿼리를 받아 인덱스 서버들과 문서 서버들에 분산 처리 요청
    • 인덱스 서버: 문서 ID(docid) 기준 샤딩(sharding)
    • 문서 서버: 문서 ID(docid) 기준 샤딩
  • 기본 원칙:
    • 문서는 정수 ID (docids) 할당 (중요/고품질 문서에 작은 ID 부여)
    • 인덱스 서버: (쿼리) → 정렬된 (점수, docid, ...) 목록 반환. docid 기반 샤딩, 용량 확보 위해 복제(replication). 비용 O(#쿼리 * 인덱스 내 #문서).
    • 문서 서버: (docid, 쿼리) → (제목, 스니펫) 생성. docid → 디스크 상 문서 전문 매핑. docid 기반 샤딩. 비용 O(#쿼리).
  • 서빙 시스템 (1999):
    • 연구 프로젝트 구조에 캐시 서버, 광고 시스템 연동 추가
    • 인덱스/문서 서버 샤드 복제본(Replicas) 운영
    • 캐싱: 인덱스 결과와 문서 스니펫 모두 캐싱. 캐시 히트율 30-60%. 성능 향상 및 쿼리 지연 시간 감소에 큰 기여. (단, 인덱스 업데이트/캐시 플러시 시 큰 지연 시간 스파이크 발생 가능성 주의)

인덱스 파티셔닝 전략

  • 문서 기준 (By doc): 각 샤드가 문서 일부의 인덱스를 가짐 (Google 선택)
    • 장점: 샤드별 독립적 쿼리 처리, 추가적인 문서별 정보 유지 용이, 네트워크 트래픽(요청/응답) 적음
    • 단점: 모든 샤드가 쿼리를 처리해야 함, K개 단어 쿼리에 대해 N개 샤드에서 O(K*N) 디스크 탐색(seek) 필요
  • 단어 기준 (By word): 각 샤드가 전체 문서에 대한 단어 일부의 인덱스를 가짐
    • 장점: K개 단어 쿼리는 최대 K개 샤드만 처리, O(K) 디스크 탐색
    • 단점: 훨씬 높은 네트워크 대역폭 필요 (매칭된 문서의 단어별 정보를 한 곳에 모아야 함), 문서별 정보 유지 어려움

초기 크롤링 및 인덱싱 (1998-1999)

  • 크롤링:
    • 간단한 배치 크롤링 시스템: 시작 URL 목록 → 페이지 크롤링 → 링크 추출 및 큐 추가 → 충분한 페이지 수집 시 중단
    • 고려사항: 특정 사이트 과부하 방지, 미크롤링 페이지 우선순위 결정 (예: PageRank), 미크롤링 URL 큐 효율적 관리, 머신 장애 처리
  • 인덱싱:
    • 간단한 배치 인덱싱 시스템: 간단한 유닉스 도구 기반
    • 문제점: 체크포인팅 부재로 머신 장애 시 고통스러움, 원본 데이터 체크섬 부재로 하드웨어 비트 오류 문제 발생 (초기 머신 ECC/패리티 부재로 악화, "대부분 정렬됨" 문제), "적대적 메모리와 프로그래밍" 경험
    • 해결책: 작은 레코드 체크섬 저장 및 손상된 레코드 건너뛰기/재동기화 가능한 파일 추상화 개발

인덱스 업데이트 방식 (1998-1999)

  • 주기: 월 1회 정도
  • 과정:
    1. 트래픽 적은 시간대까지 대기
    2. 일부 복제본 오프라인 전환
    3. 새 인덱스를 오프라인 복제본에 복사
    4. 업데이트된 인덱스를 가리키는 새 프론트엔드 시작 및 일부 트래픽 처리
  • 인덱스 서버 디스크 활용 전략:
    • 디스크 외곽(outer part)이 더 높은 대역폭 제공
    1. (기존 인덱스 서비스 중) 새 인덱스를 디스크 내곽(inner half)에 복사
    2. 새 인덱스를 사용하도록 재시작
    3. 기존 인덱스 삭제
    4. 새 인덱스를 더 빠른 외곽(faster half)으로 재복사
    5. 내곽에 복사했던 첫 번째 새 인덱스 삭제
    6. 비워진 내곽 공간을 성능 향상 데이터 구조(예: Pair cache - 자주 함께 나오는 쿼리 용어 쌍의 포스팅 리스트 교차 결과 미리 계산) 구축에 활용

성장 대응 및 확장 (1999-2001)

  • '99, '00, '01년에 인덱스 크기 및 트래픽 급증 (~5천만 → 10억 페이지 이상, 월 20% 트래픽 성장 + Yahoo 파트너십으로 하룻밤 새 트래픽 2배 증가 등)
  • 인덱스 서버 성능이 매우 중요해짐: 지속적인 머신 증설 + 매월 10-30%의 소프트웨어 기반 성능 개선 필요
  • 확장 방식: 더 많은 샤드(Shards)와 복제본(Replicas) 추가
  • 시사점:
    • 샤드 응답 시간은 디스크 탐색 횟수와 읽어야 할 데이터 양에 영향받음
    • 성능 개선 가능 영역: 더 나은 디스크 스케줄링, 개선된 인덱스 인코딩

인덱스 인코딩 기술의 발전

  • 초기 인코딩 ('97): 매우 간단한 바이트 정렬 형식 (WORD → [docid+nhits:32b, hit:16b, hit:16b...]). 히트(hit)는 위치 + 속성(폰트 크기, 제목 등). 큰 포스팅 리스트용 스킵 테이블 추가. 디코딩은 저렴하나 압축률 낮아 많은 디스크 대역폭 요구.
  • 다양한 인코딩 기법:
    • 비트 레벨: Unary, Gamma, Rice_k (Golomb 코드 특수 사례), Huffman-Int
    • 바이트 정렬: varint (바이트당 7비트 + 연속 비트)
  • 블록 기반 인덱스 형식: 공간과 CPU 사용량 모두 감소 (~30% 크기 감소), 디코딩 속도 향상. 가변 길이 블록 사용. 헤더(델타, 길이 등) + 문서 ID 델타(Rice_k) + 히트 수(Gamma) + 히트 속성(런렝스 Huffman) + 히트 위치(Huffman-Int).
  • 새로운 인덱스 형식 (2004 이후): 단일 플랫 위치 공간 사용. 보조 자료구조로 문서 경계 추적. 포스팅 리스트는 델타 인코딩된 위치 목록. 컴팩트함과 매우 빠른 디코딩 속도 모두 중요.

인메모리 인덱스 시스템 (2001년 초)

  • 배경: 샤딩 확장 + 복제본 증가 → 전체 인덱스 사본을 메모리에 유지할 만큼 충분한 총 메모리 확보 가능
  • 아키텍처: 프론트엔드 → 로드 밸런서(bal) → 샤드 (샤드당 여러 인메모리 인덱스 서버 복제본)
  • 장점: 처리량(throughput) 대폭 증가, 지연 시간(latency) 대폭 감소 (특히 이전에 GB 단위 디스크 I/O 필요했던 복잡한 쿼리 빨라짐 - 예: "circle of life")
  • 문제점:
    • 분산(Variance): 수십 대가 아닌 수천 대 머신 사용 → 예측 어려움 증가 (예: 무작위 cron 작업 문제 유발)
    • 가용성(Availability): 각 문서 인덱스 데이터 복제본 수가 1개 또는 적음 → "죽음의 쿼리"(모든 백엔드 동시 다운), 머신 장애 시 인덱스 데이터 가용성 문제 (특히 중요 문서는 복제 필요)

후기 시스템 설계 및 기술 (2004년 이후)

  • 하드웨어: 더 큰 규모의 데이터 센터, 자체 설계 랙, PC급 마더보드, 저가형 스토리지/네트워킹 하드웨어, Linux + 자체 개발 소프트웨어
  • 서빙 디자인 (2004 에디션): 계층적 구조
    • Root 서버 → Parent 서버들 → Leaf 서버들 (GFS로부터 File Loader를 통해 Repository Shard 로드)
    • 캐시 서버 연동

Group Varint 인코딩

  • 아이디어: Varint 디코딩의 비효율성(많은 분기/시프트/마스크 연산) 해결. 4개의 정수 값을 그룹으로 묶어 5~17 바이트로 인코딩.
  • 방식:
    • 각 값의 바이트 길이(1~4바이트)를 나타내는 2비트 태그 4개를 모아 1바이트짜리 접두사(prefix) 바이트 생성.
    • 접두사 바이트 뒤에 실제 데이터 바이트들을 저장.
  • 디코딩: 접두사 바이트를 읽고, 이를 인덱스로 사용하여 미리 계산된 256개 항목 테이블 조회 → 오프셋과 마스크 정보 얻어 4개 값 한 번에 디코딩.
  • 성능: 기존 방식보다 훨씬 빠름 (Group Varint: ~400M/초, 7-bit Varint: ~180M/초, 30-bit Varint w/ 2-bit len: ~240M/초)

유니버설 검색 (2007)

  • 웹 검색 결과뿐 아니라 다양한 유형의 정보(이미지, 지역 정보, 뉴스, 비디오, 블로그, 도서 등)를 통합하여 보여주는 시스템.
  • Super root 노드가 여러 전문 검색 시스템(수직 검색 엔진)에 쿼리를 보내 결과를 취합.

저지연 크롤링 및 인덱싱의 과제

  • 수 분 내 업데이트 반영은 매우 어려운 과제.
  • 크롤링 휴리스틱: 어떤 페이지를 크롤링할 것인가?
  • 크롤링 시스템: 페이지를 빠르게 크롤링해야 함.
  • 인덱싱 시스템: PageRank, 앵커 텍스트 등 전역(global) 데이터에 의존 → 실시간 근사(online approximation) 필요.
  • 서빙 시스템: 쿼리 처리 중 업데이트를 받아들일 준비가 되어 있어야 함 (배치 업데이트 시스템과 매우 다른 자료구조 필요).

실험의 중요성과 인프라

  • 실험 용이성: 매우 중요 (빠른 실험 주기 → 더 많은 실험 → 더 많은 개선).
  • 실험 종류:
    • 쉬운 실험: 기존 데이터 가중치 조절 등.
    • 어려운 실험: 운영 인덱스에 없는 새로운 데이터 필요. (새 데이터 생성/통합 및 실험 사용 용이해야 함)
  • 핵심 인프라:
    • GFS: 대규모 분산 파일 시스템
    • MapReduce: 대규모 데이터 처리 작업을 쉽게 작성/실행. (운영 인덱스 데이터 생성 가속화, 임시 실험 신속 수행)
    • BigTable: 반정형(semi-structured) 스토리지 시스템. (문서별 정보에 대한 온라인/효율적 접근, 여러 프로세스가 비동기적 문서 정보 업데이트 가능 - 시간 단위 → 분 단위 업데이트에 중요)

실험 주기 및 출시

  1. 아이디어 구상 및 오프라인 실험:
    • MapReduce, BigTable 등으로 데이터 생성.
    • 오프라인 실험 실행 및 효과 검증 (인간 평가 쿼리셋, 무작위 쿼리셋 등).
    • 이 단계에서는 프로토타입의 지연 시간/처리량은 중요하지 않음.
    • 실험 결과 기반 반복 개선.
  2. 라이브 실험:
    • 오프라인 실험 결과가 좋으면, 실제 사용자 트래픽 일부(tiny sliver) 대상 라이브 실험 진행 (주로 무작위 샘플, 때로는 특정 쿼리 클래스 대상).
    • 이 단계에서는 처리량보다 지연 시간이 중요! 실험 프레임워크는 운영 환경 지연 시간에 가깝게 동작해야 함.
  3. 성능 튜닝 및 출시:
    • 라이브 실험 결과가 좋으면, 전체 부하에서 실행 가능하도록 성능 튜닝/재구현 (예: 런타임 계산 대신 데이터 사전 계산, "충분히 좋다면" 더 저렴한 근사치 사용).
    • 출시(Rollout) 프로세스 중요: 품질 vs 비용 트레이드오프 지속적 고려, 빠른 출시와 낮은 지연 시간/사이트 안정성 간의 균형 (검색 품질팀과 성능/안정성 담당팀 간의 좋은 협업 필요).

미래 방향 및 과제

  • 다국어 정보 검색 (Cross-Language IR): 전 세계 모든 문서를 모든 언어로 번역 → 인덱스 크기 급증, 계산 비용 높음. (번역 품질 지속 개선, 더 크고 복잡한 언어 모델 처리 위한 대규모 시스템 필요)
  • 정보 검색 시스템 내 접근 제어 목록 (ACLs): 개인/반개인/널리 공유된/공개 문서 혼합 환경. (크기가 매우 다양한 ACL 효율적 처리 시스템 구축 필요 - 10명 공유 문서와 전 세계 공유 문서 최적 솔루션 다름, 공유 패턴 시간 따라 변화 가능)
  • 효율적인 IR 시스템 자동 구축: 현재 여러 목적별 시스템 사용 (초고속 업데이트용, 초대규모 문서용 등). (파라미터 입력 시 해당 요구사항에 맞는 효율적인 검색 시스템 자동 구축 가능한 단일 시스템 개발 가능성?)
  • 반정형 데이터로부터 정보 추출: 명확한 시맨틱 레이블 데이터는 극소수. 테이블, 폼 등 반정형 데이터 풍부. (비정형/반정형 소스로부터 구조화된 정보 추출 개선 알고리즘/기법 필요 - 노이즈 많지만 중복성 활용, 여러 소스 정보 연관/결합/집계 능력)

결론

  • 대규모 정보 검색 시스템 설계 및 구축은 도전적이고 재미있는 작업입니다.
  • 새로운 검색 기술은 종종 새로운 시스템 설계를 필요로 합니다.