Detecting Content Changes With Rolling Hashes #

Knowing that a page changed is useful; knowing which part changed is what lets a pipeline reprocess a paragraph instead of a document, and tell a user that a price moved rather than that something moved. Content-defined chunking with a rolling hash gives that granularity cheaply and, crucially, without the whole document shifting when a single sentence is inserted. This guide implements it, as part of incremental crawling and change detection in the Pipeline Storage, Deduplication & Monitoring section.

Problem Framing #

The obvious approach — split the document into fixed-size blocks and hash each — fails on the most common edit. Inserting one sentence near the top shifts every subsequent byte, so every block boundary moves, every hash changes, and the comparison reports that the entire document is new. The technique detects appends and nothing else.

Boundaries derived from content are what make an insertion local.

Content-defined chunking fixes this by choosing boundaries from the content rather than from the offset. A rolling hash is computed over a sliding window, and a boundary is declared wherever that hash satisfies a condition. Because the condition depends only on the bytes in the window, an insertion changes the boundaries near it and leaves every other boundary exactly where it was — so the unchanged parts of the document produce the same chunks and the same hashes.

For a crawler this yields three things: a precise change region, a stable identifier for each block that can be deduplicated across documents, and a cheap similarity measure derived from the proportion of shared chunks.

Step-by-Step Implementation #

1. A rolling hash over a sliding window #

Minimum and maximum sizes bound both pathological cases.

class RollingHash:
    """Rabin-Karp style rolling hash: O(1) to advance the window by one byte."""

    BASE = 257
    MOD = (1 << 61) - 1

    def __init__(self, window: int = 48):
        self.window = window
        self.value = 0
        self.buffer: list[int] = []
        # BASE^(window-1) mod MOD, for removing the outgoing byte.
        self.high = pow(self.BASE, window - 1, self.MOD)

    def push(self, byte: int) -> int:
        if len(self.buffer) == self.window:
            outgoing = self.buffer.pop(0)
            self.value = (self.value - outgoing * self.high) % self.MOD
        self.buffer.append(byte)
        self.value = (self.value * self.BASE + byte) % self.MOD
        return self.value

A 48-byte window is a reasonable default for text: long enough that boundaries are not triggered by trivially common byte sequences, short enough that the chunker responds quickly after an edit.

2. Chunk on a content-defined condition #

from dataclasses import dataclass
import hashlib

@dataclass(frozen=True)
class Chunk:
    index: int
    offset: int
    length: int
    digest: str

def chunk_content(data: bytes, avg_size: int = 2048,
                  min_size: int = 512, max_size: int = 8192) -> list[Chunk]:
    """Split on content-defined boundaries so an edit only shifts nearby chunks."""
    mask = (1 << (avg_size.bit_length() - 1)) - 1     # ~1-in-avg_size chance per byte
    roller = RollingHash()
    chunks: list[Chunk] = []
    start = 0

    for position, byte in enumerate(data):
        value = roller.push(byte)
        length = position - start + 1
        if length < min_size:
            continue
        if (value & mask) == 0 or length >= max_size:
            block = data[start:position + 1]
            chunks.append(Chunk(len(chunks), start, len(block),
                                hashlib.blake2b(block, digest_size=16).hexdigest()))
            start = position + 1
            roller = RollingHash()

    if start < len(data):
        block = data[start:]
        chunks.append(Chunk(len(chunks), start, len(block),
                            hashlib.blake2b(block, digest_size=16).hexdigest()))
    return chunks

The minimum and maximum sizes bound the pathological cases. Without a minimum, content that happens to satisfy the boundary condition frequently produces thousands of tiny chunks; without a maximum, content that never satisfies it produces one enormous chunk and the whole exercise degenerates to a single hash.

3. Compare two versions #

@dataclass
class ChangeReport:
    changed: bool
    similarity: float
    added: list[Chunk]
    removed: list[Chunk]
    changed_regions: list[tuple[int, int]]      # (offset, length) in the new document

def compare(old: list[Chunk], new: list[Chunk]) -> ChangeReport:
    old_digests = {c.digest for c in old}
    new_digests = {c.digest for c in new}
    shared = old_digests & new_digests
    union = old_digests | new_digests

    added = [c for c in new if c.digest not in old_digests]
    removed = [c for c in old if c.digest not in new_digests]

    regions, current = [], None
    for chunk in added:
        if current and chunk.offset == current[0] + current[1]:
            current = (current[0], current[1] + chunk.length)      # merge adjacent
        else:
            if current:
                regions.append(current)
            current = (chunk.offset, chunk.length)
    if current:
        regions.append(current)

    return ChangeReport(
        changed=bool(added or removed),
        similarity=len(shared) / len(union) if union else 1.0,
        added=added, removed=removed, changed_regions=regions,
    )

The similarity figure is genuinely useful beyond the boolean. A change of 0.98 similarity is a typographical fix; 0.4 is a substantial rewrite; 0.05 is a different page at the same URL, which usually means the site restructured or the URL was recycled. Routing those three to different handling — ignore, reprocess, re-examine the extraction — is what makes the granularity pay off.

4. Apply it to the right input #

Chunk the extracted text, not the raw HTML. Markup churn — a changed class name, a reordered attribute, a rotating advertisement — produces chunk changes that mean nothing, and the report fills with noise.

def content_for_chunking(record: dict) -> bytes:
    """Stable, reader-facing text: the same input the change fingerprint uses."""
    parts = [record.get("title") or "", record.get("description") or ""]
    parts.extend(section.get("text", "") for section in record.get("sections", []))
    text = "\n".join(" ".join(p.split()) for p in parts if p)
    return text.encode("utf-8")

Sharing this normalisation with the change fingerprint and the dedup content hash is what keeps the three answers consistent. Three different notions of “the content” produce three different verdicts about whether a page changed, and reconciling them later is much harder than sharing one function now.

5. Store chunks compactly #

CREATE TABLE content_chunks (
    natural_key text        NOT NULL,
    generation  int         NOT NULL,
    chunk_index int         NOT NULL,
    digest      bytea       NOT NULL,
    length      int         NOT NULL,
    PRIMARY KEY (natural_key, generation, chunk_index)
);
CREATE INDEX content_chunks_digest_idx ON content_chunks (digest);

Store digests, not chunk contents. A typical page produces a few dozen chunks of 16 bytes each — a few hundred bytes per version, which is affordable to keep for several generations, whereas the chunk text is not. The digest index also enables a useful side effect: identical chunks across different URLs identify shared boilerplate and syndicated passages without any extra work.

Verification & Testing #

Chunk the extracted text, not the markup, or churn dominates the report.

def test_insertion_shifts_only_nearby_chunks():
    original = b"paragraph one. " * 200
    edited = b"paragraph one. " * 5 + b"INSERTED SENTENCE. " + b"paragraph one. " * 195
    report = compare(chunk_content(original), chunk_content(edited))
    assert report.similarity > 0.9              # a fixed-size chunker would score ~0
    assert len(report.changed_regions) <= 2

def test_identical_content_is_unchanged():
    data = b"stable content " * 500
    assert compare(chunk_content(data), chunk_content(data)).changed is False

def test_chunk_sizes_stay_within_bounds():
    chunks = chunk_content(b"x" * 100_000, avg_size=2048, min_size=512, max_size=8192)
    assert all(512 <= c.length <= 8192 for c in chunks[:-1])

def test_complete_rewrite_scores_low():
    a, b = b"alpha content " * 300, b"entirely different words " * 300
    assert compare(chunk_content(a), chunk_content(b)).similarity < 0.1

The first test is the whole justification for content-defined chunking, and it is worth writing before the implementation: a fixed-size chunker fails it dramatically, which makes the comparison concrete for anyone reviewing the choice.

Compliance & Operational Guardrails #

Chunk digests inherit the retention class of the content they describe.
Chunk history is bounded — keep a small number of generations, not every version ever seen.
Personal data in changed regions is classified exactly as in the full record.
Chunking runs on normalised extracted text, shared with the fingerprint and dedup paths.
An erasure request removes the chunk rows along with the record they belong to.

Common Mistakes #

Chunking raw HTML. Markup churn dominates the report and the granularity becomes noise.
Storing chunk contents. Storage grows with the crawl rather than with the number of distinct pages.
Omitting minimum and maximum sizes. Pathological content produces either thousands of tiny chunks or one giant one.
Keeping unbounded chunk history. It becomes a full version history of every page, with the retention obligations that implies.

Frequently Asked Questions #

How does this differ from SimHash? #

They answer different questions. SimHash produces one fingerprint per document and answers “are these two documents similar”, which is what near-duplicate detection needs. Rolling-hash chunking answers “which parts of this document changed”, which is what incremental reprocessing needs. Many pipelines use both: SimHash across documents, chunking within one document over time.

What average chunk size should I use? #

One to four kilobytes suits article-length text. Smaller chunks give finer change regions and more storage; larger chunks give coarser regions and less. Since the value here is the change region rather than deduplication, err toward smaller when the downstream consumer acts on specific sections, and larger when it only needs a similarity score.

Can chunk digests deduplicate across pages? #

Yes, and it is a useful side effect. Chunks shared across many URLs on one host are boilerplate — navigation, disclaimers, footers — and excluding them before comparing improves both change detection and near-duplicate scoring. A digest appearing on more than a few percent of a host’s pages is boilerplate by definition.

How many generations of chunks should be retained? #

Two is enough for change detection: the current version and the previous one. Keeping more turns the chunk store into a full version history of every page, which multiplies both storage and the retention obligations attached to any personal data in the content. Where a longer history is genuinely required — regulatory archiving, for instance — give it its own retention class and exclude personal fields from the historical rows rather than retaining everything by default.

Can the chunking be run incrementally as bytes arrive? #

Yes, and it is one of the technique’s advantages: the rolling hash is computed in a single forward pass, so chunks can be emitted while the response is still streaming. That keeps memory flat for large documents and lets an early-exit condition — a first chunk identical to the stored one — skip the remainder of the comparison entirely.

Incremental Crawling and Change Detection — where change detection sits among the three layers.
Conditional Requests With ETag and Last-Modified — avoiding the transfer before chunking is needed at all.
Near-Duplicate Detection With SimHash — the across-documents counterpart to this within-document technique.