基于Hive QL/Impala/Python的2000万+用户多ID去重求助

Got it, let's tackle this large-scale user ID deduplication problem head-on. Your scenario boils down to grouping all linked IDs (same or different types) into a single unique user identity—this is a classic connected components problem, and the Union-Find (Disjoint Set Union, DSU) data structure is the perfect tool here. It’s efficient enough to handle 20M+ records with near-linear time complexity.

Core Idea #

Every ID (whether ID1, ID2, or ID3) that maps to the same user is part of a single "connected group." Union-Find lets us link these IDs together incrementally, then we can map every ID to a single root identifier that represents the unique user.

Step-by-Step Implementation #

1. Preprocess IDs to Avoid Collisions #

First, you need to prevent conflicts between different ID types. For example, ID1:123 and ID2:123 are distinct IDs but would clash if stored as raw values. Add a type prefix to each ID to make it globally unique:

• ID1 values become ID1:<original_value> (e.g., ID1:1001)
• ID2 values become ID2:<original_value> (e.g., ID2:A002)
• ID3 values become ID3:<original_value> (e.g., ID3:X999)

2. Initialize the Union-Find Structure #

Union-Find relies on two key mappings:

• parent: Tracks each ID's parent in the set (starts as the ID itself)
• rank: Helps optimize merging by keeping track of tree depth (starts at 1 for all IDs)

Here’s a practical Python implementation optimized for speed:

class UnionFind:
    def __init__(self):
        self.parent = {}
        self.rank = {}

    def find(self, x):
        # Path compression: Flatten the tree to speed up future lookups
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        x_root = self.find(x)
        y_root = self.find(y)
        if x_root == y_root:
            return  # Already in the same set
        
        # Union by rank: Attach smaller tree to larger tree's root
        if self.rank[x_root] < self.rank[y_root]:
            self.parent[x_root] = y_root
        else:
            self.parent[y_root] = x_root
            if self.rank[x_root] == self.rank[y_root]:
                self.rank[x_root] += 1

3. Batch Merge Linked IDs #

Process each record by merging all IDs in the record (regardless of type):

• For ID1+ID2 records: Merge every ID1 with every ID2 in the record
• For ID2+ID3 records: Merge every ID2 with every ID3 in the record
• If a record has multiple same-type IDs (e.g., two ID1s), merge those too—they belong to the same user

Example code for processing a single record:

uf = UnionFind()

# Sample record: ID1:1001, ID2:A002
id1 = "ID1:1001"
id2 = "ID2:A002"

# Add IDs to the structure if they don't exist
for id_val in [id1, id2]:
    if id_val not in uf.parent:
        uf.parent[id_val] = id_val
        uf.rank[id_val] = 1

# Merge the two IDs
uf.union(id1, id2)

4. Generate Final User Mappings #

Once all merges are done, you can create two useful mappings:

1. ID-to-Unique-User: Map every prefixed ID to its root ID (or a simplified user ID like USER_00001)
2. User-to-All-IDs: Map each unique user to the full list of linked IDs (great for auditing or downstream systems)

5. Optimization Tips for 20M+ Records #

• Memory Efficiency: If using Python, consider using collections.defaultdict or switch to a compiled language like Go/Java—they handle large dictionaries more efficiently.
• Batch Processing: If your data is too big to load into memory at once, process it in chunks. The Union-Find structure can handle incremental merges just fine.
• Pre-Deduplicate Records: Remove duplicate ID combinations first (e.g., if you have 1000 records with the same ID1+ID2 pair, you only need to merge once).

Key Note for Your Scenario #

Since ID1 and ID3 never come in the same record, they’ll still be linked through shared ID2s—exactly what you need. For example, if ID1:1001 links to ID2:A002, and ID2:A002 links to ID3:X999, all three will end up in the same user group automatically.

内容的提问来源于stack exchange，提问作者Hugo P.