      Các khái niệm Các vấn đề bất thường trong truy xuất đồng thời Lịch thao tác (Schedule) Kỹ thuật khóa Kỹ thuật nhãn thời gian Các kỹ thuật khác    Truy xuất đồng thời (Access Concurrency) Giao tác (Transaction) Đơn vị dữ liệu (Granule)   Các truy xuất dữ liệu của CSDL xảy ra cùng thời gian trong môi trường nhiều người dùng (multi user) Truy xuất đồng thời không tranh chấp : ◦ n truy xuất trên n dữ liệu khác nhau  Truy xuất đồng thời có tranh chấp : ◦ n truy xuât đồng thời trên k dữ liệu chung.    Là một dãy các thao tác (actions) trên dữ liệu được coi như là một đơn vị xử lý nguyên tố (processing unit) Các xử lý bên trong một giao tác phải hoàn thành tất cả hoặc thất bại tất cả. Khi một giao tác được thực hiện hoàn tất thì nó phải đảm bảo tính nhất quán của CSDL (biến CSDL thành một trạng thái nhất quán mới)  Nguyên tố (Atomicity) ◦ Một giao tác là một đơn vị xử lý nguyên tố không chia nhỏ được  Nhất quán (Consistency) ◦ Biến cơ sở dữ liệu từ trạng thái nhất quán này đến trạng thái nhất quán khác  Cô lập (Isolation) ◦ Không bị ánh hưởng bởi các giao tác khác  Bền vững (Durability) ◦ Các thay đổi mà giao tác thực hiện trên dữ liệu của CSDL phải được phản ánh bền vững lên CSDL     Active giai đoạn đầu tiên khi giao tác bắt đầu thực thi Partially committed sau khi lệnh cuối cùng trong giao tác thi hành. Failed sau khi phát hiện không thể thực hiện bình thường được. Aborted sau khi giao tác bị rolled back và CSDL phục hồi lại trạng thái trước của nó. Hai lựa chọn khi một giao tác bị abort: ◦ Khởi động lại giao tác ◦ Hủy giao tác  Committed ◦ Sau khi thực hiện thành công. Partially committed Committed Active Failed Aborted  Giảsử CSDL đang ở trạng thái nhất quán SELECT FNAME, LNAME FROM EMPLOYEE WHERE EMP_NUM=‘10201’   Sau khi thực hiện câu lệnh SQL thì CSDL vẫn giữ nguyên được trạng thái nhất quán Không có sự thay đổi nào xảy ra trên CSDL.  Giả sử CSDL đang ở trạng thái nhất quán Update TAIKHOAN Set SoDu=SoDu-50 Where MATK=A Update TAIKHOAN Set SoDu=SoDu+50 Where MATK=B   CSDL vẫn giữ nguyên được trạng thái nhất quán (nếu như cả hai câu lệnh SQL ở trên đều thành công hoặc đều thất bại) Hệ QTCSDL không chắc là lúc nào thực tế cũng diễn ra như thế. BEGIN TRANSACTION COMMIT TRANSACTION ROLLBACK TRANSACTION Bắt đầu giao tác Kết thúc giao tác Hủy giao tác   Là khối lượng dữ liệu nhỏ nhất mà CSDL có thể thao tác Đơn vị dữ liệu có thể là ◦ ◦ ◦ ◦  Trường (Field) Mẫu tin (Record) Bảng (Table) CSDL (Database) Kích thước của đơn vị dữ liệu ánh hưởng đến hiệu năng xử lý đồng thời       Các khái niệm Các vấn đề bất thường trong truy xuất đồng thời Lịch thao tác (Schedule) Kỹ thuật khóa Kỹ thuật nhãn thời gian Các kỹ thuật khác 1. 2. 3. 4. Vấn đề mất dữ liệu đã cập nhật Vấn đề không thể đọc lại Vấn đề đọc phải dữ liệu chưa được xác nhận Vấn đề bóng ma T1 Begin Tran Read A T2 Begin Tran Read A A:=A+10 Write A A:=A*100 Write A Commit Tran Commit Tran T1 Begin Tran T2 Read A Begin Tran Read A A:=A+10 Write A Commit Tran Read A Commit Tran T1 Begin Tran Read A T2 A:=A+10 Begin Tran Write A Read A Print A Abort Commit Tran T1 Read(A) T2 Read(A) A:=A-10 Write (A) Read(B) Read(B) Print(A+B) B:=B+10 Write(B)       Các khái niệm Các vấn đề bất thường trong truy xuất đồng thời Lịch thao tác (Schedule) Kỹ thuật khóa Kỹ thuật nhãn thời gian Các kỹ thuật khác    Định nghĩa lịch thao tác Lịch tuần tự - khả tuần tự Thuật toán kiểm tra tính khả tuần tự   Lịch thao tác của n giao tác xử lý đồng thời T1,T2,….,Tn là một thứ tự thực hiện các hành động của n giao tác này Lịch thao tác phải đảm bảo thứ tự của các hành động trong cùng một giao tác  Một lịch S được lập từ n giao tác xử lý đồng thời T1,T2,….,Tn được gọi là lịch tuần tự nếu với mọi giao tác Ti, các hành động của Ti được thực hiện liên tiếp nhau  Một lịch S lập từ n giao tác xử lý đồng thời T1,T2,….,Tn được gọi là lịch khả tuần tự nếu khi thực hiện S, cho kết quả giống một lịch tuần tự nào đó được lập từ n giao tác này   Hai thao tác Oi,Oj của hai giao tác xử lý đồng thời Ti,Tj được gọi là tương thích nếu việc thực hiện theo thứ tự < Oi,Oj > cho kết quả giống việc thực hiện theo thứ tự <Oj,Oi > Hai thao tác thực hiện trên hai đơn vị dữ liệu khác nhau thì tương thích   Hai thao tác tương thích Oi,Oj có thể thay đổi thứ tự thực hiện cho nhau mà không làm thay đổi kết quả, nên còn được gọi là hai thao tác khả hoán Bảng khả hoán của hai thao tác trên cùng đơn vị dữ liệu Read Write Read Yes No Write No No  Một lịch S được gọi là khả tuần tự nếu chúng ta có thể giao hoán các thao tác khả hoán để đưa S về một lịch tuần tự S7 1 T1 T2 T3 Read(A);A:=A-10 2 Read(B);B:=B-20 3 Read(C); C:=C+B 4 Write(B) 5 Read(B);B:=B+10 6 Write(A) 7 Read(A);A:=A+5 8 Write(C) 9 Write(A) 10 Read(A);A:=A-20 11 Read(C);C:=C+20 12 Write(B) 13 Write(C) 14 Write(A)    Bộ lập lịch sẽ phải thực hiện các hành động của nó theo các thuật toán điều khiển đồng thời Đảm bảo đơn vị xử lý trung tâm của máy tính (CPU) được xử dụng một cách hiệu quả Tạo điều kiện về cô lập dữ liệu để đảm bảo rằng hai giao tác không cập nhật cùng một đơn vị dữ liệu ở cùng một thời điểm       Các khái niệm Các vấn đề bất thường trong truy xuất đồng thời Lịch thao tác (Schedule) Kỹ thuật khóa Kỹ thuật nhãn thời gian Các kỹ thuật khác     Các kỹ thuật điều khiển đồng thời Khóa đơn giản Khóa đọc ghi Khóa trên dữ liệu phân cấp  Những kỹ thuật cho phép bộ lập lịch sử dụng để tạo một lịch khả tuần tự từ n giao tác thực hiện đồng thời.   Kỹ thuật khoá đơn giản còn gọi khoá nhị phân (Binary locks) Bộ lập lịch với cơ chế khóa đơn giản (locking scheduler) ◦ Là bộ lập lịch với thêm 2 hành động:  Lock: Khóa  Unclock: Giải phóng khóa ◦ Các khóa được ghi nhận trong bảng khóa (Lock Table)  Các giao tác trước khi muốn đọc/ghi lên 1 đơn vị dữ liệu phải phát ra yêu cầu xin khóa (lock) đơn vị dữ liệu đó. ◦ Ký hiệu Lock(A) hay l(A)  Yêu cầu này được bộ phận quản lý khóa xử lý (Lock Manager) ◦ Yêu cầu xin khóa được chấp thuận nếu đơn vị dữ liệu chưa bị khóa bởi một giao tác nào khác  Sau khi thao tác xong thì giao tác này phải phát ra lệnh giải phóng đơn vị dữ liệu (unclock) ◦ Ký hiệu: Unclock(A) hay u(A)  Giao tác đúng đắn: Giao tác Ti đọc hay ghi lên đơn vị dữ liệu A phải được thực hiện sau khi Ti khóa trên A và trước khi Ti giải phóng khóa A. ◦ Ti: …..lock(A)….read(A)/write(A)…..unclock(A)  Lịch thao tác hợp lệ: Khi Ti đang giữ khóa trên một đơn vị dữ liệu A thì không Ti nào khác được khóa trên A. S   Giao tác T1, T2 có đúng đắn không? Lịch S có hợp lệ không   Giao tác Ti nào đúng đắn? Lịch S nào hợp lệ?    Input: Lịch S được lập từ n giao tác xử lý đồng thời T1,T2,…Tn theo kỹ thuật khóa đơn giản Output: S khả tuần tự hay không? Xây dựng 1 đồ thị có hướng G ◦ Mỗi giao tác Ti là đỉnh của đồ thị ◦ Nếu một giao tác Tj phát ra Lockj(A) sau một giao tác Ti phát ra Locki(A) thì vẽ một cung từ Ti đến Tj  S khả tuần tự nếu G không có chu trình Ví dụ Lịch S có khả tuần tự không? S T1 T2 Lock(A) Read(A); A:=A+100 Write(A) Unlock(A) Lock(A) Read(A); A:=A*2 Write(A) Unlock(A) Lock(B) Read(B); B:=B*2 Unlock(B) Lock(B) Read(B); B:=B+100 Write(B) Unlock(B) Bài tập Lịch S có khả tuần tự không? S Bài tập Lịch S có khả tuần tự không? S  Vấn đề khóa sống (Live Lock)  Vấn đề khóa chết (Dead Lock)  Ngăn ngừa khóa chết Một giao tác T phải xin khóa tất cả các đơn vị dữ liệu mà mình sẽ thao tác, nếu được chấp thuận tất cả thì sẽ thao tác, ngược lại phải giải phóng các khóa đã được cấp trên các đơn vị dữ liệu Phát hiện khóa chết: Xây dựng đồ thị chờ (Waiting Graph) G  ◦ Mỗi giao tác là một nút của đồ thị G ◦ Nếu có giao tác Tj phát ra yêu cầu khóa đơn vị dữ liệu A, và phải chờ vì A đã bị khóa bởi Ti, thì vẽ cung nối Ti,Tj ◦ Nếu G xuất hiện chu trình  Xảy ra khóa chết Trong một giao tác, tất cả các thao tác khóa đều phải xảy ra trước các thao tác giải phóng khóa Nếu lịch S thỏa nghi thức khóa 2 giai đoạn (2PL) thì S khả tuần tự Chứng minh 2PL Có giải quyết được vấn đề deadlock không?!     Các kỹ thuật điều khiển đồng thời Khóa đơn giản Khóa đọc ghi Khóa trên dữ liệu phân cấp Định lý: Lịch S thỏa (1),(2),(3) thì S khả tuần tự     Các kỹ thuật điều khiển đồng thời Khóa đơn giản Khóa đọc ghi Khóa trên dữ liệu phân cấp   Quan hệ TAIKHOAN(MATK, SODU) Giao tác gửi và rút tiền ◦ Khóa relation  Các giao tác thay đổi giá trị số dư của 1 tài khoản X sẽ yêu cầu khóa độc quyền  Vì khóa ở mức độ quan hệ nên toàn bộ bảng bị khóa  Các giao tác khác muốn truy cập tài khoản Y (khác X) cũng phải chờ  Vô lý Tốc độ xử lý chậm ◦ Khóa tuple hay disk block  2 Tài khoản ở 2 block khác nhau có thể cập nhật cùng thời điểm  Xử lý nhanh  Giao tác tính tổng tiền của các tài khoản ◦ Khóa relation? ◦ Khóa tuple hay disk block?  Quản lý khóa ở nhiều mức độ ◦ Tính chất hạt (granularity) tăng khi đơn vị dữ liệu bị khóa càng lớn ◦ Tính đồng thời (concurrency) tăng khi đơn vị dữ liệu bị khóa càng nhỏ    Relations là đơn vị dữ liệu khóa lớn nhất Một relation gồm 1 hoặc nhiều blocks (pages) Một block gồm 1 hoặc nhiều bộ (tuples)  Khóa thông thường ◦ Shared lock: S ◦ Exclusive lock: X  Khóa cảnh báo (warning lock) ◦ Warning (intention to) shared lock: IS ◦ Warning (intention to) exclusive lock: IX  Cho biết các khóa có thể cùng tồn tại trên một node dữ liệu Yêu cầu khóa Trạng thái hiện hành  Cho biết các khóa có thể phát trên node con khi node cha đang có một khóa nào đó 1. 2. 3. 4. 5. 6. Thỏa ma trận tương thích trên cùng một node Khóa node gốc của cây trước Thỏa ma trận tương thích giữa node cha và node con Ti thỏa 2PL Ti có thể giải phóng node Q khi không có node con nào của Q bị khóa bởi Ti Trong trường hợp thêm mới hay xóa bỏ một node Q thì cha của Q phải được khóa bằng X trước   T2 có thể truy xuất f2.2 bằng khóa X được không? T2 sẽ có những khóa gì?   T2 có thể truy xuất f3.1 bằng khóa X được không? T2 sẽ có những khóa gì?       Các khái niệm Các vấn đề bất thường trong truy xuất đồng thời Lịch thao tác (Schedule) Kỹ thuật khóa Kỹ thuật nhãn thời gian Các kỹ thuật khác     Giới thiệu Kỹ thuật nhãn thời gian toàn phần Kỹ thuật nhãn thời gian riêng phần Kỹ thuật nhãn thời gian nhiều phiên bản  Một giao tác T khi phát sinh thì được gán một nhãn thời gian timestampTS(T) ghi nhận lại thời điểm phát sinh của T.  Mỗi đơn vị dữ liệu A cũng có một nhãn TS(A) nhãn này ghi lại nhãn thời gian TS(T) của giao tác T đã thao tác (read/ write) A thành công sau cùng  Để giảm bớt trường hợp các giao tác bị Abort, người ta tách nhãn của đơn vị dữ liệu thành hai loại nhãn: ◦ ReadTimestamp A - RT(A): để ghi nhận TS(T) gần nhất (giao tác có nhãn thời gian lớn nhất) đọc A thành công. ◦ WriteTimestamp A - WT(A): để ghi nhận TS(T) gần nhất (giao tác có nhãn thời gian lớn nhất) ghi A thành công.   Gắn các nhãn thời gian TS(T), RT(A), WT(A) Xử lý các tình huống: ◦ ◦ ◦ ◦ Đọc quá trễ Ghi quá trễ Đọc dữ liệu rác Qui tắc ghi Thomas T vào trước U : TS(T)<TS(U)  U ghi X trước T: TS(T)<WT(X)  T không thể đọc X sau U  Hủy T  T vào trước U : TS(T)<TS(U)  U đọc X trước , T ghi X sau: WT(X)<TS(T)<RT(X)  T không nên ghi X do U đã đọc X (U phải đọc giá trị do T ghi)  Hủy T     T vào trước U : TS(T)<TS(U) U ghi X trước , T ghi X sau: ST(T)<WT(X) T ghi X xong thì không làm được gì ◦ Không có giao tác nào đọc được giá trị X của T (nếu có cũng bị hủy do đọc quá trễ) ◦ Các giao tác đọc sau T và U thì mong muốn đọc giá trị X của U  Bỏ qua thao tác ghi của T  Khi có yêu cầu đọc hoặc ghi từ giao tác T. Bộ lập lịch sẽ: ◦ Đáp ứng yêu cầu ◦ Hủy và khởi tạo lại T với 1 timestamp mới ◦ Trì hoãn T, sau đó mới quyết định hủy T hoặc đáp ứng yêu cầu Procedure Read(T,A) if WT(A) <= TS(T) then begin Read(A) // Cho phép đọc A RT(A):=MAX(RT(A),TS(T)) // Có thể người đi trước đã đọc //nên phải lưu người trước end else Abort {T} //Hủy T và khởi tại lại với TS mới Procedure Write(T,A) If RT(A) <= TS(T) then If WT(A) <= TS(T) then Begin Write(A) // Cho phép ghi A WT(A) :=TS(T) End //Else : RT(A) < TS(T) < WT(A) //: không làm gì hết (bỏ qua) Else Abort{T} Abort Abort Giá trị của A đã ghi bởi T1  Bỏ qua thao tác này Abort   Giữ lại nhiều phiên bản của một đơn vị dữ liệu. Mỗi phiên bản có 2 nhãn RT và WT ghi nhận giao tác cuối cùng đã read hoặc write thành công lên nó Khi giao tác T phát ra yêu cầu thao tác trên X ◦ Tìm 1 phiên bản thích hợp của X ◦ Đảm bảo tính khả tuần tự  Một phiên bản mới của X sẽ được tạo thành khi hành động ghi X thành công Procedure Read(T,A) j:= ‘số thứ tự của phiên bản cuối cùng của A’ While WT(Aj) > TS(T) j := j-1 // lùi phiên bản Read(Aj) RT(Aj) = MAX( RT(Aj),TS(T)) Procedure Write(T,A) j:= ‘số thứ tự của phiên bản cuối cùng của A’ While WT(Aj) > TS(T) j := j-1 // lùi phiên bản if RTS(Aj) > TS(T) then // chỉ có duy nhất một trường hợp này bị bỏ Abort {T} Else Begin // tạo/chèn phiên bản Aj+1 Write(Aj+1) RT(Aj+1)=0 WT(Aj+1)=TS(T) End  Thao tác đọc ◦ Giao tác T chỉ đọc giá trị của phiên bản do T hay những giao tác trước T cập nhật  Thao tác đọc không bị hủy  Thao tác ghi ◦ Thực hiện được thì chèn phiên bản mới ◦ Không được thì hủy     Bao nhiêu Write thì có thể có tới bấy nhiêu phiên bản Không bao giờ WT của các phiên bản giảm dần Không bao giờ cập nhật WT và RT vào phiên bản cũ Tốn nhiều chi phí tìm kiếm và tốn bộ nhớ