[HTTP] 웹 로봇 1

 웹 로봇은 사람과의 상호작용 없이 연속된 웹 트랜잭션들을 자동으로 수행하는 소프트웨어 프로그램이다. 그리고 각각의 방식에 따라 '크롤러', '스파이더', '웜', '봇' 등 여러 가지 이름으로 불린다. 

https://www.researchgate.net/figure/Root-set-and-base-set_fig4_220155931

크롤러와 크롤링

 웹 크롤러는 먼저 웹페이지를 한 개 가져오고, 그 다음 페이지가 가리키는 모든 웹페이지를 가져오고 하는 이 과정을 재귀적으로 반복하는 방식으로 웹을 순회하는 로봇이다. 이렇게 웹 링크를 재귀적으로 따라가는 로봇을 크롤러 혹은 스파이더라고 부르는데, HTML 하이퍼링크들로 만들어진 웹을 따라 "기어 다니기(crawl)" 때문이다. 

 인터넷 검색엔진은 웹을 돌아다니면서 그들이 만나는 모든 문서를 끌어오기 위해 크롤러를 사용한다. 이 문서들은 나중에 처리되어 검색 가능한 데이터베이스로 만들어지는데, 이는 사용자들이 특정 단어를 포함한 문서를 찾을 수 있게 해준다. 웹에는 수십억 개의(혹은 그 이상의) 웹 페이지가 존재하기 때문에 이를 처리하는 검색엔진 스파이더들은 가장 복잡한 로봇들 중 하나가 되었다. 

 

크롤러의 시작점

내가 열심히 크롤러를 만들었다고 하면, 이제 웹에 풀어(?)놔야 하지만, 그전에 우선 출발지점을 주어야 한다. 크롤러가 방문을 시작하는 URL들의 초기 집합은 루트 집합(root set)이라고 불린다. 루트 집합을 고를 때, 모든 링크를 크롤링하면 결과적으로 관심 있는 웹페이지들의 대부분을 가져오게 될 수 있도록 충분히 다른 장소에서 URL들을 선택해야 한다.

 그렇다면 웹을 크롤링하려면 어떤 루트 집합이 좋은가?

이미지 출처: HTTP: The Definitive Guide

 실제 웹에서는 모든 문서로 이어지게 되는 하나의 문서란 없다. 위 그림에서 보다시피, 만약 A에서 시작한다면, 순차적으로 결과는 얻을 수 있을망정, A에서 R로, A에서 K로 이어지는 연결 고리는 없다. 또한 몇몇 웹페이지들은 S, T, U와 같이 이 문서로 접근할 수 있는 어떤 링크도 없이 고립되어 있을 수도 있다. 아마도 이런 페이지는 새로 만들어지고 있어서 접근할 수 없이 고립되었거나, 혹은 정말 오래되어서 잘 알려져 있지 않은 것일 수도 있다. 

 일반적으로 웹의 대부분을 커버하기 위해 루트 집합에 너무 많은 페이지가 있을 필요는 없다. 예를들어 위에 그림과 같은 상황이라면, A, G, S가 루트 집합에 있기만 하면 모든 페이지에 도달할 수 있다. 

이미지 출처: http://www.xml-data.org/DZKJDXXBYWB/html/20180206.htm#zz

 일반적으로 좋은 루트 집합은 크고 인기 있는 웹 사이트(www.google.com), 새로 생성된 페이지들의 목록, 그리고 자주 링크되지 않는 잘 알려져 있지 않은 페이지들의 목록으로 구성되어 있다. 그리고 대규모 크롤러 제품들은 대부분 루트 집합에 새 페이지나 잘 알려지지 않은 페이지들을 추가하는 기능을 제공한다. 이 루트 집합은 시간이 지남에 따라 성장하며 새로운 크롤링을 위한 시드 목록이 된다. 

이미지 출처: http://www.xml-data.org/DZKJDXXBYWB/html/20180206.htm#zz

 

링크 추출과 상대 링크 정상화

크롤러는 웹을 돌아다니며 꾸준히 HTML 문서를 검색한다. 그리고 각 페이지 안에 들어있는 URL 링크들을 파싱 해서 크롤링할 페이지들의 목록에 추가한다. 크롤러가 크롤링을 진행하면서 탐색해야 할 새 링크를 발견함에 따라, 이 목록은 보통 급속히 확장된다. 그리고 크롤러들은 간단한 HTML 파싱을 해서 이들 링크들을 추출하고 상대 링크를 절대 링크로 변환할 필요가 있다. 

 

순환 피하기

크롤러는 웹을 크롤링할 때, 루프나 순환에 빠지지 않도록 매우 조심해야 한다.

이미지 출처: HTTP: The Definitive Guide

로봇들은 순환을 피하기 위해 반드시 그들이 어디를 방문했는지 알아야 한다. 순환의 문제점은 아래와 같다.

1. 크롤러를 루프에 빠뜨려서 같은 페이지들을 반복해서 가져오는데 모든 시간을 허비하게 만들 수 있다. 이러한 크롤러가 네트워크 대역폭을 다 차지하고 그 어떤 페이지도 가져올 수 없게 되어버릴 수 있다.
2. 크롤러가 같은 페이지만 반복해서 가져오면 웹 서버의 부담으로 이어진다. 만약 크롤러의 네트워크 접슨 속도가 충분히 빠르다면, 웹사이트를 압박하여 어떤 실제 사용자도 사이트에 접근할 수 없도록 막아버리게 될 수도 있다. 이러한 서비스 방해 행위는 법적인 문제제기의 근거가 될 수 있다. 
3. 만약 루프가 문제가 되지 않더라도 크롤러는 많은 수의 중복된 페이지들을 가져오게 된다. 우리의 검색엔진이 매번 똑같은 페이지만 반환하게 된다고 생각하면 된다.

크롤러가 방문한 곳 추적하기

사실 크롤러가 방문한 곳을 지속적으로 추적하는 것은 쉽지 않다. 만약 구글과 같은 검색엔진을 만든다고 하면, 전 세계 웹 콘텐츠를 크롤링해야 할 것이다. 그럼 최소 수십억 개의 URL을 방문할 준비가 필요할 것이다. URL들은 굉장히 많기 때문에, 어떤 URL을 방문했는지 빠르게 판단하기 위해서는 복잡한 자료 구조를 사용할 필요가 있다. 이 자료 구조는 속도와 메모리 사용 면에서 효과적이어야 한다. 

 만약 평균 URL이 40bytes이고, 5억 개의 URL을 크롤링했다면, 검색 데이터 구조는 이 URL들을 유지하기 위해 20GB 이상의 메모리를 요구한다. 

 그렇다면 웹 크롤러가 방문한 곳을 관리하기 위해서는 어떠한 기법들이 있을까?

 

트리 해시 테이블

복잡한 로봇이라면 방문한 URL을 추적하기 위해 검색 트리나 해시 테이블을 사용했을 수도 있다. 

 

느슨한 존재 비트맵

공간 사용을 최소화하기 위해, 몇몇 대규모 크롤러들은 존재 비트 배열(presence bit array)과 같은 느슨한 자료 구조를 사용한다. 각 URL은 해시 함수에 의해 고정된 크기의 숫자로 변환되고 배열 안에 대응하는 '존재 비트(presence bit)'를 갖는다. URL이 크롤링되었을 때, 해당하는 존재 비트가 만들어진다. 만약 이미 존재한다면, 크롤러는 그 URL을 이미 크롤링되었다고 간주한다. 

 물론 URL의 개수는 잠재적으로 무한한데 반해, 존재 비트 배열에는 유한한 개수의 비트만이 존재하기 때문에 존재 비트에 두 URL이 매핑되어 충돌할 잠재적 가능성이 존재한다. 이 경우 크롤러는 크롤링 한 적 없는 페이지를 크롤링 했다고 잘못 판단할 것이다. 큰 존재 비트를 사용해서 이런 일이 거의 일어나지 않도록 할 수 있다. 

 

체크 포인트

크롤러가 갑작스럽게 중단될 경우를 대비해, 방문한 URL의 목록이 디스크에 저장되었는지 확인한다.

 

파티셔닝

크롤링을 하기에 한 대의 컴퓨터로는 메모리, 디스크 공간, 연산 능력, 네트워크 대역폭이 충분하지 못할 수 있다. 병렬 크롤러를 구성하여 각 크롤러에게 URL들의 특정 '한 부분'이 할당되어 그에 대한 책임을 진다. 로봇들은 서로 도와 웹을 크롤링하며, 서로 도와주기도 한다.

이미지 출처: https://www.researchgate.net/publication/263352582_WebParFA_Web_Partitioning_Framework_for_Parallel_Crawler

별칭(Alias)과 로봇 순환

올바른 자료 구조를 갖추었더라도 URL이 별칭을 가질 수 있기 때문에 방문 추적이 힘들 수 있다. 예를 들어 https://www.naver.com과 https://www.naver.com:443은 같은 URL을 가리키게 되어있다. 이를 해결하기 위해 대부분의 웹 로봇은 여러 가지 방법을 사용한다.

 

URL 정규화

대부분의 웹 로봇은 URL들을 표준 형식으로 '정규화'한다. 예를 들면 아래와 같은 행동을 수행하는 것이다.

1. 포트 번호가 명시되지 않았다면, 호스트명에 ':80'을 추가한다.
2. 모든 %xx 이스케이핑된 문자들을 대응되는 문자로 변환한다.
3. # 태그들을 제거한다.

URL 정규화는 기본적인 문법의 별칭을 제거할 수 있지만, 로봇들은 표준 형식으로 변환하는 것만으로는 제거할 수 있는 다른 URL 별칭을 만날 수 있다. 예를 들어 만약 기본 페이지가 index.html인 페이지가 있다면 http://www.foo.com/와 http://www.foo.com/index.html은 웹 서버에 대한 지식 없이 중복을 피할 수 있는 방법이 없다. 순환을 막을 수 있는 완벽한 방법은 없기 때문에 다른 방법도 더 알아보자.

 

너비 우선 크롤링

깊이 우선 크롤링이 아니라 너비 우선 크롤링을 한다면, 순환에서 페이지를 받아오기 전에 다른 웹 사이트들에서 수십만 개의 페이지들을 받아올 수 있으며 순환의 영향을 최소화할 수 있다. 또한 너비 우선 크롤링은 요청을 더 분산시켜서 특정 서버가 압박받지 않도록 해준다는 점에서 대체로 좋은 생각이다. 한 로봇이 서버의 자원을 최소로 사용하도록 유지해준다.

 

스로틀링

로봇이 웹 사이트에서 일정 시간 동안 가져올 수 있는 페이지의 숫자를 제한한다. 만약 로봇이 순환을 건드려서 지속적으로 그 사이트의 별칭들에 접근을 시도한다면, 스로틀링을 이용해 그 서버에 대한 접근 횟수와 중복의 총 횟수를 제한할 수 있을 것이다.

 

URL 크기 제한

로봇은 일정 길이(보통 1KB)를 넘는 URL의 크롤링은 거부할 수 있다. 만약 순환으로 URL이 계속해서 길어진다면, 결국에는 길이 제한으로 인해 순환이 중단될 것이다. 주의해야 할 점은 이 기법을 적용하면 가져오지 못하는 콘텐츠들도 틀림없이 있을 것이라는 점이다. 

 

URL/사이트 블랙리스트

악의적으로 로봇 순환을 만들어 내거나 함정인 것으로 알려진 사이트와 URL의 목록을 만들어 관리하고 피하는 것이다. 또한 해당 사이트를 발견될 때마다 이 블랙리스트에 추가한다(이는 사람의 손을 필요로 한다). 블랙리스트는 크롤링 되는 것을 싫어하는 특정 사이트를 피하기 위해 사용될 수도 있다.

 

패턴 발견

파일 시스템의 심벌링 링크를 통한 순환과 같은 오설정들은 일정 패턴을 따르는 경향이 있다. 이런 패턴을 감지해서 로봇은 이를 잠재적인 순환으로 보고, 둘 혹은 셋 이상의 반복된 구성요소를 갖고 있는 URL을 크롤링하는 것을 거절한다. 

이미지 출처: HTTP: The Definitive Guide

콘텐츠 지문(fingerprint)

로봇들은 페이지의 콘텐츠에서 몇 바이트를 얻어내어 체크섬(checksum)을 계산한다. 이 체크섬은 그 페이지 내용의 간략한 표현이다. 만약 로봇이 이전에 보았던 체크섬을 가진 페이지를 가져온다면, 그 페이지의 링크는 크롤링하지 않는다.

체크섬(checksum) 함수는 어떤 두 페이지가 서로 내용이 다름에도 체크섬은 똑같을 확률이 낮은 것을 사용해야 한다. 콘텐츠 지문 생성용으로는 MD5와 같은 메시지 요약 함수가 인기 있다.

하지만 일부 웹 서버들은 동적으로 페이지를 수정하기 때문에 이러한 체킹을 방해할 수 있다.

이미지 출처: HTTP: The Definitive Guide

사람의 모니터링

(역시 사람?) 웹은 거친 곳이다. 로봇에 어떤 기법을 적용해도 해결할 수 없는 문제에 봉착하게 될 것이다. 모든 상용 수준의 로봇은 사람이 쉽게 로봇의 진행 상황을 모니터링해서 뭔가 특이한 일이 일어나면 즉각 인지할 수 있게끔 반드시 진단과 로깅을 포함하도록 설계되어야 한다. 

 

이외에도 더 좋은 스파이더 휴리스틱(spider heuristics)을 만들기 위한 작업은 현재 진행형이다^^;