Tìm hiểu bài toán đồng thuận trong hệ thống phân tán (Phần 1)
1. Mở đầu
Với sự phát triển không ngừng của ngành công nghệ trên thế giới, các hệ thống phân tán không còn trở nên xa lạ đối với chúng ta nữa. Đây là một trong những lĩnh vực nghiên cứu rộng lớn và phức tạp. Các hệ thống phân tán đó có thể lựa chọn lưu trữ cơ sở dữ liệu trên một trung tâm máy chủ cở sở dữ liệu hoặc phân phối chúng trên các máy chủ khác nhau hay còn được gọi là hệ thống cơ sở dữ liệu phân tán.
Hiện nay có nhiều cơ sở dữ liệu phân tán được ưa chuộng sử dụng như TiDB, CockroachDB, YugaByteDB,.... Các hệ thống cơ sở dữ liệu phân tán này cần đảm bảo tính nhất quán dữ liệu ở các máy chủ. Hệ thống này yêu cầu mỗi máy chủ (node) trong mạng lưới cùng đồng ý cam kết hoặc cùng hủy bỏ đối với một dữ liệu hay hành động (database transaction). Điều này được gọi là sự đồng thuận (consensus) và nó là một vấn đề rất quan trọng trong hệ thống phân tán.
Bài blog này mình sẽ trình bày về một số vấn đề gặp phải trong hệ thống phân tán và bài toán đồng thuận.
2. Các vấn đề ảnh hưởng tính nhất quán trong hệ thống phân tán
Trong hệ thống mà cơ sở dữ liệu chỉ nằm trên một máy chủ duy nhất thì ta không cần quan tâm tới vấn đề nhất quán trong dữ liệu. Nhưng trong hệ thống phân tán cơ sở dữ liệu sẽ có một số tác nhân gây ảnh hưởng đến tính nhất quán đó. Sau đây mình sẽ giới thiệu qua các vấn đề đó.
Về mặt vật lý
Bởi vì các node trong hệ thống của chúng ta được kết nối qua đường mạng, mà đường mạng thì không đáng tin cậy, nên chúng ta không thể nào đảm bảo chắc chắn cho việc truyền dữ liệu và khả năng kết nối. Các gói tin có thể bị mất, sắp xếp theo thứ tự khác lúc gửi, hoặc có thể bị nhận nhiều lần một gói tin. Hơn thế nữa ta còn có thể bị phân vùng mạng, các node bị fail-stop hoặc bị fail-recovery. Các tác nhân đó có thể dẫn đến dữ liệu ở các node bị sai lệch với nhau. Các bạn có thể tìm đọc thêm ở đây.
Bài toán các vị tướng Byzantine
Bài toán được trình bày bởi Lamport, Shostak và Pease trong một báo cáo khoa học mang tên “The Byzantine Generals Problem” vào năm 1982 , đây là một phiên bản tổng quát của bài toán Two Generals Problem.
Bài toán các vị tướng Byzantine miêu tả về một nhóm các vị tướng trong đội quân Byzantine (quân đội đế quốc Đông La Mã), tiến hành vây hãm 1 thành phố. Các vị tướng cần trao đổi để đạt được đến 1 thoả thuận về kế hoạch tấn công thành phố đó. Họ thoả thuận về việc nên tấn công hay rút lui. Một số có thể muốn tấn công, nhưng một số thì lại muốn rút lui, và nếu chỉ có một bộ phận tấn công riêng lẻ, thì họ sẽ gặp thất bại. Vấn đề ở đây là tin nhắn trao đổi giữa các vị tướng có thể bị thay đổi nội dung do kẻ giả mạo hoặc tin nhắn có thể bị mất trên đường truyền, vậy làm sao để có thể đạt được sự đồng thuận cuối cùng. Các bạn nên tìm hiểu thêm về bài toán ở đây.
Tại sao mình lại nhắc đến bài toán các vị tướng Byzantine này, vì bài toán đã đưa ra một đề bài hóc búa là làm sao đạt được sự đồng thuận trên hệ thống phân tán, mà trong đó có một số node có khả năng bị lỗi, hoặc bị bất kỳ kẻ tấn công giả mạo nào cố gắng phá hoại hệ thống. Một hệ thống phân tán có khả năng chịu lỗi Byzantine hay còn được gọi Byzantine Fault Tolerance là hệ thống có thể giải quyết được bài toán các vị tướng quân Byzantine.
3. Định lý CAP
Khi nói đến hệ thống phân tán ta không thể nào bỏ qua định lý CAP được. Nội dung định lý CAP muốn nói là trong hệ thống phân tán ta chỉ có thể có 2 trong 3 tính chất sau
- Consistency: Đảm bảo dữ liệu ở các node phải giống nhau.
- Availability: Mỗi yêu cầu đều nhận được phản hồi (thành công / thất bại). Nó đòi hỏi hệ thống phải hoạt động 100% thời gian để phục vụ các yêu cầu.
- Partition Tolerance: Hệ thống vẫn có thể phản hồi, ngay cả sau khi một số node bị lỗi.
Ta có các loại database thỏa mãn:
- Tính chất CA: đa phần là loại cơ sở dữ liệu quan hệ (Relational Database Management System) như MySQL, PostgreSQL,..
- Tính chất AP: Cassandra, Dynamo,...
- Tính chất CP: HBase, Redis, MongoDB,...
Để đảm bảo được tính chất nhất quán mạnh mẽ (consistency được định nghĩa trong CAP) trong dữ liệu khi mà hệ thống ta có thể gặp những vấn đề mà mình đã nêu trên thì chúng ta cần đến sự đồng thuận giữa các node. Những phần tiếp theo mình sẽ nói kĩ hơn về bài toán đồng thuận.
4. Bài toán đồng thuận
Đồng thuận trong hệ thống phân tán là gì ?
Khái niệm đồng thuận có nghĩa là nhiều node cùng `đồng ý/hủy bỏ` về một cái gì đó — nó có thể là một giá trị, một quá trình hành động hoặc một quyết định. Đây là một vấn đề quan trọng trong các hệ thống phân tán vì nó giúp hệ thống đạt được tính nhất quán. Một khi các node đồng ý về một giá trị, thì thỏa thuận đó là cuối cùng và nhờ đó mà dữ liệu của các máy chủ được đồng bộ. Một số node có thể thất bại hoặc không đáng tin cậy theo những cách khác nhau, vì vậy các giao thức đồng thuận phải có khả năng chịu lỗi hoặc khả năng phục hồi.
Để đạt được sự đồng thuận ta phải sử dụng đến các thuật toán. Trước khi bắt đầu nói về các thuật toán mình sẽ giới thiệu về các thuộc tính của giao thức đồng thuận (consensus protocol) cần phải có.
5. Giao thức đồng thuận
Một giao thức đồng thuận có khả năng chịu lỗi phải có các thuộc tính sau:
- Validity: Nếu một node quyết định (đọc / ghi) một giá trị, thì nó phải được đề xuất bởi một node khác trong hệ thống.
- Agreement: tất cả các node phải đồng ý về một giá trị.
- Termination: Tất cả các node cuối cùng đều phải đồng ý một giá trị sau một số bước hữu hạn.
- Integrity: Nếu tất cả các node quyết định một giá trị, thì bất kỳ node nào cũng có giá trị nói trên.
Các giao thức đồng thuận có thể được chia làm hai loại chính là dựa trên node lãnh đạo (leader node) và không có lãnh đạo. Đối với các giao thức không dựa trên lãnh đạo sẽ khó thực hiện hơn nhưng có tĩnh sẵn sàng cao hơn, nó được áp dụng trong sổ cái (ledgers) phân tán của blockchain. Trong các hệ thống cơ sở dữ liệu phân tán hiện nay đa phần sử dụng giao thức có node lãnh đạo.
Hiện nay có nhiều thuật toán đồng thuận nổi tiếng được nhiều dự án lớn áp dụng như: Paxos, Raft, 2PC, 3PC,…
Mình sẽ có những bài blog giới thiệu về thuật toán Raft và 2PC ở những bài blog sau, mời các bạn đón đọc.
6. Kết luận
Để có được một hệ thống phân tán đảm bảo tính nhất quán mạnh mẽ thì chúng ta cần phải có giải pháp đồng thuận giữa các node. Hiện nay có nhiều thuật toán đồng thuận đã giải quyết tốt vấn đề đó. Điển hình như 2 thuật toán Raft và 2PC. Các bạn có thể đọc thêm về các giải thuật khác như Paxos, 3PC.
Ở các bài blog tiếp theo mình sẽ nói về các bài toán khác xung quanh hệ thống phân tán như các Consistency model, CRDT, Replication,…
Slide thuyết trình về bài blog này các bạn có thể xem thêm ở đây.
