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

Apr 12, 2021

Những bài viết hay

What is Good Data Quality for Data Engineers? — databand.ai

Về lý thuyết, chất lượng dữ liệu là vấn đề của tất cả mọi người. Khi nó kém, nó sẽ làm suy giảm hoạt động mọi thứ từ marketing, sản phẩm, thành công của khách hàng, nhận thức về thương hiệu, ... Vậy nên, mọi người nên cùng nhau hợp tác và tuần thủ trong tất cả các quy trình xử lý dữ liệu để đảm bảo được chất lượng của data. Nhưng đó chỉ là trên lý thuyết, và rất khó để đảm bảo trong thực tiễn.

Trên thực tế, chúng ta nên cần ai đó nắm quyền xử lý vấn đề, điều tra vấn đề và nói cho người khác biết phải làm gì. Đó là chính là lúc cần đến vai trò của các Data Engineers. Mọi trong những thách thức lâu năm của Data Engineers là khi nhiều người khác nhau tham gia vào việc sử dụng dữ liệu nhưng lại có cách hiểu khác nhau về việc "dữ liệu" thực sự nghĩa là gì. Và đó không thực sự là lỗi của họ.

Trong bài viết, tác giả đưa ra những tiêu chí giúp Data Engineers đánh giá chất lượng của data. Đó là khi ta có thể thiết lập được một data pipeline có thể đảm bảo được tất cả bốn yếu tố: fitness, lineage, governance, và stability. Với các hệ thống đó, chúng ta sẽ có được dữ liệu ổn định. Với dữ liệu ổn định, ta có được các quyết định chất lượng. Nhưng chúng ta phải giải quyết được cả bốn vấn đề nêu ra:

Fitness: Dữ liệu có phù hợp với mục đích sử dụng của nó không? Dữ liệu có phản ánh thực tế không (Accuracy)? Tính Fitness có duy trì ở mức cao trong suốt vòng đời của dữ liệu không (Integrity)?
Lineage: Dữ liệu này đến từ đâu? Khi nào? Nó đã thay đổi ở đâu? Nó có nên ở đây không? Nguồn gốc dữ liệu ở đâu (Origin)? Nguồn dữ liệu có ổn định không (Source)?
Governance: Dữ liệu có thể được kiểm soát không (Data controls)? Tính riêng tư (Data privacy), bảo mật (Security) của dữ liệu, khả năng tuân thủ các quy định pháp lý (Regulation) như GDPR, CCPA, ... của hệ thống có được đảm bảo không?
Stability: Dữ liệu có đầy đủ và có sẵn trong một tần suất thích hợp không? Dữ liệu đi vào có khớp với dữ liệu đi ra (Consistency)? Dữ liệu có luôn có sẵn khi ta cần đến không (Dependability)? Dữ liệu có đến đúng giờ và up-to-date không (Timeliness)? Có sự thiên vị trong dữ liệu không (Bias)?

Overview of MySQL Alternative Storage Engines — www.percona.com

Với MySQL database, MyISAM và InnoDB là 2 storage engine phổ biến nhất, ngoài ra còn có nhiều loại storage engine ít phổ biến hơn nhưng có thể được sử dụng ở một số mục đích đặc biệt như là:

FEDERATED Storage Engine
Merge or MRG_MyISAM Engine
Blackhole Engine
CSV Engine

Bài viết sau đây giới thiệu qua về những storage engines này

JVM Garbage Collector — batnamv.medium.com

JVM garbage collector là một trong những chức năng nổi bật của ngôn ngữ Java để giúp các lập trình viên bớt lo nghĩ về việc quản lý các Objects so với với C/C++. Tuy nhiên, để lập trình các ứng dụng Java một cách hiệu quả và tránh các vấn đề memory leaks thì các lập trình viên Java thường phải hiểu cách JVM garbage collector hoạt động như thế nào.

Bài viết sau đây được tác giả Nam Vu nói cụ thể về JVM garbage collector thông qua các chủ đề như là:

Garbage collector được phân vùng như thế nào (young generation, old generation, …)?
Quá trình stop-the-world là gì?
Parallel garbage collector trong java 8 hoạt động như thế nào?
G1 garbage collector trong java 9+ hoạt động như thế nào?
Z Garbage collector (ZGC) trong java 11 hoạt động như thế nào?

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