Cấu trúc dữ liệu cho big data

Vì sao cần cấu trúc dữ liệu riêng cho big data

Với dữ liệu nhỏ, bạn dùng Set để kiểm tra đã thấy chưa, Map<string, number> để đếm, sort để lấy top 10. Khi dữ liệu là 5 tỷ URL, 1 tỷ lượt click mỗi ngày hay 100 triệu user khác nhau, các cấu trúc chính xác này tốn hàng chục tới hàng trăm GB RAM và không còn nằm gọn trên một máy.

Nhóm cấu trúc trong bài này chia thành hai loại:

• Cấu trúc xác suất (sketch): Bloom filter, Count-Min Sketch, HyperLogLog, Space-Saving. Chúng đổi một sai số nhỏ, có thể tính trước, lấy bộ nhớ nhỏ hơn hàng nghìn lần. Hầu hết gộp được (mergeable): mỗi máy tính sketch riêng rồi cộng lại, rất hợp với hệ phân tán.¹
• Cấu trúc lưu trữ cho ghi nhiều: skip list và LSM tree. Chúng chính xác, nhưng được thiết kế để ghi nhanh và đồng thời tốt. Đây là nền móng bên trong nhiều database ghi nhiều.²

Bloom filter được sách dùng đúng theo hướng sai số này: trả lời "không" thì chắc chắn, trả lời "có" thì chỉ là có thể.³

Kiến trúc: các cấu trúc này nằm ở đâu trong hệ thống

Trong một pipeline xử lý sự kiện, sketch thường nằm ở tầng stream (bộ nhớ của từng worker) và tầng lưu trữ (Redis), còn LSM tree nằm trong database phía sau. Chia sẻ việc đếm cho nhiều shard rồi gộp lại cũng là ý tưởng của sharded counter trong Grokking ch.24.⁴

Vì sketch gộp được, mỗi worker chỉ xử lý partition của mình. Mỗi phút, sketch của các worker được cộng lại thành kết quả toàn cục. Không cần gửi từng sự kiện tới một điểm tập trung.¹

Từng cấu trúc và API

Bloom filter

Một mảng m bit, ban đầu toàn 0, và k hàm hash. Thêm phần tử: tính k vị trí, bật cả k bit. Kiểm tra: nếu có bit nào bằng 0 thì chắc chắn chưa thêm; nếu cả k bit bằng 1 thì "có thể đã thêm". Sách Seven Databases mô tả đúng cơ chế này, và nhấn mạnh Bloom filter dùng dung lượng cố định, đổi lại thỉnh thoảng báo nhầm "có" với tỷ lệ dự đoán được theo độ đầy.³⁵

Công thức cần nhớ, với n phần tử và tỷ lệ báo nhầm p:

m (bit)  = -n × ln(p) / (ln 2)²   ≈ n × 9,6 bit khi p = 1%
k        = (m / n) × ln 2         ≈ 7 hàm hash khi p = 1%

Mỗi lần giảm p đi 10 lần tốn thêm khoảng 4,8 bit mỗi phần tử. Bloom filter không xóa được phần tử (tắt một bit có thể ảnh hưởng phần tử khác). Cần xóa thì dùng biến thể có bộ đếm.¹

import { createHash } from "node:crypto";

class BloomFilter {
  private bits: Uint8Array;
  constructor(private m: number, private k: number) {
    this.bits = new Uint8Array(Math.ceil(m / 8));
  }
  private positions(item: string): number[] {
    const h = createHash("sha256").update(item).digest();
    const h1 = h.readUInt32BE(0), h2 = h.readUInt32BE(4);
    // Double hashing: vị trí i = h1 + i × h2
    return Array.from({ length: this.k }, (_, i) => (h1 + i * h2) % this.m);
  }
  add(item: string) {
    for (const p of this.positions(item)) this.bits[p >> 3] |= 1 << (p & 7);
  }
  mightContain(item: string) {
    return this.positions(item).every((p) => (this.bits[p >> 3] & (1 << (p & 7))) !== 0);
  }
}

Bloom filter hay đứng trước một thao tác tốn kém: HBase dùng nó để biết một row key có tồn tại không trước khi đọc đĩa,³ còn Grokking Distributed Cache gợi ý dùng nó để biết chắc một entry không có trong cache server.⁶ Với web crawler, Grokking ch.35 dùng checksum URL trong một data store để loại URL trùng; Bloom filter là cách đổi bộ nhớ lấy sai số cho bước này (nhận định của khoá học).⁷

Count-Min Sketch

Một bảng d hàng × w cột số đếm, mỗi hàng một hàm hash. Thêm phần tử: tăng 1 ô ở mỗi hàng. Ước lượng tần suất: lấy giá trị nhỏ nhất trong d ô. Va chạm hash chỉ làm số đếm tăng, nên giá trị nhỏ nhất là ước lượng ít bị nhiễu nhất.

w = ⌈e / ε⌉       d = ⌈ln(1 / δ)⌉
Sai số: ước lượng ≤ giá trị thật + ε × N, với xác suất 1 − δ  (N = tổng số sự kiện)

Với ε = 0,001 và δ = 0,01: w = 2.719, d = 5, tổng 13.595 ô × 4 B ≈ 54 KB.¹ Sai số tối đa là 0,1% tổng số sự kiện. Với 1 tỷ click, sai số tối đa 1 triệu. Nghe lớn, nhưng chỉ ảnh hưởng phần tử hiếm. Phần tử phổ biến (thứ ta quan tâm trong top-k) có số đếm lớn hơn nhiều, sai số tương đối nhỏ.

HyperLogLog

Ý tưởng (chỉ nêu khái niệm cơ bản):⁸ băm mỗi phần tử ra chuỗi bit ngẫu nhiên. Trong n giá trị ngẫu nhiên, chuỗi dài nhất các bit 0 ở đầu xấp xỉ log₂(n). HLL chia hash thành m nhóm (register), mỗi register nhớ độ dài lớn nhất thấy được, rồi lấy trung bình điều hòa để giảm phương sai.

Sai số chuẩn là 1,04 / √m: thêm register thì sai số giảm, còn bộ nhớ gần như không phụ thuộc số phần tử đang đếm.

Lệnh PFMERGE (Redis) cuối cùng tính unique trong cả tuần bằng cách gộp các HLL theo ngày, không cần lưu lại danh sách user.

PFADD uv:ad:991:2026-11-02 user:1 user:2 user:3
PFCOUNT uv:ad:991:2026-11-02
PFMERGE uv:ad:991:week uv:ad:991:2026-10-27 uv:ad:991:2026-10-28 uv:ad:991:2026-11-02

Top-K: heap và Space-Saving

Chính xác: giữ Map<item, count> đầy đủ, sau đó dùng min-heap kích thước K để lấy top K trong O(n log K). Hợp khi số phần tử khác nhau vừa RAM (vài triệu).

Xấp xỉ, bộ nhớ cố định:

• Count-Min Sketch + min-heap K phần tử. Mỗi sự kiện: tăng CMS, đọc ước lượng, nếu lớn hơn đáy heap thì đưa vào heap.
• Space-Saving. Chỉ giữ đúng k bộ đếm. Phần tử mới khi đã đầy: thay phần tử có số đếm nhỏ nhất, kế thừa số đếm đó cộng 1. Đảm bảo mọi phần tử có tần suất lớn hơn N/k đều nằm trong danh sách.¹

Grokking ch.24 mô tả bài Top K của Twitter bằng sharded counter: mỗi hashtag có một counter, số shard quyết định theo lượng follower của người dùng hashtag đó; có counter theo vùng và counter toàn cục là tổng các counter vùng. Khi counter vùng đạt một ngưỡng (ví dụ 10.000) thì hashtag trở thành trend ở vùng đó.⁹

Skip list

Danh sách liên kết có thứ tự, thêm các tầng "đường cao tốc": mỗi node được đưa lên tầng trên với xác suất 1/2 (hoặc 1/4). Tìm kiếm đi từ tầng cao nhất, nhảy xa rồi xuống dần. Chèn, xóa, tìm đều O(log n) kỳ vọng, và duyệt theo khoảng rất tự nhiên.²

So với cây cân bằng, skip list dễ cài hơn và dễ làm đồng thời hơn vì chèn chỉ sửa vài con trỏ cục bộ, không phải xoay cây. Redis in Action ch.9 nêu cấu trúc thông thường của sorted set là hash table cộng skiplist, và khi sorted set còn ngắn Redis có thể lưu dạng ziplist nén (bộ nhớ ít hơn, nhưng phải giải mã mỗi lần đọc).¹⁰

LSM tree

LSM (log-structured merge) tree biến ghi ngẫu nhiên thành ghi tuần tự:

1. Ghi vào WAL (append) và memtable trong RAM (thường là skip list). WAL được ghi trước khi sửa dữ liệu để phục hồi khi node chết, như HBase mô tả.¹¹
2. Memtable đầy thì flush xuống đĩa thành SSTable: file bất biến, key đã sắp xếp.
3. Compaction chạy nền, gộp nhiều SSTable, bỏ bản ghi cũ và tombstone.
4. Đọc: kiểm tra memtable, rồi các SSTable từ mới tới cũ. Mỗi SSTable có Bloom filter để bỏ qua file chắc chắn không chứa key (cùng ý tưởng HBase dùng Bloom filter để tránh đọc đĩa tốn kém³). Building Microservices cũng nhắc Cassandra lưu dữ liệu thành các file SSTable.¹²

Trade-off: ghi rất nhanh, nhưng đọc có thể phải xem nhiều file (read amplification), và compaction ghi lại dữ liệu nhiều lần (write amplification). Cassandra và HBase dùng họ cấu trúc này. Postgres và MySQL dùng B-tree, cân bằng hơn cho đọc.²

Con số và sizing

Các con số là ước tính (giả định của khoá học), đủ để tính nhanh trong phỏng vấn.¹

Ví dụ web crawler: mục tiêu 1 tỷ trang mỗi tháng, sai số chấp nhận 0,1% (bỏ sót 1 trên 1.000 URL mới vì Bloom báo nhầm "đã thấy"). m = 1B × 14,4 bit ≈ 1,8 GB, k = 10. Vừa trong RAM một máy, hoặc chia Bloom theo hash của domain ra nhiều worker. Con số 1 tỷ trang là giả định của khoá học.¹

Ví dụ ad click aggregator: 10.000 click/s, cần unique user mỗi quảng cáo mỗi phút. Mỗi worker giữ HLL theo (ad_id, phút) trong RAM, cuối phút gửi HLL (vài KB) về Redis bằng PFMERGE. Lượng dữ liệu gửi đi không phụ thuộc số click.

Khi nào dùng và khi nào không

Bảng trên là nhận định tổng hợp của khoá học về điều kiện dùng từng cấu trúc.¹

Vận hành ở quy mô nhỏ và lớn

Nhỏ. Đừng dùng sketch nếu dữ liệu vừa RAM. SET của Redis cho 1 triệu user id tốn cỡ vài chục đến hàng trăm MB (ước tính, cần đo), đơn giản và chính xác. Đếm top-k bằng sorted set ZINCRBY là đủ cho vài trăm nghìn phần tử; Redis in Action cũng dùng ZSET để lưu và cộng dồn thống kê.¹³

Vừa. Dùng HLL có sẵn của Redis. Bloom filter có thể cài trong code ứng dụng như ví dụ trên, lưu mảng bit vào Redis bằng SETBIT/GETBIT (Seven Databases cũng lưu Bloom filter trong Redis⁵). Đặt rõ sai số chấp nhận được trong tài liệu thiết kế.

Lớn. Sketch được tính trong job stream (Flink, Kafka Streams) theo cửa sổ thời gian, rồi lưu vào kho để gộp tiếp. Nhiều database phân tích có sẵn hàm đếm xấp xỉ.¹ Với LSM database, theo dõi compaction backlog và dung lượng đĩa dự phòng để compaction chạy.²

Một vài lưu ý vận hành:

• Bloom filter đầy dần. Khi số phần tử vượt n đã định, tỷ lệ báo nhầm tăng nhanh. Dùng scalable Bloom filter (thêm tầng mới khi đầy) hoặc tạo filter mới theo chu kỳ. Sách cũng nói tỷ lệ báo nhầm tăng khi nhồi thêm phần tử.³
• Hash phải giống nhau giữa các worker nếu muốn gộp sketch. Cố định seed và thuật toán hash trong cấu hình chung.
• Cửa sổ thời gian. CMS và HLL không trừ được. Muốn "trong 1 giờ qua", giữ 60 sketch theo phút và gộp, thay vì một sketch chạy mãi.

Điểm nói trong phỏng vấn

1. Hỏi về độ chính xác trước. "Số này dùng để hiển thị hay để tính tiền?" Chỉ đề xuất sketch khi câu trả lời là hiển thị hoặc ước lượng.
2. Tính RAM hai cách (chính xác và xấp xỉ) để cho thấy vì sao cần sketch. Bloom 1% ≈ 10 bit mỗi phần tử, HLL vài KB mỗi key, CMS vài chục KB.¹
3. Nêu hướng sai số. Bloom chỉ báo nhầm "có".³ CMS chỉ đếm dư. Điều này quyết định chỗ đặt chúng trong luồng xử lý.
4. Nhấn mạnh tính gộp được. Đây là lý do sketch hợp với hệ phân tán: tính cục bộ, gộp toàn cục.
5. Khi bàn về database ghi nhiều, giải thích LSM tree, Bloom filter trên mỗi SSTable, và trade-off write amplification so với B-tree.

Bài liên quan: Redis cho HLL và sorted set, Time-series database cho nén và lưu dữ liệu theo thời gian, Cassandra cho LSM tree trong thực tế.

Nguồn trích dẫn

1. Lý thuyết · Count-Min Sketch: bảng d hàng × w cột; mỗi phần tử được băm bằng d hàm, mỗi hàng tăng một ô; ước lượng tần suất = giá trị nhỏ nhất trong d ô. Không bao giờ đếm thấp hơn thực tế; sai số cộng thêm không quá ε × N (N là tổng số lần đếm) với xác suất ít nhất 1 − δ khi w = ⌈e/ε⌉ và d = ⌈ln(1/δ)⌉. Ví dụ ε = 0,001, δ = 0,01 cho w = 2.719, d = 5, tức 13.595 ô × 4 byte ≈ 54 KB. Bloom filter: mảng m bit với k hàm băm; thêm phần tử thì đặt k bit lên 1; kiểm tra thấy đủ k bit bằng 1 thì "có thể có", thiếu một bit thì "chắc chắn không" (không bao giờ sai âm). Với n phần tử và tỉ lệ dương tính giả p: m = −n × ln p ÷ (ln 2)², k = (m ÷ n) × ln 2. Ví dụ n = 1 tỉ URL, p = 1% cho m ≈ 9,6 tỉ bit ≈ 1,2 GB và k ≈ 7. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷ ↩⁸ ↩⁹ ↩¹⁰

2. Chưa có nguồn trong thư viện: thư viện không có sách về skip list, LSM tree hay so sánh với B-tree; chỉ nêu khái niệm cơ bản. ↩ ↩² ↩³ ↩⁴

3. Seven Databases in Seven Weeks (file .zip, tải về giải nén) · ch.4 HBase · Day 2 · mục "Compression and Bloom Filters" và hộp "How Do Bloom Filters Work?" (tr. 110–111). ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶

4. Grokking Modern System Design · ch.24 Sharded Counters · phần mở đầu (heavy hitters) và mục "Sharded counters". ↩

5. Seven Databases in Seven Weeks (file .zip, tải về giải nén) · ch.8 Redis · mục "Bloom Filters" (tr. 287–288). ↩ ↩²

6. Grokking Modern System Design · ch.16 Distributed Cache · mục "Linked list" (ghi chú về Bloom filter). ↩

7. Grokking Modern System Design · ch.35 Design a Web Crawler · mục "Duplicate eliminator" (dedup bằng checksum URL và nội dung). ↩

8. Chưa có nguồn trong thư viện: thư viện không có sách về HyperLogLog; chỉ nêu khái niệm cơ bản. ↩

9. Grokking Modern System Design · ch.24 Sharded Counters · mục "Using sharded counters for the Top K problem". ↩

10. Redis in Action · ch.9 Reducing memory use · §9.1 Short structures, §9.1.1 The ziplist representation. ↩

11. Seven Databases in Seven Weeks (file .zip, tải về giải nén) · ch.4 HBase · Day 2 · đoạn về write-ahead log (WAL), tr. 112–113. ↩

12. Building Microservices (file .zip, tải về giải nén) · ch.5 Splitting the Monolith · mục "Backup Data Pump" (tr. 99). ↩

13. Redis in Action · ch.5 Using Redis for application support · §5.2.2 Storing statistics in Redis (tr. 98–99). ↩