Khảo sát, đánh giá một số thuật toán xử lý tương tranh cập nhật dữ liệu trong các hệ phân tán

Đóng góp của tác giả trong bài viết là thực hiện nghiên cứu, đánh giá và so sánh các thuật toán đã được sử dụng, từ đó làm cơ sở tiếp tục nghiên cứu nhằm đề xuất cải tiến hoặc thuật toán mới.
Nội dung trích xuất từ tài liệu:
Khảo sát, đánh giá một số thuật toán xử lý tương tranh cập nhật dữ liệu trong các hệ phân tán TAÏP CHÍ KHOA HOÏC ÑAÏI HOÏC SAØI GOØN Soá 10 (35) - Thaùng 12/2015 c p dữ ệ c c ệp â Algorithms for concurrent data processing in distributed systems PGS.TS. Lê Văn Sơn Trường Đại học Đà Nẵng ThS. Nguyễn Hồng Minh Trường Đại học An ninh nhân dân Assoc.Prof.,Ph.D. Le Van Son The University of Da Nang M.Sc. Nguyen Hong Minh University of People Security Trong môi trường phân tán, khi nhiều giao dịch thực hiện cập nhật trên một mục dữ liệu tại cùng một thời điểm, thì ứng dụng cần xử lý tương tranh cập nhật trên mục dữ liệu đó nhằm đảm bảo nhất quán dữ liệu (tính chính xác của dữ liệu), đồng thời nhiều nhất các giao dịch được thực hiện. Đã có nhiều thuật toán được đề xuất để giải quyết yêu cầu trên. Tuy nhiên những thuật toán đó vẫn còn bộc lộ những hạn chế như tình trạng khóa chết (deadlock) hay phải khôi phục lại (restart) nhiều lần làm ảnh hưởng đến hiệu suất cũng như hoạt động ổn định của ứng dụng. Do đó, yêu cầu cải tiến hoặc đề xuất thuật toán mới nhằm đạt được hiệu quả tốt hơn là hết sức cần thiết. Đóng góp của tác giả trong bài viết là thực hiện nghiên cứu, đánh giá và so sánh các thuật toán đã được sử dụng, từ đó làm cơ sở tiếp tục nghiên cứu nhằm đề xuất cải tiến hoặc thuật toán mới. Từ khóa: thuật toán, điều khiển tương tranh, nhân bản, hệ phân tán, nhất quán… Abstract In distributed environments, when many transactions are performed on a data item at the same time, the application needs to handle access concurrently on this data item for both ensuring data consistency (the accuracy of the data) and executing maximum transactions. There have been many proposed algorithms to meet this requirement. However, they still reveal several limitations such as deadlock state or multiple restarts of the application, which affect its stability and performance. Therefore, it is essential of the requirement for improving or proposing a new algorithm in order to get better efficiency. Therefore, it is essential that improvements on the old algorithms or proposal of new ones be made. The authors’ contributions on this paper is to conduct study, evaluation and comparison of used algorithms, which will then serve as a basis for further study to suggest improvements or new algorithms. Keywords: algorithm, concurrency control, replication, distributed system, consistency… 1. Giới hiệu triển vì nhiều ưu điểm như: chi phí, hiệu Ngày nay, nhiều ứng dụng phân tán, năng, khả năng mở rộng, độ tin cậy và tính làm việc cộng tác đang được quan tâm phát phân tán cố hữu [5][6][8][9]. Trong đó, kỹ 15 thuật nhân bản dữ liệu là giải pháp hiệu lượt được cấp phát tài nguyên (dữ liệu). quả để giải quyết bài toán chia sẻ dữ liệu Tuy nhiên tài nguyên luôn luôn bị chiếm dùng chung, giúp nâng cao khả năng sẵn giữ bởi một tiến trình khác mà không thể sàng, độ tin cậy và khả năng chịu lỗi của hệ giải phóng. thống… Nhiều bản sao của một đối tượng Khôi phục lại: các giao dịch cần được dữ liệu được nhân bản tới các bộ nhớ cục xếp lịch để thực hiện. Nhưng do độ trễ bộ. Các tiến trình thực hiện trên bản sao trong truyền thông, sự không thuần nhất hoàn toàn độc lập; không đồng nhất về khả của hệ phân tán, cho nên các giao dịch đến năng xử lý, bộ nhớ, băng thông, tần số có thể không theo trật tự chính xác. Do đó vào/ra hệ thống… Vì vậy, nhiều tiến trình hệ thống cần khôi phục lại nhiều lần để có thể yêu cầu thực hiện cập nhật (thao tác đảm bảo mọi giao dịch đều được xếp lịch ghi) đồng thời trên cùng một đối tượng dữ một cách chính xác. liệu dẫn đến tương tranh cập nhật giữa Trong phạm vi bước đầu của nhiệm vụ nhiều. Điều này có thể dẫn đến không nhất nghiên cứu nhằm đề xuất thuật toán cải quán hoặc không sẵn sàng đáp ứng dữ liệu, tiến, tác giả thực hiện phân loại, so sánh, thậm chí nghiêm trọng hơn như bế tắc. Do đánh giá các kỹ thuật, các phương pháp đó, giải quyết bài toán tương tranh cập nhật tiếp cận và giải thuật. dữ liệu là một trong những khó khăn, thách Phần còn lại của bài báo được trình thức chủ yếu [10]. bày như sau: Phần 2 trình bày kỹ thuật và Chẳng hạn ta có ví dụ sau: phương pháp tiếp cận; phần 3 thực hiện T1: Read(X) T2: Read(X) phân loại, so sánh, đánh giá các thuật toán; XX+1 XX+1 kết luận và hướng nghiên cứu, phát triển Write(X) Write(X) tiếp theo được chỉ ra trong phần 4. Commit Commit 2. Kỹ thuật và Phương pháp tiếp cận Hai tiến trình T1 và T2 đồng thời yêu 2.1. Kỹ thuật cầu thực hiện chuỗi thao tác đọc, ghi hoàn Hiện nay có hai kỹ thuật chủ yếu đang toàn độc lập trên đối tượng dữ liệu X. Mỗi được sử dụng để xử lý tương tranh cập nhật tiến trình có thể cho kết quả khác nhau dữ liệu gồm: sử dụng khóa (Locking) và hoặc xẩy ra tương tranh cập nhật dữ liệu nhãn thời gian (Timestamp Ordering). nếu như ứng dụng không có cơ chế quản 2.1.1 Sử dụng khóa lý, điều khiển phù hợp. Do đó cần thiết ...