Chapter 9. 웹크롤러 설계

[minkukjo]

느낀 점

• 웹 크롤러 설계해보기!
• QPS는 그냥 일단 2배로 잡고 보는 것 같다 ㅋㅋ
• 10억 페이지 x 500k = 500TB 여전히 산수가 약해서 계산이 어렵다.
• 거미 덫은 딱히 걸러낼 알고리즘이 없다는 것도 신기했다. 수동으로 해야한다니.. ㅋㅋ
• 생각보다 간단해 보였던 웹크롤러 설계지만, 생각보다 고려할 것도 많고 복잡함에 놀랐다.
• 한 편으로는 구글과 같은 검색 엔진이 어떻게 웹상에 흩어져있는 무분별한 문서들을 검색 엔진에 적용시킬 수 있는지 알 수 있게 되는 귀한 시간이었다.

궁금한 점

• 시작 URL을 지정한다는 말이 잘 이해가 안간다. www.naver.com, www.google.com과 같은 주소를 시작 URL로 보고, 거기 안에 있는 www.naver.com/booking, www.google.com/index 등과 같은 서브 URL로 탐색을 한다는 의미일까? (아시는 분 계시면 알려주세용.. )

• DFS와 BFS를 고민하는 부분도 잘 이해가 안갔다. DFS는 콜스택을, BFS는 힙을 사용하는데.... 아? 스택보단 힙 영역을 쓰는 BFS가 조금 더 낫다고 판단한건가? 흠...

• 페이지의 우선순위를 결정하는 기준이 궁금하다. 논문을 읽어야하나? 쓰읍... ㅋㅋㅋ 어떤 기준으로 애플이라는 키워드가 들어간 페이지와 애플 페이지를 구분할 수 있을까 아시는 분 계시면 알려주십쇼..

[LOG-INFO]

끄적끄적

• 웹크롤러는 여러 목적을 가지고 있다
  • 검색 엔진 인덱싱
  • 웹 아카이빙
  • 웹 마이닝 (예전에 영화 평점이나 맛집 등을 스크래핑한 적 있는데 이런걸 멀하는 듯)
  • 웹 모니터링
• 웹크롤러가 만족시켜야할 특정
  • 규모 확장성: 이건 어느 설계나 신경써야할 듯
  • 안정성: 이것도 뭐... 여기선 장애가 있거나 악성코드가 있는 URL 등을 나타내긴 함
  • 근데 악성코드가 있는 URL은 어떻게 잡아내지?
  • 예절: 너무 많은 요청을 보내면 안됨 (다이닝코드, 네이버 영화, 구글 등은 n초당 m페이지 조회 제한이 있었음)
  • 확장성: 새로운 타입의 콘텐츠?
• QPS/TPS와 저장용량은 일단 구하고 들어가는군
• 여러 모듈
  • 시작 URL 집합
  • 미수집 URL 집합
  • HTML 다운로더
  • 스케일 아웃을 해서 병렬처리를 하자
  • 타임아웃을 두자
  • 도메인 이름 변환기
  • 이건 왜 있는거지? 그냥 DNS가 하면 되는거 아닌가?
    • 뒤에 나오네.. DNS 요청 처리 시간 때문에 캐싱해두려고 하는 듯
    • 근데 DNS가 10ms~200ms나 걸리나..?
  • 컨텐츠 파서
  • 크롤링서버와 독립적인 컴포넌트로 구성하는 것 좋은 듯
  • 스케일 아웃을 해서 병렬처리를 하자
  • 중복 컨텐츠 체크
  • 해시값, 체크섬 비교는 어떻게 하는가?
  • 만약 페이지 내에 현재 시간이나 매번 달라지는 랜덤값 같은게 있으면 매번 다른 해시값이 나올 순 있겠다
    • 크롤링 로봇 극한 직업...
  • 컨텐츠 저장소
  • URL 추출기
  • 상대경로 에다가 host 붙여줌
  • URL 필터
  • 접속 오류, 특정 컨텐츠타입, 제외 목록 필터링
  • 이미 방문한 URL 체크
  • 블룸 필터? 전에도 나왔는데 찾아보자
  • URL 저장소
• BFS 사용하는 것 동의
  • ~비슷하게, 나는 매번 공부할 때 DFS로 공부하다가 시간 엄청 잡아먹고 결국 그 날 계획한거 다 못 끝냄...~
  • ex) 오늘은 Spring Webflux를 공부해보자! 한 5시간이면 끝나겠다!
    • reactor는 뭐지? reactive streams는 뭐지? 다른 reactive streams를 따르는 라이브러리는 뭐가 있지? RxJava 1,2,3 차이가 뭐지? ..... (이것만 2~3시간 걸림)
    • Netty는 뭐지? reactor랑 Netty랑 무슨 관계지? Netty는 어케 만들어져있지? 누가 만들었지? Netty 말고 다른건 뭐가 있지? Undertow란게 있네! 이건 뭐지? ........ (이것만 2~3시간 걸림)
    • 결국 10시간 공부해도 Webflux 문서 다 못 봄
• 거미덫...
  • 크롤링 로봇 극한 직업...
  • URL 길이 제한?
• React 같은 Single Page App은 어케 하려나....

[MinJunKweon]

Chapter 9. 웹 크롤러 설계

느낀점

• DNS Resolver를 왜 따로 컴포넌트로 떼나 했는데 웹 크롤링처럼 대규모로 사용하는 경우 병목 지점이 될 수 있겠구나 이해함
• 접속하는 위치(국가)에 따라 보여지는 페이지가 다른 경우도 존재함
• 일부는 UA가 일반적이지 않은 경우 페이지를 아예 reject하는 경우가 종종 있음 이런 경우 UA를 속여서 처리하면 문제가 될지?

정리

• 웹사이트들을 순회하며 콘텐츠를 저장, 검열하는 툴
• 웹 크롤러의 목적
  • 검색엔진 인덱싱 : 웹페이지를 모아 검색 엔진을 위한 인덱스를 만듦
  • 웹 아카이빙 : 나중에 사용할 목적으로 장기보관하기 위해 웹에서 정보를 모으는 절차
  • 웹 마이닝 : 웹 사이트의 정보들을 긁어서 모으는 목적
  • 웹 모니터링 : 저작권이나 상표권이 침해되는 사례를 모니터링하는 것이 목적

간단 설계

1. URL 집합이 입력으로 주어지면, 해당 URL들의 웹 페이지를 다운로드
2. 다운로드된 웹 페이지 콘텐츠를 저장하고, 포함된 URL들을 추출
3. 추출된 URL을 다운로드 대상 URL 목록에 추가 후 1번부터 다시 반복

요구사항 구체화

• 매달 10억 개의 웹 페이지 수집
  • 10억 / 30일 / 24시간 / 30초 = 대략 초당 400페이지 처리
  • 최대 QPS = 2 * 400 = 초당 800 페이지
• 수집된 페이지는 5년간 보관 필요
  • 웹페이지 크기는 평균 500KB
  • 10억 * 500KB = 월별 500TB 저장공간 필요
  • 5년 500 TB = 60개월 500 TB = 총 30PB 저장공간 필요
• 중복 콘텐츠 무시

설계 구조

• 미수집 URL 저장소(URL Frontier) : 다운로드 해야할 URL 저장소
• HTML 다운로더 : URL에 해당하는 웹페이지 다운로드를 하는 컴포넌트
• 도메인 이름 변환기(DNS Resolver) : URL에 대응하는 IP 주소를 알아내는 컴포넌트
• 콘텐츠 파서 : 웹페이지 내용 파싱과 검증
  • 중복 컨텐츠 확인 : 웹페이지 체크섬 확인
• 콘텐츠 저장소 : 웹 페이지 내용을 저장해두기 위한 컴포넌트
• URL 추출기 : 웹 페이지 내용에 포함된 URL들을 추출
• URL 필터 : 특정 콘텐츠 타입이나 확장라를 갖는 URL, 접속 오류 URL, 접근 제외 URL 등을 걸러내는 컴포넌트
  • 방문 여부 확인 : bloom filter 알고리즘 혹은 해시 테이블을 사용해서 구분
• URL 저장소 : 이미 방문한 URL을 보관하는 저장소

상세 설계

• 상세설계 고려사항
  • DFS(Depth-First Search) vs BFS(Breath-First Search)
  • 미수집 URL 저장소
  • HTML 다운로더
  • 안정성 확보 전략
  • 확장성 확보 전략
  • 문제 있는 콘텐츠 감지 및 회피 전략

DFS vs BFS

• DFS를 쓰게되면 그래프의 깊이가 얼마나 될지 가늠하기가 어려움
• 한 페이지에서 나오는 링크의 대부분이 같은 서버의 링크를 가지는 경우가 대부분임
  • 그러므로 DFS를 사용하면 단시간동안 같은 서버에 요청을 여러번 전송하기 때문에 부하 발생요인이 될 수 있음 (DoS 공격)
  • 같은 서버에는 한번에 여러건의 요청을 보내는 일은 줄여야함 ⇒ BFS 전략이 효과적
• 하지만 BFS 알고리즘이 만능은 아님
  • URL 간에 우선순위를 두지 않기 때문에 중요한 웹 페이지를 먼저 크롤링하게 끔 하기가 어려움

미수집 URL 저장소

• 미수집된 URL들 간에 같은 서버에 대해 요청을 여러건 보내지 않도록하기 위해 보통 Queue를 사용함
• 호스트명(도메인)별로 Queue를 따로 두어 워커 스레드가 처리할 URL을 선별해주는 큐 선택기(Queue Selector)를 통해 미수집 URL을 선별할 수 있도록 함

• 또한, 웹 페이지 간에 우선순위가 존재할 수 있음
  • 애플 홈페이지 vs 국내 모 대학교 공지사항 게시판의 5년 전 글
• 그렇기 때문에 웹 페이지의 우선순위를 계산하여 우선순위에 따른 URL들을 별도의 큐들로 관리함
• 이런 우선순위에 대한 큐들도 큐 선택기(Queue Selector)가 우선순위에 따른 URL을 골라서 워커 스레드로 할당해줌
• 호스트명 큐 보다 앞단에 두어 우선순위를 먼저 계산하도록 설계

• 또한, 웹페이지가 자주 변경되거나 변경에 민감한 페이지들(변경이 일어나면 바로바로 반영되어야하는 페이지들)도 신선도(freshness)를 유지하기 위해 자주 크롤링하는 튜닝을 할 수 있다.
  • 웹 페이지의 변경 이력(update history) 활용
  • 우선순위를 활영해 중요한 페이지는 좀 더 자주 재수집

미수집 URL 저장소를 위한 지속성 저장장치

• 처리해야할 URL들을 메모리에 저장하는 것보다 Disk에 저장해 두는 것이 안정성이나 규모를 확장할 때 편리하다.
• 하지만 Disk에 저장해두고 사용하는 것은 성능이 매우 느리기 때문에 메모리 버퍼를 사용하고 버퍼를 주기적으로 Disk에 저장하는 절충안을 사용한다.

HTML 다운로더

• Robots.txt : 로봇 제외 프로토콜의 표준적 방법
• 이 파일에는 크롤러가 수집해도 되는 페이지 목록들이 들어있음.
• 웹사이트가 긁어 가기 전에 크롤러는 해당 파일에 나열된 규칙을 확인해야함

성능 최적화

1. 분산 크롤링
   • 크롤링 서버를 여러대 두어 동시에 여러대로 크롤링을 할 수 있도록 분산 시킴
2. 도메인 이름 변환(DNS Resolve) 결과 캐시
   • 도메인 이름을 변환하는 데에는 꽤 오랜 시간이 소요될 수 있으므로 이를 미리 IP로 변환하는 작업을 동시에 진행한다
3. 지역성
   • 크롤링 대상 URL의 서버와 지역적으로 가까운 서버들에 배정시켜서 속도를 빠르게하는 전략을 사용함
4. 짧은 타임아웃
   • 접속이 안되는 서버 혹은 응답시간이 너무 느린 경우에는 타임아웃을 짧게 주어서 빠르게 실패시키고 다른 URL을 처리하게끔 변경한다

확장성

• 컴포넌트 중에 확장이 필요한 부분을 골라 확장하기 쉽도록 설계한다.
• 만약 웹 크롤링과 동시에 웹 모니터링을 함께 진행해야된다고 하면 URL을 추출하는 부분에 웹 모니터링을 진행하는 컴포넌트를 끼워넣으면 가능하다.
• 이렇게 확장가능한 모듈화를 하도록 설계한다.

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

1. 중복 콘텐츠
   • 해시 체크섬을 사용해서 중복 컨텐츠를 필터링
2. 거미 덫 (Spider Trap)
   • 악의적으로 무한루프에 빠뜨리도록 설계한 웹 페이지가 존재할 수 있음
   • ex. 영원히 끝나지 않는 디렉토리 구조를 포함하는 링크
     • 최대 URL 길이를 제한하면 회피 가능
   • 하지만 이외에도 다양한 웹페이지가 많기 때문에 수작업으로 튜닝하는 것이 좋음
   • 웹 페이지 태그가 깨지는 등 정말 다양한 사례가 존재할 수 있음
3. 데이터 노이즈
   • 광고, 스크립트 코드, 스팸 URL, 악성 코드 등 크롤링에 의미 없는 데이터는 가능한 제외시켜야함

추가적으로 고려할만한 사항

• URL이 동적으로 생성되는 경우가 존재할 수 있음 ⇒ 서버 측에서 렌더링해서 URL을 추출하는 방법 존재
• 원치 않는 페이지 필터링 : 스팸성 페이지나 조악한 페이지들을 걸러내도록 필터 추가
• 데이터베이스 다중화 및 샤딩
• 수평적 규모 확장성 : 크롤러를 무상태(stateless)로 만드는 방법
• 가용성, 일관성, 안정성
• 데이터 분석 솔루션

[2rohyun]

느낀점

---

• 크롤러에 대해 잘 알지 못했는데, 크롤러가 어디에서 사용되며, 전체적으로 어떤 아키텍처를 가지는지, 그리고 구현하며 고려해야하는 것들이 무엇이 있는지 알게된 시간이었다. ( 다음에 혹시 크롤러를 구현할 일이 생기면 꼭 다시 봐야지 .. )
• 작업 흐름을 다이어그램으로 보고서, 꽤 간단하게 구현할 수 있겠네? 라는 생각이 들었지만.. 상세 설계 부분을 읽으면서 .. 고려해야할 수 많은 문제들이 있구나.. 어렵다! 라는 생각이 들었다. 역시 모든 것은 디테일로 들어가면 어려워지고, 또 가장 중요하다는 이치를 체감했다.

끄적끄적

---

• 크롤링 활용 분야
  • 검색 엔진 인덱싱
  • 웹 아카이빙
  • 웹 마이닝
  • 웹 모니터링
• 크롤러가 만족시켜야할 속성
  • 규모 확장성 : parallelism 활용
  • 안정성 : 잘못 작성된 HTML, 아무 반응 없는 서버, 장애, 악성 코드가 붙어 있는 링크 등 비정상적 입력이나 환경에 잘 대응할 수 있어야 한다.
  • 예절 : 크롤러는 수집 대상 웹 사이트에 짧은 시간 동안 너무 많은 요청을 보내서는 안된다.
  • 확장성 : 새로운 형태의 컨텐츠를 지원하기 쉬워야 한다.
• 개략적 규모 추정
  • 매달 10억 개의 웹 페이지 다운로드
  • QPS = 10억 = 대략 400페이지/초
  • Max QPS = 800
  • 웹 페이지 크기 평균은 500k
  • 10억 페이지 x 500k = 500TB/월
  • 5년간 보관한다고 가정하면 30PB 의 저장용량 필요
• 작업 흐름
  1. 시작 URL들을 미수집 URL 저장소에 저장
  2. HTML 다운로더는 미수집 URL 저장소에서 URL 목록을 가져옴.
  3. HTML 다운로더는 도메인 이름 변환기를 사용하여 URL의 IP 주소를 알아내고, 해당 IP 주소로 접속하여 웹 페이지를 다운 받음.
  4. 컨텐츠 파서는 다운된 HTML 페이지를 파싱하여 올바른 형식을 갖춘 페이지인지 검증
  5. 컨텐츠 파싱과 검증이 긑나면 중복 컨텐츠 확인
  6. 페이지가 이미 컨텐츠 저장소에 있다면 버리고, 아니라면 저장소에 저장한 뒤, URL 추출기로 전달
  7. URL 추출기는 해당 HTML 페이지에서 링크를 뽑음.
  8. 골라낸 링크를 URL 필터로 전달
  9. 필터링이 끝나고 남은 URL만 중복 URL 판별 단계로 전달
  10. 이미 저장소에 있는 URL은 버리고, 저장소에 없는 URL은 URL 저장소에 저장하고, 미수집 URL 저장소에 전달