Introduction

With 1 TB of data and only 512 MB of RAM, duplicate detection is no longer an in-memory hash-table problem. It becomes an external-memory problem. The practical answer is to reorganize the data on disk so duplicates become adjacent or at least land in the same small working set.

Use an External Algorithm, Not a Giant Hash Set

A rough estimate shows why naive approaches fail. If each record is around 1 KB, then 1 TB contains roughly one billion records. Even storing short fingerprints for that many records would exceed 512 MB once you include hash-table overhead.

The two standard exact solutions are:

• external sort, then scan adjacent records
• hash partitioning, then deduplicate bucket by bucket

Both are valid. If you truly have "infinite disk space," external sort is often the simplest exact method because it avoids hash-collision reasoning.

External Sort in Two Phases

External sort works like this:

1. read as many records as fit comfortably in memory
2. sort that chunk in RAM
3. write the sorted chunk back to disk as a run file
4. repeat until the full dataset has been split into sorted runs
5. merge the runs and detect duplicates by comparing neighboring records

If two records are identical, they become adjacent in the fully merged sorted order. That turns deduplication into a simple linear scan.

Phase 1: Write Sorted Runs

The example below assumes newline-delimited records and uses a conservative chunk size.

1from pathlib import Path
2
3CHUNK_SIZE = 100_000
4RUN_DIR = Path("runs")
5RUN_DIR.mkdir(exist_ok=True)
6
7
8def write_sorted_runs(source_path):
9    chunk = []
10    run_index = 0
11
12    with open(source_path, "rb") as source:
13        for line in source:
14            chunk.append(line)
15            if len(chunk) == CHUNK_SIZE:
16                chunk.sort()
17                with open(RUN_DIR / f"run_{run_index:04d}.bin", "wb") as out:
18                    out.writelines(chunk)
19                chunk.clear()
20                run_index += 1
21
22        if chunk:
23            chunk.sort()
24            with open(RUN_DIR / f"run_{run_index:04d}.bin", "wb") as out:
25                out.writelines(chunk)
26
27
28write_sorted_runs("records.txt")

CHUNK_SIZE is only an example. In practice, you size the chunk based on record structure, Python overhead, and safety margin.

Phase 2: Merge and Detect Duplicates

Once the runs are sorted, perform a k-way merge and compare each record with the previous one.

1import heapq
2from pathlib import Path
3
4
5def merged_lines(paths):
6    files = [open(path, "rb") for path in paths]
7    try:
8        for line in heapq.merge(*files):
9            yield line
10    finally:
11        for f in files:
12            f.close()
13
14
15def write_duplicates(run_dir, output_path):
16    previous = None
17
18    with open(output_path, "wb") as out:
19        for line in merged_lines(sorted(Path(run_dir).glob("run_*.bin"))):
20            if line == previous:
21                out.write(line)
22            previous = line
23
24
25write_duplicates("runs", "duplicates.txt")

This is exact duplicate detection. No fingerprint collisions can create false matches because the final comparison uses the full record.

When Hash Partitioning Is Better

Hash partitioning is another good design when external sort tooling is inconvenient or when you want easy parallelism. You stream the data once, hash each full record, write it into a bucket file, and then deduplicate each bucket independently in memory.

That works because identical records produce the same hash and therefore land in the same bucket. The downside is operational rather than theoretical: badly chosen bucket counts can create skew, and if you trust fingerprints without comparing full records, collisions can produce incorrect results.

Practical Engineering Concerns

At this scale, disk behavior matters almost as much as the algorithm:

• prefer large sequential reads and writes
• compress runs only if CPU is cheaper than I/O
• keep temporary files on fast local storage when possible
• record a checksum or row count per run so crashes are easier to recover from

Also decide what "duplicate" means before writing code. Is it byte-for-byte identity, or equality after trimming whitespace, normalizing case, or parsing structured fields? The answer changes the pipeline.

Common Pitfalls

• Trying to hold all hashes or records in RAM anyway and hoping the estimate works out.
• Deduplicating by hash alone instead of verifying full-record equality.
• Choosing a chunk size with no margin for language and container overhead.
• Ignoring whether records are fixed-width, delimited, or length-prefixed.
• Forgetting crash recovery and temporary-file management for long-running jobs.

Summary

• With 1 TB of data and 512 MB RAM, you need an external-memory algorithm.
• External sort is a clean exact solution: sort runs on disk, merge them, and compare adjacent records.
• Hash partitioning is another exact option if you still verify full records inside each bucket.
• Disk layout, streaming behavior, and crash recovery matter at this scale.
• Define duplicate semantics clearly before you choose the pipeline.