Chapter 9. Designing web crawler

[matteblack9]

Fingerprinting by random polynomials Center for Re-search in Computing Tech

Rabin Fingerprint의 핵심 원리:

1. 다항식 해시: Rabin fingerprint 해시 함수는 문자열을 하나의 다항식으로 간주하여 처리한다. 문자열의 각 문자는 다항식의 계수가 되며, 문자의 위치는 다항식의 지수(차수)가 된다.

2. 모듈로 연산: 해시 계산 과정에서 수가 매우 커질 수 있으므로, 보통 모듈로 연산을 사용하여 해시값의 크기를 제한. 모듈로는 일반적으로 큰 소수를 사용.

3. 롤링 해시: Rabin-Karp 알고리즘에서 사용되는 Rabin fingerprint 해시 함수는 롤링 해시의 형태를 취한다. 이는 문자열을 한 문자씩 이동하면서 해시값을 효율적으로 업데이트할 수 있게 해준다.

해시 함수 만드는 과정:

문자열을 숫자로 변환: 문자열의 각 문자를 ASCII 값 등의 숫자로 변환. 예를 들어, 'a'는 97, 'b'는 98 등으로 변환될 수 있다.

다항식 계산: 각 문자에 대응하는 숫자를 다항식의 계수로 사용하고, 문자의 위치를 지수로 사용하여 다항식을 계산. 예를 들어, 문자열 "abc"에 대해 다항식은 97x^0 + 98x^1 + 99*x^2와 같이 된다.

모듈로 연산 적용: 계산된 다항식에 대해 특정한 큰 소수를 모듈로 사용하여 나머지를 계산. 이렇게 하여 해시값의 크기를 관리할 수 있다.

롤링 해시 업데이트: 문자열을 한 문자씩 이동하면서 해시값을 업데이트. 예를 들어, "abc"에서 "bcd"로 이동할 때, 'a'에 대한 부분을 제거하고 'd'를 추가. 이 과정은 고정된 시간 복잡도를 가지므로 매우 효율적.

예시)

H("abc") = 97 * 256^0 + 98 * 256^1 + 99 * 256^2 (mod 101)
= 97 + 25088 + 6422528 (mod 101)
= 6471713 (mod 101)
= 72

H("abcde") = 97 * 256^0 + 98 * 256^1 + 99 * 256^2 + 100 * 256 ^3 + 101 * 256^4 (mod 101)
= 97 + 25088 + 6422528 (mod 101)
= 6471713 (mod 101)
= 57

해시 충돌 발생할 경우

추가 검증 단계: 해시 충돌이 발생했다고 의심되는 경우, 해당 데이터 블록을 추가적으로 검증하는 단계를 거친다. 이는 일반적으로 충돌이 발생한 블록들의 전체 내용을 직접 비교하는 방식으로 이루어짐. 이 방법은 매우 정확하지만, 충돌이 자주 발생하는 경우 비효율적일 수 있다.

매개변수 조정: Rabin fingerprint의 구현에서 해시 함수의 매개변수(예: 사용하는 소수의 크기)를 조정하여 충돌 확률을 줄이는 방법도 있다. 하지만, 이는 충돌 확률을 줄일 수는 있지만 완전히 제거하지는 못한다. 따라서, 항상 해시 충돌이 발생할 수 있다는 점을 고려하고, 이를 적절히 처리할 수 있는 방안을 마련해야 한다.

활용

Web Crawler 활용 LBFS(Low Bandwitdh Filesystem) : 품질이 좋지 않은, 파일 시스템의 동기화를 진행할 때 사용되기도 했다.

[gimmizz]

Tracking Web Spam with Hidden Style Similarity

http://airweb.cse.lehigh.edu/2006/urvoy.pdf

한 번 쭉 봤는데, document fingerprinting, minsampling 등등 생소한 개념이 많아서 페널티받고,,, 좀 더 준비해서 발표하겠습니다 😭

[Enoch-Kim]

Google Dynamic Rendering

https://developers.google.com/search/docs/crawling-indexing/javascript/dynamic-rendering?hl=en

몇몇 웹사이트는 JS로 페이지에 추가 컨텐츠를 만든다. (client-side rendering) -> 문제는 이런 경우 구글 검색에 노출되는데 한계가 있을 수 있음

동적 렌더링은 이렇게 검색엔진에 노출되지 못하는 JS 결과물을 가진 웹사이트에 적용할 수 있다. 동적 렌더링 서버는 JS 결과물을 수집할 수 없는 클롤링 봇을 탐지하고 서버에서 렌더링한 버전을 봇에게 전달한다. (일반 사용자들은 클라이언트에서 JS 렌더링을 진행한다.)

동적 렌더링은 추가 복잡도와 리소스 요구사항을 발생시키기 때문에 추천하는 방식은 아니다. JS 컨텐츠가 빠른 변경되거나 크롤러에서 지원하지 않는 JS 기능을 사용하는 경우에만 동적 렌더링을 사용하는게 좋다.

작동방식

동적 렌더링 서버는 user-agent 등을 통해서 크롤러를 탐지한다. 만약 크롤러인 경우 별도로 라우팅을 해준다. (추가로 버전별로 렌더 페이지를 나눠서 줄 수도 있다.)

동적 렌더링은 cloaking 으로 간주되지 않음

cloaking: 검색 순위를 조작하거나 다른 경로로 보내는 등의 목적으로 검색엔진과 사용자에게 서로 다른 컨텐츠를 주는 행위 (해킹된 사이트에서 관리자 모르게 클로킹을 할 수도 있음)

구글 검색엔진은 동적 렌더링을 클로킹으로 간주하지 않음

동적렌더링 말고 다른건 뭐가 있나

https://web.dev/articles/rendering-on-the-web?hl=en