Các thuật toán điều khiển tương tranh trong cập nhật dữ liệu phân tán

Bài viết Các thuật toán điều khiển tương tranh trong cập nhật dữ liệu phân tán trình bày kết quả nghiên cứu phương pháp quản lý giao dịch trong môi trường phân tán hiện đại và đặc biệt là các thuật toán điều khiển tương tranh trong cập nhật dữ liệu phân toán.
Nội dung trích xuất từ tài liệu:
Các thuật toán điều khiển tương tranh trong cập nhật dữ liệu phân tánI. ĐẶT VẤN ĐỀTrong xu hướng toàn cầu hóa hiện nay, để phù hợp với nhu cầu phát triển, các tổ chứcthường phân bố các chi nhánh phân tán trên nhiều vị trí địa lý khác nhau. Lúc này, việc sửdụng hệ cơ sở dữ liệu tập trung với chỉ duy nhất một hoặc một vài Servers phục vụ đa người18ÑAÏI HOÏC ÑOÂNG AÙSoá 05-2011bàisẽ gặp nhiều vấn đề khó khănhiệu năngdùng với một xảy toán dữ liệu lớn chậm, không an toàn,… Điều đónhưthể dẫn đến khai tháckhông cao, dễra ùn tắc, tốc độcósự khôngnhất quán về dữ liệu. Chẳng hạn, một hệ thống bán vé máy bay nếu sử dụng hệ cơ sở dữ liệutập trung thì tình trạng một ghế ngồi có thể được bán nhiều lần.Hệ cơ sở dữ liệu phân tán là giải pháp phù hợp với cấu trúc tự nhiên của các tổ chứchiện nay. Việc sử dụng nhiều Servers đặt trên nhiều vị trí địa lý khác nhau của hệ cơ sở dữliệu phân tán có thể giúp các Client tại mỗi vị trí ngoài việc truy xuất những dữ liệu sử dụngthường xuyên tại vị trí của mình mà còn có thể truy xuất đến dữ liệu tại các vị trí khác. Hệcơ sở dữ liệu phân tán có thể giải quyết tốt các vấn đề như đa truy cập từ xa, ngẫu nhiên, sốlượng truy cập lớn, tăng tốc, an toàn,…Tuy nhiên, một trong những vấn đề khó khăn trong hệ cơ sở dữ liệu phân tán đó là xửlý tương tranh. Trong quá trình hoạt động, có thể có nhiều truy xuất đồng thời đến một tàinguyên tại cùng một thời điểm, điều đó dẫn đến vấn đề tranh dành tài nguyên. Để đảm bảocơ sở dữ liệu luôn đáng tin cậy, gắn bó và nhất quán khi xảy ra tương tranh người ta đã đềxuất một số thuật toán điều khiển tương tranh. Các thuật toán này tương đối phức tạp trongkhi ở Việt Nam chưa có nhiều công trình nghiên cứu liên quan mà chủ yếu là các tài liệuđược biên dịch từ các tác giả nước ngoài. Vì vậy, bài viết này mang ý nghĩa thời sự trongbối cảnh hiện nay.II. QUẢN LÝ GIAO DỊCH1. Giao dịchMột giao dịch là một truy cập từ một chương trình ứng dụng nào đó vào hệ thống nhằmmục đích truy cập các đơn vị dữ liệu có thể được lưu trữ tại nhiều vị trí khác nhau. Một giaodịch sẽ đọc dữ liệu từ cơ sở dữ liệu vào một vùng làm việc riêng (Private workspace), thựchiện các tính toán trong vùng làm việc này và ghi dữ liệu từ đó vào cơ sở dữ liệu. Như vậy,các tính toán do giao dịch thực hiện không làm thay đổi cơ sở dữ liệu cho đến khi các giá trịmới được ghi vào cơ sở dữ liệu. [4]Giao dịch có thể thực hiện việc đọc, ghi, tính toán tạo ra dữ liệu mới cho cơ sở dữ liệu,vì vậy yêu cầu của giao dịch là tính nhất quán và tin cậy. Điều này có nghĩa là một giao dịchthực hiện một truy cập trên cơ sở dữ liệu, gây ra một sự biến đổi trạng thái. Nếu cơ sở dữliệu đã nhất quán trước khi thực hiện giao dịch thì cũng sẽ nhất quán khi kết thúc giao dịchcho dù giao dịch này có thực hiện đồng thời với các giao dịch khác hoặc xảy ra sự cố tronglúc nó được thực hiện. [3]Để truy cập đến cơ sở dữ liệu, giao dịch có thể thực hiện các thao tác Read hoặc Write.ÑAÏI HOÏC ÑOÂNG AÙSoá 05-201119Giao dịch là một đơn vị có tính nhất quán và tin cậy. Điều đó có đượctínhchất: Tính nguyên tử, tính nhất quán, tính riêng biệt và tính bền vững (gọi chunglàlàdo 4 chấttínhACID - ACIDity).2. KhóaKhóa (Lock) là quyền của một giao dịch được bộ quản lý khóa trao cho để có thể truycập trên một mục dữ liệu. Bộ quản lý khóa cũng có thể thu hồi lại khóa này. Có hai loạikhóa cơ bản là khóa đọc (Read-lock) chỉ cho phép một giao dịch đọc một mục và khóa ghi(Write-lock) cho phép thực hiện cả hai thao tác đọc và ghi. Bộ quản lý khóa lưu các khóatrong một bảng khóa (Lock table). [2]3. Kiểu khóa tương thíchKhi giao dịch thực hiện việc truy cập một đơn vị dữ liệu thì trước hết phải xin khóa dữliệu. Hai giao dịch có 2 kiểu khóa được gọi là tương thích với nhau nếu chúng có thể thựchiện đồng thời trên 1 đơn vị dữ liệu (cùng có kiểu khóa ReadLock). Với 2 kiểu ReadLockvà WriteLock, ta có ma trận tương thích như sau:RLWLRLYesNoWLNoNo4. Bộ xếp lịch và các giao thứcĐể ngăn ngừa bế tắc có thể sử dụng bộ xếp lịch (Scheduler) và các giao thức (Protocol).B ngkhóaTrao ho c tch i khóaB qu n lý khóaYêu c u khóaB x p l chYêu c u khóaTrao quy n truyc p, i ho ch ybGiao d ch tuân theo giao th c20ÑAÏI HOÏC ÑOÂNG AÙSoá 05-2011Bộ xếpphần của hệ thống cơ sở dữ liệusắp xếpmột lịch biểu lịch là một thànhcủa các giao dịch. Nó cũng có thểchịu trách nhiệmdịch phảicho các thao tácbuộc một giaođợi cho đến khi khóa mà giao dịch yêu cầu được giải phóng hoặc buộc một giao dịch phảihủy bỏ và thực hiện lại.Giao thức là các quy tắc mà các giao dịch phải tuân theo. Chẳng hạn, chiến lược yêucầu khóa trên các mục theo một thứ tự tuyến tính là một giao thức.5. Tính khả tuần tự của các lịch (Serializability of Schedules) [4]Cho n giao dịch T1, T2,…, Tn- Gọi một lịch (Schedule) S của 1 tập các giao dịch T1, T2,…, Tn là một thứ tự màtrong đó các lệnh của các giao dịch này được thực hiện lần lượt hoàn toàn ...