#173 - Pregel: hệ thống phân tán xử lý dữ liệu graph của Google

May 31, 2021

Những bài viết hay

Rust là một trong những ngôn ngữ được yêu thích nhất trong những năm gần đây thông qua kết quả khảo sát của Stackoverflow. Do đó, ngày càng nhiều công ty bắt đầu khám phá về Rust cho các dự án của họ. Bài viết sau đây được các kỹ sư ở Facebook nói về lịch sử của Rust tại Facebook, đặc biệt là cách họ đã sử dụng Rust như thế nào và tương lai của ngôn ngữ này ở trong codebase của Facebook sẽ ra sao.

Vào năm 2016-2017, Rust đã được một nhóm ở Facebook sử dụng để tối ưu hóa source control của họ trên Mercurial mặc dù Facebook backend codebase thời đấy đa phần là được viết bằng C++. Tuy nhiên, do Rust có ưu điểm mạnh về việc phát hiện được bugs trong lúc biên dịch code, họ đã quyết định dùng thử Rust cho dự án này thay vì C++. Kết quả là dự án được xây dựng và triển khai thành công hơn mong đợi. Đây là bước đi đầu tiên ở Facebook về việc triển khai một dự án về Rust.

Sau đó, một vài đội khác ở Facebook cũng bắt đầu dùng Rust cho các dự án của họ vào những năm 2017-2020. Một ví dụ đặc biệt ở đây là Facebook cryptocurrency, Libra, được viết hầu như 90% bằng Rust. Với ngày càng nhiều dự án liên quan tới Rust. Hiện tại, Facebook đang bắt đầu đầu tư thêm nhân lực cho việc hỗ trợ các dự án liên quan tới Rust. Đồng thời, họ cũng mong đợi rằng Rust sẽ ngày càng phát triển hơn trong nội bộ.

GCC vs. Clang/LLVM: An In-Depth Comparison of C/C++ Compilers — alibabatech.medium.com

Các bạn lập trình viên C/C++ chắc hẳn cũng không còn xa lạ gì với các bộ trình dịch phổ biến như là Visual C++, GNU Compiler Collection (GCC), và Clang/LLVM. Tuy nhiên, nếu nói về nền tảng Linux thì GCC với Clang/LLVM sẽ là 2 bộ trình dịch thông dụng nhất của nền tảng này, đặc biệt là khi đa số các máy chủ backend hiện tại đều được vận hành trên Linux. Bài viết sau đây được các đội ngũ kỹ sư ở Alibaba nói về 2 bộ trình dịch này và các benchmarks được họ xây dựng lên để hiểu rõ hơn về việc nên dùng bộ trình dịch nào cho từng trường hợp. Bài viết đồng thời cũng thảo luận về quá trình xây dựng và phát triển của mỗi bộ trình dịch để người đọc hiểu rõ hơn về GCC và Clang/LLVM.

Thông qua khảo sát và kết quả benchmarks của các kỹ sư ở Alibaba thì họ nhận ra một vài ưu điểm của GCC như là:

GCC hỗ trợ nhiều loại ngôn ngữ truyền thông hơn Clang/LLVM như là Ada, Fortran, và Go
GCC hỗ trợ hơn Clang/LLVM về các loại kiến trúc ít phổ biến
GCC hỗ trợ nhiều chức năng mở rộng ở các ngôn ngữ lập trình và hỗ trợ nhiều chức năng ở assembly hơn là Clang/LLVM. Đồng thời, GCC vẫn là bộ trình duy nhất được dùng để compile Linux kernel

Trong khi đó, một vài điểm nổi bật của Clang/LLVM được nêu lên như là:

Các ngôn ngữ mới nổi đa phần sử dụng LLVM như là Swift, Rust, Ruby, …
Clang cung cấp nhiều công cụ hữu dụng hơn cho các lập trình viên như là scan-build, Clang static analyzer, clang-format, clang-tidy, …
Clang cung cấp nhiều thông tin chính xác và thân thiện hơn GCC về mặt chẩn đoán về lỗi hay gợi ý

The world beyond batch — www.oreilly.com

Khi bàn luận về data processing, chúng ta thường nhắc tới streaming và batch processing. Batch processing xuất hiện trước và được implement một cách đơn giản hơn nhiều so với stream processing, phương thức có quá nhiều yếu tố có thể phát sinh. Ngày nay, stream processing là một vấn đề lớn của big data vì những lý do chính đáng. Ví dụ, business cần dữ liệu được xử lý kịp thời với độ trễ thấp hơn; các tập dữ liệu khổng lồ, không giới hạn (unbounded datasets), với khối lượng không ngừng tăng lên ngày càng phổ biến trong các business; việc xử lý dữ liệu khi chúng đến sẽ phân tán khối lượng công việc ra đồng đều hơn theo thời gian, mang lại mức tiêu thụ tài nguyên nhất quán và có thể dự đoán được.

Để làm việc hiệu quả với streaming data, chúng ta cần hiểu hết các đặc tính của dữ liệu cũng như nhưng yếu tố không thể bỏ qua trong quá trình xử lý. Trong bài viết, tác giả đã đưa ra và phân tích chi tiết những yếu tố quan trọng của streaming data processing.

Định nghĩa "streaming" chỉ để áp dụng cho các công cụ thực thi (execution engines), trong khi sử dụng các thuật ngữ mang tính mô tả hơn như dữ liệu không giới hạn (unbounded data) và kết quả gần đúng / suy đoán (approximate/speculative result) thường được phân loại để sử dụng trong ngữ cảnh "streaming".

Để streaming cỏ thể thay thế batch, tác giả có nêu ra 2 yếu tố high-level quan trọng, đó là: correctness và công cụ để suy luận về thời gian. Với correctness, một streaming processing engine cần có persistant checkpoint để lưu trữ trạng thái của ứng dụng qua thời gian. Điều này đặc biệt quan trọng để khi lỗi xảy, ứng dụng có thể hồi phục lại trạng thái và tiếp tục chạy chính xác từ latest state trong checkpoint. Về vấn đề thời gian trong streaming, chúng ta cần hiểu rõ và thiết lập sự khác biệt quan trọng giữa event time và processing time, mô tả những khó khăn mà những khác biệt đó đặt ra khi phân tích dữ liệu, để từ đó xử dụng chúng một cách hợp lý và chính xác cho các business khác nhau. Các công cụ xử lý streaming cần có khả năng hỗ trợ xử lý dữ liệu theo event hay processing time.

Ngoài ra, trong bài viết, tác giả cũng phân tích các phương pháp đang được sử dụng phổ biến hiện nay cho cả batch và stream processing để xử lý dữ liệu có giới hạn (bounded) lẫn không giới hạn (unbounded): time-agnostic, approximation, windowing by processing time, và windowing by event time.

Góc Distributed System

Pregel: a system for large-scale graph processing

Đa phần các thuật toán xử lý graph thường được thi hành theo dạng multi-threading trên một máy tính. Tuy nhiên, đối với các graph lớn như web graph của Google hay social graph của Facebook thì việc thi hành các thuật toán này trên một máy tính sẽ trở nên không hiệu quả do dữ liệu quá lớn để truy vấn hoàn toàn lên bộ nhớ. Do đó, vào năm 2010 thì Google đã công bố tại hội nghị SIGMOD’10 về hệ thống Pregel, một hệ thống phân tán xử lý graph.

Cả mô hình Pregel lẫn MapReduce của Google đều được dựa trên mô hình Bulk Synchronous Parallel (BSP). Tuy nhiên, Pregel có vài điểm khác biệt so với mô hình MapReduce là hệ thống được tối ưu hóa cho việc viết các thuật toán về graph trên nền phân tán, đặc biệt là việc cung cấp giao diện message passing cho người dùng để dễ dàng kiểm soát việc trao đổi dữ liệu giữa các vertices trên graph.

Tựa như mô hình BSP, mỗi lần chạy một superstep S thì Pregel sẽ đi theo các bước sau đây:

Chạy user-defined function cho mỗi vertex (được chạy song song cho nhiều vertices). User-defined function có thể chỉnh sửa dữ liệu của vertex như là: trạng thái của vertex (active/inactive), outgoing edges (topology), giá trị của vertex hay edge, ...
Function chạy ở bước (1) chỉ định một tác vụ ở vertex V cho superstep S. Vertex V này có thể đọc được những messages được gửi tới nó từ những vertices khác ở bước superstep trước đó là S - 1. Đồng thời, vertex V này có thể gửi messages cho các vertices khác cho bước superstep tiếp theo S + 1 nếu cần
Messages thường sẽ được gửi tới các outgoing edges do Pregel API chỉ cung cấp outgoing vertices cho vertex hiện tại. Tuy nhiên, một vertex có thể lưu trữ ids của các vertices khác để gửi thẳng tới các vertices này

Về mặt thiết kế hệ thống thì Pregel sẽ chia graph thành nhiều partitions với mỗi partition chứa một vài vertices và các outgoing edges của các vertices đó. Trong đó, Pregel sẽ chạy ứng dụng của người dùng theo các bước sau đây:

Ứng dụng của người dùng sẽ được triển khai trên một cụm máy chủ. Một trong những máy chủ đó sẽ được chọn làm master và không nhận dữ liệu về graph. Các máy còn lại sẽ được chọn làm workers và gửi tín hiệu tới master để đăng ký
Master sẽ chia graph ra nhiều partitions và phân bố một hoặc vài partitions tới mỗi worker. Mỗi worker sẽ có nhiệm vụ là: quản lý trạng thái cho các vertices; chạy các logic từ ứng dụng của người dùng cho mỗi vertex; và quản lý messages được gửi đi và nhận được giữa các workers khác
Master sẽ hướng dẫn mỗi worker để thi hành một superstep. Mỗi worker sẽ chạy qua các vertices ở trạng thái active (1 thread cho 1 partition → có thể chạy nhiều partitions song song ở mỗi worker). Mỗi worker chạy lệnh Compute cho mỗi active vertex bao gồm những messages được gửi tới vertex đó từ superstep trước đó. Sau khi worker hoàn thành superstep này thì sẽ gửi tín hiệu tới master để thông báo các active vertices tiếp theo. Messages được gửi asynchronously và được gửi trước khi một superstep hoàn thành
Khi không còn active vertices thì master sẽ hướng dẫn các worker lưu dữ liệu cho mỗi partition

Góc Lập Trình

Đề ra tuần này: Bài toán trộm bánh.

Bạn là một tên trộm nổi tiếng, và gần đây đã đổi từ kim cương sang ăn trộm bánh để đạt được lợi nhuận siêu khủng khiếp. Bạn đã đột nhập vào kho bánh của nữ hoàng Anh, mặc dù có một số lượng giới hạn các loại bánh, nhưng lại có nguồn cung cấp không giới hạn cho mỗi loại. Mỗi loại bánh có trọng lượng và giá trị, được đặt trong 1 tuple gồm 2 số. Một số nguyên đại diện cho trọng lượng của chiếc bánh tính bằng kilôgam. Một số nguyên khác đại diện cho giá trị tiền tệ của chiếc bánh tính bằng đồng shilling của Anh

Ví dụ:

(7, 160) # Nặng 7 kg và có giá trị là 160 shilling

(3, 90) # Nặng 3 kg và có giá trị là 90 shilling

Bạn đã mang theo một chiếc túi vải thô có thể chứa được trọng lượng giới hạn và bạn muốn tận dụng nó để lấy một số lượng bánh với giá trị lớn nhất có thể.

Viết một hàm với input là danh sách các loại bánh và trọng lượng tối đa chiếc túi bạn mang theo có thể chứa được, hãy trả về giá tiền lớn nhất từ số bánh mà bạn có thể lấy được.

Ví dụ:

Input: cake_tuples = [(7, 160), (3, 90), (2, 15)]

capacity = 20

Output: 555

Giải thích: 6 chiếc bánh loại 2 và 1 chiếc bánh loại 3, sẽ có tổng giá trị là 6 * 90 + 1 * 15 = 555, là giá trị lớn nhất có thể. Tổng trọng lượng là 6*3 + 2 = 20.

Lời giải tuần trước:

Time Complexity = O(N) với N là chiều dài của mảng đầu vào.

Space Complexity = O(1).

Code & Tools

This Week Sponsors

LINE đang tích cực tìm kiếm nhiều nhân tố ở các vị trí chủ chốt để đáp ứng nhu cầu phát

triển mạnh mẽ của hệ sinh thái LINE. Đặc biệt, trong vai trò Engineering Manager, các bạn sẽ có cơ hội tác động tích cực đến sự phát triển của con người, tổ chức, sản phẩm và hàng trăm triệu người dùng.

Góc Tuyển Dụng

See other openings at LINE Technology Vietnam

Quotes

The belief that complex systems require armies of designers and programmers is wrong. A system that is not understood in its entirety, or at least to a significant degree of detail by a single individual, should probably not be built

- Niklaus Wirth