Tự tạo cơ sở dữ liệu của riêng bạn

• Giải thích nguyên lý cơ bản và quy trình triển khai của cơ sở dữ liệu khóa-giá trị
• Bắt đầu từ cách lưu trữ bền vững và tìm kiếm qua hệ thống tệp
• Khi thêm, sửa, xóa dữ liệu sẽ phát sinh các vấn đề kém hiệu quả
• Dần dần phát triển sang cấu trúc hiệu quả hơn với append-only file, chỉ mục, sắp xếp, nén phân đoạn (compaction) và nhiều cải tiến khác
• Liên kết với các cấu trúc hiện đại như LSM Tree và đang được áp dụng trong các hệ thống quy mô lớn thực tế

---

Lời mở đầu: Bắt đầu tự xây dựng cơ sở dữ liệu

Giả sử không có khái niệm cơ sở dữ liệu, hãy cùng khám phá từng bước cách tạo cơ sở dữ liệu của riêng mình
Nhìn vào quy trình tự triển khai một cơ sở dữ liệu khóa-giá trị ở dạng đơn giản nhất

Ý tưởng cơ bản: Lưu trữ bền vững bằng tệp

• Mục tiêu của cơ sở dữ liệu là lưu dữ liệu lâu dài và sau đó tìm kiếm hiệu quả
• Cách phổ biến nhất là dùng hệ thống tệp để ghi mỗi cặp key-value vào file
• Khi lưu dữ liệu, ví dụ ghi thêm vào file theo định dạng $ db set 1 "Lorem ipsum"
• Khi tìm kiếm dữ liệu, kiểm tra tuần tự tất cả các cặp key-value trong file để tìm key mong muốn
• Khi sửa, thay trực tiếp giá trị của key trong file; khi xóa, loại bỏ bản ghi tương ứng khỏi file

Vấn đề: sửa tại chỗ kém hiệu quả

• Cách sửa/xóa trực tiếp trong file là rất kém hiệu quả
• File là một chuỗi byte đơn thuần, nên khi thay đổi dữ liệu ở giữa thì toàn bộ dữ liệu phía sau phải bị dịch chuyển
• Ví dụ, khi thay thế một bản ghi bằng giá trị mới và độ dài thay đổi, phát sinh chi phí di chuyển toàn bộ nội dung phía sau
• Khi dữ liệu tăng lên, tốc độ và hiệu quả bị ảnh hưởng rất lớn

Cải tiến 1: Cấu trúc append-only file

• Khi sửa hoặc xóa, giữ nguyên dữ liệu cũ và chỉ thêm bản ghi mới vào cuối file
• Mỗi lần dữ liệu thay đổi, thêm một bản ghi mới và thay đổi thuật toán truy vấn để lấy giá trị key mới nhất từ cuối cùng
• Xóa được đánh dấu bằng một giá trị đặc biệt "tombstone" (như null)
• Ưu điểm: ghi hiệu quả hơn mà không cần di chuyển dữ liệu hiện có
• Nhược điểm: dữ liệu lặp lại và chỉ dấu xóa làm file dần phình ra
• Tốc độ truy vấn vẫn chậm vì vẫn phải duyệt toàn bộ file

Cải tiến 2: Quản lý kích thước file và compaction

• Để giải quyết vấn đề file tăng vô hạn, khi file vượt quá một kích thước nhất định, chuyển sang file mới (segment) và loại bỏ dữ liệu không cần thiết (trùng lặp/đã xóa) ở file trước để giảm dung lượng (compaction)
• Khi compaction, chỉ giữ lại dữ liệu thực sự cần thiết, xóa các bản ghi cũ hoặc chỉ còn đánh dấu xóa
• Tiến hóa thành cấu trúc quản lý nhiều file segment và hợp nhất (merge) chúng khi cần

Cải tiến 3: Tìm kiếm nhanh bằng chỉ mục (index)

• Tạo chỉ mục hash table trong bộ nhớ theo offset của file cho từng key để truy vấn nhanh hơn
• Khi tìm kiếm, tra cứu index trước rồi đọc trực tiếp vị trí tương ứng trong file
• trade-off: tốc độ truy vấn nhanh nhưng vì index nằm trong bộ nhớ, khi số key tăng lớn sẽ gặp giới hạn RAM
• Vì cần quản lý index nên hiệu năng ghi có thể giảm nhẹ

Cải tiến 4: Sắp xếp (Sorted String Tables) và sparse index

• Nếu luôn lưu theo thứ tự key, có thể đạt hiệu quả cao khi thực hiện range query
• Dựa vào tính sắp xếp, có thể lưu chỉ mục chỉ cho một phần key (sparse index), thay vì toàn bộ key
• Có thể điều chỉnh mật độ chỉ mục để cân bằng giữa dung lượng bộ nhớ và hiệu suất truy vấn

Cách hiện thực: Kết hợp in-memory và on-disk để đảm bảo tính bền vững

• Dữ liệu mới trước tiên được ghi vào danh sách in-memory đã sắp xếp, đồng thời ghi vào append-only file để dự phòng
• Khi danh sách in-memory tăng lớn, sắp xếp và lưu ra file trên đĩa (SST), sau đó cập nhật index
• Khi tra cứu, kiểm tra RAM trước; nếu không có thì dùng index để tìm trên đĩa
• Tệp trên đĩa được quản lý theo chế độ immutable; sửa/xóa cũng xử lý bằng việc thêm bản ghi mới
• Dữ liệu trùng lặp/đã xóa không cần thiết được compact định kỳ để kiểm soát kích thước file

Sự xuất hiện của LSM Tree

• Nhìn rộng ra, cấu trúc đã phát triển này thực tế là kiến trúc được gọi là LSM Tree
• Với cấu trúc kết hợp memtable và on-disk sorted string table (SST), nó phù hợp cho môi trường cần tốc độ và quy mô lớn
• Nền tảng như LevelDB, Amazon DynamoDB và các hệ thống khóa-giá trị lớn đang dùng nó làm cấu trúc dữ liệu cốt lõi
• Dù có nhược điểm và khác biệt với các cấu trúc khác (như DB quan hệ dựa trên B-Tree), nó đã chứng minh hiệu năng tốt cho môi trường có lưu lượng lớn và mở rộng cao

Kết luận

• Từ việc bắt đầu bằng lưu trữ file đơn giản, dần dần tiến hóa qua append-only, index, sắp xếp, segment compaction và kết hợp in-memory/on-disk để có thiết kế cơ sở dữ liệu tốt hơn
• Có thể học được hoạt động nội bộ và tư duy kiến trúc của cơ sở dữ liệu thông qua quá trình triển khai trực tiếp
• Cấu trúc LSM Tree vẫn giữ vai trò quan trọng trong các hệ thống dữ liệu quy mô lớn hiện đại
• Còn nhiều hướng để tiếp tục nghiên cứu thêm, như các cách tiếp cận khác của cơ sở dữ liệu quan hệ với cấu trúc B-Tree

[GN⁺]

Ý kiến trên Hacker News

• Thiết kế và ví dụ của bài này thực sự ấn tượng với tôi; cấu trúc dễ đọc tạo cảm giác dễ tiếp thu. Bản thân bài tập này cũng là một trải nghiệm rất thú vị. Khi bắt đầu từ trạng thái trống, mình có thể tự kiểm chứng thật sự mình biết được bao nhiêu.
  • Bản thân tôi cũng từng có thái độ nôn nóng kiểu “đừng tự làm cơ sở dữ liệu, cũng đừng dùng cơ sở dữ liệu khóa-giá trị, chỉ dùng SQL”. Nhưng ngay cả suy nghĩ đó cũng đến sau khi tôi tự thiết kế DB hoặc cố tránh SQL bằng cách chỉ dùng KV rồi cuối cùng vẫn tái tạo SQL một cách rất thô sơ. Rõ ràng, việc học bằng trải nghiệm thực tế là có giá trị.
  • Một điều hơi tiếc là họ dùng lorem ipsum cho ví dụ; vì vậy rất dễ đọc qua loa. Nếu có ví dụ dữ liệu thực tế thì sẽ thu hút hơn nhiều. Ngoài ra thì đây là một bài viết cực kỳ hay.
• Bài viết nói rằng “Cây LSM là cấu trúc dữ liệu cơ bản trong DynamoDB và cho hiệu năng rất tốt trong môi trường quy mô lớn… có thể xử lý đến 80 triệu yêu cầu mỗi giây”, nhưng điều này hơi có thể gây hiểu nhầm. LSM được dùng cho engine lưu trữ ở cấp độ node, chứ không mô tả quá trình toàn hệ thống phân tán mở rộng lên 80 triệu RPS. Theo như tôi nhớ, bài báo Dynamo ban đầu dùng BerkeleyDB (b-tree hoặc LSM), và đến bài báo năm 2012 mới chuyển hoàn toàn sang engine dựa trên LSM.
• Tôi đã bấm vào một vài bài trong danh sách bài viết và rất ấn tượng vì thiết kế cùng animation rất đẹp.
• Ví dụ đầu tiên trong phần “Sorting in Practice” có vẻ bị lỗi. Trong phần giải thích có ghi rằng dữ liệu phải được sắp xếp trong bộ nhớ rồi ghi ra đĩa ở trạng thái đã sắp xếp, nhưng trong ví dụ thực tế khi ghi ra đĩa lại không còn sắp xếp nữa; ví dụ recap về flush (thứ hai) cũng tương tự, nhưng dòng chữ thì nói file đã được ghi theo thứ tự sắp xếp.
• Bài rất thú vị. Gần đây tôi đang mô hình hóa hoạt động của lập trình viên thành một hệ thống key-value dạng time series: key là mỗi nhà phát triển, value là commit. Tôi gặp vấn đề tương tự: log tăng rất nhanh, index trở nên nặng, truy vấn theo phạm vi chậm dần. Khi nén segment (compaction) tôi băn khoăn làm sao quyết định dữ liệu nào sẽ bị loại bỏ; cân bằng giữa tính mới mẻ và thời gian giữ lại dữ liệu khá khó.
• Tôi đã dành 4 tuần qua để viết một triple store thủ công. Nếu bài này ra sớm hơn một chút, chắc tôi đã có thêm vài insight để hiểu nhanh hơn từ trước, nên còn cảm giác tiếc.
• Nếu tác giả đọc được bình luận này, tôi tò mò không biết có thể thêm RSS feed trên site được không? Tôi muốn thêm vào Feedly để đọc.
• Nếu muốn tự làm cơ sở dữ liệu của riêng mình, tôi chắc chắn khuyên bạn nên xem cuốn sách trực tuyến miễn phí này.
  • Tôi nhớ có một bài viết từng giải thích các khái niệm cơ bản của cơ sở dữ liệu bằng ví dụ bash (ví dụ: “cách tạo DB bằng bash”), nhưng không tìm thấy nữa; nếu ai biết link đó, mong chia sẻ giúp.
• Trang web đã quá tải đến mức không thể truy cập nữa.
  • Chắc hẳn cần một cơ sở dữ liệu nhanh hơn.
• Cách giải thích theo kiểu “nguyên lý gốc (First Principles)” từng bước một thật sự rất hợp với tôi. Đi theo bài này, ở mỗi giai đoạn bạn thấy rõ vấn đề nào nảy sinh và khi giải quyết thì phát sinh thêm vấn đề gì; nhờ đó có thể đi tới giải pháp rất thỏa mãn.