kaonmir
시리즈
SAA
DOP
System Design Interview
Linux
ETC
Share
Sign In
Home
Kaonmir (손성훈)
Copy & Translate
시리즈
SAA
후기
시험 소개 & 꿀팁
Terminology
Region & Availability Zone
Budget
IAM
EC2 - Fundamentals
EC2 - SAA Level
EC2 Storage
ELB & ASG
RDS / Aurora / ElastiCache
S3
CloudFront & Global Accelerator
Route 53
Storage Extras
Decoupling
Container
Serverless
Database
Monitoring, Troubleshooting & Audit
IAM Advanced
Security & Encryption
VPC
Disaster Recovery & Migrations
Ohter Services
기술 백서 총 모음
기술 백서(White paper)
DOP
CodeCommit, CodeBuild, CodeDeploy
CodePipeline, CodeStar, Jenkins
CloudFormation - Fundamentals
CloudFormation - DOP Level
Elastic Beanstalk
Lambda & Step Function & API Gateway
ECS & ECR & OpsWorks
Kinesis
CloudWatch
CloudTrail & X-Ray & ElasticSearch & Tagging
SSM & Config & Service Catalog & Inspector
Other Services
Auto Scaling Group (ASG)
DynamoDB & S3
Multi AZ & Multi Region & Multi Account
AWS Organizations & On-Premise Strategy
Disaster Recovery (DR)
서비스별 기본 배포 전략 비교
CodeDeploy appspec hook
System Design Interview
사용자 수에 따른 규모 확장성
개략적인 규모 추정
시스템 설계 면접 공략법
처리율 제한 장치
안정 해시
키-값 저장소
분산 시스템을 위한 유일 ID 생성기
URL 단축기
웹 크롤러
알림 시스템
뉴스 피드 시스템
채팅 시스템
검색어 자동완성 시스템
유튜브
구글 드라이브
Linux
ETC
AI를 더 잘 쓰기 위한 IT 용어
웹 크롤러
목차
웹 크롤러
웹에 새로 올라오거나 갱신된 콘텐츠를 찾아내는 기술
활용
검색 엔진 인덱싱 : 웹 페이지를 모아 로컬 인덱스를 만든다. (Googlebot)
웹 아카이빙 : 장기보관을 목적으로 정보를 모음
웹 마이닝 : 유용한 지식을 도출
웹 모니터링 : 저작권, 상표권 침해 사례 모니터링
알고리즘
1.
URL 집합의 모든 웹 페이지를 다운로드한다.
2.
다운받은 웹 페이지에서 URL들을 추출한다.
3.
추출한 URL로 1부터 반복한다.
속성
규모 확장성
: 여러 대의 크롤러로 병렬 수집한다.
안정성(robustness)
: 비정상적 입력이나 환경에 대응한다.
예절(politeness)
: 짧은 시간에 너무 많은 요청을 보내면 안된다.
확장
: 새로운 형태의 콘텐츠(음악, 영상 등)를 쉽게 지원해야 한다.
관리과 재구성
: 여러 지표와 설정을 위한 인터페이스를 정해야 한다.
설계
개력적 설계안
seed URLs
: 크롤링의 시작 주소 지정
루트 도메인(*.naver.com, *.google.com)을 쓴다.
지역, 주제별로 다른 seed를 사용한다.
URL Frontier
: 아직 fetch 되지 않은
URL FIFO queue
HTML Fetcher
: URL Frontier에서 주소를 가져와 웹 페이지를 다운로드한다.
DNS Resolver
: URL을 IP로 바꾼다.
HTML Parser
: parsing과 validation을 수행, 불필요한 웹 페이지를 버린다.
Duplicate Detection
: 웹 페이지의 해시값을 비교해서 중복을 제거한다.
Data Storage & Caching
:
HTML 문서
를 저장한다.
URL Extractor
: 파싱한 HTML 페이지 중
URL을 추출
한다. 상대 경로는 절대 경로로 변환한다.
URL Filter
: 특정 확장자, 오류가 나는 URL, deny list에 있는 URL 등
규칙에 의해 배제
한다.
URL Lodaer/Detector
: 블룸 필터나 해시 테이블로
중복 URL을 제거
한다.
URL Storage
: 이미
방문한 URL
을 보관
상세 설계
DFS vs BFS
웹은 하이퍼링크로 연결된 방향이 있는 그래프이다.
크롤링은 이 그래프를 탐색하는 것이고, DFS 혹은 BFS 알고리즘을 사용한다.
웹 그래프의 깊이를 알 수 없으므로
DFS는 적합하지 않다
.
링크는 같은 서브 도메인을 가리키는 경향이 크기 때문에, BFS(너비 우선 탐색)를 사용하면 한 서버에 많은 부하를 줄 수 있다. (impolite)
그래서 페이지 순위, 트래픽 등을 지표로 BFS 큐의 우선순위를 조정한다.
URL Frontier
BFS 알고리즘의 큐를 구현한 컴포넌트이다. politeness와 freshness를 구별한다.
우선순위(Priority)
페이지 랭크, 트래픽 양, 갱신 빈도 등의 지표를 사용해 우선순위를 정한다.
Priority Router
: 우선순위별로 URL을 큐에 넣는다.
Priority Selector
: 높은 순위부터 데이터를 꺼내 넘긴다.
예의(politeness)
예의 바른 크롤러는 동일 웹 사이트에 대해서는 한 번에 한 페이지만 요청한다.
이를 위해 호스트 이름별로 다른 FIFO 큐를 만들고 이 큐들을 돌아가면서 사용한다.
Politeness Router
: 호스트별로 URL을 큐에 넣는다.
Politeness Selector
: 큐를 순회하면서 하나씩 URL을 꺼낸다.
Mapping Table
: 호스트 이름과 큐를 매핑한다.
신선도(Freshness)
이미 같은 페이지도 주기적으로 다시 다운로드한다.
웹 페이지 변경 이력, 우선순위를 고려하여 다운로드 주기를 결정한다.
저장장치
URL이 방대하기 때문에 일단 메모리 버퍼에 넣고 천천히 디스크에 저장하는 방식을 쓴다.
HTML Fetcher
Robots.txt
로봇 제외 프로토콜이라고도 불리며, 크롤러가 수집해도 되는 페이지 목록을 정한 파일이다.
성능 최적화
분산 크롤링
: Politeness Selector는 여러 서버로 URL을 배분한다.
DNS Resolver 캐싱
: DNS를 cron job을 통해 주기적으로 캐싱한다.
지역성
: 크롤링 서버를 웹 서버가 있는 지역에 둬서 latency를 줄인다.
짧은 타임아웃
: 오래 기다리지 말고 빨리빨리 다음 페이지로 넘어간다.
안정성
안정 해시
: 부하를 효율적으로 분산한다.
크롤링 상태 및 수집 데이터 저장
: 크롤링 서버에 장애가 발생할 경우 쉽게 복구할 수 있다.
예외 처리
데이터 검증
확장성
위 그림처럼 기능별로 컴포넌트를 분리해서 새로운 컴포넌트를 추가하고 변경하기 용이하도록 한다.
문제 있는 콘텐츠 감지 및 회피
중복 콘텐츠
: 해시나 체크섬으로 탐지
spider trap
: 무한히 깊은 URL에 빠지지 않도록 최대 길이를 제한하거나 deny list를 설정한다.
데이터 노이즈
: 광고, 스팸 URL 등을 제거한다.
추가 논의
Server-side Rendering(Dynamic Rendering)
: 요즘은 동적으로 웹사이트를 만들기 때문에 단순히 HTML만 다운로드하면 안되고, 렌더링을 한 다음 파싱해야 한다.
원치 않는 페이지 필터링
: 품질이 조악하거나 스팸인 사이트를 거른다.
데이터베이스 다중화 및 샤딩
: Data layer의 가용성(HA), 확장성, 안정성이 좋아진다.
수평 확장
: 서버를 stateless하게 만들어 수평 확장을 하여 대규모 작업을 수행한다.
가용성(HA), 확장성, 안정성
:
사용자 수에 따른 규모 확장성
참조
데이터 분석
: 데이터를 분석해 시스템을 세밀하게 조정한다.
출처
Designing Web Crawler: System Design Interview Question :
https://www.enjoyalgorithms.com/blog/web-crawler
Made with SlashPage