웹 크롤러는 로봇 또는 스파이더라고 부른다.
웹 크롤러 사용 용도
- 검색 엔진 인덱싱: 크롤러의 가장 보편적인 사례. 웹 페이지를 모아 검색 엔진을 위한 로컬 인덱스를 만든다. 구글 봇은 구글 검색 엔진이 사용하는 웹 크롤러다.
- 웹 아카이빙: 나중에 사용할 목적으로 장기보관하기 위해 웹에서 정보를 모으는 절차. 국립 도서관이 크롤러를 돌려 웹 사이트를 아카이빙하고 있다.
- 웹 마이닝: 웹 마이닝을 통해 인터넷에서 유용한 지식을 도출해 낼 수 있다. 유명 금융 기업들이 크롤러를 사용해 주주 총회 자료나 연차 보고서를 다운받아 기업의 핵심 사업 방향을 알아낸다.
- 웹 모니터링: 인터넷에서 저작권이나 상표권이 침해되는 사례를 모니터링할 수 있다. 디지마크 사는 웹 크롤러를 사용해 해적판 저작물을 찾아내서 보고한다.
문제 이해 및 설계 범위
기본적인 크롤러 알고리즘
- URL 집합이 입력으로 주어지면, 해당 URL이 가리키는 모든 웹 페이지를 다운로드
- 다운받은 웹 페이지에서 URL에서 추출
- 추출된 URL을 다운로드할 URL 목록에추가하여 위의 과정을 반복
이처럼 단순하고 크롤러는 동작하지 않는다.
좋은 크롤러 특성
면접관과 클로러 기능 요구사항을 명확히하고, 좋은 웹크롤러가 만족시키는 특성도 주의하자.
- 규모의 확장성: 웹에는 수십억 개의 페이지가 존재하는데, 병행성을 활용하면 효과적으로 웹 크롤링을 할 수 있다.
- 안정성: 웹은 함정으로 가득하기 때문에 비정상적 입력이나 환경(악성 코드, 응답 없는 서버)에 잘 대응해야한다.
- 예절: 수집 대상 웹 사이트에 짧은 시간동안 많은 요청을 보내면 안 된다.
- 확장성: 새로운 형태의 콘텐츠를 지원하기 쉬워야 한다. 이미지 파일도 크롤링하고 싶다고 새로 설계하면 곤란하다.
개략적 규모 추정
면접관에게 질문하여 합의한 내용.
- 매달 10억 개의 웹 페이지 다운로드
- QPS(Queries Per Second) = 10억 / 30일 / 24시간 / 3600초 = 400 페이지 / 초
- 최대(Peak) QPS= 2 * QPS = 800
- 웹 페이지의 크기 평균은 500k
- 10억 페이지 * 500k = 500TB/월
- 5년간 보관하면 500TB * 12 개월 * 5 년 = 30 PB
개략적 설계안
컴포넌트들이 어떤 기능을 수행하는지 살펴보자.
시작 URL 집합
- 웹 크롤러가 크롤링을 시작하는 출발점
- 가능한 많은 링크를 탐색할수 있도록 URL을 고른다
- 전체 URL공간을 작은 부분집합으로 나누거나 주제별로 다른 URL을 고른다
미수집 URL 저장소
- 웹 크롤러는 크롤링 상태를 다운로드할 URL과 다운로드된 URL 두 가지로 나눠 관리한다.
- 다운로드할 URL을 저장하고 관리하는 컴포넌트를 미수집 URL 저장소(URL frontier)라고 한다.
- FIFO(First In First Out) 이라고 생각하면 된다.
HTML 다운로더
- 인터넷에서 웹 페이지를 다운로드하는 컴포넌트
- 다운로드할 페이지의 URL은 미수집 URL 저장소가 제공
도메인 이름 변환기
- 웹 페이지를 다운받으려면 URL을 IP 주소로 변환하는 절차가 필요
- URL에 대응하는 IP 주소를 알아낸다.
콘텐츠 파서
- 웹 페이지를 다운로드하면 파싱과 검증 절차를 거쳐야 한다,
- 크롤링 서버 안에 콘텐츠 파서를 구현하면 크롤링 과정이 느려지게 될 수 있으므로, 독립된 컴포넌트로 만든다.
중복 콘텐츠
- 웹 페이지는 29% 정도가 중복이다.
- 자료 구조를 도입하여 데이터 중복을 줄이고 데이터 처리에 소요되는 시간을 줄인다.
- 간단한 방법은 HTML 문서를 문자열로 비교하는 것이지만, 비효율적이다.
- 효과적인 방법은 해시 값을 비교하는것
콘텐츠 저장소
- HTML 문서를 보관하는 시스템
- 저장할 데이터의 유형, 크기, 저장소 접근 빈도, 데이터 유효 기간 등을 고려해야 한다.
- 본 설계에서는 디스크와 메모리를 동시에 사용하는 저장소를 택한다.
- 데이터 양이 많으므로 대부분의 콘텐츠는 디스크에 저장
- 인기 있는 콘텐츠는 메모리에 두어 접근 지연시간을 줄인다.
URL 추출기
- HTML 페이지를 파싱하여 링크들을 골라내는 역할을 한다.
URL 필터
- 특정한 콘텐츠 타입이나 파일 확장자를 갖는 URL, 접속 시 오류가 발생하는 URL, 접근 제외 목록에 포함된 URL 등을 클로링 대상에서 배제하는 역할
이미 방문한 URL
- 이미 방문한 URL이나 미수집 URL 저장소에 보관된 URL을 추적할 수 있도록 자료구조를 사용
- 여러번 처리하는 일을 방지할 수 있기 때문에 서버 부하를 줄이고 무한 루프에 빠지는 일을 방지
- 해시 테이블이나 블룸 필터을 사용한다.
URL 저장소
- 이미 방문한 URL을 보관하는 저장소
웹 크롤러 작업 흐름
- 시작 URL을 미수집 URL 저장소에 저장
- HTML 다운로더는 미수집 URL 저장소에서 URL 목록을 가져온다.
- HTML 다운로더는 도메인 이름 변환기를 사용해서 도메인의 IP주소를 알아내고 웹 페이지를 다운로드
- 콘텐츠 파서는 다운된 HTML 페이지를 파싱하여 올바른 형식을 갖춘 페이지인지 검증
- 콘텐츠 파싱과 검증이 끝나면 중복 콘텐츠인지 확인하는 절차를 진행
- 중복 콘텐츠인지 확인하기 위해서, 해당 페이지가 저장소에 있는지 확인
- 저장소에 있는 경우, 처리하지 않고 버린다.
- 저장소에 없는 경우, URL 추출기로 전달
- URL 추출기는 HTML 페이지에서 링크를 골라낸다.
- 골라낸 링크를 URL 필터로 전달
- 필터링이 끝나고 남은 URL만 중복 URL 판별 단계로 전달
- 이미지 처리한 URL인지 확인하기 위해 URL 저장소에서 확인
- 저장소에 없는 URL은 URL 저장소에 저장하고 미수집 URL 저장소에도 전달.
상세 설계
컴포넌트에서 사용한 구현 기술을 살펴본다.
- DFS vs BFS
- 미수집 URL 저장소
- HTML 다운로더
- 안정성 확보 전략
- 확장성 확보 전략
- 문제 있는 콘텐츠 감지 및 회피 전략
DFS vs BFS
- 웹은 유향 그래프(directed graph)
- 페이지는 노드(node), 하이퍼링크(URL)은 에지(edge)
- 유향 그래프를 탐색하는 알고리즘은 깊이 우선 탐색법(depth-first search, DFS)와 너비우선탐색(breath-frist search, BFS)를 널리 사용
- 그래프 크기가 클 수록 깊이 가늠이 안되기 때문에 DFS는 좋은 선택이 아닐 가능성이 높다.
- BFS는 FIFO 큐를 사용하는 알고리즘으로 한 쪽에는 탐색할 URL을 집어 넣고, 다른 한쪽은 꺼내기만 한다.
- 해당 방법은 두 가지 문제가 있다.
- 한 페이지에서 나오는 링크의 상당수는 같은 서버로 되돌아 간다.
- 특정 페이지에서 추출한 링크는 내부 링크, 즉 동일한 서버의 다른 페이지를 참조한다.
- 크롤러는 같은 호스트에 속한 많은 링크를 다운받느라 바쁘게 되고, 병렬로 처리하게 되면 해당 서버는 수많은 요청으로 과부하 걸리게 된다.
- 이런 크롤러는 예의 없는 크롤러로 간주 된다.
- 표준적 BFS 알고리즘은 URL 간에 우선순위를 두지 않는다.
- 처리 순서에 있어 모든 페이지를 공평하게 대우한다.
- 페이지 순위, 사용자 트래픽의 양,업데이트 빈도 등 여러 가지 척도에 비추어 처리 우선순위를 구별하는 것이 맞다.
- 한 페이지에서 나오는 링크의 상당수는 같은 서버로 되돌아 간다.
미수집 URL 저장소
미수집 URL 저장소를 활용하면 예의를 갖춘 크롤러, URL 사이의 우선순위와 신선도를 구별하는 크롤러를 구현할 수 있다.
예의
예의 바른 크롤러를 만드는데 있어서 한 가지 원칙을 지켜야한다.
동일 웹 사이트에 대해서는 한 번에 한 페이지만 요청한다는 것이다.
해당 요구사항을 만족시키려면 웹사이트의 호스트명과 다운로드를 수행하는 작업 스레드 사이의 관계를 유지하면 된다.
- 큐 라우터: 같은 호스트에 속한 URL은 언제나 같은 큐에 가도록 보장하는 역할
- 매핑 테이블: 호스트 이름과 큐 사이의 관계를 보관하는 테이블
- 큐 선택기: 큐들을 순회하면서 큐에서 URL을 꺼내서 해당 큐에서 나온 URL을 다운로드하도록 지정된 작업 스레드에 전달하는 역할
- 작업 스레드: 전달된 URL을 다운로드하는 작업을 수행 순차적으로 처리되며 작업들 사이에는 일정한 지연시간을 둘 수 있다.
우선순위
유용성에 따라 URL의 우선순위를 나눌 때는 페이지랭크, 트래픽, 갱신 빈도 등 다양한 척도를 사용한다.
순위우선결정장치는 URL 우선순위를 정하는 컴포넌트이다.
- 순위결정장치: URL을 입력으로 받아 우선순위를 계산
- 큐(f1, ... , fn): 우선순위별로 큐가 하나씩 할당. 우선순위가 높으면 선택될 확률도 올라간다.
- 큐 선택기: 임의 큐에서 처리할 URL을 꺼내는 역할을 담당. 순위가 높은 큐에서 더 자주 꺼내도록 프로그램되어 있다.
우선순위 + 예의
- 전면 큐: 우선쉰위 결정 과정을 처리
- 후면 큐: 크롤러가 예의 바르게 동작하도록 보증
신선도
웹 페이지는 수시로 추가되고, 삭제되고, 변경된다. 데이터의 신섬함을 유지해줘야 한다.
- 웹 페이지의 변경 이력 활용
- 우선순위를 활용하여, 중요한 페이지는 좀 더 자주 재수집
미수집 URL 저장소를 위한 지속성 저장장치
- 검색 엔질을 위한 크롤러의 경우, 처리해야 하는 URL의 수는 수 억개에 달한다.
- 모두 메모리에 보관하는 것은 안정성이나 규모 확장성 측면에서 바람직 하지 않다.
- 절충안 방법으로 대부분의 URL은 디스크에 두지만 IO 비용을 줄이기 위해 메모리 버퍼에 큐를 두는 것.
- 버퍼에 있는 데이터는 주기적으로 디스크에 기록한다.
HTML 다운로더
Robots.txt
- 로봇 제외 프로토콜(Robots.txt)이 있다.
- 웹 사이트가 크롤러와 소통하는 표준적 방법
- 해당 파일에는 크롤러가 수집해도 되는 페이지 목록이 들어 있다.
성능 최적화
아래는 HTML 다운로더에 사용할 수 있는 성능 최적화 기법
- 분산 크롤링
- 크롤링 작업을 여러 서버에 분산하여 성능을 높이는 방법
- 각 서버는 여러 스레드를 돌려 다운로드 작업을 처리한다. - 도메인 이름 변화 결과 캐시
- 도메인 이름 변환기는 크롤러 성능의 병목 중 하나로, DNS 요청을 보내고 결과를 받는 동기적 특성 때문
- DNS 조회 결과로 얻어진 도메인 이름과 IP 주소 사이의 관계를 캐시에 보관해 놓고 크론 잡(cron job) 등을 돌려 주기적으로 갱신하도록 하여 성능을 높이기 - 지역성
- 크롤링 작업을 수행하는 서버를 지역별로 분산하는 방법
- 크롤링 대상 서버와 지역적으로 가까우면 페이지 다운로드 시간이 줄어든다. - 짧은 타임 아웃
- 어떤 웹 서버는 응답이 느리거나 아예 응답하지 않는다.
- 이를 대비하여 미리 최대 얼마나 기다릴지 정해 놓는다.
안정성
최적화된 성능뿐 아니라 안정성도 다운로더 설계시 중요하게 고려해야 하는 부분
아래는 안정성을 향상시키기 위한 접근법
- 안정 해시: 다운로더 서버에 부하를 분산할 때 적용하는 기술로, 다운로더 서버를 쉽게 추가하고 삭제할 수 있다.
- 클로링 상태 및 수집 데이터 저장: 장애가 발생한 경우에도 쉽게 복구할 수 있도록 크롤링 상태와 수집된 데이터를 지속적으로 저장 장치에 기록하는 것
- 예외 처리: 에러는 불가피하기 때문에 전체 시스템이 중단되는 일이 없도록 해야한다.
- 데이터 검증: 시스템 오류를 방지하기 위한 중요 방법
확장성
새로운 형태의 콘텐츠를 쉽게 지원할 수 있도록 신경써야 한다.
문제 있는 콘텐츠 감지 및 회피
중복이거나 의미없거나 또는 유해한 콘텐츠를 어떻게 감지하고 차단하는지 살펴보자.
- 중복 콘텐츠
- 해시나, 체크섭을 사용하면 중복 콘텐츠를 쉽게 탐지할 수 있다.
- 거미 덫
- 크롤러를 무한 루프에 빠드리도록 설계한 웹 페이지
- 예시) spidertrapexample.com/foo/bar/foo/bar/foo/bar/...
- 모든 종류의 덫을 피할 수 있는 해결책은 없고, 알고리즘을 만드는 것도 어렵다.
- 한 가지 방법으로 사람이 수작업으로 덫을 확인하고 URL 필터 목록에 넣는 방법이 있다.
- 데이터 노이즈
- 콘텐츠가 가치가 없는 광고나 스팸 URL, 스크립트 코드 등이 있다.
- 가능하면 제외한다.
마무리
추가적으로 논의해보면 좋은 것들
- 서버 측 렌더링
- 많은 웹사이트가 자바스크립트, AJAX 등의 기술을 사용해서 링크를 즉석에서 만들어 낸다.
- 다운받아서 파싱하면 동적으로 생성되는 링크는 발견할 수 없기 때문에, 파싱하기 전 서버 측 렌더링(동적 렌더링)을 적용하여 해결한다.
- 원치 않는 페이지 필터링
- 크롤링에 소요되는 자원은 유한하기 때문에 스팸 방지 컴포넌트를 두어 품질이 안 좋거나 스팸성인 페이지는 거른다.
- 데이터베이스 다중화 및 샤딩
- 해당 기술을 적용하여 데이터 계층의 가용성, 규모 확장성, 안정성이 향상한다.
- 슈평적 규모 확장성
- 수평적 규모 확장을 달성하는데 중요한 것은 서버가 상태정보를 유지하지 않도록 하는 것, 무상태 서버로 만드는 것이다.
- 가용성, 일관성, 안전성
- 대형 시스템을 만들기 위해 필수적으로 고려해야하는 사항
- 데이터 분석 솔루션
- 시스템을 세밀하게 조정하기 위해서는 데이터를 수집하고 분석하는 것이 중요하다.
'읽은 책 > [책] 가상 면접 사례로 배우는 대규모 시스템 설계 기초 1권' 카테고리의 다른 글
11장. 뉴스 피드 시스템 설계 (1) | 2024.07.16 |
---|---|
10장. 알림 시스템 설계 (0) | 2024.07.15 |
8장. URL 단축기 설계 (3) | 2024.07.14 |
7장. 분산 시스템을 위한 유일 ID 생성기 설계 (0) | 2024.07.11 |
6장. 키-값 저장소 설계 (0) | 2024.07.09 |