Kiến thức cơ bản về cơ sở dữ liệu

Những điều cơ bản về bashdb

• bashdb, chương trình cơ sở dữ liệu đơn giản nhất, được cấu thành từ hai hàm bash.
• Hàm db_set thêm dữ liệu vào tệp, còn hàm db_get truy vấn dữ liệu.
• Các vấn đề của bashdb bao gồm độ bền, tính nguyên tử, tính cô lập và hiệu năng.

Cải thiện bashdb để đạt ACID

• ACID là các thuộc tính của giao dịch cơ sở dữ liệu, bao gồm tính nguyên tử, tính nhất quán, tính cô lập và độ bền.
• Để cải thiện độ bền của bashdb, thêm lệnh sync vào db_set.
• Để đảm bảo tính cô lập, sử dụng chương trình flock để thêm khóa tệp.

Độ bền

• fsync và fdatasync là các system call dùng để flush bộ đệm ghi xuống đĩa.
• Lệnh sync flush mọi trang "bẩn" xuống đĩa, và cờ -d sẽ gọi fdatasync.

Tính cô lập

• Sử dụng flock để cung cấp tính cô lập đa tiến trình cho bashdb.
• flock là chương trình Linux dùng cho khóa tệp, và cờ -s cho phép đọc đồng thời.

Tin xấu

• Không tìm được cách đơn giản để đảm bảo tính nguyên tử với bashdb.
• Để cải thiện hiệu năng, cần tối ưu thuật toán O(n).

Storage engine

• Mục đích của storage engine là cung cấp một lớp trừu tượng để đọc và ghi dữ liệu vào bộ nhớ lưu trữ bền vững.
• Thiết kế storage engine hướng tới việc giảm thiểu disk I/O và disk seek.

B-tree biến đổi được

• B-tree là một biến thể của BST có tính cục bộ không gian, giúp giảm thiểu disk I/O và seek.
• B-tree là BST được tổng quát hóa để các nút có thể có nhiều nút con hơn.

LSM tree bất biến

• LSM tree là cấu trúc dữ liệu bất biến được ghi tuần tự, phù hợp với workload thiên về ghi.
• LSM tree đệm dữ liệu trong bộ nhớ, rồi khi đạt dung lượng nhất định sẽ flush thành SSTable đã được sắp xếp.

Bloom filter

• Bloom filter là cấu trúc dữ liệu xác suất cho phép kiểm tra hiệu quả việc một phần tử không tồn tại trong tập hợp.
• Bloom filter hoạt động bằng cách sử dụng các hàm băm, với độ phức tạp không gian là O(log n).

Write Ahead Log

• WAL là một tệp đặc biệt ghi log mọi thao tác giao dịch, và tái dựng trạng thái khi tiến trình cơ sở dữ liệu khởi động.

Tính cô lập

• Để đạt được tính cô lập, có thể dùng khóa bi quan, khóa lạc quan hoặc MVCC.
• Chuẩn ANSI/ISO SQL 92 định nghĩa nhiều mức cô lập đọc khác nhau.

Hệ thống phân tán

• Hệ thống phân tán làm tăng độ phức tạp, và có thể phân tán dữ liệu trên nhiều máy để đạt tính sẵn sàng và mở rộng theo chiều ngang.
• Theo lý thuyết CAP, hệ thống chỉ có thể đảm bảo hai trong ba yếu tố: tính nhất quán, tính sẵn sàng và khả năng chịu phân vùng.

Consistent hashing

• Consistent hashing là phương pháp phân mảnh dữ liệu giúp giảm lượng mục phải di chuyển khi thêm hoặc bớt nút.

Ý kiến của GN⁺:

• Hiểu các vấn đề cơ bản của cơ sở dữ liệu và các thuộc tính ACID là cốt lõi của kỹ thuật cơ sở dữ liệu.
• Ví dụ bashdb giúp hiểu các vấn đề phát sinh trong hệ thống cơ sở dữ liệu thực tế.
• Thiết kế storage engine và hệ thống phân tán là các yếu tố quan trọng quyết định hiệu năng và độ tin cậy của cơ sở dữ liệu.

[GN⁺]

Ý kiến trên Hacker News

• Tóm tắt bình luận thứ nhất:

  • Một trong những đặc tính của cơ sở dữ liệu dựa trên LSM là các bản ghi đã bị xóa hoặc tombstone vẫn tồn tại trong thời gian dài.
  • Chỉ nên bỏ qua tombstone ở level cuối cùng, không nên bỏ qua ở mọi level.
  • Nếu không, tombstone ở level trên có thể bị loại bỏ và khiến các mục ở level dưới xuất hiện trở lại.
  • Các cơ sở dữ liệu như RocksDB cố gắng giải quyết vấn đề này bằng các tối ưu hóa.

• Tóm tắt bình luận thứ hai:

  • Né tránh việc học về hệ thống phân tán có thể là điều nguy hiểm.
  • Trên thực tế, mọi hệ thống production không tầm thường đều là hệ thống phân tán.
  • Nếu cơ sở dữ liệu là một tập hợp sao chép, thì đó là một hệ thống phân tán.
  • Nếu muốn tìm hiểu về hệ thống phân tán, hãy xem jepsen.io và raft.github.io.

• Tóm tắt bình luận thứ ba:

  • Về tính nhất quán, có tính nhất quán của cơ sở dữ liệu và tính nhất quán của ứng dụng.
  • Có thể đạt được ACID (tính nguyên tử, tính nhất quán, tính cô lập, tính bền vững) trong một bảng, nhưng vẫn có thể thất bại với các lần ghi trải trên nhiều bảng.
  • Khi xử lý transaction cập nhật nhiều bảng cùng lúc, tất cả các bảng phải được cập nhật đồng thời hoặc hoàn toàn không được cập nhật.

• Tóm tắt bình luận thứ tư:

  • Đây là một bài viết cung cấp cái nhìn tổng quan rất tốt về nhiều khái niệm liên quan đến việc xây dựng cơ sở dữ liệu.
  • Bài viết đề cập từ việc tận dụng hiệu năng trên một máy đơn bằng SIMD cho đến các thuật toán đồng thuận.
  • Có nhắc đến các phương pháp hình thức áp dụng cho độ tin cậy của cơ sở dữ liệu và hệ thống phân tán.
  • Có một bài báo thú vị về cách đội ngũ Amazon S3 sử dụng TLA+ để mô hình hóa.

• Tóm tắt bình luận thứ năm:

  • Nhiều người học SQL để học về cơ sở dữ liệu, nhưng việc hiểu B-tree giúp hiểu rõ hơn điểm mạnh và điểm yếu của RDBMS.
  • Mọi người cố gắng tăng tốc cơ sở dữ liệu bằng cách thêm index, nhưng thực ra đó chỉ là che giấu vấn đề.
  • Một số vấn đề phù hợp với B-tree, nhưng nhiều vấn đề thì không.
  • SQL chỉ là giao diện truy vấn cho một hệ thống B-tree từ xa.

• Tóm tắt bình luận thứ sáu:

  • Nhiều lập trình viên đến một lúc nào đó đều trải qua giai đoạn tự tạo một cơ sở dữ liệu nhỏ của riêng mình.
  • Qua quá trình này, họ có thể học được rất nhiều về những gì không hoạt động.
  • Tự xây dựng cơ sở dữ liệu giúp tăng sự trân trọng đối với các giải pháp hiện có.
  • Việc truyền dữ liệu từ đĩa một cách nhanh chóng và đáng tin cậy là điều khó khăn.

• Tóm tắt bình luận thứ bảy:

  • Trong phiên bản Bash, tính nguyên tử có thể đạt được bằng cách sao chép tệp sang tệp tạm, sau đó chỉnh sửa và dùng sync; mv; sync.

• Tóm tắt bình luận thứ tám:

  • Đây là một thiết kế rất hay, trong đó document API giống MongoDB, cơ chế sao chép không leader giống Cassandra, và kiến trúc một core cho mỗi thread giống ScyllaDB.
  • Tất cả những điều này đều được triển khai bằng Rust.

• Tóm tắt bình luận thứ chín:

  • Cuốn sách 'Database Internals' hay một cách đáng ngạc nhiên và cung cấp một góc nhìn chuyên sâu về phần bên trong.
  • Người bình luận hỏi liệu có cuốn sách tương tự nào khác không.

• Tóm tắt bình luận thứ mười:

  • Cuốn sách 'Database Design and Implementation' cũng rất đáng đọc, với nhiều ví dụ được viết bằng Java.
  • Đối với nghiên cứu thực tế, người bình luận khuyến nghị các công trình của Andy (Pavlo), Viktor Leis, Thorsten Grust và Thomas Neumann.