Những điều cơ bản về cơ sở dữ liệu

 (tontinton.com)
5 điểm bởi GN⁺ 2023-12-16 | 1 bình luận | Chia sẻ qua WhatsApp
  • Bắt đầu từ một kho khóa-giá trị Bash đơn giản, bài viết từng bước cho thấy vì sao cơ sở dữ liệu thực tế phải xem độ bền dữ liệu, tính nguyên tử, tính cô lập và hiệu năng là những bài toán thiết kế riêng biệt
  • fsync/fdatasync, flock, WAL là những công cụ cơ bản để bảo vệ dữ liệu trong tình huống sự cố và truy cập đồng thời, nhưng mức đảm bảo càng cao thì chi phí hiệu năng càng lớn
  • Storage engine sử dụng các cấu trúc như B-tree và LSM tree để giảm chi phí I/O đĩa và chi phí tìm kiếm, và mỗi cấu trúc lại đi kèm bảo trì như vacuum hoặc compaction
  • Cơ sở dữ liệu phân tán đổi lấy tính sẵn sàng và khả năng mở rộng theo chiều ngang bằng cách chấp nhận độ phức tạp của hệ thống phân tán như định lý CAP, phân hoạch mạng, điều phối tính nhất quán và giải quyết xung đột
  • Khi chọn hoặc triển khai cơ sở dữ liệu, cần điều chỉnh theo workload các yếu tố như đảm bảo ACID, mức cô lập, cấu trúc lưu trữ, cách sao chép và yêu cầu nhất quán

Những vấn đề cơ bản của cơ sở dữ liệu bộc lộ qua bashdb

  • bashdb là một kho khóa-giá trị đơn giản được tạo bằng hai hàm Bash
    • db_set append vào file theo định dạng key,value
    • db_get kết hợp grep, sed, tail để đọc giá trị cuối cùng
  • Dù đơn giản cho mục đích học tập, chỉ riêng cách triển khai này cũng đã làm lộ ra các vấn đề mà cơ sở dữ liệu production phải giải quyết
    • Durability: nếu máy bị crash sau khi db_set thành công, dữ liệu chưa được flush xuống đĩa có thể biến mất
    • Atomicity: nếu crash giữa lúc ghi, dữ liệu có thể chỉ được ghi một phần và bị hỏng
    • Isolation: nếu đọc và ghi đồng thời truy cập cùng một mục, phía đọc có thể chỉ thấy một phần dữ liệu
    • Performance: db_get tìm kiếm toàn bộ file theo từng dòng nên có độ phức tạp O(n)

ACID và nỗ lực cải thiện bashdb

  • ACID là từ viết tắt gộp các thuộc tính mà nhiều cơ sở dữ liệu cố gắng đảm bảo
    • Atomicity: nếu xảy ra lỗi trong lúc ghi, toàn bộ transaction sẽ bị hủy hoặc rollback để không để lại trạng thái ghi dở
    • Consistency: transaction không hợp lệ không được làm hỏng cơ sở dữ liệu
    • Isolation: không được có race condition khi truy cập đồng thời cùng một dữ liệu
    • Durability: ghi thành công phải được giữ lại ngay cả sau các tình huống như mất điện
  • Không phải mọi transaction của cơ sở dữ liệu đều nhất thiết phải đảm bảo ACID, và trong một số trường hợp sử dụng có thể giảm bớt đảm bảo để đổi lấy hiệu năng

  • Độ bền dữ liệu và fsync

    • System call write ghi buffer vào file, nhưng không có nghĩa là nó sẽ được ghi ngay lập tức vào thiết bị lưu trữ không bay hơi
    • Kernel có thể lưu buffer dưới dạng dirty page trong page cache rồi flush xuống đĩa sau đó
    • Thiết bị đĩa hoặc hệ thống RAID cũng có thể có write cache riêng
    • fsync và fdatasync là các system call dùng để flush dirty page xuống thiết bị lưu trữ bền vững
    • fdatasync flush raw buffer được truyền bởi write
    • fsync không chỉ flush dữ liệu mà còn flush cả metadata của file như mtime
    • Nếu gắn sync -d database sau db_set thì có thể tăng độ bền dữ liệu với hành vi gần với fdatasync, nhưng thông thường sync chậm hơn chính thao tác write nên làm giảm hiệu năng
    • Việc fsync() thành công có nghĩa là “mọi lệnh write kể từ lần fsync trước đó đã tới đĩa”, chứ không chỉ là “các lệnh write sau lần fsync thành công gần nhất”
    • PostgreSQL đã gặp vấn đề này vào năm 2018 và đổi cách hoạt động sang panic khi fsync thất bại thay vì retry
    • Sự việc này được biết đến với tên fsyncgate, và có liên kết đến bài báo về fsync failures
    • MongoDB mặc định sync thao tác ghi mỗi 100ms, nên không đạt độ bền dữ liệu 100%

  • Tính cô lập và flock

    • Cách cô lập đa tiến trình đơn giản nhất trong bashdb là đặt lock lên file lưu trữ trước khi đọc hoặc ghi
    • flock trên Linux khóa file, và nếu dùng cờ -s thì nhiều reader có thể cùng đọc bằng shared lock
    • bashdb được cải tiến dùng exclusive lock cho ghi và shared lock cho đọc
    • Nhược điểm là mỗi lần ghi đều khóa toàn bộ cơ sở dữ liệu
    • Rất khó để đảm bảo tính nguyên tử một cách đơn giản chỉ với Bash, và tuy có thể dùng mv -T hoặc rename nhưng phần này chưa được hoàn thiện
    • bashdb vẫn chưa giải quyết được vấn đề truy vấn O(n)

Vai trò của storage engine và các nút thắt cổ chai

  • Storage engine cung cấp lớp trừu tượng để đọc và ghi dữ liệu vào bộ nhớ lưu trữ bền vững, với mục tiêu chính là thông lượng cao và độ trễ thấp
  • Ràng buộc lớn nhất đến từ sự chênh lệch tốc độ của chính đĩa
    • Trong bảng độ trễ ví dụ, truy cập L1 cache khoảng 0.5ns, đọc ngẫu nhiên 4KB từ SSD là 150,000ns, còn disk seek là 10,000,000ns
    • Nếu coi một lần truy cập L1 cache tương đương nhịp tim khoảng 0,5 giây, thì đọc tuần tự 1MB từ SSD sẽ tương đương khoảng 12 ngày, còn đọc tuần tự 1MB từ đĩa sẽ tương đương khoảng 8 tháng
  • Vì vậy, thiết kế storage engine phát triển theo hướng giảm tối đa I/O đĩa và disk seek
  • Các yếu tố thiết kế phổ biến của storage engine gồm
    • cấu trúc dữ liệu cơ bản để lưu mục trên đĩa
    • transaction ACID
    • cache để giảm số lần đọc đĩa
    • lớp API như SQL, document, graph
  • Cấu trúc dữ liệu của storage engine có thể chia lớn thành cấu trúc có thể thay đổi và cấu trúc bất biến
    • Cấu trúc có thể thay đổi cho phép ghi đè dữ liệu đã ghi vào file sau này
    • Cấu trúc bất biến chỉ đọc lại dữ liệu đã ghi vào file

B-tree có thể thay đổi

  • Để vẫn giữ hiệu năng tốt khi dữ liệu tăng lên, thay vì tìm kiếm tuyến tính như bashdb, cần có khả năng tìm mục trong thời gian tối đa là logarit
  • BST có thể truy vấn O(log n), nhưng nếu các node nằm xa nhau trên đĩa thì quá trình duyệt có thể phát sinh nhiều disk seek
  • B-tree là dạng tổng quát của BST, trong đó một node có thể có nhiều hơn hai node con, và tận dụng spatial locality
    • Trên đĩa thường đọc một page 4KB hoặc 8KB, rồi so sánh tuần tự nhiều node bên trong page đó bằng bộ nhớ và CPU cache
    • Vì truy cập bộ nhớ và CPU cache nhanh hơn đĩa nhiều bậc độ lớn, điều quan trọng là tận dụng tối đa các byte đã đọc từ đĩa
  • Truy cập bộ nhớ tuần tự có thể rất mạnh nhờ SIMD, instruction pipelining và prefetching
  • B+ tree chỉ lưu giá trị ở leaf node, còn các node khác chỉ lưu key, nhờ đó có thể so sánh được nhiều key hơn trong một page đĩa

  • Thu hồi không gian và vacuum

    • B-tree cần thu hồi khoảng trống sinh ra do phân mảnh dữ liệu để tối ưu không gian
    • Nếu cập nhật bằng giá trị lớn hơn, nó có thể đè lên dữ liệu của node tiếp theo nên mục đó phải được chuyển sang vị trí khác và để lại lỗ hổng trong page gốc
    • Nếu cập nhật bằng giá trị nhỏ hơn, sẽ để lại khoảng trống ở phần cuối
    • Xóa dữ liệu tạo ra lỗ hổng tại vị trí của giá trị đã bị xóa
    • Quá trình thu hồi không gian và ghi lại page này có thể được gọi là vacuum, compaction, page defragmentation hoặc maintenance
    • Thường được thực hiện ở chế độ nền để tránh spike độ trễ của request người dùng
    • PostgreSQL có thể cấu hình auto vacuum daemon
    • B-tree thường được dùng làm cấu trúc nền cho index, chẳng hạn như index mặc định của PostgreSQL, và DynamoDB từng được đùa là một “distributed B-tree”

LSM tree bất biến

  • LSM tree là một cấu trúc dữ liệu append-only xuất phát từ thực tế disk seek rất tốn kém
  • Nếu chỉ thêm dữ liệu vào cuối file thì đầu đọc/ghi của đĩa ít phải di chuyển xa đến vị trí ghi tiếp theo, nên có lợi cho các workload nhiều ghi
  • Log Structured Merge tree, viết tắt là LSM tree, được dùng trong các storage engine cơ sở dữ liệu hiện đại như RocksDB, Cassandra, ScyllaDB
  • Cơ chế hoạt động cơ bản như sau
    • Buffer các ghi vào một cấu trúc dữ liệu có thể sắp xếp trong bộ nhớ
    • Ví dụ là AVL tree, Red Black tree, Skip List
    • Khi đạt đến một dung lượng nhất định thì flush thành file đã sắp xếp là Sorted String Table, tức SSTable
  • SSTable lưu dữ liệu đã sắp xếp nên có thể giảm disk I/O bằng binary search và sparse index
  • Để bảo đảm độ bền, các thao tác đã ghi vào bộ nhớ sẽ được ghi vào Write-Ahead Log, tức WAL
    • Khi chương trình khởi động, nó đọc WAL để khôi phục về trạng thái trước khi thoát hoặc crash
  • Xóa cũng được append giống như ghi bình thường, và lưu tombstone thay vì giá trị
    • tombstone sẽ bị loại bỏ trong quá trình compaction

  • Đọc và compaction trong LSM tree

    • Việc đọc trong LSM tree trước tiên tìm trong cấu trúc dữ liệu bộ nhớ, nếu không có thì duyệt các SSTable trên đĩa theo thứ tự từ file mới nhất đến file cũ nhất
    • Càng nhiều ghi thì số SSTable cần kiểm tra càng tăng
    • Dù mỗi file đều được sắp xếp, việc rà qua nhiều file nhỏ có thể chậm hơn so với xem một file lớn duy nhất
    • Biểu thức so sánh là log(num_files * table_size) < num_files * log(table_size)
    • compaction là tác vụ nền gộp nhiều SSTable nhỏ thành một SSTable lớn và loại bỏ tombstone
    • RocksDB triển khai Leveled Compaction
    • SSTable mới được flush sẽ nằm ở level 0
    • Khi số file tích lũy trong một level đạt ngưỡng cấu hình, sau compaction file mới sẽ được nâng lên level tiếp theo
    • Việc loại bỏ tombstone cần được xử lý cẩn thận
    • Có thể phát sinh vấn đề data resurrection, khi mục đã xóa sống lại trong quá trình compaction với các file cũ hơn
    • RocksDB giữ lại tombstone cho đến lần compaction nâng lên level cuối cùng
    • Ví dụ thực tế bằng Rust được liên kết tại mã LSM tree của dbeel

  • Bloom filter

    • Bloom filter là một cấu trúc dữ liệu tập hợp xác suất giúp kiểm tra hiệu quả rằng một phần tử không có trong tập hợp
    • Kết quả tra cứu có hai loại
      • false: phần tử chắc chắn không có trong tập hợp
      • true: phần tử có thể có trong tập hợp
    • Bloom filter ánh xạ kết quả của nhiều hash function vào các vị trí bit của bitmap và đặt chúng thành 1
    • Độ phức tạp không gian được nêu là O(log n) thay vì O(n) của set thông thường
    • Có thể điều chỉnh “xác suất chắc chắn là không có” bằng cách cấp phát thêm bộ nhớ bitmap và tăng số lượng hash function, đồng thời cũng có công cụ tính
    • LSM tree lưu Bloom filter cho từng SSTable, nhờ đó có thể bỏ qua việc tìm kiếm trong các SSTable đã xác định là không có key cụ thể

WAL và bảo đảm giao dịch

  • WAL là cách ghi mọi thao tác giao dịch vào một file đặc biệt để sống sót qua các crash đột ngột
  • Khi tiến trình cơ sở dữ liệu khởi động, nó đọc file WAL và tái tạo lại trạng thái dữ liệu
    • Các giao dịch không có commit log sẽ bị bỏ qua, nhờ đó đạt được tính nguyên tử
  • Nếu dữ liệu của yêu cầu ghi được ghi vào WAL và flush trước khi phản hồi cho người dùng, thì khi khởi động nó chắc chắn có thể được đọc lại, nhờ đó đạt được tính bền vững
  • WAL có thể được xem là một dạng event sourcing đối với các sự kiện giao dịch

Mức cô lập và kiểm soát đồng thời

  • Có thể chia các cách đạt được tính cô lập thành ba loại lớn
    • khóa bi quan: chặn truy cập vào dữ liệu đang được ghi
    • khóa lạc quan: sửa trên bản sao dữ liệu, rồi chỉ commit khi dữ liệu gốc không thay đổi trong suốt giao dịch, nếu không thì retry
    • MVCC: không ghi đè dữ liệu mà tạo version mới, để mỗi người dùng nhìn thấy snapshot tại một thời điểm cụ thể
  • Không phải mọi ứng dụng đều cần cô lập hoàn toàn, tức serializable isolation
  • ANSI/ISO SQL 92 phân loại thành ba kiểu kết quả có thể xảy ra khi giao dịch khác thay đổi cùng dữ liệu trong lúc một giao dịch đang chạy
    • Dirty read: đọc cập nhật từ một giao dịch khác chưa commit
    • Non-repeatable read: giữa hai lần đọc cùng một row, một giao dịch khác đã commit nên giá trị thay đổi
    • Phantom read: giữa hai lần đọc tập row theo cùng điều kiện, có row bị thêm vào hoặc bị xóa đi
  • Các mức cô lập ANSI/SQL 92 theo thứ tự từ cao xuống thấp như sau
    • Serializable: chỉ đọc dữ liệu đã commit và tránh phantom read, kể cả với ghi nhiều row dựa trên phạm vi
    • Repeatable reads: cho phép phantom read
    • Read committed: cho phép non-repeatable read
    • Read uncommitted: cho phép dirty read
  • Mức cô lập cao thường đi kèm đánh đổi về hiệu năng
  • Mức cô lập ANSI/SQL 92 bị chỉ trích là chưa hoàn chỉnh
    • Nhiều triển khai MVCC cung cấp snapshot isolation thay vì serializable isolation
    • HyPer được khuyến nghị như một thuật toán MVCC serializable nhanh

Vì sao cần hệ phân tán và CAP

  • Hệ phân tán làm tăng thêm rất nhiều độ phức tạp, nên nên tránh nếu giải pháp không phân tán là đủ
  • Có hai lý do phổ biến để phải phân tán dữ liệu trên nhiều máy
    • Tính sẵn sàng (Availability): ngay cả khi máy cơ sở dữ liệu bị crash hoặc mất kết nối với người dùng, vẫn có thể gửi yêu cầu sang máy khác
    • Mở rộng theo chiều ngang (Horizontal Scaling): thay vì vertical scaling lên một máy đơn lớn hơn, cho nhiều máy nối mạng hoạt động như một máy duy nhất
  • Hệ phân tán đưa vào độ phức tạp vận hành và vấn đề network partition
  • Định lý CAP nói rằng hệ thống chỉ có thể bảo đảm hai trong ba đặc tính sau
    • Consistency: lượt đọc nhận được lượt ghi mới nhất
    • Availability: mọi yêu cầu đều thành công bất kể lỗi xảy ra
    • Partition Tolerance: hệ thống tiếp tục hoạt động ngay cả khi có mất mát hoặc độ trễ thông điệp giữa các node
  • Cơ sở dữ liệu một máy không có network partition và có tính nhất quán, nhưng khi máy gặp sự cố thì các yêu cầu mới sẽ thất bại, vi phạm availability
  • Nếu hai máy có CPU, bộ nhớ và đĩa riêng, được nối với nhau bằng cáp, thì trong tình huống sự cố sẽ phải chọn một trong hai hướng
    • Nếu hủy yêu cầu thì hy sinh availability để giữ consistency
    • Nếu tiếp tục xử lý yêu cầu chỉ trên máy còn hoạt động thì hy sinh consistency để giữ availability
  • Những hệ thống hy sinh consistency và đồng bộ lại sau này được gọi là eventually consistent
  • Network partition cũng khiến JOIN hiệu quả trở nên khó khăn vì phải gom dữ liệu nằm rải rác trong cụm, và phía NoSQL khuyến nghị denormalization để giảm nhẹ điều này

Sao chép và trường hợp Amazon Dynamo

  • Bài báo Dynamo gốc của Amazon được giới thiệu như một trường hợp mà availability được xem là quan trọng hơn consistency đối với giỏ hàng trên amazon.com
    • Nếu người dùng thấy cùng một sản phẩm xuất hiện hai lần trong giỏ hàng thì chỉ cần xóa một cái
    • Đây được xem là tốt hơn so với tình huống hoàn toàn không thể mua hàng
  • Để có được availability, chỉ việc nhiều node chia nhau dữ liệu là chưa đủ; mỗi mục còn phải có ít nhất một bản sao trở lên
  • Node lưu bản sao của mục là replica, còn quá trình sao chép là replication
  • Tăng số lượng replica sẽ cải thiện availability, nhưng cũng cần nhiều tài nguyên hơn để lưu các bản sao
  • Bản sao dữ liệu không nhất thiết phải được lưu nguyên khối; chúng cũng có thể được chia bằng erasure coding và phân tán trên nhiều node, với đặc tính độ trễ liên quan được nói tới trong bài viết về erasure coding

Consistent Hashing và phân bố dữ liệu

  • Khi có nhiều node, cần một cách cân bằng tải hoặc phân vùng dữ liệu để quyết định node nào sẽ xử lý yêu cầu lưu trữ
  • Cách đơn giản là băm primary key rồi lấy modulo theo số lượng node
    • Khi node được thêm vào hoặc bị loại bỏ, len(nodes) thay đổi nên cùng một key sẽ trỏ sang node khác
    • Trong trường hợp này gần như phải di chuyển toàn bộ mục dữ liệu, nên chi phí rất lớn
  • Consistent Hashing đặt node lên một ring thay vì một mảng, để giảm số mục phải di chuyển khi thêm hoặc bớt node
    • Được dùng trong các cơ sở dữ liệu như Dynamo và Cassandra
  • Trong consistent hashing, hash của tên node được đặt lên ring, và node gặp đầu tiên sau hash của key yêu cầu sẽ trở thành chủ sở hữu
  • Việc chọn replica có thể thực hiện bằng cách đi ngược chiều kim đồng hồ trên ring và lưu bản sao vào các node tiếp theo
    • Nếu node sở hữu bị chết, các node replica sẽ xử lý yêu cầu để duy trì availability
    • Cách này được gọi là Leaderless Replication, và được dùng trong các cơ sở dữ liệu kiểu Dynamo như Cassandra
  • Số key phải di chuyển khi thêm node trung bình là num_keys / num_nodes
  • Virtual node đặt một node vật lý lên ring nhiều lần để giảm khả năng một số node sở hữu quá nhiều mục hơn các node khác
    • Ví dụ là thêm hậu tố chỉ số vào tên node như "half-0", "half-1"
  • Một cách khác để chọn leader node và replica node là leader election, nhưng ở đây không bàn tới

Leaderless Replication và điều chỉnh tính nhất quán

  • Cấu hình leaderless đánh đổi consistency để đạt availability cao
  • Nếu node sở hữu đang down tại thời điểm có yêu cầu write, dữ liệu sẽ được ghi vào replica, và sau khi node sở hữu hoạt động lại thì yêu cầu read có thể đọc phải dữ liệu cũ
  • Nếu cần consistency cho một yêu cầu cụ thể, có thể gửi song song yêu cầu read tới nhiều replica và node sở hữu, rồi client chọn dữ liệu mới nhất
  • Yêu cầu write thường được gửi song song tới tất cả replica, nhưng chỉ chờ acknowledgement từ một phần node
  • Để điều chỉnh consistency ở mức yêu cầu, kiểm tra điều kiện R + W > N/2 + 1
    • N: số node có bản sao dữ liệu
    • W: số node phải acknowledgement để write thành công
    • R: số node phải phản hồi để read thành công
  • Yêu cầu tới đa số node, tức W hoặc R bằng N/2 + 1, được gọi là quorum

  • Giải quyết xung đột

    • Quá trình chọn write mới nhất được gọi là Conflict Resolution
    • Chỉ so sánh timestamp là cách khó đáng tin cậy trong hệ thống phân tán
    • Mỗi máy có hardware clock riêng, và clock không hoàn toàn chính xác nên sẽ có drift
    • NTP lấy thời gian từ nguồn chính xác hơn, nhưng bản thân yêu cầu cũng đi qua mạng nên không thể biết chính xác mất bao lâu để nhận được phản hồi
    • Cassandra dùng timestamp, tài liệu liên quan nằm ở Cassandra data versioning
    • Google Spanner đạt được bảo đảm consistency dựa trên clock bằng phần cứng thời gian độ chính xác cao chuyên dụng và API phơi bày phạm vi bất định của timestamp; bài báo liên quan là Spanner paper
    • Các hệ thống như Dynamo dùng Version Vectors để giảm một phần xung đột
    • Mỗi version của mục gắn một cặp (node, counter) để tìm quan hệ nhân quả giữa các version
    • Có thể tìm ra version chắc chắn mới hơn để loại bỏ một số giá trị cũ
    • Tài liệu chi tiết hơn được liên kết tại Dotted Version Vectors
    • Cũng có thể như Riak KV, trả về toàn bộ các giá trị xung đột cho ứng dụng, rồi để ứng dụng giải quyết dựa trên hiểu biết về dữ liệu
    • Nhiều kỹ thuật giảm xung đột trong hệ thống eventually consistent thường được gộp dưới thuật ngữ Anti Entropy

Các kỹ thuật Anti Entropy

  • Read Repair

    • Sau khi client chọn giá trị mới nhất từ kết quả read của nhiều node, nó sẽ gửi lại giá trị đó tới những node chưa lưu để repair

  • Hinted Handoff

    • Nếu yêu cầu write không đến được node đích, nó sẽ được lưu dưới dạng hint ở node khác
    • Khi node đích available trở lại, hint đã lưu sẽ được chuyển đi
    • Trong quorum write, cách này còn được gọi là Sloppy Quorum, giúp tăng thêm availability của yêu cầu quorum

  • Merkle Trees

    • Read repair chỉ sửa dữ liệu đã được truy vấn, nên nhiều dữ liệu có thể vẫn không nhất quán trong thời gian dài
    • Việc các node đồng bộ với nhau để tìm toàn bộ khác biệt sẽ tốn kém O(n) khi dữ liệu nhiều
    • Merkle tree là cấu trúc phân cấp trong đó hash của các dải dữ liệu được lưu ở leaf, còn node cha lưu hash kết hợp từ hash của các node con
    • Nếu root hash giống nhau thì dữ liệu ở hai node là giống nhau; nếu khác thì so sánh đệ quy các hash cấp dưới để tìm dữ liệu không khớp, nhờ đó có thể tăng tốc đồng bộ xuống O(log n)

  • Gossip Dissemination

    • Đây là cách lan truyền sự kiện tới toàn bộ cluster một cách đơn giản và đáng tin cậy
    • Node gửi thông điệp tới một số node ngẫu nhiên được cấu hình sẵn, tức fanout, và node nhận được lại gửi tiếp cho N node ngẫu nhiên
    • Khi đã thấy cùng một thông điệp gossip đủ số lần được cấu hình, node sẽ không broadcast nữa
    • Có liên kết tới simulator để cảm nhận quá trình hội tụ dữ liệu
    • Thông điệp gossip thường được truyền bằng UDP

Các mảng có thể đào sâu hơn

  • Trong cơ sở dữ liệu còn rất nhiều chủ đề ngoài những nội dung đã nói ở đây
    • Sử dụng O_DIRECT của Linux và tự triển khai page cache
    • failure detection trong hệ thống phân tán
    • Thuật toán consensus như Raft
    • distributed transaction
    • leader election
  • Khi chọn hoặc triển khai cơ sở dữ liệu, cần xem cùng lúc storage engine, ACID, mức cô lập, sao chép phân tán và cách giải quyết xung đột có phù hợp với yêu cầu thực tế hay không

Bài viết liên quan

1 bình luận

 
GN⁺ 2023-12-16
Ý kiến trên Hacker News

  • Có lỗi trong phương thức compact: tombstone chỉ nên được bỏ qua khi nén cấp cuối cùng, tức cấp lớn nhất, chứ không được loại bỏ giữa mọi cấp
    Nếu không, tombstone ở cấp trên sẽ biến mất trong quá trình nén, khiến các entry ở cấp dưới lộ ra trở lại
    Trong cơ sở dữ liệu dựa trên LSM, việc bản ghi xóa/tombstone tồn tại lâu là một trong những đặc tính; một số cơ sở dữ liệu như RocksDB đưa vào các tối ưu hóa để tránh điều này

    • Đúng, trong bài viết đã cố ý bỏ qua để ngắn gọn, còn trong dbeel thì có xử lý
    • Mình tò mò RocksDB thực hiện tối ưu hóa nào
      Mình biết về tính năng xóa theo phạm vi, nhưng không nhớ đã đọc nhiều về xóa khóa đơn lẻ

  • Nhiều người học cơ sở dữ liệu thông qua SQL, nhưng tôi khuyên nên học theo cách tham gia các lớp kiểu này và hiểu B-tree
    Phần lớn ưu và nhược điểm của RDBMS có thể hiểu được khi biết B-tree và tác động của nó lên việc chèn khóa, truy vấn, sắp xếp
    Nhiều người cố làm cơ sở dữ liệu nhanh hơn bằng cách thêm index, nhưng rốt cuộc đó chỉ là đặt thêm một cây khác lên trên cây, che khuất vấn đề cốt lõi
    Một số bài toán rất hợp với B-tree, nhưng rất nhiều bài toán thì không
    SQL chỉ là giao diện truy vấn cho một hệ thống B-tree từ xa

    • Như vậy là quá quy giản
      B-tree không phải chiến lược lập chỉ mục duy nhất, và việc index là công cụ để tăng hiệu năng đọc bằng cách hy sinh hiệu năng ghi cũng là điều đã biết rõ
      Vì nói chung cơ sở dữ liệu xử lý đọc nhiều hơn ghi rất nhiều
      Tôi tò mò “đặt thêm một cây khác lên trên cây” đang che khuất chính xác vấn đề gì, và sẽ giải quyết thế nào mà không động đến index
      Với các bảng có kích thước vừa phải, index gần như là bắt buộc
    • Tôi đồng ý với ý này
      Cần học những thứ như B-tree và hash index, tầng I/O, mô hình tiến trình
      Ngày nay, các chiến lược phổ biến của cơ sở dữ liệu hướng cột cũng đáng học: materialize tuple muộn, thực thi trì hoãn, quét tuyến tính và tìm kiếm nhị phân, pipeline lệnh, v.v.
      Khi quen với những thứ này, trong thực tế bạn sẽ nhận ra có những lúc không cần DBMS, mà chỉ cần flat file đơn giản hoặc cơ sở dữ liệu nhúng như RocksDB là đủ
    • Có thể là B-tree, cũng có thể là LSM-tree, trie, hoặc một cấu trúc index khác phù hợp với tình huống
      Tất nhiên cũng có thể có covering index
    • Sẽ hay hơn nếu giải thích phần “đặt thêm một cây khác lên trên cây nên che khuất vấn đề” bằng một ví dụ cụ thể

  • Với lời khuyên “nếu giải pháp không phân tán là đủ, hãy tránh hệ thống phân tán”, tôi muốn nói ngược lại
    Mọi hệ thống vận hành không tầm thường đều là hệ thống phân tán
    Tối thiểu, nếu cơ sở dữ liệu là một replica set thì nó đã là hệ thống phân tán, nên không học hệ thống phân tán là chấp nhận rủi ro
    https://jepsen.io/ và https://raft.github.io/ rất đáng xem

    • Một số phần của hệ thống có thể không tránh được các lệnh gọi qua mạng hoặc khía cạnh phân tán
      Nhưng điều đó không có nghĩa là đưa nó vào mọi nơi cũng ổn; làm vậy sẽ làm tăng độ phức tạp lớn hơn mức cần thiết
    • Trước hết cần định nghĩa “hệ thống vận hành không tầm thường”
      Nói như vậy không phản bác được lời khuyên hãy tránh độ phức tạp không cần thiết. Trọng tâm không phải là về mặt kỹ thuật có phân tán hay không, mà là có thật sự cần hay không
      Học hệ thống phân tán và sử dụng chúng là hai chuyện khác nhau
      Điều quan trọng là sau khi học, có đủ kiềm chế để chỉ áp dụng vào nơi phù hợp hay không
      Ngày nay thường có nhiều nỗ lực lớn để chuyển các hệ thống đơn giản, đang chạy tốt sang mô hình phân tán mạnh hơn, như thể chi phí gần như bằng không
      Nhưng nhìn vào vấn đề và quy mô cần giải quyết, có những trường hợp rõ ràng chỉ một instance Postgres đơn và một monolith là đủ
      Lời khuyên trong bài gốc có vẻ mang ý đó
    • Trong bong bóng HN thì có thể đúng, nhưng từ góc nhìn doanh nghiệp trung bình thì hoàn toàn không phải vậy
      Ít nhất là không nhất thiết phải như vậy
    • Hệ thống phân tán/dư thừa không phải là backup
      Tôi vẫn sẽ khuyên chọn giải pháp đơn giản
      Các hệ thống thường không lưu, sao lưu và khôi phục đúng trạng thái bền vững ngay cả với “kho lưu trữ tầm thường và đơn giản”
      Cố khôi phục trạng thái của kho lưu trữ phân tán trong tình huống khắc phục thảm họa còn khó hơn
      Có một giải pháp backup hoạt động được trước, rồi sau đó chọn giải pháp phân tán cũng chưa muộn
    • Khó gọi failover replica là hệ thống phân tán
      Cấu hình master có replica chỉ đọc cũng khác với “phân tán” theo cách mọi người thường nói, vì ghi không được phân tán
      Trong thực tế, phân tán thường có nghĩa là dữ liệu được sharding, và đó là phần nhất định muốn tránh nếu thật sự không cần

  • Bài viết lướt qua khá tốt nhiều khái niệm liên quan khi xây dựng cơ sở dữ liệu, nên đọc rất thú vị
    Nó bao quát từ SIMD để vắt hiệu năng trên một máy đơn cho đến thuật toán đồng thuận
    Nhân nói về cơ sở dữ liệu, độ tin cậy và hệ thống phân tán, cũng đáng đọc thêm về phương pháp hình thức có thể áp dụng cho các tình huống này và cho triển khai nội bộ của cơ sở dữ liệu
    Có một bài báo thú vị của nhóm S3 về việc mô hình hóa bằng TLA+
    [0] Use of Formal Methods at Amazon Web Services
    https://lamport.azurewebsites.net/tla/formal-methods-amazon....
    [1] How Amazon Web Services uses formal methods
    https://www.amazon.science/publications/how-amazon-web-servi...

  • 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
    Ví dụ, ở phạm vi một bảng có thể đạt được tính nguyên tử, tính cô lập và tính bền vững, nhưng có thể thất bại khi ghi trên nhiều bảng
    Khi bắt đầu xử lý các transaction cập nhật đồng thời nhiều bảng, tính nhất quán trở nên quan trọng
    Tất cả các bảng phải được cập nhật cùng lúc, hoặc không bảng nào được cập nhật

    • Ví dụ hay, tôi sẽ đưa vào bài viết

  • Thiết kế “có document API như MongoDB, leaderless replication như Cassandra, kiến trúc thread-per-core như ScyllaDB” rất tuyệt
    Hơn nữa, tất cả đều được viết bằng Rust

  • Giai đoạn “sách đã khơi gợi sự tò mò nên tôi tự tay làm một cơ sở dữ liệu nhỏ” có vẻ là điều mà rất nhiều lập trình viên đều trải qua ít nhất một lần
    Tôi sẽ không cố ngăn cản. Tự làm thử sẽ học được rất nhiều về những gì không hoạt động
    Nếu có thể dành thời gian, đó là một bài học cực kỳ giá trị
    Việc tự mình làm một cơ sở dữ liệu đã khiến tôi tôn trọng các giải pháp hiện có hơn bao giờ hết
    Ghi và đọc byte trên đĩa thật nhanh không phải là phần khó
    Điều thực sự khó là hỗ trợ những use case mà ta chưa từng tưởng tượng tới, đồng thời vận hành ổn định trong nhiều năm

    • Tôi thường tự hỏi trong độ phức tạp của DBMS hiện đại, có bao nhiêu phần đến từ các ràng buộc do use case của một miền nghiệp vụ cụ thể tạo ra
      Nếu thiết kế một DBMS chuyên biệt theo miền với giả định rằng các use case ngoài miền đó bị cấm và có thể bỏ qua, ta có thể đạt được hiệu quả như thế nào?
      Ví dụ, hiện nay ta vẫn dùng cơ sở dữ liệu đa dụng ngay cả cho các dataset về bản chất là chỉ-append
      Sẽ ra sao nếu có một cơ sở dữ liệu hoàn toàn không có khái niệm cập nhật hay xóa các hàng hiện có, chỉ có chèn và xóa toàn bộ bảng/dataset?
      Cơ sở dữ liệu như vậy có cần triển khai transaction MVCC không? Vì mỗi bảng chính là write-ahead log, liệu có thể tránh một write-ahead log riêng không? Có thể lưu trữ hiệu quả hơn không? Có thể giảm khóa bằng cách làm cho indexing có tính nguyên tử theo đơn vị chunk thay vì nguyên tử theo toàn bộ bảng không?

  • Chẳng phải tính nguyên tử của phiên bản Bash có thể đạt được “đơn giản” bằng cách sao chép file sang file tạm, chỉnh sửa rồi dùng sync; mv; sync sao?

    • Trong lúc sao chép cũng có thể tránh trùng lặp bằng bộ lọc grep ngược
      Nhân tiện sao chép thì cũng có thể đảm bảo sắp xếp, nhưng làm vậy chỉ với “bash” và các tiện ích cơ bản có vẻ không hợp lý lắm
      Cho mục đích đó có CDB của DJB, tức cdbget, cdbmake, v.v.:
      https://cr.yp.to/cdb.html
    • Đúng, tôi sẽ thêm sau

  • Bài viết rất hay
    Cuốn Database Internals trông có vẻ hay; còn cuốn nào tương tự đào sâu vào triển khai nội bộ không?

    • Không phải sách, nhưng tôi khuyên nên xem các bài giảng môn cơ sở dữ liệu do nhóm @apavlo của CMU đăng lên
      https://www.youtube.com/c/cmudatabasegroup
      Cả lớp nhập môn lẫn nâng cao đều có online, và còn có các bài trình bày/bài giảng về sản phẩm trong ngành
      Rất hữu ích
      Nếu muốn tài liệu ở góc nhìn khoa học máy tính lý thuyết cấp cao hơn và ít tập trung vào triển khai vật lý hơn, cuốn “Alice”, tức “Foundations of Databases”, rất xuất sắc
      Sách rất cô đọng và mang tính toán học, nhưng bàn về đại số quan hệ, Datalog, cũng như việc chuyển Datalog thành đại số quan hệ
      Sách giấy giờ khó kiếm; cuốn tôi mua cũ thì gáy đã hỏng và các trang bị rơi ra, nhưng toàn bộ sách có trên mạng: http://webdam.inria.fr/Alice/
    • Cũng có một tài liệu nổi tiếng tập trung vào Postgres: https://www.interdb.jp/pg/
    • Với dạng tổng quan tương tự, bài báo này rất hay:
      https://dsf.berkeley.edu/papers/fntdb07-architecture.pdf
    • Cuốn Database Management Systems của Raghu Ramakrishnan cũng rất hữu ích
      Tuy nhiên Database Internals hiện đại hơn

  • Tôi thích việc bài viết không thần bí hóa “cơ sở dữ liệu”, mà bắt đầu bằng cách cho thấy một triển khai tầm thường chỉ bằng một dòng Bash
    Một phần mở đầu tuyệt vời