#113 - Bài toán các vị tướng Byzantine và ứng dụng trong các hệ thống phân tán

Mar 29, 2020

Do ảnh hưởng của dịch bệnh, nên từ đầu năm nay, các hoạt động TechTalk, Workshop, InterviewDay của Grokking đã ngưng lại và sẽ chỉ mở lại sau khi dịch bệnh kết thúc.

Trong thời gian này, các hoạt động của Grokking chủ yếu trên càng nền tảng online như Webinar, Newsletter, Survey, v.v...

Cùng theo dõi và cập nhật những tin tức mới nhất và chính xác về dịch bệnh tại website của Bộ Y Tế nhé: https://ncov.moh.gov.vn/

Ngoài ra, các bạn yêu thích data có thể research thông qua tập dữ liệu covid-19 (được update mỗi ngày) được phát triển bởi team CSSE tại Johns Hopkins University. Các bạn có thể xem qua một hướng dẫn của team timescale tại đây.

Những bài viết hay

FB thiết kế Network Time Protocol (NTP) như thế nào ? — engineering.fb.com

Đồng hồ là chức năng đều có trên những thiết bị kỹ thuật số. Chức năng đồng hồ rất quan trọng với những hệ thống đòi hỏi tính chuẩn xác cao như phóng vệ tinh vào vụ trũ. Việc đồng bộ thời gian giữa những thiết bị được xử lý thông qua Network Time Protocol (NTP) và Facebook đã thiết kế NTP service với độ precision đến level sub-millisecond. Vậy họ đã làm như thế nào ?

Why the GOV.UK Design System team changed the input type for numbers — technology.blog.gov.uk

Để cung cấp cho người dùng một dịch vụ tốt, các tổ chức chính phủ thường cần thu thập rất nhiều dữ liệu. Nhóm thiết kế hệ thống của GOV.UK (website của chính phủ Anh Quốc) cung cấp những pattern và component cho phép người dùng có thể nhập dữ liệu một cách dễ dàng.

Trong đó, những con số là một trong những dữ liệu được yêu cầu nhiều nhất, đặc biệt được dùng trong việc việc thể hiện ngày tháng.

Phần lớn người dùng thích bàn phím số lớn để nhập số trên thiết bị di động. Team thiết kế của GOV.UK đã sử dụng HTML element <input type="number"> để cung cấp bàn phím số khi người dùng nhập vào ngày tháng.

Tuy nhiên gần đây, họ đã đổi qua sử dụng <input type="text" inputmode="numeric" pattern="[0-9]*"> đồng thời cung cấp một hướng dẫn làm thế nào để yêu cầu người dùng nhập vào những con số tại đây https://design-system.service.gov.uk/components/text-input/#numbers.

Talk Transcript: How Cloudflare Thinks About Security — blog.cloudflare.com

Security ở một công ty công nghệ gồm những vấn đề gì? Có phải là các thuật toán mã hóa, các giao thức bảo mật, các cuộc tấn công,... Hay còn là văn hóa, con người, là cách công ty phản ứng lại với các sự kiện bảo mật. Cùng tìm hiểu thêm qua bài talk của CTO Cloudflare.

How is the Linux kernel tested? — embeddedbits.org

Đã bao giờ bạn tự hỏi, Linux kernel đã được test như thế nào? Làm thế nào để có thể duy trì chất lượng của hàng triệu dòng code được phát triển bởi hàng ngàn lập trình viên trên toàn thế giới?

Đó chắc chắn ko phải là công việc dễ dàng nhưng không có nghĩa là không thể.

Có thể bạn chưa biết

The Byzantine Generals’ Problem

Bài toán các vị tướng Byzantine (Byzantine Generals) là một bài toán nổi tiếng trong khoa học máy tính và được ứng dụng vào trong các hệ thống phân tán.

Nội dung của bài toán này như sau:

Có N vị tướng cầm các cánh quân khác nhau xung quanh thành phố mà họ dự định tấn công. Các vị tướng cần phải thống nhất với nhau về quyết định tấn công hoặc rút lui. Do đó cần đồng thuận về một quyết định để cùng phối hợp với nhau. Các vị tướng chỉ có thể liên lạc thông qua lính truyền tin, tin tức lúc này có thể bị thất lạc hoặc giả mạo. Ngoài ra có những vị tướng phản bội, sẽ ngăn cản các vị tướng làm theo thỏa thuận bằng cách gửi đi những thông điệp gây nhiễu. Ví dụ:

– 4 tướng muốn tấn công

– 4 tướng muốn rút quân

– 1 tướng phản bội nói với nhóm thứ nhất là muốn tấn công, nói với nhóm thứ 2 là muốn rút quân

Vậy các tướng trung thành làm thế nào để có thể đạt được thỏa thuận?

Một trong những lời giải được sử dụng là thuật toán Paxos.

Thuật toán Paxos được mở rộng cho môi trường thực tế trong đó các node bị lỗi (ngẫu nhiên hoặc bị tấn công) tại các thời điểm ngẫu nhiên, hoặc là bị lợi dụng để phá hoại. Thuật toán mở rộng đó được gọi là Byzantine Paxos.

Byzantine Paxos được giới thiệu vào năm 1999 bởi Castro và Liskov (Lab of computer science, MIT), đã thêm 1 bản tin verify để kiểm tra tính đúng đắn và khả năng đồng thuận của các node trong mạng.

Thuật toán Byzantine Paxos được ứng dụng rộng rãi thông qua phiên bản thực hành và có nhiều sửa đổi phù hợp với các hành vi xảy ra trong thực tế có tên là Practical Byzantine Fault Tolerance (PBFT). Ngày nay PBFT dần được ứng dụng rộng rãi bởi vì hiện trạng ngày càng gia tăng của các vụ tấn công mạng dẫn tới tỉ lệ lỗi ở các node mạng rất cao. Các node mạng bị hiện tượng đó gọi chung là faulty node.

Đọc thêm về thuật toán Byzantine Paxoz tại đây

Đọc paper gốc về bài toán các vị tướng Byzantine tại đây

Góc Database

Tạo một bảng sử dụng Engine InnoDB trên MySQL 5.7 có cấu trúc ban đầu như sau:

Mở 2 session từ command line và thực thi song song 2 dòng lệnh như bên dưới:

Team Grokking có 2 câu hỏi dành cho bạn:

1- Tại sao ở bước số 5 lại có lỗi "Lock wait timeout exceeded;" như hình bên trái?

2- Nếu vẫn thực thi câu lệnh COMMIT ở bước số 7 thì kết quả cuối cùng sẽ như thế nào?

Các bạn nào quan tâm có thể gửi câu trả lời về cho nhóm biên tập để chia sẻ với cộng đồng trong kỳ newsletter tuần tới nhé.

Row scanned equals to 1, Is the query is optimally tuned? — mydbops.wordpress.com

Explain là cách thường dùng để đánh giá performance của một câu query trong MySQL. Tuy nhiên, trong thực tế có những tình huống khi Explain cho kết quả khá tốt (chỉ có 1 row scanned), nhưng câu query được thực thi lại rất chậm. Bài viết dưới đây chia sẻ một ví dụ như vậy.

Announcing Saved Queries

DoIt - Một hệ thống online giúp chia sẻ dataset với mô hình tương tự Git vừa cung cấp tính năng mới Saved Queries.

Code & Tools

Tin tức khác

Quote

Codes are a puzzle. A game, just like any other game. - Alan Turing