Naming - Informatik 4

Transcrição

Lehrstuhl für Informatik 4
Kommunikation und verteilte Systeme
Middleware Services
Apart from communication facilities, a “good” middleware offers services
supporting the application developer as well as the application at runtime:
• Naming, Trading
• Security
• Time, Synchronization
• Replication
• Concurrency, Transactions
• Persistency
• Licensing
• …
Naming
and enhanced concepts
What are the concepts behind such services?
→ Focus here on naming, time and synchronization, replication,
concurrency and transactions
Chapter 3: Naming
1
Why Name Services?
Basic task of Middleware:
Communication: information exchange for coordination of objects/components/…
• Resources are accessed using identifiers or references
An identifier can be stored in variables and retrieved from tables quickly
Identifier includes or can be transformed to an address for an object
• E.g. NFS file handle, CORBA remote object reference
A name is a human-readable value (usually a string) that can be resolved to an
identifier or address
• Internet domain name, file pathname, process number
• E.g. ./etc/passwd, http://www-i4.informatik.rwth-aachen.de/
• For many purposes, names are preferable to identifiers
because the binding of the named resource to a physical location can be
changed
because they are more meaningful to users
• Resource names are resolved by name services
to give identifiers and other useful attributes
how can a client or a human user find the right server object for
communication?
Name Service, Naming (e.g. DNS, GNS)
• Central concept in distributed systems
• Mapping of logical names to the address of resources (objects, files, services,
hosts, ...)
Directory Service / Discovery Service / Trading Service
(e.g. X.500, LDAP / Jini Discovery Service / CORBA Trading Service)
• Mapping of service attributes to resource addresses ('yellow page')
• The client don't need to know the resource name, only a description of its
characteristics
Chapter 3: Naming
2
Name Service
But:
Chapter 3: Naming
3
Chapter 3: Naming
4
Mappings
Name Resolution: URLs
Internet DNS (Domain Name System)
URL
Mapping of domain names to host attributes:
• IP address,
• Type of entry (host, name server, email, ...),
• Period of validity, ...
http://www-i4.informatik.rwth-aachen.de:8888/content/teaching/lectures/sub/vsSS04/
DNS lookup
Resource ID (IP number, port number, pathname)
Directory service X.500
137.226.12.8
Originally: Mapping of person names to the person's attributes:
• Email address,
• Phone number, ...
8888
content/teaching/lectures/sub/vsSS04/
ARP lookup
(Ethernet) Network address
CORBA Naming Service
• Mapping of an object name onto an object reference, like in DNS
Socket
The given address possibly is one more logical name which has to be mapped onto
a resource address, e.g. in case of an IP address
Chapter 3: Naming
file
2:60:8c:2:b0:5a
5
Web server
Chapter 3: Naming
6
Organisation of Naming Information
Name Spaces
In large systems like the Internet:
• Large number of entities to be named
• Distribution of naming information to several hosts
Structuring of naming data
Management by local organisations
Better performance by holding less data
Hierarchical structure allows sub-names without name clashes
• Naming of entities by path names to leaf nodes
Name Spaces
• Separation of edge labels by special characters like '/' or '.'
Represented by a labelled, directed graph
• Similar concept like in many file systems
• Distinction between absolute and relative path names
Leaf nodes represent a named entity (contains e.g. address)
• Very often, the graph is organised as a tree
Directory node has several outgoing, labelled edges
Root node mostly is the unique start node of the graph
Chapter 3: Naming
7
Name resolution: looking up information stored in the node identified by
a path name
Chapter 3: Naming
8
Linking and Mounting (1)
Linking and Mounting: NFS
Directory for
mount points
required information:
• name of access protocol
• name of server
• name of mounting point
mount point
mounting point
Often required: aliases
• Another name for the same entity
• Usage of symbolic links: no address is stored in the leaf node, but another path name
Merge name spaces: mounting
Chapter 3: Naming
Mounting by setting an alias into a different name space: Network File System (NFS)
9
10
NFS Architecture for UNIX Systems
Mounting in NFS
• Virtual file system (VFS) replaces local file system interface and forwards remote
file operation via RPC
• VFS hides differences between access implementations on different platforms
Chapter 3: Naming
Chapter 3: Naming
11
• Possible to mount nested directories from multiple servers
• Exported directories can include imported subdirectories
• No transparent import of such subdirectories by third party
Chapter 3: Naming
12
Alternative Approach to Merge
different Name Spaces
Name Space Distribution (1)
The name space is the core of a naming service
Operations for adding, removing and looking up names
home
Implemented by name servers
Structuring of naming
information
root node and its
children: stable nodes
Nodes that are
managed within a
single organisation:
administrative units
Host in local networks,
shared files, userdefined directories, ...:
typically frequently
changing nodes
Alternative approach for merging name spaces: Global Name Service (GNS)
• Add a new root node and add existing root nodes as children
• Problem: new root node has to maintain a mapping for old root nodes
13
Chapter 3: Naming
14
Chapter 3: Naming
Implementation of Name Resolution
(1)
Name Space Distribution (2)
Iterative name resolution
Item
Global
Administrational
Managerial
Geographical scale of network
Worldwide
Organization
Department
Total number of nodes
Few
Many
Vast numbers
Responsiveness to lookups
Seconds
Milliseconds
Immediate
Update propagation
Lazy
Immediate
Immediate
Number of replicas
Many
None or few
None
Is client-side caching applied?
Yes
Yes
Sometimes
A client's name resolver contacts a name server. This name server passes back a
reference to the next responsible name server. The resolver contacts this server, ...
A comparison between name servers for implementing nodes from a large-scale
name space partitioned into a global layer, an administrational layer, and a
managerial layer.
Chapter 3: Naming
request
15
Chapter 3: Naming
address
16
(2)
(3)
Recursive name resolution
A client's name resolver only contacts the next name server. Finding the responsible
name server and thus the address now is made by the involved name servers.
Server for
node
Should
resolve
Looks up
Passes to
child
Receives
and caches
Returns to
requester
cs
<ftp>
#<ftp>
--
--
#<ftp>
vu
<cs,ftp>
#<cs>
<ftp>
#<ftp>
#<cs>
#<cs, ftp>
nl
<vu,cs,ftp>
#<vu>
<cs,ftp>
#<cs>
#<cs,ftp>
#<vu>
#<vu,cs>
#<vu,cs,ftp>
root
<nl,vu,cs,ftp>
#<nl>
<vu,cs,ftp>
#<vu>
#<vu,cs>
#<vu,cs,ftp>
#<nl>
#<nl,vu>
#<nl,vu,cs>
#<nl,vu,cs,ftp>
Recursive name resolution of <nl, vu, cs, ftp>. Name servers cache
intermediate results for subsequent lookups (performance improvement).
Chapter 3: Naming
17
Chapter 3: Naming
(4)
DNS – Name Service for the Internet
•
•
•
•
•
A distributed naming database
Name structure reflects administrative structure of the Internet
Rapidly resolves domain names to IP addresses
exploits caching heavily
typical query time ~100 milliseconds
Scales to millions of computers
partitioned database
caching
Resilient to failure of a server
replication
Basic DNS algorithm for name resolution (domain name → IP number)
• Look for the name in the local cache
• Try a superior DNS server, which responds with:
– another recommended DNS server
– the IP address (which may not be entirely up to date)
Recursive resolution often helps to decrease communication costs
Chapter 3: Naming
18
19
Chapter 3: Naming
20
DNS Name Space
Domains and Zones
““
com
edu
““
gov
se
mil
de
Oxford
edu
rwth-aachen
cs
org
com
edu Zone
informatik
Generic
Countries
berkeley
purdue
nwu
““
The domain Name is given by the
sequence of labels, beginning with the root
of the target domain, ending with the root
of the whole tree. The labels are separated
by '.'
Chapter 3: Naming
com
hp
• Domains are divided in Zones
corp
(would be: winnie.corp.hp.com.)
21
• Less information overhead for Name Servers
•
•
Naming information are stored in the leafs in so-called Resource Records
Other functions:
get mail host for a domain
reverse resolution - get domain name from IP address
Host information - type of hardware and OS
Well-known services - a list of well-known services offered by a host
Other attributes can be included (optional)
Name tables change infrequently, but when they do, caching can result in the
delivery of stale data.
Clients are responsible for detecting this and for recovering
Its design makes changes to the structure of the name space difficult. For example:
merging previously separate domain trees under a new root
moving sub-trees to a different part of the structure
Chapter 3: Naming
22
Chapter 3: Naming
DNS Resource Records
Main function is to resolve domain names for computers, i.e. to get their IP
addresses
caches the results of previous searches until they pass their 'time to live'
Delegation
DNS – Functions
•
edu Domain
• Name Server manages a zone
winnie
•
purdue.edu Zone
berkeley.edu Zone
winnie.corp.hp.com
23
Type of
record
Associated
entity
Description
SOA
Zone
Holds information on the represented zone
A
Host
Contains an IP address of the host this node represents
MX
Domain
Refers to a mail server to handle mail addressed to this
node
SRV
Domain
Refers to a server handling a specific service
NS
Zone
Refers to a name server that implements the represented
zone
CNAME
Node
Symbolic link with the primary name of the represented
node
PTR
Host
Contains the canonical name of a host
HINFO
Host
Holds information on the host this node represents
TXT
Any kind
Contains any entity-specific information considered useful
Chapter 3: Naming
24
Name Resolution in DNS
• DNS supports iterative and recursive name resolution
Example of
Name Server
Content
• Iterative resolution is the standard technique
• Recursive resolution is needed when the client only has limited access in a
domain (security reasons)
• Iterative resolution can be made by a name server instead of the client's
name resolver:
NS2
NS2
2
2
1
client
4
NS1
client
3
1
4
NS1
5
NS3
NS3
Non-recursive
server-controlled
25
Chapter 3: Naming
reply
request
reference to gov.au
Name Server
request for address of
girigiri.gbrmpa.gov.au
Resolver
Resolver
Chapter 3: Naming
reference to gbrmpa.gov.au
Name Server
address of
A name server NS1 communicates with other name servers on behalf of a client
Chapter 3: Naming
26
Global Name Service (GNS)
Name
Name
Server
Server
Recursive
server-controlled
Name Resolution in DNS
reference to au
Name Server
3
GNS has more flexibility than DNS
““
• DNS was originally not designed for that large data volumes
“ ““ “
Name
NameServer
Server
au
au
Name
NameServer
Server
• an early research project (1985) developed solutions for the problems of resource
location, mail addresses and authentication: GNS
consideration of large name spaces
au
nz
restructuring name spaces
sg
home
gov.au
gov.au
Name
NameServer
Server
gov
edu
Problem:
scalability and performance of root
node after merging several sub-trees
gbrmpa.gov.au
gbrmpa.gov.au
Name
NameServer
Server
sa ips gbrmpa
27
Chapter 3: Naming
28
Directory and Discovery Service
•
•
X.500
Directory service: 'yellow pages' for the resources in a network
– Retrieves the set of names that satisfy a given description
– e.g. X.500, LDAP, MS Active Directory Services (DNS holds some descriptive
data, but the data is very incomplete and additionally DNS isn't organised to
search it)
Discovery service: a directory service that also:
– is automatically updated as the network configuration changes
– meets the needs of clients in spontaneous networks
– discovers services e.g. required by a client (who may be mobile) within the
current scope, for example, to find the most suitable printing service for image
files after arriving at a hotel.
– Examples of discovery services: Jini discovery service, the 'service location
protocol', the 'simple service discovery protocol', the 'secure discovery
service'.
– Automatic registration of new services and automatic connection of new
clients to the discovery service
Chapter 3: Naming
OSI X.500 - Directory Service (by ITU/ISO)
• a hierarchically-structured standard directory service designed for world-wide
use
accommodates resource descriptions in a standardised form and their
retrieval for any resource
never fully deployed, but the standard forms the basis for LDAP, the
Lightweight Directory Access Protocol, which is widely used
• Originally designed for descriptions of human beings, but can be applied to
any type of 'resource'
Lightweight Directory Access Protocol, LDAP
• X.500 uses higher OSI layers for access operations, LDAP defines a simpler
approach: direct access by using TCP/IP
• X.500 uses ASN.1 to describe resources, LDAP only needs a textual description
(ASCII)
• LDAP not depends on X.500, each directory service can be used
29
X.500 Database Entries
X.500 Directory Information Tree
Attribute
Abbr.
Value
Country
C
NL
Locality
L
Amsterdam
Organization
O
Vrije Universiteit
OrganizationalUnit
OU
Math. & Comp. Sc.
CommonName
CN
Main server
Mail_Servers
--
130.37.24.6, 192.31.231,192.31.231.66
FTP_Server
--
130.37.21.11
WWW_Server
--
30
Chapter 3: Naming
Unique names by hierarchical
structure
Globally unique name is
sequence of identifiers in
directory entry, e.g.
/C=NL/O=Vrije Universiteit/OU=Math. & Comp. Sc.
/CN=Main server
Resulting tree: Directory Information Tree
130.37.21.11
A X.500 directory entry using X.500 naming conventions.
Similar to DNS resource records
Collection of (attribute, value) pairs
Collection of all directory entries: Directory Information Base
Chapter
Globally
unique name for each entry
3: Naming
31
Attribute
Value
Country
NL
Locality
Amsterdam
Organization
Vrije Universiteit
OrganizationalUnit
Math. & Comp. Sc.
CommonName
Main server
Host_Name
star
Host_Address
192.31.231.42
Chapter 3: Naming
32
X.500 Architecture
• Implemented similar to name
services like DNS
• Provides more lookup
operations (advanced search
operations)
X.500 Search Operations
• Adding functionality to a simple name service: more lookup operations
DUA
DSA
• Facilities are given for searching an entry by its attributes
• Example: list all main servers at Vrije Universiteit:
DUA
DSA
answer=search("&(C=NL)(O=Vrije Universiteit)(OU=*)(CN=Main Server)")
DSA
• Two different components:
Directory User Agent
(DUA)
DSA
DUA
DSA
Directory Service Agent
(DSA)
DSA
• Searching generally is an expensive operation: access several leaf nodes to get
an answer, several DSAs have to be accessed
• Result: never really implemented, only LDAP as simpler version becomes a defacto standard in the Internet (e.g. Windows 2000)
• Naming information are distributed over several DSAs (like zones in DNS)
• DUAs are representing clients (like name resolver in DNS)
Chapter 3: Naming
33
Chapter 3: Naming
34
LDAP
• Developed in the 90ies at University of Michigan as a lightweight version of an
access protocol to X.500 directories
• Managed by the Internet Engineering Task Force (IETF)
• Goal: central information service for the administration of users and services in
networked environments
• Integration of information form various resources
• Concepts adopted from X.500:
Directory Information Tree
Directory Information Base
Directory service agents
Format of database entries (attribute/value pairs)
• Standardisation of entry types, e.g.:
person
user security information
IP host
…
Chapter 3: Naming
LDAP and X.500
Disadvantages of LDAP
• Less access operations than X.500
• Performance aspects: load sharing, redundant servers
Advantages of LDAP
• Communication uses the standard protocols TCP/IP
• Simpler model, easier to implement
• Encoding of information using textual description: usage of data by several
applications
Application areas for LDAP
• Information service for contact data
• User management in heterogeneous networks
• Authentication services
• Resource management
• Certification service for public key infrastructures
• …
35
Chapter 3: Naming
36
Discovery Services - Jini
Organisation of Service Descriptions
The lookup service maps interfaces indicating the functionality provided by a
service to sets of objects that implement the service
Object
Discovery services require more than search facilities:
• Discovery
– Clients in most cases find the Jini lookup services in their scope by IP
multicast/broadcast
• Multicast UDP for nearby Lookup services
• Unicast TCP for known Lookup services
• hierarchical organisation of
services by type hierarchy
• leaf nodes store service
descriptions including proxies
to access services
• Join
– Used by services to register with a Lookup Service
Printer
Store
Copier
Fax
• Lookup
– Clients and services use to request a service type from a Lookup service
• Search by type, not by name
• Closer to a directory service than to a naming service
p1
37
Chapter 3: Naming
Print
p2
Canon
HP
BJ-100
p3 BJC-70
38
Chapter 3: Naming
Discovery and Lookup
Discovery
Jini Service
Jini Service
Jini Lookup Service
Jini Lookup Service
Jini Service
Jini Service
Chapter 3: Naming
39
Chapter 3: Naming
40
Attribute
Proxy Attribute
Join
Attribute
Attribute
Proxy Code
Proxy Attribute
Jini Service
Attribute
Jini Service
Proxy Code
Jini Lookup Service
Jini Lookup Service
Jini Service
Jini Service
41
Chapter 3: Naming
42
Chapter 3: Naming
Attribute
Attribute
Proxy Attribute
Proxy Attribute
Attribute
Attribute
Attribute
Attribute
Proxy Attribute
Proxy Attribute
Attribute
Jini Service
Attribute
Jini Service
Jini Lookup Service
Jini Lookup Service
Lookup
Proxy Code
Jini Service
Jini Client
Jini Service
PDA
Chapter 3: Naming
Jini Client
PDA
43
Chapter 3: Naming
44
Naming vs. Locating Entities
Till now: resources with fixed locations (hierarchical, caching, ...)
Problem: some entity may change its location frequently
Simple solution: record aliases for the new address or the new name
Attribute
But: efficiency, re-use of old names, ...
Proxy Attribute
Attribute
Attribute
New approaches are necessary, e.g. identifiers for an resource
Proxy Attribute
Attribute
Jini Service
Entity ID
Jini Lookup Service
Proxy Code
Jini Service
Jini Client
PDA
Chapter 3: Naming
45
a) Direct, single level mapping between names and addresses
b) Two-level mapping using identifiers. Needs a location service to resolve identifiers
46
Chapter 3: Naming
Simple Solution for a Location Service
Forwarding Pointers (1)
Using Broadcast or Multicast
More popular approach
for location:
Broadcast is typically offered in LANs
Forwarding Pointers
Simple locating process: broadcast identifier and wait on a reply
Principle:
(principle used in the Internet protocol ARP [Address Resolution Protocol])
But: inefficient in large systems
• A moving entity leaves
behind a reference to
the new location
More efficient: using multicast for location
• Client follows the chain
of forwarding pointers
old location
But: you need to build up and to know the multicast group
But...
Long chains make the location process very expensive
Intermediate nodes have to store all pointers as long as needed
Broken links prohibit location
Chapter 3: Naming
47
Short chains and robust pointers are needed
Chapter 3: Naming
new location
48
Forwarding Pointers (2)
Home-Based Approaches
When an object moves it leaves behind a proxy having the new location
reference
Location is transparent for the client, request is forwarded along the chain
Object sends back its new location to the caller, the forwarding pointer is
redirected
Chapter 3: Naming
49
• Popular approach for large-scale networks: home location
• principle of Mobile IP
• But: increase in communication latency, fixed home location
Chapter 3: Naming
50
Hierarchical Approaches
Information Stored in Nodes
Extending the home-based approach to several layers
Network is divided into domains, sub-domains, ... (similar to DNS)
Leaf domains: local area network, cell in a mobile telephone network, ...
• Entities may have multiple addresses (e.g. replication)
• Higher-level node stores pointers to each location
• Scalability problem: root node has to store all information…
An entity located in domain D is represented by a location record in directory
node dir(D)
Location records on higher hierarchies point to next sub-domain directory node
Chapter 3: Naming
51
Chapter 3: Naming
52
Location Lookup
Location Update
Install a replicate in a new domain: new pointers have to be set
a) An insert request is forwarded to the first node that knows about entity E.
•
•
•
Looking up a location in a hierarchically organized location service
Client contacts directory node in its own domain
Go up hierarchy to the first directory node holding the information
Chapter 3: Naming
b) A chain of forwarding pointers to the leaf node is created.
53
Similar operation: deletion of pointers
Chapter 3: Naming
54
Pointer Caches
Invalidation of Pointer Caches
• Caching can be used to store locations of 'stable' nodes
• Location caching: inefficient lookup with each location change
• Pointer caching: Caching a reference to a directory node (dir(D)) of the lowest-level
domain in which an entity (E) will reside most of the time.
• A cache entry that needs to be invalidated because it returns a non-local address,
while such an address is available.
Chapter 3: Naming
55
Chapter 3: Naming
56
Scalability Issues
The Problem of Unreferenced Objects
• Root directory node becomes bottleneck
• Solution: placing sub-nodes of a partitioned root across the network
• Spread sub-nodes uniformly; but… new scalability problems: which node
to give responsibility???
Chapter 3: Naming
•
•
•
•
57
Problem with forwarding pointers: unreferenced object
Garbage collection for remote objects: hidden from clients and objects itself
How many proxies point to another one?
Reference graph
Chapter 3: Naming
58
Solution: Reference Counting
Reference Counting
• Simply count the references pointing to you
• Problem: unreliable communication
Process P expects to get an acknowledgement when it increases the
skeletons counter
Acknowledgement can get lost
P sends the increase message again
• Necessary to detect duplicates
Another problem: copying a remote reference to another process
a) Copying a reference to another process and incrementing the counter too late
b) Solution by using acknowledgements
Chapter 3: Naming
59
One more problem: performance problems in large-scale systems by communication
overhead
Chapter 3: Naming
60
Advanced Referencing Counting
Weighted reference counting: each object has
• Copying a reference to P2 causes P1 in transmitting half the weight
• A fixed total weight
• A partial weight, initialised with the total weight
Creating a remote reference causes transmitting half the partial weight to the
referencer
• Deleting a reference causes the remote object to subtract the weight of the
referencer from its total weight
a) The initial assignment of weights in weighted reference counting
b) Weight assignment when creating a new reference.
Chapter 3: Naming
61
• When the total weight becomes zero, there are no more references
Chapter 3: Naming
• Alternative to the use of indirections: generation reference counting
• Problem: the partial weight of the remote object can become zero. What is with
former objects which want to make a reference?
• Make use of indirections when partial weight reaches one
• When copying the reference to P2, P1 creates a local skeleton with some total
weight and the same partial weight
• Then transmitting half the partial weight to P2
Chapter 3: Naming
62
63
• Associate a generation and a copy counter with each referencing process
• Both counters are initialised with zero
• When copying a reference, the copy counter is increased; the new referencer
becomes the next generation compared to the old one
• Skeleton maintains the numbers of outstanding copies for each generation; in case
of a decrement request, the counter for the referencer's generation is decreased.
The copies of the referencer is added to the next generation. If all generation
entries are zero, there are no more references
Chapter 3: Naming
64
And much simpler...
Tracing-based Garbage Collection
How can isolated referencer groups be located?
Reference listing
Tracing all entities in a distributed system
• Skeleton keeps track of the proxies having a reference to it, i.e. it has a list of all
these proxies (reference list) instead of a counter
Removing all non-reachable entities
Scalability problems! → only consider groups
of processes
No problems with duplicated increments
Easy to keep the list consistent in case of process failures
Problem: copying a reference and deleting it too early (as in reference
counting)
Main drawback: bad scalability in case of many references
• Used in Java RMI
Chapter 3: Naming
65
Chapter 3: Naming
66
Tracing in Groups (2)
Tracing in Groups (3)
1. Marking the skeletons
If there are no more changes: deletion of soft-marked objects
• Hard mark: reachable from a root object, a hard marked proxy, or an external object
• Soft mark: only reachable from inside the group
2. Propagating marks to proxies
3. Repeating these steps till no more change is made
• reduction of objects in groups
• after that: analysis of intergroup references on higher-level groups
Chapter 3: Naming
67
Chapter 3: Naming
68
Conclusion
Different concepts:
• Naming Services for mapping of logical names to addresses
• Directory Services for searching addresses by describing the needed object
• Discovery Services as a name database in “dynamic” networks
• Location Services for supporting moving objects
• Some close relations to file systems and reference counting
What is the best concept?
For this, there is no general answer – it always depends on the application
Chapter 3: Naming
69

Naming - Informatik 4

Transcrição

Documentos relacionados

Mobile Communications

Mobile Communications

Chapter 2 - Informatik 4

Limitations of Object-Based Middleware Components

On the Way to Today`s Internet ARPANET ARPANET

Data Encryption Standard (DES) General Structure of

das institut für südasien-, tibet- und

Name of Module: Biometric Identification Credit Points (ECTS):3

Transfer and Control Protocols Standards of ITU H.261

Mangamarkt Anmeldung