#147 - Giải thưởng Dijkstra và định lý FLP-Impossibility

Nov 15, 2020

Những bài viết hay

How we designed Dropbox’s ATF - an async task framework — dropbox.tech

Asynchronous tasks như là gửi email xác nhận hay phục hồi mật khẩu hay xóa dữ liệu người dùng đều là những tác vụ phổ biến trong tất cả sản phẩm. Do đó, asynchronous task framework (ATF) thường được tạo ra ở những công ty phần mềm để đáp ứng được nhu cầu xử lý và vận hành những asynchronous tasks trên. Tuy nhiên, có khá là ít tài liệu trên mạng nói về cách các công ty lớn phát triển và scale hệ thống asynchronous task framework của họ như thế nào.

Các đội ngũ kỹ sư ở Dropbox phải phát triển hệ thống này để đáp ứng nhu cầu xử lý 10k asynchronous tasks mỗi giây. Tuy nhiên, trong lúc design và research hệ thống, họ thấy rằng rất khó kiếm tài liệu tham khảo cho ATF ở trên mạng từ những công ty . Do đó, sau khi thiết kế và đưa hệ thống ATF của họ lên production, các đội ngũ kỹ sư ở Dropbox đã quyết định chia sẽ hệ thống ATF của họ trên blog.

Bài viết sau đây giới thiệu về cách Dropbox thiết kế hệ thống ATF của họ như thế nào để đáp ứng được nhu cầu xử lý cao đó của họ. Mặc dù thiết kế của hệ thống ATF này của Dropbox không quá phức tạp và cũng không có những đột phá gì, chúng ta vẫn có thể học hỏi thêm cách scale hệ thống ATF của mình như thế nào nếu cần phải đáp ứng 10k tác vụ mỗi giây bằng việc hiểu rõ hơn cách phát triển và những kinh nghiệm vận hành trong hệ thống ATF của Dropbox qua 7 components chính:

Frontend
Task Store
Store Consumer
Queue
Controller
Executor
Heartbeat and Status Controller (HSC)

Góc Distributed System

Hadoop, Kafka, Kubernetes sử dụng ZooKeeper và etcd để đồng bộ cấu hình, tìm kiếm dịch vụ (service discovery) … cho các máy trong mạng nội bộ. Thuật toán chủ đạo của ZooKeeper và etcd là hai thuật toán đồng thuận Paxos và Raft. Paxos và Raft cũng được sử dụng trong Cassandra, Google Spanner, CockroachDB …

Mặt khác, nổi lên trong giai đoạn hiện tại là blockchain cũng với cốt lõi là các thuật toán đồng thuận đằng sau như Proof-of-work, Proof-of-stake… Từ hai ví dụ trên, ta thấy đồng thuận mang tính chất quyết định khi thiết kế hệ thống có nhiều tác nhân tham gia. Do vậy, chủ đề về tính đồng thuận từ rất lâu đã là trọng tâm nghiên cứu trong lĩnh vực hệ thống phân tán. Năm 1985, ba nhà khoa học máy tính Fischer, Lynch, và Paterson đã phát biểu định lí “FLP-Impossibility” - lấy theo tên chữ cái đầu của họ:

Trong hệ thống mạng bất đồng bộ, khi mà các tin nhắn có thể nhận trễ tại bất kì thời điểm nào nhưng không bao giờ thất lạc, không tồn tại một thuật toán đồng thuận nào đảm bảo kết thúc trong mọi khả năng có thể thực thi, với mọi cấu hình ban đầu, khi tồn tại ít nhất một máy tính bị lỗi-và-dừng-hẳn (crash-stop model).

Ngay tại thời điểm báo cáo được công bố, định lí hoàn toàn thay đổi góc nhìn khi thiết kế thuật toán đồng thuận. Các nghiên cứu bắt đầu đưa ra các thuật toán đồng thuận phù hợp hơn với các mô hình thực tế. Do tính chất quan trọng và cơ bản, báo cáo đạt được giải Dijkstra năm 2001 (giải thưởng Dijkstra được trao cho các công trình ảnh hưởng lớn trong hệ thống phân tán bắt đầu từ năm 2000). Chúng ta cùng điểm lại nội dung định lí và cách chứng minh qua paper sau: https://groups.csail.mit.edu/tds/papers/Lynch/jacm85.pdf

Góc Database

Nếu bạn đã từng làm việc nhiều với MySQL thì hẳn cũng biết thiết kế storage engine là một trong những đặc trưng thiết kế khá hay của MySQL giúp tách biệt phần query logic với phần lưu trữ và truy vấn dữ liệu trên đĩa. Nhờ thiết kế này, MySQL có thể hỗ trợ nhiều loại storage engine khác nhau như InnoDB, MyISAM, … với mỗi loại sẽ có một đặc tính riêng.

MyRocks là một storage engine được viết cho MySQL trong đó sử dụng RocksDB làm nơi lưu trữ dữ liệu, nhờ vậy, thông qua MyRocks, chúng ta có thể vừa sử dụng những tính năng của MySQL vừa tận dụng được write-throughput cao nhờ đặc tính của LSM tree (xem ghi chú).

Trong bài viết này, tác giả chia sẻ nhận định của mình về performance của hai loại cấu trúc dữ liệu LSM và Btree, đồng thời cũng chia sẻ về một số đặc điểm (ưu/khuyết) của MyRocks trong giai đoạn đầu được phát triển.

Link bài báo

Ghi chú thêm:

Log-Structured-Merge Tree (LSM) là một trong các cấu trúc dữ liệu được dùng nhiều trong các hệ dữ liệu phân tán NoSQL do có write throughput cao hơn nhiều so với các cấu trúc index khác được dùng trong database như B-tree. LSM được sử dụng trong các database như BigTable, Cassandra, ScyllaDB, RocksDB.
RocksDB là một embedded key-value database được phát triển bởi Facebook trên nền tảng LevelDB trong đó có sử dụng LSM.

Góc Data Warehouse

Snowflake, một công ty chuyên cung cấp giải pháp data warehouse trên cloud, đã đưa ra một bài báo trên NSDI’20 để nói về những quyết định họ đã đặt ra khi thiết kế hệ thống hạ tầng Snowflake. 3 mục đích chính khi thiết kế hệ thống Snowflake là:

Compute & Storage Elasticity
Support for multi-tenancy
High performance

Thay vì dùng kiến trúc shared-nothing, Snowflake đã tập trung vào việc:

Tách mảng compute và storage để dễ dàng scale và đáp ứng như cầu của khách hàng
Intermediate data (dữ liệu được tạo ra khi chạy queries - ví dụ như là lúc JOIN) và Cache sẽ được đặt ở Distributed Ephemeral Storage (hệ thống phân tán chứa dữ liệu tạm thời) để có thể truy vấn và viết dữ liệu với low-latency và high-throughput
Tràn dữ liệu từ memory tới SSD tới persistent storage (e.g. S3) ở Distributed Ephemeral Storage để scale dễ dàng hơn nếu intermediate data quá lớn khi thi hành queries (có thể lên tới GB hoặc TB data cho intermediate data)
Mỗi khách hàng sẽ có Virtual Warehouse riêng cho việc đáp ứng multi-tenancy

Từ những quyết định thiết kế này, chúng đã giúp Snowflake có chỗ đứng tốt trong thị trường data warehouse và giúp các khách hàng của họ trả tiền một cách linh hoạt hơn khi mà compute và storage nodes được chia ra thành 2 mảng khác nhau thay vì được gọp chung lại.

Bạn có thể đọc bài viết này trên The Morning Paper hoặc trên link bài báo

Code & Tools

Quotes

A primary cause of complexity is that software vendors uncritically adopt almost any feature that users want.

- Niklaus Wirth