Đề thi Hệ Phân Tán K48

Đề K48

Đề chẵn
1. Trình bày nguyên lý và so sánh các mô hình di trú mã.
2. Trình bày về các khái niệm name, address, identifier, namespace.
3. Giải thích các tính chất ACID (Automic, Consistent, Isolated, Durable) của các giao tác phân tán
Đề lẻ
1 Trình bày phương pháp triệu gọi đối tượng từ xa (roi) sử dụng trong hệ phân tán
2 Phân giải tên là gì và nó đuợc thực hiện thế nào
3 So sánh mô hình nhất quán chặt và mô hình nhất quán tuần tự trong hệ phân tán

GỢI Ý:

câu 1 Đề chẵn K48 : Trình bày nguyên lý và so sánh các mô hình di trú mã. ( đã có trong đề K47 )

Câu 2 để chẵn K48 : Trình bày về các khái niệm name, address, identifier, namespace.

Có rất nhiều từ dùng để xác định một thực thể đó là: tên (name), địa chỉ (address), định danh (identifier), tên thân thiện (Human-friendly name).
•   Tên (name): là xâu các bit hoặc kí tự dùng để tham chiếu đến một thực thể trong hệ phân tán.
•   Địa chỉ (address): khi truy cập đến thực thể ta sử dụng điểm truy cập (access point). Các điểm truy cập này cũng phải được đặt tên và tên đó chính là địa chỉ của nó. Như vậy địa chỉ của thực thể chính là tên của điểm truy cập thực thể tương ứng.
•   Định danh (Identifiers): đây cũng là một kiểu tên đặc biệt. Việc định danh một tên phải thỏa mãn ba tính chất sau:
–   Mỗi thực thể chỉ được tham chiếu bởi duy nhất một định danh ID
–   Mỗi ID tham chiếu tới một thực thể.
–   ID đó không được gán cho một thực thể khác
Không gian tên (Name Space ) :Tập hợp tất cả các từ dùng để xác định thực thể gọi là không gian tênNếu xét về mặt hình học thì đây là một đồ thị có hướng, gồm các nút và các cung, gọi là đồ thị tên (naming graph). Đồ thị có cấu trúc: Mỗi nút lá miêu tả một một thực thể. Mỗi nút directory gắn với nhiều nút khác; lưu trữ trong bảng directory, bảng này là tập các cặp (label,indetifier).
Tên thân thiện (Human-friendly name): là các tên được đặt một cách dễ hiểu, thân thuộc với con người

Giao tác là gì? Giao tác phân tán là gì, để làm gì?so sánh các giao tác phân tán

Giao tác là một đơn vị công việc( bao gồm nhiều lệnh ) riêng lẻ, hay còn gọi là một nguyên tử công việc . Mỗi giao dịch có nhiều bước ( nhiều lệnh ) mỗi lệnh phải thành công thì giao tác mới thành công
Giao tác có 4 tính chất đó là :
Tính nguyên tử (atomic ) : mọi giao tác không thể phân chia nhỏ thành các giao tác nhỏ hơn. Nếu giao tác không thành công thì hệ thống sẽ trở lại trạng thái trước khi giao tác bắt đầu.
Tính nhất quán ( consistent ) : giao tác không xâm phạm các bất biến của hệ thống. Có nghĩa là trước khi giao tác thực thi các bất biến hệ thống như thế nào thì sau giao tác các bất biến đó vẫn giữ nguyên. ví dụ trong ngân hàng , khi có một giao dịch nội bộ thì sau giao dịch đó tổng số tiền trong ngân hàng vẫn giữ nguyên. Tuy nhiên trong quá trình giao dịch thì số tiền đó có thể bị thay đổi , nhưng nó lại ẩn nếu đứng ở ngoài giao dich. — ( tương tự như giao tác )
Tính cô lập ( isolated ) : các giao tác đồng thời không gây trở ngại cho nhau . Nghĩa là các giao tác cùng chạy mỗi thời gian thì ko gây ra ảnh hưởng cho nhau , ko thay đổi giao tác khác
Tính lâu bền (Durable): khi giao tác đã cam kết thì các thay đổi đối với nó không phải là tạm thời mà là kéo dài . Ví dụ khi một giao tác cam kết , thì trong trường hợp mất điện nó ko bị mất đi mà khi có điện thì nó sẽ dc khôi phục lại

Giao tác phân tán là giao tác thực hiện đc trên nhiều cơ sở dữ liệu và nhiều câu lệnh có thể thực thi trên cùng một cơ sở dữ liệu trong cùng một thời điểm

So sánh các giao tác : Có 3 loại giao tác là Limition of Flat Transaction ( giao tác phẳng ),Nested Transaction ( giao tác lồng ) ,Distributed Transaction ( giao tác phân tán )

a.   Giao tác phẳng: Là loại giao tác đơn giản và được dùng nhiều nhất thỏa mãn 4 tính chất nguyên tử, nhất quán, độc lập, và bền bỉ như kể trên.
+Ưu điểm: Đơn giản và được dùng nhiều nhất.
+Nhược điểm: Chính bản thân tính chất nguyên tử khiến cho giao tác phẳng không cho phép một phần kết quả được hoàn thiện độc lập hoặc là bị bỏ qua. Giảm hiệu năng của hệ thống.
b.   Giao tác lồng: Giao tác lồng có cấu trúc là một tập hợp các giao tác con được phân cấp. Giao tác trên cùng là giao tác cha nó có thể được thực thi song song với các giao tác khác và được chia nhỏ hơn, các giao tác nhỏ hơn này cũng có thể được thực hiện song song và lại được chia tiếp.
+Ưu điểm: Giao tác lồng có thể thực hiện tính chất chồng sâu giúp nâng cao hiệu quả của hệ thống.
+Nhược điểm:
Tuy nhiên nó cũng có nhược điểm nhỏ nhưng rất quan trọng là nếu tính huống sảy ra như sau các giao tác con được diễn ra song song , một trong các giao tác con đó đưa ra kết quả trước cho giao tác trên cùng, sau khi tính toán giao tác trên cùng hủy bỏ và đưa trạng thái hệ thống về thời điểm ban đầu trước khi giao tác lồng thực hiện. Vì vậy các giao tác con còn lại sẽ bị dừng và không được hoàn thành.
Tính chất bền bỉ của giao tác lồng chỉ được áp dụng cho tầng trên cùng cũng là một hạn chế.
c.   Giao tác phân tán: Giao tác phân tán bản chất là một giao tác phẳng có cách hoạt động hợp lý, giao tác mà không thể phân chia được và được thực hiện trên dữ liệu phân tán.
+Nhược điểm: Bản chất là giao tác phẳng nên nó cũng có một số yếu điểm giao tác phẳng.
+Ưu điểm: Là một sự lựa chọn thích hợp cho hệ phân tán.

Câu hỏi 2: Trình bày nguyên lý điều khiển tương tranh và so sánh 2 loại điều khiển tương tranh bi quan và lạc quan?
1.   Nguyên lý điều khiển tương tranh:
+Là quá trình điều khiển giúp cho nhiều giao tác diễn ra đồng thời mà không sảy ra tranh chấp.
+Có 2 loại điều khiển:
(1)   Điều khiển bi quan.
(2)   Điều  khiển lạc quan.
2.   So sánh
a.   Điều khiển bi quan:
+ Là phương pháp điều khiển với quan điểm “Nếu một sự kiện có khả năng sai thì nó sẽ sai”. Vì vậy để thực hiện phương pháp này người ta thực hiện đồng bộ bằng tem thời gian trước khi tiến hành thực hiện giao tác.
+Ưu điểm: Với phương pháp này đảm bảo độ tin cậy cao, thích hợp với hệ thống tải lớn.
+Nhược điểm: Sẽ tạo ra thời gian trễ(deadlock) vì các tiến trình phải chờ đợi, làm hiệu quả của hệ thống không cao.
b.   Điều khiển lạc quan:
+Là  phương pháp điều khiển với quan điểm “Nói chung tất cả mọi sự kiện đều đúng”. Với phương pháp này người ta thực hiện đồng bộ sau khi thực hiện thành công giao tác.
+Ưu điểm: Giải phóng thời gian trễ (deadlock), các tiến trình được xử lý luôn không phải chờ, làm nâng cao hiệu năng của hệ thống.
+Nhược điểm: Đôi khi gây ra lỗi giao tác phải thực hiện lại, với hệ thống tải lớn thì phương pháp này là không thích hợp.

Các mô hình nhất quán

Nhất quán cuối cùng (eventual consistency)
ĐN : Là mô hình nhất quán mà khi 1 dữ liệu có nhiều bản sao thì khi thực hiện cập nhật thì tất cả các bản sao phải giống nhau (cùng được cập nhật).
Ưu điểm :
đảm bảo khả năng trong suốt caoà    o   Thực hiện tốt
o   Rẻ, dễ thực hiện.
Nhược điểm
o   Yêu cầu các client thực hiện cập nhật thường xuyên
o   Khi các client di chuyển khó thực hiện
o   Thường chỉ áp dụng cho những hệ thống có ít người cập nhật

Nhất quán đọc đều (monotonic – read consistency)
ĐN : “Là mô hình nhất quán mà khi 1 tiến trình đọc giá trị 1 mục dữ liệu x, phải đảm bảo rằng thao tác đọc trên x luôn trả về cùng 1 giá trị hay là 1 giá trị gần đấy nhất”
Nói cách khác, nếu 1 tiến trình nhận được giá trị của x ở thời điểm t thì tại thời điểm sau t, nó sẽ không nhận được giá trị cũ hơn của x tại thời điểm t.
Ví dụ : hệ thống CSDL mail. Thư điện tử có thể thêm vào mailbox ở bất cứ đâu. Một người đọc thư điện tử ở A (coi như không xóa thư). Khi người đó đến B và mở mailbox thì những thư trong mailbox ở A cũng phải nằm ở trong maibox khi được mở tại B.

Nhất quán ghi đều (monotonic – write consistency)
   ĐN : Là mô hình nhất quán mà 1 tiến trình ghi lên 1 mục dữ liệu x được hoàn thành trước khi bất kỳ quá trình ghi nào khác trên x bởi cùng 1 tiến trình.
Mô hình này tương tự như nhất quán FIFO trong mô hình hướng dữ liệu, tuy nhiên nó chỉ liên quan đến 1 tiến trình chứ không phải nhiều tiến trình đang cùng thực hiện.
Nói cách khác, với mô hình này, khi 1 tiến trình ghi thực hiện, nó phải đảm bảo rằng mọi tiến trình ghi trước nó (về mặt thời gian) phải được hoàn thành. Mô hình nhất quán này được áp dụng trong những hệ thống mà quá trình ghi có thể bị thay thế và việc thực hiện tuần tự quá trình ghi không được đảm bảo. (vd : việc cập nhật lên 1 bản sao của thư viện, mọi bản cập nhật trước đó phải được thực hiện trước)

Nhất quán đọc kết quả ghi (Read – your – write consistency)
    ĐN : “Tác động của một thao tác ghi của một tiến trình lên mục dữ liệu x sẽ luôn được nhìn thấy bởi một thao tác đọc lần lượt trên x của cùng tiến trình đó”
Nói cách khác, 1 quá trình ghi luôn hoàn thành trước khi trước khi 1 quá trình đọc của cùng tiến trình thực hiện bất kể việc đọc diễn ra ở đâu.
Ưu điểm : Đảm bảo người dùng luôn nhận được kết quả mới nhất
Nhược điểm : Khi thực hiện ghi (cập nhật), có thể người dùng không thể truy cập được dữ liệu (vd:việc thay đổi password của 1 tài khoản thư viện) hay khi bộ đệm ko có hiệu lực (truy cập Web)

Nhất quán ghi theo sau đọc (write – follow – read consistency)
ĐN : “Tác động bởi một thao tác ghi của một tiến trình lên mục dữ liệu x theo sau 1 quá trình đọc trước đó của cùng 1 tiến trình được đảm bảo xảy ra trên giá trị mới nhất đã được đọc”
Nói cách khác, một quá trình ghi của 1 tiến trình trên mục dữ liệu x sẽ được thực hiện trên 1 bản sao của x được cập nhật với giá trị đọc gần nhất bởi tiến trình đó.
Ưu nhược điểm : bó tay, chả biết nói thế nào
Gớm: Khó hiểu và trừu tượng thì vô đối  confused confused confused

* Những người dùng chỉ đọc bài báo (article) không cần bất cứ mô hình nhất quán hướng client cụ thể nào cả.

Câu hỏi : Nguyên lý nhất quán và nhân bản? Phân tích (so sánh)  các mô hình nhất quán lấy dữ liệu làm chung tâm?

Trả lời
1.   Nguyên lý nhất quán và nhân bản:
Trong hệ phân tán có 2 lý do để sử dụng bản sao:
+Thứ nhất dùng bản sao để tăng độ tin cậy và tính sẵn sàng của hệ thống.
+Thứ 2 dùng bản sao để tăng hiệu năng  của hệ thống.
Tuy nhiên việc sử dụng bản sao cũng phải trả giá, đó là tính nhất quán dữ liệu của hệ thống bị suy giảm. Do sử dụng bản sao nên có thể xảy ra trường hợp có sự thay đổi trên một dữ liệu mà không cập nhật trên các bản sao của nó. Điều này gây ra các sai sót trong hệ thống. Nguyên lý nhất quán và nhân bản được đưa ra cung cấp:
(1)   Các mô hình nhất quán.
(2)   Các giao thức phân phối .
(3)   Các giao giao thức nhất quán.
+ Có một mâu thuẫn là tính nhất quán càng cao thì hiệu năng của hệ thống càng thấp vì vậy khi thiết kế hệ phân tán cần cân nhắc kỹ.

2.   Phân tích ưu nhược điểm của các mô hình nhất quán lấy dữ liệu làm trung tâm:
+ Các mô hình nhất quán lấy dữ liệu làm trung tâm:
(1)   Mô hình nhất quán chặt.
(2)   Mô hình nhất quán tuần tự.
(3)   Mô hình nhất quán tuyến tính.
(4)   Mô hình nhất quán nhân quả.
(5)   Mô hình nhất quán FIFO.
(6)   Mô hình nhất quán yếu.
(7)   Mô hình nhất quán đi ra.
(8)   Mô hình nhất quán đi vào.
+ Phân tích các mô hình trên:
(1)   Mô hình nhất quán chặt:
+Là một mô hình nghiêm ngặt phải thỏa mãn điều kiện sau: Thao tác đọc bất kỳ trên mục dữ liệu x đều trả về một giá trị tương ứng với kết quả của thao tác ghi gần nhất trên x đó. Để đảm bảo điều kiện này người ta phải làm sáng tỏ khái niệm thao tác ghi gần nhất tức là phải đưa ra định nghĩa về thời gian tuyệt đối. Thời gian tuyệt đối này phải bao quát tổng thể hệ thống.
+Ưu điểm: Mô hình đưa ra đảm bảo cho tính nhất quán lý tưởng, và dễ hiểu.
+Nhược điểm: Mô hình trên dựa vào khái niệm thời gian tuyệt đối cho toàn bộ hệ thống phân tán là không thể thực hiện được. Vì tất cả các quá trình đọc ghi được phân tán trên rất nhiều máy khác nhau có vị trí địa lý khác nhau mặt khác lại có sự trễ trên đường truyền…Vì vậy đây chỉ là mô hình nguyên lý không thể thực hiện với hệ phân tán thực tế.
(2)   Mô hình nhất quán tuần tự:
+ Mô hình tuần tự có điều kiện cần phải thỏa mãn như sau: “kết quả của bất kỳ sự thực thi nào cũng phải giống nhau, như thể tất cả các hành động đọc, ghi dữ liệu là của mọi tiến trình và được thực thi theo một thứ tự nào đó. Hành động đọc ghi của mỗi tiến trình riêng biệt xuất hiện trong thứ tự đó là do chương trình của chính nó quyết định.” . Có nghĩa là khi mà các tiến trình được diễn ra đồng thời trên các máy khác nhau mà có sự xen ngang của hành động đọc ghi dữ liệu thì tất cả các tiến trình đều nhìn thấy hành động đó.
+Ưu điểm: Trong điều kiện của mô hình không nhắc đến khái niệm  trước sau về thời gian tuyệt đối khắc phục được nhược điểm không thể thực thi của mô hình nhất quán chặt chẽ.
+Nhược điểm: Chính vì sự định nghĩa thứ tự của các hành động đọc ghi của mỗi tiến trình chưa có khái niệm tem thời gian nên nó không thật sự chặt chẽ, nên mô hình nhất quán này hơi yếu.
(3)   Mô hình nhất quán  tuyến tính:
+Là mô hình thỏa mãn điều kiện sau: “ kết quả của bất kỳ sự thực thi nào cũng phải giông nhau như thể tất cả các hành động đọc, ghi dữ liệu là của mọi tiến trình và được thực thi theo một thứ tự nào đó. Hành động đọc ghi của mỗi tiến trình riêng biệt xuất hiện trong thứ tự đó là do chương trình của chính nó quyết định. Đồng thời quy định nếu Tsop1(x) < Tsop2(y) (Tsop1(x): là tem thời gian của hành động ghi học đọc trên dữ liệu x) thì op1(x) sẽ đứng trước op2(y) trong thứ tự”. Trong nhất quán tuyến tính thì việc lưu trữ dữ liệu cũng phải đảm bảo tính tuyến tính tuần tự.
+Ưu điểm: Việc sử dụng tem thời gian làm cho thứ tự xếp đặt tương đối chăt chẽ, và mô hình này được đánh giá mạnh hơn mô hình nhất quán tuần tự.
+Nhược điểm: Mô hình này tính nhất quán mạnh nhưng hiệu năng hệ thống lại không cao.
(Ưu điểm nhược điểm ở đây em bịa đấy, cao thủ nào hiểu sâu fix hộ cái).

Cam kết 3 pha:
– Thêm trạng thái PRECOMMIT
:
+ Khi tiến trình điều phối nhận được thông báo VOTE_COMMIT từ tất cả các tiến trình thành viên nó sẽ phát thông báo PREPARE_COMMIT tới tất cả các thành viên.
+ Các tiến trình thành viên ở trạng thái READY, khi nhận được thông báo PREPARE_COMMIT thì đáp ứng lại thông báo READY_COMMIT tới tiến trình điều phối.
+ Khi nhận được phản hòi READY_COMMIT từ tất cả thành viên trong nhóm, tiến trình điều phối sẽ phát thông báo GLOBAL_COMMIT và bước vào trạng thái COMMIT

– Khi tiến trình điều phối ở trạng thái PRECOMMIT, nếu thời gian timeout đã hết mà còn thành viên nào đó chưa phản hồi thì nó vẫn chuyển sang trạng thái COMMIT bởi vì nó đã chắc chắn được rằng thành viên đó đã đáp ứng bằng thông điệp VOTE_COMMIT trước khi bị lỗi. Và cuối cùng thì khi tiến trình thành viên lỗi được khôi phục nó cũng bước vào trạng thái COMMIT.
– Trạng thái PRECOMMIT còn đảm bảo một tiến trình thành viên luôn quyết định được bước chuyển của nó một cách an toàn
+ Khi tham vấn thành viên Q, Q chỉ ở trạng thái INIT khi và chỉ khi không có thành viên nào khác nằm ở trạng thái PRECOMMIT.
+ Nếu tất cả các thành viên P tham vấn đều ở trạng thái READY thì giao tác bị loại bỏ.
+ Khi P là một tiến trình lỗi được khôi phục lại, nếu tồn tại tiến trình thành viên khác ơ trạng thái READY thì trạng thái của P chỉ có thể là INIT, ABORT hoặc PRECOMMIT.
+ Nếu tồn tại một thành viên ở trạng thái PRECOMMIT thì các thành viên khác khi được khôi phục lại sẽ nằm ở một trong 3 trạng thái READY, PRECOMMIT và COMMIT

*Chú ý : cam kết 3 pha chỉ được đề cập nhiều trong lý thuyết còn thực tế cam kết 2 pha vẫn được sử dụng rộng rãi hơn. Cam kết 3 pha chỉ cho thấy khả năng chịu lỗi của hệ phân tán

Leave a Reply