Design a Web Crawler

// RFC 9309 status handling. The asymmetry is the part people get wrong:
//   4xx  -> "unavailable": the crawler MAY access any resource.
//   5xx or transport failure -> "unreachable": MUST assume complete disallow.
const CACHE_MS = 24 * 60 * 60 * 1000;   // section 2.4: not more than 24 hours
const PARSE_LIMIT = 500 * 1024;         // section 2.5: at least 500 KiB

const cache = new Map();   // origin -> { policy, fetchedAt }

export async function robotsFor(origin, { userAgent }) {
  const hit = cache.get(origin);
  if (hit && Date.now() - hit.fetchedAt < CACHE_MS) return hit.policy;

  let policy;
  try {
    const res = await fetch(`${origin}/robots.txt`, {
      headers: { 'user-agent': userAgent },
      redirect: 'follow',
      signal: AbortSignal.timeout(10_000),
    });

    if (res.status >= 400 && res.status < 500) {
      policy = { allowAll: true };                    // unavailable: crawl freely
    } else if (!res.ok) {
      policy = { disallowAll: true };                 // unreachable: stop
    } else {
      // Truncate before parsing. A multi-megabyte robots.txt is either a
      // mistake or an attempt to exhaust your parser.
      const body = (await res.text()).slice(0, PARSE_LIMIT);
      policy = parseRobots(body, userAgent);
    }
  } catch {
    // A timeout, DNS failure or TLS error is "unreachable", not "allowed". The
    // RFC does let you keep using a stale cached copy while it is unreachable,
    // which is kinder than stopping dead on one bad minute.
    policy = hit?.policy ?? { disallowAll: true };
  }

  cache.set(origin, { policy, fetchedAt: Date.now() });
  return policy;
}

// Two details worth getting right in parseRobots: group lines by user-agent and
// use the most specific matching group only (not the union with *), and pick the
// longest matching Allow or Disallow rule, where Allow wins a tie.

// 64-bit simhash - the near-duplicate test described in Manku, Jain and Das
// Sarma, "Detecting near-duplicates for web crawling" (WWW 2007). Documents
// whose hashes differ in at most 3 of the 64 bits count as near-duplicates.
// Unlike MD5, a one-word change moves a few bits rather than all of them.
import { createHash } from 'node:crypto';

function featureHash(token) {
  return createHash('md5').update(token).digest().readBigUInt64BE(0);
}

// Shingles, not single words: word frequency alone cannot tell a page from a
// reshuffling of the same page.
function* shingles(text, n = 4) {
  const words = text.toLowerCase().match(/[a-z0-9]+/g) ?? [];
  for (let i = 0; i + n <= words.length; i++) yield words.slice(i, i + n).join(' ');
}

export function simhash(text) {
  const weights = new Array(64).fill(0);
  for (const token of shingles(text)) {
    const h = featureHash(token);
    for (let bit = 0; bit < 64; bit++) {
      // `1n << BigInt(bit)` is shorthand for 2n ** BigInt(bit).
      weights[bit] += (h & (1n << BigInt(bit))) === 0n ? -1 : 1;
    }
  }
  let out = 0n;
  for (let bit = 0; bit < 64; bit++) if (weights[bit] > 0) out |= 1n << BigInt(bit);
  return out;
}

export function nearDuplicate(a, b, k = 3) {
  let x = a ^ b;
  let bits = 0;
  while (x !== 0n) { x &= x - 1n; bits++; }   // clears the lowest set bit each pass
  return bits <= k;
}

// Scanning every stored hash is O(n) and hopeless at scale. The paper's trick:
// split the 64 bits into blocks, build one sorted table per permutation of the
// blocks, and look up by block prefix - any pair within 3 bits must share at
// least one whole block.
export function blocks(h) {
  return [0n, 16n, 32n, 48n].map((shift) => Number((h >> shift) & 0xffffn));
}

// Canonicalise before the seen-check. The WHATWG URL parser already lowercases
// the host, resolves dot segments and drops default ports, so the work left is
// the part that is policy rather than parsing.
const TRACKING = /^(utm_|gclid$|fbclid$|mc_eid$|ref$)/;

export function canonicalise(raw, base) {
  const u = new URL(raw, base);     // throws on a malformed href - catch and drop
  u.hash = '';                      // fragments never reach the server
  u.hostname = u.hostname.replace(/\.$/, '');   // trailing root dot
  if (u.pathname === '') u.pathname = '/';

  // Drop tracking parameters and sort the rest: query order is not meaning on
  // the overwhelming majority of sites. This is a heuristic, and on the rare
  // site where order matters it will merge two distinct pages - which is why
  // the rule belongs in one reviewable function rather than inline.
  const keep = [...u.searchParams].filter(([k]) => !TRACKING.test(k));
  keep.sort(([a], [b]) => (a < b ? -1 : a > b ? 1 : 0));
  u.search = new URLSearchParams(keep).toString();

  return u.toString();
}

// The seen-set is the other half. Exact membership in a database is correct and
// costs a round trip per URL. A Bloom filter is in-memory and O(1), and its
// false positives mean silently never fetching a page you have never seen.
// That is a reasonable trade at ten billion URLs and a bad one at ten thousand:
// on a site audit, the pages you drop are the finding.
export class SeenSet {
  constructor(bloom, db) { this.bloom = bloom; this.db = db; }

  async addIfNew(url) {
    const key = canonicalise(url);
    if (!this.bloom.mightContain(key)) {      // definitely new - no query needed
      this.bloom.add(key);
      await this.db.insertUrl(key);
      return true;
    }
    // Possible false positive: confirm against the exact set. This keeps the
    // filter as a cheap negative cache instead of the source of truth.
    const existed = await this.db.insertUrlIfAbsent(key);
    return existed === false;
  }
}