Tổng quan nghiên cứu

Trong kỷ nguyên bùng nổ công nghệ thông tin và mạng xã hội, các hệ thống mạng quy mô lớn như Facebook, Twitter, mạng lưới giao thông thông minh hay mạng sinh học ghi nhận tốc độ tăng trưởng dữ liệu chóng mặt với hàng chục triệu người dùng và hàng trăm triệu liên kết. Điển hình, mạng xã hội LiveJournal có gần 10 triệu thành viên với hơn 68 triệu kết nối, hay mạng Pokec sở hữu hơn 1,6 triệu người dùng và trên 30 triệu liên kết. Thách thức cốt lõi đặt ra là làm thế nào để giải quyết bài toán tìm đường đi ngắn nhất giữa hai thực thể trong thời gian thực khi đồ thị liên tục biến động với hàng trăm nghìn thao tác thêm và xóa cạnh mỗi phút.

Luận văn thạc sĩ chuyên ngành Hệ thống thông tin của tác giả Phạm Hải Đăng, dưới sự hướng dẫn khoa học của Phó Giáo sư Nguyễn Ngọc Hóa tại Trường Đại học Công nghệ – Đại học Quốc gia Hà Nội, tập trung giải quyết triệt để bài toán tối ưu hóa truy vấn tìm đường ngắn nhất trên đơn đồ thị động, có hướng và không trọng số ở quy mô dữ liệu lớn. Mục tiêu cụ thể của công trình là xây dựng cấu trúc dữ liệu lưu trữ đồ thị tối ưu bộ nhớ đệm CPU, phát triển thuật toán duyệt hai hướng có khả năng dự đoán không gian tìm kiếm, và ứng dụng công nghệ tính toán song song đa lõi để đạt tốc độ xử lý nhanh nhất có thể.

Phạm vi nghiên cứu bao quát các tập dữ liệu đồ thị có quy mô từ 1,5 triệu đến hơn 6 triệu đỉnh và từ 3,2 triệu đến gần 69 triệu cạnh. Nghiên cứu mang ý nghĩa thực tiễn to lớn khi giúp giảm 32 lần dung lượng bộ nhớ dùng để đánh dấu trạng thái duyệt đỉnh, xử lý thành công khối lượng 1.000.000 sự kiện biến động liên tục và đưa giải pháp của nhóm tác giả lọt vào nhóm 5 đội xuất sắc nhất thế giới tại cuộc thi lập trình quốc tế danh giá ACM SIGMOD Programming Contest năm 2016.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu được xây dựng trên nền tảng lý thuyết đồ thị hiện đại, biểu diễn đồ thị có hướng không trọng số dưới dạng tập hợp các đỉnh và các cung nối có thứ tự. Trong cấu trúc này, khoảng cách giữa hai đỉnh được đo bằng số lượng cạnh trung gian ít nhất kết nối giữa chúng. Để giải quyết triệt để vấn đề hiệu năng trên đồ thị lớn, luận văn vận dụng lý thuyết phân cấp độ trễ bộ nhớ của kiến trúc vi xử lý hiện đại năm 2016. Theo đó, thời gian truy xuất bộ nhớ đệm L1 chỉ mất khoảng 0,5 nano-giây, bộ nhớ đệm L2 mất khoảng 4 nano-giây, trong khi truy xuất bộ nhớ chính (RAM) mất tới 100 nano-giây, tức chậm hơn tới 200 lần so với L1.

Khung lý thuyết của luận văn tích hợp ba khái niệm và mô hình nền tảng:

  • Thuật toán duyệt đồ thị theo chiều rộng hai hướng (Bi-directional Breadth-First Search - BBFS) nhằm thu hẹp không gian tìm kiếm từ cả đỉnh nguồn và đỉnh đích.
  • Tối ưu hóa tỷ lệ trúng bộ nhớ đệm (Cache hit ratio) thông qua việc tổ chức dữ liệu liên tiếp trong bộ nhớ phẳng thay vì sử dụng danh sách liên kết truyền thống.
  • Mô hình lập lịch tính toán song song đa luồng tận dụng sức mạnh phần cứng đa lõi, đa bộ vi xử lý.

Phương pháp nghiên cứu

Nghiên cứu sử dụng phương pháp thực nghiệm định lượng kết hợp đo lường hiệu năng trực tiếp trên các bộ dữ liệu chuẩn quốc tế. Cỡ mẫu nghiên cứu bao gồm 4 bộ dữ liệu thi đấu chính thức từ ACM SIGMOD Contest 2016 với quy mô từ mức Small (1.574.074 đỉnh, 3.232.855 cạnh) đến mức XX-Large (6.009.555 đỉnh, 16.518.948 cạnh, bậc ra lớn nhất 12.770), cùng 2 bộ dữ liệu mạng xã hội thực tế từ nền tảng SNAP của Đại học Stanford là Pokec (1.632.803 đỉnh, 30.622.564 cạnh) và LiveJournal (4.847.571 đỉnh, 68.993.773 cạnh, bậc vào lớn nhất đạt 20.293).

Phương pháp chọn mẫu kiểm thử được thực hiện thông qua công cụ sinh tự động có kiểm soát với tổng khối lượng 1.000.000 sự kiện cho mỗi đồ thị. Dữ liệu kiểm thử được phân bổ theo tỷ lệ chuẩn 8:1:1, bao gồm 800.000 truy vấn tìm đường ngắn nhất, 100.000 sự kiện thêm cạnh mới và 100.000 sự kiện xóa cạnh.

Lý do lựa chọn phương pháp phân tích thực nghiệm so sánh định lượng là nhằm kiểm chứng chính xác độ trễ thực thi tính bằng giây và mili-giây trên môi trường phần cứng thực tế gồm hệ thống máy chủ 2 chip Intel E5-2620v2 (12 nhân, 24 luồng, 20GB RAM) và máy chủ 4 chip Intel Xeon E7-4850 (10 nhân, 20 luồng, 128GB RAM). Phương pháp này cho phép so sánh khách quan giải pháp đề xuất với các nền tảng phân tích đồ thị danh tiếng như Stanford Network Analysis Platform (SNAP C++) và giải pháp tham chiếu chuẩn. Toàn bộ quá trình thực nghiệm, hiệu chỉnh thuật toán và đánh giá kết quả được hoàn thành trọn vẹn trong năm 2016.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Quá trình thực nghiệm đã chứng minh tính ưu việt của mô hình tối ưu thông qua bốn phát hiện cốt lõi:

Thứ nhất, cấu trúc dữ liệu danh sách kề phẳng kép gồm các mảng số nguyên 4 byte liên tiếp (incoming_edges, incoming_index và outgoing_edges, outgoing_index) kết hợp kỹ thuật di chuyển phần tử xuống cuối mảng khi thêm cạnh giúp loại bỏ hoàn toàn hiện tượng phân mảnh bộ nhớ. Phương pháp này giảm thiểu triệt để tỷ lệ trượt bộ nhớ đệm (cache miss) so với kỹ thuật cấp phát khoảng trống trước.

Thứ hai, thuật toán BBFS cải tiến với cơ chế dự đoán hướng đi 2 mức (2-Hop Lookahead) mang lại bước đột phá trong việc cắt tỉa không gian tìm kiếm. Thay vì chỉ so sánh số lượng đỉnh trong hàng đợi tại mức hiện tại, thuật toán ước lượng tổng số đỉnh vào và ra ở cả mức thứ nhất và mức thứ hai. Trong các kịch bản phân nhánh rộng, thuật toán đã giảm số lượng đỉnh cần nạp vào hàng đợi duyệt từ 9 đỉnh xuống chỉ còn 3 đỉnh, giúp cắt giảm hơn 60% không gian duyệt trung gian.

Thứ ba, kỹ thuật sử dụng mảng bit (Bit-vector) để đánh dấu trạng thái đỉnh đã xét mang lại hiệu quả vượt bậc về tài nguyên. Đối với đồ thị quy mô 1 triệu đỉnh, mảng số nguyên truyền thống đòi hỏi khoảng 4 megabyte bộ nhớ, trong khi mảng bit chỉ tiêu tốn 0,125 megabyte. Kỹ thuật này giúp giảm không gian bộ nhớ chính xác 32 lần, đồng thời các phép toán thao tác trực tiếp trên bit có tốc độ thực thi nhanh hơn từ 3 đến 5 lần so với thao tác trên mảng thông thường khi quy mô phép toán tăng từ 1.000 lên 100.000 thao tác.

Thứ tư, thư viện song song hóa Intel Cilk Plus chứng minh hiệu quả vượt trội so với OpenMP và Pthreads trong việc xử lý các lô truy vấn liên tiếp nhờ cơ chế đánh cắp công việc (work-stealing) và tự động cân bằng tải. Tại cuộc thi ACM SIGMOD Contest 2016, giải pháp của tác giả hoàn thành tập kiểm thử Small chỉ trong 0,878 giây, đứng trong nhóm 5 đội xuất sắc nhất toàn cầu bên cạnh đội vô địch đạt 0,333 giây.

Thảo luận kết quả

Nguyên nhân cốt lõi tạo nên sự vượt trội của giải pháp là việc thiết kế thuật toán bám sát kiến trúc phần cứng, tận dụng tối đa băng thông bộ nhớ đệm và khả năng xử lý song song mức luồng. Khi so sánh với các thư viện phổ biến như NetworkX hay SNAP, vốn chỉ xử lý tuần tự từng truy vấn hoặc gặp nghẽn nghiêm trọng khi cấu trúc đồ thị bị cập nhật liên tục, giải pháp trong luận văn đã đồng bộ hóa xuất sắc giữa luồng cập nhật cấu trúc và luồng xử lý truy vấn tìm kiếm.

Dữ liệu thực nghiệm được trực quan hóa sinh động qua các bảng biểu và đồ thị phân tích chuyên sâu. Biểu đồ đường thể hiện thời gian thực thi giữa thao tác bit và thao tác mảng cho thấy đường chi phí thời gian của mảng bit luôn duy trì ở mức tiệm cận 0 mili-giây ngay cả khi số lượng phép toán chạm mốc 100.000. Đồng thời, biểu đồ cột so sánh thời gian thực thi trên hai bộ dữ liệu SNAP Pokec và LiveJournal minh chứng rõ nét rằng thời gian phản hồi của thuật toán đề xuất ổn định hơn gấp nhiều lần so với giải pháp SNAP gốc khi phải xử lý đồng thời 800.000 truy vấn tìm đường và 200.000 thao tác cập nhật cạnh.

Đề xuất và khuyến nghị

Dựa trên các kết quả thực nghiệm vững chắc, luận văn đưa ra bốn khuyến nghị hành động mang tính ứng dụng cao:

Thứ nhất, các kỹ sư hệ thống dữ liệu lớn cần tái cấu trúc mô hình lưu trữ đồ thị mạng xã hội bằng cách áp dụng cấu trúc mảng kề liên tục kết hợp cặp chỉ mục vị trí và số lượng đỉnh. Mục tiêu là nâng cao tỷ lệ trúng bộ nhớ đệm L1/L2 lên trên 85%, giảm độ trễ truy xuất dữ liệu trong vòng 3 tháng tới.

Thứ hai, các nhóm phát triển hệ thống thông tin địa lý (GIS) và ứng dụng định vị dẫn đường GPS nên tích hợp thuật toán BBFS cải tiến với cơ chế dự đoán phân nhánh 2 mức. Giải pháp này giúp cắt giảm không gian duyệt đỉnh, hướng tới mục tiêu rút ngắn thời gian phản hồi truy vấn tìm đường xuống dưới 50 mili-giây trong quý tiếp theo.

Thứ ba, các kiến trúc sư phần mềm cần chuyển đổi toàn bộ cơ chế đánh dấu trạng thái duyệt đỉnh từ mảng số nguyên sang cấu trúc mảng bit (Bit-vector) trong tất cả các module xử lý đồ thị. Hành động này giúp giải phóng ngay 96,8% dung lượng RAM tiêu thụ cho mảng đánh dấu, cho phép hệ thống mở rộng quy mô phục vụ lên hàng chục triệu đỉnh mà không cần nâng cấp phần cứng.

Thứ tư, các doanh nghiệp công nghệ cần ứng dụng framework xử lý song song có khả năng tự động cân bằng tải như Intel Cilk Plus vào quy trình xử lý truy vấn hàng loạt. Lộ trình triển khai trong 6 tháng sẽ giúp hệ thống đạt mục tiêu thông lượng xử lý trên 10.000 truy vấn mỗi giây trên các máy chủ đa nhân tiêu chuẩn.

Đối tượng nên tham khảo luận văn

Công trình nghiên cứu mang lại giá trị học thuật và ứng dụng thực tiễn to lớn cho bốn nhóm đối tượng:

  • Kỹ sư phần mềm hạ tầng và kiến trúc sư hệ thống (System & Infrastructure Engineers): Khai thác các giải pháp tối ưu hóa bộ nhớ đệm CPU, kỹ thuật thao tác bit và cơ chế song song hóa luồng để xây dựng các công cụ xử lý dữ liệu thời gian thực có hiệu năng vượt trội.
  • Chuyên gia phân tích dữ liệu và kỹ sư đồ thị (Graph Data Engineers): Ứng dụng các thuật toán và mô hình biểu diễn đồ thị động quy mô hàng chục triệu cạnh để phân tích mạng lưới kết nối trên các nền tảng mạng xã hội và thương mại điện tử.
  • Học viên cao học và nghiên cứu sinh chuyên ngành Công nghệ thông tin, Khoa học máy tính: Sử dụng luận văn như một tài liệu tham khảo chuẩn mực về phương pháp nghiên cứu thực nghiệm, kỹ thuật tối ưu thuật toán lý thuyết đồ thị và cách thức xử lý dữ liệu lớn.
  • Doanh nghiệp công nghệ phát triển dịch vụ định vị, Logistics và Mạng xã hội: Vận dụng khung giải pháp của luận văn để nâng cấp công cụ tìm đường, tính toán khoảng cách tương tác giữa người dùng với chi phí đầu tư hạ tầng thấp nhất.

Câu hỏi thường gặp

Tại sao không sử dụng ma trận kề để biểu diễn đồ thị trong nghiên cứu này? Ma trận kề đòi hỏi không gian lưu trữ bậc hai theo số đỉnh. Với đồ thị quy mô hơn 6 triệu đỉnh như bộ dữ liệu XX-Large, ma trận kề cần hàng chục terabyte bộ nhớ, vượt quá giới hạn tài nguyên hệ thống, trong khi danh sách kề phẳng chỉ tiêu tốn không gian tuyến tính theo số đỉnh và số cạnh.

Thuật toán BBFS cải tiến 2 mức vượt trội hơn BBFS truyền thống ở điểm nào? BBFS truyền thống chỉ so sánh số lượng đỉnh trong hàng đợi ở mức hiện tại để chọn nhánh duyệt, dễ rơi vào nhánh bùng nổ liên kết ở bước sau. BBFS cải tiến dự đoán tổng số đỉnh ở cả mức một và mức hai, giúp giảm số đỉnh cần duyệt từ 9 đỉnh xuống 3 đỉnh trong các trường hợp phân nhánh rộng.

Tại sao phương pháp di chuyển phần tử xuống cuối mảng lại tối ưu hơn cấp phát khoảng trống trước khi thêm cạnh? Cấp phát trước tạo ra nhiều khoảng trống rỗng trong mảng, gây phân mảnh bộ nhớ và làm tăng tỷ lệ trượt bộ nhớ đệm khi duyệt. Chuyển phần tử xuống cuối mảng giữ cho toàn bộ dữ liệu đỉnh luôn nằm liên tiếp nhau, tối ưu hóa cơ chế nạp trước của bộ nhớ đệm vi xử lý.

Kỹ thuật mảng bit mang lại lợi ích cụ thể gì cho hệ thống? Mỗi phần tử đánh dấu trạng thái chỉ chiếm đúng 1 bit thay vì 4 byte (32 bit) như kiểu số nguyên thông thường. Điều này giúp giảm chính xác 32 lần dung lượng RAM (từ 4 megabyte xuống 0,125 megabyte cho 1 triệu đỉnh) và tận dụng trực tiếp các lệnh thao tác bit siêu nhanh của phần cứng CPU.

Vì sao Intel Cilk Plus được lựa chọn để song song hóa thay vì OpenMP hay Pthreads? Intel Cilk Plus sở hữu cơ chế lập lịch tác vụ ngẫu nhiên dựa trên thuật toán đánh cắp công việc và hỗ trợ tối ưu vector hóa tự động. Thử nghiệm thực tế chứng minh Cilk Plus mang lại hiệu năng cân bằng tải vượt trội và giảm độ trễ khóa đồng bộ tốt hơn hẳn OpenMP và Pthreads.

Kết luận

  • Luận văn đã giải quyết trọn vẹn bài toán tối ưu hóa truy vấn tìm đường ngắn nhất trên đồ thị động, có hướng, không trọng số quy mô hàng triệu đỉnh với tốc độ phản hồi tính bằng mili-giây.
  • Đề xuất cấu trúc dữ liệu danh sách kề phẳng kép tối ưu hóa bộ nhớ đệm CPU và cơ chế cập nhật cạnh động không gây phân mảnh bộ nhớ.
  • Phát triển thành công thuật toán BBFS cải tiến với cơ chế dự đoán không gian tìm kiếm 2 mức, giúp cắt giảm hơn 60% số lượng đỉnh duyệt trung gian.
  • Tiết kiệm 32 lần dung lượng bộ nhớ RAM và tăng tốc độ xử lý trạng thái đỉnh nhờ kỹ thuật mảng bit chuyên sâu.
  • Khẳng định chất lượng học thuật và giá trị thực tiễn quốc tế khi đạt thành tích Top 5 chung cuộc tại cuộc thi lập trình toàn cầu ACM SIGMOD Contest 2016 trên tập dữ liệu hơn 6 triệu đỉnh và 16,5 triệu cạnh.

Trong giai đoạn 12 tháng tiếp theo, nghiên cứu mở ra hướng phát triển mở rộng thuật toán sang đồ thị có trọng số và tích hợp trên các cụm máy chủ phân tán quy mô lớn. Quý độc giả, nhà nghiên cứu và kỹ sư hệ thống hãy khai thác toàn văn công trình để ứng dụng ngay các giải pháp tối ưu hóa đồ thị tiên tiến vào các bài toán công nghệ thực tế!