View profile

#166 - Xử lí việc đồng thuận với mô hình lỗi Byzantine

Revue
 
 

Grokking Newsletter

April 12 · Issue #167 · View online

Tuyển tập những bài viết hay cùng sự kiện bổ ích dành cho kĩ sư phần mềm tại Việt Nam.


Những bài viết hay
What is Good Data Quality for Data Engineers? What is Good Data Quality for Data Engineers?
Overview of MySQL Alternative Storage Engines Overview of MySQL Alternative Storage Engines
JVM Garbage Collector JVM Garbage Collector
Góc Distributed System
Practical Byzantine Fault Tolerance
Trong các bài toán về hệ thống phân tán, ta trước hết phải xây dựng có giả định về mạng / máy tính trước khi thật sự giải quyết. Các giả định thường đơn giản như:
  • Một máy tính bị lỗi do bị ngừng hoạt động
  • Bỏ sót một số tin nhắn
  • Tạm thời ngưng hoạt động một thời gian sau đó hoạt động trở lại
Tuy nhiên, song song đó vẫn có một số lỗi ít tường minh và khó giải quyết hơn:
  • Máy tính có những hành vi tùy tiện không thể xác định được
  • Logic trên một node bị thay thế, từ đó không hoạt động đúng với thiết kế ban đầu. (malicious attack)
Ta có thể tóm tắt sự liên quan giữa các mô hình lỗi thông qua hình minh họa sau:
Qua đó, ta thấy Byzantine là mô hình lỗi abstract nhất. Tại sao các nhà khoa học máy tính lại rất quan tâm về vấn đê này?
  • Cho dù tính đúng đắn của thuật toán đồng thuận chính xác, nhưng rất khó đảm bảo nền tảng thực thi (hệ điều hành / phần cứng) không bị lỗi, đẫn đến nội dung message bị thay đổi; delay; nuốt mất … Hay mở rộng ra, rất nhiều tình huống ta không thể ngờ trong thực tế. Hay mỗi khi ta nâng cấp hệ thống, cũng khó đảm bảo logic mới chạy hoàn toàn đúng với mong muốn (software bug)
  • Nguy hiểm hơn, máy tính trong mạng bị thỏa hiệp từ bên thứ 3, từ đó dẫn đến các thao tác bất thường trong hệ thống. Yêu cầu này càng trở nên cấp thiết hơn, trong giai đoạn hiện tại khi mà mô hình blockchain nở rộ
Do vậy, một thuật toán đồng thuận chịu được lỗi Byzantine là thuật toán mà không có bất cứ một giả định nào cho trước về các hành vi lỗi có thể gây ra bởi các node trong mạng, và do vậy toàn bộ hệ thống có thể vận hành bình thường khi hacker có thể nắm quyền trên một số các máy.
Đây là bài toán không dễ giải quyết. Với mô hình lỗi thông thường, để có khả năng chịu được f máy tính bị lỗi, hệ thống phải có tối thiểu 2f+1 máy tính. Đây cũng là tính chất phải có trong các thuật toán đồng thuận thông thường như Raft; Paxos; ZAB; Trong mô hình lỗi Byzantine, để chịu được f máy tính bị lỗi, hệ thống phải có tối thiểu 3f+1 máy tính (một định lí đã được chứng minh). Từ đó, ta thấy chi phí xử lí cho bài toán này trở nên rất cao và các thuật toán được phát triển trước đó hầu như không khả thi trong thực tế.
Practical Byzantine Fault Tolerance được xuất bản năm 1999 là bài báo xử lí việc đồng thuận với mô hình lỗi Byzantine. Đây là bài báo đầu tiên có khả năng ứng dụng cao vì chi phí tương đối phù hợp trong lúc vận hành. Từ đó, bài báo này được sử dụng như nguồn tham khảo trong việc implement một blockchain như Tendermint; IBM’s Openchain; hay xây dựng một thuật toán chịu lỗi Byzantine khác.
Cụ thể hơn, bài báo lấy tư tưởng từ ViewStamp Replication:
  • Dùng public-key cryptography để định danh các máy tính trong mạng.
  • Dùng ý tưởng ViewStamp (tương tự như trong ViewStamp Replication), tuy nhiên thay vì chỉ có 2 phrase là Prepare và Commit, giao thức sẽ có 3 phrase: Pre-prepare / Prepare / Commit
Ta có thể tham khảo kĩ hơn cách thuật toán hoạt động trong bài báo này.
Góc Database
Đối với các hệ thống cơ sở dữ liệu phân tán hiện đại, high-availability là một trong các đặc tính khá được xem trọng thời gian gần đây, đôi lúc còn hơn cả tính consistency.
Để đạt được high-availability trong các tình huống mạng phân mảnh, nhiều hệ thống phân tán thường đi theo hướng chấp nhận dữ liệu có thể mất nhất quán trong một khoảng thời gian ngắn và tìm cách tái lập sự nhất quán bằng hai kỹ thuật phổ biến:
  • Chấp nhận conflict có thể xảy ra khi có nhiều lệnh ghi đồng thời (nhưng dữ liệu khác) trên cùng một đối tượng, và sử dụng kỹ thuật đồng hồ logic theo từng key (per-key logical clock) để sửa các conflict này.
  • Thực thi một quá trình gọi là anti-entropy để định kỳ phát hiện sai lệch và đồng bộ các dữ liệu ở các replica khác nhau thông qua Merkle Tree.
Hai kỹ thuật này đã được sử dụng khá lâu từ thời DynamoDB được phát triển (mô tả trong bài báo năm 2007 của Amazon) và cũng tồn tại một số nhược điểm như:
  • Việc xử lý conflict sử dụng đồng hồ logic theo từng key sẽ khiến cho version-vector (cấu trúc dữ liệu được sử dụng để đánh dấu sự thay đổi của dữ liệu) ngày càng phình to nếu không tìm cách thu gọn lại.
  • Việc delete dữ liệu sẽ cần phải được đánh dấu bằng tombstones, điều này khiến cho việc lưu trữ các đối tượng bị thêm/xoá lập đi lập lại nhiều lần không hiệu quả. Đồng thời cũng sẽ trở thành chướng ngại cho việc thu gọn lại vì sẽ làm mất đi tính nhân quả (casuality) của quá trình cập nhật dữ liệu.
  • Tiến trình anti-entropy sử dụng Merkle Tree cũng sẽ ngày càng thiếu hiệu quả khi cơ sở dữ liệu phình to ra. Nếu cây Merkle Tree quá nhỏ thì sẽ khó xác định được nơi dữ liệu bị mất đồng bộ. Còn nếu cây Merklee Tree quá lớn thì sẽ tốn nhiều không gian và băng thông để truyền tải các cây này. Chưa kể đến việc xác định tần suất để truyền dữ liệu qua lại giữa các cây này.
Trong bài báo này, các tác giả chia sẻ một kỹ thuật khác đó là NDC (nodewide logical framework), được thiết kế như một giải pháp thay thế cho hai kỹ thuật per-key logical clock và Merkle Tree trong quá trình đồng bộ các node dữ liệu. Kỹ thuật này được tích hợp trong một cơ sở dữ liệu nguồn mở tên là DottedDB được phát triển bởi chính các tác giả.
Mời các bạn cùng đọc bài báo để hiểu rõ hơn.
Code & Tools
This Week Sponsors
Theo đuổi sứ mệnh rút ngắn khoảng cách giữa con người, thông tin và dịch vụ, LINE đã phát triển thành nền tảng mạng xã hội với hàng trăm triệu người dùng thường xuyên trên toàn cầu, tập trung chiến lược vào thị trường châu Á vốn luôn tăng trưởng sôi động.
Là một trung tâm phát triển của Tập đoàn LINE, đội ngũ LINE Technology Vietnam đang sát cánh cùng LINE toàn cầu xây dựng và tối ưu các ứng dụng, dịch vụ đa dạng quanh hệ sinh thái LINE.
Góc Tuyển Dụng
Xem thêm các vị trí khác tại LINE Technology Vietnam
Quotes
“Don’t comment bad code. Rewrite it.”
– Brian W. Kernighan
Did you enjoy this issue?
If you don't want these updates anymore, please unsubscribe here.
If you were forwarded this newsletter and you like it, you can subscribe here.
Powered by Revue
Charmington La Pointe, 181 Cao Thang, Dist 10, Ho Chi Minh city, Viet Nam