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

> Clean Markdown view of GeekNews topic #20488. Use the original source for factual precision when an external source URL is present.

## Metadata

- GeekNews HTML: [https://news.hada.io/topic?id=20488](https://news.hada.io/topic?id=20488)
- GeekNews Markdown: [https://news.hada.io/topic/20488.md](https://news.hada.io/topic/20488.md)
- Type: news
- Author: [lemonmint](https://news.hada.io/@lemonmint)
- Published: 2025-04-23T12:18:29+09:00
- Updated: 2025-04-23T12:18:29+09:00
- Original source: [static.googleusercontent.com](https://static.googleusercontent.com/media/research.google.com/en//people/jeff/WSDM09-keynote.pdf)
- Points: 5
- Comments: 0

## Summary

대규모 정보 검색 시스템 설계 시 **인덱싱된 문서 수**, **초당 처리 쿼리 수**, **인덱스 최신성**, **쿼리 지연 시간** 등 여러 요소 간의 균형을 고려해야 합니다. 지난 10년간 시스템 규모와 성능 요구사항이 크게 변화하여, 시스템 설계는 지속적으로 진화해야 합니다. 초기 시스템 아키텍처는 **문서 ID 기반 샤딩**을 사용하여 쿼리를 처리했으며, **캐시 서버**와 **광고 시스템**을 연동하여 성능을 향상시켰습니다. 최근에는 **인메모리 인덱스 시스템**과 **유니버설 검색**을 통해 처리량과 지연 시간을 개선하고, 다양한 유형의 정보를 통합하여 제공하고 있습니다.

## Topic Body

#### 정보 검색 시스템의 주요 차원과 트레이드오프  
  
- 시스템 설계 시 다음과 같은 요소들 간의 엔지니어링 트레이드오프를 균형 있게 고려해야 합니다.  
    - 인덱싱된 문서의 수  
    - 초당 처리 쿼리 수 (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 시스템 자동 구축**: 현재 여러 목적별 시스템 사용 (초고속 업데이트용, 초대규모 문서용 등). (파라미터 입력 시 해당 요구사항에 맞는 효율적인 검색 시스템 자동 구축 가능한 단일 시스템 개발 가능성?)  
- **반정형 데이터로부터 정보 추출**: 명확한 시맨틱 레이블 데이터는 극소수. 테이블, 폼 등 반정형 데이터 풍부. (비정형/반정형 소스로부터 구조화된 정보 추출 개선 알고리즘/기법 필요 - 노이즈 많지만 중복성 활용, 여러 소스 정보 연관/결합/집계 능력)  
  
#### 결론  
  
- 대규모 정보 검색 시스템 설계 및 구축은 도전적이고 재미있는 작업입니다.  
- 새로운 검색 기술은 종종 새로운 시스템 설계를 필요로 합니다.

## Comments



_No public comments on this page._