서론: 웹 크롤러란?
웹 크롤러
- 로봇(robot), 스파이더(spider)라고도 부름
- 검색 엔진에 널리 쓰이는 기술로 웹에 새로 올라오거나 갱생된 콘텐츠를 찾아내는 것이 목적
- 몇 개의 웹 페이지에서 시작하여 그 링크를 따라 나가면서 새로운 콘텐츠를 수집함 몇 개의 웹 페이지에서 시작하여 그 링크를 따라 나가면서 새로운 콘텐츠를 수집함
활용
1. 검색 엔진 인덱싱(search engine indexing)
- 크롤러의 가장 보편적인 용례
- 크롤러는 웹 페이지를 모아 검색 엔진을 위한 로컬 인덱스를 만든다
- Googlebot은 구글 검색 엔진이 사용하는 웹 크롤러
- 웹 아카이빙(web archiving)
- 나중에 사용할 목적으로 장기보관하기 위해 웹에서 정보 모으는 절차를 의미
- 많은 국립 도서관이 크롤러를 돌려 웹 사이트를 아카이빙하고 있음
- 미국 국회 도서관, EU 웹 아카이브 등
- 웹 마이닝(web minig)
- 웹의 폭발적 성장세는 데이터 마이닝 업계에 전례 없는 기회
- 웹 마이닝을 통해 인터넷에서 유용한 지식을 추출해낼 수 있음
- 금융 기업들은 크롤러를 사용해 총회 자료나 연차 보고서를 다운받아 기업의 핵심 사업 방향을 알아내기도 함
- 웹 모니터링(web monitoring)
- 크롤러를 사용하면 인터넷에서 저작권이나 상표권이 침해되는 사례를 모니터링할 수 있음
- 디지마크사 사는 웹 크롤러를 사용해 해적판 저작물을 찾아내 보고함
웹 크롤러의 복잡도
- 웹 크롤러가 처리해야 하는 데이터의 규모에 따라 달라짐
- 따라서 먼저 설계할 웹 크롤러가 감당해야 하는 데이터의 규모와 기능을 알아내야 함
1단계: 문제 이해 및 설계 범위 확정
웹 크롤러 기본 알고리즘
1. URL 집합이 입력으로 주어지면, 해당 URL들이 가리키는 모든 웹 페이지를 다운로드
2. 다운받은 웹 페이지에서 URL들을 추출
3. 추출된 URL들을 다운로드할 URL 목록에 추가하고 위의 과정을 처음부터 반복
하지만 실제로는 훨씬 복잡하므로 요구상황을 명확히 해야 함
주의해야 할 속성
- 규모 확장성: 웹은 거대하기 때문에 병행성을 활용하면 보다 효과적으로 웹 크롤링을 할 수 있을 것
- 안정성: 웹은 함정으로 가득하기 때문에 비정상적인 입력이나 환경에 잘 대응할 수 있어야 함
- 예절: 크롤러는 수집 대상 웹 사이트에 짧은 시간 동안 너무 많은 요청을 보내서는 안 됨
- 확장성: 새로운 형태의 콘텐츠를 지원하기 쉬워야 함
개략적 규모 추정
- 매달 10억 개의 웹 페이지를 다운로드
- QPS = 대략 400 페이지/초
- 최대 QPS = 800
- 웹 페이지 크기 평균은 500k로 가정
- 500TB/월 -> 5년 동안 30PB 저장 용량 필요
2단계: 개략적 설계안 제시 및 동의 구하기
구조 설계안
이 다이어그램에 등장하는 컴포넌트들이 어떤 기능을 수행하는지 살핀 후 크롤러의 작업 흐름을 알아보자
컴포넌트
시작 URL 집합
웹 크롤러가 크롤링을 시작하는 출발점
- 예시: 어떤 대학 웹사이트로부터 찾아 나갈 수 있는 모든 웹 페이지를 크롤링
- 해당 대학 도메인 이름이 붙은 모든 페이지의 URL을 시작 URL로 쓰는 게 가장 직관적인 방법
전체 웹을 크롤링해야 하는 경우 시작 URL을 고를 때 창의적일 필요가 있음 - 방법: 크롤러가 가능한 한 많은 링크를 탐색할 수 있도록 하는 URL을 고르는 것이 바람직할 것
1. 전체 URL 공간을 작은 부분집합으로 나누는 전략
나라별로 인기 있는 웹 사이트가 다르다는 점에 착안하는 것
2. 주제별로 다른 시작 URL을 사용하는 것
URL 공간을 쇼핑, 스포츠, 건강 등의 주제별로 세분화하고 그 각각에 다른 시작 URL을 쓰는 것
시작 URL로 무엇을 쓸 것이냐는 질문에 답은 없으므로 의도 전달 정도만 생각해라
미수집 URL 저장소
대부분의 현대적 웹 크롤러는 크롤링 상태를 (1) 다운로드할 URL, (2) 다운로드된 URL 두 개로 나눠 관리
=> 여기에서 다운로드할 URL을 저장/관리하는 컴포넌트가 미수집 URL 저장소(URL frontrer)
- FIFO 큐라고 생각하면 됨
- 상세 정보는 상세 설계에
HTML 다운로더
인터넷에서 웹 페이지를 다운로드하는 컴포넌트
- 다운로드할 페이지의 URL은 미수집 URL 저장소가 제공
도메인 이름 변환기
웹 페이지를 다운받으려면 URL을 IP 주소로 변환하는 절차가 필요한데, HTML 다운로더는 도메인 이름 변환기를 사용하여 URL에 대응되는 IP 주소를 알아냄
컨텐츠 파서
웹 페이지를 다운로드 하면 파싱, 검증 절차를 거챠야 함
-> 이상한 웹 페이지가 문제를 일으킬 수 있고, 저장 공간만 낭비하게 되기 때문
- 크롤링 서버 안에 콘텐츠 파서를 구현하면 크롤링 과정이 느려지게 될 수 있으므로 독립된 컴포넌트로 만든다
중복 콘텐츠?
웹 페이지의 해시 값을 비교해 중복을 줄이고 데이터 처리에 소요되는 시간을 줄이도록 함
콘텐츠 저장소
HTML 문서를 보관하는 시스템
저장소를 구현할 때 쓰일 기술을 고를 땐 저장할 데이터의 유형, 크기, 저장소 접근 빈도, 데이터 유효 기간 들을 종합적으로 고려해야 함
- 데이터의 양이 너무 많으므로 대부분의 콘텐츠는 디스크에 저장
- 인기 있는 콘텐츠는 메모리에 두어 접근 지연시간을 줄임
URL 추출기
HTML 페이지를 파싱하여 링크들을 골라내는 역할 담당
- 상대 경로를 전부 절대 경로로 변환
URL 필터
특정한 콘텐츠 타입, 파일 확장자를 갖는 URL, 접속 시 오류가 발생하는 URL, 접근 제외 목록(deny list)에 포함된 URL 등을 크롤링 대상에서 배제하는 역할을 함
이미 방문한 URL
구현을 위해 이미 방문한 URL이나 미수집 URL 저장소에 보관된 URL을 추적할 수 있게 하는 자료 구조를 사용할 것
이미 방문한 적 있는 URL인지 추적하면 같은 URL을 여러 번 처리하는 일을 방지해 서버 부하를 줄이고 시스템이 무한 루프에 빠지는 일을 방지할 수 있음
=> 이 자료 구조로 블룸 필터나 해시 테이블을 사용함
URL 저장소
이미 방문한 URL을 보관하는 저장소
웹 크롤러 작업 흐름
1. 시작 URL들을 미수집 URL 저장소에 저장
2. HTML 다운로더는 미수집 URL. 저장소에서 URL 목록을 가져옴
3. HTML 다운로더는 도메인 이름 변환기를 사용하여 URL의 IP 주소를 알아
내고, 해당 IP 주소로 접속하여 웹 페이지를 다운받음
4. 콘텐츠 파서는 다운된 HTTMIL 페이지를 파싱하여 올바른 형식을 갖춘 페이지인지 검증
5. 콘텐츠 파싱과 검증이 끝나면 중복 콘텐츠인지 확인하는 절차를 개시
6. 중복 콘텐츠인지 확인하기 위해서, 해당 페이지가 이미 저장소에 있는지 봄
• 이미 저장소에 있는 콘텐츠인 경우에는 처리하지 않고 버림
• 저장소에 없는 콘텐츠인 경우에는 저장소에 저장한 뒤 URL 추출기로 전달
7. URL 추출기는 해당 HTML 페이지에서 링크를 골라냄
8. 골라낸 링크를 URL 필터로 전달
9. 필터링이 끝나고 남은 URL만 중복 URL 판별 단계로 전달
10. 이미 처리한 URL인지 확인하기 위하여, URL 저장소에 보관된 URIL인지 살피고, 이미 저장소에 있는 URL은 버림
11. 저장소에 없는 URL은 URL 저장소에 저장할 뿐 아니라 미수집 URL 저장소에도 전달
3단계: 상세 설계
DFS VS BFS
크롤링 프로세스는 유향 그래프를 에지를 따라 탐색하는 과정
(페이지=노드, URL=에지)
DFS와 BFS는 그래프 탐색에 널리 사용되는 알고리즘이나, DFS는 좋은 선택이 아닐 가능성이 높음
-> 그래프 크기가 클 경우 어느 정도로 깊숙하게 가게 될지 가늠이 어렵기 때문
웹 크롤러는 보통 BFS(너비 우선 탐색법)을 사용
- FIFO 큐를 사용하는 알고리즘
큐의 한쪽에 탐색할 URL을 넣고, 다른 한쪽으로는 꺼내기만 하면 되는데 문제점이 있음
문제점
1. 한 페이지에서 나오는 링크의 상당수는 같은 서버로 되돌아감
Ex) wikipedia.com 페이지에서 추출한 모든 링크는 내부 링크(동일한 wikipedia.com 서버의 다른 페이지를 참조하는 링크)
- 따라서 크롤러는 같은 호스터에 속한 많은 링크를 다운받느라 바빠지게 되는데 이 링크들을 병렬로 처리하면 수많은 요청으로 위키피이다 서버는 과부하가 걸릴 것
=> 이런 크롤러는 보통 '예의 없는(impolite)' 크롤러로 간주함
2. 표준적 BFS 알고리즘은 URL 간에 우선순의를 두지 않음
처리 순서에 있어 모든 페이지를 공평하게 대우하는데 => 모든 웹 페이지가 같은 수준의 품질, 중요성을 갖지 않으므로 척도에 맞춰 우선순위 구별이 필요함
미수집 URL 저장소
미수집 URL 저장소를 활용해 위의 문제를 좀 쉽게 해결할 수 있음
=> 이 저장소를 잘 구현하면 '예의(politeness)'를 갖춘 크롤러, URL 사이의 우선순위와 신선도(freshness)를 구별하는 크롤러를 구현할 수 있음
예의
예의를 챙기기 위한 한 가지 원칙 => 동일 웹 사이트에 대해서는 한 번에 한 페이지만 요청
같은 웹 사이트의 페이지를 다운받는 테스크는 시간차를 두고 실행하도록 하면 될 것
이 요구사항을 만족시키려면 => 웹사이트의 호스트명, 다운로드를 수행하는 작업 스레드 사이의 관계를 유지하면 됨
각 다운로드 스레드는 별도 FIFO 큐를 가지고 있어 해당 큐에서 꺼낸 URL만 다운로드함
우선순위
유용성에 따라 페이지랭크, 트래픽 양, 갱신 빈도 등 다양한 척도를 사용할 수 있음
신선도
웹 페이지는 수시로 추가되고, 삭제되고, 변경됨 -> 따라서 데이터의 신선함을 유지하기 위해서는 이미 다운로드한 페이지라고 해도 주기적으로 재수집할 필요가 있음
최적화 전략
- 웹 페이지의 변경 이력 활용
- 우선순위를 활용하여 중요한 페이지는 좀 더 자주 재수집
미수집 URL 저장소를 위한 지속성 저장장치
대부분의 URL은 디스크에 두고 IO 비용을 줄이기 위해 메모리 버퍼에 큐를 두는 것
버퍼에 있는 데이터는 주기적으로 디스크에 기록할 것
HTML 다운로더
HTTP 프로토콜을 통해 웹 페이지를 내려 받는데 다운로더에 대해 알아보기 전에 먼저 로봇 제외 프로토콜부터 살펴보자
Robots.txt
웹사이트가 크롤러와 소통하는 표준적 방법
이 파일에는 크롤러가 수집해도 되는 페이지 목록이 들어 있음 => 웹 사이트를 긁어 가기 전에 크롤러는 해당 파일에 나열된 규칙을 먼저 확인해야 함
성능 최적화
1. 분산 크롤링
- 성능을 높이기 위해 크롤링 작업을 여러 서버에 분산하는 방법
- 각 서버는 여러 스레드를 돌려 다운로드 작업을 처리
- 이 구성을 위해 URL 공간은 작은 단위로 분할하여 각 서버가 그중 일부의 다운로드를 담당하도록 함
2. 도메인 이름 변환 결과 캐시
DNS 요청을 보내고 결과를 받는 작업의 동기적 특성 때문에 크롤러 성능의 병목 중 하나가 됨
따라서 DNS 조회 결과로 얻어진 도메인 이름과 IP 주소 사이의 관계를 캐시에 보관해 놓고 크론 잡 등을 돌려 주기적으로 갱신하도록 하면 성능을 높일 수 있음
3. 지역성
크롤링 작업을 수행하는 서버를 지역별로 분산하는 방법
-> 크롤 서버, 캐시, 큐, 저장소 등 대부분의 컴포넌트에 적용 가능
4. 짧은 타임아웃
대기 시간이 길어지면 좋지 않으므로 최대 얼마나 기다릴지 정해 놓고 이 시간 동안 응답하지 않으면 크롤러는 해당 페이지 다운로드를 중단하고 다음 페이지로 넘어감
안정성
- 안정 해시: 다운로더 서버들에 부하를 분산할 때 적용 가능한 기술
- 크롤링 상태 및 수집 데이터 저장
- 예외 처리
- 데이터 검증
확장성
진화하지 않는 시스템은 없으므로 새로운 형태의 콘텐츠를 쉽게 지원할 수 있도록 신경 써야 함
문제 있는 콘텐츠 감지 및 회피
1. 중복 콘텐츠
해시나 체크섬을 사용해서 중복 콘텐츠 탐지
2. 거미 덫
크롤러를 무한 루프에 빠지도록 설계한 웹페이지
자동으로 피해가는 알고리즘 만드는 건 까다로움
3. 데이터 노이즈
쓸모 없는 데이터는 제외해야 함
4단계: 마무리
