�ݺ�ߣ

NAMING
Định danh trong các hệ thống phân tán

Hướng dẫn nghiên cứu và thuyết trình phần Định danh
(Naming) trong DS:
1.Tầm quan trọng của định danh (Tại sao phải cần đến định
danh (để làm gì, thiếu định danh có được không)?
Những gì cần định danh? Trong hệ thống không phân tán
có cần đến định danh hay không, nếu có thì dẫn chứng
bằng ví dụ cụ thể?
2. Đã nói đến định danh thì phải đề cập đến những vấn đề
và công việc cụ thể gì?
3. Phân biệt: name, entity, access point, address, identifier

4. Bản chất của công việc định danh? Định danh trong hệ
thống phân tán khác gì với định danh trong hệ thống không
phân tán?
5. Thế nào là định danh phẳng (Flat naming)? Các kiểu
định danh phẳng đơn giản: multicast, broadcast,
forwarding pointer? Các kiểu định danh phẳng phức tạp
hơn: home-based, DHT, phân cấp (Hierarchical)? So sánh?
6. Thế nào là định danh có cấu trúc? Khái niệm Name
Space? Các cách cài đặt name space? Ví dụ minh họa:
DNS name space?
7. Thế nào là định danh dựa vào thuộc tính? Tại sao, khi
nào phải dùng loại này? Khó khăn là gì và
giải pháp ra sao?--> hệ thống LDAP

 Định danh: cách thức đặt tên, dùng để xác định một thực
thể trong hệ thống là duy nhất.
 Trong tất cả các hệ thống máy tính, tên có vai trò rất quan
trọng. Chúng được sử dụng để chia sẻ tài nguyên, xác định
thực thể duy nhất, tham chiếu đến vị trí…
 Các công việc cần thực hiện:
 Từ định danh xác định thực thể tương ứng.
 Thực thi hệ thống phân giải tên.
 Tìm kiếm thực thể đã định danh phù hợp với miêu tả
của người dùng.

Tên, Từ Định Danh, Và Địa Chỉ
Names, Identifiers, And Addresses

 Name: một chuỗi các bit hoặc ký tự được sử dụng để tham
chiếu đến một entity (thực thể).
 Entity: hầu như bất kỳ những gì có trong hệ thống ( host,
printer, file, người dùng, tiến trình…).
 Access point: điểm truy cập vào một entity, một entity có thể
có nhiều điểm truy cập.
 Address: tên của access point. Dạng đặc biệt của name: có
thể tham chiếu đến access point của entity.
 Identifier (ký hiệu nhận dạng): một name thoả mãn 3 đặc tính:
 Một identifier chỉ tham chiếu nhiều nhất đến một entity.
 Môt entity được tham chiếu nhiều nhất bởi một identifier.
 Một identifier luôn tham chiếu đến cùng một entity.

 Bản chất của công việc định danh là đặt tên để phục vụ việc
truy xuất tới các thực thể trong hệ thống máy tính.
 Sự khác biệt giữa cách định danh trong các hệ thống phân tán
và không phân tán nằm trong cách hệ thống định danh được
thực thi.
 Trong hệ thống phân tán, việc thực thi của hệ thống định
danh thường phân tán trên nhiều máy. Việc phân tán như thế
nào đóng vai trò quan trọng trong tính hiệu quả và khả năng
mở rộng của hệ thống định danh.

Định Danh Phẳng
Flat Naming

 Các ký hiệu nhận dạng (identifiers) thì thuận tiện để đại
diện duy nhất cho các thực thể (entities). Trong nhiều
trường hợp, các ký hiệu nhận dạng chỉ đơn giản là chuỗi
bit ngẫu nhiên, để thuận tiện người ta gọi đó là tên không
có cấu trúc hoặc tên phẳng.
 Một tính chất quan trọng của một tên như vậy là chúng
không chứa bất kỳ thông tin nào về cách xác định vị trí
các điểm truy cập của thực thể đã được liên kết của chúng.

Broadcasting và Multicasting
 Cả hai giải pháp này chỉ áp dụng cho mạng cục bộ (LAN).
 Cách định vị một thực thể: một tin nhắn có chứa ký hiệu
nhận dạng của thực thể được broadcast tới từng máy và
mỗi máy được yêu cầu để kiểm tra cho dù nó có hay không
có thực thể đó.
 Nguyên tắc này được sử dụng trong giao thức phân giải địa
chỉ Internet (ARP) để tìm địa chỉ liên kết dữ liệu của máy khi
chỉ có địa chỉ IP.
 Broadcasting kém hiệu quả khi mạng phát triển, Multicasting
được dùng để thay thế.

Forwarding Pointers (1)
 Một cách tiếp cận phổ biến để định vị các thực thể di động.
 Nguyên tắc rất đơn giản: khi một thực thể di chuyển từ A đến B,
nó để lại phía sau một tham chiếu đến vị trí mới của nó tại B.
 Ưu điểm: sự đơn giản.
 Nhược điểm: không có phạm vi cụ thể để thực hiện, tất cả các
vị trí trung gian trong một chuỗi sẽ phải duy trì một phần của
nó trong chuỗi Forwarding Pointer, liên kết có thể bị phá vỡ.

Hình 5-1. Nguyên lý Forwarding Pointer sử dụng cặp
(client stub, server stub)

Hình 5-2 . Chuyển hướng Forwarding Pointer bằng
cách lưu trữ một đường tắt ở client stub.

Home-Based Approaches (1)
 Giải quyết vấn đề mở rộng, tính hiệu quả trong mạng quy
mô lớn của broadcasting và forwarding pointers.
 Cơ chế dự phòng cho dịch vụ định vị dựa trên forwarding
pointers.
 Giải pháp phổ biến để hỗ trợ các thực thể di động trong các
mạng quy mô lớn là đưa ra một vị trí gốc, giúp theo dõi vị trí
hiện tại của một thực thể.

Home-Based Approaches (2)
Hình 5-3. Nguyên tắc của Mobile IP.

Distributed Hash Tables (1)
 Chord sử dụng một không gian định danh m-bit để gán lựa
chọn ngẫu nhiên cho note cũng như các khoá cho các thực
thể cụ thể. Số m-bit thường là 128 hoặc 160.
 Một thực thể với khóa k thuộc quyền hạn của các node với
ký hiệu nhận dạng nhỏ nhất id ≥ k. Node này được gọi là kế
nhiệm của k. Ký hiệu: succ(k).
 Vấn đề chính trong các hệ thống dựa trên DHT là phân giải
một cách hiệu khoá k đến địa chỉ của succ(k).

 Mỗi node Chord duy trì một finger table của hầu hết đầu vào m.
FT p [i] = succ (p + 2 i-1)
 Để tìm một khóa k, nút p sau đó sẽ ngay lập tức gửi yêu cầu
tới nút q với chỉ số j trong finger table của p:
q = FT p [j] ≤ k <FT p [j + 1]

Hình 5-4. Phân
giải khoá 26 từ
node 1 và khoá
12 từ node 28
trong một hệ
thống Chord.

Hierarchical Approaches (1)
Hình 5-5. Tổ chức phân cấp của một dịch vụ định vị thành
các miền, mỗi cái có một node thư mục liên quan.

Hình 5-6. Một ví dụ về lưu trữ thông tin của một thực thể
có hai địa chỉ trong miền lá khác nhau.

Hình 5-7. Tìm kiếm một vị trí trong một dịch vụ định vị
có cấu tạo phân cấp.

Hình 5-8. (a) Một yêu cầu thêm vào được chuyển tiếp đến
nút đầu tiên biết về thực thể E.
(b). Một chuỗi các con trỏ chuyển tiếp đến nút lá được tạo ra.

Định Danh Có Cấu Trúc
Structured Naming

 Định danh phẳng thích hợp cho máy, nhưng không thuận
tiện cho người sử dụng.
 Do đó, ra đời hệ thống định danh hỗ trợ tên có cấu trúc
được cấu tạo từ sự đơn giản, phù hợp với con người.
 Hệ thống này không chỉ hỗ trợ định danh tên file mà cả
hệ thống tên host trên Internet.

Name Spaces (1)
 Trong hệ thống định danh có cấu trúc, không gian tên được
biểu diễn bằng biểu đồ có hướng với các node và nhãn.
 Có hai loại node:
 Node lá (leaf node): biểu diễn bằng một thực thể chứa
thông tin như địa chỉ hoặc trạng thái của thực thể.
 Node thư mục (directory node): chứa bảng directory
table, trong bảng chứa các cặp (nhãn, nhận dạng node).

Name Spaces (2)
Hình 5-9. Đồ thị định danh tổng thể với duy nhất một nút gốc.

Name Spaces (3)
Hình 5-10. Cấu tạo chung của việc cài đặt hệ thống file UNIX trên
một ổ đĩa logic của khối đĩa liền kề.

Name Resolution
 Không gian tên cung cấp một cơ chế thuận tiện cho việc
lưu trữ và lấy thông tin về các đối tượng bằng tên. Tổng
quát hơn, cho một tên đường dẫn, nó có thể tìm kiếm bất
kỳ thông tin được lưu trữ trong các node được gọi bằng
cái tên đó. Quá trình này gọi là phân giải tên.

Name Resolution: Linking and Mounting(1)
Hình 5-11. Khái niệm về một liên kết ký hiệu được giải thích trong
một đồ thị định danh.

 Để gắn kết một không gian tên ngoại trong một hệ
thống phân tán cần có ít nhất các thông tin sau:
Tên của một giao thức truy cập.
Tên của server.
Tên của điểm lắp ghép trong không gian tên ngoại.

Hình 5-12. Lắp ghép các không gian tên từ xa thông qua
một giao thức truy cập cụ thể.

Name Space Distribution (1)
 Trong hệ thống phân tán, việc quản lí tên được thực hiện
bằng cách phân thành các mức:
 Globle: được hình thành bởi các node cấp cao nhất.
 Administrational: được hình thành bởi các node thư
mục gộp lại với nhau được quản lý trong một tổ chức
duy nhất.
 Managerial: chứa những node thư mục ở mức thấp,
thay đổi thường xuyên.

Hình 5-13. Một ví dụ phân vùng của không gian tên DNS, bao
gồm các file có thể truy cập Internet, với ba lớp.

Hình 5-14. So sánh giữa các tên server để thực hiện các node
từ một không gian tên quy mô lớn được phân chia thành một
lớp toàn cầu, một lớp cơ quan chủ quản, và một lớp quản lý.

Implementation of Name Resolution (1)
Hình 5-15. Nguyên tắc phân giải tên lặp đi lặp lại.

Hình 5-16. Nguyên tắc phân giải tên đệ quy.

Hình 5-17. Phân giải tên đệ quy của <nl, vu, cs, ftp>. Tên server
lưu lại kết quả trung gian để tra cứu sau này.

Example: The Domain Name System
Hình 5-18. So sánh giữa phân giải tên đệ quy và lặp đi lặp lại,
quan tâm tới chi phí truyền thông.

The DNS Name Space
Hình 5-19. Các loại quan trọng nhất của bản ghi tài nguyên
hình thành các nội dung của các node trong không gian tên DNS.

DNS Implementation (1)
Hình 5-20. Một đoạn trích từ cơ sở dữ liệu DNS cho miền
cs.vu.nl.

DNS Implementation (2)
Hình 5-20. Một đoạn trích từ cơ sở dữ liệu DNS cho miền
cs.vu.nl.

Định Danh Dựa Trên Thuộc Tính
Attribute-based Naming

 Định vị độc lập và thân thiện với con người không phải là
tiêu chí duy nhất để đặt tên cho các thực thể.
 Khi một thực thể càng có nhiều thông tin hợp lệ cho việc
tìm kiếm chúng một cách hiệu quả thì việc định danh hợp
lý cho thực thể đó càng trở nên cần thiết.
 Với cách tiếp cận này, người dùng chỉ đơn thuần cung cấp
những mô tả về những gì mà người dùng đang tìm kiếm.
 Cách mô tả phổ biến trong hệ thống phân tán là để mô tả
thuộc tính theo cặp (thuộc tính, giá trị).
=> Định danh dựa trên thuộc tính.

Directory Services
 Hệ thống đặt tên dựa trên buộc thuộc tính còn được gọi là
dịch vụ thư mục.
 Với các dịch vụ thư mục, các thực thể có một tập hợp các
thuộc tính liên quan có thể được sử dụng để tìm kiếm.
 Trong một số trường hợp, sự lựa chọn của các thuộc tính
có thể tương đối đơn giản.
 Trong hệ thống phân tán, RDF (khung mô tả tài nguyên) giúp
thống nhất cách thức mô tả nguồn tài nguyên.
 Nguyên tắc cơ bản của mô hình RDF: nguồn tài nguyên được
mô tả theo bộ 3 (subject, predicate, object).

Hierarchical Implementations: LDAP (1)
 Một phương pháp phổ biến để giải quyết các dịch vụ thư
mục phân tán là kết hợp định danh có cấu trúc với định
danh dựa trên thuộc tính.
 Nhiều hệ thống sử dụng cái này, hoặc dựa vào các giao
thức truy cập thư mục nhẹ gọi là LDAP (Lightweight
Directory Access Protocol).
 Một dịch vụ thư mục LDAP bao gồm một số lượng record
(bản ghi), mỗi record được tạo thành từ một cặp (giá trị,
thuộc tính).

Hình 5-22. Một ví dụ đơn giản của một đường dẫn thư mục
LDAP sử dụng quy ước định danh LDAP.

Hình 5-23 (a). Một phần của một cây thông tin thư mục.

Hình 5-23 (b). Hai đường dẫn thư mục có Host_Name là RDN.

Mapping to Distributed Hash Tables (1)
Hình 5-24. (a) Một mô tả chung về một tài nguyên.
(b) Biểu diễn dạng AVTree.

Mapping to Distributed Hash Tables (2)
Hình 5-25. (a) Các mô tả tài nguyên của một truy vấn.
(b) Biểu diễn dạng AVTree.

Nguyễn Tri Ni
N12DCCN122
Đỗ Minh Sang
N12DCCN129
Phạm Tân Tiến
N12DCCN138
Bùi Minh Thắng
N12DCCN133
Trần Xuân Quang
N12DCCN128
Trần Văn Tài
N12DCCN130
Đỗ Lưu Nhật
Trường
N12DCCN141
Phan Khánh Toàn
N12DCCN140
Nguyễn Huỳnh
Thanh
N12DCCN134
Lê Minh Thạnh
N12DCCN135
Nhóm 4

�ݺ�ߣ

Naming - Định danh trong các hệ thống phân tán

More Related Content

Naming - Định danh trong các hệ thống phân tán