A forensic fingerprint lab never compares a fresh print against every record in a national database one pixel at a time. It first reduces the print to a coarse classification, loops, whorls, arches, a handful of minutiae points, and only then runs a detailed comparison against the short list of records that share that coarse signature. Cheap coarse filter first, expensive exact comparison second, is the only reason an AFIS system stays fast as its database grows into the hundreds of millions of records.

Pinterest’s image corpus needs the exact same funnel, except the fingerprints are photographs and there are 300 billion of them. A single popular product photo, recipe image, or wedding dress gets uploaded to Pinterest thousands of times over: saved from a retailer’s site, re-cropped by a blogger, recompressed by a third app, watermarked by a stock photo site, resized by a mobile client. Every one of those is visually the same image to a human looking at it, and every one of those produces a completely different sequence of bytes on disk.

That last part is what breaks the naive approach. Hashing the raw file bytes (MD5, SHA-256) and looking for an exact match only catches images that are byte-for-byte identical, which in practice is a small minority of real-world duplicates. Change one pixel, resave as a lower JPEG quality, or crop ten pixels off an edge, and the exact hash is unrecognizably different even though nothing meaningful about the image changed. At 300 billion pins, exact-hash dedup catches almost none of the actual redundancy sitting in the corpus, which means Pinterest is paying to store, replicate, and serve the same visual content dozens of times over under dozens of different pin IDs.

What we need instead is a notion of “close enough” similarity, computed cheaply enough to run on every upload, and searchable across hundreds of billions of existing images without a linear scan. The forces in tension are speed (the check has to add almost nothing to the pin creation path), correctness (never merge two genuinely different images just because their fingerprints happen to collide), and cost (the index built to find duplicates cannot itself become bigger than the storage it saves). We need to solve for sublinear candidate lookup across a hash space with hundreds of billions of entries, a tunable definition of “the same image,” and a safe, reversible way to reclaim storage from confirmed duplicates, simultaneously.

Requirements and Constraints

Functional Requirements

• Compute a perceptual fingerprint for every newly uploaded pin image before it is durably stored
• Check the new fingerprint against the existing corpus and, if a near-duplicate is found above the configured similarity threshold, link the new pin to the existing canonical image instead of storing a new copy
• If no match is found, store the image as a new canonical image and index its fingerprint for future lookups
• Support configurable similarity thresholds per use case: strict for automatic merge-on-ingest, looser for surfacing “possible duplicate” candidates to a moderation queue
• Run a background storage reclamation pipeline that finds duplicate images stored before this system existed, or missed at ingest time, and merges them to free blob storage
• Guarantee that hash collisions never cause two genuinely different images to be silently merged
• Expose a query API so downstream systems (visual search, copyright tooling) can ask “does this image already exist in the corpus” without triggering ingest side effects

Non-Functional Requirements

• Ingest latency: the dedup check adds p99 under 50ms to the pin creation path
• Scale: roughly 190 billion canonical images already indexed (of 300 billion total pins, since many pins already point at a shared image), 150 million new pin uploads/day, averaging ~1,740 uploads/sec with peaks around 8,000/sec
• Index availability: 99.95% for the fingerprint index; the ingest path fails open (stores as new) rather than blocking a pin creation when the index is unavailable
• Precision: false-merge rate (two genuinely different images incorrectly linked as duplicates) under 1 in 10 million comparisons
• Reclamation throughput: able to re-scan the full existing corpus for missed duplicates within a rolling 30-day window
• Durability: the reclamation pipeline must never delete a blob that still has a live pin reference, under any failure or retry condition

Constraints and Assumptions

• Out of scope: the visual search and “shop the look” recommendation products built on top of image similarity - we build the dedup detection and storage reclamation layer they could sit on, not those products themselves
• We assume images arriving at this system have already passed content moderation and virus scanning
• We fail open on the ingest path: a dedup check that cannot complete within budget, or an unavailable index, results in the image being stored as new, never in a blocked or dropped upload
• We do not attempt to deduplicate video or animated GIF content in this design, only static images
• We target a single authoritative fingerprint index per region; cross-region replication is discussed but region failover is not the primary design target

High-Level Architecture

The system has five major components: the Ingest Gateway (orchestrates the synchronous dedup check), the Perceptual Hash Service (turns pixels into a compact fingerprint), the LSH Index Cluster (sharded approximate-match lookup over the fingerprint space), the Similarity Verifier (turns candidates into a yes/no duplicate decision), and the Storage Reclamation Pipeline (an offline batch process that finds and merges duplicates the ingest path missed).

A pin upload arrives at the Ingest Gateway carrying the raw image bytes. The Gateway calls the Perceptual Hash Service, which decodes the image and computes two complementary fingerprints, a dHash (difference hash, fast and robust to recompression) and a pHash (DCT-based, more robust to color and contrast shifts), each a 64-bit integer. The Gateway then queries the LSH Index Cluster with those fingerprints, which returns a small candidate set of canonical images that are plausibly similar, without ever scanning the full corpus. The Similarity Verifier computes the exact Hamming distance between the new fingerprint and every candidate, cross-checks agreement between dHash and pHash, and decides whether this is truly a duplicate. If it is, the new pin links to the existing canonical image and no new blob is stored. If it is not, the image is stored as a new canonical image and its fingerprint is written into the LSH Index for future lookups.

The Storage Reclamation Pipeline runs entirely off the hot path. It periodically re-scans the corpus (or a targeted slice of it, such as images uploaded before this system existed, or images affected by a threshold change) looking for duplicate clusters the ingest-time check missed, merges them, and garbage collects blobs whose reference count drops to zero. Nothing in that pipeline is allowed to touch the ingest latency budget.

Component Deep Dives

The Ingest Gateway and Perceptual Hash Service

This component’s job is to turn raw image bytes into a compact, comparable fingerprint fast enough that computing it never becomes the bottleneck in the pin creation flow.

A smart engineer’s first instinct is to use a cryptographic hash (SHA-256) because it is fast, well understood, and collision-resistant. The problem is that cryptographic hashes are designed to change completely for a single flipped bit, which is exactly the wrong property here. We want the opposite: a hash that changes gracefully, staying close in hash space when the image changes only a little, and moving far away when the image changes a lot. That property is what perceptual hashing is built for.

// Ingest Gateway -> Perceptual Hash Service RPC contract
// Demonstrates: request/response shape for the synchronous ingest-time hash call
syntax = "proto3";

package pinterest.dedup.v1;

message HashRequest {
  string upload_id = 1;
  bytes image_bytes = 2;
  string content_type = 3;  // image/jpeg, image/png, image/webp
}

message HashResponse {
  fixed64 dhash = 1;        // 64-bit difference hash
  fixed64 phash = 2;        // 64-bit DCT perceptual hash
  uint32 width = 3;
  uint32 height = 4;
  bool low_entropy = 5;     // flagged for near-blank / low-detail images
}

service PerceptualHashService {
  rpc ComputeHash(HashRequest) returns (HashResponse);
}

# Perceptual Hash Service: dHash computation
# Demonstrates: difference hash generation, robust to recompression and minor crops
from PIL import Image
import numpy as np

def compute_dhash(image: Image.Image, hash_size: int = 8) -> int:
    # Resize to (hash_size+1) x hash_size grayscale - the extra column
    # gives us hash_size horizontal gradient comparisons per row
    resized = image.convert("L").resize((hash_size + 1, hash_size), Image.LANCZOS)
    pixels = np.asarray(resized, dtype=np.int16)

    diff = pixels[:, 1:] > pixels[:, :-1]  # each pixel brighter than its left neighbor?
    bits = diff.flatten()

    fingerprint = 0
    for bit in bits:
        fingerprint = (fingerprint << 1) | int(bit)
    return fingerprint  # 64-bit integer for hash_size=8 (8 rows * 8 comparisons)

dHash is deliberately cheap: resize to a 9x8 grid, compare adjacent pixel brightness, pack the booleans into a 64-bit integer. It survives JPEG recompression and small crops well because the gradient structure of an image barely changes under those transforms, even though every byte on disk does. It is more fragile to rotation and heavy watermarking, which is why we compute a second, complementary fingerprint.

# Perceptual Hash Service: pHash computation
# Demonstrates: DCT-based perceptual hash, robust to color/contrast shifts
import numpy as np
from PIL import Image
from scipy.fftpack import dct

def compute_phash(image: Image.Image, hash_size: int = 8, highfreq_factor: int = 4) -> int:
    img_size = hash_size * highfreq_factor
    resized = image.convert("L").resize((img_size, img_size), Image.LANCZOS)
    pixels = np.asarray(resized, dtype=np.float64)

    # 2D DCT concentrates image energy into the top-left, low-frequency corner
    dct_result = dct(dct(pixels, axis=0), axis=1)
    low_freq = dct_result[:hash_size, :hash_size]

    # Median, not mean - resistant to a few very bright/dark outlier pixels
    median = np.median(low_freq[1:, 1:])  # skip DC coefficient at [0][0]
    diff = low_freq > median

    fingerprint = 0
    for bit in diff.flatten():
        fingerprint = (fingerprint << 1) | int(bit)
    return fingerprint

The pHash operates in the frequency domain instead of the pixel domain. Two images with the same overall structure but different color grading or brightness will produce nearly identical low-frequency DCT coefficients, so pHash catches similarity that dHash sometimes misses, at roughly 5-10x the compute cost. We run both, in parallel, on every upload, and require both signals to agree during verification, which is what makes the collision-handling story in the next component work at all.

LSH Index and Hash Bucket Sharding

This component’s job is to answer “which existing canonical images are plausibly similar to this fingerprint” in milliseconds, without ever comparing against all 190 billion indexed images.

The naive approach is a linear scan: compute the Hamming distance between the new fingerprint and every fingerprint in the corpus, keep the ones under a threshold. That is O(n) per lookup, and at 190 billion entries it is not a database query, it is a batch job. What we need is a way to only look at a small, likely-relevant slice of the index, which is exactly what locality-sensitive hashing (LSH) buys us: a family of hash functions where similar inputs are far more likely to land in the same bucket than dissimilar inputs, so we only need to compare against whatever else is already in our bucket.

Our banding scheme uses a specific, well-known LSH construction for Hamming space based on the pigeonhole principle. If we want to guarantee catching every pair of fingerprints within Hamming distance k, we partition the 64-bit fingerprint into k + 1 blocks and build one index table per block position. Any two fingerprints that differ in at most k bits must, by the pigeonhole principle, be identical in at least one of the k + 1 blocks, because k differing bits spread across k + 1 blocks cannot touch every block. For our operating threshold of k = 8, that means 9 index tables.

# LSH Index: pigeonhole bit-partitioning for Hamming-distance search
# Demonstrates: block table construction, candidate lookup via block-value match
from collections import defaultdict

HASH_BITS = 64
NUM_BLOCKS = 9  # guarantees recall for Hamming distance <= 8

def block_boundaries(num_blocks: int = NUM_BLOCKS, total_bits: int = HASH_BITS) -> list[tuple[int, int]]:
    # 9 blocks over 64 bits: eight 7-bit blocks + one 8-bit block
    base = total_bits // num_blocks
    remainder = total_bits % num_blocks
    bounds, start = [], 0
    for i in range(num_blocks):
        width = base + (1 if i < remainder else 0)
        bounds.append((start, start + width))
        start += width
    return bounds

BLOCKS = block_boundaries()

def extract_block(fingerprint: int, block_idx: int) -> int:
    start, end = BLOCKS[block_idx]
    width = end - start
    shift = HASH_BITS - end
    mask = (1 << width) - 1
    return (fingerprint >> shift) & mask

class LSHIndexShard:
    # One shard holds NUM_BLOCKS tables, each mapping a block value -> candidate set
    def __init__(self):
        self.tables = [defaultdict(set) for _ in range(NUM_BLOCKS)]

    def insert(self, canonical_image_id: int, fingerprint: int) -> None:
        for i in range(NUM_BLOCKS):
            key = extract_block(fingerprint, i)
            self.tables[i][key].add(canonical_image_id)

    def candidates(self, fingerprint: int, max_bucket_scan: int = 2000) -> set[int]:
        # Union candidates across every block table - one exact-block match is enough
        found = set()
        for i in range(NUM_BLOCKS):
            key = extract_block(fingerprint, i)
            bucket = self.tables[i].get(key, ())
            if len(bucket) > max_bucket_scan:
                continue  # degenerate hot bucket - handled by verifier's low-entropy path
            found.update(bucket)
        return found

Think of it like the fingerprint lab’s coarse classification, except instead of one classification (loop, whorl, arch), we run nine independent coarse classifications in parallel and take the union of everyone who matches on at least one of them. A single block match is a weak signal on its own (as few as 7 bits of agreement), which is why every candidate still goes through exact Hamming-distance verification before being treated as a duplicate.

We do not run a single global index. We shard by a coarse routing prefix (the top 12 bits of the dHash) across 4,096 index shards, so a lookup only ever queries the one shard that owns that fingerprint’s prefix range, not all 4,096. Each shard holds its own 9 block tables for the ~46 million canonical images that route to it.

# LSH index shard topology configuration
# Demonstrates: coarse routing bits, shard count, replica factor
index_cluster:
  routing_bits: 12          # top 12 bits of dhash select the shard
  shard_count: 4096         # 2^12
  replicas_per_shard: 2
  block_tables_per_shard: 9
  max_bucket_scan: 2000     # candidates beyond this are treated as degenerate
  shard_node_class: r6g.xlarge
  images_per_shard_avg: 46_000_000

The Similarity Verifier and Threshold Tuning

This component’s job is to turn a noisy candidate set into a precise yes-or-no duplicate decision, and to make that decision tunable rather than hardcoded.

The naive assumption is that a block match from the LSH index is already good enough evidence of similarity. It is not: a 7-bit or 8-bit block match happens by pure chance far more often than most engineers expect, especially against a 190-billion-image corpus, and treating a raw candidate as a confirmed duplicate would flood the corpus with false merges. The verifier’s job is to take every candidate that survived the LSH lookup and apply the actual comparison we care about: full 64-bit Hamming distance, cross-checked across both hash signals.

# Similarity Verifier: exact Hamming distance + multi-signal agreement
# Demonstrates: bit-count popcount, dual-hash cross-check, threshold decision
def hamming_distance(a: int, b: int) -> int:
    return bin(a ^ b).count("1")  # XOR then popcount

DUPLICATE_THRESHOLD_BITS = 8      # out of 64 - roughly 12.5% of bits may differ
REVIEW_QUEUE_THRESHOLD_BITS = 14  # looser band surfaced to moderators, not auto-merged

def classify(new_dhash: int, new_phash: int, candidate_dhash: int, candidate_phash: int) -> str:
    d_dist = hamming_distance(new_dhash, candidate_dhash)
    p_dist = hamming_distance(new_phash, candidate_phash)

    # Require both signals to agree - this is what makes single-block collisions safe.
    # A candidate that only matches on dHash but diverges wildly on pHash is very
    # likely a false positive from the LSH block table, not a true duplicate.
    if d_dist <= DUPLICATE_THRESHOLD_BITS and p_dist <= DUPLICATE_THRESHOLD_BITS:
        return "duplicate"
    if d_dist <= REVIEW_QUEUE_THRESHOLD_BITS and p_dist <= REVIEW_QUEUE_THRESHOLD_BITS:
        return "possible_duplicate"
    return "unique"

A smart engineer’s next assumption is that one fixed threshold works everywhere. It does not, because different use cases weigh false positives and false negatives differently. Auto-merging on ingest needs a strict, high-precision threshold, because a wrongful merge silently makes a user’s unique upload disappear behind someone else’s pin. Surfacing “possible duplicate” suggestions to a moderation or storage-savings dashboard can tolerate a looser threshold, because a human reviews before anything is deleted. We expose both thresholds as tuned, versioned config rather than constants, and we cover how those numbers get chosen in the algorithms section below.

Storage Reclamation Pipeline

This component’s job is to find and merge duplicates that the ingest-time check missed, and to safely delete the now-redundant blob storage behind them.

The ingest check only ever compares a new upload against images already in the corpus at the moment of upload. It cannot retroactively catch two images that were both uploaded before this system existed, or a pair that should have matched but did not because the similarity threshold was tightened after the fact, or a match that was missed because a degenerate hot bucket got capped during the original lookup. All of that redundancy sits latent in the corpus until an offline process goes looking for it.

// Storage Reclamation worker: merge a confirmed duplicate cluster and GC the loser
// Demonstrates: reference counting, safe blob deletion, idempotent merge
package reclamation

import (
	"context"
	"fmt"
)

type MergeDecision struct {
	SurvivingImageID  int64
	DuplicateImageID  int64
	HammingDistance   int
}

// MergeCluster relinks every pin pointing at DuplicateImageID to SurvivingImageID,
// then decrements the duplicate's ref count. It never deletes a blob directly -
// deletion only happens once ref_count reaches zero, checked separately by the GC pass.
func MergeCluster(ctx context.Context, db Querier, d MergeDecision) error {
	tx, err := db.BeginTx(ctx)
	if err != nil {
		return fmt.Errorf("begin tx: %w", err)
	}
	defer tx.Rollback()

	// Idempotent: re-running a merge that already happened is a no-op, not an error.
	affected, err := tx.Exec(ctx, `
		UPDATE pins SET canonical_image_id = $1
		WHERE canonical_image_id = $2`,
		d.SurvivingImageID, d.DuplicateImageID)
	if err != nil {
		return fmt.Errorf("relink pins: %w", err)
	}

	if _, err := tx.Exec(ctx, `
		UPDATE images SET ref_count = ref_count - $1
		WHERE image_id = $2 AND ref_count >= $1`,
		affected, d.DuplicateImageID); err != nil {
		return fmt.Errorf("decrement ref_count: %w", err)
	}

	if _, err := tx.Exec(ctx, `
		UPDATE images SET ref_count = ref_count + $1
		WHERE image_id = $2`,
		affected, d.SurvivingImageID); err != nil {
		return fmt.Errorf("increment ref_count: %w", err)
	}

	return tx.Commit(ctx)
}

// GCEligibleBlobs finds images with zero references that have been zero for at
// least the grace period, so an in-flight pin creation racing the merge can never
// point at an already-deleted blob.
func GCEligibleBlobs(ctx context.Context, db Querier, graceHours int) ([]int64, error) {
	rows, err := db.Query(ctx, `
		SELECT image_id FROM images
		WHERE ref_count = 0
		  AND ref_count_zero_since < NOW() - ($1 || ' hours')::interval
		LIMIT 5000`, graceHours)
	if err != nil {
		return nil, err
	}
	defer rows.Close()

	var ids []int64
	for rows.Next() {
		var id int64
		if err := rows.Scan(&id); err != nil {
			return nil, err
		}
		ids = append(ids, id)
	}
	return ids, rows.Err()
}

The pipeline runs as a nightly Spark batch job over the images and LSH index tables, re-clusters fingerprints using the same pigeonhole blocks and verifier logic as the ingest path (so a merge decision made in batch is held to the same precision bar as one made online), and writes merge decisions that a smaller online worker applies transactionally. Deletion is always a two-step, delayed process: a blob only becomes GC-eligible once its reference count has been at zero for a grace period, which absorbs any race between a merge and a concurrent pin creation that had already resolved to the “loser” image before the merge committed.

Data Model

The core schema separates three concerns: the canonical image itself, the many pins that may point at it, and the LSH index entries used to find it.

-- Canonical images: one row per unique visual fingerprint kept in the corpus
CREATE TABLE images (
    image_id            BIGINT       PRIMARY KEY,
    dhash                BIGINT       NOT NULL,
    phash                BIGINT       NOT NULL,
    blob_key             TEXT         NOT NULL,   -- pointer into the blob store
    byte_size            INTEGER      NOT NULL,
    width                INTEGER      NOT NULL,
    height               INTEGER      NOT NULL,
    low_entropy          BOOLEAN      NOT NULL DEFAULT FALSE,
    ref_count            INTEGER      NOT NULL DEFAULT 1,
    ref_count_zero_since TIMESTAMPTZ,
    created_at           TIMESTAMPTZ  NOT NULL DEFAULT NOW(),
    CONSTRAINT ref_count_non_negative CHECK (ref_count >= 0)
);

CREATE INDEX idx_images_dhash ON images (dhash);
CREATE INDEX idx_images_low_entropy ON images (low_entropy) WHERE low_entropy = TRUE;
CREATE INDEX idx_images_gc_eligible ON images (ref_count_zero_since)
    WHERE ref_count = 0;

-- Pins: the user-visible object, always resolving through a canonical image
CREATE TABLE pins (
    pin_id              BIGINT       PRIMARY KEY,
    user_id              BIGINT       NOT NULL,
    canonical_image_id   BIGINT       NOT NULL REFERENCES images(image_id),
    upload_dhash          BIGINT       NOT NULL,  -- fingerprint of the bytes this user actually uploaded
    created_at            TIMESTAMPTZ  NOT NULL DEFAULT NOW()
);

CREATE INDEX idx_pins_canonical_image ON pins (canonical_image_id);
CREATE INDEX idx_pins_user_created ON pins (user_id, created_at DESC);

-- LSH block tables: one logical table per pigeonhole block, sharded independently
CREATE TABLE lsh_block_entries (
    shard_id             SMALLINT     NOT NULL,
    block_idx             SMALLINT     NOT NULL,   -- 0-8, which of the 9 blocks
    block_value            INTEGER      NOT NULL,   -- 7 or 8-bit block extracted from dhash
    image_id               BIGINT       NOT NULL REFERENCES images(image_id),
    PRIMARY KEY (shard_id, block_idx, block_value, image_id)
);

CREATE INDEX idx_lsh_lookup ON lsh_block_entries (shard_id, block_idx, block_value);

images.dhash and images.phash are stored inline for verification, but lsh_block_entries is the actual index used for candidate lookup, and it is partitioned first by shard_id (the coarse 12-bit routing prefix described earlier) and then by block_idx, so a single lookup for one fingerprint only ever touches the partitions for its shard. We deliberately keep the pins table separate from images and always resolve through canonical_image_id, so a merge is a cheap pointer update on the pins rows that referenced the losing image, never a rewrite of blob data.

An image record moves through four states over its life: uploaded (fingerprint computed, not yet classified), matched or new (the ingest-time verifier’s decision), indexed (a new canonical image’s fingerprint lands in lsh_block_entries), and reclaimed (a later batch pass finds it was actually a duplicate of something else, merges it, and its blob is garbage collected once its reference count hits zero). The diagram traces a single upload through each of those states and which component drives the transition.

Key Algorithms and Protocols

Perceptual Hash Generation

Covered in the Ingest Gateway section above (compute_dhash and compute_phash), the core property both algorithms share is that they map visually similar inputs to nearby points in a 64-bit space, rather than treating any byte-level change as a total change. dHash runs in O(hash_size^2) time dominated by the image resize, effectively constant per image regardless of original resolution since we always downscale first. pHash costs more, O(n^2 log n) for the DCT over an n x n grid, but n here is small (32x32 before extracting the top-left 8x8), so both hashes compute in low single-digit milliseconds even on modest hardware.

LSH Bucketing via Bit-Partitioned Index Tables

Covered in the LSH Index component above, the property that makes this correct rather than just fast is the pigeonhole guarantee: partitioning a 64-bit fingerprint into k + 1 blocks and indexing each block independently guarantees that any true match within Hamming distance k produces at least one exact block match, so it is found by the union of candidate lookups. Lookup complexity per query is O(NUM_BLOCKS) hash table lookups, each O(1) average case, plus verification cost proportional to the (capped) candidate set size, not to corpus size.

# Choosing block count from a target Hamming distance guarantee
def blocks_needed_for_distance(k: int) -> int:
    return k + 1

# k=8 -> 9 blocks (what this system uses)
# k=4 -> 5 blocks (fewer, wider blocks - tighter recall guarantee, smaller buckets)
# k=16 -> 17 blocks (more, narrower blocks - looser recall guarantee, larger buckets)

There is a direct tradeoff embedded in that formula: raising k to catch more distant near-duplicates requires more blocks, and more blocks means each block is narrower (fewer bits), which means more images collide on any given block value, which grows candidate set sizes and verification cost. We chose k=8 empirically as the point where recall on our labeled near-duplicate dataset stopped improving meaningfully while candidate set sizes kept growing.

Similarity Threshold Tuning

Choosing DUPLICATE_THRESHOLD_BITS is not a guess, it is a measured tradeoff against a labeled dataset of known-duplicate and known-distinct image pairs, swept across candidate thresholds to find the operating point that meets our precision target.

# Threshold calibration: sweep Hamming distance thresholds against labeled pairs
# Demonstrates: precision/recall tradeoff, picking an operating point
from dataclasses import dataclass

@dataclass
class LabeledPair:
    hamming_distance: int
    is_true_duplicate: bool  # ground truth from human-reviewed labeling

def evaluate_threshold(pairs: list[LabeledPair], threshold: int) -> tuple[float, float]:
    true_positives = false_positives = false_negatives = 0
    for pair in pairs:
        predicted_duplicate = pair.hamming_distance <= threshold
        if predicted_duplicate and pair.is_true_duplicate:
            true_positives += 1
        elif predicted_duplicate and not pair.is_true_duplicate:
            false_positives += 1
        elif not predicted_duplicate and pair.is_true_duplicate:
            false_negatives += 1

    precision = true_positives / max(true_positives + false_positives, 1)
    recall = true_positives / max(true_positives + false_negatives, 1)
    return precision, recall

def find_operating_point(pairs: list[LabeledPair], min_precision: float = 0.9999999) -> int:
    # Walk thresholds from strict to loose, pick the loosest one that still
    # clears the precision bar - maximizes recall subject to the false-merge budget
    best_threshold = 0
    for threshold in range(0, 33):
        precision, _ = evaluate_threshold(pairs, threshold)
        if precision >= min_precision:
            best_threshold = threshold
        else:
            break
    return best_threshold

Two thresholds, not one, come out of this process for us: a strict auto_merge threshold used at ingest, calibrated against a very high precision bar (we would rather miss a duplicate than silently merge two different users’ distinct uploads), and a looser review_queue threshold used only to populate a moderation dashboard where a human confirms before anything changes. The precision bar is intentionally asymmetric with recall: missing a duplicate costs a few hundred KB of avoidable storage, wrongly merging two images costs a user’s content silently disappearing behind someone else’s pin, which is a far more expensive mistake to make.

Hash Collision Handling

Two distinct failure shapes hide behind the word “collision” here, and they need different fixes. The first is a spurious LSH block match: two genuinely unrelated images happen to share one 7 or 8-bit block value by chance, which is common enough at this scale that it must be assumed to happen constantly. This is handled entirely by the verifier’s full 64-bit, dual-hash check covered above, a candidate surviving one block match is not evidence of similarity on its own, only a reason to look closer.

The second shape is degenerate hot buckets: images with very little visual entropy (solid color backgrounds, generic icons, near-blank scanned documents) whose fingerprints legitimately cluster together because there genuinely is not enough visual information to spread them across the hash space. A bucket like this can grow to millions of entries, and naively scanning all of them for every query would blow the latency budget. The max_bucket_scan cap in the LSH shard code, and the low_entropy flag from the hash service, exist specifically to short-circuit this case: once a bucket crosses the cap, we stop treating block matches from it as useful candidate signal and fall back to the stricter, capped comparison path described in the verifier section.

Scaling and Performance

The system scales along two independent axes: more LSH index shards to hold more canonical images and absorb more lookup throughput, and more Perceptual Hash Service workers to absorb more upload throughput. Because hashing is stateless and shard routing is a pure function of the fingerprint, both scale horizontally without coordination.

Capacity Estimation:

Given:
  - 190,000,000,000 canonical images already indexed
  - 150,000,000 new pin uploads/day (avg ~1,740/sec, peak ~8,000/sec)
  - 16-byte fingerprint per image (8-byte dhash + 8-byte phash)
  - 9 LSH blocks per image, ~12 bytes per block-table entry
  - 4,096 index shards, routed by a 12-bit prefix of dhash
  - 280 KB average stored size per canonical image (original + renditions)

LSH index storage:
  190e9 images * 9 blocks * 12 bytes/entry = 20.52 TB total block-table storage
  Per shard: 20.52 TB / 4096 shards ~= 5 GB/shard (comfortably fits in memory)

Fingerprint + metadata storage:
  190e9 images * (16 bytes hash + 8 bytes image_id + ~8 bytes metadata) ~= 6.1 TB

Ingest throughput per shard:
  Peak 8,000 uploads/sec routed across 4,096 shards ~= ~2 lookups/sec/shard average,
  with hot shards (viral content) absorbing far more - each lookup does 9 block-table
  reads (sub-millisecond, in-memory) plus a capped candidate verification pass

Verification cost:
  Candidate set capped at 2,000 per shard per query
  Hamming distance (XOR + popcount) per candidate: ~20-30ns
  2,000 candidates * 30ns ~= 60 microseconds - negligible next to the ~2-4ms hashing cost

Bandwidth saved by ingest-time dedup:
  ~35% of new uploads match an existing canonical image
  8,000 uploads/sec * 0.35 * 280 KB = ~784 MB/sec of write bandwidth
  never sent to durable blob storage during peak ingest

Legacy reclamation opportunity:
  Assume ~30% of the pre-system corpus is redundant, never deduped
  300e9 pins * 0.30 * 280 KB ~= ~25 PB of reclaimable blob storage

Reads dominate writes by a wide margin here too, but not in the usual sense: every ingest is simultaneously a write (a new fingerprint might get indexed) and a read (a lookup against existing fingerprints), so the real hot spot is not read/write ratio but shard skew. A single viral image, or a mass-produced product photo uploaded by thousands of sellers in a short window, routes an outsized share of lookups and inserts to one shard. We mitigate this the same way the low-entropy path does: cap candidate scanning per query, and let index shard placement rebalance based on observed load rather than a static prefix assignment alone, moving the hottest prefix ranges onto dedicated, more heavily replicated shards.

Failure Modes and Recovery

Failure	Detection	Impact	Recovery
LSH index shard unavailable	Ingest Gateway RPC to shard times out or errors	New uploads to that shard’s prefix range cannot be checked against the corpus	Fail open: store as new canonical image, index write retried async once shard recovers; a later reclamation pass catches any resulting duplicate
Degenerate hot bucket (low-entropy image)	Bucket size exceeds max_bucket_scan at insert or query time	Candidate scan would blow latency budget if run unfiltered	Bucket flagged, block-match signal from it dropped, image routed through the stricter low-entropy verification path instead
Reclamation merge races a concurrent pin creation	Pin insert references an image_id mid-merge	New pin could momentarily point at an image about to be marked a duplicate loser	Merge relinks all pins referencing the loser at transaction time; any pin created after commit already resolves against the surviving image via its own ingest-time lookup
Blob deleted while still referenced	Reference count check fails before delete, or GC query returns a false eligible ID	Would cause a broken image for any pin still pointing at that blob	GC only deletes blobs with ref_count = 0 sustained through a grace period (default 72 hours), never immediately on merge
Hash Service returns inconsistent hashes for the same image across retries	Ingest Gateway compares hash on retry against the one attached to the upload_id	A retried upload could be classified differently than the original attempt	Hash computation is deterministic and pure (no randomness, no external state); Gateway caches the first computed hash per upload_id and reuses it on retry rather than recomputing
Threshold miscalibration after a model or hash algorithm change	Precision/recall metrics on the labeled validation set regress after deploy	Either a spike in false merges or a drop in caught duplicates	Threshold changes are versioned and canaried against a shadow traffic slice before rollout; a regression triggers automatic rollback to the last validated threshold

Comparison of Approaches

Approach	Latency	Complexity	Failure Mode	Best Fit
Exact byte hash (MD5/SHA-256)	Under 1ms	Low	Misses the overwhelming majority of real-world duplicates (any recompression or crop defeats it)	Detecting truly identical file uploads, not near-duplicates
Perceptual hash + brute-force linear scan	Grows linearly with corpus size, infeasible past low millions of images	Low to build, does not scale operationally	Query latency degrades directly with corpus growth; unusable at hundreds of billions of images	Small, bounded corpora, or offline batch analysis with no latency requirement
Perceptual hash + bit-partitioned LSH (this design)	Sub-10ms candidate lookup, ~50ms total ingest check	High (shard topology, threshold calibration, collision handling)	Degenerate hot buckets need explicit capping; threshold miscalibration risks false merges	High-volume, latency-sensitive dedup at massive scale, the common case for a large-scale UGC image platform
CNN embedding + approximate nearest neighbor (FAISS/HNSW)	Comparable to LSH for lookup, higher hash generation cost (inference vs. simple hash)	Very high (model training, embedding drift, GPU inference infra)	Embedding drift when the model is retrained requires re-indexing the entire corpus	Semantic similarity search (find visually related but not literally duplicate images), not exact near-duplicate detection
Single global hash table, no banding	Fast for exact fingerprint match only	Low	Catches only exact fingerprint collisions, not near-duplicates with any bit-level drift	A cheap first-pass filter layered in front of a real near-duplicate system, not a replacement for one

For pure duplicate detection at Pinterest’s scale, bit-partitioned LSH over perceptual hashes is the right call: it gives a provable recall guarantee at a tunable distance threshold, keeps the index small enough to live in memory across shards, and keeps per-query cost bounded regardless of corpus size. CNN embeddings and approximate nearest neighbor search solve a related but different problem, finding images that are semantically or visually related rather than the same photo re-encoded, and would be the right foundation for a visual search product built on top of this system, not for the dedup layer itself. Mixing the two into one system would mean paying GPU inference costs on every single upload just to answer a question a 64-bit hash already answers in microseconds.

Key Takeaways

• Perceptual hashing trades exactness for graceful degradation: dHash and pHash are designed so visually similar images land close together in hash space, which is the opposite property of a cryptographic hash and exactly what near-duplicate detection needs.
• Bit-partitioned LSH gives a provable recall guarantee, not a probabilistic one: splitting a 64-bit fingerprint into k + 1 blocks guarantees catching any pair within Hamming distance k, by the pigeonhole principle, rather than relying on a collision-probability curve.
• A single block match is weak evidence, not a decision: every LSH candidate still needs full 64-bit Hamming verification with dual-hash agreement before being treated as a true duplicate.
• Threshold tuning is a calibration exercise against labeled data, not a constant: the operating threshold is chosen by sweeping precision/recall on a labeled dataset and re-validated whenever the hash algorithm or corpus composition changes.
• Degenerate low-entropy images need a different code path entirely: nearly-blank images collide with huge numbers of unrelated images by chance, and capping bucket scans plus routing them through a stricter threshold is what keeps them from overwhelming the index.
• Reference counting decouples the fast ingest path from the slow reclamation path: neither needs to coordinate with the other because merges only ever transfer references and deletion only happens once a count is provably and durably zero.
• The ingest path and the reclamation pipeline solve different problems on purpose: one is a fast, approximate, fail-open check; the other is a slow, thorough, offline sweep, and trying to make either one do the other’s job breaks the latency or the thoroughness guarantee.
• Sharding by fingerprint prefix, not by image ID, keeps lookups local: a query only ever touches the one shard whose prefix range matches its fingerprint, independent of how many total shards exist.

The counter-intuitive lesson is that the hard part of this system is not detecting that two images look alike, that is a well-studied hashing problem. The hard part is deciding, with a measured and monitored precision bar, when “looks alike” is confident enough to justify making a user’s upload silently disappear behind someone else’s pin. Every architectural decision here, from running two independent hash signals to keeping the auto-merge threshold deliberately conservative to delaying blob deletion behind a grace period, exists to make that one irreversible decision safe to make automatically, billions of times a day.

Frequently Asked Questions

Q: Why not just use a cryptographic hash like SHA-256 and accept that recompressed or cropped duplicates get missed?

A: Because that misses the overwhelming majority of real-world duplicates on a platform like Pinterest. Users constantly resave images from other sites, and even a lossless recompression at a different JPEG quality changes every byte on disk while leaving the image visually identical. An exact hash would only catch a small slice of true duplicates, undermining the entire storage-savings case for building this system in the first place.

Q: Why not use a CNN embedding and approximate nearest neighbor search (FAISS or HNSW) instead of perceptual hashing and LSH?

A: Embeddings are the right tool for semantic similarity, finding images that are related in subject or style, and that is a different, harder problem than detecting the same photo re-encoded. For pure near-duplicate detection, a 64-bit perceptual hash is orders of magnitude cheaper to compute than a neural network forward pass, requires no GPU fleet, and needs no re-indexing when a model gets retrained, since the hash algorithm itself does not drift the way a learned embedding space does after retraining. We would reach for embeddings if the goal were visual search, not deduplication.

Q: How do you avoid false merges when two genuinely different images happen to share a fingerprint block?

A: A single block match from the LSH index is treated as a hint, never a decision. Every candidate goes through full 64-bit Hamming distance verification on both dHash and pHash, requiring both signals to agree within a threshold calibrated against a labeled dataset to a precision bar of roughly one false merge per ten million comparisons. The threshold is deliberately conservative because a wrongful merge is a much more expensive mistake than a missed duplicate.

Q: Why run two separate perceptual hashes (dHash and pHash) instead of just one?

A: Each hash has different failure modes. dHash is cheap and robust to recompression and small crops but more fragile to rotation and color shifts; pHash operates in the frequency domain and handles color and contrast changes better at higher compute cost. Requiring both to agree during verification catches cases where one signal alone would produce a false positive, and it is the mechanism that makes single-block LSH collisions safe to treat as candidates rather than confirmed matches.

Q: Why does the ingest-time check fail open instead of blocking the upload when the index is unavailable?

A: Availability of the pin creation flow matters far more than catching every possible duplicate in real time. Blocking uploads on an index outage would turn a storage-optimization system into a product-availability risk, which is a bad trade. Failing open means a small number of duplicates get stored as new images during an outage window, and the offline reclamation pipeline catches and merges them later, at no cost to the user-facing upload experience.

Q: How would you extend this design to work across multiple regions without a single global index becoming a bottleneck?

A: Each region would run its own authoritative index and hash service, and the ingest-time check would only compare against images already visible in that region, accepting that a duplicate uploaded near-simultaneously in two regions might briefly exist as two canonical images. A cross-region reconciliation pass, similar in spirit to the reclamation pipeline but comparing across regional indexes on a longer cadence, would catch and merge those rarer cross-region duplicates asynchronously, trading a small amount of eventual redundancy for avoiding a synchronous cross-region round trip on every upload.

Interview Questions

Q: Design the fingerprint indexing scheme for a near-duplicate detection system that needs to guarantee catching any pair of images within a given similarity distance, not just probably catch them. How would you approach this?

Expected depth: Discuss why probabilistic LSH schemes (random projection, MinHash) only give a collision probability rather than a guarantee, and how bit-partitioning a fixed-width fingerprint into k + 1 blocks provides a deterministic pigeonhole guarantee for Hamming distance k. Cover the tradeoff between block count, block width, and candidate set size, and how to choose k empirically against a labeled dataset rather than arbitrarily.

Q: A user reports that their newly uploaded pin got auto-merged into someone else’s completely unrelated image. Walk through how you would investigate this in a system using perceptual hashing and LSH.

Expected depth: Walk through likely causes in order: a degenerate low-entropy image that wasn’t correctly flagged, a threshold that was recently loosened without adequate revalidation, a bug in the dual-hash agreement check that let a single-signal match through, or a legitimate but surprising near-duplicate (stock photo, template) that the labeled dataset didn’t anticipate. Discuss what telemetry is needed: the exact Hamming distances on both hash signals, the candidate’s low_entropy flag, and the threshold version active at merge time.

Q: How would you re-tune the similarity threshold if the platform started accepting a new content type, such as hand-drawn illustrations, that behaves very differently under perceptual hashing than photographs?

Expected depth: Discuss why a single global threshold calibrated on photographs may not transfer to illustrations (different entropy distribution, different sensitivity to the DCT-based pHash versus gradient-based dHash), the need for a fresh labeled dataset specific to the new content type, and options like per-content-type thresholds versus a single conservative global threshold. Cover the operational cost of maintaining multiple threshold regimes versus the precision loss of a one-size-fits-all threshold.

Q: The storage reclamation pipeline needs to re-scan a corpus of hundreds of billions of images within a 30-day window without disrupting the ingest path. How would you design that batch job?

Expected depth: Discuss partitioning the batch scan by the same shard prefix scheme as the online index so work can run in parallel per shard, using the same pigeonhole block tables and verifier logic to keep online and offline decisions consistent, and rate-limiting or isolating batch compute from the online serving tier’s resources. Cover how to make merges idempotent and safe to retry, and how the reference-count-plus-grace-period deletion mechanism prevents a batch job bug from destroying live data.

Q: Walk through what happens end-to-end, both in terms of correctness and cost, when a single stock product photo gets uploaded by ten thousand different sellers over a week.

Expected depth: Cover ingest-time behavior (the first upload becomes the canonical image, the remaining 9,999 should each resolve as duplicates and link without storing new blobs), the load pattern on the specific LSH shard that owns that image’s fingerprint prefix (a hot shard scenario), how bucket-size capping and shard-level load-aware placement mitigate that hot spot, and the storage cost difference between correctly deduping all 10,000 uploads versus storing each as a separate 280KB canonical image.