Normal proxy
Main proxy
Normal node ring Proxy ring
Hình 3.4. Kiến trúc của giải pháp caching proxy
3.4.2.2. QB02 uá trình caching
Xét một ví dụ như sau, node A tìm kiếm dữ liệu K, dữ liệu K được lưu trên node
Có thể bạn quan tâm!
-
Đồ Thị Biểu Diễn Tỷ Lệ Tìm Kiếm Thành Công Theo Băng Thông Trung Bình Một Node Sử Dụng Của Kelisp Và Tapestry Với Rtt=1S, 10S Và Node Join/leave Với -
Ảnh Hưởng Của Tham Số “Base” Đối Với Hiệu Năng Của Tapestry (Trái) Và Tham Số “Gossip Interval” Đối Với Hiệu Năng Của Mạng Kelips Trong Mạng -
Biểu Đồ Thời Gian Biểu Diễn Quá Trình Một Node Rời Khỏi Mạng -
Đánh giá hiệu năng của một số thuật toán bảng băm phân tán DHT và đưa ra giải pháp cải tiến hiệu năng của thuật toán CHORD - 12
Xem toàn bộ 98 trang tài liệu này.
C. Node B nằm ngay trước node C. Khi nhận được yêu cầu tìm dữ liệu K từ node A, node B trả kết quả tìm kiếm là node C về cho node A và đồng thời trả kết quả (keyed, nodeid, ipaddress) này cho main proxy chịu trách nhiệm cho node C. Main proxy chuyển tiếp thông tin về node C tới normal proxy chịu trách nhiệm cho node C. Normal proxy cache lại thông tin này.
event n.CacheReq
sendto p.cache ()
end event
event p.cache from n
forwardto pi.cache()
end event
event pi.cache from p
if KeyID exists in cache then
if associated nodeid is in cache then
⊲ Ignore request
else if associated nodeid is in replication groups
then
else
⊲Add to cache
⊲Replicate associated nodeID in cache
end if
else
⊲Add to cache
end if end event.
Thuật toán 3.4. Quá trình caching
Normal proxy
Main proxy
Node A
keyid, nodeid, nodeip
nodeid, nodeip
{Add to cache}
Hình 3.5. Biểu đồ thời gian biểu diễn quá trình caching thành công
3.4.2.3. 21BQuá trình tìm kiếm
Khi một node tìm kiếm một key, nó sẽ gửi đồng thời hai request, request thứ nhất tới main proxy tương ứng, request thứ hai được gửi tới node đứng trước gần key nhất trong bảng finger như trong thuật toán Chord
Request được gửi tới main proxy sẽ được chuyển tới proxy chịu trách nhiệm cho key cần tìm. Nếu thông tin về key đó đã được cache, proxy sẽ gửi thông tin này tới node tìm kiếm và node tìm kiếm sẽ bỏ qua các thông điệp từ các quá trình tìm kiếm khác. Nếu key đó chưa được cache, proxy sẽ trả về hệ số replication của key đó. Trong trường hợp này, node có thể tìm kiếm key tại các node có ID được tính ra từ hệ số replication.
Request gửi tới node trong bảng finger sẽ được xử lý như trong thuật toán Chord.
3.4.2.4. B2Quá trình duy trì
Duy trì vòng proxy
Proxy không phải là các node Chord thông thường trên mạng, chúng là các server được dành riêng làm nhiệm vụ proxy. Các server này có tính sẵn sang cao, tần suất gia nhập, rời khỏi mạng hay lỗi của các server này thấp.
Cấu trúc overlay, quá trình duy trì (join/leave/failure) tương tự như với vòng
Chord.
Các proxy có chung danh sách main proxy.
Nếu proxy đang join vào vòng proxy là main proxy, nó sẽ thông báo với các
proxy khác cập nhật nó trong danh sách main proxy. Nếu main proxy leave khỏi mạng, nó sẽ thông báo với các proxy khác để các proxy này xóa nó khỏi danh sách main proxy. Nếu main proxy bị fail, successor và predecessor của nó sẽ thông báo với các proxy khác để cập nhật danh sách main proxy.
Nếu node đang join hoặc leave là normal proxy, nó sẽ thông báo với main proxy tương ứng để main proxy cập nhật danh sách proxy của nó. Nếu normal proxy bị fail, successor và predecessor của nó sẽ thông báo với main proxy để cập nhật danh sách proxy.
Sao lưu: một proxy sao lưu cache của nó trong k proxy liên tiếp sau nó. Khi một proxy phát hiện successor của nó bị fail, nó sẽ thay thế proxy đó bởi proxy đầu tiên còn online trong danh sách proxy của nó.
Đồng bộ giữa vòng proxy và vòng các node thông thường
Đồng bộ khi node thông thường thay đổi.
Khi một node join vào mạng, nó sẽ lấy một bản sao danh sách main proxy từ successor của nó.
Khi một node leave khỏi mạng, nó thông báo với caching proxy tương ứng với nó và gửi successor của nó tới proxy. Proxy sẽ kiểm tra xem node đang leave khỏi mạng có trong cache của nó không. Nếu node đã được cache, proxy sẽ chuyển các key mà node chịu trách nhiệm sang successor của node đó và xóa node khỏi danh sách cache.
Khi một node join vào mạng, nó sẽ gửi thông tin về successor của nó tới proxy tương ứng. Proxy sẽ kiểm tra xem successor đó đã được cache chưa. Nếu successor đã được cache, các key có ID < ID của node đang join vào mạng sẽ được chuyển tới node này.
Khi một node phát hiện successor của nó bị fail, nó sẽ thông báo với proxy tương ứng. Nếu node đã được cache trong proxy, proxy sẽ xóa node đó khỏi cache.
event n.Leave from app
sendto p.NotifyLeave()
end event
event p.NotifyLeave from n
sendto pi.NotifyLeave()
end event
event pi.NotifyLeave from p
If n is not in cache then
else
⊲Ignore leaving node
If succ(n) is in cache then
else
⊲Merge cache of n to cache of succ(n)
⊲Add succ(n) to cache
endif end event
end if
event n.Join from app
sendto p.NotifyJoin()
end event
event p.NotifyJoin from n
sendto pi.NotifyJoin()
end event
event pi. NotifyJoin from p
If succ(n) is not in cache then
⊲Ignore joining node
else
If some cached keys of succ(n) belong to n then
else
⊲Add n to cache and move keys to n
⊲Ignore joining node
end if end if
end event
event p.NotifyFailure from successor of n
sendto p.NotifyFailure()
end event
event pi.NotifyFailure from p
sendto p.NotifyFailure()
end event
event pi.NotifyFailure
if n is not in cache then
⊲Ignore failure node
else
⊲Remove n from cache (or replicate by associate node)
end if end event
Thuật toán 3.5. Đồng bộ hóa vòng proxy và vòng node Chord thông thường
Đồng bộ khi vòng proxy thay đổi
Khi một proxy join vào mạng, successor của proxy này sẽ chuyển các key tương ứng với proxy mới join vào mạng sang cho proxy này. Nếu proxy đang join vào mạng là normal proxy, nó sẽ thông báo với main proxy tương ứng cập nhật lại danh sách proxy. Nếu node đang join vào mạng là main proxy, nó sẽ thông báo với main proxy đứng trước nó để lấy về danh sách proxy list và cập nhật danh sách main proxy trong tất cả proxy. Main proxy cũng thông báo cập nhật danh sách main proxy trong các node được cache.
Khi một proxy leave khỏi hệ thống, successor của proxy đó sẽ chịu trách nhiệm cho các key được cache trong proxy đang leave. Nếu proxy đang leave là normal proxy, nó sẽ thông báo với main proxy tương ứng để cập nhật danh sách proxy. Nếu proxy đang leave là main proxy, nó sẽ chuyển danh sách proxy sang main proxy ngay sau nó và thông báo với các proxy cập nhật lại danh sách main proxy. Các proxy cũng thông báo với các node thông thường để các node này cập nhật lại danh sách main proxy.
Khi một proxy phát hiện successor của nó fail, nó sẽ thay thế proxy đó bởi proxy đầu tiên còn hoạt động trong danh sách successor của nó. Nếu proxy fail là normal proxy, successor hoạt predecessor của nó sẽ thông báo với main proxy tương ứng để main proxy này cập nhật lại proxy list. Nếu proxy bị fail là main proxy,
successor hoặc predecessor của nó sẽ thông báo với các proxy khác và các node thông thường cập nhật lại danh sách main proxy.
Để cập nhật danh sách main proxy trong các node thông thường, mỗi proxy thông báo danh sách main proxy mới cho các node mà nó đang cache. Node thông thường sẽ thông báo danh sách main proxy mới cho successor và predecessor của nó cho đến khi các node trong vòng có cùng danh sách main proxy (version giống nhau). Một node dừng việc thông báo danh sách main proxy mới cho successor và predecessor của nó khi danh sách main proxy của nó giống với danh sách main proxy nó nhận được từ successor hoặc predecessor. Quá trình cập nhật này là quá trình lan tỏa nên kết thúc rất nhanh.
Quá trình xử lý join/leave/failure của các proxy tương tự như node Chord thông thường
Giả mã xử lý thay đổi trong vòng proxy
event p.MainProxyListChanged
for node n in cache do
sendto n.NotifyMainProxyListChanged()
end for end event
event Notify MainProxyListChanged from p
If vn is less than received from proxy or predecessor then
# vn: version number of proxy list
⊲Replace its proxy list
⊲Forward proxy list to it successor and predecessor
else
⊲Ignore received proxy list
end if end event
Thuật toán 3.6. Xử lý thay đổi trong vòng proxy
3.5. Giải pháp dùng nhân bản đối xứng cải tiến
3.5.1. Mục tiêu
Nhân bản đối xứng nhằm tăng cường tính sẵn sàng của dữ liệu và tránh bottle-neck.
3.5.2. Cơ chế làm việc
Giải pháp này dựa trên cơ chế nhân bản đối xứng
3.5.2.1. 23BNhân bản đối xứng
Ý tưởng chính của nhân bản đối xứng là mỗi ID i trong hệ thống cần có liên kết với ID f khác. Nếu ID i liên kết với ID f thì node chịu trách nhiệm cho item i cũng chịu trách nhiệm cho cả item i và item j. Tương tự, node chịu trách nhiệm cho item j cũng sẽ chịu trách nhiệm cho item i.
Mỗi ID trong hệ thống liên kết với một tập f các ID khác thỏa mãn: nếu ID i liên kết với tập ID r1, ...,rf , thì ID rx, với 1 ≤ x ≤ f , cũng liên kết với các ID r1, ...,rf.
Nói cách khác, không gian ID được chia thành N/f lớp tương được sao cho ID
trong mỗi lớp này liên kết với nhau. Để đơn giản, người ta thường sử dụng các lớp với module m với m = N/f với N là kích thước của không gian ID.
Cho F = {1, ..., f }, khi đó ID i sẽ liên kết với các ID f được xác định bởi công thức r : I x F → I:
r(i, x) = i (x − 1) + N/f
3.5.2.2. 24BCơ chế nhân bản đối xứng cải tiến
Ý tưởng cải tiến ở đây là các key được tìm kiếm với tần suất khác nhau sẽ được nhân bản với hệ số nhân bản khác nhau.
Các item trong hệ thống được nhân bản ở các mức khác nhau. Mọi node trong hệ thống đều được nhân bản với hệ số cơ bản (giống nhân bản đối xứng). Các node được tìm kiếm nhiều hơn sẽ được nhân bản với hệ số bổ xung, các node này sẽ được