Tổng quan nghiên cứu

Trong kỷ nguyên số hóa và quản trị dữ liệu quy mô lớn, các hệ thống cơ sở dữ liệu phân tán ngày càng đóng vai trò huyết mạch trong việc bảo đảm khả năng mở rộng và tăng tốc độ xử lý thông tin. Thực tế cho thấy khối lượng truy vấn phức tạp trên môi trường phân tán đang tăng trưởng trung bình hơn 35% mỗi năm, dẫn đến hiện tượng tắc nghẽn đường truyền và làm gia tăng 40% đến 60% tổng thời gian thực thi nếu không có cơ chế tối ưu hóa phù hợp. Vấn đề cốt lõi đặt ra trong xử lý phân tán song song là làm thế nào để cực tiểu hóa chi phí truyền thông mạng phát sinh từ việc phân mảnh lại dữ liệu giữa các nút xử lý độc lập.

Nhằm giải quyết thách thức này, nghiên cứu tập trung xây dựng và đánh giá các thuật toán tô màu tối ưu cho cây truy vấn, chuyển đổi bài toán lập kế hoạch thực thi truy vấn thành bài toán tối ưu hóa trên cấu trúc cây toán tử đại số quan hệ. Mục tiêu cụ thể là tìm ra phương án gán thuộc tính phân mảnh tối ưu cho từng nút toán tử, giảm thiểu tối đa chi phí phân mảnh lại ngang và khai thác triệt để năng lực tính toán song song. Phạm vi nghiên cứu được thực hiện trong khuôn khổ luận văn Thạc sĩ ngành Hệ thống thông tin, mã số 60.04 tại Trường Đại học Công nghệ thuộc Đại học Quốc gia Hà Nội, hoàn thành vào năm 2015.

Ý nghĩa thực tiễn của công trình được chứng minh thông qua việc mô hình hóa và áp dụng trực tiếp vào hệ thống quản lý cơ sở dữ liệu phạm nhân tại 3 trại giam trọng điểm thuộc Tổng cục Cảnh sát Thi hành án hình sự và Hỗ trợ tư pháp. Kết quả nghiên cứu chứng minh các giải thuật tô màu cây truy vấn kết hợp tối ưu hóa hai pha giúp cắt giảm từ 30% đến 45% chi phí trao đổi dữ liệu qua mạng diện rộng, đồng thời cải thiện tốc độ đáp ứng của hệ thống lên hơn 40% so với phương thức tuần tự truyền thống.

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 cơ sở dữ liệu phân tán chuẩn mực với kiến trúc 4 tầng bao gồm sơ đồ tổng thể, sơ đồ phân mảnh, sơ đồ định vị và sơ đồ ánh xạ cục bộ. Trong môi trường này, tính trong suốt phân mảnh và trong suốt vị trí là 2 yếu tố then chốt giúp người dùng thực thi các câu lệnh đại số quan hệ mà không cần quan tâm đến vị trí vật lý của dữ liệu tại các nút mạng.

Lý thuyết thứ hai được vận dụng là mô hình tối ưu hóa truy vấn hai pha JOQR, viết tắt của quy trình sắp xếp thứ tự các phép nối và viết lại câu truy vấn. Mô hình này tiến hành tiền xử lý câu lệnh SQL để sinh ra cây truy vấn tiền xử lý AQT và cây toán tử, trong đó các phép toán được phân tách thành cạnh đường ống và cạnh khối. Dựa trên đồ thị cây, bài toán tối ưu hóa được quy về bài toán tô màu đồ thị cây, với mỗi màu đại diện cho một thuộc tính phân mảnh vật lý của quan hệ. Nghiên cứu khai thác sâu 4 khái niệm trọng tâm bao gồm phân mảnh ngang nguyên thủy, cây toán tử nhị phân, chi phí phân mảnh lại ReF và giao thức điều khiển đồng thời phân tán dựa trên khóa chốt Lock Manager nhằm duy trì tính nhất quán giao tác ACID.

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

Nguồn dữ liệu thực nghiệm được thu thập trực tiếp từ cơ sở dữ liệu Phần mềm quản lý phạm nhân tại Bộ Công an tính đến mốc thời gian tháng 10 năm 2015. Cỡ mẫu nghiên cứu bao gồm 4.307 hồ sơ phạm nhân đang chấp hành án, được phân bổ tại 3 cơ sở giam giữ độc lập về mặt địa lý: Trại giam Phú Sơn tại Thái Nguyên quản lý 1.519 hồ sơ, Trại giam Thanh Xuân tại Hà Nội quản lý 1.643 hồ sơ và Trại giam Ninh Khánh tại Ninh Bình quản lý 1.145 hồ sơ. Tập dữ liệu được phân loại chi tiết thành 8 nhóm hành vi phạm tội chính yếu: tội trộm cắp có 1.431 phạm nhân, tội cướp tài sản có 1.140 phạm nhân, tội chống người thi hành công vụ có 900 phạm nhân, tội buôn bán ma túy có 345 phạm nhân, tội gây rối trật tự có 230 phạm nhân, tội hiếp dâm có 146 phạm nhân, tội xâm phạm an ninh có 65 phạm nhân và tội tham nhũng có 50 phạm nhân.

Phương pháp chọn mẫu có chủ đích được áp dụng nhằm phản ánh cấu trúc phân mảnh ngang tự nhiên của các cơ quan quản lý phân tán theo vùng địa lý. Phương pháp phân tích được lựa chọn bao gồm giải tích thuật toán kết hợp mô phỏng thực nghiệm trên môi trường máy ảo tính toán song song. Lý do lựa chọn phương pháp này xuất phát từ yêu cầu phải định lượng chính xác sự tương quan giữa chi phí truyền thông từ xa và chi phí tính toán cục bộ của 3 nhóm giải thuật gộp nhóm: thuật toán trộn tập trung CM, thuật toán trộn phân tán DM và thuật toán phân mảnh lại ReF. Timeline nghiên cứu được thực hiện xuyên suốt trong 12 tháng của năm 2015, từ khâu chuẩn hóa lý thuyết đến kiểm thử thực nghiệm trên các câu truy vấn thống kê phức tạp.

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

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

Quá trình phân tích và thực nghiệm trên các mô hình cây truy vấn đã đem lại 4 phát hiện khoa học quan trọng:

Thứ nhất, việc áp dụng mô hình hai pha JOQR kết hợp cấu trúc cây toán tử phân tầng cho phép phân biệt rõ ràng giữa các cạnh đường ống thực thi song song và các cạnh khối bắt buộc tuần tự. Cơ chế này giúp loại bỏ hơn 30% dung lượng bộ nhớ đệm dành cho việc ghi các bảng trung gian ra đĩa từ, đồng thời tận dụng hiệu quả khả năng tính toán độc lập của từng bộ vi xử lý đơn lẻ.

Thứ hai, trong bài toán thực thi phép gộp nhóm GROUP BY đối với 4.307 bản ghi phạm nhân, thuật toán trộn phân tán DM và thuật toán phân mảnh lại ReF thể hiện sự vượt trội rõ rệt so với thuật toán trộn tập trung CM. Cụ thể, khi dữ liệu được phân chia theo hàm băm STT mod 3 về 3 nút mạng, nhóm nút thứ nhất xử lý 2.571 bản ghi thuộc tội cướp và trộm cắp, nhóm nút thứ hai xử lý 1.310 bản ghi và nhóm nút thứ ba xử lý 426 bản ghi. Thuật toán DM đã triệt tiêu hoàn toàn hiện tượng nút thắt cổ chai tại máy điều phối trung tâm, rút ngắn hơn 52% thời gian xử lý tổng thể khi số lượng bản ghi trả về vượt quá ngưỡng 1.000 dòng.

Thứ ba, các thuật toán tách màu mở rộng có xét đến thuộc tính vật lý của quan hệ như chỉ mục Index Scan và thuộc tính sắp xếp Sort-Merge Join giúp cắt giảm từ 35% đến 50% chi phí phân mảnh lại. Khi một quan hệ đã được sắp xếp sẵn trên thuộc tính nối, chi phí khởi tạo bảng băm giảm xuống 0, tạo điều kiện cho phép nối song song PHJ đạt tốc độ xử lý cực đại.

Thứ tư, việc ứng dụng kỹ thuật nửa nối Semi-Join trên các bảng quan hệ nhân viên và phân công dự án chứng minh khả năng loại bỏ tới 40% các bộ dữ liệu không thỏa mãn vị từ nối trước khi truyền qua mạng diện rộng, giúp tiết kiệm đáng kể băng thông giữa các máy chủ từ xa.

Thảo luận kết quả

Nguyên nhân cốt lõi dẫn đến sự khác biệt về hiệu năng giữa các chiến lược truy vấn bắt nguồn từ mô hình chi phí trong môi trường đa xử lý. Chi phí truyền thông từ xa Remote Communication luôn có độ trễ cao hơn gấp 10 đến 50 lần so với chi phí trao đổi dữ liệu cục bộ Local Communication trên cùng một nút mạng. Khi sử dụng thuật toán tô màu tối ưu, cây truy vấn được cấu trúc sao cho các phép nối quan hệ có cùng màu sẽ được tiến hành ngay tại nút chứa dữ liệu, triệt tiêu nhu cầu chuyển toàn bộ quan hệ qua đường truyền viễn thông.

Dữ liệu thực nghiệm của nghiên cứu có thể được biểu diễn trực quan thông qua bảng phân mảnh ngang và biểu đồ phân bổ tải trọng giữa 3 trạm địa lý. Trong khi mô hình trộn tập trung CM dồn toàn bộ 4.307 bản ghi về một điều phối viên duy nhất gây quá tải bộ nhớ, mô hình phân mảnh lại ReF theo hàm băm số dư chia cho 3 đã phân bổ đồng đều các phép toán tính tổng SUM và đếm COUNT lên cả 3 trạm mạng tại Thái Nguyên, Hà Nội và Ninh Bình.

So sánh với các nghiên cứu trước đây vốn chỉ tập trung vào việc tối ưu hóa số lượng phép nối mà bỏ qua trạng thái vật lý của dữ liệu, đóng góp của luận văn này là tích hợp thành công các thuộc tính vật lý sẵn có vào hàm mục tiêu của giải thuật tô màu. Điều này cho phép bộ tối ưu hóa QEP lựa chọn được kế hoạch thực thi có tổng chi phí thời gian Tpart kết hợp Tasm và độ trễ cực đại đạt mức tối thiểu toàn cục.

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

Dựa trên các kết quả đạt được, luận văn đưa ra 4 đề xuất mang tính hành động cao nhằm nâng cấp hiệu năng các hệ sinh thái phần mềm phân tán:

Một là, tích hợp trực tiếp module giải thuật tô màu cây truy vấn vào bộ tối ưu hóa truy vấn của các hệ quản trị cơ sở dữ liệu chuyên ngành. Chủ thể thực hiện là đội ngũ kỹ sư phát triển phần mềm thuộc Cục Công nghệ thông tin; mục tiêu hướng tới là giảm thiểu ít nhất 40% thời gian phản hồi đối với các truy vấn liên trạm phức tạp; lộ trình triển khai hoàn thành trong 6 tháng đầu năm 2016.

Hai là, chuẩn hóa kiến trúc phân mảnh dữ liệu ngang ngay từ giai đoạn thiết kế hệ thống, kết hợp giữa yếu tố địa lý và các thuộc tính khóa định danh bằng các hàm băm đồng đều. Chủ thể thực hiện là các chuyên viên quản trị hệ thống tại Tổng cục VIII; mục tiêu bảo đảm độ lệch tải giữa các trạm máy chủ không vượt quá 10%; thời gian thực hiện kéo dài 9 tháng.

Ba là, bắt buộc áp dụng kỹ thuật nửa nối Semi-Join và giải thuật gộp nhóm phân tán DM đối với toàn bộ các báo cáo thống kê định kỳ trên hệ thống mạng diện rộng. Chủ thể thực hiện là bộ phận vận hành cơ sở dữ liệu tại các trại giam Phú Sơn, Thanh Xuân và Ninh Khánh; target metric là tiết kiệm 50% lưu lượng băng thông truyền dẫn mạng WAN; thời gian hoàn thành trong quý IV năm 2016.

Bốn là, đầu tư nâng cấp hạ tầng phần cứng theo hướng kiến trúc xử lý song song lớn MPP và hỗ trợ giao thức điều khiển 2 pha 2PC tự động khôi phục khi mất thông điệp. Chủ thể phê duyệt và cấp kinh phí là Ban Lãnh đạo Bộ Công an; mục tiêu bảo đảm hệ thống vận hành liên tục với độ sẵn sàng đạt 99,99% và chịu tải trên 1.000 giao tác đồng thời trong giai đoạn 2016 đến 2020.

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

Luận văn cung cấp nguồn tư liệu học thuật và kỹ thuật giá trị cao cho 4 nhóm đối tượng cụ thể:

Nhóm thứ nhất là các kỹ sư kiến trúc dữ liệu và chuyên gia quản trị cơ sở dữ liệu phân tán. Nhóm này có thể ứng dụng trực tiếp các công thức tính toán chi phí và phương pháp phân mảnh ngang để thiết kế các kho dữ liệu quy mô lớn, tối ưu hóa kế hoạch thực thi QEP trong các doanh nghiệp viễn thông hoặc ngân hàng.

Nhóm thứ hai là các nhà phát triển phần mềm và kỹ sư an ninh mạng trong khối cơ quan nhà nước. Nhóm này có thể tham khảo chi tiết ca sử dụng thực tế về phần mềm quản lý phạm nhân để xây dựng các giải pháp nghiệp vụ quản lý hồ sơ tập trung nhưng vẫn bảo đảm tính độc lập dữ liệu tại các trạm địa phương.

Nhóm thứ ba là các học viên cao học, nghiên cứu sinh chuyên ngành Khoa học máy tính và Hệ thống thông tin. Tài liệu cung cấp cơ sở toán học chặt chẽ về lý thuyết đồ thị ứng dụng trong tối ưu hóa truy vấn, mô hình hai pha JOQR và các biến thể giải thuật tô màu cây đại số quan hệ.

Nhóm thứ tư là giảng viên tại các trường đại học khối kỹ thuật công nghệ. Luận văn là tài liệu tham khảo bài bản phục vụ giảng dạy các học phần chuyên sâu như Cơ sở dữ liệu nâng cao, Tính toán song song và Hệ thống phân tán.

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

Bản chất của bài toán tô màu cây truy vấn trong cơ sở dữ liệu phân tán là gì?
Bài toán tô màu cây truy vấn thực chất là việc gán các thuộc tính phân mảnh vật lý của bảng dữ liệu cho từng nút toán tử trên cây đại số quan hệ. Mục tiêu chính là tìm ra phương án gán màu có tổng chi phí phân mảnh lại thấp nhất, giúp giảm từ 30% đến 45% lượng dữ liệu cần hoán chuyển giữa các trạm mạng khác nhau.

Vì sao thuật toán trộn phân tán lại vượt trội hơn thuật toán trộn tập trung khi xử lý dữ liệu lớn?
Thuật toán trộn tập trung dồn toàn bộ kết quả cục bộ về một trạm điều phối duy nhất, dễ gây ra hiện tượng nghẽn cổ chai khi số lượng bản ghi lớn. Ngược lại, thuật toán trộn phân tán sử dụng hàm băm để phân chia việc tính toán đồng thời trên cả 3 nút mạng, giúp tăng hơn 50% hiệu suất xử lý trên tập 4.307 mẫu tin phạm nhân.

Kỹ thuật nửa nối đóng vai trò gì trong việc tối ưu hóa đường truyền mạng diện rộng?
Kỹ thuật nửa nối chỉ truyền các thuộc tính tham gia vào vị từ nối thay vì chuyển toàn bộ bảng dữ liệu sang nút mạng khác. Phương pháp này giúp loại bỏ tới 40% các dòng dữ liệu dư thừa không thỏa mãn điều kiện nối trước khi gửi qua mạng viễn thông, từ đó tiết kiệm tối đa băng thông truyền tải.

Hệ thống phân tán bảo đảm tính toàn vẹn dữ liệu như thế nào khi xảy ra sự cố mất thông điệp?
Hệ thống sử dụng giao thức khóa chốt kết hợp quy trình ủy thác hai pha với các trạng thái ghi nhật ký như PREPARE, COMMIT và ABORT. Nếu một thành viên bị mất thông điệp xác nhận sau khoảng thời gian hết hạn, điều phối viên sẽ tự động gửi lại lệnh hoặc hủy bỏ giao tác để bảo đảm 100% tính nhất quán.

Phương pháp phân mảnh lại theo phép toán số dư được áp dụng như thế nào trong bài toán thực tế?
Trong bài toán quản lý phạm nhân, thuộc tính số thứ tự của 8 loại tội danh được chia theo hàm băm số dư cho 3 trạm giam giữ. Kết quả chia thành 3 nhóm độc lập với 2.571 bản ghi ở nhóm dư 0, 1.310 bản ghi ở nhóm dư 1 và 426 bản ghi ở nhóm dư 2, giúp các máy chủ xử lý song song hoàn toàn.

Kết luận

  • Luận văn đã hệ thống hóa toàn diện cơ sở lý thuyết về cơ sở dữ liệu phân tán, xử lý truy vấn song song và các giao thức quản lý giao tác phân tán an toàn.
  • Đề xuất và hoàn thiện các thuật toán tô màu tối ưu cho cây truy vấn, tích hợp thành công các thuộc tính vật lý của quan hệ vào bài toán giảm thiểu chi phí phân mảnh lại.
  • So sánh định lượng hiệu quả của các giải thuật gộp nhóm song song, chứng minh tính ưu việt của thuật toán trộn phân tán và phân mảnh lại trên môi trường đa xử lý.
  • Hiện thực hóa thành công mô hình lý thuyết vào bài toán quản lý 4.307 hồ sơ phạm nhân tại 3 trại giam Phú Sơn, Thanh Xuân và Ninh Khánh thuộc Bộ Công an.
  • Mở ra hướng nghiên cứu tiếp theo về việc ứng dụng giải thuật di truyền và trí tuệ nhân tạo trong việc tự động hóa tối ưu hóa cây truy vấn trên các nền tảng đám mây quy mô lớn.

Các tổ chức, doanh nghiệp và nhà nghiên cứu quan tâm đến việc nâng cao hiệu năng xử lý dữ liệu phân tán có thể liên hệ trực tiếp với tác giả hoặc Khoa Công nghệ Thông tin – Trường Đại học Công nghệ, Đại học Quốc gia Hà Nội để tiếp nhận chuyển giao mô hình và mã nguồn thử nghiệm.