2024-01-16 Search Engine

240116

• Hyperlinks
• Internet Archive: Grateful Dead at Internet Archive

Surface Web

• Surface Web: Discoverable by Search Engines
• Deep Web: Not discoverable by Search Engines (Surface-level crawlers). Has 90% of the internet's data
  • Dark Web: Accessible through specific browsers like Tor

Google Pizza Box

See content.

Web Crawlers with Recursions

Web crawlers recurse with Hyperlinks:

• call crawler(link) -> Get all hyperlinks in that page -> for link in all links, call_crawler(link)

Web Crawling Issues

How to Crawl?

• Quality -- find "best" pages
• Efficiency -- avoid duplications
• Etiquette -- don't disturb the website's performance (robots.txt includes information on this): New York Times sues Microsoft and OpenAI for 'billions'

How much to crawl?

• Coverage -- How many % of the web?
• Relative Coverage -- How many do competitors have?

How often do you crawl?

• Freshness -- How much has changed?
• How much has changed?

Cohere Rerank

See content.

Simplest Crawler Lifecycle

flowchart LR
  A[Seed pages] --> B[Queue]
  B -->|dequeue| C[Fetch and parse]
  C -->|new links| B

• Begin with known seed pages
• Fetch and parse a page, loop.
  • Whenever you discover a new link, enqueue.
  • Dequeue one by one.
• Not feasible in 1 machine, need to distribute
• Challenges
  • need to filter spam or spider traps (a spider trap, also known as a crawler trap, is a set of web pages that can cause a web crawler or search bot to enter an infinite loop or other recursive situation, wasting its resources and affecting the crawler's ability to explore a website.)
• Non-malicious sites also have problems
  • Latency and bandwidth of remote servers
  • Robots.txt stipulation prevents web pages from being visited.
  • Mirrored or duplicate content
• Politeness, only visit it occasionally.

Crawling Strategies

• BFS crawling brings in high-quality pages early in the crawl
• Adding links to the end of the queue (FIFO) results in a BFS
• Adding them to the front of the queue (LIFO) yields a DFS
• Prioritizing links in a certain way can create a "focused crawler" that targets "interesting" pages, such as
  • documents that change frequently
  • those whose content is relevant to a specific topic.
• One method of re-ordering the URLs on the queue is reordering by
  • High In-degree
  • High PageRank.

Avoid Page Duplications

• Determine if the page is already seen
  • Must store URLs in a "standard" format
  • Must develop a fast way to check if a URL has already been seen: Use trie with / as the separator
• Determine if a new page has already been seen,
  • Identify whether a particular page was indexed
  • Identify whether a near-identical page was already indexed

Anomalies

• Some anchors don't have links
• Some anchors produce dynamic pages with JS, which can lead to looping

Representing URLs

URLs are long, about 80 bytes on average. 1 trillion URLs take 80 terabytes. Google found 30 trillion unique URLs, which comes to 2400 terabytes (2.4 petabytes).

Two ways to check whether a new URL was already seen:

• Hash the host or domain name first, then walk a trie to see whether the path matches one already in the URL database.
• Sort the URLs alphabetically and save them in a text file with delta encoding. Each URL is stored as the difference (delta) from the one before it. Storage drops a lot, but getting a URL back is slow, because you have to apply every delta from the first URL. So you checkpoint every so often by storing a full URL.

Normalize URLs

Avoiding Spider Traps

A spider trap is when a crawler keeps visiting the same page over and over. One of the most common kinds comes from session IDs, which J2EE, ASP, .NET, and PHP manage. Sites use them to track visitors, and some put a unique ID right in the URL, so every visitor gets their own ID, often requested on every page. Googlebot visits a page, crawls it, and leaves. Then it lands on another page that links back to the first one, but with a different session ID, so the link looks like a brand new URL. One fix is to be careful whenever the query string has "ID=". Another is to watch the URL length and stop once it gets too long.

Handling Spam Web Pages

Spam pages came in three generations.

1. Repeated words. The first spam pages repeated words to rank high, and hid them by making the text the same color as the background. Search engines still indexed and counted them.
2. Cloaking. When the server detected a crawler, it returned a different page than the one a user would get, so the page got indexed for the wrong content.
3. Doorway pages. Text and metadata picked to rank high for specific keywords. But a browser that requested the doorway page got a more "commercially oriented" page with more ads.

Measuring and Tuning a Crawler

A faster crawler comes down to three things. Faster URL parsing, more network bandwidth, and better fault tolerance. Other issues come up too, like how often to restart the process (refresh strategies), detecting duplicate pages, spotting mirror sites, speeding up DNS lookup, normalizing URLs, and handling malformed HTML.

DNS caching, pre-fetching and resolution

DNS lookup in a common operating system can block, because only one request can be outstanding at a time. Three ways around it:

1. DNS caching. Run a caching server that keeps the IP and domain name mappings you already found.
2. Pre-fetching client. As soon as a page is parsed, send DNS resolution requests to the caching server. If it can't resolve one, use UDP (User Datagram Protocol) to resolve it from the DNS server.
3. Customize the crawler. Run many DNS resolvers, so the crawler can send many resolution requests at once.

Multi-Threaded Crawling

One major bottleneck in downloading pages one by one is network delay. So run many threads in parallel, each requesting a page from a different host. (A thread is the smallest sequence of instructions a scheduler can manage on its own. Usually a thread lives inside a process, and several threads in one process share its resources.)

Hand URLs out to the threads so requests spread evenly across hosts. That maximizes throughput without overloading any one server. Early Google's spider had several coordinated crawlers with around 300 threads each, and together they downloaded over 100 pages per second in 2010. In 2021, Google is estimated to download around 50,000 pages per second, or 4 billion+ a day.

Distributed Crawling Approaches

Once the crawler program itself is tuned, the next question is how many crawlers to run at once. Two setups:

1. A centralized crawler controls a set of parallel crawlers on a local area network. A parallel crawler is several crawling processes talking over the network, also called an intra-site parallel crawler.
2. A distributed set of crawlers runs on machines spread far apart, and they may or may not talk to each other.

Crawlers in different places need some organization, by country, region, or available bandwidth. Distributed crawlers should update a master index every so often. Luckily incremental updates are usually cheap, since you can compress and send just the differential update, which keeps communication small.

Benefits

• Scalability: Large-scale web crawls can be easily handled.
• Cost-effectiveness: Cheaper machines can be used.
• Network load reduction: By dividing the web into regions, only the nearest pages are crawled.

Issues

• Overlap: Multiple downloaded pages should be minimized.
• Quality: The crawl strategy determines the quality of the results.
• Communication bandwidth: Minimization is required to ensure smooth communication.

Three strategies

Classification of Parallel Crawlers

In exchange mode, there are two ways to cut down communication between processes.

• Batch communication. Each process collects some URLs and sends them in a batch.
• Replication. The k most popular URLs are copied to every process and never exchanged (picked from the previous crawl or on the fly).

There are a few ways to partition the web. URL-hash-based partitioning makes lots of links between partitions, and site-hash-based partitioning makes fewer. Hierarchical partitioning splits by top-level domain (TLD), like .com, .net, and so on.

Going by Cho and Garcia-Molina's research, firewall crawlers are cheap and give good, general coverage. Cross-over crawlers get 100% quality but suffer from overlap. Replicating URLs and batching communication both cut the overhead.

Freshness

Crawlers follow a set of policies. Which pages to download, when to check for changes, how not to overload websites, and how to coordinate distributed crawlers. The web keeps changing, with new pages, updated pages, and deleted pages. To stay current, crawlers re-check pages they already crawled for updates and deletions. They use the LastModified indicator to tell whether a page changed, and reload the whole page only when they have to. They also track how often each page changes and come back sooner to pages that have historically changed a lot. And to keep popular pages fresh, they update pages that get visited more often first.

Implications for a Web Crawler

Search engines usually run several crawlers nonstop. When a crawler swaps an old version of a page for a new one, it can do it in place or by shadowing.

Shadowing

With shadowing, a new set of pages is collected and stored separately, then all of them go live at once. So queries have to search two databases, the current one and the one with the new pages. That can slow queries down or make results less fresh. So it's better to run several kinds of crawlers and update the index in place to keep it current.