View profile

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

Revue
 
 

Grokking Newsletter

May 31 · Issue #174 · 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
A brief history of Rust at Facebook
GCC vs. Clang/LLVM: An In-Depth Comparison of C/C++ Compilers GCC vs. Clang/LLVM: An In-Depth Comparison of C/C++ Compilers
The world beyond batch The world beyond batch
Góc Distributed System
Đ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:
  1. 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, …
  2. 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
  3. 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:
  1. Ứ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ý
  2. 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
  3. 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
  4. 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
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
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