Tối Ưu Tìm Kiếm Người Dùng Với Bloom Filter Trong Node.js
Khi hệ thống của bạn phát triển lên hàng triệu người dùng, ngay cả những thao tác đơn giản nhất—như kiểm tra xem một số điện thoại hay email đã tồn tại hay chưa—cũng có thể trở nên tốn kém.
Mặc dù bạn có thể thêm chỉ mục vào cơ sở dữ liệu, nhưng mọi tìm kiếm vẫn tiêu tốn I/O và CPU cycles. Dưới tình trạng lưu lượng đăng ký cao, điều này có thể nhanh chóng làm quá tải cơ sở dữ liệu của bạn.
Đây chính là lúc Bloom Filters xuất hiện như một giải pháp hữu hiệu. 🌸
🌱 Bloom Filter Là Gì?
Bloom Filter là một cấu trúc dữ liệu xác suất được sử dụng để kiểm tra sự tồn tại của một tập hợp. Nó cho phép chúng ta đặt câu hỏi:
👉 “Giá trị này có thể tồn tại không?”
Bloom Filter có thể trả lời:
- ❌ Chắc Chắn Không → An toàn để bỏ qua cơ sở dữ liệu.
- ✅ Có Thể Tồn Tại → Xác nhận với cơ sở dữ liệu.
Sự đánh đổi nhỏ này (cho phép sai số dương, nhưng không bao giờ sai số âm) mang lại cho chúng ta O(1) lookups với rất ít bộ nhớ sử dụng.
🔬 Cấu Trúc Của Một Bloom Filter
Cốt lõi của Bloom Filter là:
- Mảng Bit (kích thước
m) → bắt đầu với tất cả giá trị là 0. - k Hàm Băm → mỗi hàm ánh xạ một đầu vào tới một trong những vị trí
m.
👉 Khi chúng ta thêm một phần tử:
- Chạy nó qua tất cả
khàm băm. - Đổi trạng thái những vị trí đó trong mảng bit thành
1.
👉 Khi chúng ta kiểm tra một phần tử:
- Chạy nó qua cùng
khàm băm. - Nếu tất cả những vị trí đó là
1→ phần tử có thể tồn tại. - Nếu bất kỳ vị trí nào là
0→ nó chắc chắn không tồn tại.
📈 Hình Ảnh Minh Họa
Hãy tưởng tượng nó như một đường số (abscissa = trục x):
Mảng Bit (kích thước m)
0 1 2 3 4 5 6 7 8 9 ... m-1
[0][0][0][0][0][0][0][0][0][0]- Mỗi hàm băm chọn một số vị trí dọc theo đường này.
- Thêm
"alice@example.com"có thể đổi trạng thái các vị trí 3, 7, và 9 thành1. - Kiểm tra
"bob@example.com"? Nếu một trong các vị trí băm của nó vẫn là0, chúng ta biết rằng Bob không có trong tập hợp.
⚖️ Cân Bằng
- Nhiều bit (m) → ít va chạm hơn, giảm tỷ lệ sai số dương.
- Nhiều hàm băm (k) → chính xác hơn, nhưng cũng tốn nhiều tính toán hơn.
- Điểm ngọt phụ thuộc vào số lượng phần tử mong đợi
n.
Công thức cho k tối ưu:
k = n/m(ln2)
Sự cân bằng này là lý do tại sao Bloom Filter có kích thước nhỏ trong bộ nhớ nhưng mạnh mẽ trong quy mô.
🏗️ Kiến Trúc Của Chúng Tôi
Chúng tôi đã xây dựng một Dịch Vụ Bloom Filter trong Node.js hoạt động như một cổng kiểm soát nhanh trước khi truy cập cơ sở dữ liệu.
Nó bao gồm:
- Lớp Routes → điểm cuối API cho khách hàng.
- Lớp Handler → Xử lý yêu cầu, tương tác với dịch vụ.
- Lớp Service → Quản lý các Bloom Filter, tạo mới, làm mới và kiểm tra.
📜 Lớp Routes
Chúng tôi cung cấp ba điểm cuối dưới /bloom_filter:
javascript
import express from 'express';
import { getBloomFilterStatus, refreshBloomFilter, checkPhoneExists } from './handler.js';
const router = express.Router();
router.get('/status', getBloomFilterStatus);
router.post('/refresh', refreshBloomFilter);
router.get('/check', checkPhoneExists);
export default router;GET /status→ Giám sát trạng thái filters.POST /refresh→ Buộc làm mới.GET /check?phoneNumber=...→ Kiểm tra sự tồn tại.
⚙️ Lớp Handler
Các handler ngồi giữa yêu cầu API và dịch vụ. Chúng quản lý lỗi và phản hồi:
javascript
import userSearchBloomFilter from '../../services/userSearchBloomFilter.js';
import { generateInternalServerErrorRepsonse } from '../../utils/errorHandler.js';
export async function getBloomFilterStatus(req, res) {
try {
const status = userSearchBloomFilter.getStatus();
return res.status(200).json({ success: true, data: status });
} catch (error) {
const errorResponse = await generateInternalServerErrorRepsonse(error, 'getBloomFilterStatus');
return res.status(500).json(errorResponse);
}
}
export async function refreshBloomFilter(req, res) {
try {
await userSearchBloomFilter.refresh();
return res.status(200).json({
success: true,
message: 'Bloom filter đã được làm mới thành công'
});
} catch (error) {
const errorResponse = await generateInternalServerErrorRepsonse(error, 'refreshBloomFilter');
return res.status(500).json(errorResponse);
}
}
export async function checkPhoneExists(req, res) {
try {
const { phoneNumber } = req.query;
if (!phoneNumber) {
return res.status(400).json({
success: false,
error: 'Số điện thoại là bắt buộc'
});
}
const mightExist = userSearchBloomFilter.mightExist(phoneNumber);
return res.status(200).json({
success: true,
data: {
phoneNumber,
mightExist,
note: mightExist
? 'Có thể tồn tại - kiểm tra cơ sở dữ liệu'
: 'Chắc chắn không tồn tại'
}
});
} catch (error) {
const errorResponse = await generateInternalServerErrorRepsonse(error, 'checkPhoneExists');
return res.status(500).json(errorResponse);
}
}👉 Lưu ý cách checkPhoneExists không ngay lập tức truy cập cơ sở dữ liệu. Nó hỏi Bloom Filter trước.
🧠 Lớp Dịch Vụ: Logic Chính Của Bloom Filter
Đây là nơi mà phép màu thực sự xảy ra.
Chúng tôi duy trì bốn Bloom filter:
emailFilterphoneFilteralternateEmailFilteralternatePhoneFilter
Mỗi filter được khởi tạo với dung lượng mục tiêu và tỷ lệ lỗi (0.01 = 1%).
javascript
import BloomFilter from '../utils/BloomFilter.js';
import User from '../models/user.js';
import logger from '../setup/logger.js';
class UserSearchBloomFilterService {
constructor() {
this.emailFilter = new BloomFilter(100000, 0.01);
this.phoneFilter = new BloomFilter(100000, 0.01);
this.alternateEmailFilter = new BloomFilter(50000, 0.01);
this.alternatePhoneFilter = new BloomFilter(50000, 0.01);
this.isInitialized = false;
this.lastUpdated = null;
this.updateInterval = 24 * 60 * 60 * 1000; // 24 giờ
}🔄 Điền Dữ Liệu Cho Các Filter
Khi khởi động, chúng tôi lấy danh sách người dùng theo lô và thêm các định danh của họ vào các filter:
javascript
async populateFilters() {
const batchSize = 1000;
let offset = 0;
let hasMoreUsers = true;
while (hasMoreUsers) {
const users = await User.query(qb => {
qb.select('email', 'phone_number', 'alternate_email', 'alternate_phone');
qb.whereNotNull('email').orWhereNotNull('phone_number');
qb.limit(batchSize);
qb.offset(offset);
}).fetchAll();
const userList = users.toJSON();
if (userList.length === 0) {
hasMoreUsers = false;
break;
}
userList.forEach(user => {
if (user.email) this.emailFilter.add(user.email);
if (user.phone_number) this.phoneFilter.add(user.phone_number);
if (user.alternate_email) this.alternateEmailFilter.add(user.alternate_email);
if (user.alternate_phone) this.alternatePhoneFilter.add(user.alternate_phone);
});
offset += batchSize;
logger.info(`Đã xử lý ${offset} người dùng cho bloom filter`);
}
logger.info(`Hoàn thành việc điền dữ liệu cho Bloom filter. Tổng số người dùng đã xử lý: ${offset}`);
}Điều này đảm bảo tất cả người dùng hiện có đều được đại diện trong filter.
⚡ Logic Tìm Kiếm
Khi một yêu cầu kiểm tra số điện thoại/email đến:
javascript
mightExist(searchKey) {
if (!this.isInitialized) {
return true; // bảo vệ tạm thời cho đến khi khởi tạo
}
const normalizedKey = searchKey.toLowerCase().trim();
return (
this.emailFilter.mightContain(normalizedKey) ||
this.phoneFilter.mightContain(normalizedKey) ||
this.alternateEmailFilter.mightContain(normalizedKey) ||
this.alternatePhoneFilter.mightContain(normalizedKey)
);
}👉 Nếu nó trả về false, chúng tôi biết chắc chắn rằng người dùng không tồn tại.
👉 Nếu nó trả về true, chúng tôi truy vấn cơ sở dữ liệu để xác nhận.
🕒 Tự Động Làm Mới
Để giữ cho dữ liệu luôn mới, chúng tôi lập lịch một làm mới hàng ngày:
javascript
schedulePeriodicUpdate() {
setInterval(async () => {
try {
logger.info('Bắt đầu cập nhật bloom filter theo lịch trình');
await this.refresh();
} catch (error) {
logger.error('Cập nhật bloom filter theo lịch trình thất bại:', error);
}
}, this.updateInterval);
}Điều này sẽ xóa và điền lại các filter.
📊 Báo Cáo Tình Trạng
Cuối cùng, chúng tôi có thể kiểm tra tình trạng của filter:
javascript
getStatus() {
return {
isInitialized: this.isInitialized,
lastUpdated: this.lastUpdated,
emailFilterStats: this.emailFilter.getStats(),
phoneFilterStats: this.phoneFilter.getStats(),
alternateEmailFilterStats: this.alternateEmailFilter.getStats(),
alternatePhoneFilterStats: this.alternatePhoneFilter.getStats()
};
}🚀 Quy Trình Ví Dụ
Một form đăng ký kiểm tra xem 1231881971 có tồn tại hay không:
- Khách hàng gọi →
GET /bloom_filter/check?phoneNumber=<phoneNumber> - Bloom filter trả lời:
- ❌ Không có trong tập → Trả về ngay lập tức (bỏ qua DB).
- ✅ Có thể tồn tại → Truy vấn DB để xác nhận.
Điều này giảm tải cho cơ sở dữ liệu một cách đáng kể.
✅ Lợi Ích
- O(1) Tìm Kiếm → Siêu nhanh.
- Giảm Tải Cơ Sở Dữ Liệu → Ít truy vấn hơn.
- Có Thể Mở Rộng → Xử lý hàng triệu mục.
- Chịu Lỗi → Luôn sai về phía an toàn (chỉ sai số dương).
⚠️ Hạn Chế
- Sai Số Dương → Có thể nói “tồn tại” khi thực tế không.
- Không Thể Xóa → Bloom filters tiêu chuẩn không hỗ trợ xóa mục.
- Khởi Đầu Lạnh → Cho đến khi khởi tạo, trả về “có thể tồn tại” để tránh sai số âm.
🌟 Những Suy Nghĩ Cuối Cùng
Bloom Filters không phải là một sự thay thế cho cơ sở dữ liệu—chúng là một tầng tối ưu hóa. Hãy nghĩ về chúng như một người kiểm soát ở cổng vào câu lạc bộ:
- Nếu bạn chắc chắn không có trong danh sách, bạn sẽ bị từ chối ngay lập tức.
- Nếu bạn có thể có trong danh sách, họ sẽ kiểm tra lại bên trong.
Đối với các hệ thống có lưu lượng cao, việc kiểm soát đơn giản này có thể tạo ra sự khác biệt lớn.
