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 15 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 Ngày nay, nhiều ứng dụng phân tán, làm việc cộng tác đang được quan tâm phát triển vì nhiều ưu điểm như: chi phí, hiệu năng, khả năng mở rộng, độ tin cậy và tính phân tán cố hữu [5][6][8][9]. Trong đó, kỹ 16 thuật nhân bản dữ liệu là giải pháp hiệu quả để giải quyết bài toán chia sẻ dữ liệu dùng chung, giúp nâng cao khả năng sẵn sàng, độ tin cậy và khả năng chịu lỗi của hệ thống Nhiều bản sao của một đối tượng dữ liệu được nhân bản tới các bộ nhớ cục bộ. Các tiến trình thực hiện trên bản sao hoàn toàn độc lập; không đồng nhất về khả năng xử lý, bộ nhớ, băng thông, tần số vào/ra hệ thống Vì vậy, nhiều tiến trình có thể yêu cầu thực hiện cập nhật (thao tác ghi) đồng thời trên cùng một đối tượng dữ liệu dẫn đến tương tranh cập nhật giữa nhiều. Điều này có thể dẫn đến không nhất quán hoặc không sẵn sàng đáp ứng dữ liệu, thậm chí nghiêm trọng hơn như bế tắc. Do đó, giải quyết bài toán tương tranh cập nhật dữ liệu là một trong những khó khăn, thách thức chủ yếu [10]. Chẳng hạn ta có ví dụ sau: Hai tiến trình T1 và T2 đồng thời yêu cầu thực hiện chuỗi thao tác đọc, ghi hoàn toàn độc lập trên đối tượng dữ liệu X. Mỗi tiến trình có thể cho kết quả khác nhau hoặc xẩy ra tương tranh cập nhật dữ liệu nếu như ứng dụng không có cơ chế quản lý, điều khiển phù hợp. Do đó cần thiết thực hiện đồng bộ hóa các giao dịch nhằm xử lý tương tranh cập nhật dữ liệu giữa các giao dịch đồng thời trên cùng đối tượng dữ liệu nhằm đạt được hai mục đích: đảm bảo tính nhất quán dữ liệu và nhiều nhất các giao dịch đồng thời được thực hiện [13]. Có nhiều nghiên cứu được đề xuất [1][4][5][6][8][9][14] để giải quyết bài toán tương tranh cập nhật dữ liệu. Tuy nhiên vẫn còn những hạn chế sau: Khóa chết: khi các tiến trình đợi đến lượt được cấp phát tài nguyên (dữ liệu). Tuy nhiên tài nguyên luôn luôn bị chiếm giữ bởi một tiến trình khác mà không thể giải phóng. Khôi phục lại: các giao dịch cần được xếp lịch để thực hiện. Nhưng do độ trễ trong truyền thông, sự không thuần nhất của hệ phân tán, cho nên các giao dịch đến có thể không theo trật tự chính xác. Do đó hệ thống cần khôi phục lại nhiều lần để đảm bảo mọi giao dịch đều được xếp lịch một cách chính xác. Trong phạm vi bước đầu của nhiệm vụ nghiên cứu nhằm đề xuất thuật toán cải tiến, tác giả thực hiện phân loại, so sánh, đánh giá các kỹ thuật, các phương pháp tiếp cận và giải thuật. Phần còn lại của bài báo được trình bày như sau: Phần 2 trình bày kỹ thuật và phương pháp tiếp cận; phần 3 thực hiện phân loại, so sánh, đánh giá các thuật toán; kết luận và hướng nghiên cứu, phát triển tiếp theo được chỉ ra trong phần 4. 2. Kỹ thuật và Phương pháp tiếp cận 2.1. Kỹ thuật Hiện nay có hai kỹ thuật chủ yếu đang được sử dụng để xử lý tương tranh cập nhật dữ liệu gồm: sử dụng khóa (Locking) và nhãn thời gian (Timestamp Ordering). 2.1.1 Sử dụng khóa Khóa là cơ chế kiểm soát nhiều cập nhật đồng thời vào một mục dữ liệu tại cùng một thời điểm. Mục dữ liệu có thể bị khóa ở một trong hai chế độ: exclusive(X) – mục dữ liệu có thể được đọc hoặc ghi; shared(S) – mục dữ liệu chỉ có thể được đọc. Các khóa được lưu trữ và quản lý bởi một bảng khóa. Thuật ngữ khóa tương thích để chỉ hai giao dịch có hai khóa mà chúng có thể thực hiện đồng thời trên một mục dữ liệu. Giao dịch chỉ được thực hiện trên mục dữ liệu khi được cấp khóa phù T1: Read(X) T2: Read(X) XX+1 XX+1 Write(X) Write(X) Commit Commit 17 hợp trên mục dữ liệu đó. S X S True False X False False Hình 1: Ma rận ương hích kh a 2.1.2 Nhãn thời gian Mỗi giao dịch khi tham gia vào hệ thống sẽ được gán một nhãn thời gian duy nhất. Đó chính là thời điểm bắt đầu của giao dịch. Giá trị của nhãn thời gian có thể thiết lập bằng phép đếm logic hoặc đồng hồ hệ thống toàn cục và đơn điệu tăng. Do đó, các nhãn thời gian được gán trước khi giao dịch được thực hiện và theo quy tắc: nếu giao dịch Ti có nhãn thời gian là TS(Ti), giao dịch mới Tj có nhãn thời gian TS(Tj) thì TS(Ti)<TS(Tj). Giao dịch được thực hiện theo thứ tự nhãn thời gian. 2.2. Phương pháp tiếp cận Có hai phương pháp tiếp cận với bài toán xử lý tương tranh cập nhật dữ liệu của các giao dịch đồng thời gồm: Optimistic (Lạc quan) và Pessimistic (Bi quan). Sự khác nhau cơ bản là thời điểm quyết định xử lý tương tranh giữa các giao dịch. 2.2.1 Phương pháp tiếp cận Optimistic Phương pháp tiếp cận Optimistic cho rằng có ít giao dịch xảy ra tương tranh. Do đó, mọi giao dịch đều được xử lý, nhưng trì hoãn yêu cầu xác thực cho đến trước giai đoạn thực hiện thao tác ghi trên mục dữ liệu. Vì vậy, giao dịch có thể bị hủy bỏ khi hệ thống thực hiện đồng bộ hóa tại thời điểm cuối cùng [2][3]. Sơ đồ minh họa: Read Compute Validate Write 2.2.2 Phương pháp tiếp cận Pessimistic Phương pháp tiếp cận Pessimistic cho rằng có nhiều giao dịch xảy ra tương tranh. Vì vậy xử lý tương tranh giữa các giao dịch cần được kiểm tra và thực hiện trước tiên [15]. Sơ đồ minh họa: Validate Read Compute Write 3. Phân loại, so sánh, đánh giá các huậ oán xử lý ương ranh cập nhậ dữ liệu Các thuật toán xử lý tương tranh có thể được phân loại dựa trên kỹ thuật hoặc phương pháp tiếp cận. Trong bài viết này, tác giả thực hiện phân loại dựa trên phương pháp tiếp cận. 3.1. Thuật toán sử dụng phương pháp tiếp cận Optimistic Thuật toán được đề xuất bởi [1] sử dụng khóa và có nguyên lý hết sức đơn giản. Khi giao dịch thực hiện cập nhật một mục dữ liệu thì trước hết phải yêu cầu khóa cho mục dữ liệu đó từ bộ quản lý khóa. Nếu mục dữ liệu này đã được khóa bởi khóa không tương thích (xem bảng tương thích khóa ở trên) với khóa được yêu cầu thì giao dịch phải chờ và được đưa vào hàng đợi để thực hiện. Ngược lại giao dịch sẽ được cấp khóa để thao tác với mục dữ liệu. Khi giao dịch hoàn thành, khóa được giải phóng và giao dịch trong hàng đợi sẽ được thực hiện tiếp theo. Thao tác chỉ có thể được thực hiện khi có sự tương thích về khóa với xác suất chỉ là 25%. Đặc biệt là các thao tác ghi dữ liệu. Do đó, nếu ứng dụng có nhiều giao dịch yêu cầu ghi dữ liệu thì thuật toán sẽ không hiệu quả. Thuật toán chỉ phù hợp khi thao tác đọc dữ liệu là chủ yếu. Ngoài ra thuật toán có thể xảy ra trường hợp khóa chết. Tức là một số giao dịch chờ đợi nhau vô thời hạn và cần có sự can thiệp từ bên ngoài. Thuật toán được đề xuất bởi [4] dựa trên nhãn thời gian để kiểm tra các giao dịch đến theo một thứ tự chính xác, mỗi 18 mục dữ liệu sẽ được gán nhãn thời gian ghi (wts) - là nhãn thời gian lớn nhất của thao tác ghi sau khi thực hiện thành công trên mục dữ liệu X; nhãn thời gian đọc (rts) - là nhãn thời gian lớn nhất của thao tác đọc sau khi thực hiện thành công trên mục dữ liệu X.  Yêu cầu đọc mục dữ liệu X: Ri(X) Nếu TS(Ti) < wts(X): hủy bỏ giao dịch và quay trở lại để gán nhãn thời gian mới cho các giao dịch Ti. Nếu TS(Ti) ≥ wts(X): thực hiện giao dịch và cập nhật lại nhãn thời gian đọc của mục dữ liệu X là rts(X).  Yêu cầu ghi mục dữ liệu X: Wi(X) Nếu TS(Ti) >= wts(X) và TS(Ti) >= rts(X): thực hiện thao tác. Nếu rts(X) < TS(Ti) < wts(X): không thực hiện gì. Nếu TS(Ti) < rts(X): hủy bỏ giao dịch, quay trở lại để gán nhãn thời gian mới cho các giao dịch Ti. Bảng 1 minh họa các giao dịch T1, T2, T3 có nhãn thời gian là 10, 20, 30 thao tác trên dữ liệu X, Y. Thuật toán xếp lịch tuần tự cho các giao dịch để giải quyết yêu cầu tương tranh và tránh được khóa chết. Tuy nhiên hệ thống có thể phải thực hiện khôi phục lại nhiều lần để thực hiện gán nhãn thời gian mới cho các giao dịch. Bảng 1: Minh họa sử dụng nhãn thời gian Ti T1 T2 T3 X Y 10 20 30 rts=0 wts=0 rts=0 wts=0 1 R(X) rts=20 2 R(X) rts=30 3 W(Y) wts=20 4 W(A) 30 5 R(Y) ? Ti bị hủy bỏ và phải quay lại để gán nhãn thời gian mới cho các giao dịch Đánh giá: Mọi thao tác đều được xử lý và chỉ thực hiện đồng bộ khi có yêu cầu ghi nên có thể dẫn sự hủy bỏ các giao dịch do không thỏa mãn. Ứng dụng có thể phải khôi phục lại nhiều lần (chẳng hạn như quay ngược lại để gán nhãn thời gian mới cho các giao dịch...). Do đó, phương pháp tiếp cận Optimistic chỉ đạt hiệu quả cao khi có ít tương trang xảy ra giữa các giao dịch. 3.2. Thuật toán sử dụng phương pháp tiếp cận Pessimistic Hiệu suất của thuật toán dựa trên khóa được trình bày ở trên không cao (25%), không phù hợp với các ứng dụng có nhiều yêu cầu ghi dữ liệu và đặc biệt là có thể dẫn đến sự chiếm dụng khóa không cần thiết, khóa chết. Thuật toán được đề xuất bởi [14] sử dụng khóa 2 pha (2PL) với từng thao tác trong mỗi giao dịch nhằm nâng cao hiệu quả. Hình 2: Sơ đồ kh a 2 pha Pha hứ nhấ (pha ăng rường): giành được khóa. Pha hứ hai (pha hu hẹp): giải phóng khóa. Lock point: thời điểm chuyển từ pha thứ nhất sang pha thứ hai. Thuật toán cho phép các giao dịch có thể thực hiện xen kẽ nhằm nâng cao hiệu suất của việc sử dụng khóa. Tuy nhiên thuật toán cũng có thể dẫn đến trường hợp 19 các giao dịch bị hủy bỏ theo hiệu ứng chuỗi (cuộn nhau). Điều này xảy ra khi một giao dịch bị hủy bỏ sau khi chúng đã giải phóng khóa, dẫn đến các giao dịch khác đã cập nhật tới các mục dữ liệu không bị khóa cũng bị hủy bỏ theo. Để khắc phục trường hợp này thuật toán khóa hai pha nghiêm ngặt cho phép các giao dịch được chiếm giữ các khóa cho đến khi giao dịch kết thúc. Trong ứng dụng, thuật toán có thể triển khai theo các phương thức sau: a. Sử dụng bộ quản lý khóa trung tâm Chỉ duy nhất một site trung tâm chịu trách nhiệm quản lý khóa. Mọi giao dịch có yêu cầu khóa phải liên lạc với nó để được cấp khóa. Phương pháp này có ưu điểm là dễ dàng triển khai, tuy nhiên nhược điểm là dễ xảy ra tắc nghẽn và độ tin cậy thấp khi có nhiều yêu cầu tới site trung tâm hay site trung tâm gặp lỗi. b. Sử dụng bản sao chính và bộ quản lý khóa phân tán Một bản được lựa chọn là bản sao chính (primary copy) thông qua thuật toán Voting [7]. Các bản sao khác gọi là bản phụ thuộc. Chỉ khi bản sao chính thực hiện ghi thì mới sử dụng khóa và thực hiện lan truyền tới các bản sao khác. Nhiều bộ quản lý khóa được sử dụng và đặt tại các vị trí khác nhau. Mỗi bộ quản lý khóa chịu trách nhiệm một tập các mục dữ liệu. Thuật toán giảm chí phí truyền thông và hiệu suất tốt hơn so với thuật toán sử dụng bộ quản lý khóa trung tâm. Tuy nhiên xử lý các trường hợp khóa chết sẽ rất khó khăn. c. Sử dụng bộ quản lý khóa phân tán Mọi site đều có bộ quản lý khóa chịu trách nhiệm cấp khóa cho site đó. Nếu site không có yêu cầu cập nhật dữ liệu thì thuật toán thực hiện tương tự như với sử dụng bản sao chính và bộ quản lý khóa phân tán. Ngược lại, giao thức điều khiển nhân bản Read - one - Write - All (ROWA) [7] được thực hiện. Đó là, mọi bản sao của mục dữ liệu phải được khóa trước khi thực hiện cập nhật; thao tác đọc được thực hiện tại bất kỳ bản sao nào nếu dành được khóa của bản sao đó. Thuật toán được đề xuất bởi [11] sử dụng nhiều phiên bản của mục dữ liệu. Do đó, các thao tác ghi không làm thay đổi dữ liệu trên mục dữ liệu mà sẽ tạo ra một phiên bản mới. Thuật toán thực hiện gán nhãn thời gian cho các phiên bản mới được tạo ra. Chẳng hạn, mục dữ liệu X có thể có nhiều phiên bản X1, X2,Xn.  Yêu cầu đọc mục dữ liệu X Ri(X) Thao tác luôn thực hiện được với giá trị trả về là phiên bản Xv thỏa mãn: wts(Xv) là giá trị lớn nhất và nhỏ hơn TS(Ti).  Yêu cầu ghi mục dữ liệu X Wi(X) Thao tác ghi sinh ra một phiên bản mới của mục dữ liệu X gọi là Xv có TS(Xv) = TS(Ti) khi trong lịch chưa có yêu cầu đọc Rj(Xr) trên phiên bản Xr mà TS(Ti) < rts(Xr), ngược lại thao tác ghi bị từ chối. Thuật toán dựa trên nhãn thời gian được đề xuất bởi [12] thực hiện sinh lịch tuần tự các giao dịch theo nhãn thời gian. Tất cả các thao tác của mỗi giao dịch đều được thực hiện liên tiếp nhau. Trong lịch tuần tự mỗi giao dịch thực hiện toàn bộ các thao tác của nó và không có tương tranh. Do đó các giao dịch không phải đợi nhưng có thể bị từ chối thực hiện do lịch tuần tự xuất hiện tình trạng khóa chết. Khi đó chi phí là số lần cần thiết phải khôi phục lại các giao dịch. Để khắc phục tình trạng phải khôi phục lại nhiều lần, thuật toán cải tiến yêu cầu các thao tác của mỗi giao dịch phải được lưu trữ trong bộ đệm cho đến khi 20 hoàn thành việc sắp xếp theo đúng thứ tự nhãn thời gian. Như vậy sẽ không có các giao dịch có nhãn thời gian nhỏ hơn đến nữa. Do đó không xẩy ra trường hợp bị từ chối hay hệ thống phải khôi phục lại lại. Tuy nhiên ứng dụng có thể xẩy ra trường hợp khóa chết, do giao dịch có nhãn thời gian nhỏ không bao giờ đến được bộ đệm. Đánh giá: Trong trường hợp có nhiều giao dịch xẩy ra tương tranh thì phương pháp tiếp cận Pessimistic có hiệu quả cao hơn so với phương pháp tiếp cận Optimistic. Chẳng hạn chi phí cần thiết để khôi phục lại hay trường hợp khóa chết. Phương pháp này nếu sử dụng nhãn thời gian thì thứ tự sắp xếp của các giao dịch được quyết định tĩnh, nếu sử dụng khóa thì thứ tự được quyết định động. Thuật toán sử dụng nhãn thời gian sẽ có hiệu quả hơn nếu ứng dụng có thao tác đọc là chủ yếu. Các giao dịch bị hủy bỏ sẽ được quyết định ngay lập tức. Thuật toán sử dụng khóa sẽ có hiệu quả hơn khi ứng dụng có thao tác ghi là chủ yếu. Tuy nhiên có thể dẫn đến sự chiếm dụng khóa không hiệu quả, yêu cầu các giao dịch khác phải đợi hoặc thậm chí dẫn đến khóa chết. 4. luận hướng nghi n cứu Các thuật toán dựa trên kỹ thuật khóa và nhãn thời gian vẫn tồn tại những vấn đề về khóa chết hay đòi hỏi khôi phục lại nhiều lần. Do đó làm giảm độ tin cậy, hiệu năng của thuật toán. Bên cạnh đó thì hai phương pháp tiếp cận Optimistic và Pessimistic cũng có những ưu và nhược điểm riêng và người xây dựng ứng dụng cần đánh giá yêu cầu, đòi hỏi của hệ thống, bài toán đặt ra để từ đó lựa chọn phương pháp tiếp cận hiệu quả nhất. Nghiên cứu đánh giá và so sánh các thuật toán xử lý tương tranh cập nhật dữ liệu là bước đầu tiên hết sức quan trọng và hữu ích nhằm tìm hiểu những nguyên lý, nền tảng tri thức và khai mở vấn đề. Thời gian tới, chúng tôi sẽ tiếp tục nghiên cứu trong lĩnh vực này nhằm đề xuất thuật toán hoặc thực hiện những cải tiến xử lý tương tranh cập nhật dữ liệu trong môi trường phân tán; thực hiện mô phỏng, chứng minh tính tính đúng đắn; so sánh, đánh giá toàn diện phương pháp mới. ÀI LIỆU HAM HẢO 1. Atul, et al. Adya (1995), “Efficient optimistic concurrency control using loosely synchronized clocks”, ACM SIGMOD Record, pp. 23-34, 24.2. 2. Christoph, Rajesh Bordawekar, and Calin Cascaval von Praun (2008), “Modeling optimistic concurrency using quantitative dependence analysis”, Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, ACM. 3. Dag, et al Nyström (2004), “Pessimistic concurrency control and versioning to support database pointers in real-time databases”, Real- Time Systems, 2004, ECRTS 2004, Proceedings, 16th Euromicro Conference on, IEEE. 4. Ho-Jin, and Byeong-Soo Jeong. Choi (2006), “A timestamp-based optimistic concurrency control for handling mobile transactions”, Computational Science and Its Applications- ICCSA 2006, pp. 796-805. 5. Jiming, et al Chen (2010), “Distributed collaborative control for industrial automation with wireless sensor and actuator networks”, Industrial Electronics, IEEE Transactions, pp. 4219-4230, 57.12. 6. Jun, et al Wang (2006), “Distributed collaborative filtering for peer-to-peer file sharing systems”, Proceedings of the 2006 ACM symposium on Applied computing, ACM. 7. Matthias, et al Wiesmann (2000), “Database replication techniques: A three parameter classification”, in Reliable Distributed Systems, 2000, SRDS-2000, Proceedings The 19th IEEE Symposium on. IEEE. 21 8. Michael E, et al Locasto (2004), Collaborative distributed intrusion detection. 9. Peng, et al. Han (2004), “A scalable P2P recommender system based on distributed collaborative filtering”, Expert systems with applications, pp. 203-210, 27.2. 10. Philip A., and Nathan Goodman Bernstein (1981), Concurrency control in distributed database systems, CSUR. 11. Philip A., and Nathan Goodman Bernstein (1983), “Multiversion concurrency control- theory and algorithms”, ACM Transactions on Database Systems (TODS), pp. 465-483, 8.4. 12. Quazi Ehsanul Kabir, and Hidenori Nakazato Mamun (2005), “Timestamp based optimistic concurrency control”, in TENCON 2005, 2005 IEEE Region 10 Conference. 13. R., Berard, P., and Decitre, P Balter (1982), “Why control of concurrency level in distributed systems is more important than deadlock management”, in Proc. ACM SIGACT-SIGOPS 1st Symp, on the Principles of Distributed Computing, pp. pages 183–193. 14. Samuel Kounev (2001), “Eliminating ECperf persistence bottlenecks when using RDBMS with pessimistic concurrency control”, Technical Report, dvs1. informatik. tu-darmstadt. de/~ skounev, Technical University of Darmstadt, Germany. 15. Timothy R. Learmont (2001), “Fine-grained consistency mechanism for optimistic concurrency control using lock groups”, U.S. Patent, No. 6,240,413, 29 May. Ngày nhận bài: 31/7/2015 Biên tập xong: 15/12/2015 Duyệt