Design and Implementation of a High-Performance Distributed Web
웹 크롤러란?
방대한 웹 페이지를 방문하여 각종 정보를 자동적으로 수집하는 일을 하는 프로그램으로서 검색엔진의 근간이 됨
방대한 페이지를 고성능으로 방문하기 위한 이슈
- 좋은 크롤링 전략
- 고도화 된 시스템 아키텍쳐
크롤링 전략
Breadth-First Crawler : 크롤러는 작은 페이지 집합에서 시작하여 BF 방식을 기반으로 탐색
Crawling Pages for Updates : 최신 검색 인덱스를 유지하기 위해서 페이지 업데이트 이력에 대한 관찰이 중요
Focused Crawling : 전문화된 검색 엔진을 위해 크롤링 하므로 특정 종류의 페이지에 집중. 많은 대역폭을 사용하지 않고 최신의 많은 페이지를 찾는 것이 목적
Random Walking and Sampling : 웹 그래프에서 랜덤 워크를 사용하여 샘플 페이지 검색을 하거나 검색엔진 크기와 품질 평가에 사용
Crawling the “Hidden Web’” : 실제로 데이터베이스에 있지만 쿼리나 웹페이지에서 양식으로 접근이 가능한 데이터. 이러한 데이터에 자동으로 접근하려는 크롤러는 프론트 엔드 시스템으로 확장될 수 있는 것이 특징.
크롤러의 필요 요소
Flexibility (유연성)
: 가감을 통해 다른 시스템에 사용되거나 다른 시스템을 사용할 수 있어야 한다.
Low Cost and High Performance (저비용 고성능)
: 수백만 페이지를 다운로드 한 뒤의 성능에 효율적인 디스크 접근이 필요하다
Robustess (견고성)
: 많은 어플리케이션에서 받은 페이지 중 이상한 HTML을 견뎌야 함, 크롤링은 오래걸리므로 충돌과네트워크 중단을 버텨야 함.
Etiquette and Speed Control (에티켓과 속도조절)
: 로봇룰을 따라야 한다, 하나의 서버에 많은 유입이 발생하지 않도록 각 사이트에 일정시간을
두고연결한다. 전체 다운로드 비율을 시간에 따라 나눠줘야 한다.(이
프로젝트는 캠퍼스에서 진행되기때문에 학생들의 사용에 영향을 끼치지 않기 위해서)
Manageability and Reconfigurability (관리성과 재구성 가능성)
: 크롤러의 속도, 통계 등과 관련된 모니터링이 필요하고 속도, 요소 가감, 시스템 차단 등의 매니저가필요
크롤러의 구조
크게 두가지 구성요소로 나뉘게 된다
1. 크롤링 어플리케이션
주어진 현 상태와 이전에 크롤링 된 페이지를 통해 무슨 페이지를 요청할 지 결정을 하고 요청을 하는 역할
2. 크롤링 시스템
요청된 페이지를 다운받고 제공해 주는 역할
각각의 크롤러의 시나리오가 모두 다르지만 크롤러는 기본적으로 중복제거, 페이지의 적절성 검사, 로봇 차단 등의 공통적인 기능들이 있으므로 시스템과 전략을 디자인 할 때 유연하게 해야 한다.
시스템 아키텍쳐
크롤러는 크게 크롤링 시스템과 크롤링 어플리케이션으로 나뉜다. 그리고 크롤링 시스템은 크롤링 매니저, 다운로더, DNS리졸버의 요소들로 분화된다.
1.Crawl Manager
크롤링 시스템의 중요 요소
어플리케이션으로 부터 URL 요청과 NFS를
통해 접근할 수 있는 URL 정보를 가진 파일에 대한 포인터를 받는다.
높은 성능을 유지하기 위해 대략적으로 어플리케이션이 지정한 순서대로 페이지를 다운 받으면서 특정웹에 너무 부하가 가지 않도록 요청을
재정렬 해주는 목적을 가진다.
URL들을 로드
-> 캐시되지 않은 주소는 DNS resolver에
IP 주소를 요청
-> 이와 분리되어 우선순위에 따라 로봇 파일을 요청
의 과정을 걸쳐 제외된 URL을 빼고 최종적으로 남은
URL을 일괄적으로 다운로더에게 전송하고 같은 서버는 일정 간격으로 요청되는지를 학인하는 역할을 한다.
또한 매니저는 모니터링을 통해 다운로더와 DNS Resolver의 속도를 맞추고 제한한다. 그리고 데이터 구조의 주기적인 스냅샷을 수행하고 충돌 후 제한된 수의 페이지를 다시 크롤링해야 한다.
2. Downloaders
다운로더는 높은 퍼포먼스의 비동기식 HTTP 클라이언트다.
파이썬으로 구현 된 다운로더는
다른 최대 1000개의 연결을 열고 도착하는 데이터에 대해 연결을 폴링(충돌회피, 동기화 목적으로 다른 장치 상태 검사)
-> 웹에서 파일을 가져 옴
-> NFS를 통해 액세스 할 수 있는 파일로 데이터를 마샬링(한 객체의 메모리에서
표현방식을 저장 또는 전송에 적합한 다른 데이터 형식으로 변환하는 과정)
의 과정을 책임진다. 이 과정에서 매니저는 현재 동시 연결된 수를 조절하여 다운로더의 속도만
조절한다.
3. DNS Resolver
DNS의 클라이언트로 호스트의 정보를 구하는 프로그랭믜 요청을 서버에 대한 질의 형태로 번역해
주고, 그 응답을 프로그램에 만들어 변형시켜주는 역할을 한다.
기존의 크롤러 디자인들은 동기화 특성 때문에 심각한 보틀넥이 있었지만 해당 논문에서는 GNU
adns 비동기 DNS 클라이언트 라이브러리로 하나의 컴퓨터에 함께 배치된 DNS 서버에 접근하도록 하여 해결 하였다. 그러나 DNS조회는 대량의 트레픽 프레임을 만들기 때문에 제한된 라우터 용량으로는 크롤링 속도가 제한되었다.
4. Crawling Application
크롤링 어플리케이션은 주어진 URL 시드에서 부터 너비우선 크롤링을 하여 각 페이지에서 파싱된 URL의 이전 발생 여부가 없으면 배치 관리자에게 넘긴다. 다운로드 된 파일은 압축하여 저장소 관리자로 전달된다. 두 가지 유의할 점으로는 첫 번째로 각 페이지의 다수의 하이퍼링크 때문에 중복을 제거한 후에 발생하는 URL 크기는 빠르게 증가하여 메인 메모리 크기를 초과할 수 있다. 두 번째로 이 과정에서 한 페이지에서 파싱되어 관리자에게 전송된 페이지는 오래 후에 다운로드 되므로 어플리케이션이 새로운 요청을 동적 데이터 구조에 즉시 삽입 할 이유가 없다.
5. Scaling the System
해당 논문에서의 주요 목표 중 하나는 적은 비용의 워크 스테이션을 추가하여 추가 구성요소를 확장할 수 있는 시스템을 설계하는 것이다. 하나의 매니저에게 가장 적절한 갯수인 8개의 다운로더와 2~3개의 DNS Resolver의 수를 넘어가게 되면 두 번째 크롤 관리자를 만들고 어플리케이션은 두 가지 관리자 간의 요청을 분리해야 한다.
인터넷 아카이브 크롤러와 같이 너비우선 크롤러를 4개의 구성요소로 분할하는 것은 간단하다. URL을 해시함수를 사용하여 4가지 하위 집합으로 분리한다. 각 하위 구성요소는 하나의 하위 집합을 처리하고 요청하는 역할을 한다. 매니저는 각자의 어플리케이션에서 다운받은 페이지들을 분리된 디렉토리에 저장하였는지 확인한다. 파싱하는 동안 구성요소가 다른 하위 집합에 속한 URL은 해시값대로 구성요소가 옮겨간다. 크롤링 관리자는 완전히 다르게 표시된 두 개의 어플리케이션 구성요소에서 사용할 수 있다.
특정한 서버에 대한 과도한 부하를 각 호스트가 최대 하나의 하위 집합에 매핑되도록 하여 피할 수 있다. 일부 집중형 크롤러는 병렬화되기 어렵지만 피할 수 없고 디자인에 국한될 수 없다. 상당 양의 데이터가 포함된 유일한 통신은 다운로드 한 파일의 전송이다. 따라서
다운로드된 파일들이 원격 위치에서 끝날 수 있다는 사실을 감안할 떄 광역분산 환경에서도 시스템을 사용할 수 있다. )
네트워크 성능
다운로더가 NFS를 통해 크롤링 어플리케이션에 페이지들을 저장한 후 어플리케이션이 파일을 읽어 파싱을 하고 스토리지 매니저가 NFS를 통해 영구적인 레파지토리에 복사한다. 이러한 데이터의 이동 과정들이 네트워크를 통해 이루어지게 되며 병목현상이 일어날 수 있게 되자 네트워크의 성능이 중요해졌다. 이를 위한 솔루션으로 병목 현상이 발생하자 마자 어플리케이션을 여러 구성요소로 분할하여 시스템을 확장한다. 다른 방법으로는 기가 비트 이터넷으로 업데이트 하고 rcp를 사용하도록 전환하면 병목현상을 크게 제거할 수 있다.
URL Handling
하이퍼 링크는 구문 분석만 하고 색인을 하지 않기 때문에 속도가 훨씬 느려진다. 이를 해결하기
위하여 하이퍼 링크들을 연관된 링크들로 정규화를 한다. 정규화된 하이퍼 링크들은 지금까지 다운로드 되고
접해본 모든 URL에 대하여 검사한다. 이때 URL은 빠르게 증가하며 메모리 크기를 초과하게 된다.
몇가지 해결책 중에 Bloom Filter(원소가 집합에 속하는지 여부만 확인하는 자료구조)를 사용하는 방법이 있는데 어떠한 페이지는 다운로드되지 않는 문제가 있고 무손실 압축으로 URL의 크기를 줄이는 방법은 크롤링에 문제가 생긴다. 다른 방법으로
어플리케이션을 분할하여 여러 기계에 데이터를 저장해도 주 메모리에서 병목 현상이 생긴다.
이보다 확장성있는 솔루션으로 디스크 상주 구조를 사용하는 방법이 있다. URL들을 메인
메모리에 Red-Black 트리 구조로 저장을 하고 새로 URL을
발견하였을 때 메인 메모리에 버퍼링하고 메모리 상주데이터를 디스크 상주데이터로 간단한 스캔 및 복사 작업을 통해 주기적으로 합병한다. 합병을 하는 동안 모든 조회와 삽입을 수행한다. 병합은 새로운 스레드를
생성하여 수행하므로 어플리케이션은 계속해서 새로운 파일을 파싱할 수 있다. 이 방법을 통해서 디스크
랜덤 접근을 완전히 피하거나 적어도 URL 접근으로 선형적인 확장을 하는 것을 목표로 한다.
Domain-Based Throttling (도메인 기반 조절)
일부 도메인들은 웹 서버 수가 많지만 네트워크 속도가 느려서 크롤러에 영향을 받을 수 있고 대규모 조직의 많은 서버에 단시간에 많은 접촉이 있으면 경보가 울리기도 한다. 마지막으로 크롤러는 IP 주소가 아닌 호스트 이름에 기반한 접근에 타임아웃이 발생하고 같은 시스템에 웹 서버들이 배치되어 있는지를 감지하지 못한다. 이러한 문제의 해결책으로 크롤 어플리케이션에서 도메인 기반 제한을 해결하기로 하였다. URL을 랜덤한 순서로 섞이 같은 도메인의 URL들이 균등하게 분산되도록 한다.
Crawl Manager Data Structures
크롤링 매니저는 N초룰과 로봇룰을 지키면서 다운로더에 요청들을 스케줄링하기 위해 여러 데이터 구조를
유지한다.
요청 파일들을 리스트에 포함하기 위한 FIFO 요청 큐와 호스트 이름으로 구성되고 여러
호스트 데이터 구조로 구성된 URL을 포함하는 FIFO 호스트
큐가 여러개 있다.
호스트 구조로는
1. 현재 매니저에 있는 각 호스트들의 목록과 호스트 큐에 대한 포인터를 가진 호스트
dictionary
2. 다운로드 준비가 되어 있는 포인터를 가진 우선순위 큐
3. 최근에 액세스되어 다시 접촉되기 위해 30초를 기다리는 호스트들에 대한 포인터가 있는
우선순위 큐
이러한 세가지 구조가 있다.
매니저는 요청 번호가 있는 URL을 전송받으면서 목표는 요청간의 간격을 관찰하고 고성능을
달성하면서 많이 보관하는 것이다. 준비 큐의 호스트 포인터는 해당 호스트 큐의 첫번째 URL의 요청 번호를 키로 가져 최소 키값 추출로 다운로드 준비가 완료된 전체
URL 중에 가장 작은 요청 번호를 가진 URL을 선택하여 다운로더에 보낸다. 페이지가 다운로드 된 후에 호스트에 대한 포인터는 대기 큐에 삽입되고 키 값은 호스트에 다시 액세스 할 수
있는 시간과 같다. 우선 순위 큐의 키 값의 최소 인자의 대기시간을 확인하고 대기시간이 지났을 때 추출하여
호스트 대기 큐로 다시 전송한다.
새 호스트에 직면하면 우리는 먼저 호스트 구조를 생성하고 호스트 dictionary에 넣는다. DNS 분석과 로봇 배제가 끝나면 호스트에 대한 포인터를 대기 큐에 삽입한다.
모든 URL들이 큐에 다운로드 되었을 때 호스트는 구조에서 삭제 된다. 그러나 로봇 파일의 특정 정보는 다른 URL이 들어왔을 때 재인증을
할 필요가 없도록 유지된다. 마지막으로 만약 호스트가 응답하지 않으면 호스트를 대기 큐에 잠시 넣고
두 번째 시도에도 대기 상태이면 더 오래 기다린다. 어플리케이션은 특정 호스트의 시간 초과를 결정하여
서버의 중요도에 따라 더 빨리 혹은 더 느리게 크롤링하도록 결정할 수 있다.
Scheduling Policy and Manager Performance
URL을 바로 DB에 계속 삽입을 하면 빠르게 메모리
사이즈를 초과하게 되므로 크롤링 된 페이지수와 타임아웃 간격, 대기 큐의 상태 등을 고려하여 삽입을
해야 한다. I/O 성능에 대하여도 고민을 해야 한다. 다운로드
되길 기다리는 URL들과 호스트의 수와 계속 자라는 큐로 인해 메인 메모리가 부족해지게 된다. 그러므로 가장 많은 액티브 데이터 페이지를 저장하기 충분한 메인 메모리를 가지고 있다면 합리적인 캐싱 정책이
잘 작동 될 것으로 기대 된다.
여러 요청이 들어오는 경우에는 같은 호스트의 페이지에 두개의 요청이 들어오면 어플리케이션에서 요청된 순서대로 다운로드 될 것이다. 다른 호스트의 페이지에 대한 두 요청은 하나의 호스트 대기열이 제한 시간 규칙 또는 호스트가 다운되거나 요청이
없거나 로봇룰, DNS 확인 중 지연 과 같은 과정이 일어나지 않는 한 발급된 순서로 다운로드 된다.
결과와 경험
- 실험을 하는 환경이 학교여서 학교 외부의 공격 등으로 인해 원활하게 진행이 되지 않았다. 그리고 다른 사용자에게 미치는 영향을 최소화 하기 위해 크롤러의 속도를 제어해야 하는 한계가 있었다. 속도를 조절하기 위해서는 크롤링 매니저에게 연결 되는 다운로더의 수를 변경하기도 하였다. 상황에 따라 변경이 어렵기 때문에 각 속도 설정에 대한 연결 수에 대한 절대적인 상한으로 연결 수를 수정하는
솔루션으로 끝맺었다.
- 실험에 사용 된 하드웨어도 영향을 많이 끼쳤다. 하드웨어의 양에 따라서 CPU, 메모리, 디스크의 배치에 대한 이해가 필요하다. 다운로더는 CPU의 대부분을 차지하지만 메모리는 거의 차지하지 않는다. 매니저는 몇 명의 다운로더가 연결되어 있는지에 따라 CPU 사용
시간이 거의 필요하지 않으며 DB용으로 적당한 양의 버퍼 공간이 필요하다. 어플리케이션은 CPU와 메모리를 모두 필요로 하므로 다운로더와 함께
배치하면 안된다.
논문을 읽으면서
* 스스로에게 칭찬할만한 점
느리더라도 읽는 부분을 이해하려고 노력하며 몇번이고 다시 읽은 점
보면서 몰랐던 주변 지식들(NFS)등도 같이 찾아보며 공부한 점
* 부족했던 점
무언가를 할 때 그것에 대한 목적이 뚜렷할 때 더 효율이 높아지는데 중요한 부분이 무엇일지에 대한 생각없이 읽은 점
영어 해석 능력...😂
속도!
* 기타 소감
학습에 있어서 why에 대한 고민의 중요성을 한번 더 깨달았다
지금 모르는 것에 다급해하지 말고 발표 끝나고 말씀 해 주셨듯이 부족한 부분은 아직 생소해서 그런 것이라는 생각을 가지고 차분하게 꾸준히 노력하면 좋겠다.
논문을 정리하면서
* 스스로에게 칭찬할만한 점
읽은 대로 정리했을 때 정리한 글이 너무 긴 줄글이어서 줄이기 위한 노력들을 한 것
* 부족했던 점
정리를 했음에도 불구하고 문장이 너무 장황한 줄글이었음
나만 이해할 것 같이 정리를 했음
* 기타 소감
논문을 정리하는 과정에서 단락단위로 읽고 정리하는 방식으로 진행을 했는데 일단 쭉 읽어보고 다시 읽으면서 머릿속에 정리가 되면 글로 정리하는게 좋을 것 같다
아직은.... 감이 안잡히지만 정리의 방식을 바꿔야 할 것 같다 (키워드 중심의 트리식 정리 후에 문장으로 만들기 처럼...) -> 충분히 고민해 보아야 할 부분
발표하면서
* 스스로에게 칭찬할만한 점
스스로는 이해를 하고 발표를 했다는 점 (과연...?)
* 부족했던 점
발표의 중요한 부분은 상대방이 이해할 수 있도록 준비를 해야 한다는 점을 놓친 것
혼자서 볼 때는 그냥 슥 읽어서 놓친 오타, 글의 구조(? 구성?)들이 있었음. 혼자서도 입밖으로 읽으면서 준비하는게 중요한데 이번에도 안한것~~~
* 기타 소감
글만으로는 상대방을 이해시키기가 어렵다. 특히 나처럼 줄글은!
그림, 표, 등등... 을 같이 사용해 주면 다음번은 더 나아지지 않을까!