# 웹 크롤러

**목차**

## 웹 크롤러

- 웹에 새로 올라오거나 갱신된 콘텐츠를 찾아내는 기술

### 활용

- 검색 엔진 인덱싱 : 웹 페이지를 모아 로컬 인덱스를 만든다. (Googlebot)

- 웹 아카이빙 : 장기보관을 목적으로 정보를 모음

- 웹 마이닝 : 유용한 지식을 도출

- 웹 모니터링 : 저작권, 상표권 침해 사례 모니터링

### 알고리즘

1. URL 집합의 모든 웹 페이지를 다운로드한다.

2. 다운받은 웹 페이지에서 URL들을 추출한다.

3. 추출한 URL로 1부터 반복한다.

### 속성

- **규모 확장성** : 여러 대의 크롤러로 병렬 수집한다.

- **안정성(robustness)** : 비정상적 입력이나 환경에 대응한다.

- **예절(politeness) **: 짧은 시간에 너무 많은 요청을 보내면 안된다.

- **확장** : 새로운 형태의 콘텐츠(음악, 영상 등)를 쉽게 지원해야 한다.

- **관리과 재구성** : 여러 지표와 설정을 위한 인터페이스를 정해야 한다.

## 설계

### 개력적 설계안

![Image](https://upload.cafenono.com/image/slashpageHome/20240820/134402_lSy6tSfwmY6ORDqBtK?q=80&s=1280x180&t=outside&f=webp)

- **seed URLs** : 크롤링의 시작 주소 지정

    - 루트 도메인(*.naver.com, *.google.com)을 쓴다.

    - 지역, 주제별로 다른 seed를 사용한다.

- **URL Frontier** : 아직 fetch 되지 않은 URL FIFO queue

- **HTML Fetcher** : URL Frontier에서 주소를 가져와 웹 페이지를 다운로드한다.

- **DNS Resolver** : URL을 IP로 바꾼다.

- **HTML Parser** : parsing과 validation을 수행, 불필요한 웹 페이지를 버린다.

- **Duplicate Detection** : 웹 페이지의 해시값을 비교해서 중복을 제거한다.

- **Data Storage & Caching **: HTML 문서를 저장한다.

- **URL Extractor** : 파싱한 HTML 페이지 중 URL을 추출한다. 상대 경로는 절대 경로로 변환한다.

- **URL Filter** : 특정 확장자, 오류가 나는 URL, deny list에 있는 URL 등 규칙에 의해 배제한다.

- **URL Lodaer/Detector** : 블룸 필터나 해시 테이블로 중복 URL을 제거한다.

- **URL Storage** : 이미 방문한 URL을 보관

## 상세 설계

### DFS vs BFS

- 웹은 하이퍼링크로 연결된 방향이 있는 그래프이다. 

- 크롤링은 이 그래프를 탐색하는 것이고, DFS 혹은 BFS 알고리즘을 사용한다.

- 웹 그래프의 깊이를 알 수 없으므로 DFS는 적합하지 않다.

- 링크는 같은 서브 도메인을 가리키는 경향이 크기 때문에, BFS(너비 우선 탐색)를 사용하면 한 서버에 많은 부하를 줄 수 있다. (impolite)

- 그래서 페이지 순위, 트래픽 등을 지표로 BFS 큐의 우선순위를 조정한다.

### URL Frontier

BFS 알고리즘의 큐를 구현한 컴포넌트이다. politeness와 freshness를 구별한다.

![Image](https://upload.cafenono.com/image/slashpageHome/20240820/134403_oXk3wlJQkTfDmgQRZv?q=80&s=1280x180&t=outside&f=webp)

**우선순위(Priority)**

- 페이지 랭크, 트래픽 양, 갱신 빈도 등의 지표를 사용해 우선순위를 정한다.

- **Priority Router** : 우선순위별로 URL을 큐에 넣는다.

- **Priority Selector **: 높은 순위부터 데이터를 꺼내 넘긴다.

**예의(politeness)**

- 예의 바른 크롤러는 동일 웹 사이트에 대해서는 한 번에 한 페이지만 요청한다.

- 이를 위해 호스트 이름별로 다른 FIFO 큐를 만들고 이 큐들을 돌아가면서 사용한다.

- **Politeness Router **: 호스트별로 URL을 큐에 넣는다. 

- **Politeness Selector** : 큐를 순회하면서 하나씩 URL을 꺼낸다.

- **Mapping Table** : 호스트 이름과 큐를 매핑한다.

**신선도(Freshness)**

- 이미 같은 페이지도 주기적으로 다시 다운로드한다. 

- 웹 페이지 변경 이력, 우선순위를 고려하여 다운로드 주기를 결정한다.

**저장장치**

URL이 방대하기 때문에 일단 메모리 버퍼에 넣고 천천히 디스크에 저장하는 방식을 쓴다.

### HTML Fetcher

**Robots.txt**

- 로봇 제외 프로토콜이라고도 불리며, 크롤러가 수집해도 되는 페이지 목록을 정한 파일이다.

**성능 최적화**

- **분산 크롤링** : Politeness Selector는 여러 서버로 URL을 배분한다. 

- **DNS Resolver 캐싱** : DNS를 cron job을 통해 주기적으로 캐싱한다.

- **지역성 **: 크롤링 서버를 웹 서버가 있는 지역에 둬서 latency를 줄인다.

- **짧은 타임아웃** : 오래 기다리지 말고 빨리빨리 다음 페이지로 넘어간다.

**안정성**

- 안정 해시 : 부하를 효율적으로 분산한다.

- **크롤링 상태 및 수집 데이터 저장** : 크롤링 서버에 장애가 발생할 경우 쉽게 복구할 수 있다.

- **예외 처리**

- **데이터 검증**

**확장성**

- 위 그림처럼 기능별로 컴포넌트를 분리해서 새로운 컴포넌트를 추가하고 변경하기 용이하도록 한다.

**문제 있는 콘텐츠 감지 및 회피**

- **중복 콘텐츠** : 해시나 체크섬으로 탐지

- **spider trap** : 무한히 깊은 URL에 빠지지 않도록 최대 길이를 제한하거나 deny list를 설정한다.

- **데이터 노이즈** : 광고, 스팸 URL 등을 제거한다.

## 추가 논의

- **Server-side Rendering(Dynamic Rendering)** : 요즘은 동적으로 웹사이트를 만들기 때문에 단순히 HTML만 다운로드하면 안되고, 렌더링을 한 다음 파싱해야 한다.

- **원치 않는 페이지 필터링** : 품질이 조악하거나 스팸인 사이트를 거른다.

- **데이터베이스 다중화 및 샤딩** : Data layer의 가용성(HA), 확장성, 안정성이 좋아진다.

- **수평 확장** : 서버를 stateless하게 만들어 수평 확장을 하여 대규모 작업을 수행한다.

- **가용성(HA), 확장성, 안정성** : 사용자 수에 따른 규모 확장성 참조

- **데이터 분석** : 데이터를 분석해 시스템을 세밀하게 조정한다.

## 출처

- **Designing Web Crawler: System Design Interview Question : **[https://www.enjoyalgorithms.com/blog/web-crawler](https://www.enjoyalgorithms.com/blog/web-crawler)

For the site tree, see the [root Markdown](https://slashpage.com/kaonmir.md).