Đã đăng vào thg 8 30, 1:20 SA 4 phút đọc

Từ Bloom Filter tới Cuckoo filter và cài đặt

Dẫn nhập

Khi mình đọc báo, mình tình cờ thấy một bài viết về Bloom Filter. Trước đây, mình đã tham dự một buổi thuyết trình về chủ đề này trong nhóm Grokking Vietnam, nhưng lúc đó mình không hiểu rõ và cũng không biết Bloom Filter có thể ứng dụng ra sao, nên mình đã bỏ qua. Giờ đây, khi đọc lại bài viết, mình thấy nó dễ hiểu và thú vị, cùng với các ứng dụng của Bloom Filter. Quyết định tìm hiểu thêm, cài đặt và áp dụng nó.

Phần lý thuyết của Bloom Filter thì nó khá đơn giản:

Cần 1 cái mảng để lưu dữ liệu, kiểu dữ liệu của nó là các bit 0,1. Mặc định ban đầu là các bit = 0
Một giá trị cần đưa vào mảng này thì cần băm ra các giá trị index : 16, 2, 7,... Ứng với các index băm ra được, ta set tại vị trí 16, 2, 7, ... giá trị = 1
Để kiểm tra 1 giá trị Y có hay không thì cũng băm Y ra các index: 16, 2, 7, ..., Ứng với các index này mà mình kiểm tra đều = 1, thì kết luận là có thể có giá trị Y. Nếu tồn tại một index mà tại đó = 0 thì kết luận là chắc chắn không có giá trị Y.

Ứng dụng của Bloom filter

Hệ quản trị cơ sở dữ liệu: Các hệ thống như Google Bigtable, Apache HBase, Apache Cassandra và PostgreSQL sử dụng Bloom Filter để tăng tốc quá trình tìm kiếm. Nó giúp nhanh chóng xác định những bản ghi không tồn tại, từ đó giảm chi phí và cải thiện hiệu năng tìm kiếm.
Trình duyệt web: Google Chrome áp dụng Bloom Filter để phát hiện các URL độc hại. Mọi URL đều được kiểm tra bằng Bloom Filter nội bộ. Chỉ những URL nào được xác định có nguy cơ cao mới được kiểm tra kỹ lưỡng hơn, và nếu thực sự là độc hại, trình duyệt sẽ cảnh báo người dùng.
Hệ thống gợi ý: Medium sử dụng Bloom Filter trong hệ thống gợi ý để kiểm tra xem một bài viết đã được đọc bởi người dùng hay chưa. Điều này giúp hệ thống đề xuất nội dung phù hợp hơn cho từng người dùng.

Từ Bloom Filter tới Cuckoo Filter

Trong quá trình cài đặt, mình phát hiện được là bloom filter nó chỉ cho insert mà không cho remove, nên không thể áp dụng cho bài toán kiểm tra có dữ liệu trong hệ thống của mình không. Vì dữ liệu của mình có insert vào và có remove đi. Mình có tìm kiếm và Google có trả lời cho mình 1 khái niệm khác nữa là Counting Bloom Filter (cái này các bạn Google sẽ rõ thêm) nhưng mình chưa thõa man. Mình tiếp tục tìm và biết thêm về Cukoo Filter, đây là bản rất cải tiến của Bloom Filter.

Cuckoo Filter là một cấu trúc dữ liệu xác suất, tương tự như Bloom Filter, được sử dụng để kiểm tra sự hiện diện của một phần tử trong một tập hợp. Tuy nhiên, Cuckoo Filter có một số ưu điểm nổi bật, như khả năng xóa phần tử và hiệu suất tốt hơn trong một số tình huống so với Bloom Filter.

Ưu điểm của Cuckoo Filter:

Khả năng xóa phần tử: Cuckoo Filter cho phép xóa phần tử, điều mà Bloom Filter không thể thực hiện. Hiệu suất: Trong một số tình huống, Cuckoo Filter có thể cung cấp hiệu suất tốt hơn so với Bloom Filter, đặc biệt khi xét đến việc xóa phần tử và tốc độ tìm kiếm.

Cài đặt

Redis có hỗ trợ Cuckoo Filter, và mình dùng Redis để cài đặt và test thử.

Bước 1 là chạy redis rebloom lên

Đương nhiên là mình phải cài docker trước rùi nhé

docker run -d --name redis-bloom -p 6379:6379 redislabs/rebloom:latest

Bước 2: cài đặt


import io.lettuce.core.RedisClient;
import io.lettuce.core.RedisURI;
import io.lettuce.core.api.StatefulRedisConnection;
import io.lettuce.core.cluster.api.sync.RedisClusterCommands;
import io.lettuce.core.codec.StringCodec;
import io.lettuce.core.output.BooleanOutput;
import io.lettuce.core.output.StatusOutput;
import io.lettuce.core.protocol.CommandArgs;
import io.lettuce.core.protocol.ProtocolKeyword;

public class RedisCuckooFilterTest {

    // Define protocol keywords for Cuckoo Filter commands
    private static final ProtocolKeyword CF_RESERVE = new ProtocolKeyword() {
        @Override
        public byte[] getBytes() {
            return "CF.RESERVE".getBytes();
        }

        @Override
        public String name() {
            return "CF.RESERVE";
        }
    };

    private static final ProtocolKeyword CF_ADD = new ProtocolKeyword() {
        @Override
        public byte[] getBytes() {
            return "CF.ADD".getBytes();
        }

        @Override
        public String name() {
            return "CF.ADD";
        }
    };

    private static final ProtocolKeyword CF_EXISTS = new ProtocolKeyword() {
        @Override
        public byte[] getBytes() {
            return "CF.EXISTS".getBytes();
        }

        @Override
        public String name() {
            return "CF.EXISTS";
        }
    };

    private static final ProtocolKeyword CF_DEL = new ProtocolKeyword() {
        @Override
        public byte[] getBytes() {
            return "CF.DEL".getBytes();
        }

        @Override
        public String name() {
            return "CF.DEL";
        }
    };

    public static void main(String[] args) {

        // Redis client and connection setup
        RedisClient redisClient = null;
        StatefulRedisConnection<String, String> connection = null;
        String cuckooFilterName = "myCuckooFilter";

        try {
            // Create Redis client and connect to Redis Cluster
            redisClient = RedisClient.create(RedisURI.Builder.redis("localhost", 6379).build());
            connection = redisClient.connect();
            System.out.println("Connected to Redis");

            // Obtain synchronous commands interface
            RedisClusterCommands<String, String> commands = connection.sync();

            // Create a Cuckoo Filter
            commands.dispatch(CF_RESERVE, new StatusOutput<>(StringCodec.UTF8),
                    new CommandArgs<>(StringCodec.UTF8).add(cuckooFilterName).add(1000));

            // Add elements to the filter
            commands.dispatch(CF_ADD, new BooleanOutput<>(StringCodec.UTF8),
                    new CommandArgs<>(StringCodec.UTF8).add(cuckooFilterName).add("element1"));
            commands.dispatch(CF_ADD, new BooleanOutput<>(StringCodec.UTF8),
                    new CommandArgs<>(StringCodec.UTF8).add(cuckooFilterName).add("element2"));

            // Check if an element exists in the filter
            boolean exists = commands.dispatch(CF_EXISTS, new BooleanOutput<>(StringCodec.UTF8),
                    new CommandArgs<>(StringCodec.UTF8).add(cuckooFilterName).add("element1"));
            System.out.println("Element1 exists: " + exists);

            // Remove elements from the filter
            commands.dispatch(CF_DEL, new BooleanOutput<>(StringCodec.UTF8),
                    new CommandArgs<>(StringCodec.UTF8).add(cuckooFilterName).add("element1"));
            commands.dispatch(CF_DEL, new BooleanOutput<>(StringCodec.UTF8),
                    new CommandArgs<>(StringCodec.UTF8).add(cuckooFilterName).add("element2"));

            // Check if an element exists after removal
            exists = commands.dispatch(CF_EXISTS, new BooleanOutput<>(StringCodec.UTF8),
                    new CommandArgs<>(StringCodec.UTF8).add(cuckooFilterName).add("element1"));
            System.out.println("Element1 exists: " + exists);

            // Remove Cuckoo Filter
            removeCuckooFilter(commands, cuckooFilterName);
        } catch (Exception e) {
            e.printStackTrace();
        } finally {
            // Close connection and shutdown client
            if (connection != null) {
                connection.close();
            }
            if (redisClient != null) {
                redisClient.shutdown();
            }
        }
    }

    private static void removeCuckooFilter(RedisClusterCommands<String, String> commands, String filterName) {
        commands.del(filterName);
    }
}

=> Kết Quả:

Connected to Redis
Element1 exists: true
Element1 exists: false

Bloom Filters