100 triệu URL loại bỏ trùng lặp, làm sao để không crash? Phân tích toàn diện giải pháp cấp sản xuất (từ cơ bản đến thực chiến tại các công ty lớn)

Tại phát triển backend, việc "loại bỏ trùng lặp URL" là một tình huống thường gặp và đầy thách thức - với lượng dữ liệu nhỏ (vài nghìn, vài chục nghìn), việc dùng tập hợp thông thường là đủ, nhưng khi dữ liệu vượt quá 100 triệu, các phương pháp thông thường sẽ gặp phải các vấn đề như "tràn bộ nhớ, thời gian xử lý quá lâu, ổ đĩa đầy".

Các ứng dụng phổ biến: loại bỏ URL trùng lặp trong quá trình bò web (tránh truy cập lại), thống kê URL độc lập trong hệ thống nhật ký, loại bỏ URL trùng lặp trong nền tảng liên kết ngắn (tránh tạo liên kết ngắn trùng lặp), làm sạch URL trong nền tảng dữ liệu lớn, v.v.

Bài viết này không nói chuyện phiếm, tập trung hoàn toàn vào "lõi vấn đề loại bỏ trùng lặp 100 triệu URL", từ "so sánh phương pháp, triển khai thực tế, kỹ thuật tối ưu, mở rộng phỏng vấn" bốn góc độ, giải thích rõ ràng phương pháp tối ưu nhất trong môi trường sản xuất thật tại các công ty lớn. Dù là phát triển hàng ngày hay chuẩn bị phỏng vấn, đều có thể áp dụng trực tiếp.

Một, xác định rõ các điểm cốt lõi (điểm khó của 100 triệu URL ở đâu?)

Hiểu rõ điểm cốt lõi mới có thể tránh nỗ lực vô ích. Loại bỏ trùng lặp 100 triệu URL, vấn đề lớn nhất không phải là "loại bỏ trùng lặp" mà là "hạn chế tài nguyên do lượng dữ liệu lớn", chủ yếu có 3 điểm cốt lõi:

1.1 Hạn chế về bộ nhớ

Chiều dài của một URL thông thường khoảng 50~200 byte, tính trung bình 100 byte, kích thước tổng cộng của 100 triệu URL khoảng: 10 tỷ byte = 9,3GB.

Nếu dùng phương pháp thông thường "tập hợp bộ nhớ" (như HashSet trong Java, set trong Python) để loại bỏ trùng lặp, sẽ thấy rằng: tập hợp lưu trữ không chỉ URL mà còn bao gồm giá trị băm, con trỏ, v.v., tiêu thụ bộ nhớ thực tế đạt 2~~3 lần kích thước ban đầu (khoảng 18~~28GB), máy chủ thông thường (16GB bộ nhớ) sẽ trực tiếp tràn bộ nhớ (OOM).

1.2 Hạn chế về thời gian

Lõi của việc loại bỏ trùng lặp là "xác định URL có tồn tại hay không", hiệu suất truy vấn của phương pháp thông thường sẽ giảm nhanh theo lượng dữ liệu tăng:

Truy vấn tuyến tính (như mảng): độ phức tạp thời gian O(n), 100 triệu dữ liệu cần duyệt 100 triệu lần, tiêu tốn thời gian theo giờ tính;
Bảng băm thông thường: mặc dù có thể đạt được O(1) truy vấn, nhưng xung đột băm của 100 triệu dữ liệu sẽ tăng nhanh, hiệu suất truy vấn thực tế giảm hơn 50%, và khi chèn cần mở rộng thường xuyên, thời gian tăng gấp đôi.

1.3 Hạn chế về đĩa

Nếu từ bỏ bộ nhớ, trực tiếp dùng đĩa để lưu trữ (như cơ sở dữ liệu, tệp) để loại bỏ trùng lặp, sẽ đối mặt với vấn đề "IO thường xuyên": mỗi lần xác định URL có tồn tại hay không, đều cần đọc đĩa, 100 triệu lần IO, thời gian sẽ đạt hàng giờ hoặc thậm chí hàng ngày, hoàn toàn không thể đáp ứng nhu cầu sản xuất.

1.4 Các hạn chế bổ sung

Trong môi trường sản xuất, ngoài hiệu suất, còn có các yêu cầu bổ sung: độ chính xác loại bỏ trùng lặp (có cho phép sai sót hay không), tính thời gian thực (là loại bỏ trùng lặp offline hay thời gian thực), sử dụng tài nguyên (có thể chạy trên máy chủ thông thường hay không). Các tình huống khác nhau, phương án tối ưu hoàn toàn khác nhau.

Hai, so sánh 5 phương pháp loại bỏ trùng lặp (từ cơ bản đến công ty lớn, chọn theo nhu cầu)

Đối với việc loại bỏ trùng lặp 100 triệu URL, tôi đã tổng hợp 5 phương pháp phổ biến, phân cấp theo "cơ bản, trung cấp, cấp sản xuất" để so sánh, xác định rõ ràng các ưu điểm, nhược điểm và chi phí tài nguyên của mỗi phương pháp, giúp bạn chọn loại hình nhanh chóng.

Phương pháp	Nguyên lý cốt lõi	Tiêu thụ bộ nhớ	Thời gian (100 triệu)	Độ chính xác	Ứng dụng	Độ khó thực hiện
1\. Tập hợp băm (HashSet/set)	URL được băm và lưu vào tập hợp, xác định có tồn tại hay không	18~28GB (bắt buộc OOM)	≥2 giờ (mở rộng tốn thời gian lâu)	100% (không có sai sót)	≤10 triệu, lượng dữ liệu nhỏ	Rất thấp
2\. Bộ lọc Bloom (Bloom Filter)	Nhiều hàm băm ánh xạ đến biểu đồ bit, xác định có tồn tại hay không	≤1GB (có thể điều chỉnh)	≤30 phút	99%+ (có thể chịu sai sót)	100 triệu+, cho phép sai sót nhỏ (bò web, nhật ký)	Trung bình
3\. Phân vùng đĩa + băm (loại bỏ theo đoạn)	URL được băm và phân vùng lưu vào đĩa, loại bỏ từng vùng trong bộ nhớ	≤2GB	1~2 giờ	100% (không có sai sót)	100 triệu, không giới hạn bộ nhớ máy chủ, cần loại bỏ chính xác	Trung bình
4\. Loại bỏ phân tán (Redis Cluster)	URL được băm và phân mảnh lưu vào cụm Redis, dùng Set để loại bỏ trùng lặp	Bộ nhớ cụm ≥20GB	≤1 giờ (tần suất cao)	100% (không có sai sót)	100 triệu+, loại bỏ thời gian thực (liên kết ngắn, giao diện)	Cao
5\. Khung dữ liệu lớn (Hadoop/Spark)	MapReduce/Spark RDD, loại bỏ phân mảnh phân tán	Phân tán trên các nút, mỗi nút ≤1GB	≤40 phút (cụm)	100% (không có sai sót)	1 tỷ+, loại bỏ lượng lớn offline (nền tảng dữ liệu lớn)	Rất cao

Kết luận cốt lõi: loại bỏ trùng lặp 100 triệu URL, "Bộ lọc Bloom" và "phân vùng đĩa + băm" là hai phương pháp phổ biến nhất trong môi trường sản xuất - phương pháp trước phù hợp với các tình huống cho phép sai sót, theo đuổi hiệu suất cao; phương pháp sau phù hợp với các tình huống cần loại bỏ chính xác, không có tài nguyên cụm; phương pháp phân tán phù hợp với loại bỏ thời gian thực, khung dữ liệu lớn phù hợp với dữ liệu quy mô cực lớn.

Ba, phương án thực tế cấp sản xuất (tập trung triển khai 2 phương pháp phổ biến nhất)

Dưới đây sẽ giải thích chi tiết hai phương pháp "Bộ lọc Bloom" và "phân vùng đĩa + băm" trong thực tế triển khai, bao gồm ví dụ mã, tối ưu tham số, kỹ thuật tránh bẫy, có thể chạy trên máy chủ thông thường, tái sử dụng trực tiếp.

Phương án 1: Bộ lọc Bloom (khuyến nghị, lựa chọn hàng đầu cho 100 triệu, hiệu suất tối ưu nhất)

Bộ lọc Bloom là "kết cấu dữ liệu xác suất có hiệu quả không gian cực cao", ưu điểm cốt lõi là "sử dụng bộ nhớ cực nhỏ để thực hiện xác định sự tồn tại hiệu quả", phù hợp với loại bỏ trùng lặp 100 triệu URL (cho phép sai sót dưới 0.1%).

3.1.1 Nguyên lý cốt lõi (hiểu đơn giản)

Khởi tạo một "biểu đồ bit" có kích thước cố định (mảng nhị phân, mỗi phần tử chỉ có 0 và 1);
Dùng nhiều hàm băm độc lập, đối với mỗi URL thực hiện băm, nhận được nhiều chỉ mục biểu đồ bit;
Thiết lập các vị trí biểu đồ bit tương ứng thành 1;
Xác định URL có tồn tại hay không: đối với URL thực hiện băm lại, nếu tất cả chỉ mục tương ứng đều là 1, có thể tồn tại (có sai sót); nếu có một là 0, chắc chắn không tồn tại.

Điểm quan trọng: tỷ lệ sai sót càng thấp, biểu đồ bit cần càng lớn, số lượng hàm băm càng nhiều; 100 triệu URL, muốn tỷ lệ sai sót ≤0.1%, kích thước biểu đồ bit khoảng 1.2GB, số lượng hàm băm đặt thành 8 là đủ.

3.1.2 Ví dụ mã thực tế (phiên bản Java, dùng công cụ BloomFilter của Google Guava)

Không cần tái tạo bánh xe, trực tiếp sử dụng công cụ BloomFilter của Google Guava, đơn giản dễ dùng, hiệu suất ổn định.

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class UrlBloomFilterDemo {
    // 100 triệu URL
    private static final long URL_COUNT = 100_000_000L;
    // Tỷ lệ sai sót (0.1%)
    private static final double FALSE_POSITIVE_RATE = 0.001;

    public static void main(String[] args) {
        // 1. Khởi tạo bộ lọc Bloom (tham số: kiểu phần tử, số lượng phần tử, tỷ lệ sai sót)
        BloomFilter<CharSequence> bloomFilter = BloomFilter.create(
                Funnels.stringFunnel(StandardCharsets.UTF_8),
                URL_COUNT,
                FALSE_POSITIVE_RATE
        );

        // 2. Mô phỏng 100 triệu URL, lưu vào bộ lọc Bloom (trong thực tế đọc từ tệp/cơ sở dữ liệu)
        List<String> urlList = generateUrlList(URL_COUNT);
        long startTime = System.currentTimeMillis();
        for (String url : urlList) {
            bloomFilter.put(url);
        }
        System.out.println("100 triệu URL lưu vào bộ lọc Bloom tiêu tốn thời gian: " + (System.currentTimeMillis() - startTime) / 1000 + " giây");

        // 3. Mô phỏng xác định trùng lặp (xác định URL có tồn tại hay không)
        String testUrl1 = "https://www.example.com/123"; // Có tồn tại
        String testUrl2 = "https://www.example.com/456"; // Không tồn tại
        System.out.println("testUrl1 có tồn tại: " + bloomFilter.mightContain(testUrl1)); // true
        System.out.println("testUrl2 có tồn tại: " + bloomFilter.mightContain(testUrl2)); // false

        // 4. Thống kê tỷ lệ sai sót (tùy chọn)
        long falseCount = 0;
        List<String> newUrlList = generateNewUrlList(100_000L); // 100 nghìn URL mới
        for (String url : newUrlList) {
            if (bloomFilter.mightContain(url)) {
                falseCount++;
            }
        }
        System.out.println("Tỷ lệ sai sót thực tế: " + (double) falseCount / 100_000);
    }

    // Mô phỏng tạo 100 triệu URL ngẫu nhiên
    private static List<String> generateUrlList(long count) {
        List<String> urlList = new ArrayList<>();
        Random random = new Random();
        for (long i = 0; i < count; i++) {
            String url = "https://www.example.com/" + random.nextInt(100_000_000);
            urlList.add(url);
        }
        return urlList;
    }

    // Mô phỏng tạo 100 nghìn URL mới (chưa lưu vào bộ lọc Bloom)
    private static List<String> generateNewUrlList(long count) {
        List<String> urlList = new ArrayList<>();
        Random random = new Random();
        for (long i = 0; i < count; i++) {
            String url = "https://www.new-example.com/" + random.nextInt(100_000_000);
            urlList.add(url);
        }
        return urlList;
    }
}

3.1.3 Kỹ thuật tối ưu (phải làm trong môi trường sản xuất)

Tối ưu tham số: tỷ lệ sai sót đặt thành 0.001~~0.01 (cân bằng giữa bộ nhớ và độ chính xác), 100 triệu URL tương ứng kích thước biểu đồ bit 1~~1.5GB, số lượng hàm băm 8~10;
Tối ưu bộ nhớ: nếu bộ nhớ máy chủ không đủ (như 8GB), có thể сериализ bộ lọc Bloom ra đĩa, sử dụng khi tải vào bộ nhớ (Guava hỗ trợ seriализ);
Xử lý sai sót: nếu kinh doanh không cho phép sai sót, sau khi bộ lọc Bloom xác định là "tồn tại", hãy kiểm tra lại trên đĩa/cơ sở dữ liệu (đảm bảo kép);
Xử lý theo lô: đọc URL, lưu vào bộ lọc Bloom theo lô (như mỗi lần 1000 cái), giảm chi phí vòng lặp, nâng cao hiệu suất.

3.1.4 Điểm cần tránh bẫy

Bộ lọc Bloom "chỉ có thể xác định tồn tại, không thể xóa": nếu URL cần xóa động (như bò web loại bỏ sau đó cần xóa liên kết hết hạn), cần dùng "Bộ lọc Bloom đếm" (Counting Bloom Filter);
Chọn hàm băm: dùng hàm băm độc lập (như MurmurHash, MD5), tránh xung đột băm tập trung;
Tránh lưu trữ vượt quá: nếu số lượng URL lưu trữ vượt xa số lượng ban đầu, tỷ lệ sai sót sẽ tăng đột biến (khuyến nghị dự trữ 20% số lượng ban đầu).

Phương án 2: Phân vùng đĩa + băm (loại bỏ chính xác, không giới hạn bộ nhớ)

Nếu kinh doanh không cho phép bất kỳ sai sót nào (như loại bỏ liên kết ngắn, nhật ký tài chính), và không có tài nguyên cụm, "phân vùng đĩa + băm" là lựa chọn tối ưu nhất - cốt lõi là "chia để trị", chia 100 triệu URL thành nhiều tệp nhỏ (phân vùng), loại bỏ từng phân vùng trong bộ nhớ, tránh OOM.

3.2.1 Quy trình cốt lõi (hiểu đơn giản)

Phân vùng: đối với mỗi URL thực hiện băm, nhận được một giá trị băm, theo giá trị băm phân phối URL đến các tệp đĩa khác nhau (như 100 phân vùng, tên tệp là 0~99.txt);
Loại bỏ từng phân vùng: đọc từng tệp phân vùng vào bộ nhớ (dùng HashSet để loại bỏ trùng lặp), sau đó ghi vào tệp loại bỏ mới;
Kết hợp kết quả: kết hợp tất cả các tệp loại bỏ phân vùng, nhận được danh sách URL loại bỏ cuối cùng.

Điểm quan trọng: số lượng phân vùng càng nhiều, số lượng URL trong từng phân vùng càng ít, tiêu thụ bộ nhớ càng thấp; 100 triệu URL, chia thành 100 phân vùng, mỗi phân vùng khoảng 1 triệu URL, tiêu thụ bộ nhớ ≤2GB, máy chủ thông thường hoàn toàn chịu được.

3.2.2 Ví dụ mã thực tế (phiên bản Java, quy trình cốt lõi)

import java.io.*;
import java.nio.charset.StandardCharsets;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;

public class UrlBucketDeduplicationDemo {
    // 100 triệu URL
    private static final long URL_COUNT = 100_000_000L;
    // Số lượng phân vùng (100 phân vùng, có thể điều chỉnh)
    private static final int BUCKET_COUNT = 100;
    // Đường dẫn tệp phân vùng tạm thời
    private static final String BUCKET_DIR = "D:/url_bucket/";
    // Đường dẫn tệp loại bỏ cuối cùng
    private static final String FINAL_URL_FILE = "D:/url_deduplication_final.txt";

    public static void main(String[] args) throws IOException {
        // 1. Khởi tạo thư mục phân vùng
        File bucketDir = new File(BUCKET_DIR);
        if (!bucketDir.exists()) {
            bucketDir.mkdirs();
        }

        // 2. Tạo 100 triệu URL và phân vùng ghi vào đĩa (trong thực tế đọc từ tệp/cơ sở dữ liệu)
        long startTime = System.currentTimeMillis();
        splitIntoBuckets();
        System.out.println("Phân vùng hoàn tất, tiêu tốn thời gian: " + (System.currentTimeMillis() - startTime) / 1000 + " giây");

        // 3. Loại bỏ từng phân vùng
        deduplicateEachBucket();
        System.out.println("Loại bỏ từng phân vùng hoàn tất, tiêu tốn thời gian: " + (System.currentTimeMillis() - startTime) / 1000 + " giây");

        // 4. Kết hợp tất cả các tệp loại bỏ phân vùng
        mergeBuckets();
        System.out.println("Kết hợp hoàn tất, tổng thời gian tiêu tốn: " + (System.currentTimeMillis() - startTime) / 1000 + " giây");
    }

    // Bước 1: Phân vùng URL ghi vào đĩa
    private static void splitIntoBuckets() throws IOException {
        // Khởi tạo 100 luồng ghi tệp phân vùng
        BufferedWriter[] bucketWriters = new BufferedWriter[BUCKET_COUNT];
        for (int i = 0; i < BUCKET_COUNT; i++) {
            bucketWriters[i] = new BufferedWriter(
                    new OutputStreamWriter(
                            new FileOutputStream(BUCKET_DIR + i + ".txt"),
                            StandardCharsets.UTF_8
                    )
            );
        }

        // Tạo URL và phân vùng ghi
        Random random = new Random();
        for (long i = 0; i < URL_COUNT; i++) {
            String url = "https://www.example.com/" + random.nextInt(100_000_000);
            // Băm phân vùng: giá trị băm URL lấy mô, nhận được chỉ mục phân vùng
            int bucketIndex = Math.abs(url.hashCode()) % BUCKET_COUNT;
            bucketWriters[bucketIndex].write(url);
            bucketWriters[bucketIndex].newLine();
        }

        // Đóng tất cả luồng ghi
        for (BufferedWriter writer : bucketWriters) {
            writer.close();
        }
    }

    // Bước 2: Loại bỏ từng phân vùng (đọc tệp phân vùng, loại bỏ trong bộ nhớ sau đó ghi vào tệp mới)
    private static void deduplicateEachBucket() throws IOException {
        for (int i = 0; i < BUCKET_COUNT; i++) {
            File bucketFile = new File(BUCKET_DIR + i + ".txt");
            File deduplicatedFile = new File(BUCKET_DIR + i + "_deduplicated.txt");

            // Đọc tệp phân vùng, loại bỏ trong bộ nhớ
            Set<String> urlSet = new HashSet<>();
            BufferedReader reader = new BufferedReader(
                    new InputStreamReader(
                            new FileInputStream(bucketFile),
                            StandardCharsets.UTF_8
                    )
            );
            String url;
            while ((url = reader.readLine()) != null) {
                urlSet.add(url);
            }
            reader.close();

            // Ghi URL loại bỏ vào tệp mới
            BufferedWriter writer = new BufferedWriter(
                    new OutputStreamWriter(
                            new FileOutputStream(deduplicatedFile),
                            StandardCharsets.UTF_8
                    )
            );
            for (String uniqueUrl : urlSet) {
                writer.write(uniqueUrl);
                writer.newLine();
            }
            writer.close();

            // Xóa tệp phân vùng ban đầu (tiết kiệm không gian đĩa)
            bucketFile.delete();
        }
    }

    // Bước 3: Kết hợp tất cả các tệp loại bỏ phân vùng
    private static void mergeBuckets() throws IOException {
        BufferedWriter finalWriter = new BufferedWriter(
                new OutputStreamWriter(
                        new FileOutputStream(FINAL_URL_FILE),
                        StandardCharsets.UTF_8
                )
        );

        for (int i = 0; i < BUCKET_COUNT; i++) {
            File deduplicatedFile = new File(BUCKET_DIR + i + "_deduplicated.txt");
            BufferedReader reader = new BufferedReader(
                    new InputStreamReader(
                            new FileInputStream(deduplicatedFile),
                            StandardCharsets.UTF_8
                    )
            );
            String url;
            while ((url = reader.readLine()) != null) {
                finalWriter.write(url);
                finalWriter.newLine();
            }
            reader.close();
            // Xóa tệp loại bỏ phân vùng (tiết kiệm không gian đĩa)
            deduplicatedFile.delete();
        }

        finalWriter.close();
    }
}

3.2.3 Kỹ thuật tối ưu (phải làm trong môi trường sản xuất)

Tối ưu số lượng phân vùng: điều chỉnh theo bộ nhớ máy chủ, 16GB bộ nhớ chia thành 100 phân vùng, 8GB bộ nhớ chia thành 200 phân vùng, đảm bảo số lượng URL trong từng phân vùng đọc vào bộ nhớ không OOM;
Tối ưu IO: dùng luồng đệm (BufferedReader/BufferedWriter), giảm số lần IO đĩa; đọc/ghi theo lô (như mỗi lần 1000 cái), nâng cao hiệu suất IO;
Tối ưu đĩa: chọn đĩa IO nhanh (như SSD), tránh cổng xoay; tệp phân vùng tạm thời và tệp cuối cùng lưu trữ ở đĩa khác, giảm cạnh tranh IO;
Tối ưu song song: xử lý song song nhiều phân vùng (như mở 10 luồng, xử lý đồng thời 10 phân vùng loại bỏ), thời gian tiêu tốn có thể giảm hơn 50%;
Tối ưu không gian: sau khi loại bỏ, xóa ngay tệp phân vùng ban đầu, tránh đầy đĩa (100 triệu URL loại bỏ, nếu tỷ lệ trùng lặp 30%, tệp cuối cùng khoảng 6.5GB).

3.2.4 Điểm cần tránh bẫy

Xung đột băm: giá trị băm của URL khác nhau có thể giống nhau, dẫn đến phân vào cùng một phân vùng, hiện tượng này bình thường, không ảnh hưởng đến kết quả loại bỏ (cuối cùng mỗi phân vùng dùng HashSet để loại bỏ);
Mã hóa tệp: dùng UTF-8 thống nhất, tránh URL tiếng Trung bị lỗi mã hóa, dẫn đến loại bỏ thất bại;
Xử lý ngoại lệ: thêm bắt lỗi đọc/ghi tệp, tránh xử lý một phân vùng thất bại khiến toàn bộ quy trình loại bỏ bị gián đoạn;
Tỷ lệ trùng lặp cao: nếu tỷ lệ trùng lặp URL rất cao (≥50%), có thể thực hiện một lần loại bỏ thô trước (như bộ lọc Bloom), sau đó phân vùng, giảm áp lực IO đĩa.

Bốn, phương án nâng cao: loại bỏ phân tán (tình huống loại bỏ thời gian thực)

Nếu kinh doanh cần "loại bỏ thời gian thực" (như nền tảng liên kết ngắn, người dùng nộp URL sau đó ngay lập tức xác định có tồn tại hay không), và lượng dữ liệu tăng trưởng liên tục, cần dùng "phương án loại bỏ phân tán", cốt lõi là Redis Cluster (cụm Redis).

4.1 Nguyên lý cốt lõi

Phân mảnh cụm Redis: thực hiện băm URL, theo giá trị băm phân phối đến các nút Redis khác nhau (phân mảnh), thực hiện cân bằng tải;
Redis Set loại bỏ trùng lặp: mỗi nút Redis dùng Set dữ liệu để lưu trữ URL, đặc tính của Set là "phần tử duy nhất", tự nhiên hỗ trợ loại bỏ trùng lặp;
Xác định thời gian thực: sau khi người dùng nộp URL, băm nhận được nút, truy vấn Set của nút có chứa URL hay không, tồn tại thì trả về trùng lặp, không tồn tại thì thêm vào Set.

4.2 Điểm cốt lõi thực tế

Cấu hình cụm: Redis Cluster ít nhất 3 nút chính, 3 nút phụ, bộ nhớ tổng ≥20GB (100 triệu URL, mỗi URL 100 byte, Set lưu trữ khoảng 20GB);
Phân mảnh băm: dùng phân mảnh băm nhất quán của Redis, tránh khi nút mở rộng/tắt nguồn, lượng lớn URL được phân mảnh lại;
Chiến lược hết hạn: nếu URL có thời gian hết hạn (như liên kết bò), đặt thời gian hết hạn cho phần tử trong Set (EXPIRE), tránh bộ nhớ Redis tràn;
Tính sẵn sàng cao: mở kích hoạt lưu trữ của Redis (RDB + AOF), tránh mất dữ liệu loại bỏ khi nút宕 cơ;
Ví dụ mã: dùng RedisTemplate thao tác Redis Cluster, gọi opsForSet().add() và opsForSet().isMember() là được.

Năm, các câu hỏi phỏng vấn nâng cao (điểm cộng)

"Loại bỏ trùng lặp 100 triệu URL" là câu hỏi phỏng vấn thường gặp trong phần hậu-end, dữ liệu lớn của các công ty lớn, ngoài các phương án cơ bản, giám khảo chú trọng hơn sự hiểu biết của bạn về chi tiết, tối ưu và thích ứng với tình huống, dưới đây là các câu hỏi phỏng vấn thường gặp và câu trả lời tiêu chuẩn:

Câu hỏi phỏng vấn 1: Tại sao không dùng HashSet để loại bỏ trùng lặp 100 triệu URL?

Câu trả lời tiêu chuẩn:

Hạn chế bộ nhớ: 100 triệu URL trung bình 100 byte, kích thước ban đầu 9.3GB, HashSet lưu trữ cần thêm lưu trữ giá trị băm, con trỏ, v.v., tiêu thụ bộ nhớ thực tế 18~28GB, máy chủ thông thường (16GB) sẽ trực tiếp tràn bộ nhớ (OOM);
Hạn chế hiệu suất: khi chèn 100 triệu dữ liệu vào HashSet, sẽ thường xuyên kích hoạt mở rộng (mỗi lần mở rộng gấp đôi kích thước trước), mở rộng cần lại băm lại tất cả phần tử, tiêu tốn thời gian cực kỳ dài (≥2 giờ);
Ứng dụng: HashSet chỉ phù hợp với loại bỏ dữ liệu nhỏ dưới 10 triệu, 100 triệu dữ liệu hoàn toàn không phù hợp.

Câu hỏi phỏng vấn 2: Tỷ lệ sai sót của Bộ lọc Bloom được kiểm soát như thế nào? Nguyên nhân gây sai sót là gì?

Câu trả lời tiêu chuẩn:

Nguyên nhân sai sót: các URL khác nhau sau khi qua nhiều hàm băm có thể ánh xạ đến cùng một vị trí trong biểu đồ bit (xung đột băm), dẫn đến xác định là "tồn tại";
Kiểm soát tỷ lệ sai sót: điều chỉnh hai tham số để kiểm soát - kích thước biểu đồ bit và số lượng hàm băm;
Kích thước biểu đồ bit càng lớn, tỷ lệ sai sót càng thấp (nhưng tiêu thụ bộ nhớ càng cao);
Số lượng hàm băm càng nhiều, tỷ lệ sai sót càng thấp (nhưng tiêu tốn thời gian băm càng cao, cần cân bằng);
Kinh nghiệm thực tế: 100 triệu URL, tỷ lệ sai sót 0.001, kích thước biểu đồ bit 1.2GB, số lượng hàm băm 8 cái là đủ.

Câu hỏi phỏng vấn 3: Trong loại bỏ trùng lặp phân vùng đĩa + băm, số lượng phân vùng được xác định như thế nào?

Câu trả lời tiêu chuẩn:

Nguyên tắc cốt lõi: số lượng phân vùng = tổng số URL / số lượng tối đa mỗi phân vùng có thể chứa;
Số lượng tối đa mỗi phân vùng có thể chứa: được xác định bởi bộ nhớ máy chủ, giả sử bộ nhớ máy chủ 16GB, dành 10GB cho hệ thống và chương trình khác, phần còn lại 6GB dùng cho mỗi phân vùng loại bỏ, mỗi URL 100 byte, HashSet lưu trữ cần 2 lần không gian, mỗi phân vùng có thể chứa khoảng 3 triệu URL;
Ví dụ tính toán: 100 triệu URL ÷ 3 triệu URL/phân vùng ≈ 34 phân vùng, thực tế lấy 100 phân vùng (dự trữ dư thừa, tránh phân vùng quá lớn);
Kỹ thuật điều chỉnh: bộ nhớ càng nhỏ, số lượng phân vùng càng nhiều; tỷ lệ trùng lặp càng cao, số lượng phân vùng có thể điều chỉnh giảm.

Câu hỏi phỏng vấn 4: Làm thế nào để chọn phương án tối ưu nhất khi loại bỏ trùng lặp 100 triệu URL?

Câu trả lời tiêu chuẩn (theo tình huống):

Cho phép sai sót nhỏ, theo đuổi hiệu suất cao, không có tài nguyên cụm: chọn Bộ lọc Bloom (bộ nhớ ≤1GB, thời gian ≤30 phút);
Không cho phép sai sót, không có tài nguyên cụm, máy chủ thông thường: chọn phân vùng đĩa + băm (bộ nhớ ≤2GB, thời gian 1~2 giờ);
Loại bỏ thời gian thực, tần suất cao, dữ liệu tăng trưởng liên tục: chọn cụm Redis phân tán để loại bỏ (bộ nhớ cụm ≥20GB, thời gian ≤1 giờ);
Dữ liệu ≥1 tỷ, loại bỏ lượng lớn offline: chọn khung dữ liệu lớn Hadoop/Spark (phân tán áp lực trên các nút, thời gian ≤40 phút).

Câu hỏi phỏng vấn 5: Điểm cốt lõi khác biệt giữa Bộ lọc Bloom và phân vùng đĩa + băm là gì?

Câu trả lời tiêu chuẩn:

Độ chính xác: Bộ lọc Bloom là xác suất, có sai sót; phân vùng đĩa + băm là chính xác, không có sai sót;
Tiêu thụ bộ nhớ: Bộ lọc Bloom rất thấp (≤1.5GB); phân vùng đĩa + băm thấp (≤2GB);
Thời gian tiêu tốn: Bộ lọc Bloom nhanh hơn (≤30 phút); phân vùng đĩa + băm chậm hơn một chút (1~2 giờ);
Chức năng: Bộ lọc Bloom không thể xóa phần tử; phân vùng đĩa + băm có thể xóa, sửa phần tử bất kỳ lúc nào;
Ứng dụng: Bộ lọc Bloom phù hợp với loại bỏ offline/thời gian thực cho phép sai sót; phân vùng đĩa + băm phù hợp với loại bỏ chính xác trong tình huống offline.

Sáu, kết luận

Lõi của việc loại bỏ trùng lặp 100 triệu URL không phải là "tìm một phương pháp vạn năng", mà là "theo tình huống kinh doanh, cân bằng giữa bộ nhớ, thời gian, độ chính xác và chi phí tài nguyên". Chúng ta có thể dùng một câu để tóm tắt tất cả logic chọn phương pháp:

Cho phép sai sót chọn Bộ lọc Bloom, loại bỏ chính xác chọn phân vùng, thời gian thực cao chọn Redis, trên 1 tỷ chọn khung dữ liệu lớn.

Các phương pháp được bài viết này giải thích đều là phương pháp tối ưu nhất đã được xác minh trong môi trường sản xuất thật tại các công ty lớn - Bộ lọc Bloom và phân vùng đĩa + băm, không cần tài nguyên cụm, máy chủ thông thường cũng có thể chạy, trực tiếp sử dụng mã để giải quyết vấn đề; phương pháp phân tán và khung dữ liệu lớn, phù hợp với các tình huống quy mô lớn hơn, phức tạp hơn.

Cuối cùng nhắc nhở: bản chất tối ưu hóa loại bỏ là "chia để trị" (phân vùng, phân mảnh) và "tái sử dụng tài nguyên" (bộ nhớ, đĩa, cụm), chỉ cần nắm vững hai lõi này, bất kể lượng dữ liệu lớn đến đâu, đều có thể tìm được phương pháp loại bỏ hiệu quả.

Nếu trong phát triển thực tế gặp phải tình huống đặc biệt (như URL chứa chữ Trung Quốc, cần xóa động, tần suất cao loại bỏ thời gian thực), có thể kết hợp ý tưởng trong bài viết này, điều chỉnh linh hoạt phương pháp - không có phương pháp tối ưu nhất, chỉ có phương pháp phù hợp nhất với kinh doanh.

Thẻ: Bloom Filter URL Deduplication Data Processing Memory Optimization Disk Storage

Đăng vào ngày 20 tháng 5 lúc 08:06

Thành phố Cuồng loạn

100 triệu URL loại bỏ trùng lặp, làm sao để không crash? Phân tích toàn diện giải pháp cấp sản xuất (từ cơ bản đến thực chiến tại các công ty lớn)

Một, xác định rõ các điểm cốt lõi (điểm khó của 100 triệu URL ở đâu?)

1.1 Hạn chế về bộ nhớ

1.2 Hạn chế về thời gian

1.3 Hạn chế về đĩa

1.4 Các hạn chế bổ sung

Hai, so sánh 5 phương pháp loại bỏ trùng lặp (từ cơ bản đến công ty lớn, chọn theo nhu cầu)

Ba, phương án thực tế cấp sản xuất (tập trung triển khai 2 phương pháp phổ biến nhất)

Phương án 1: Bộ lọc Bloom (khuyến nghị, lựa chọn hàng đầu cho 100 triệu, hiệu suất tối ưu nhất)

3.1.1 Nguyên lý cốt lõi (hiểu đơn giản)

3.1.2 Ví dụ mã thực tế (phiên bản Java, dùng công cụ BloomFilter của Google Guava)

3.1.3 Kỹ thuật tối ưu (phải làm trong môi trường sản xuất)

3.1.4 Điểm cần tránh bẫy

Phương án 2: Phân vùng đĩa + băm (loại bỏ chính xác, không giới hạn bộ nhớ)

3.2.1 Quy trình cốt lõi (hiểu đơn giản)

3.2.2 Ví dụ mã thực tế (phiên bản Java, quy trình cốt lõi)

3.2.3 Kỹ thuật tối ưu (phải làm trong môi trường sản xuất)

3.2.4 Điểm cần tránh bẫy

Bốn, phương án nâng cao: loại bỏ phân tán (tình huống loại bỏ thời gian thực)

4.1 Nguyên lý cốt lõi

4.2 Điểm cốt lõi thực tế

Năm, các câu hỏi phỏng vấn nâng cao (điểm cộng)

Câu hỏi phỏng vấn 1: Tại sao không dùng HashSet để loại bỏ trùng lặp 100 triệu URL?

Câu hỏi phỏng vấn 2: Tỷ lệ sai sót của Bộ lọc Bloom được kiểm soát như thế nào? Nguyên nhân gây sai sót là gì?

Câu hỏi phỏng vấn 3: Trong loại bỏ trùng lặp phân vùng đĩa + băm, số lượng phân vùng được xác định như thế nào?

Câu hỏi phỏng vấn 4: Làm thế nào để chọn phương án tối ưu nhất khi loại bỏ trùng lặp 100 triệu URL?

Câu hỏi phỏng vấn 5: Điểm cốt lõi khác biệt giữa Bộ lọc Bloom và phân vùng đĩa + băm là gì?

Sáu, kết luận

Thẻ Phổ Biến