Trang chủ / Bảng Băm Phân Tán

Biểu Đồ Thời Gian Biểu Diễn Quá Trình Một Node Rời Khỏi Mạng


status := joinreq

sendto e.JoinReq(n)

end if end event


event n.JoinReq(d) from m

if JoinForward and m = oldpred then

sendto pred.JoinReq(d) ⊲ Join Forwarding

else if LeaveForward then

sendto succ.JoinReq(d) ⊲ Leave Forwarding

Có thể bạn quan tâm!

Xem toàn bộ 98 trang tài liệu này.

else if pred 6= nil and d (n, pred] then sendto succ.JoinReq(d)

else


if lock 6= free or pred = nil then sendto m.RetryJoin()

else


JoinForward := true lock := taken

sendto m.JoinPoint(pred) oldpred := pred

pred := m

end if end if

end event


event n.JoinPoint(p) from m status :=joining

pred := p succ := m

sendto pred.NewSucc()

end event


event n.NewSucc() from m sendto succ.NewSuccAck(m) succ := m

end event


event n.NewSuccAck(q) from m lock := free JoinForward := false sendto q.JoinDone()

end event


event n.JoinDone() from m lock := free

status := inside

end event

Thuật toán 3.1. Thuật toán join tối ưu hóa


3.3.2.3. 15BQuá trình rời mạng của một node

Cơ chế leave của một node khỏi vòng Chord được biểu diễn trong HX


ình 3.3X, giả

sử node q muốn rời khỏi mạng, node q là successor của p và predecessor của r. Quá trình leave như sau:

Khi node q muốn rời khỏi mạng, nó phải lấy lock của bản thân, nếu lock của q đang ở trạng thái taken thì q phải đợi đến khi lock chuyển sang trạng thái free. Khi lock của q ở trạng thái free, nó lấy lock và gửi thông điệp yêu cầu rời khỏi mạng đến node r. Nếu lock của r không free thì node q phải đợi, khi lock của r free, r sẽ gửi thông điệp cho phép q rời khỏi mạng. Lúc này



Hình 3 3 Biểu đồ thời gian biểu diễn quá trình một node rời khỏi mạng event 1


Hình 3.3. Biểu đồ thời gian biểu diễn quá trình một node rời khỏi mạng


event n.Leave() from app

if lock 6= free then ⊲ Application should try again later

else if succ = pred and succ = n then


else

⊲ Last node, can quit

status := leavereq lock := true

sendto succ.LeaveReq()

end if end event


event n.LeaveReq() from m

if lock = free then

lock := taken

sendto m.GrantLeave() state :=predleavereq

else if lock 6= free then

sendto m.RetryLeave()

end if end event


event n.RetryLeave() from m status := inside

lock := free ⊲ Retry leaving later

end event


event n.GrantLeave() from m LeaveForward := true status := leaving

sendto m.LeavePoint(pred)

end event


event n.LeavePoint(q) from m status :=predleaving pred := q

sendto pred.UpdateSucc()

end event


event n.UpdateSucc() from m sendto succ.UpdateSuccAck() succ := m


end event


event n.UpdateSuccAck() from m

sendto succ.LeaveDone() ⊲ Leave the system

end event


event n.LeaveDone() from m lock := free

status := inside

end event


Thuật toán 3.2. Thuật toán leave tối ưu hóa


3.3.2.4. 16BXử lý trường hợp node bị lỗi


Các hàm FixSucc, FixPred (chạy định kỳ) và cơ chế timer được sử dụng để xử lý trường hợp node bị lỗi. Periodic stabilization có hai mục đích: gộp các node mới vào vòng và xóa các node lỗi khỏi vòng.

+ Cơ chế timer

Mỗi khi lock của node i chuyển sang trạng thái busy, node khởi tạo timer. Timer sẽ tắt ngay khi lock của node chuyển sang trạng thái free. Nếu quá thời gian định trước (timeout), lock chưa chuyển sang trạng thái free, node sẽ chuyển trạng thái của lock sang free và thiết lập các biến JoinForward và LeaveForward sang false.

Nếu timeout xuất hiện tại node đang join vào mạng, có 2 trường hợp xảy ra. Nếu succ = nil, nó sẽ khởi động lại quá trình join cho đến khi nó lấy được con trỏ successor. Nếu succ ≠ nil, các lock sẽ được giải phóng và quá trình stabilization sẽ đưa node này vào vòng.

Nếu timeout xảy ra tại node đang rời khỏi mạng, node đó sẽ rời khỏi hệ thống không đưa ra thông báo.


Nếu timeout xảy ra tại successor của node đang trong quá trình gia nhập hoặc rời khỏi mạng, node sẽ thiết lập biến lock của nó sang trạng thái free và khởi tạo quá trình stabilization.

Nếu predecessor thực sự bị fail, quá trình stabilization sẽ tự động khôi phục hệ thống và các lock tương ứng được giải phóng, khi đó hệ thống sẽ trở về trạng thái đúng.

FixSucc, FixPred tương tự như các thuật toán manintenance của Chord. Hai cơ chế này đảm bảo p.succ.pred = p đối với bất kỳ node p nào.

Cơ chế FixSucc định kỳ chuyển con trỏ successor của một node tới node còn trên mạng gần nó nhất theo chiều kim đồng hồ. Nếu một node phát hiện successor của nó không còn tồn tại nữa, node sẽ thay thế successor bằng node đầu tiên f còn trên mạng trong successor list. Ngay cả khi f kông phải là successor của node này thì có chế FixSucc sẽ cập nhật con trỏ succ trỏ đến successor gần nhất.

Cơ chế FixPred định kỳ chuyển con trỏ predecessor của một node tới node gần nhất còn trên mạng theo hướng ngược chiều kim đồng hồ và thiết lập con trỏ pred thành nil nếu nó phát hiện node predecessor không còn tồn tại trên mạng nữa. Điều kiện trong thủ tục Notify được đổi lại để con trỏ pred luôn cập nhật mỗi khi nó có giá trị nil.

Successor-list tại mỗi node được duy trì định kỳ. Mỗi node định kỳ cập nhật successor-list của nó bằng cách copy successor-list của successor, đặt successor vào đầu của successor-list và chặt successor-list tới một kích thước cố định.

Thuật toán join được xửa để successor của node đang trong quá trình join vào mạng gửi successor-list cùng với thông điệp JoinPont, như vậy các node có thể khởi tạo successor list của mình.


procedure n.CheckPredecessor(p) //Locally called periodically

if IsAlive(pred) = false then

pred := nil


end if end procedure

procedure n.Stabilize() // Locally called periodically

try

p := succ.GetPredecessor()

if p=nil and p ∈ (n, succ] then

succ := p

end if

slist := succ.GetSuccList()

succlist := succ + slist //Prepend succ to slist succlist := trunc(succlist, k) //Right-truncate

//to fixed size k

succ.Notify(n)

end try catch(RemoteException)

succ := getFirstAliveNode(succlist) //Get closest alive

//node

end catch end procedure


procedure n.GetPredecessor()

return pred

end procedure


procedure n.GetSuccList()

return succlist

end procedure


procedure n.Notify(p)

if pred = nil or p ∈ (pred, n] then

pred := p

end if end procedure


Thuật toán 3.3. Quá trình stabilization định kỳ để xử lý failure


3.3.2.5. B17B ảng finger

Bảng finger được xây dựng như trong thuật toán Chord


3.3.2.6. 18BQuá trình lookup

Có thể tìm kiếm sử dụng proxy, dựa trên quá trình tìm kiếm thông thường của Chord hoặc sử dụng tìm kiếm song song (phần nhân bản)

3.4. Giải pháp caching proxy


3.4.1. Mục tiêu

Giải pháp caching proxy nhằm làm giảm độ trễ tìm kiếm và góp phần cải tiến cơ chế replication.

3.4.2. Cơ chế làm việc


3.4.2.1. 91BSơ đồ mạng overlay

Mạng peer-to-peer được chia thành hai vòng Chord, một vòng là các nút mạng thông thường, vòng kia bao gồm các proxies. Không gian ID của hai vòng giống nhau.

Các proxy được chia thành hai loại: main proxy và normal proxy:

Mỗi main proxy chịu trách nhiệm cho các normal proxy theo sau nó và main proxy đứng ngay trước nó.

Mỗi normal proxy chịu trách nhiệm cho các node có ID đứng trước ID của nó và đứng sau ID của proxy trước nó.

..... Xem trang tiếp theo?
⇦ Trang trước - Trang tiếp theo ⇨

Ngày đăng: 26/04/2022