intTypePromotion=1

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

Chia sẻ: ViNobinu2711 ViNobinu2711 | Ngày: | Loại File: PDF | Số trang:7

0
13
lượt xem
0
download

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

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đó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.

Chủ đề:
Lưu

Nội dung Text: 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<br /> <br /> <br /> <br /> <br /> c p dữ ệ c c ệp â<br /> Algorithms for concurrent data processing in distributed systems<br /> <br /> PGS.TS. Lê Văn Sơn<br /> Trường Đại học Đà Nẵng<br /> ThS. Nguyễn Hồng Minh<br /> Trường Đại học An ninh nhân dân<br /> <br /> Assoc.Prof.,Ph.D. Le Van Son<br /> The University of Da Nang<br /> M.Sc. Nguyen Hong Minh<br /> University of People Security<br /> <br /> <br /> <br /> 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<br /> 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ữ<br /> 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<br /> 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<br /> 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<br /> 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<br /> 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<br /> 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<br /> nhằm đề xuất cải tiến hoặc thuật toán mới.<br /> 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…<br /> Abstract<br /> In distributed environments, when many transactions are performed on a data item at the same time, the<br /> application needs to handle access concurrently on this data item for both ensuring data consistency (the<br /> accuracy of the data) and executing maximum transactions. There have been many proposed algorithms<br /> to meet this requirement. However, they still reveal several limitations such as deadlock state or<br /> multiple restarts of the application, which affect its stability and performance. Therefore, it is essential<br /> of the requirement for improving or proposing a new algorithm in order to get better efficiency.<br /> Therefore, it is essential that improvements on the old algorithms or proposal of new ones be made. The<br /> authors’ contributions on this paper is to conduct study, evaluation and comparison of used algorithms,<br /> which will then serve as a basis for further study to suggest improvements or new algorithms.<br /> Keywords: algorithm, concurrency control, replication, distributed system, consistency…<br /> <br /> <br /> <br /> 1. Giới hiệu triển vì nhiều ưu điểm như: chi phí, hiệu<br /> 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<br /> 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ỹ<br /> <br /> 15<br /> 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).<br /> 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<br /> 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ể<br /> sàng, độ tin cậy và khả năng chịu lỗi của hệ giải phóng.<br /> 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<br /> 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ễ<br /> 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<br /> 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<br /> 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 đó<br /> 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 để<br /> 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<br /> ghi) đồng thời trên cùng một đối tượng dữ một cách chính xác.<br /> 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ụ<br /> 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<br /> 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,<br /> 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<br /> đó, giải quyết bài toán tương tranh cập nhật tiếp cận và giải thuật.<br /> 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<br /> thức chủ yếu [10]. bày như sau: Phần 2 trình bày kỹ thuật và<br /> Chẳng hạn ta có ví dụ sau: phương pháp tiếp cận; phần 3 thực hiện<br /> T1: Read(X) T2: Read(X) phân loại, so sánh, đánh giá các thuật toán;<br /> XX+1 XX+1 kết luận và hướng nghiên cứu, phát triển<br /> Write(X) Write(X) tiếp theo được chỉ ra trong phần 4.<br /> Commit Commit<br /> 2. Kỹ thuật và Phương pháp tiếp cận<br /> Hai tiến trình T1 và T2 đồng thời yêu 2.1. Kỹ thuật<br /> 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<br /> 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<br /> 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à<br /> hoặc xẩy ra tương tranh cập nhật dữ liệu nhãn thời gian (Timestamp Ordering).<br /> nếu như ứng dụng không có cơ chế quản 2.1.1 Sử dụng khóa<br /> lý, điều khiển phù hợp. Do đó cần thiết Khóa là cơ chế kiểm soát nhiều cập<br /> thực hiện đồng bộ hóa các giao dịch nhằm nhật đồng thời vào một mục dữ liệu tại<br /> xử lý tương tranh cập nhật dữ liệu giữa các cùng một thời điểm. Mục dữ liệu có thể bị<br /> giao dịch đồng thời trên cùng đối tượng dữ khóa ở một trong hai chế độ: exclusive(X)<br /> liệu nhằm đạt được hai mục đích: đảm bảo – mục dữ liệu có thể được đọc hoặc ghi;<br /> tính nhất quán dữ liệu và nhiều nhất các shared(S) – mục dữ liệu chỉ có thể được<br /> giao dịch đồng thời được thực hiện [13]. đọc. Các khóa được lưu trữ và quản lý bởi<br /> Có nhiều nghiên cứu được đề xuất một bảng khóa. Thuật ngữ khóa tương<br /> [1][4][5][6][8][9][14] để giải quyết bài thích để chỉ hai giao dịch có hai khóa mà<br /> toán tương tranh cập nhật dữ liệu. Tuy chúng có thể thực hiện đồng thời trên một<br /> nhiên vẫn còn những hạn chế sau: mục dữ liệu. Giao dịch chỉ được thực hiện<br /> Khóa chết: khi các tiến trình đợi đến trên mục dữ liệu khi được cấp khóa phù<br /> <br /> 16<br /> hợp trên mục dữ liệu đó. vậy xử lý tương tranh giữa các giao dịch cần<br /> S X được kiểm tra và thực hiện trước tiên [15].<br /> Sơ đồ minh họa:<br /> S True False<br /> X False False Validate Read Compute Write<br /> 3. Phân loại, so sánh, đánh giá các<br /> Hình 1: Ma rận ương hích kh a huậ oán xử lý ương ranh cập nhậ<br /> 2.1.2 Nhãn thời gian dữ liệu<br /> Mỗi giao dịch khi tham gia vào hệ Các thuật toán xử lý tương tranh có thể<br /> thống sẽ được gán một nhãn thời gian duy được phân loại dựa trên kỹ thuật hoặc<br /> nhất. Đó chính là thời điểm bắt đầu của phương pháp tiếp cận. Trong bài viết này,<br /> giao dịch. Giá trị của nhãn thời gian có thể tác giả thực hiện phân loại dựa trên phương<br /> thiết lập bằng phép đếm logic hoặc đồng pháp tiếp cận.<br /> hồ hệ thống toàn cục và đơn điệu tăng. Do 3.1. Thuật toán sử dụng phương pháp<br /> đó, các nhãn thời gian được gán trước khi tiếp cận Optimistic<br /> giao dịch được thực hiện và theo quy tắc: Thuật toán được đề xuất bởi [1] sử<br /> nếu giao dịch Ti có nhãn thời gian là dụng khóa và có nguyên lý hết sức đơn<br /> TS(Ti), giao dịch mới Tj có nhãn thời gian giản. Khi giao dịch thực hiện cập nhật một<br /> TS(Tj) thì TS(Ti)= wts(X) và TS(Ti) >= dẫn đến sự chiếm dụng khóa không cần<br /> rts(X): thực hiện thao tác. thiết, khóa chết.<br /> Nếu rts(X) < TS(Ti) < wts(X): không Thuật toán được đề xuất bởi [14] sử<br /> thực hiện gì. dụng khóa 2 pha (2PL) với từng thao tác<br /> Nếu TS(Ti) < rts(X): hủy bỏ giao dịch, trong mỗi giao dịch nhằm nâng cao hiệu<br /> quay trở lại để gán nhãn thời gian mới cho quả.<br /> các giao dịch Ti.<br /> Bảng 1 minh họa các giao dịch T1, T2,<br /> T3 có nhãn thời gian là 10, 20, 30 thao tác<br /> trên dữ liệu X, Y.<br /> Thuật toán xếp lịch tuần tự cho các<br /> giao dịch để giải quyết yêu cầu tương tranh<br /> và tránh được khóa chết. Tuy nhiên hệ<br /> thống có thể phải thực hiện khôi phục lại<br /> nhiều lần để thực hiện gán nhãn thời gian<br /> mới cho các giao dịch. Hình 2: Sơ đồ kh a 2 pha<br /> Bảng 1: Minh họa sử dụng nhãn thời gian<br /> Ti T1 T2 T3 X Y Pha hứ nhấ (pha ăng rường):<br /> rts=0 rts=0 giành được khóa.<br /> 10 20 30 Pha hứ hai (pha hu hẹp): giải<br /> wts=0 wts=0<br /> 1 R(X) rts=20 phóng khóa.<br /> 2 R(X) rts=30 Lock point: thời điểm chuyển từ pha<br /> 3 W(Y) wts=20 thứ nhất sang pha thứ hai.<br /> 4 W(A) 30 Thuật toán cho phép các giao dịch có<br /> 5 R(Y) ? Ti bị hủy bỏ và phải quay lại để thể thực hiện xen kẽ nhằm nâng cao hiệu<br /> gán nhãn thời gian mới cho các suất của việc sử dụng khóa. Tuy nhiên<br /> giao dịch thuật toán cũng có thể dẫn đến trường hợp<br /> <br /> 18<br /> các giao dịch bị hủy bỏ theo hiệu ứng Read - one - Write - All (ROWA) [7] được<br /> chuỗi (cuộn nhau). Điều này xảy ra khi một thực hiện. Đó là, mọi bản sao của mục dữ<br /> giao dịch bị hủy bỏ sau khi chúng đã giải liệu phải được khóa trước khi thực hiện cập<br /> phóng khóa, dẫn đến các giao dịch khác đã nhật; thao tác đọc được thực hiện tại bất kỳ<br /> cập nhật tới các mục dữ liệu không bị khóa bản sao nào nếu dành được khóa của bản<br /> cũng bị hủy bỏ theo. Để khắc phục trường sao đó.<br /> hợp này thuật toán khóa hai pha nghiêm Thuật toán được đề xuất bởi [11] sử<br /> ngặt cho phép các giao dịch được chiếm dụng nhiều phiên bản của mục dữ liệu. Do<br /> giữ các khóa cho đến khi giao dịch kết đó, các thao tác ghi không làm thay đổi dữ<br /> thúc. Trong ứng dụng, thuật toán có thể liệu trên mục dữ liệu mà sẽ tạo ra một<br /> triển khai theo các phương thức sau: phiên bản mới. Thuật toán thực hiện gán<br /> a. Sử dụng bộ quản lý khóa trung tâm nhãn thời gian cho các phiên bản mới được<br /> Chỉ duy nhất một site trung tâm chịu tạo ra. Chẳng hạn, mục dữ liệu X có thể có<br /> trách nhiệm quản lý khóa. Mọi giao dịch có nhiều phiên bản X1, X2,…Xn.<br /> yêu cầu khóa phải liên lạc với nó để được  Yêu cầu đọc mục dữ liệu X Ri(X)<br /> cấp khóa. Phương pháp này có ưu điểm là Thao tác luôn thực hiện được với giá<br /> dễ dàng triển khai, tuy nhiên nhược điểm là trị trả về là phiên bản Xv thỏa mãn:<br /> dễ xảy ra tắc nghẽn và độ tin cậy thấp khi wts(Xv) là giá trị lớn nhất và nhỏ hơn<br /> có nhiều yêu cầu tới site trung tâm hay site TS(Ti).<br /> trung tâm gặp lỗi.  Yêu cầu ghi mục dữ liệu X Wi(X)<br /> b. Sử dụng bản sao chính và bộ quản Thao tác ghi sinh ra một phiên bản<br /> lý khóa phân tán mới của mục dữ liệu X gọi là Xv có<br /> Một bản được lựa chọn là bản sao TS(Xv) = TS(Ti) khi trong lịch chưa có<br /> chính (primary copy) thông qua thuật toán yêu cầu đọc Rj(Xr) trên phiên bản Xr mà<br /> Voting [7]. Các bản sao khác gọi là bản TS(Ti) < rts(Xr), ngược lại thao tác ghi bị<br /> phụ thuộc. Chỉ khi bản sao chính thực hiện từ chối.<br /> ghi thì mới sử dụng khóa và thực hiện lan Thuật toán dựa trên nhãn thời gian<br /> truyền tới các bản sao khác. Nhiều bộ quản được đề xuất bởi [12] thực hiện sinh lịch<br /> lý khóa được sử dụng và đặt tại các vị trí tuần tự các giao dịch theo nhãn thời gian.<br /> khác nhau. Mỗi bộ quản lý khóa chịu trách Tất cả các thao tác của mỗi giao dịch đều<br /> nhiệm một tập các mục dữ liệu. Thuật toán được thực hiện liên tiếp nhau. Trong lịch<br /> giảm chí phí truyền thông và hiệu suất tốt tuần tự mỗi giao dịch thực hiện toàn bộ các<br /> hơn so với thuật toán sử dụng bộ quản lý thao tác của nó và không có tương tranh.<br /> khóa trung tâm. Tuy nhiên xử lý các trường Do đó các giao dịch không phải đợi nhưng<br /> hợp khóa chết sẽ rất khó khăn. có thể bị từ chối thực hiện do lịch tuần tự<br /> c. Sử dụng bộ quản lý khóa phân tán xuất hiện tình trạng khóa chết. Khi đó chi<br /> Mọi site đều có bộ quản lý khóa chịu phí là số lần cần thiết phải khôi phục lại<br /> trách nhiệm cấp khóa cho site đó. Nếu site các giao dịch.<br /> không có yêu cầu cập nhật dữ liệu thì thuật Để khắc phục tình trạng phải khôi<br /> toán thực hiện tương tự như với sử dụng phục lại nhiều lần, thuật toán cải tiến yêu<br /> bản sao chính và bộ quản lý khóa phân tán. cầu các thao tác của mỗi giao dịch phải<br /> Ngược lại, giao thức điều khiển nhân bản được lưu trữ trong bộ đệm cho đến khi<br /> <br /> 19<br /> hoàn thành việc sắp xếp theo đúng thứ tự hữu ích nhằm tìm hiểu những nguyên lý,<br /> nhãn thời gian. Như vậy sẽ không có các nền tảng tri thức và khai mở vấn đề. Thời<br /> giao dịch có nhãn thời gian nhỏ hơn đến gian tới, chúng tôi sẽ tiếp tục nghiên cứu<br /> nữa. Do đó không xẩy ra trường hợp bị từ trong lĩnh vực này nhằm đề xuất thuật toán<br /> chối hay hệ thống phải khôi phục lại lại. hoặc thực hiện những cải tiến xử lý tương<br /> Tuy nhiên ứng dụng có thể xẩy ra trường tranh cập nhật dữ liệu trong môi trường<br /> hợp khóa chết, do giao dịch có nhãn thời phân tán; thực hiện mô phỏng, chứng minh<br /> gian nhỏ không bao giờ đến được bộ đệm. tính tính đúng đắn; so sánh, đánh giá toàn<br /> Đánh giá: Trong trường hợp có nhiều diện phương pháp mới.<br /> giao dịch xẩy ra tương tranh thì phương<br /> pháp tiếp cận Pessimistic có hiệu quả cao ÀI LIỆU HAM HẢO<br /> hơn so với phương pháp tiếp cận<br /> 1. Atul, et al. Adya (1995), “Efficient optimistic<br /> Optimistic. Chẳng hạn chi phí cần thiết để concurrency control using loosely<br /> khôi phục lại hay trường hợp khóa chết. synchronized clocks”, ACM SIGMOD<br /> Phương pháp này nếu sử dụng nhãn thời Record, pp. 23-34, 24.2.<br /> gian thì thứ tự sắp xếp của các giao dịch 2. Christoph, Rajesh Bordawekar, and Calin<br /> được quyết định tĩnh, nếu sử dụng khóa thì Cascaval von Praun (2008), “Modeling<br /> thứ tự được quyết định động. Thuật toán sử optimistic concurrency using quantitative<br /> dependence analysis”, Proceedings of the 13th<br /> dụng nhãn thời gian sẽ có hiệu quả hơn nếu ACM SIGPLAN Symposium on Principles and<br /> ứng dụng có thao tác đọc là chủ yếu. Các practice of parallel programming, ACM.<br /> giao dịch bị hủy bỏ sẽ được quyết định 3. Dag, et al Nyström (2004), “Pessimistic<br /> ngay lập tức. Thuật toán sử dụng khóa sẽ concurrency control and versioning to support<br /> có hiệu quả hơn khi ứng dụng có thao tác database pointers in real-time databases”, Real-<br /> ghi là chủ yếu. Tuy nhiên có thể dẫn đến sự Time Systems, 2004, ECRTS 2004, Proceedings,<br /> 16th Euromicro Conference on, IEEE.<br /> chiếm dụng khóa không hiệu quả, yêu cầu<br /> các giao dịch khác phải đợi hoặc thậm chí 4. Ho-Jin, and Byeong-Soo Jeong. Choi (2006),<br /> “A timestamp-based optimistic concurrency<br /> dẫn đến khóa chết. control for handling mobile transactions”,<br /> 4. luận hướng nghi n cứu Computational Science and Its Applications-<br /> Các thuật toán dựa trên kỹ thuật khóa ICCSA 2006, pp. 796-805.<br /> và nhãn thời gian vẫn tồn tại những vấn đề 5. Jiming, et al Chen (2010), “Distributed<br /> về khóa chết hay đòi hỏi khôi phục lại collaborative control for industrial automation<br /> nhiều lần. Do đó làm giảm độ tin cậy, hiệu with wireless sensor and actuator networks”,<br /> Industrial Electronics, IEEE Transactions, pp.<br /> năng của thuật toán. Bên cạnh đó thì hai 4219-4230, 57.12.<br /> phương pháp tiếp cận Optimistic và<br /> 6. Jun, et al Wang (2006), “Distributed<br /> Pessimistic cũng có những ưu và nhược collaborative filtering for peer-to-peer file<br /> điểm riêng và người xây dựng ứng dụng sharing systems”, Proceedings of the 2006<br /> cần đánh giá yêu cầu, đòi hỏi của hệ thống, ACM symposium on Applied computing,<br /> ACM.<br /> bài toán đặt ra để từ đó lựa chọn phương<br /> pháp tiếp cận hiệu quả nhất. 7. Matthias, et al Wiesmann (2000), “Database<br /> replication techniques: A three parameter<br /> Nghiên cứu đánh giá và so sánh các<br /> classification”, in Reliable Distributed<br /> thuật toán xử lý tương tranh cập nhật dữ Systems, 2000, SRDS-2000, Proceedings The<br /> liệu là bước đầu tiên hết sức quan trọng và 19th IEEE Symposium on. IEEE.<br /> <br /> 20<br /> 8. Michael E, et al Locasto (2004), 13. R., Berard, P., and Decitre, P Balter (1982),<br /> Collaborative distributed intrusion detection. “Why control of concurrency level in<br /> 9. Peng, et al. Han (2004), “A scalable P2P distributed systems is more important than<br /> recommender system based on distributed deadlock management”, in Proc. ACM<br /> collaborative filtering”, Expert systems with SIGACT-SIGOPS 1st Symp, on the Principles<br /> applications, pp. 203-210, 27.2. of Distributed Computing, pp. pages 183–193.<br /> 10. Philip A., and Nathan Goodman Bernstein 14. Samuel Kounev (2001), “Eliminating ECperf<br /> (1981), Concurrency control in distributed persistence bottlenecks when using RDBMS<br /> database systems, CSUR. with pessimistic concurrency control”,<br /> 11. Philip A., and Nathan Goodman Bernstein Technical Report, http://www. dvs1.<br /> (1983), “Multiversion concurrency control- informatik. tu-darmstadt. de/~ skounev,<br /> theory and algorithms”, ACM Transactions on Technical University of Darmstadt, Germany.<br /> Database Systems (TODS), pp. 465-483, 8.4. 15. Timothy R. Learmont (2001), “Fine-grained<br /> 12. Quazi Ehsanul Kabir, and Hidenori Nakazato consistency mechanism for optimistic<br /> Mamun (2005), “Timestamp based optimistic concurrency control using lock groups”, U.S.<br /> concurrency control”, in TENCON 2005, Patent, No. 6,240,413, 29 May.<br /> 2005 IEEE Region 10 Conference.<br /> <br /> <br /> Ngày nhận bài: 31/7/2015 Biên tập xong: 15/12/2015 Duyệt đăng: 20/12/2015<br /> <br /> <br /> <br /> <br /> 21<br />
ADSENSE
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2