Video học lập trình mỗi ngày

Câu chuyện của một dev gửi tới anonystick.com

Bài viết được đưa vào: Con đường trở thành Backend

Ngày mà tôi đã chờ một tuần để chuẩn bị mở ra con đường mới trong sự nghiệp của mình. Tôi vẫn còn nhớ như in... Và cũng có thể nhìn lại và khắng định đó là, ở cái thời buổi này đôi khi chăm chỉ thôi chưa đủ để thành công?.

Xe máy dừng lại trước toà nhà, nó to hơn tôi nghĩ, cách 10m là có 3 bác bảo vệ ngồi đó, bên cạnh là hộp cơm đang ăn dở... Tôi tiến vào hỏi... Và câu chuyện nó như thế này.

Cái ngày "định mệnh"

Ngày hôm đó, tôi ngồi trong một phòng họp nhỏ ở tầng 15 tòa nhà Bitexco. Công ty này làm về công nghệ tài chính, khá nổi tiếng trong giới. Người phỏng vấn là một anh kỹ sư trên dưới 39 tuổi, mặc áo len đen giản dị, chiếc MacBook trên bàn dán đầy nhãn dán.

Anh ấy mở trình soạn thảo mã, nhìn vào tôi và hỏi:

"Bạn có biết Bloom Filter không?"

Lúc đó tôi cảm thấy tim mình đập nhanh hơn. Trong đầu thoáng nghĩ đến câu trả lời: "Bloom như hoa nở sao anh?"

May mắn thật, ba tuần trước đó tôi mới giải quyết một vấn đề hiệu năng cho hệ thống gợi ý sản phẩm ở công ty cũ. Đó là một công ty khởi nghiệp làm thương mại điện tử. Khi đó, người dẫn đầu kỹ thuật cấp cao đã gợi ý tôi tìm hiểu về Bloom Filter. Và điều đó hóa ra lại trở thành chìa khóa giúp tôi vượt qua cuộc phỏng vấn này.

Hôm nay tôi muốn kể lại câu chuyện về Bloom Filter - cấu trúc dữ liệu đã giúp tôi có công việc mơ ước.

Bloom Filter là cái gì thế?

Tôi thở nhẹ, gỡi gàng giữ bình tĩnh và trả lời, vì sao tôi lại có một chút thoải mái đến như vậy. Có thời gian tôi nghĩ bạn nên xem video này của tôi trước khi xem cuộc nói chuyện giữa tôi và người phỏng vấn.

Cố gắng xem kỹ: Cấu trúc dữ liệu của YouTube, GitHub đã giúp tôi 'flex' trong buổi phỏng vấn Senior | Bloom Filters

"Bloom Filter là một cấu trúc dữ liệu xác suất, dùng để kiểm tra tư cách thành viên - nghĩa là kiểm tra xem một phần tử có trong tập hợp không. Nó có ưu điểm là rất nhanh và tiết kiệm bộ nhớ."

Anh kỹ sư gật đầu: "Tốt. Vậy 'xác suất' ở đây có nghĩa là gì?"

Tôi biết rằng đây là câu hỏi then chốt. Và đây cũng chính là ưu điểm của mình, vì thực sự mình đã sử dụng nó trong một vài dự án. Mình mừng thầm...

Nhưng có điều đặc biệt ở đây.

• Nếu nó nói "KHÔNG" → Chắc chắn 100% là không có
• Nếu nó nói "CÓ" → Có thể có, nhưng cũng có thể... không có

Hoạt động như thế nào?

Hình dung như này: Bloom Filter giống như một dãy công tắc đèn (bit array):

Khởi tạo: [TẮT][TẮT][TẮT][TẮT][TẮT][TẮT][TẮT][TẮT]

Khi muốn thêm một phần tử (ví dụ "hello"):

1. Dùng 3 hàm hash khác nhau
2. Mỗi hàm cho ra 1 vị trí
3. Bật đèn tại các vị trí đó

h1("hello") = 2, h2("hello") = 5, h3("hello") = 7
Kết quả: [TẮT][TẮT][BẬT][TẮT][TẮT][BẬT][TẮT][BẬT]

Khi kiểm tra "hello" có tồn tại không:

• Tính lại 3 hash → vị trí 2, 5, 7
• Kiểm tra: đều BẬT → "Có thể có!"
• Nếu có 1 vị trí TẮT → "Chắc chắn không có!"

Tại sao phải dùng Bloom Filter?

Anh ấy mở một tài liệu trình chiếu và nói: "Bây giờ chúng ta thử với tình huống thực tế. Công ty chúng tôi có khoảng 80 triệu tài khoản người dùng. Khi có người đăng ký mới, làm sao kiểm tra tên đăng nhập có sẵn sàng hay chưa một cách nhanh nhất?"

"Trấn vấn cơ sở dữ liệu?" - tôi thử đưa ra giải pháp đầu tiên mà ai cũng nghĩ tới.

"80 triệu bản ghi mà. Câu trấn vấn SELECT COUNT() FROM users WHERE username = 'anonystick' sẽ mất khoảng 200-300ms dù đã có chỉ mục rồi. Nếu có 500 người đăng ký cùng lúc thì sao?"*

Tôi nhận ra vấn đề. "Vậy thì lưu vào bộ đệm?"

"Tốt! Nhưng hãy tính xem, 80 triệu tên đăng nhập, trung bình 12 ký tự, UTF-8..." - Anh ấy đưa cho tôi cây bút.

Tôi viết lên bảng trắng: 80 triệu * 12 byte = 960MB... chưa kể phần tăng thêm của hệ thống bộ đệm nữa.

Và đó là lúc tôi nhớ ra Bloom Filter!

So sánh thực tế:

Khi nào nên dùng Bloom Filter?

Từ kinh nghiệm thực tế, tôi thấy Bloom Filter tỏa sáng khi:

1. Volume lớn: Hàng triệu/tỷ records cần check
2. Tốc độ quan trọng: Cần response time cực thấp
3. Memory hạn chế: Không thể cache toàn bộ data
4. Chấp nhận false positive: 1-5% sai lầm không sao
5. Read-heavy: Nhiều lần check, ít khi thêm mới

Các ứng dụng thực tế:

• Công cụ thu thập web: Kiểm tra liên kết đã thu thập chưa
• Mạng phân phối nội dung: Kiểm tra nội dung có trong bộ đệm không
• Phần mềm diệt virus: Kiểm tra chữ ký tập tin có độc hại không
• Cơ sở dữ liệu: Kiểm tra hàng có tồn tại trước khi đọc đĩa cứng

Nhược điểm của Bloom Filter (và cách tôi đã trả lời)

Đến phần này, anh interviewer hỏi: "Vậy nhược điểm thì sao? Không lẽ perfect à?"

Tôi thở dài và kể thật:

4 nhược điểm chính:

1. False Positive - "Tỷ lệ nói dối"

• Có thể nói "CÓ" khi thực tế "KHÔNG CÓ"
• Tỷ lệ phụ thuộc vào: số hash functions, kích thước array, số elements

Ví dụ thực tế:

// Tên người dùng "anonystick" chưa tồn tại
// Nhưng Bloom Filter nói "CÓ" vì băm trùng với người dùng khác
bloomFilter.mightContain("anonystick"); // true (dương tính!)

// Phải trấn vấn cơ sở dữ liệu để chắc chắn
const exists = await db.query("SELECT * FROM users WHERE username = ?", ["anonystick"]);
// Kết quả: không tồn tại

2. Không thể DELETE

• Một khi đã set bit = 1, không thể set về 0
• Vì nhiều elements có thể cùng hash đến 1 vị trí

bloomFilter.add("anonystick");  // đặt bit tại vị trí [2,5,7] = 1
bloomFilter.add("tipsjavascript");  // cũng đặt bit tại vị trí 5 = 1

// Không thể xóa anonystick vì sẽ ảnh hưởng tipsjavascript!
// bloomFilter.delete("anonystick"); // Không có phương thức này

3. Không lưu trữ data thực tế

• Chỉ biết "có/không có", không biết value gốc là gì
• Phải kết hợp với storage khác

4. Kích thước cố định

• Phải estimate trước số lượng elements
• Thêm quá nhiều → false positive tăng cao

Cách khắc phục (phần làm anh interviewer impressed!)

Anh ấy hỏi tiếp: "Vậy là senior developer, bạn sẽ handle những vấn đề này thế nào?"

Đây là lúc tôi "flex" kinh nghiệm thực chiến:

1. Giải quyết False Positive: Layered Approach

// Chiến thuật 3 tầng phòng thủ
async function checkUserExists(username) {
    // Tầng 1: Bloom Filter (siêu nhanh - 0.01ms)
    if (!bloomFilter.mightContain(username)) {
        return false; // 100% chắc chắn không tồn tại
    }

    // Tầng 2: Bộ đệm (nhanh - 1ms) 
    const cached = await redis.get(`user:${username}`);
    if (cached !== null) {
        return cached === 'exists';
    }

    // Tầng 3: Cơ sở dữ liệu (chậm nhưng chính xác - 50ms)
    const exists = await db.query('SELECT 1 FROM users WHERE username = ?', [username]);

    // Cache kết quả cho lần sau
    await redis.setex(`user:${username}`, 300, exists ? 'exists' : 'not_exists');

    return !!exists;
}

Kết quả (rough estimate):

• Khoảng 65-75% requests dừng ở Tầng 1
• ~20-30% requests hit cache ở Tầng 2
• Chỉ còn 5-10% requests phải đến database

(Con số này tôi estimate dựa trên monitoring, không chính xác 100%)

2. Giải quyết Deletion: Counting Bloom Filter

class CountingBloomFilter {
    constructor(size, hashFunctions) {
        this.counters = new Array(size).fill(0); // Dùng counter thay vì bit
        this.hashFunctions = hashFunctions;
    }

    add(item) {
        this.getIndexes(item).forEach(index => {
            this.counters[index]++; // Tăng counter
        });
    }

    remove(item) {
        this.getIndexes(item).forEach(index => {
            if (this.counters[index] > 0) {
                this.counters[index]--; // Giảm counter
            }
        });
    }

    mightContain(item) {
        return this.getIndexes(item).every(index => this.counters[index] > 0);
    }
}

3. Giải quyết Fixed Size: Dynamic Scaling

class ScalableBloomFilter {
    constructor(initialCapacity = 1000, targetFPR = 0.01) {
        this.filters = [];
        this.capacity = initialCapacity;
        this.targetFPR = targetFPR;
        this.currentCount = 0;

        // Tạo filter đầu tiên
        this.addNewFilter();
    }

    add(item) {
        // Nếu filter hiện tại đầy, tạo filter mới
        if (this.currentCount >= this.capacity) {
            this.addNewFilter();
        }

        // Thêm vào filter hiện tại
        const currentFilter = this.filters[this.filters.length - 1];
        currentFilter.add(item);
        this.currentCount++;
    }

    mightContain(item) {
        // Check tất cả filters
        return this.filters.some(filter => filter.mightContain(item));
    }

    addNewFilter() {
        const newFilter = new BloomFilter(this.capacity, this.targetFPR);
        this.filters.push(newFilter);
        this.capacity *= 2; // Tăng capacity cho filter tiếp theo
        this.currentCount = 0;
    }
}

Case Study: Hệ thống của tôi ở công ty cũ

Cuối cùng, anh interviewer hỏi: "Kể cho tôi một case study thực tế bạn đã áp dụng."

Tôi kể về dự án e-commerce mà tôi đã optimize:

Context của dự án (công ty cũ):

Chúng tôi là một sàn thương mại giống như Shopee nhưng quy mô nhỏ hơn - có khoảng 15 triệu sản phẩm từ 200 nghìn người bán. Trên trang chủ có tính năng "Sản phẩm vừa xem" và "Có thể bạn cũng thích".

Vấn đề gặp phải:

• Database PostgreSQL với bảng user_product_views có ~500M records
• Mỗi user vào homepage → query check 24 sản phẩm (6 rows x 4 products)
• Query: SELECT product_id FROM user_product_views WHERE user_id = ? AND product_id IN (?)
• Response time: 400-800ms (peak hours)
• Database CPU spiked 85% vào 8-9pm hàng ngày
• PM và business team "hỏi thăm" hàng ngày

Giải pháp với Bloom Filter:

// Trước kia: Query trực tiếp database
async function getRecommendations(userId, productIds) {
    const viewedProducts = await db.query(`
        SELECT product_id FROM user_views 
        WHERE user_id = ? AND product_id IN (?)
    `, [userId, productIds]);

    const viewedIds = viewedProducts.map(p => p.product_id);
    return productIds.filter(id => !viewedIds.includes(id));
}

// Sau này: Bloom Filter + Database
class UserViewTracker {
    constructor() {
        this.userFilters = new Map(); // userId -> BloomFilter
    }

    async getUserFilter(userId) {
        if (!this.userFilters.has(userId)) {
            // Load từ Redis hoặc tạo mới
            const filter = new BloomFilter(10000, 0.05);

        // Đồng bộ với cơ sở dữ liệu (chỉ 1 lần)
        const viewedProducts = await db.query(
            'SELECT product_id FROM user_views WHERE user_id = ?', 
            [userId]
        );            viewedProducts.forEach(p => filter.add(p.product_id));
            this.userFilters.set(userId, filter);
        }

        return this.userFilters.get(userId);
    }

    async getRecommendations(userId, productIds) {
        const filter = await this.getUserFilter(userId);

        // Filter nhanh với Bloom Filter
        const possiblyNotViewed = productIds.filter(id => !filter.mightContain(id));

        // Chỉ query database cho những cái "có thể đã xem"
        const definitelyViewed = productIds.filter(id => filter.mightContain(id));
        let actuallyViewed = [];

        if (definitelyViewed.length > 0) {
            const result = await db.query(`
                SELECT product_id FROM user_views 
                WHERE user_id = ? AND product_id IN (?)
            `, [userId, definitelyViewed]);

            actuallyViewed = result.map(p => p.product_id);
        }

        // Kết hợp kết quả
        return [
            ...possiblyNotViewed,  // Chắc chắn chưa xem
            ...definitelyViewed.filter(id => !actuallyViewed.includes(id)) // Có thể chưa xem
        ];
    }

    async markAsViewed(userId, productId) {
        const filter = await this.getUserFilter(userId);
        filter.add(productId);

        // Persist vào database
        await db.query(
            'INSERT IGNORE INTO user_views (user_id, product_id) VALUES (?, ?)',
            [userId, productId]
        );
    }
}

Kết quả sau 2 tuần deploy:

• Response time: 650ms → 120ms (homepage load)
• Database load: Giảm từ 85% → 45% CPU usage (peak hours)
• Memory usage: ~1.8MB per 10K viewed products per user
• False positive rate: ~3.2% (acceptable vì chỉ ảnh hưởng UX nhẹ)
• Bug phát sinh: 2 bugs nhỏ về cache invalidation (đã fix)
• Team feedback: PM hài lòng, senior dev khen "creative approach"

Lesson learned:

• Bloom Filter không phải silver bullet
• Phải hiểu trade-offs và use cases phù hợp
• Kết hợp với caching và database indexing mới hiệu quả

Phút cuối định mệnh

Anh interviewer gật đầu hài lòng, rồi hỏi câu cuối:

"Một câu hỏi cuối. Nếu bạn implement Bloom Filter trong production với high concurrency, bạn sẽ handle race condition thế nào?"

Đây là lúc tôi nhớ lại bug đau đớn từng gặp ở dự án cũ:

Thread Safety Issues:

// Code có bug - race condition
class UnsafeBloomFilter {
    add(item) {
        const indexes = this.getHashIndexes(item);

        // Nếu 2 threads cùng add -> có thể miss update
        indexes.forEach(index => {
            this.bits[index] = 1; // Not atomic!
        });
    }
}

Giải pháp đã áp dụng:

1. Read-Write Lock Pattern:

   class SafeBloomFilter {
    constructor(size, hashCount) {
        this.filter = new BloomFilter(size, hashCount);
        this.readCount = 0;
        this.writeLock = false;
        this.mutex = new Mutex();
    }
   
    async add(item) {
        await this.acquireWriteLock();
        try {
            this.filter.add(item);
        } finally {
            this.releaseWriteLock();
        }
    }
   
    async mightContain(item) {
        await this.acquireReadLock();
        try {
            return this.filter.mightContain(item);
        } finally {
            this.releaseReadLock();
        }
    }
   }
   

2. Lock-free với Redis:

   class RedisBloomFilter {
    constructor(redisClient, keyPrefix) {
        this.redis = redisClient;
        this.keyPrefix = keyPrefix;
    }
   
    async add(item) {
        const indexes = this.getHashIndexes(item);
        const pipeline = this.redis.pipeline();
   
        // Atomic operations với Redis
        indexes.forEach(index => {
            pipeline.setbit(`${this.keyPrefix}:bloom`, index, 1);
        });
   
        await pipeline.exec();
    }
   
    async mightContain(item) {
        const indexes = this.getHashIndexes(item);
        const pipeline = this.redis.pipeline();
   
        indexes.forEach(index => {
            pipeline.getbit(`${this.keyPrefix}:bloom`, index);
        });
   
        const results = await pipeline.exec();
        return results.every(([err, result]) => result === 1);
    }
   }
   

Anh ấy gật đầu, gõ mấy cái note gì đó trên laptop. Rồi nhìn tôi và nói: "Cảm ơn bạn đã chia sẻ. Tôi rất ấn tượng với cách bạn áp dụng Bloom Filter trong thực tế."

Tôi thở phào nhẹ nhõm - có vẻ như pass rồi? Và sau này tôi mới biết anh ta viết đó là: "Interesting... sounds like you've actually implemented this in production. That's good to see."

Epilogue: "Và tôi đã được nhận!"

Thứ sáu tuần sau, đang ngồi uống cà phê ở quán quen thuộc thì điện thoại rênh lên:

"Chào anh, em là nhân sự của công ty. Chúc mừng! Chúng em muốn mời anh vào vị trí kỹ sư phần mềm cấp cao với mức lương..."

Lúc đó tôi suýt như làm đổ cả ly cà phê.

Nhìn lại, Bloom Filter đã giúp tôi không chỉ vì kiến thức kỹ thuật, mà còn vì cách tôi thể hiện khả năng giải quyết vấn đề và kinh nghiệm thực tế. Người phỏng vấn đã nói họ thích những ứng viên có thể kết nối lý thuyết với thực hành.

Mấy điều tôi rút ra được:

1. Technical knowledge có thể học, nhưng experience thì phải trải qua - Anh ấy không hỏi tôi thuật toán, mà hỏi cách áp dụng
2. Thừa nhận limitations và trade-offs thể hiện sự mature hơn là "flex" kiến thức
3. Production experience > theoretical knowledge - Về cơ bản ai cũng biết Bloom Filter là gì, nhưng có mấy đứa implement thật?
4. Biết kể chuyện - Tech interview không chỉ là coding test, mà còn là conversation

Tóm tắt cho anh em dev

Khi nào dùng Bloom Filter:

• Khối lượng dữ liệu lớn (hàng triệu/tỷ bản ghi)
• Bộ nhớ hạn chế, cần tối ưu hóa
• Tốc độ quan trọng hơn độ chính xác tuyệt đối
• Chấp nhận được dương tính (1-5%)
• Tải trọng đọc nhiều

Ưu điểm:

• Cực kỳ nhanh (dưới một mili giây)
• Tiết kiệm bộ nhớ (kích thước cố định)
• Không có âm tính giả (nói "không" thì chắc chắn không)
• Mở rộng tốt với hệ thống phân tán

Nhược điểm:

• Dương tính (có thể nói "có" nhầm)
• Không thể xóa (Bloom Filter truyền thống)
• Không lưu trữ dữ liệu thực tế
• Kích thước cố định, khó mở rộng linh hoạt

Cách khắc phục:

• Layered approach: BF + Cache + Database
• Counting Bloom Filter: Support deletion
• Scalable Bloom Filter: Dynamic scaling
• Thread-safe: Proper locking/Redis atomic ops

Lời cuối: Tôi thấy Bloom Filter là một trong những concepts hay nhất mà tôi đã học. Nó simple nhưng lại rất hiệu quả trong những tình huống đúng. Nếu bạn đang gặp vấn đề performance với large dataset, thử xem có thể áp dụng được không.

Happy coding và chúc mọi người phỏng vấn thành công!

Disclaimer: Đây là kinh nghiệm cá nhân của tôi, ko phải tất cả công ty đều hỏi như vậy. Và các con số mà tôi đưa ra là rough estimate, không chính xác tuyệt đối. Nếu có thắc mắc gì, welcome to discuss!