#1 - Thiết kế KV database như thế nào? Bài học từ Bitcask

Tôi bắt đầu series này vì LinkedIn của tôi toàn rác

50 Days of System Design

Tôi thích đọc về thiết kế hệ thống nên trang LinkedIn cũng tràn ngập những bài viết về chủ đề này. Tiếc rằng, chúng thường là những bài viết nông cạn đến kinh ngạc, kiểu như:

khứa này muốn dạy bạn về Youtube trong 2ph

, hay là:

khứa này chuyên vẽ mấy cái hộp và mũi tên

Trong thời đại của tiktok, của reel, và youtube short, việc các KOL biên ra mấy bài viết như vầy cũng là điều dễ hiểu. Tuy nhiên, tôi tin rằng việc đào sâu vào bản chất của vấn đề và giải pháp, trong dài hạn, sẽ cho độc giả nhiều giá trị hơn (hoặc ít nhất, không làm họ thối não).

Vì vậy, series 50 Days of System Design (S.D) ra đời. Nó viết về thiết kế hệ thống nhưng dành cho người đọc chậm và muốn hiểu sâu. Bắt đầu thôi!

Bitcask

Bitcask¹ là một database dạng Key-Value với hiệu suất cao ra đời năm 2009. Mặc dù hiện tại ít công ty đang dùng Bitcask (vì đã có những giải pháp tốt hơn), theo tôi, Bitcask vẫn có một thiết kế “đẹp” và đáng tìm hiểu.

Yêu cầu bài toán khá đơn giản: 1 database để lưu trữ dữ kiệu dạng key-value:

• get(key)

• put(key, value)

• delete(key)

Tuy nhiên không dễ để đạt hiệu suất cao cho 3 thao tác này trên ổ cứng (HDD). Điều này xuất phát từ cơ chế hoạt động của HDD.

HDD

Dữ liệu trong HDD được lưu trữ trên các vùng (sector) của các đĩa từ (platter). Để đọc hoặc ghi dữ liệu lên đĩa từ, cần thực hiện 2 bước:

1. di chuyển đầu đọc đến đúng track.

2. quay đĩa từ để đầu đọc quét qua đúng sector cần đọc/ghi.

Random IO và Sequential IO

Việc đọc ghi dữ liệu vào HDD, về cơ bản, có 2 loại:

• Sequential IO: dữ liệu được đọc/ghi lên các bit gần nhau của các sector liên tiếp nhau trên đĩa từ.

• Random IO: dữ liệu được đọc/ghi lên các ô lộn xộn trên các sector phân bố ngẫu nhiên trên đĩa từ.

  

Vì cơ chế di chuyển đầu đọc và quay đĩa khi đọc/ghi dữ liệu, Random IO trên HDD chậm hơn nhiều so với Sequential IO. Tận dụng đặc điểm này, Bitcask đã hạn chế tối đa Random IO bằng cách lưu trữ dữ liệu key-value trên các append-only log files, nghĩa là việc ghi dữ liệu vào Bitcask được thực hiện bằng cách chỉ chèn thêm data vào cuối file ~ sequential IO.

Data files

Các dữ liệu Key-Value của Bitcasks được lưu trữ trên các append-only file, với một active file để ghi, các non-active file còn lại là read-only. Mọi thao tác ghi (put, delete) đều được thực hiện bằng cách ghi thêm entry vào cuối active file. Điều này khiến latency và throughput của các tác vụ ghi trên Bitcask cực kỳ tốt.

Khi kích thước active file đạt đến một ngưỡng định trước, nó tự động chuyển thành non-active read-only file và một active file mới sẽ được tạo ra để tiếp tục quá trình ghi.

Bitcask data file structure

Mỗi entry trong data file được mô tả như hình trên, gồm có:

• CRC²: giá trị dùng để phát hiện lỗi data trong quá trình truyền đi hay lưu trữ (tương tự như checksum), ví dụ server bị crash trong quá trình ghi dữ liệu.

• Timestamp: thời gian entry được ghi vào file.

• Key Size: kích thước của key.

• Value Size: kích thước của value.

• Key: giá trị của key.

• Value: giá trị của value.

KeyDir

Việc tối ưu hóa tốc độ ghi bằng cách sử dụng các append-only file trong Bitcask vô tình làm chậm quá trình đọc dữ liệu. Để thực hiện tác vụ get(key), chúng ta phải duyệt qua từng file của Bitcask và tìm entry (key, value) có timestamp mới nhất.

Để khắc phục vấn đề này, Bitcask đã áp dụng một nguyên tắc phổ biến trong database:

When reading is slow, consider using an index

KeyDir là 1 hash table trong RAM để lưu trữ vị trí của tất cả các key trong Bitcask.

key -> { file_id, value_position, value_size }

Nhờ đó, để get(key), thay vì phải duyệt tuần tự tất cả các file, chúng ta chỉ cần đọc vị trí của key từ KeyDir trong O(1), và từ đó có đủ dữ kiện (file id, vị trí cần đọc, lượng data cần đọc) để đọc trực tiếp giá trị value từ data file.

KeyDir được lưu trong RAM, đóng vai trò như một hashing index

Compaction

Cơ chế sử dụng append-only data file sẽ chiếm nhiều bộ nhớ theo thời gian vì chúng ta chỉ chèn thêm các giá trị mới mà không xóa đi các giá trị cũ. Để giải quyết vấn đề này, Bitcask sử dụng cơ chế compaction để định kỳ hợp nhất các read-only data file. Cơ chế này khá phổ biến trong các NoSQL database sử dụng LSM Tree như Cassandra³, Scylladb⁴, chúng ta sẽ thảo luận LSM Tree trong một bài viết khác.

Quá trình compaction diễn ra như sau:

• duyệt từng entry trong từng non-active file. Việc này được tiến hành dễ dàng vì các entry trong data file đều có cấu trúc xác định.

  

• kiểm tra xem entry hiện tại có phải là data hợp lệ và mới nhất không bằng cách lock và truy vấn entry tương ứng trong KeyDir?

  • no: skip entry

  • yes: chèn entry vào cuối file mới và update KeyDir

• unlock entry trong KeyDir.

• xóa data file cũ đi.

Compaction sẽ được kích hoạt tự động bởi Bitcask khi số lượng key cũ (dead key) chạm ngưỡng định trước (mặc định 60%) hoặc dung lượng key cũ (dead key) chạm ngưỡng định trước (mặc định 512MB)⁵.

Operations

Như vậy, chúng ta đã khám phá cơ chế hoạt động tổng quát của Bitcask, cùng điểm lại chi tiết của từng tác vụ:

1. get(key)

   • tìm kiếm data file id và offset của key bằng KeyDir

     { file_id,  value_position, value_size } = KeyDir.get(key)

   • đọc value của key bằng cách sử dụng thông tin trên

2. put(key, value)

   • chèn (key, value) cùng các meta information vào cuối active file

   • update hoặc tạo mới 1 entry mới trong KeyDir

   Hai bước này phải được thực hiện một cách atomically để tránh race condition.

3. delete(key)

   Tác vụ xóa key có thể được tiến hành bằng put(key, tombstone), với tombstone là 1 giá trị đặc biệt để biểu thị các key bị xóa.

Ưu và nhược của Bitcask

Ưu điểm

• độ trễ thấp (low latency) và ổn định.

• thông lượng ghi cao (high write throughput), ~5000-6000 qps⁶.

• dễ backup và phục hồi do data file hầu hết là read-only.

• thiết kế đơn giản và dễ hiểu.

Nhược điểm

• lưu trữ toàn bộ key trong KeyDir ở RAM, với những hệ thống lớn đây sẽ là hạn chế lớn.

• không hỗ trợ range query, ví dụ get tất cả các key trong khoảng [min, max).

• không có các tính năng nâng cao như transaction, các kiểu dữ liệu và query phức tạp.

Lesson learned

• trên HDD, hiệu suất sequential IO vượt trội hơn hẳn so với random IO. Việc ghi dữ liệu vào các append-only file cũng diễn ra nhanh chóng hơn.

• when reading is slow, consider using an index.

• khi lưu trữ data, nên có checksum/CRC để bảo đảm tính toàn vẹn.

Happy weekend, until next time!

1. https://docs.riak.com/riak/kv/2.2.3/setup/planning/backend/bitcask/index.html

2. https://en.wikipedia.org/wiki/Cyclic_redundancy_check

3. https://cassandra.apache.org/doc/latest/cassandra/managing/operating/compaction/overview.html

4. https://opensource.docs.scylladb.com/stable/kb/compaction.html

5. https://docs.riak.com/riak/kv/2.2.3/setup/planning/backend/bitcask/index.html#merge-triggers

6. https://riak.com/assets/bitcask-intro.pdf