Xem mẫu
- DISTRIBUTED SYSTEMS
Principles and Paradigms
Đỗ Minh Nam
Chapter 5
ĐỊNH DANH TRONG HỆ
PHÂN TÁN
- 5.1. Tên, định danh và địa chỉ
• Tên:
• Thực thể: Entity
• Điểm truy cập: Access point
• Thực thể và điểm truy cập: ví dụ điện
thoại đi động
• Địa chỉ: một địa chỉ chỉ là một loại đặc
biệt của tên
• Địa chỉ, điểm truy cập và thực thể
• Tên cho một thực thể
- Names, Identifiers, And Addresses
Một định danh thực sự là một tên:
Properties of a true identifier:
• An identifier refers to at most one entity.
• Each entity is referred to by at most one
identifier.
• An identifier always refers to the same
entity
- Names, Identifiers, And Addresses
Phân giải một tên
Ta có một tên; ftp.cs.vu.nl
NS(.) ~ NS(nl) ~ NS(vu.nl) ~ address ofjtp.cs.vu.nl
NS(.) ~ NS(nl) ~ NS(vu.nl) ~ address ofjtp.cs.vu.nl
- 5.2. Định danh phẳng (Flat naming)
NS(.) ~ NS(nl) ~ NS(vu.nl) ~ address ofjtp.cs.vu.nl
- Điểm trỏ chuyển tiếp (Forwarding
Pointers) (1)
Figure 5-1. nguyên tắc chuyển tiếp điểm dùng cặp (client stub,
server stub).
- Forwarding Pointers (2)
Figure 5-2. Redirecting a forwarding pointer by
storing a shortcut in a client stub.
- Forwarding Pointers (3)
Figure 5-2. Định hướng trực tiếp một forwarding pointer bởi việc
lưu trữ một lối tắt trong một client stub
- Home-Based Approaches
Figure 5-3. The principle of Mobile IP.
- Bảng băm phân tán (Distributed Hash
Table - DHT)
- Bảng băm phân tán (Distributed
Hash Table - DHT)
DHTs là cơ sở để xây dựng các hệ thống ứng dụng
phân tán như distributed file systems, peer-to-peer file
sharing và content distribution systems. Bên cạnh đó là
các hệ thống web caching, multicast, anycast, domain
name services, và instant messaging.
Các hệ thống ứng dụng sử dụng DHTs đáng chú ý có
BitTorrent, eDonkey ….
- Bảng băm phân tán (Distributed
Hash Table - DHT)
DHTs là một lớp (class) của hệ thống phân tán có cấu
trúc, cung cấp khả năng tìm kiếm (lookup) tương tự
như bảng hash:
– Là một dạng của cấu trúc bảng băm thông thường.
– Cặp (khóa - key, giá trị - value) được lưu trữ ở DHTs và bất kì node
nào cũng có thể truy vấn lấy value một cách hiệu quả thông qua
key đã cho.
– Hỗ các 3 thao tác: chèn, tìm kiếm, xoá các cặp (key, value).
- DHT: Không gian địa chỉ
Không gian địa chỉ của DHT là một tập gồm nhiều số
nguyên, vd: từ 0 … 23-1, 0 … 2160-1, v.v….
0
1
7
6 2
5 3
4
- DHT: Không gian địa chỉ
Các Node và dữ liệu (data items) được ánh xạ vào cùng m ột
không gian địa chỉ.
Sử dụng hàm băm bảo mật SHA-1 (sinh ra một số 160 bit).
Đầu vào của hàm băm
– Địa chỉ IP của một Node.
– Tên các files dữ liệu.
– Hoặc nội dung của dữ liệu.
- DHT: Không gian địa chỉ
Trong hình vẽ:
– Không gian địa chỉ: 0…65535 (216 -1)
– Được phân hoạch cho 8 Node
- DHT: Quản lý dữ liệu
Địa chỉ IP của một node được băm để xác định vị trí của
nó trong bảng băm.
– NodeID = SHA-1(Node IP Address)
Mỗi file dữ liệu được gán một số định danh (Key)
– Key = SHA-1(tên file) hoặc SHA-1(nội dung file).
– Key là giá trị duy nhất trong không gian địa chỉ.
Mỗi node quản lý một khoảng giá trị trong không gian địa
chỉ.
Dữ liệu được lưu trữ ở node và được quản lý khoá của
dữ liệu.
- DHT: Quản lý dữ liệu
Dữ liệu có thể được lưu trữ trực tiếp hoặc gián tiếp thông qua
địa chỉ IP.
(a) Lưu trữ trực tiếp (b) Lưu trữ gián tiếp
- DHT: Tìm kiếm dữ liệu
Thông điệp tìm kiếm khoá K sẽ được chuyển đi lần
lượt đến các node trong DHT cho đến khi gặp node qu ản
lý khoá K.
- DHT: Cơ chế quản lý
Một node ra nhập (join) hoặc rời bỏ (leave) hệ th ống được
quản lý như thế nào?
Node Join: 4 bước
– Step 1: liên lạc với một node tồn tại trong DHT.
– Step 2: xác định khoảng địa chỉ mà nó quản lý.
– Step 3: cập nhật lại thông tin phục vụ cho việc tìm kiếm.
– Step 4: chuyển tất cả các cặp (Key, Value) thu ộc quy ền qu ản lý t ừ
node trước về nó.
- DHT: Cơ chế quản lý
Node Leave: 2 bước
– Step 2: chuyển các cặp (Key, Value) của nó về node trước nó.
– Step 2: cập nhật lại thông tin phục vụ cho việc tìm kiếm.
nguon tai.lieu . vn
