Tối ưu RAM trên Redis với HyperLogLog và Bloom Filter: Đếm và lọc dữ liệu lớn - ITFROMZERO - Share tobe shared! Tìm hiểu cách ứng dụng Redis HyperLogLog và Bloom Filter để đếm unique visitor và lọc trùng lặp dữ liệu lớn, giúp cắt giảm hơn 95% RAM so với cấu trúc Set truyền thống.

Khi hệ thống chạm mốc 20-30 triệu lượt truy cập mỗi ngày, bài toán RAM trên Redis sẽ lộ rõ điểm yếu. Thông thường, anh em hay ném thẳng user ID hoặc IP vào Set để đếm lượng người dùng duy nhất (UV – Unique Visitors). Hậu quả? Vài chục GB RAM bốc hơi chỉ sau một tuần chạy chiến dịch.

Nguyên nhân rất đơn giản: Set lưu trọn vẹn từng chuỗi dữ liệu thô để bảo đảm độ chính xác 100%. Tuy nhiên, ở các tác vụ phân tích traffic hay lọc spam URL, ta sẵn sàng đánh đổi 1% sai số để nén hàng chục gigabyte xuống còn vài megabyte. Lúc này, hai cấu trúc dữ liệu xác suất gồm HyperLogLog và Bloom Filter sẽ là lựa chọn thay thế hợp lý.

Table of Contents

1. Quick start: Thử nghiệm trong 5 phút

Bật terminal lên và test ngay với redis-cli để thấy cách hoạt động.

Thử nghiệm HyperLogLog (Có sẵn trong Redis core)

HyperLogLog tích hợp sẵn trong mọi bản Redis chuẩn mà không cần cài thêm module ngoài:

# Kết nối redis-cli
redis-cli

# Ghi nhận IP truy cập trong ngày
PFADD uv:2026-10-26 "192.168.1.1" "192.168.1.2" "192.168.1.3"
# Trả về: (integer) 1 (khi cardinality ước tính có thay đổi)

# Thêm lại một IP đã có
PFADD uv:2026-10-26 "192.168.1.1"
# Trả về: (integer) 0 (không làm tăng giá trị đếm)

# Lấy tổng lượng IP duy nhất
PFCOUNT uv:2026-10-26
# Trả về: (integer) 3

Thử nghiệm Bloom Filter (Cần Redis Stack)

Bloom Filter cần module RedisBloom. Cách nhanh nhất ở môi trường local là dựng một container Redis Stack:

docker run -d --name redis-stack -p 6379:6379 redis/redis-stack-server:latest

Sau khi container chạy, kiểm tra khả năng lọc trùng:

redis-cli

# Khởi tạo filter: sai số chấp nhận 1% (0.01), dung lượng dự kiến 1 triệu phần tử
BF.RESERVE blacklisted_emails 0.01 1000000

# Thêm email vi phạm vào danh sách chặn
BF.ADD blacklisted_emails "[email protected]"

# Kiểm tra email tồn tại
BF.EXISTS blacklisted_emails "[email protected]"
# Trả về: (integer) 1 (rất có thể đã nằm trong danh sách)

BF.EXISTS blacklisted_emails "[email protected]"
# Trả về: (integer) 0 (chắc chắn 100% chưa từng xuất hiện)

2. Bản chất bên dưới hoạt động ra sao?

Redis HyperLogLog: Đếm Cardinality với mức trần 12KB RAM

HyperLogLog giải quyết bài toán đếm phần tử duy nhất (Count-Distinct). Điểm ăn tiền nằm ở kích thước cố định: dù ghi nhận 1 nghìn hay 1 tỷ bản ghi, một key HyperLogLog trong Redis tốn tối đa 12KB bộ nhớ. Đổi lại, sai số chuẩn ở mức xấp xỉ 0.81%.

Về nguyên lý, thuật toán hash giá trị đầu vào thành một chuỗi 64 bit ngẫu nhiên. Xác suất để một chuỗi nhị phân ngẫu nhiên bắt đầu bằng k số 0 liên tiếp là (1/2)^k. Bằng cách phân chia dữ liệu vào 16.384 bucket (thùng) và ghi lại chuỗi số 0 dài nhất ở mỗi bucket, Redis ước lượng được tổng số phần tử độc bản cực kỳ sát với thực tế.

Đoạn script Python dưới đây minh họa việc gộp số liệu nhiều ngày:

import redis

r = redis.Redis(host='localhost', port=6379, db=0)

# Ghi nhận lượt truy cập riêng lẻ của từng ngày
r.pfadd('uv:day1', 'user_A', 'user_B', 'user_C')
r.pfadd('uv:day2', 'user_B', 'user_C', 'user_D')

# Merge trực tiếp hai key sang key tuần ngay trên Redis RAM
r.pfmerge('uv:week_total', 'uv:day1', 'uv:day2')

total_uv = r.pfcount('uv:week_total')
print(f"Tổng UV tuần ước tính: {total_uv}")  # Kết quả: 4

Bloom Filter: Kiểm tra tồn tại với tốc độ O(k)

Bloom Filter giải quyết bài toán kiểm tra tập hợp (Set Membership): phần tử X đã từng xuất hiện hay chưa?

Cấu trúc này gồm một chuỗi bit dài (bit array) và k hàm băm độc lập. Khi nạp một phần tử vào, phần tử đó đi qua k hàm băm để tính ra k chỉ mục (indexes), sau đó bật toàn bộ bit tại các vị trí đó lên 1.

Kết quả trả về 0: Phần tử chắc chắn 100% chưa từng xuất hiện. Chỉ cần một bit mang giá trị 0, phần tử đó không thể có mặt trong tập dữ liệu.
Kết quả trả về 1: Phần tử có thể đã tồn tại. Vẫn có tỷ lệ nhỏ bị dương tính giả (False Positive) do đụng độ hash từ các phần tử khác. Hiện tượng âm tính giả (False Negative) tuyệt đối không xảy ra.

Một giới hạn kỹ thuật cần chú ý: Bloom Filter cơ bản không hỗ trợ xóa phần tử. Nếu bạn tắt một bit về 0, thao tác đó có thể vô tình làm sai lệch kết quả của hàng loạt phần tử khác.

3. Ứng dụng thực tế trong kiến trúc Backend

Chống Cache Penetration (Thủng bộ nhớ đệm)

Kịch bản tấn công quen thuộc: Kẻ xấu gửi dồn dập hàng triệu request với ID rác (ví dụ: product_id = -1 hoặc 99999999). Vì các ID này không có trong cache, mọi request đều xuyên thẳng xuống PostgreSQL. Cơ sở dữ liệu nhanh chóng nghẽn pool kết nối và sập.

Đặt một Bloom Filter chặn trước tầng cache giải quyết dứt điểm vấn đề này:

import redis

r = redis.Redis(host='localhost', port=6379, decode_responses=True)

def get_product(product_id: int):
    # 1. Chặn ngay tại cổng bằng Bloom Filter
    if not r.execute_command('BF.EXISTS', 'bf:products', product_id):
        # Chắc chắn 100% ID không tồn tại trong hệ thống, dừng xử lý
        return None

    # 2. Đọc Redis cache thông thường
    cache_key = f"product:{product_id}"
    data = r.get(cache_key)
    if data:
        return data

    # 3. Query DB chỉ khi ID đó thực sự tồn tại hợp lệ
    data = query_from_postgres(product_id)
    if data:
        r.setex(cache_key, 3600, data)
    return data

Lọc trùng URL cho hệ thống Web Crawler

Với hệ thống bot cào hàng triệu link mỗi ngày, query database để kiểm tra URL đã tải hay chưa sẽ sớm tạo nút thắt cổ chai về Disk I/O. Lưu 10 triệu URL dạng chuỗi trong RAM có thể nuốt trọn vài GB. Nếu nén vào Bloom Filter với tỷ lệ lỗi 1%, toàn bộ mảng bit chỉ chiếm khoảng 11.5MB RAM, sẵn sàng đáp ứng 50.000 ops/giây với độ trễ dưới 1ms.

4. Kinh nghiệm thực chiến và lưu ý vận hành

Đội ngũ của mình từng gặp sự cố nghiêm trọng khi tracking click event cho một sàn thương mại điện tử. Ban đầu, team chọn cách an toàn là đẩy toàn bộ user ID vào Redis Set. Đến ngày Flash Sale, lượng truy cập tăng đột biến, Redis nuốt sạch 32GB RAM chỉ sau 4 ngày.

Server chính cạn kiệt bộ nhớ khiến Redis Sentinel phải kích hoạt failover khẩn cấp. Ngay trong đêm, team refactor lại logic đếm lượt xem bằng HyperLogLog. Mức tiêu thụ RAM hạ từ hơn 30GB xuống chưa đầy 400MB cho toàn bộ cụm Redis, chạy ổn định suốt mùa sale.

Dưới đây là một số bài học rút ra:

Luôn chủ động khởi tạo bằng BF.RESERVE: Đừng gọi thẳng BF.ADD lên một key chưa từng khai báo. Khi đó RedisBloom sẽ tự tạo bộ lọc với sức chứa mặc định rất nhỏ (thường chỉ 100 phần tử). Dữ liệu phình ra sẽ ép Redis tự động tạo thêm các lớp sub-filter nối tiếp (stacked filters), gây tốn thêm RAM và tăng độ trễ truy vấn.
Không dùng HyperLogLog nếu cần danh sách ID: Cấu trúc này sinh ra chỉ để trả về một con số đếm duy nhất. Bạn không có cách nào giải mã ngược lại danh sách ID ban đầu. Nếu nghiệp vụ yêu cầu tính năng như “Hiển thị 10 người vừa xem tin”, bạn vẫn phải dùng Set hoặc lưu vào database.
Cân nhắc kỹ ngưỡng False Positive: Muốn tỷ lệ sai số giảm từ 1% (0.01) xuống 0.01% (0.0001), kích thước mảng bit phải tăng gần gấp đôi và số lần băm (hash calculations) trên mỗi request cũng tăng theo, kéo CPU lên cao. Với đa số ứng dụng web, 1% sai số là mức dung hòa tối ưu giữa độ chính xác và tài nguyên.
Cần xóa dữ liệu? Hãy dùng Cuckoo Filter: Khi bài toán bắt buộc phải gỡ bỏ phần tử đã lưu mà vẫn muốn giữ ưu thế tiết kiệm bộ nhớ, hãy chuyển sang Cuckoo Filter (lệnh CF.ADD, CF.DEL trên Redis Stack).