Do Thi Song Song.docx

Pregel: Hệ thố ng xử lý đồ thi ̣ lớn 1. 1. Pregel: Hệ thống xử lý đồ thị lớn. Grzegorz Malewicz, Matthew H. Austern, Aart J. C. Bik, James C. Dehnert, Ilan Horn, Naty Leiser, and Grzegorz Czajkowski Google, Inc. {malewicz, austern, ajcbik, dehnert, ilan, naty, gczaj}@google.com Nhóm dịch: Phùng Đức Nhật, Đặng Minh Hiếu, Lưu Trung Hiếu, Phạm Đức Đạo TỔNG QUAN Nhiều vấn đề thực tế về tính toán liên quan đến đồ thị lớn. Ví dụ điển hình bao gồm đồ thị Web và các mạng xã hội. Độ lớn của đồ thị, trong một vài trường hợp, có hàng tỉ đỉnh, triệu tỷ cạnh, tạo ra thách thức đối với hệu năng xử lý. Trong bài viết này ta sẽ giới thiệu một mô hình tính toán phù hợp với vấn đề này. Chương trình được biểu diễn bởi một chuỗi các vòng lặp, đối với mỗi vòng lặp một đỉnh có thể nhận các thông điệp được gửi đi trong vòng lặp trước, gửi thông điệp tới những đỉnh khác, thay đổi trạng thái của chính nó và trạng thái của các cạnh đi ra từ nó hoặc biến đổi cấu trúc của đồ thị. Cách tiếp cận tập trung vào các đỉnh đủ linh hoạt để biểu diễn các thuật toán. Mô hình được thiết kế cho phiên bản cài đặt có hiệu năng cao, khả năng mở rộng và chịu lỗi trên các cụm máy chủ gồm hàng nghìn các máy tính thông thường, và khả năng đồng bộ của nó giúp cho việc lập trình trở nên dễ dàng hơn. Các chi tiết liên quan đến sự phân tán được che giấu bên dưới một API trừu tượng. Kết quả là một framework cho việc xử lý một đồ thị lớn mà thuận tiện cho việc biểu đạt và dễ dàng cho việc lập trình. 1. Giới thiệu chung Mạng internet đã làm cho đồ thị mạng trở thành đề tài phần tích và nghiên cứu phổ biến. Web 2.0 tăng thêm sự quan tâm của mạng xã hội. Các đồ thị lớn, ví dụ bao gồm chuyển tin qua các router, sự tương đồng của các bài báo, đường phát tán của bệnh tật, hoặc các đường trích dẫn đến các bài báo khoa học khác nhau, đã được xử lý trong hàng thập kỷ. Các thuật toán phổ biến bao gồm tìm đường đi ngắn nhất, các loại phân loại khác nhau, và các biến thể xếp hạng các trang. Có nhiều vấn đề tính toàn đồ thị đối với các giá trị thực tế, như đường cắt nhỏ nhất và các thành phần được nối. Hiệu năng xử lý của một đồ thị lớn là một thách thức. Các thuật toàn đồ thị thường cho thấy sự ít ỏi trong khả năng truy cập bộ nhớ cục bộ, gần như không có công việc nào được thực thi ở mỗi đỉnh và sự kém linh hoạt trong việc xử lý song song. Sự phân tán trên nhiều máy làm tăng các vấn đề cục bộ và làm tăng khả năng thấ bại trong việc tính toàn của một máy. Mặc dù sự tồn tại của đồ thị lớn ở khắp nơi và tính thương mại cao của chúng, nhwng chúng ta biết được không có hệ thống có khả năng mở rộng và hướng tới một mục đích chung nào cho việc cài đặt thuật toán đồ thị phù hợp với tất cả các đồ thị trong môi trường phân tán lớn. Cài đặt một thuật toán cho việc xử lý một đồ thị lớn nghĩa là chọn một trong các lựa chọn sau: 1. Tự xây dựng một cơ sở hạ tầng phân tán riêng, thường đòi hỏi sự nỗ lực trong việc thực thi mà phải lặp đi lặp lại mỗi khi thay đổi thuật toán hoặc cách biểu diễn đồ thị. 2. Dựa trên các nền tảng hệ phân tán có sẵn, thường không phù hợp cho việc xử lý đồ thị. MapReduce là một ví dụ điển hình cho sự 2. 2. phù hợp của một mảng lớn trong việc tính toán vấn đề đồ thị lớn. Nó đôi khi được dùng để khai phá đồ thị lớn, nhưng điều này có thể dẫn đến việc phải tối ưu hóa hiệu năng và vấ đề về bộ nhớ. Mô hình cơ bản cho việc xử lý dữ liệu đã được mở rộng để làm thuận tiên hơn cho việc kết tập và thực thi các câu truy vấn giống như SQL, nhưng những mở rộng này thường không được lý tưởng cho các thuật toán đồ thị mà thường phù hợp hơn cho mô hình truyền tin. 3. Sử dụng thư viện thuật toán đồ thị cho một máy tính, như là BGL, LEDA, NetworkX, JDSL, Standford GraphBase, hoặc FGL, giới hạn độ lớn của vấn đề tới mức mà có thể xử lý được. 4. Sử dụng những hệ thống đồ thị song song có sẵn. Sử dụng song song thư viện BGL và CGMgraph biểu diễn thuật toán đồ thị song song, nhưng không cho phép chịu lỗi hay xử lý các vấn đề khác – những vấn đề rất quan trọng đối với những hệ thống phân tán lớn. Không có một phương pháp thay thế nào phù hợp. Để giải quyết vấn đề xử lý sự phân tán của các đồ thị lớn, chúng tôi đã xây dựng một nền tảng có khả năng mở rộng và có khả năng chịu lỗi với một API mà đủ linh hoạt trong việc thể hiện tham vọng của thuật toán đồ thị. Bài báo này miêu tả hệ thống được gọi là Pregel và báo cáo các kinh nghiệm của chúng tôi với hệ thống này.

3. 3. Cách thức tổ chức ở mức cao của Pregel lấy cảm hứng từ mô hình đồng bộ song song cụm của Valiant. Pregel tính toán bằng những vòng lặp được gọi là superstep. Trong một superstep, framework gọi tới chức năng do người dùng định nghĩa cho mỗi đỉnh một cách song song. Chức năng chỉ rõ hoạt động ở một đỉnh V ở một superstep S. Nó có thể đọc thông điệp gửi đến V trong superstep S–1, gửi thông điệp tới những đỉnh khác mà sẽ nhận được trong superstep S + 1, và thay đổi trạng thái của V và của những cạnh đi ra từ nó. Thông điệp thường được gửi đi thông qua các cạnh, nhưng thông điệp có thể gửi đi tới bất kỳ đỉnh nào với điều kiện biết được định danh của nó. Cách thức tiếp cận tập trung vào các đỉnh giống MapReduce ở điểm là người dùng tập trung vào các hoạt động ở cục bộ, xử lý mỗi đối tượng một cách độc lập, và hệ thống biên soạn những hoạt động này để có thể xử lý tập dữ liệu lớn. Bằng cách xây dựng mô hình phù hợp cho hệ phân tán: nó không để lộ bất kỳ cơ chế nào để phát hiện thứ tự thực hiện lệnh trong một superstep và các giao tiếp giữa các superstep. Sự đồng bộ của mô hình này làm nó dễ dàng hơn trong việc suy luật ngữ nghĩa của chương trình khi cài đặt giải thuật, và chắc chắn rằng chương trình viết bằng pregel sẽ không gặp trường hợp dead-lock và data races thường thấy trong các hệ thống đồng bộ. Theo nguyên tắc, hiệu năng của chương trình pregel có tính cạnh tranh với những hệ thống bất đồng bộ mà được cấp đủ slack song song. Bởi vì tính toán đồ thị thông thường có nhiều đỉnh hơn các máy rất nhiều, nên một giải thuật cần phải cân bằng tải của máy để việc đồng bộ giữa các superstep không phải chịu thêm độ trễ đáng kể. 2. Mô hình tính toán Đầu vào cho việc tính toán Pregel là một đồ thị có hướng. Trong đó mỗi đỉnh được đặc trưng bởi một xâu định danh. Mỗi đỉnh được liên kết với một giá trị có thể thay đổi được định nghĩa bởi người sử dụng. Cạnh có hướng được liên kết với các đỉnh nguồn và mỗi cạnh bao gồm bởi một giá trị có thể thay đổi được định nghĩa bởi người sử dụng. Việc tính toán Pregel đặc trưng bao gồm đầu vào, được bắt đầu từ khi đô thị được khởi tạo, theo sau là một chuỗi liên tiếp các superstep được ngăn cách với nhau bởi điểm đồng bộ hóa toàn cục và tiếp diễn cho tới khi thuật toán được ngắt và kết thúc với đầu ra. Trong các superstep các đỉnh được tính toán song song. Mỗi superstep thực thi một chức năng của người sử dụng và thể hiện ra logic thuật toán. Một đỉnh có thể tự thay đổi trạng thái của nó hoặc trạng thái của các cạnh đi ra từ nó, nhận các thông điệp được gửi tới nó trong superstep đó, gửi thông điệp tới các đỉnh khác ( sẽ được nhận trong superstep tiếp theo), hoặc thậm chí thay đổi cấu trúc của đồ thị. Các cạnh không phải là đối tượng bậc nhất trong mô hình và không có bất cứ liên quan gì đến với việc tính toán. Vote to halt Active Inactive Message received Figure 1: Vertex State Machine Việc dừng thuật toán dựa trên việc các đỉnh đề xuất dừng. Trong superstep 0, mọi đỉnh đều trong trạng thái hoạt động. Tất cả các đỉnh đang hoạt động đều tham gia vào việc tính toán của bất kỳ superstep nào. Mội đỉnh tự ngưng hoạt động bằng cách đề xuất để ngắt. Điều này có nghĩa là đỉnh đó không còn bất cứ công việc nào để thực hiện trừ khi nó được kích hoạt từ bên ngoài và Pregel framework sẽ không thực thi đỉnh đó trong các superstep tiếp theo nếu như nó không nhận được thông điệp. Nếu như được khởi động lại bằng các thông điệp, một đỉnh bắt buộc phải tự ngừng hoạt động lại một cách 4. 4. tường minh. Thuật toán được ngắt hoàn toàn khi tất cả các đỉnh đều ngừng hoạt động và không có bất cứ thông điệp nào được truyền đi. Mô hình đơn giản của trạng thái được mô tả trong hình 1. Đầu ra của một chương trình Pregel là một tập các giá trị tường minh được đưa ra bởi các đỉnh. Nó thường là các đồ thị định hướng đẳng cấu với đầu vào nhưng không nhất thiết bởi các đỉnh và các cạnh có thể được thêm vào hoặc bớt đi trong quá trình tính toán. Ví dụ một thuật toán phân cụm có thể sinh ra một tập các đỉnh không liên kết với nhau được chọn từ đồ thị lớn. Một thuật toán khai phá đồ thị đơn giản có thể cho đầu ra là tập hợp các thống kê được khai phá từ đồ thị. Hình 2 minh họa các khái niệm này sử dụng một ví dụ đơn giản: Cho một đồ thị được kết nối chặt. Mỗi đỉnh bao gồm một giá trị và nó sẽ truyền giá trị lớn nhất tới tất cả các đỉnh. Trong mỗi superstep, bất cứ đỉnh nào tìm được giá trị lớn hơn từ các thông điệp sẽ gửi giá trị đó cho các đỉnh liền kề nó. Khi không còn thêm bất cứ thay đổi nào của các đỉnh trong các superstep thì thuật toán sẽ dừng lại. Chúng ta chọn mô hình truyền thông điệp thuần túy, bỏ đọc từ xa và các phương pháp khác để thực hiện việc chia sẻ dữ liệu bởi 2 lí do sau. Thứ nhất, mô hình truyền thông điệp đủ để thể hiện

rằng không nhất thiết phải có quá trình đọc từ xa. Thứ 2, lựa chọn này sẽ tốt hơn về hiệu năng. Trong môi trường phân cụm, việc đọc một giá trị từ một máy chủ ở xa gây ra độ trễ cao khó có thể tránh được. Mô hình truyền thông điệp cho phép chúng ta có thể bù lại độ trễ bằng cách gửi các thông điệp một cách bất đồng bộ theo nhiều lô. Thuật toán đồ thị có thể được viết như một chuỗi liên liên tục các lời gọi MapReduce. Chúng ta chọn một mô hình khác vì khả năng sử dụng và hiệu năng. Pregel giữ các cạnh và đỉnh trên một máy chủ mà thực hiện việc tính toán và chỉ sử dụng mạng để truyền các thông điệp. Tuy nhiên MapReduce cũng thuần túy là lập trình hướng chức năng, do đó việc thực hiện thuật toán như một chuỗi MapReduce đòi hỏi cần phải truyền toàn bộ trạng thái của đò thị từ một giai đoạn sang giai đoạn tiếp theo – nói chung nó sẽ đòi hỏi nhiều việc giao tiếp và các vấn đề tuần tự hóa kết hợp. Hơn nữa, các vòng lặp thông qua các superstep sẽ tránh được việc lập trình phức tạp – cái mà sẽ xảy ra khi điều phối các bước trong một chuỗi MapReduce. 5. 5. 3 6 2 1 Superstep 0 6 6 2 6 Superstep 1 6 6 6 6 Superstep 2 6 6 6 6 Superstep 3 Figure 2: Maximum Value Example. Dotted lines are messages. Shaded vertices have voted to halt. 3. C++ API Phần này sẽ nói về khía cạnh quan trọng nhất của pregel, C++ API, bỏ qua những vẫn để liên quan đến cơ chế. Viết một chương trình Pregel liên quan đến việc kế thừa lại (subclassing) lớp Vertex đã được định nghĩa trước. Các tham số mẫu của nó định nghĩa 3 loại giá trị, liên quan đến các đỉnh, cạnh và các thông điệp. Mỗi đỉnh có một giá trị liên kết của một loại nhất định. Sự bất tương đồng dường như gây ra hạn chế, nhưng người dùng có thể xử lý bằng cách sử dụng các kiểu linh hoạt như bộ đệm của giao thức. Các kiểu cạnh và thông điệp xử lý tương tự. Người dùng ghi đè phương thức Compute (), phương thức mà sẽ được thực hiện tại mỗi đỉnh đang hoạt động trong mỗi superstep. Các phương thức được định nghĩa trước của lớp Vertex cho phép Compute() truy xuất thông tin về đỉnh hiện tại và các cạnh của nó, và gửi thông điệp tới các đỉnh khác. Compute() có thể dò giá trị liên quan tới đỉnh của nó thông qua phương thức GetValue() hoặc thay đổi nó thông qua phương thức MutableValue(). Nó có thể dò và thay đổi những giá trị của những cạnh đi ra bằng cách sử dụng phương thức được đã được cung cấp thông qua việc duyệt các cạnh đi ra. Việc cập nhật trạng thái sẽ được nhìn thấy ngay lập tức. Vì khả năng hiển thị bị hạn chế đối với các đỉnh bị sửa đổi, sẽ không có hiện tượng data racestrên các giá trị đồng thời được truy cập từ các đỉnh khác nhau. Các giá trị liên kết với các đỉnh và các cạnh của nó chỉ là trạng thái cho từng đỉnh mà không đổi trong suốt các superstep. Giới hạn trạng thái đồ thị được quản lý bởi framework tới một giá trị mỗi đỉnh và cạnh đơn giản hóa chu kỳ tín toán chính, phân tán đồ thị và phục hồi khi gặp lỗi. 3.1 Truyền tin Các đỉnh giao tiếp trực tiếp với nhau bằng các gửi các thông điệp. Mỗi thông điệp chứa giá trị của thông điệp và tên của đích đến. Kiểu của giá trị thông điệp sẽ được chỉ rõ bởi người dùng ở tham số mẫu của lớp Vertex. Một dỉnh có thể gửi các thông điệp với số lượng bất kỳ trong 1 superstep. Tất cả các thông điệp được gửi đến đỉnh V trong superstep S sẽ được thực thi khi phương thức Compute() của đỉnh V được gọi ở superstep S+1 thông qua một con trỏ lặp. Thứ tự của các thông điệp sẽ không được lưu trữ trong con trỏ lặp, nhưng các thông điệp chắc chắn sẽ được gửi đi và chúng sẽ không bị trùng lặp. Một cách dùng thông dụng là cho 1 đỉnh V duyệt qua các cạnh đi ra từ nó, gửi thông điệp đến đỉnh đích của mỗi cạnh, như trong thuật toán PageRank. Tuy nhiên, dest_vertex không cần phải là đỉnh kề của V. 6. 6. template class Vertex { public: virtual void Compute(MessageIterator* msgs) = 0; const string& vertex_id() const; int64 superstep() const; const VertexValue& GetValue(); VertexValue* MutableValue(); OutEdgeIterator GetOutEdgeIterator(); void SendMessageTo (const string& dest_vertex, const MessageValue& message); void VoteToHalt (); }; Figure 3: The Vertex API foundations. Một đỉnh có thể học được định danh của một đỉnh không kề từ thông điệp nhận từ trước, hoặc các định danh của các đỉnh có thể được ngầm định. Ví dụ như đồ thị có thể là một cụm, và được định danh công khai từ V1 đến Vn, trong trường hợp này thậm chí có thể không cần tới những cạnh rõ ràng trên đồ thị. Khi một đỉnh đích của một thông điệp bất kỳ không tồn tại, các bộ xử lý được người dùng định nghĩa sẽ được thực thi. Ví dụ bộ xử lý có thể tạo ra một đỉnh đang thiếu hoặc gỡ bỏ một cạnh thừa từ đỉnh của nó. 3.2 Bộ kết

hợp Việc gửi một thông điệp, đặc biệc tới một đỉnh trên một máy khác, chịu một số chi phí. Điều này có thể được giảm thiểu trong một số trường hợp với sự trợ giúp của người dùng. Ví dụ, giả sử rằng Compute() nhận các thông điệp dưới dạng số nguyên và chỉ cần tính tổng chứ không cần các giá trị từng phần. Trong trường hợp đó, hệ thống có thể kết hợp nhiều thông điệp hướng tới đỉnh V vào thành 1 thông điệp chứa tổng, giúp giảm thiểu số lượng thông điệp cần chuyển đi và lưu trong buffer. Bộ kết hợp không được kích hoạt theo mặc định, bởi vì không có một cơ chế nào để tìm ra một hàm kết hợp mà đồng bộ với phương thức Compute() của người dùng. Để kích hoạt phương thức tối ưu này, người dùng sẽ viết lớp con của lớp Combiner, ghi đề phương thức Combine (). Không thể biết được những thông điệp nào sẽ được kết hợp (nếu có), các nhóm nào sẽ được kết hợp, hoặc thứ tự kết hợp, vì vậy bộ kết hợp sẽ chỉ được kích hoạt cho các tiến trình có tính giao hoán và kết hợp. Đối với một số thuật toán, ví dụ như thuật toán tìm đường ngắn nhất từ đỉnh nguồn, chúng ta sẽ tìm hiểu cách giảm lưu lượng thông điệp 4 lần bằng cách sử dụng combiners. 3.3 Aggregators Pregel aggregators là một cơ chế cho giao tiếp toàn cục, giám sát và dữ liệu. Mỗi đỉnh có thể cung cấp một giá trị cho một aggregator trong superstep S, hệ thống kết hợp các giá trị đó bằng toán tử tối giảm, và giá trị trả về được cấp cho mọi đỉnh trong superstep S + 1. Pregel bao gồm một số aggregtors được định nghĩa sẵn, ví dụ như min, max, hoặc sum đối với kiểu số nguyên hoặc chuỗi. Các aggregator có thể sử dụng cho thống kê. Ví dụ sum aggregator áp dụng cho các cạnh đi ra của mỗi đỉnh là tổng các cạnh của đồ thị. 7. 7. Các toán tử tối giản phức tạp có thể tạo ra những biểu đồ thống kê. Các aggregator còn có thể được sử dụng cho việc điều phối toàn cục. Ví dụ như, một nhánh của Compute() có thể thực thi cho các superstep cho đến khi một aggregator nhận định là tất cả các đỉnh đã thỏa mãn một số điều kiện nào đó, tiếp theo một nhánh khác có thể thực thi cho đến khi kết thúc. Một aggregator min hoặc max, áp dụng cho ID của đỉnh, có thể được sử dụng để chọn một đỉnh để đóng vai trò phân biệt trong một thuật toán. Để định nghĩa một aggregator mới, người dùng viết lớp con của lớp Aggregator đã được định nghĩa trước, và chỉ rõ cách giá trị tổng hợp được khởi tạo của từ giá trị đầu vào và cách từ nhiều phân của giá trị tổng hợp tối giản về một giá trị. Các toán tử của Aggregation nên có tính giao hoán và kết hơp. Theo mặc định một aggregator chỉ nên giảm thiểu giá trị đầu vào từ một superstep, nhưng có thể định nghĩa một sticky aggregator mà dùng những giá trị đầu vào từ tất cả các superstep. Điều này rất hữu dụng, ví dụ như, để giữ một số đếm số cạnh toàn cục mà chỉ thay đổi khi mà các cạnh được thêm vào hay loại bỏ. Những chức năng nâng cao có thể được cài đặt. Ví dụ như, một aggregator có thể được sử dụng để cài đặt một hàng đợi ưu tiên phân tán cho thuật toán đường delta ngắn nhất. Mỗi đỉnh được chỉ định tới một đống ưu tiên dựa trên khoảng cách ước lượng của nó. Điểm nhỏ nhất được quảng bá tất cả các máy thợ trong superstep tiếp theo và các đỉnh trong đống có index nhỏ nhất nới lỏng các cạnh. 3.4 Biến đổi cấu trúc Một số thuật toán đồ thị cần thay đổi cấu trúc của đồ thị. Ví dụ như một thuật toán gom nhóm có thể thay thế một nhóm bằng một đỉnh, và một thuật toán nhánh cây nhỏ nhất có thể loại bỏ tất cả trừ các nhánh cây. Cũng như hàm Compute() của người dùng có thể gửi các thông điệp, việc biến đổi cấu trúc có thể xử lý các yêu cầu thêm hoặc loại bỏ các đỉnh hoặc các cạnh. Nhiều đỉnh có thể gặp xung đột yêu cầu trong cùng một superstep (Ví dụ như 2 yêu cầu để thêm đỉnh V với 2 giá trị khởi tạo khác nhau). Chúng ta sử dụng 2 cơ chế để đạt được sự thống nhất: sắp xếp thứ tự từng phần và bộ xử lý. Đối với các thông điệp, sự biến đổi trở nên hiệu quả trong superstep sau khi mỗi yêu cầu được gửi đi. Trong superstep đó việc loại bỏ được thực thi đầu tiên, loại bỏ cạnh trước khi loại bỏ đỉnh, vì việc loại bỏ một đỉnh mặc định loại bỏ tất cả các cạnh đi ra từ nó. Việc thêm vào diễn ra tiếp theo việc loại bỏ, với việc thêm đỉnh trước khi thêm cạnh và tất cả các biến đổi đều gọi tới Compute(). Việc sắp xếp thứ tự từng phần giải quyết cho hầu hết các xung đột. Những xung đột còn lại được xử lý bởi bộ xử lý do người dùng định nghĩa. Nếu như nhiều yêu cầu sinh thêm cùng một đỉnh trong cùng một superstep, thì theo mặc định của hệ thống sẽ chọn một cách tùy tiện, nhưng người dùng với những yêu cầu đặc biệt có thể cụ thể hóa một chính sách giải quyết xung đột tốt hơn bằng cách định nghĩa một phương thức của bộ xử lý phù hợp trong lớp con của Vertex. Cơ chế tương tự bộ xử lý có thể được sử dụng để giải quyết

xung đột do nhiều yêu cầu loại bỏ đỉnh, thêm cạnh cũng như loại bỏ cạnh. Chúng ta ủy thác phương thức giải quyết cho bộ xử lý để giữ cho code của phương thức Compute() đơn giản, điều này giảm thiểu việc ảnh hưởng lẫn nhau của bộ xử lý và Compute(), nhưng điều này chưa bao giờ là vấn đề trong thực tế. Cơ chế phối hợp rất lỏng lẻo: sự thay đổi toàn cục không yêu cầu sự điều phối cho đến khi chúng được áp dụng. Lựa chọn thiết kế này làm đơn giản hóa việc xử lý luồng. Mấu chốt là xung đột liên quan đến sự thay đổi của một đỉnh V được xử lý bởi chính đỉnh V đó. Pregel cũng hỗ trợ biến đổi cục bộ, ví dụ như một đỉnh thêm hoặc xóa các cạnh đi ra từ chính nó hoặc tự xóa chính nó. Biến đổi cục bộ không 8. 8. thể gây ra xung đội và ngay lập tức làm chúng hiệu quả và dễ dàng cho việc lập trình phần tán bằng cách sử dụng một loại các câu lệnh dễ hiểu hơn. 3.5 Đầu vào và đầu ra Có những nhiều định dạng file cho đồ thị, ví dụ như file text, một tập các đỉnh trong hệ cơ sở dữ liệu quan hệ hoặc các hàng trong Bigtable. Để tránh áp đặt một định dạng nhất định của file, Pregel phân giải nhiệm vụ của việc thông dịch một file đầu vào như một đồ thị từ nhiệm vụ của việc tính toán đồ thị. Tương tự, đầu ra có thể được sinh ra trong một định dạng tùy ý và có thể lưu trữ trong form mà phù hợp nhất cho ứng dụng. Thư viện Pregel cung cấp Readers và Writers cho nhiều định dạng file phổ biến, nhưng người dùng với những nhu cầu bất thường cần phải tự viết các lớp con của các lớp trừu tượng cơ sở Reader và Writer để xử lý vấn đề này. 4. Cài đặt Pregel được thiết kế cho kiến trúc phân cụm của Google. Mỗi cụm gồm hàng nghìn PC thông thường được sắp xếp vào các rãnh với băng thông nội rãnh rộng. Các cụm được nội kết nối với nhau nhưng được phân tán theo địa lý. Chương trình thường được xử lý trên một hệ thống quản lý cụm có chức năng lập lịch các công việc để tối ưu hóa việc cấp phát các tài nguyên, đôi khi loại bỏ các thể hiện hoặc chuyển chúng đến những máy khác. Hệ thông bao gồm dịch vụ quản lý tên, để các thể hiện có thể tham chiếu đến thông qua tên logic không bị phụ thuộc vào máy mà chúng đang được lưu trữ. Dữ liệu ít thay đổi được lưu trữ dưới dạng file trên hệ thông lưu trữ phân tán, GFS, hoặc trong Bigtable, và dữ liệu tạm thời ví dụ như thông điệp trong buffer lưu trữ trên ổ đĩa cục bộ. 4.1 Kiến trúc cơ bản Thư viện của Pregel chia đồ thị thành nhiều phần, mỗi phần chứa một tập các đỉnh và tất cả các cạnh đi ra từ các đỉnh đó. Việc gán một đỉnh vào một phần dựa hoàn toàn vào ID của đỉnh đó, vì vậy có thể biết được một đỉnh thuộc phần nào của đồ thị cho dù đỉnh đó thuộc về một máy tính khác, hoặc thậm chí là đỉnh đó chưa được tạo ra. Chức năng chia phần mặc định là lấy phần dư của phép chia của hash(ID) cho N với N là số phần mà đồ thị được phân chia, nhưng người dùng có thể ghi đè chức năng này. Việc gán các đỉnh với các máy thợ là phần chính mà người dung có thể thấy được. Một số ứng dụng hoạt động tốt với cách gán mặc định, nhưng một số lại hoạt động tốt hơn với các cách gán tự đề xuất để khai thác tốt hơn tính cục bộ vốn có của đồ thị. Ví dụ như, một hàm đánh giá thông dụng sử dụng cho đồ thị Web là để ghép các đỉnh đại diện cho các trang của cùng một web site. Nếu không xảy ra lỗi, việc thực thi của chương trình Pregel bao gồm các giai đoạn: 1. Nhiều bản sao của chương trình người dùng bắt đầu bằng cách thực thi trên một nhóm các máy tính. Một trong số chúng hoạt động như một máy chủ chính. Nó không được gán vào bất kỳ phần nào của đồ thị, nhưng nó chịu trách nhiệm điều phối các hoạt động của máy thợ. Các máy thợ sử dụng dịch vụ quản lý tên của hệ thống quản lý cụm để tìm ra địa điểm của máy chủ, và gửi thông điệp đang ký đến máy chủ chính. 9. 9. 2. Máy chủ chính quyết định đồ thị sẽ được phân chia ra làm bao nhiêu phân vùng, và gán một hoặc nhiều phân vùng của đồ thị cho từng máy thợ. Số lượng có thể được điều chỉnh bởi người dùng. Có nhiều hơn một phân vùng mỗi máy thợ cho phép song song hóa giữa các phân vùng và cân bằng tải tốt hơn, và thường sẽ tăng hiệu năng. Mỗi máy thợ có nhiệm vụ bảo trì trạng thái của các phần đồ thị của nó, thực thi Compute() của người dùng trên các đỉnh mà nó quản lý, và quản lý các thông điệp đến và đi. Mỗi máy thợ đều biết máy nào được gán phần đồ thị nào. 3. Máy chủ chính phân một phần của các giá trị đầu vào của người dùng cho các máy thợ. Đầu vào được coi như một tập các bản ghi, mà mỗi bản ghi chứa một số lượng bất kỳ các đỉnh và các cạnh. Sự phân chia đầu vào khớp với phân vùng của đồ thị của nó, và thông thường dựa trên giới hạn của file. Nếu một máy thợ tải một cạnh thuộc về một máy khác, cấu trúc dữ liệu phù hợp sẽ được cập nhật ngay lập tức. Nếu không

máy thợ đó sẽ đưa một thông điệp vào hàng đợi cho máy thợ chưa đỉnh đó. Sau khi đầu vào tải xong, tất cả các đỉnh sẽ được đánh dấu là đang hoạt động. 4. Máy chủ chính hướng dẫn cho từng máy thợ để thực hiện một superstep. Máy thợ sẽ duyệt qua các đỉnh đang hoạt động, mỗi phần sẽ sử dụng một luồng riêng biệt. Máy thợ gọi hàm Compute() cho từng đỉnh đang hoạt động, truyền những thông điệp mà được gửi tới trong những superstep trước. Những thông điệp mà được gửi đi một cách không đồng bộ gây nên sự chồng chéo trong tính toán và giao tiếp và xếp lô, nhưng được gửi đi trước khi kết thúc superstep. Khi một máy thợ hoàn thành, nó sẽ phàn hồi cho máy chủ chính, trả về số lượng đỉnh sẽ hoạt động trong superstep tiếp theo. Bước này được lặp đi lặp lại cho đến khi tất cả các đỉnh đều không còn hoạt động, hoặc không còn thông điệp đang được chuyển giao. 5. Sau khi công việc tính toán kết thúc, máy chủ chính có thể đưa ra chỉ thị cho từng máy thợ lưu lại phần đồ thị của nó. 4.2 Khả năng chịu lỗi Khả năng chịu lỗi được thể hiện qua các điểm mốc. Ở điểm bắt đầu của superstep, máy chủ chính chỉ định cho các máy thợ lưu lại trạng thái của chúng vào kho, bao gồm các giá trị của các đỉnh, giá trị các cạnh và các thông điệp đến; máy chủ chính lưu một cách riêng biệt các giá trị aggregator. Các lỗi ở máy thợ được phát hiện bằng cách máy chủ chính sẽ “ping” đến các máy thợ. Nếu một máy thợ không nhận được ping sau một khoảng thời gian nhất định, máy thợ đó sẽ ngừng lại. Nếu máy chủ chính không nhận phản hồi từ máy thợ, máy chủ chính đánh dấu tiến trình của máy thợ đó gặp lỗi. Khi một hay nhiều hơn một máy thợ gặp sự cố, trạng thái hiện tại được gán cho chúng sẽ bị mất. Máy chủ chính sẽ gán lại phần của đồ thị đó cho các máy thợ đang hoạt động còn lại, và chúng sẽ tải lại các trạng thái gần nhất ở đầu của một superstep S. Điểm mốc đó có thể từ những superstep trước superstep gần nhất S0 một vài superstep và được hoàn thành bởi bất kỳ phần nào trước khi gặp lỗi, việc cần thực hiện là phục hồi những superstep bị mất. Việc chọn những mốc thường dựa trên tần suất gặp lỗi của mô hình, cân bằng chi phí tạo mốc và chi phí ước tính cho việc phục hồi. Việc hạn chế trong phục hồi đang được phát triển để giảm chi phí và độ trễ của việc phục hồi. Ngoài các mốc cơ bản, máy thợ có thể ghi lại các thông điệp chuyển đi từ phần của nó trong khi đồ thị được tải và giữa các superstep. Việc phục hồi từ đó được giới hạn trong các phần bị mất mà được phục hồi từ các mốc. Hệ thông tính toán lại những superstep bị mất cho đến superstep S0 bằng cách sử dụng các thông điệp từ các phần không bị lỗi và tính toán lại các superstep từ các phần đang được phục hồi. 10. 10. Hướng tiếp cận này tiết kiệm tài nguyên tính toán trong khi phục hồi bằng cách chỉ tính toán lại phần bị mất, và có thể giảm độ trễ của phục hồi vì mỗi máy thợ có thể phục hồi một vài phần. Lưu lại nhưng thông điệp được chuyển đi tăng thêm chi phi, nhưng một máy tính thông thường có ở nhớ phù hợp để đảm bảo rằng việc vào ra không trở thành một nút thắt cổ chai. Giới hạn việc phục hồi đòi hỏi thuật toán của người dùng phải được xác định, để tránh sự thiếu đồng bộ vì trộn lẫn các thông điệp được lưu từ những thực thi gốc với những thông điệp mới từ việc phục hồi. Thuật toán ngẫu nhiên có thể được làm cho rõ ràng bằng cách thêm vào một bộ tạo số ngẫu nhiên với kết quả dựa trên superstep và các phần được phân. Thuật toán không xác định có thể vô hiệu hóa giới hạn phục hồi và trở lại cơ chế phục hồi cơ bản. 4.3 Cài đặt máy thợ Một máy thợ lưu trữ trạng thái của phân vùng đồ thị của nó trong bộ nhớ. Khái niệm này có thể hiểu như một bảng quy chiều từ ID của đỉnh đến trạng thái của từng đỉnh, trạng thái của từng đỉnh bao gồm giá trị hiện tại của nó, một danh sách các cạnh đi từ nó ra (cạnh đi ra từ nó bao gồm ID của đỉnh, và giá trị hiện tại của cạnh), một hàng đợi bao gồm những thông điệp gửi tới, và một cờ để chỉ định đỉnh có hoạt động hay không. Khi một máy thợ thực hiện một superstep nó duyệt qua tất cả các đỉnh và gọi Compute(), truyền vào đó giá trị hiện tại, một con trỏ lặp đến các thông điệp gửi tới, và một con trỏ lặp đến các cạnh đi ra. Không có truy nhập đến các cạnh đi vào vì mỗi cạnh đi vào là một phần của một danh sách lưu b ởi đỉnh nguồn, thường ở một máy tính khác. Vì vấn đề về hiệu năng, cờ của các đỉnh đang hoạt động được lưu trữ một cách riêng biệt với hàng đợi các thông điệp gửi tới. Hơn nữa, trong khi chỉ có một bản sao lưu của đỉnh và giá trị cạnh tồn tại, thì có tới 2 bản sao lưu của cờ của đỉnh hoạt động và hàng đợi các thông điệp gửi tới: một bản cho superstep hiện tại và bản còn lại cho superstep tiếp theo. Trong khi các

máy thợ xử lý đỉnh của nó trong superstep S, trong một luồng khác, nó nhận các thông điệp từ những máy thợ khác đang thực thi cùng superstep. Vì các đỉnh nhận được thông điệp mà được gửi tới trong superstep trước đó, các thông điệp cho superstep S và S + 1 phải được giữ riêng biệt. Tương tự, các thông điệp đến đỉnh V nghĩa là V sẽ hoạt động trong superstep tiếp theo, mà không nhất thiết phải là superstep hiện tại. Khi Compute() yêu cầu gửi một thông điệp tới một đỉnh khác, đầu tiên máy thợ sẽ quyết định xem đỉnh đích có thuộc máy khác hay không hay thuộc chính máy đó. Nếu đỉnh đích thuộc máy ngoài, thông điệp được đưa vào buffer để đưa đến máy đích. Khi kích thước của buffer đạt một ngưỡng nhất định, buffer lớn nhất bị xóa một cách bất đồng bộ, gửi từng thông điệp đến máy đích như một thông điệp đơn. Trong trường hợp đỉnh đích thuộc máy gửi, thông điệp sẽ được đưa trực tiếp vào hàng đợi các thông điệp đến của đỉnh đích. Nếu người dùng sử dụng bộ kết hợp, nó sẽ được thực thi khi các thông điệp được đưa vào hàng đợi các thông điệp gửi đi và khi chúng được nhận tại hàng đợi các thông điệp gửi tới. Khi chúng được nhận, chúng sẽ không làm giảm lượng băng thông được sử dụng, nhưng làm giảm bộ nhớ cần để lưu trữ các thông điệp. 11. 11. 4.4 Cài đặt máy chủ chính Máy chủ chính có chức năng điều phối các hoạt động của các máy thợ. Mỗi máy thợ được gán một định danh duy nhất ở thời điểm nó được thêm vào hệ thống. Máy chủ chính lưu trữ danh sách các máy thợ hiện tại đang hoạt động, bao gồm định danh, thông tin về địa chỉ, phần đồ thị mà nó quản lý. Kích thước của cấu trúc dữ liệu của máy chủ chính tỉ lệ với lượng máy thợ, chứ không phải lượng đỉnh hay cạnh, vì thế mỗi máy chủ chính có thể điều phối tính toán cho cả những đồ thị rất lớn. Hầu hết các hoạt động của máy chủ chính, bao hồm đầu vào, đầu ra, tính toán, lưu trữ và phục hồi từ các mốc đều kết thúc tại điểm biên: máy chủ chính gửi cùng một thông điệp đến các máy thợ đang được cho là hoạt động từ lúc bắt đầu phiên làm việc và đợi phàn hồi từ những máy đó. Nếu bất kỳ máy thợ nào gặp lỗi, máy chủ chính sẽ được đưa vào trạng thái phục hồi. Nếu điểm biên đồng bộ thành công, máy chủ chính tiếp tục phiên làm việc tiếp theo. Ví dụ như trong trường hợp nếu một điểm biên tính toán, máy chủ chính sẽ tăng chỉ số của superstep toàn cục và xử lý tiếp superstep tiếp theo. Máy chủ chính cũng thống kê về quá trình tính toán và trạng thái của đồ thị, như tổng kích thước của đồ thị, biểu đồ thống kê sự phân tán của các cạnh, số lượng đỉnh đang hoạt động, thời gian và lưu lượng thông điệp của những superstep gần đấy, và giá trị của tất cả aggregator mà người dùng định nghĩa. Để kích hoạt giao diện người dùng, máy chủ chính chạy những server HTTP hiển thị các thông tin. 4.5 Aggregators Một aggregator tính toán một giá trị toàn cục bằng cách áp dụng một hàm kết tập cho một tập những giá trị mà người dùng cung cấp. Mỗi máy thợ duy trì một tập các aggregator, định danh bởi kiểu và tên. Khi một máy thợ thực thi một superstep cho bất kỳ phần nào của đồ thị, nó sẽ kết hợp tất cả các giá trị được cung cấp cho biến aggregator thành một giá trị cục bộ duy nhất: một aggreagator tối giản trên tất cả các đỉnh của máy thợ trong phần đó. Đến cuối superstep các máy thợ hình thành một cây để tối giản các aggregator đã được tối giản thành một giá trị toàn cục và chuyển nó đến máy chủ chính. Sử dụng tối giản cây cân bằng hơn là sử dụng đường ống với một chuỗi các máy thợ để sử dụng CPU song song trong khi giảm tải. Máy chủ chính gửi các giá trị toàn cục tới tất cả các máy thợ tại đầu superstep tiếp theo. 5. Các ứng dụng 5.1 Phân hạng trang Cách áp dụng Pregel với thuật toán PageRank được chỉ ra ở hình 4. Lớp `PageRankVertext` được kế thừa từ `Vert ex`. Các đỉnh của chúng có giá trị thuộc kiểu `dou ble` để chứa các giá trị không chắc chắn để phân hạng trang, và các thông điệp của chúng có kiểu `double` mang giá trị là các phân số phân hạng tr ang, trong khi đó giá trị các cạnh thuộc kiểu `voi d` bởi vị các cạnh không lưu trữ bất cứ thông tin nào. Chúng ta giả sử rằng đồ thị được khởi tạo đ ể trong superstep thứ 0, giá trị của mỗi đỉnh là `1 / NumVertices()` (1/ số lượng các đỉnh). Trong từng superstep của 30 superstep đầu tiên, mỗi đỉnh gửi tới mỗi cạnh đi ra từ chún g giá trị phân hạng trang chia cho số đỉnh đi ra từ nó. class PageRankVertex : public Vertex<double, void, double> { public: virtual void Compute(MessageIterator* msgs) { if (superstep() >= 1) { double sum = 0; 12. 12. for (; !msgs->Done(); msgs- >Next()) sum += msgs- >Value(); *MutableValue() = 0.15 / NumVertices() + 0.85 * sum; } if (superstep() < 30) { const int64 n =

GetOutEdgeIterator().size(); SendMessageToAllNeighbors(GetValu e() / n); } else { VoteToHal t(); } } }; Figure 4: PageRank implemented in Pregel. Bắt đầu từ superstep 1, mỗi đỉnh tính tổng các giá trị trên các thông điệp lại thành `sum` và gán giá trị không chắc chắn đó cho việc phân hạng trang là `0.15 / NumVertices() + 0.85 * sum`. Sau khi tới superstep 30, không có thêm thông điệp nào được gửi đi và mỗi cạnh tự đề xuất ngắt, Trong thực tế, một thuật toán phân hạng trang sẽ chạy cho tới khi đạt đến điểm hội tụ và các aggregators sẽ được sử dụng để xác định điều kiện hội tụ. 5.2 Shortest Paths Bài toán các tuyến đường ngắn nhất là một trong những bài toán được biến đến nhiều nhất trong lý thuyết đồ thị và xuất hiện trong nhiều ứng dụng với nhiều biến thể. Bài toán tuyến đường ngắn nhất với một đỉnh nguồn yêu cầu tìm một đường ngắn nhất giữa một đỉnh nguồn với các đỉnh khác trong đồ thị. Bài toán đường đi s-t ngắn nhất yêu cầu tìm một đường đi đơn ngắt nhất giữa hai đỉnh s và t cho trước, nó có ứng dụng thực tế là chỉ đường và thu hút lượng lớn sự quan tâm. Nó cũng là vấn đề có lời giải tương đối đơn giản trong các đồ thị đặc trưng như mạng lưới các tuyến đường với một phần nhỏ của các đỉnh. Với việc khảo sát của Lumsdaine et al lên tới 80000 đỉnh và trong 32 triệu đỉnh trong một ví dụ. Biến thể thứ ba, tất cả các cặp đường ngắn nhất là không thực tế đối với đồ thị lớn bởi vì nó yêu cầu độ phức tạp O(|V|^2) về bộ nhớ. Để đơn giản và rõ ràng, chúng ta tập trung vào biến thể bài toán một nguồn vì nó phù hợp với việc xử lý đồ thị lớn của Pregel, nhưng những dữ liệu mở rộng khác thú vị hơn vấn đề đường đi ngắn nhất s-t. Một cài đặt được thể hiện ở Hình 5. Trong giải thuật này, chúng ta giả sử rằng giá trị liên quan đến các đỉnh được thiệt lập ban đầu là INF (một giá trị lớn hơn bất kỳ một khoảng cách khả thi nào trong đồ thị từ đỉnh nguồn). Trong một superstep, đầu tiền mỗi đỉnh sẽ nhận thông điệp từ các đỉnh xung quanh, cập nhật lại khoảng cách có thể là ngắn nhất từ đỉnh nguồn. Nếu như khoảng cách ngắn nhất trong cập nhật nhỏ hơn giá trị hiện tại của đỉnh, thì đỉnh sẽ cập nhật lại giá trị của nó và gửi những cập nhật đến các đỉnh lân cận, bao gồm trọng số của từng cạnh đi ra cộng với khoảng cách ngắn nhất vừa tìm được. Trong superstep đầu tiên, chỉ có đỉnh nguồn sẽ cập nhật giá trị của nó (từ INF thành 0) và gửi cập nhật tới các đỉnh lân cận của nó. 13. 13. class ShortestPathVertex : public Vertex { void Compute(MessageIterator* msgs) { int mindist = IsSource(vertex_id()) ? 0 : INF; for (; !msgs->Done(); msgs- >Next()) mindist = min(mindist, msgs- >Value()); if (mindist < GetValue()) { *MutableValue() = mindist; OutEdgeIterator iter = GetOutEdgeIterator(); for (; !iter.Done(); iter.Next()) SendMessageTo(iter.Target(), mindist + iter.GetValue()); } VoteToHalt(); } }; Figure 5: Singlesource shortest paths. class MinIntCombiner : public Combiner { virtual void Combine(MessageIterator* msgs) { int mindist = INF; for (; !msgs->Done(); msgs- >Next()) mindist = min(mindist, msgs->Value()); Output("combined_source", mindist); } }; Figure 6: Combiner that takes minimum of message values. Những đỉnh lân cận lần lượt sẽ cập nhật lại giá trị của chúng và gửi các thông điệp, kết quả là một làn sóng của những cập nhật xuyên suốt đồ thị. Thuật toán kết thúc khi không còn cập nhật, sau đó giá trị của từng đỉnh biểu thị khoảng cách nhỏ nhất từ đỉnh nguồn đến đỉnh đó. (Gía trị INF thể hiện là đỉnh đó không thể đi tới được ). Việc kết thúc sẽ chắc chắn xảy ra nếu tât cả chỉ số của tất cả các cạnh đều không âm. Các thông điệp trong thuật toán này bao gồm các khoảng cách có thể là ngắn nhất. Vì đỉnh nhận sẽ chỉ quan tâm đến cái nhỏ nhất, thuật toán này có thể tối ưu bằng cách sử dụng bộ kết hợp. Bộ kết hợp được thể hiện trong hình 6 làm giảm lượng lớn dữ liệu truyền đi giữa 2 máy thợ, cũng như là lượng dữ liệu trong buffer trước khi xử lý trong superstep tiếp theo. Trong khi các câu lệnh trong hình 5 chỉ tính toán các khoảng cách, thay đổi nó để tính toán cây đường đi ngắn nhất một cách đơn giản. Thuật toán này có thể thực hiện nhiều phép so sánh hơn các thuật toán như Dijkstra hay Bellman-Ford, nhưng nó có khả năng xử lý vấn đề đường đi ngắn nhất ở một quy mô mà không thể thực thi với bất kỳ cài đặt trên một máy đơn nào. Có những thuật toán song song cao cấp hơn, ví dụ như Thorup hay thuật toán delta và đã được sử dụng như cài đặt cơ bản cho các mục đích chạy song song. Những thuật toán cao cấp như thế có thể được cài đặt trong pregel framework. Tuy nhiên, tính đơn giản trong cài đặt ở hình 5 với hiệu năng ở mức có thể chấp nhận phù hợp đối với những người mà không thể làm các tinh chỉnh lớn hay tự cài đặt. 5.3 Ghép nối

Đầu vào của một thuật toán ghép nỗi bao gồm 2 bộ đỉnh độc lập cùng với các cạnh và đầu ra là tập con của các cạnh mà không có điểm cuối chung. Sự kết hợp tối đa là khi không thể có thêm cạnh nào mà không có chung điểm ra. 14. 14. Một thuật toán tối đa hóa ghép nối ngẫu nhiên và tối đa hóa ghép nối theo chỉ số được cài đặt. Chúng tôi sẽ miêu tả thuật toán tối đa hóa ghép nối theo chỉ số. Thuật toán này cài đặt với Pregel thì giá trị của đỉnh là một tập hợp của 2 giá trị: một cờ chỉ định tập mà định thuộc vào (Trái hoặc Phải) và tên của đỉnh ghép nối với nó khi mà được tìm thấy. Gía trị của cạnh có kiểu void (các cạnh không chưa thông tin), và thông điệp là dạng boolean. Thuật toán thực hiện các chu trình gồm 4 giai đoạn, với chỉ mục của từng giai đoạn là chỉ mục superstep mod 4, sử dụng bắt tay 3 bước. Trong giai đoạn 0 của chu trình, mỗi đỉnh bên trái chưa ghép nối gửi một thông điệp tới mỗi đỉnh lân cận của nó, yêu cầu ghép nối và đề xuất ngắt vô điều kiện. Nếu nó không gửi các thông điệp (bởi vì nó đã được kết nối hoặc nó không có cạnh đi ra) hoặc nếu tất cả các đỉnh nhận thông điệp đều đã ghép nối, nó sẽ không được khởi động lại. Ngược lại, nó sẽ nhận một thông điệp phản hồi trong 2 superstep và khởi động lại. Trong giai đoạn 1 của chu trình, mỗi đỉnh bên phải chưa được ghép nối sẽ ngẫu nhiên chọn một thông điệp mà nó nhận được, gửi một thông điệp phản hổi cho phép ghép nối và gửi tới các đỉnh còn lại thông điệp từ chối yêu cầu. Cuối cùng đề xuất ngắt. Trong giai đoạn 2 của chu trình, mỗi đỉnh bên trái chưa được ghép nối chọn một trong các thông điệp chấp nhận và gửi thông điệp chấp nhận kết nối. Các đỉnh bên trái đã được ghép nối sẽ không hoạt động trong giai đoạn này vì chúng sẽ không gửi thông điệp ở giai đoạn 0. Cuối cung, trong giai đoạn 3, mỗi đỉnh bên phải chưa ghép nối nhận nhiều nhất 1 thông điệp chấp nhận kết nối. Nó sẽ ghi lại đỉnh để ghép nối và đề xuất ngắt. 5.4 Bán phân cụm Pregel đã sử dụng một số phiên bản khác nhau của phân cum. Một phiên bản, bán phân cụm, phát sinh trong các đồ thị xã hội. Các đỉnh trong một đồ thị xã hội thường tượng trưng cho con người và các cạnh tượng trưng cho các mối quan hệ giữa họ. Các cạnh có thể dựa trên những hành động rõ ràng hoặc có thể dựa trên cách ứng xử của con người. Các cạnh có thể có các chỉ sô để biểu diễn độ thường xuyên và gắn bó của mối quan hệ. Một bán phân cum là một đồ thị xã hội thuộc một nhóm người mà thường xuyên tương tác với nhau và ít tương tác với những người khác. Điều làm nó khác biệt so với các loại phân cụm khác là một đỉnh có thể thuộc vào nhiều hơn một bán cụm. Phần này sẽ miêu tả lại một thuật toán bán phân cụm tham lam song song. Đầu vào là một chỉ số, một đồ thị vô hướng và đầu ra là nhiều nhất Cmax bán phân cụm, mỗi cái chưa nhiều nhất Vmax đỉnh, trong đó Cmax và Vmax là các tham số đầu vào do người dùng nhập. Một bán phân cụm c được phân một điểm số , trong đó Ic là tổng điểm số của tất cả các cạnh bên trong, Bc là tổng các điểm số của tất cả các cạnh biên, Vc là số đỉnh trong một bán phân cụm và fB là hệ số cạnh biên, là một tham số đầu vào của người dùng, thường nằm giữa 0 và 1. Chỉ số được chuẩn hóa tức là chia cho số cạnh trong một nhóm có kích thước Vc để các cụm lớn không nhận các điểm số lớn một cách bất thường. 15. 15. Mỗi đỉnh V giữ một danh sách chứa nhiều nhất Cmax các bán phân cụm, được sắp xếp theo điểm số. Trong superstep 0 V đưa mình vào danh sách đó như một bán phân cụm có kích thước 1 và điểm số 1, và thông báo cho các đỉnh lân cận. Trong chuỗi con các superstep: Đỉnh V lặp đi lặp lại trên bán cụm c1,...,ck gửi tới nó trong các superstep trước. Nếu một bán phân cụm c chưa chứa V , và Vc < Mmax thì V sẽ được thêm vào c để hình thành c0 . Các bán phân cụm c1 ,…, ck; c0 1,…, c0 k được sắp xếp theo điểm số và cái có chỉ số lớn nhật được gửi đến các đỉnh lân cận của V. Đỉnh V cập nhật danh sách của mình về các bán phân cụm với những bán phân cụm từ c1,…, ck, c0 1,…, c0 k mà có chứa V. Thuật toán ngắt khi các bán phân cụm ngừng thay đổi hoặc khi số lượng superstep đạt đến ngưỡng mà người dùng chỉ định. Tại thời điểm đó danh sách các bán phân cụm tốt nhất cho từng đỉnh có thể được At that point the list of best semi-cluster candidates for each vertex may be tổng hợp thành một danh sách toàn cục các bán phân cụm tốt nhất. 6. Thí nghiệm Nhiều thí nghiệm được thực hiện trên cùng một cài đặt của thuật toán đường đi ngắn nhất từ 1 điểm nguồn trên một nhóm 300 PC nhiều nhân thông dụng. Theo thống kê thời gian chạy của cây nhị phân và đồ thị lognormal ngẫu nhiên sử dụng nhiều kích thước đồ thị với

trọng số của tất cả các cạnh ngầm định là 1. Thời gian để khởi tạo cụm, sinh đồ thị để kiểm tra trong bộ nhớ, và kiểm tra kết quả không được tính vào trong các đánh giá. Vì tất cả các thí nghiệm có thể chạy trong một thời gian tương đối ngắn, khả năng gặp lỗi khá thấp và các điểm mốc bị vô hiệu hóa. Như một số chỉ các Pregel đánh giá hiệu năng máy thợ, Hình 7 cho thấy thời gian chạy thuật toán đường đi ngắn nhất với cây nhị phân 1 triệu đỉnh khi số lượng máy thợ Pregel có gía trị từ 50 đến 800. Số máy thợ tăng lên 16 lần thì tốc độ tăng lên 10 lần, thời gian từ 174 giây giảm xuống con 17,3 giây. Để cho thấy khả năng mở rộng của Pregel với kích thước đồ thị, hình số 8 thể hiện thời gian chạy thuật toán đường đi ngắn nhất cho cây nhị phân có kích thước đa dạng từ 1 tỉ đến 50 tỉ đỉnh, bây giờ sử dụng một số xác định Figure 7: SSSP - 1 billion vertex binary tree: vary- ing number of worker tasks scheduled on 300 multi-core machines Figure 8: SSSP|binary trees: varying graph sizes on 800 worker tasks scheduled on 300 multicore ma-chines là 800 máy thợ lập lịch trên 300 máy nhiều nhân. Ở đây thời gian tăng từ 17,3 đến 702 giây cho thấy với những đồ thị với các cạnh đi ra thấp thời gian chạy tăng tuyến tính theo kích thước đồ thị. Mặc dù thí nghiệm trước cho thấy chỉ số của Pregel để đánh giá các máy thợ và kích thước đồ 16. 16. thị, các cây nhị phân rõ ràng không đại diện cho các đồ thị trong thực tế. Vì vậy, chúng ta cũng có thể tiến hành các thí nghiệm với các đồ thị ngẫu nhiên sử dụng phân bố log-nomal của các cạnh đi ra, Với µ = 4 và σ = 1,3 thì trung bình số cạnh đi ra là 127,1 . Sự phân tán nay tương tự nhiều đồ thị lớn trong thực tế, ví dụ như đồ thị Web hoặc các mạng xã hội, nơi hầu hết các đỉnh có ít cạnh nhưng một số ngoại lai lại lớn hơn một trăm nghìn hay hơn. Hình số 9 cho thấy thời gian chạy thuật toán đường đi ngắn nhất cho những loại đồ thị đó với nhiều loại kích cỡ từ 10 triệu đến một 1 tỉ đỉnh (cùng với hơn 127 tỉ cạnh), một lần nữa với 800 máy thợ lập lịch trên 300 máy nhiều nhân. Chạy thuật toán đường đi ngắn nhất cho một đồ thị lớn nhất cần hơn 10 phút. Trong tất cả các thí nghiệm, đồ thị được phân ra các máy thợ sử dụng hàm phân chia mặc định dựa trên phân chia ngẫu nhiên; một hàm phân chia nhận biết được topo sẽ cho hiệu năng tốt hơn. Hơn nữa, một thuật toán đường đi ngắn nhất song song na¨ıve được sử dụng Figure 9: SSSP|log-normal random graphs, mean outdegree 127.1 (thus over 127 billion edges in the largest case): varying graph sizes on 800 worker tasks scheduled on 300 multicore machines 17. 17. Đây cũng là một thuật toán nân cao giúp nâng cao hiệu năng. Vì vậy, kết quả của thí nghiệm trong phần này không phải là hiệu năng lớn nhất của thuật toán đường đi ngắn nhất viết bằng Pregel. Thay vào đó, các kết quả không được sử dụng để cho thấy sự thỏa đáng của hiệu năng có thể có được mà không tôn công sức code. Trên thực tế, kết quả với 1 tỷ đỉnh và cạnh so với kết quả thuật toán đường deltaIn có được từ Parallel BGL là đáng chú ý đối với một nhóm 112 bộ vi xử lý trên một đồ thị 256 triệu đỉnh và 1 tỉ cạnh và quy mô của Pregel lớn hơn kích thước đó. 7. Những công trình liên quan Pregel là một framework cho lập trình phân tán, Tập trung vào việc cung cấp cho người dùng một API tự nhiên để lập trình thuật toán đồ thị khi quản lý chi tiết sự rõ ràng của hệ phân tán, bao gồm gửi thông điệp và chống chịu lỗi. Nó tương tự MapReduce về tư tưởng, nhưng với một API đồ thị tự nhiên và nhiều hỗ trợ hiệu quả cho tính lặp của tính toán trên đồ thị. Đồ thị cũng tập trung vào việc tạo sự khác biệt giữa nó và những framework khác mà giấu chi tiết về phân tán như Sawzall, Pig Latin và Dryad. Pregel cũng khác biệt vì nó tập trung cài đặt mô hình trạng thái mà những tiến trình được tính toán, truyền tải và thay đổi trạng thái cục bộ dài hạn hơn là một mô hình dòng data mà bất kỳ tiến trình nào cũng chỉ tính toán chỉ trên data đầu vào và tạo ra data đầu ra bởi những tiến trình khác. Pregel được lấy cảm hứng từ mô hình Bulk Synchronous Parallel, mô hình mà cung cấp mô hình đồng bộ superstep, tính toán và truyền thông của nó. Đã có nhiều thư viện BSP phổ thông được được cài đặt, ví dụ như thư viện BSP Oxford Oxford BSP Library, Green BSP, BSPlib và thư viện BSP của trường đại học Paderborn. Chúng đa dạng về tập giao tiếp ban đầu được cung cấp và cách chúng xử lý các vấn đề về phân tán như độ tin cậy, cân bằng tải và đồng bộ hóa. Khả năng mở rộng và chịu lỗi của các cài đặt BSP chưa được đánh giá ở mức cao hơn vài chục máy và không máy nào cung một API đồ thị nhất định. Thư viện gần nhất vơi Pregel là Parallel Boost Graph Library và CGMgraph. Parallel BGL chỉ rõ một số khái niệm mấu chốt chung về định nghĩa

đồ thị phân tán, cung cấp cài đặt dựa trên MPI, và cài đặt một số thuật toán dựa trên chúng. Nó có giữ sự đồng bộ với BGL để tạo điều kiện cho thuật toán dùng cổng. Nó thêm bảng các thuộc tính để giữ liên kết dữ liệu với các đỉnh và các cạnh trong đồ thị, sử dụng các ghost cell để giữ giá trị liên quan đến các phần tử ở xa. Điều này có thể dẫn đến các vấn đề về quy mô nếu cần gọi đến quá nhiều phần tử ở xa. Pregel sử dụng thông điệp ngầm để lấy thông tiên từ xa và không sao chép lại giá trị đó vào cục bộ. Điểm khác biệt lớn nhất là Pregel có khả năng chịu lỗi phòng trừ lỗi xảy ra trong khi tính toán, cho phép nó trong một nhóm môi trường lớn mà thường xuyên gặp lỗi, dù là lỗi phần cứng hay ưu tiên một công việc nào đó. CGMgraph có tư tưởng tương tụ, cung cấp một số thuật toán đồ thị song song sử dụng mô hình dựa trên MPI Coarse Grained Mul- ticomputer (CGM). Nó nằm bên dưới cơ chế phân tán, và tập trùng vào cung cấp các cài đặt của các thuật toán hơn là cơ sở hạ tầng cần để sử dụng chúng. 18. 18. Ngược lại phong cách lập trình tổng quát của Parallel BGL và Pregel, CGMgraph sử dụng phong cách lập trình theo hướng đối tương cho một số chi phí về hiệu năng. Ngoài Pregel và Parallel, đã có một số hệ thống có các thí nghiệm với các đồ thị ở mức 1 tỉ đỉnh. Đồ thị lớn nhất được sử dụng là từ thống kê của một cài đặt tự viết của thuật toán đường đi ngắn nhất s-t chử không phải một framework phổ thông. Yoo et al thống kê trên một cài đặt tìm kiếm theo chiều rộng BlueGene/L trên 32,768 bộ vi xử lý PowerPC với mạng torus hiệu năng cao, cho thấy hiệu năng đạt tới 1,5 giây mỗi đồ thị phân tán ngẫu nhien Poisson với 3,2 tỉ đỉnh và 32 tỉ cạnh. Bader và Madduri báo cáo về một cài đặt Cray MTA-2 của một vấn đề tương tự trên một hệ thống 10 nút, đa luồng tốc độ cao, kết quả đạt được 0,43 giay cho một R-MAT đồ thị ngẫu nhiên kích thước bất kỳ với 134 triệu đỉnh và 805 triệu cạnh. Lumsdaine et al so sánh kết cuarcuar Parallel BGL trên một cụm Opteron x86-64 của 200 bộ vi xử lý với cài đặt BlueGene/L, kết quả đạt được 0,43 giây cho một đồ thị ngẫu nhiên Erdo˝s-Renyi với 4 tỉ đỉnh và 20 tỉ cạnh. Chúng cps hiệu năng tốt hơn ghost cells và theo thực nghiệm thì hiệu năng bắt đầu giảm nếu có từ 32 bộ vi xử lý trở lên. Những kết quả cho bài toán đường đi ngắn nhất từ một nguồn trên một đồ thị ngẫu nhiên với 256 triệu đỉnh và số cạnh đi ra không đồng bộ 4, sử dụng thuật tón delta, được thống kề cho Cray MTA-2 và cho Parallel BGL trên Opterons. Cái thứ 2 tương tự với kết quả của 400 máy thợ của Pregel cho một cây nhị phân với 1 tỉ nút và cạnh. Chưa có thống kê về kết quả cho SSSP trên kích thước 1 tỉ đỉnh và 127,1 tỉ cạnh đồ thị log- normal. 8. Kết luận và cải tiến trong tương lai. Đóng góp của bài báo này là một mô hình phù hợp với cách tính toán trong đồ thị lớn và một miêu tả cách cài đặt về chất lượng sản phẩm, khả năng mở rộng, khả năng chịu lỗi. Dựa vào các đầu vào của người dùng, chúng tôi nghĩ chúng tôi đã thành công trong việc tạo ra một mô hình hữu ích và có thể sử dụng được. Rất nhiều các ứng dụng Pregel đã được triển khai và sẽ có nhiều ứng dụng hơn nữa đang được thiết kế, cài đặt và tinh chỉnh. Người dùng phản hồi cho chúng tôi rằng một khi họ chuyển qua chế độ lập trình “nghĩ mình như một đỉnh”, API sẽ trực quan, linh hoạt và đơn giản hơn khi sử dụng. Điều này không ngạc nhiên bởi vì chúng tôi đã làm việc với “các người chấp nhận” – người mà ảnh hưởng đến API từ những bước đầu. Ví dụ, các aggregators đã được thêm vào để xóa đi các giới hạn người dùng tìm được trong các mô hình Pregel trước. Các khía cạnh sử dụng của Pregel đã được thúc đẩy bởi kinh nghiệm người dùng bao gồm một tập các trang trạng thái với thông tin chi tiết về quá trình của chương trình Pregel, một unittesting framework, một chế độ máy đơn – cái mà đã giúp tăng tốc tạo mẫu và sửa lỗi. Hiệu năng, tính khả mở và khả năng chịu lỗi của Pregel đạt yêu cầu đối với các đồ thị với hàng tỉ đỉnh. Chúng tôi đang nghiên cứu kỹ thuật để mở rộng các đồ thị lớn hơn, như là giảm bớt tính đồng bộ của mô hình để tránh chi phí các máy thợ nhanh phải đợi thường xuyên tại điểm biên liên superstep. Hiện tại toàn bộ trạng thái tính toán đang được lưu trữ trên RAM. Chúng tôi đã thiết kế để dữ liệu có thể lưu trong ổ đĩa và chúng tối sẽ tiếp tục theo hướng này để có thể tính toán trên các đồ thị lớn khi dữ liệu lên đến hàng terabytes và bộ nhớ chính sẽ không thể chứa nổi. 19. 19. Việc gán các cạnh đến các máy để giảm thiểu tối đa giao tiếp liên máy là một thách thức. Phân mảnh đồ thị đầu vào dựa trên cấu trúc có thể đáp ứng được nếu cấu trúc tương đương với lưu lượng thông điệp nhưng nó không thể. Chúng tôi mong muốn đưa ra các cơ

chế phân mảnh lại và các cơ chế này là linh hoạt. Pregel được thiết kế cho các đồ thị thưa – nơi mà việc giao tiếp chủ yếu xảy ra qua các cạnh, và chúng tôi không mong muốn tập trung để thay đổi. Mặc dù đã quan tâm để hỗ trợ lưu lượng lớn, nhưng hiệu năng sẽ không được đảm bảo khi hầu hết các đỉnh gửi các thông điệp cùng lúc tới các đỉnh khác. Tuy nhiên, trong thực tế, các đồ thị dày rất hiếm, cũng như các giải thuật với sự giao tiếp dày đặc qua một đồ thị thưa là rất hiếm gặp. Một vài giải thuật có thể biến đổi thành các biến thể của Pregel một cách thân thiện hơn, ví dụ như sử dụng các combiners, aggregators hoặc biến đổi cấu trúc và đương nhiên là việc tính toán sẽ trở nên khó khăn đối với bất kỳ hệ thống có mức độ phân tán cao nào. Thực tế cho thấy rằng Pregel đang trở thành một phần của nền tảng sản phẩm cho nền tảng người dùng của chúng tôi. Chúng tôi sẽ không tự do thay đổi API mà không cân nhắc đến sự tương thích. Tuy nhiên, chúng tôi tin rằng giao diện lập trình mà chúng tôi đã thiết kế đủ tính khái quát và linh hoạt cho sự phát triển sau này của các hệ thống nền tảng.