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

<br /> <br /> I. ĐẶT VẤN ĐỀ<br /> 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ức<br /> thườ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ử<br /> 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ười<br /> 18<br /> <br /> ÑAÏI HOÏC ÑOÂNG AÙ<br /> Soá 05-2011<br /> <br /> <br /> <br /> bài<br /> sẽ gặp nhiều vấn đề khó khăn<br /> hiệu năng<br /> 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ác<br /> không cao, dễ<br /> ra ùn tắc, tốc độ<br /> có<br /> sự không<br /> nhấ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ệu<br /> tập trung thì tình trạng một ghế ngồi có thể được bán nhiều lần.<br /> 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ức<br /> hiệ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ữ<br /> 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ụng<br /> thườ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ệ<br /> 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ố<br /> lượng truy cập lớn, tăng tốc, an toàn,…<br /> 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ử<br /> 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ài<br /> nguyê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ảo<br /> cơ 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 đã đề<br /> 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 trong<br /> khi ở 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<br /> đượ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ự trong<br /> bối cảnh hiện nay.<br /> <br /> II. QUẢN LÝ GIAO DỊCH<br /> 1. Giao dịch<br /> <br /> Mộ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ằm<br /> mụ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 giao<br /> dị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ực<br /> hiệ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,<br /> 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ị<br /> mới được ghi vào cơ sở dữ liệu. [4]<br /> 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,<br /> 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ịch<br /> thự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ữ<br /> 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ịch<br /> cho 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ố trong<br /> lúc nó được thực hiện. [3]<br /> Để 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.<br /> ÑAÏI HOÏC ÑOÂNG AÙ<br /> Soá 05-2011<br /> <br /> 19<br /> <br /> <br /> <br /> Giao dịch là một đơn vị có tính nhất quán và tin cậy. Điều đó có được<br /> tính<br /> 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ất<br /> tính<br /> ACID - ACIDity).<br /> 2. Khóa<br /> <br /> Khóa (Lock) là quyền của một giao dịch được bộ quản lý khóa trao cho để có thể truy<br /> cậ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ại<br /> khó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<br /> (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óa<br /> trong một bảng khóa (Lock table). [2]<br /> <br /> 3. Kiểu khóa tương thích<br /> Khi 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ữ<br /> 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ực<br /> hiệ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 ReadLock<br /> và WriteLock, ta có ma trận tương thích như sau:<br /> RL<br /> WL<br /> <br /> RL<br /> Yes<br /> No<br /> <br /> WL<br /> No<br /> No<br /> <br /> 4. Bộ xếp lịch và các giao thức<br /> Để 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).<br /> <br /> B ng<br /> khóa<br /> <br /> Trao ho c t<br /> ch i khóa<br /> <br /> B qu n lý khóa<br /> Yêu c u khóa<br /> B x p l ch<br /> Yêu c u khóa<br /> <br /> Trao quy n truy<br /> c p, i ho c<br /> h yb<br /> <br /> Giao d ch tuân theo giao th c<br /> <br /> <br /> 20<br /> <br /> ÑAÏI HOÏC ÑOÂNG AÙ<br /> Soá 05-2011<br /> <br /> Bộ xếp<br /> phần của hệ thống cơ sở dữ liệu<br /> sắp xếp<br /> 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ải<br /> cho các thao tác<br /> buộc một giao<br /> đợ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ải<br /> hủy bỏ và thực hiện lại.<br /> 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êu<br /> cầu khóa trên các mục theo một thứ tự tuyến tính là một giao thức.<br /> 5. Tính khả tuần tự của các lịch (Serializability of Schedules) [4]<br /> <br /> Cho n giao dịch T1, T2,…, Tn<br /> - 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à<br /> 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.<br /> - Một lịch S được gọi là tuần tự (Serial) nếu tất cả các bước của mỗi giao dịch đều được<br /> thực hiện liên tiếp nhau. Như vậy trong lịch tuần tự mỗi giao dịch thực hiện toàn bộ các lệnh<br /> của nó và không có tương tranh.<br /> Như vậy, với n giao dịch thì sẽ có n! lịch là tuần tự.<br /> - Một lịch S được gọi là khả tuần tự (Serializable) nếu nó tương đương với 1 lịch tuần<br /> tự nào đó (gọi 2 lịch là tương đương nếu kết quả cuối cùng trong cơ sở dữ liệu sau khi thực<br /> hiện 2 lịch này là như nhau).<br /> Ví dụ 1: Giả sử rằng A và B có giá trị ban đầu lần lượt là 1000 và 2000. Giao dịch T1<br /> chuyển 50 từ A sang B và giao dịch T2 chuyển 10% từ A sang B. Các thao tác của các giao<br /> dịch được viết như sau:<br /> T1:<br /> <br /> Read(A);<br /> <br /> T2: <br /> <br /> Read(A);<br /> <br /> A=A-50;<br /> <br /> t=A*0.1;<br /> <br /> Write(A);<br /> <br /> <br /> <br /> A=A-t;<br /> <br /> Read(B);<br /> <br /> Write(A);<br /> <br /> B=B+50;<br /> <br /> Read(B);<br /> <br /> Write(B);<br /> <br /> B=B+t;<br /> Write(B);<br /> <br /> Lịch (a) là tuần tự: S(T1,T2) và sau khi thực hiện lịch tương tranh (b) thì kết quả tương<br /> đương lịch (a). Sau khi thực hiện lịch (c) thì giá trị của A và B lần lượt là 950 và 2100 như<br /> vậy rơi vào tình trạng không nhất quán.<br /> ÑAÏI HOÏC ÑOÂNG AÙ<br /> Soá 05-2011<br /> <br /> 21<br /> <br /> <br /> <br /> <br /> <br /> T1<br /> <br /> T2<br /> <br /> T1<br /> Read(A)<br /> A=A-50<br /> Write(A)<br /> <br /> Read(A)<br /> A=A-50<br /> Write(A)<br /> Read(B)<br /> B=B+50<br /> Write(B)<br /> <br /> Read(A)<br /> t=A*0.1<br /> A=A-t<br /> Write(A)<br /> Read(B)<br /> B=B+t<br /> Write(B)<br /> <br /> Read(B)<br /> B=B+50<br /> Write(B)<br /> <br /> (a)<br /> S1: Lịch tuần tự<br /> <br /> T2<br /> <br /> T1<br /> Read(A)<br /> A=A-50<br /> <br /> Read(A)<br /> t=A*0.1<br /> A=A-t<br /> Write(A)<br /> <br /> Read(B)<br /> B=B+t<br /> Write(B)<br /> <br /> (b)<br /> S2: Lịch khả tuần tự<br /> <br /> Write(A)<br /> Read(B)<br /> B=B+50<br /> Write(B)<br /> <br /> T2<br /> <br /> Read(A)<br /> t=A*0.1<br /> A=A-t<br /> Write(A)<br /> Read(B)<br /> <br /> B=B+t<br /> Write(B)<br /> <br /> (b)<br /> S3: Không khả tuần tự<br /> <br /> II. CÁC THUẬT TOÁN DỰA TRÊN CƠ SỞ KHÓA<br /> <br /> Ý tưởng chính: Các thao tác trên một đơn vị dữ liệu nếu có đụng độ (conflict) nhau thì<br /> chỉ cho phép 1 thao tác thực hiện tại một thời điểm. Điều này được thực hiện dựa trên việc<br /> khóa (Lock) đơn vị dữ liệu. [4]<br />  Các khai báo kiểu<br /> Declare-Type <br /> <br /> {Các khai báo kiểu dữ liệu}<br /> <br /> Operation: Một trong các thao tác Read, Write, Abort hay Commit<br /> DataItem: Một đơn vị dữ liệu trong cơ sở dữ liệu phân tán<br /> TransactionId: Chỉ danh duy nhất được gán cho mỗi Transaction<br /> DataVal: Một giá trị của kiểu dữ liệu cơ bản (như integer, real,…)<br /> SiteId: chỉ danh của một vị trí<br /> DbOp: Record {thao tác CSDL từ chương trình ứng dụng}<br /> <br /> <br /> Opn: Operation<br /> <br /> <br /> <br /> Data: DataItem<br /> <br /> <br /> <br /> Tid: TransactionId<br /> <br /> <br /> <br /> End<br /> <br /> DpMsg: Record {message từ bộ phận xử lý dữ liệu (DataProcessor)}<br /> 22<br /> <br /> ÑAÏI HOÏC ÑOÂNG AÙ<br /> Soá 05-2011<br /> <br /> <br /> <br />