Các vấn đề cơ bản môn Các hệ thống phân tán và ứng dụng | Trường Đại học Bách Khoa Hà Nội

Hệ thống Phân tán Distributed Systems lOMoAR cPSD| 59421307 II. Các vấn ề cơ bản
Downloaded by Quoc Khai (quockhai36@gmail.com) lOMoAR cPSD| 59421307 1. Giới thiệu
Trong hệ phân tán, hay áp dụng
Phân tán dữ liệu ở nhiều nút
Nhân bản - quản lý các bản sao của dữ liệu (trên nhiều nút/máy tính)
Tại sao nhân bản dữ liệu
Nhân bản dữ liệu đem lại nhiều ưu điểm cho hệ phân tán. Một số động lực: cải thiện hiệu năng
Downloaded by Quoc Khai (quockhai36@gmail.com) lOMoAR cPSD| 59421307
tính sẵn sàng p - xác suất 1 nút gặp sự cố => n nút: tính sẵn sàng 1-p^n chịu lỗi fault tolerance
Downloaded by Quoc Khai (quockhai36@gmail.com) lOMoAR cPSD| 59421307 1. Giới thiệu Mô hình hệ thống
Client: yc dịch vụ, dữ liệu Front-end (FE): giao tiếp
• tiếp nhận yc và trả kết quả
• giao tiếp với server/replica => client kh cần biết bên trong phía server - đảm bảo tính trong suốt Server:
• phân hệ quản lý nhân bản Replica manager (RM)
• giả định replica manager duy trì bản sao có thể phục hồi (đảm bảo tính toàn vẹn) và
đầy đủ dữ liệu/đối tượng lOMoAR cPSD| 59421307
1. Nhân bản và nhất quán - Giới thiệu
Có thể phân thành 5 bước xử lý 1 yc
0/ client gửi yc => tới font end
1/ FE gửi yc tới 1 hay nhiều RM + có thể
giao tiếp với 1 RM => đến lượt RM giao
tiếp với các RM khác + có thể gửi
thông điệp multicast tới nhiều RM
2/ Điều phối: RM chuẩn bị xử lý yêu cầu đảm bảo toàn vẹn xem
xét xử lý hay từ chối phục vụ yc
xem xét thứ tự yc so với các yc khác (FIFO, nhân quả-causal ordering, total ordering)
3/ Xử lý yc, đảm bảo khả năng kết thúc commit hoặc hủy abort
4/ Đồng thuận: đồng thuận về ảnh hưởng-kết quả của yc
5/ Trả kết quả: trả kết quả cho FE để trả lại client lOMoAR cPSD| 59421307
2. Nhất quán lấy dữ liệu làm trung tâm
Nhất quán lấy dữ liệu làm trung tâm
kho dữ liệu: có thể đc lưu phân tán
tiến trình truy cập kho dữ liệu, đọc và ghi
khi đọc => mong muốn nhận đc giá trị phản ánh tác vụ ghi cuối cùng trên obj đó
mô hình nhất quán: thỏa thuận giữa tiến trình và kho
nếu tuân thủ các quy tắc => kho dữ liệu sẽ làm việc đúng lOMoAR cPSD| 59421307 2. Nhất quán
Nhất quán theo thứ tự thao tác biến x:
• Wi(x)a - tiến trình pi ghi giá trị a vào biến x
• Ri(x)b - tiến trình pi đọc x nhận được giá trị b 1. Nhất quán chặt lOMoAR cPSD| 59421307
Đọc x nhận được giá trị tương ứng giá trị tác vụ ghi gần nhất
Sử dụng thời gian tuyệt đối thống nhất trên toàn hệ thống => để xác định tác vụ ghi gần nhất => khó đáp ứng 2. Nhất quán
Nhất quán theo thứ tự thao tác biến x:
• Wi(x)a - tiến trình pi ghi giá trị a vào biến x
• Ri(x)b - tiến trình pi đọc x nhận được giá trị b 2. Nhất quán tuần tự
Tác vụ ghi trên x không nhất thiết được "thấy" ngay. lOMoAR cPSD| 59421307
Nhưng nhiều tác vụ ghi (tuần tự) trên x đc thực hiện bởi các process sẽ được mọi process
"thấy" theo cùng thứ tự nào đó
bảo toàn: không bảo toàn: 2. Nhất quán
Nhất quán theo thứ tự thao tác 3. Nhất quán nhân quả lOMoAR cPSD| 59421307
Các tác vụ (ghi) có quan hệ nhân quả phải được bảo toàn - các tiến trình khác đều
"thấy" theo cùng thứ tự nhân quả. Tuy nhiên các sự kiện khác thì có thể không - các tác
vụ (ghi) của các tiến trình song song có thể được thấy theo thứ tự khác nhau bảo toàn: không bảo toàn: 2. Nhất quán
Nhất quán theo thứ tự thao tác 4. Nhất quán FIFO lOMoAR cPSD| 59421307
Chỉ yêu cầu các tác vụ (ghi) bởi 1 tiến trình - được nhìn thấy nhất quán bởi các tiến trình khác.
Nhưng tác vụ bởi các tiến trình song song - được nhìn thấy theo thứ tự tùy ý 2. Nhất quán
Nhất quán theo thứ tự thao tác
Nhất quán với dữ liệu truy cập chung - shared data
Giả định: trong vùng loại trừ - tiến trình chỉ thao tác với 1 replica Cần quan tâm các khía cạnh:
Thời điểm đảm bảo nhất quán - đồng bộ cập nhật: có entry, release lOMoAR cPSD| 59421307
Kiểm soát loại trừ , biến đồng bộ/lock
Tác vụ gốc: yêu cầu (acquire) lock, trả lại (release) lock 2. Nhất quán
Nhất quán theo thứ tự thao tác
Nhất quán với dữ liệu truy cập chung - shared data
5. Nhất quán vào (entry consistency)
Kiểm soát nhất quán có sử dụng loại trừ nhau
Thời điểm đảm bảo nhất quán - khi bắt đầu vào vùng loại trừ
Mỗi dữ liệu chia sẻ gắn với biến đồng bộ S
• S: có thông tin current owner - tiến trình nào đang độc chiếm (exclusive) S Tiến trình p: lOMoAR cPSD| 59421307
• khi bắt đầu vào vùng loại trừ: phải chiếm được S - lệnh Acq(s) - acquire
tác vụ ghi: exclusive acquired, tác vụ đọc: shared acquire
• các tác vụ xử lý, ghi - được nhất quán
• khi thực hiện xong: trả lại S - lệnh Rel(S) - release Các cập nhật được lan truyền 2. Nhất quán
Nhất quán theo thứ tự thao tác
Nhất quán với dữ liệu truy cập chung - shared data
5. Nhất quán vào (entry consistency)
Tiến trình P' muốn truy cập S => phải chờ S được giải phóng ~ tất cả các tác vụ cập nhật/ghi kết thúc lOMoAR cPSD| 59421307 2. Nhất quán
Nhất quán theo thứ tự thao tác
Nhất quán với dữ liệu truy cập chung - shared data
6. Nhất quán ra (release consistency)
Khác với nhất quán vào (mỗi đối tượng dữ liệu - acq(s) riêng), tiến trình P trước khi vào
vùng tới hạn => cần thông báo - lệnh acquire lock
và khi kết thúc => thông báo bằng lệnh release
Trước khi thực hiện bất kỳ tác vụ đọc/ghi dữ liệu chung => phải kết thúc tất cả các lệnh acquire trước đó lOMoAR cPSD| 59421307
Trước khi release: các tác vụ đọc ghi phải thực hiện xong
2. Nhất quán client làm trung tâm
Nhất quán client làm trung tâm Môi trường
thường là tác vụ đọc
không có cập nhật đồng thời
nói chung chấp nhận mức độ không nhất quán khá cao Mong muốn: lOMoAR cPSD| 59421307
eventualy consistency - nhất quán sau cùng
với từng client - luôn nhất quán
2. Nhất quán client làm trung tâm
Nhất quán sau cùng - eventualy lOMoAR cPSD| 59421307
Khi một dữ liệu có nhiều bản sao thì
yêu cầu là sau các thao tác cập nhật thì
tất cả các bản sao cuối cùng phải giống nhau
(có thể kh ngay lập tức) Cập nhật các bản sao
thực hiện ngay=> trans duration dài thực hiện sau 2. Nhất quán client làm trung tâm
Nhất quán đọc tăng dần (monotonic read) lOMoAR cPSD| 59421307
Đảm bảo nếu một tiến trình Pi thực hiện thao tác đọc trên một mục dữ liệu x thì
phải đảm bảo các thao tác đọc x sau đó (cùng bởi Pi) phải có cùng một kết quả hay kết quả mới hơn.
=> khi một máy trạm thực hiện một thao tác đọc trên một bản sao (L1) rồi tiếp theo lại đọc
trên một bản sao khác (L2) thì bản sao thứ hai kia ít nhất cũng phải được ghi giống với bản
sao đầu tiên, hoặc mới hơn L1: local copy 1 L2: local copy 2 WS: write set
2. Nhất quán client làm trung tâm
Nhất quán ghi tăng dần (monotonic write) lOMoAR cPSD| 59421307
Nếu một tiến trình Pi ghi trên một mục dữ liệu x thì phải đảm bảo tác vụ ghi này
phải kết thúc trước khi có các tác vụ ghi x sau đó (cùng bởi Pi)
=> dẫn đến: tác vụ ghi trên các bản sao của x - chỉ đc thực thi nếu dữ liệu là mới nhất -
có nghĩa các tác vụ ghi trước đó trên x phải được phản ánh ở bản sao bất kỳ
2. Nhất quán client làm trung tâm
Nhất quán đọc kết quả ghi (read your writes)
Đảm bảo tiến trình P luôn đọc đúng giá trị mới nhất của dữ liệu x (giá trị này là kết
quả của các tác vụ ghi lên x bởi chính P)