ࡱ> fhe` Bjbjb "|c|c89 ~8d~,rR rd>@"d@ [_dTyb!b!4~~ ~~Naming in Distributed Systems OGSA Naming Design Team working Draftg note OGSA-Naming-02. Monday, December 13, 2004  DATE \@ "MMMM d, yyyy" December 12, 2004December 10, 2004 Contributors: Andrew Grimshaw (University of Virginia) (Edited by Hiro Kishimoto (Fujitsu) Dave Snelling (Fujitsu) Mark Morgan (University of Virginia) Andreas Savva (Fujitsu) Ravi Subramaniam (Intel) Frank Siebenlist (ANL) Takuya Mori (NEC/ANL) Bill Horn (IBM) Mike Behrens (R2AD, LLC) Alan Luniewski (IBM) ) Introduction The objective of this working note is to begin the discussion on a WS-Naming standard. To stimulate discussion, and provide background, we begin with a short section on terms and desirable properties in a classic two-level name scheme abstract names to addresses. This document serves a second purpose in providing input to the OASIS/WSRF TC with respect to requirements for the proposed Renewable References specification. It is understood Renewable References address only a subset of the full requirements set for Naming, but the requirements addressed by Renewable References may come very close, hence this full set of requirements for naming is being presented to the WSRF TC. Naming in distributed systems has a rich history and literature and the basics are very well understood. At the end of the document are references to a set of other extant naming schemes. It is important to understand those schemes because it is likely that one of these can simply be adopted. Traditional distributed systems often have a three layer naming scheme. Human names such as paths or attributes are mapped to abstract names, which are then mapped to some form of address. In this document we are not concerned with human names. Rather we are interested in the abstract name to address mapping. Terms Resource A resource is a namable entity that accepts a set of method calls specified in an IDL such as WSDL. A resource may be an instance of some class or template (itself a resource) but that this is not required. How resources come into existence is not an issue for the purposes of naming. Resources may have metadata or attributes associated with them. It is useful if resources have a set of common basic methods such as get_name, get/set attribute, and get_interface. The distinction between stateful and stateless services is irrelevant in naming schemes though it may impact the implementation of services. Abstract resource name: an abstract name should not include rely on any location, type, implementation, or number cardinality information. This ensures that the abstract name can persist across resource migration, container restart, etc. Resource identity. An identity not only uniquely identifies a resource as does a resource address, an identity may also have authentication properties that permit verification (usually via cryptographic means) of the entity. Resource Address: A resource address can be used directly to communicate with the resource using some protocol. A resource address refers to a particular communication endpoint and may include or imply the protocol to use. In this document we will assume that the address in this case is an EPR as defined in the WS-Addressing standard. Sameness. Two abstract names refer to the same resource if it is not possible to distinguish between the two resources given arbitrary and equivalent message histories. Alternatively if the semantics of the service define sameness differently the service semantics set the standard for that service. If two abstract names are aliases if the abstract names are different yet they refer to the same resource. In other words, from the outside it is not possible to tell them apart. Similarly, two different resource addresses may refer to the same resource. Resource identity. An identity not only uniquely identifies a resource as does a resource address, an identity also has authentication properties that permit verification (usually via cryptographic means) of the entity. Note that the notion of identity is orthogonal to that of naming, but is defined here for clarity. Human names. The two most frequently used examples of human names are paths such as /home/grimshawsmith/datafile, and properties (a.k.a. attributes and metadata), e.g., invoice where modification date=9-15-03 and costvalue<$45.00. Binding scheme: The mechanism that binds abstract names to resource addresses, i.e., given an abstract name the binding scheme returns a resource address that can be used to communicate with the resource. Bind time: The point at which an abstract name is bound to a resource address. Note that this can happen at many different times, e.g., at compile time, at program load time, at first use in a program, on failure of an old binding, and/or on every use. For all but the last case, on every use, we assume that the binding is may be cached somehow in the callers address spacecontext. Binding In some schemes, binding can be an expensive operation, thus there is a trade-off in bind time decisions between performance and dynamics. Name granularity: What are the named entities?This defines what the named entities are, e.g. lLarge (whole files), small (fields in a data base or member variables in a class), or somewhere in between. The granularity should be as large as possible (for effeciencyefficiency) but small enough to support desired application semantics. Motivation Distributed systems research has a rich literature. In the literature virtualization of resources and objects is a common solution to many problems. Naming is essential to the creation of virtualization. This virtualization results in a transparency. Nine of these show up again and again, and have been called the nine golden transparencies. They are used with respect to accessing a remote service or object. In all cases the intent is that the programmer/user need not know about or deal with somethingan object or entity, but can do so if they want to. The These transparencies are: Access. The mechanism used for a local call invovationinvocation is the same as for a remote callinvocation. Many have argued this is a special case on location transparency. Location. The caller need not know where the objectresource is located, California or Virginia it makes no difference. Failure. If the objectresource or service fails the caller is unaware. Somehow the requested service or function is performed, the objectresource is restarted, or whatever is needed to isolate the client from failure.. Heterogeneity. Architecture and OS boundaries are invisible. ObjectResources cannot can migrate without limitation due to system architecture or operating environment. At a bare minimum communication with objectresources on other architectures requires no explicit data coercion. Migration. The caller need not know whether an objectresource has moved since they last communicated with it. Replication. An objectresource or service's function can be provided by one or many instances without the caller being aware - the same name applies to any and all instances simultaneously. Is there one object or many objects behind the name? The caller need not know about or nor deal with coherence issues. Concurrency. Are there other concurrent users of an object? The caller need not be aware of other callers invocating operations on a given objectresource or service.of them. Scaling. An increase or decrease in the number of servers requires no change in the software. Naturally performance may vary. Behavioral. Is it live or is it Memorex? Whether an actual objectresource or a simulation of the objectresource is used is irrelevant to the caller. Similarly the existaneexistence is there an objectresource or service there at allis immaterial as or is one may be created as needed. Use Cases Several of the transparencies are non-controversial and are captured by existing Web Services best practices, e.g., behavioral, heterogeneity, and concurrency. Persistent or abstract naming are required to provide other transparencies. The following use cases highlight these issues. Migrate closer to a heavy user. Suppose that a client application is making intense use of a service or resource, and that the client and resource are widely separated, inducing a large latency. For example, an application in California reading and modifying a file in New York that other clients may need to continue to access though less intensely. One would like to be able to migrate the file resource from New York to California CA without any interruption in service. Migrate away from failing or overloaded resource. Consider a service or resource executing on a host that is heavily loaded (either the host, or perhaps the network into the site where the host is located). We would like to be able re-schedule the execution to another host without interrupting the service and without disrupting on-going interactions with this and other services and resources. Similarly, it may be known that a host is going to go down soon, either because of maintenance, or perhaps problems with the physical environment (power shortage, air conditioning failure, etc.). Once again we want to be able to migrate the service to another location without interrupting on-going interactions. Recovery from a failed resource. Consider a stateful resource that has failed (either due to underlying hardware failure, or perhaps a software failure) and needs to be restarted perhaps on a different physical resource. We want to be able to migrate the active instance to a different location or machine. (How the state management between the failed version is kept synchronized with the replicant is not the issue here. There are many well-known techniques, periodic checkpoints, message logging, etc.) Replica management and usage. Some resources may have multiple back-ends, end points that can each perform the service as well as the other. (Once again we ignore here the issue of state consistency between replicants. There are well-known techniques.) We would like to be able to dynamically select which replicant to use. For example, one replicant may be closer (in network terms) than another. Or, one may offer better QOS in some dimension (e.g., performance). Desirable properties of abstract naming and binding scheme. Required: The following are required by many Grid like use cases similar to the above. There is some expectation that all of these might be met by current proposals for Renewable References. Unique If two names are the same, they refer to the same resource. Sameness is defined by the semantics of the service that the resource provides. Further, they names should must be unique in space and time. Thus,, and therefore names cannot be reused. Comparable Given two different names it is possible to determine equality, without having to contact either the resource or some other third party. No aliases The same resource cannot have two different names. Thus, names are comparable directly. Persistent The name for a resource is valid as long as the resource exists. Location portable An abstract name can be used anywhere and will refer to the same resource from any context. Support the usual transparencies Location, migration, failure, replication, implementationand implementation. Extensible To accommodate future requirements a name naming scheme should be extensible. High-performance Nobody wants a lowLow performance naming schemes prevent scalability and usability. If the scheme is too slow, it will not be used, defeating the purpose. Dynamic binding Binding (an abstract name to an , address) is not static, i.e., it can change. The speed at which re-binding takes place is critical if it takes hours to rebind, then resource mobility is highly constrained. Scalable binding We expect the scale of future distributed systems to be very large. The binding schemes performance (e.g., bindings per second or time to bind) must scale with the system. Often this can be achieved with caching. However, caching must be balanced against the need to have dynamic bindings. Language neutral. Some naming schemes were developed specifically to support particular programming languages. Efficient/concurrentConcurrent name generation. This is an aspect of scalability. It must be possible to partition the name space, and generate names concurrently. Large name-space. You dont want to runRunning out of names is not acceptable. Desirable: Identity The name can also act as an identity. Authentication Mutual authentication between two named resources without requiring a trusted third party has advantages, particularly with respect to scalability. Comparable Given two different names it is possible to determine equality, ideally without have having to contact either the resource or some other third party. Widely adopted The usefulness of a naming scheme increases when it is widely used. Not require trust Schemes that do not require a trusted third party are, all else being equal, preferred over those that do require a trusted third party. Whom do you trust? Free. Open software license with no license feeThe Grid community expects open software license with no license fee. Human readable and printable. Often it will be necessary to print a name. Name Resolution Name resolution goes hand in hand with abstract naming schemes. The general form of a resolution function is: Resource_Address Resolve(Abstract_Name); Sometimes the resolution function returns a binding, consisting of either a 2-tuple or a 3-tuple containing . Sometimes the resolution function takes two parameters: Resource_Address Resolve(Abstract_Name name, Binding bad); the Abstract_Name as well as a bad binding, i.e., a binding that has been found to be inaccurate. This last form is particularly useful in lazy cache-coherence schemes. Naming schemes in the recent past Note that it may be possible to use an existing scheme rather than invent a whole new one. Some existing schemes, which address some or all of these requirements, include: OGSI (GSH-GSR). WS-Addressing http://www.w3.org/Submission/2004/SUBM-ws-addressing-20040810/ DNS http://www.ietf.org/rfc/rfc1034.txt?number=1034 Handle.net http://www.handle.net/ SGNP http://www.globalgridforum.org/Meetings/ggf4/bofs/SGNP%20-%20GWD-R%202002.02.05.pdf LSID WSRF and RR URI/URN/URL JXTA  In general "Human Names" will be human readable, but human names are not synonymous with "printable names." By human names we typically mean names assigned and understood by humans. This implies printable, but also assumes some semantic content within the name, which is meaningful to humans within some context.  The WSRF WS-Resource specification defines Resource normatively in the context of the Resource Access Pattern, see http://docs.oasis-open.org/wsrf/2004/09/wsrf-WS-Resources-1.2-draft-01.pdf. The above definition is consistent with this definition.  How the state management between the failed instance is kept synchronized with the replica is not the issue here. There are many well-known techniques, periodic checkpoints, message logging, etc. The important fact is that naming facilitates this process.     <CXYZstu¸頍nSI?5HhzThoHhchoHhcho4hohocHcHdhdhbdhhi&mHnHu=HhbhohocHdhdhdhhi&mHnHu%hohocHdhdhdh7k&.jhohoUcHdhdhdh7k&Hh8k&hoHh7k&ho%hohKcHdhdhdhcHhchohohhoCJaJhoCJaJZtXT$C$Eƀca$gdoocd&$a$J$C$Eƀ7k&a$gdo$a$gdo>B B SV$C$EƀzTa$gdoocd&$a$V$C$Eƀca$gdoocd&$a$  $0IW`ab¸®¸šoNDHhcho@HhchdhoB*phc*B*mHphsH@Hhch5!^hoB*phc*B*mHphsHHhchoHhchoHhThoHhzThoHhchoHhcho2HhThoh5!^cHdhdhdhc2HhzThoh5!^cHdhdhdhc %Jb{WWWWWRC$Eƀcgdoocd&FV$C$Eƀca$gdoocd&$a$  WHCAAAgdoC$gdoocd&V$C$Eƀca$gdoocd&$a$RC$Eƀcgdoocd&F  L q ~ ) F L !  ʶ|r_NI ho6 jHhTho0JU%hoh8cHdhdhdhTHhTho%hoh8cHdhdhdhT%hoh8cHdhdhdhTHhThoHhThoHhThoHhThoHhThoHhThoHhThoho%hoh5M{cHdhdhdhc zhM1ecccccGC$EƀcgdoGC$Eƀcgdogdogdo  txyz$)ghyyoeo[LyHhch'ho6HhThoHhThoHhThoHhcho%hohcHdhdhdhcHhTho%hoh8cHdhdhdhT ho6h4Aho6 h'ho jHhTho0JU h/hoHhTho%hoh8cHdhdhdhThoM]*_l-7K={q\qRqqHhcho)Hhch.5hoc*6HhchoHhchoHhchoHhchoHhchoHhcho)Hhchhoc*6%hoh8cHdhdhdhTHhThohoh4Aho6HhchoHhcho ow| 8ջճukkkccYFY%hoh8cHdhdhdhUHhUhohUfho6HhTho%hoh8cHdhdhdhTHhThoHhcho%hohcHdhdhdhchoh'ho62HhThohcHdhdhdhc%hohcHdhdhdhc.h'hoh6cHdhdhdhc8ELNVo>?@AGM#0޹ޯޯޒxndZdPHhUhoHhUhoHhUhoHhcho2HhUhoh.5cHdhdhdhcHhUho%hoh8cHdhdhdhUHhUhohYho6HhUho%hoh8cHdhdhdhUhoHhUho%hoh8cHdhdhdhU1<: !H""t#$$%'a*`,6.r.|.GC$EƀUgdogdogdogdo09LV\mqw:Bhnv5;Cg޼޼ޅ{޼ޅ{qޅ{gHhchoHhUhoHhcho%hohA/cHdhdhdhcHhcho2HhUhohA/cHdhdhdhc ho6%hoh8cHdhdhdhUHhUhohoHhUho%hoh8cHdhdhdhU"3 Z ` h !! !#!)!1!!!!賩茂茂x^xTxHhUho2HhUhohA/cHdhdhdhcHhUhoHhcho%hohA/cHdhdhdhcHhUhoHhUho%hoh8cHdhdhdhUHhcho%hohA/cHdhdhdhc ho6ho%hohXGcHdhdhdhc!""%"(","H"S"U""""""""""t#~##########$$$ޙ޳|ii_UHhUhoHhUho%hohA/cHdhdhdhc%hoh8cHdhdhdhUHhcho2HhUhohA/cHdhdhdhc%hoh8cHdhdhdhU ho6%hoh8cHdhdhdhUHhUhoho%hoh8cHdhdhdhU$!$*$+$5$8$>$F$R$^$a$o$x$|$$?%@%J%%%%f'q't''''(ҿܻҞwoeRoK hh-Sho%hoh8cHdhdhdhUHhUhohh-Sho6HhUhoHhUho%hoh8cHdhdhdhUHhUho%hohA/cHdhdhdhcho%hoh8cHdhdhdhUHhUhoHhcho2HhUhohA/cHdhdhdhc()`*a*h*i*n*p**++_,`,|,,,,`-----6.p.q.r.{.|..qgXHHhUh8hoh8ho5CJ HhUh8ho5CJ HhUho hho%hoh8cHdhdhdhUhho6%hoh8cHdhdhdhU jHhUho0JUHhUhF<ho6hF<ho6hh-Sho6hoHhUho.0/1/7/z///////00060@00003141>1111λΨ΋rh^R^hJBhCk2ho6hho6Hhcho6HhchoHhchoHhchCk2ho6HhUho%hoh8cHdhdhdhUHhUho%hoh8cHdhdhdhU%hohXGcHdhdhdhchohaZho6 h8ho<HHhUh8hoh.5cHdhdhdhc|.1/600314111b22k3O45mmhgdoGC$EƀcgdoGC$Eƀcgdo 1112@2N2`2b2l2222222222"3k3z3333333333O4_444555񧔊wd\hlho6%hoh8cHdhdhdhU%hoh8cHdhdhdhUHhUho%hoh8cHdhdhdhUHhUhoHhUho%hoh8cHdhdhdhUh! ho6%hoh8cHdhdhdhUhjho6hoHhUho$55666%77o88u994:5:CEƀUgdo 5 66#666666666666%7377777)8.8ͺͰ͟ͅ{cP;)hohicHcHdhdhUdhc%hohicHdhdhdhc.hCk2hohi6cHdhdhdhcHhUhohcho6hzho6h8ho5CJ HhUh8ho5CJ HhUho%hoh8cHdhdhdhUhohho6HhUhho6.hhoh86cHdhdhdhU.84858o8}888b9t9u9z9{9999:3:4:5::::::ʷukuaN@N@HhchoOJQJ%HhchoOJQJcHhchoHhUho%hoh8cHdhdhdhUhqjho6%hoh8cHdhdhdhUhlho6hohcho6%hohicHdhdhdhc2HhUhohicHdhdhdhc6HHhUhohicHdhdhdhc5:E:::ggPC$Eƀcgdoocd&FGC$Eƀcgdo:::;;;1;>;@;P;j;k;x;z;;;;;;;;;;ƱƧyydZPPBHhchoOJQJHhchoHhcho)Hhchhoc*6Hhchho6Hhcho)Hhchhoc*6Hhcho)HhchQhoc*6Hhcho.Hhchhoc*OJQJ.Hhchhoc*OJQJ:;;_PC$Eƀcgdoocd&FPC$Eƀcgdoocd&F;<<<3<<<>========I>>>>????Q?U?̸yh^TJT@JHhThoHhThoHhThoHhTho jHhTho0JU)h`LhomHsHb*mH sH )h`LhomHsHb*mH sH  h:hoHhUhoho&Hhchhoc*HhchoHhchoHhchoOJQJ!HhchhoOJQJ;<<<===%>I>>>>gb````````gdoPC$Eƀcgdoocd&FGC$Eƀcgdo >>>@@@ABBBBBB B B B BBC$gdooTd&F^DC$EƀTU????????@@@X@w@@@@@@@@AA¸xn]SF9HhUh8hoHhUh8hoHhUho jHhUho0JUHhThoHhTh8hoHhTh8ho6HhTh`LhomH sH b*mH sH HhThoHhTho jHhTho0JUhoHhThoHhThoHhThoHhThoAAAABBBBBB B BBjhoUho h8hoHhUh8hoHhUh8ho 1h/ =!"#$%H@H /NormalxCJ_HaJmH nHsH tHZ@Z I: Heading 1$<@&5CJ KH OJQJ\^JaJ \@\ ' Heading 2$<@& 56CJOJQJ\]^JaJDA@D Default Paragraph FontRiR  Table Normal4 l4a (k(No ListDD 8 Balloon TextCJOJQJaJ6@6 8 Footnote Text@&@@ 8Footnote ReferenceH*O 8Title page info descriptionP$ 2( Px 4 #\'*.25@9dP^CJOJPJQJ^JtH e@2 5!^HTML Preformatted; 2( Px 4 #\'*.25@9CJOJQJ^JaJ x %<;68;;6688;<  z z z z z zN4+5<cZn.;Zt %Jb{ z h M 1<:Ht!a$`&6(r(|(1)6**3+4+++b,,k-O.//000%11o22u334454E44455666777%8I888888:::;<<<<<< < < <<0@0ː0ˀ0ˈ0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@00000000@00000(0(0(0(0(0(0(0(0(0(0(0000000-(0-(0-(0-(0-(0-(0-(0-(0-(0-(0-(0-(0-(0-(0-(0-(0-(0-(0-(0-(0-(@0-(0-(0-(0-(@00,40,40,40,40,40,4006060606060606060600@Ѐ0000@0p̀0@0p0@0p0@0p0@0@Zt<ppp PL50At@  80!$(.15.8:;U?AB"&)+,-.01234579:<>AB  1|.55::;>B#%'(*/68;=?@ B$t<osRWbz{u444415>5@5P5k5x5z555555566(68<<Ztbz{07 "57^aa$$`&}&(( 0$034445566N8U88+;3;<<:::::::::::::: |,}2DĴ~v"]nw jhǐ8lGlnj^`.^`.88^8`.^`. ^`OJQJo( ^`OJQJo( 88^8`OJQJo( ^`OJQJo(hh^h`. hh^h`OJQJo( ~}| 8::<@ssss$< @UnknownAndrew GrimshawDavid SnellingHiro KishimotoGTimes New Roman5Symbol3 Arial7CourierG5  hMS Mincho-3 fgC Lucida Grande? Courier New"Ah8k&8k&ki&5.cu80f#24dt98_3qHX?<wzNaming in Distributed SystemsAndrew GrimshawDavid Snelling4          Oh+'0 $ @ L X dpx'Naming in Distributed SystemsAndrew GrimshawNormalDavid Snelling2Microsoft Word 11.1@@ƒ@x =@x =5. ՜.+,0 hp  'University of Virginiaict9 Naming in Distributed Systems Title  !"#$%&'()*+,-./0123456789:;<=>?@ABCEFGHIJKLMNOPQRSTVWXYZ[\^_`abcdgRoot Entry F1i1TableD!WordDocument"SummaryInformation(UDocumentSummaryInformation8]CompObjXObjectPool11 FMicrosoft Word DocumentNB6WWord.Document.8