Issue 3921: FT-FTF Issue: Intelligent factory selection (ft-ftf) Source: AT&T (Mr. Robert E. Gruber, ) Nature: Uncategorized Issue Severity: Summary: An FT-FTF (Fault Tolerance Finalization Task Force) Issue: GOAL: Introduce intelligent factory selection. On a single machine (perhaps an N-way multiprocessor, but even for a uniprocessor) one might want to have N factories, corresponding to N processes that will have replicas created in them. Ideally, only one replica for a given group should be started for the entire machine. Similarly, if one has several subnets, one might have factories on all machines, but ideally only one replica should be started per subnet, if appropriate factories are available. If the only factories available for a given type happen to be on the same subnet or same machine, then it should be possible to specify either that it is OK to go ahead with replicas on the same subnet or same machine or it is not OK. Alternatively, I might want all replicas to be on the same subnet, if possible, to reduce coordination costs, while still wanting a different hosts requirement. How to extend the specification to enable this feature? One proposal is to take advantage of the fact that location names are structured. While any structuring is allowed, we could declare that if you want to use an intelligent factory selection policy you must use names that capture the hierarchical nature of fault domains. E.g., for my scenario I could use names that capture subnet/host/processor distinctions: sA.h1.p1, sA.h1.p2, sA.h2.p1, sA.h2.p2, ... sA.hJ.p1, sA.hJ.p2 sB.h1.p1, sB.h1.p2, sB.h2.p1, sB.h2.p2, ... sB.hK.p1, sB.hK.p2 I believe there should be a LocationHints property for types or groups that is distinct from the issue of how many actual locations have available factories, where hints are like location names but can have wildcards. Thus, I could specify sA.*.* and sB.*.* as LocationHints for type T to indicate that I prefer replicas for type T to be started on machines on subnets sA and sB. Note that this is very different from giving a list of specific locations. (I certainly do not want to specify which processor number to use!) While the set of available factories might change frequently, the hints should be relatively stable. Assume that as factories are created at specific locations (such as a new factory F1 at location sA.h3.p1) they could be registered with a FactoryManager. This manager knows all the location names that have factories registered for a given group or object type. One algorithm to select a location, given a set of existing replica locations and possibly some location hints, is to choose a location name that matches one of the hints and has the greatest difference from the existing names, where a difference in the i'th part of a name dominates a difference in the j'th part of the name. Alternative algorithms are possible, e.g., one might prefer to keep replica groups in the same subnet but on different machines, which corresponds to a rule that says equality of the first part of the name is the primary determinant, while for positions 2 and on, use the greatest difference rule above. We could have a QoS property called FactorySelectionPolicy which is a string and have some predefined algorithms (+ algorithm names). Vendors could define additional algorithms. An alternative to having a fixed number of predefined algorithms is to introduce a means of describing a whole class of algorithms. Here is one approach. For a given part, one of 5 requirements holds: . NC : no constraint . EB : equality best, inequality allowed . ER : equality required . DB : difference best, equality allowed . DR : difference required A policy string is a sequence of <requirement> specs separated by dots ("."). Each requirement applies to the part at the given location, while the final <requirement> applies to the part at its location and all subsequent locations. E.g., the spec ER.DB.DR requires equality for part 1, prefers difference for part 2 (but not required), and requires difference for all remaining parts (3, 4, ... ). DR/ER constraints have higher priority than DB/EB constraints (all DR/ER constraints must be met). When there are optional constraints, a solution that satisfies an earlier optional constraint has priority over a solution that satisfies a later optional constraint. This is true regardless of how many optional constraints can be satisfied, e.g., satisfying the first optional constraint but not the second or third has priority over satisfying both the second and third optional constraint but not the first. The reverse ordering (favoring later optional constraints over earlier ones) can be selected by adding a less-than ("<") sign at the end of the policy string. For solutions that satisfy the same earliest (or latest in the case of "<") optional constraint, solutions that satisfy more optional constraints have priority over solutions that satisfy fewer optional constraints. This rule can be overridden by adding "MIN:" as a prefix to the policy string (indicating that the minimal number of optional constraints should be met --- i.e., at least one optional constraint should be met, if possible, but beyond this, solutions that satisfy the fewest additional optional constraints are favored). The resulting location selection policy implicitly includes a final global constraint: the locations chosen for a given group must be unique. N.B. When locations have a different number of parts, EB and DB requirement are ignored for missing part locations, while if one location has a part but another does not, this satisfies the DR requirement and fails the ER requirement. Some example selection policies: [1] NC No part is constrained. Due to the implicit global constraint, NC selects unique locations, but selection is otherwise random. [2] DR *Every* part must differ. This policy is not often used; it is more common to follow one or more DR constraints with some optional constraints or with NC, as in the next example. [3] DR.NC The first part must differ, while there are no constraints on the other parts. [4] DB A difference is best for each part, but not required for any given part. The result is a selection algorithm that attempts to find a difference in the earliest possible part. When several locations differ starting at the same earliest part, the algorithm favors selecting locations that differ in as many subsequent parts as possible. [5] MIN:DB Like DB, except when several locations differ starting at the same earliest part, the algorithm favors selecting locations that differ in as few subsequent parts as possible. [6] DB< Like DB, except the algorithm favors locations that differ in the latest possible part. [7] EB Equality is best for every part, but not required for any part. The result is a selection algorithm that attempts to find equality in the earliest possible part. When several locations are equal starting at the same earliest part, the algorithm favors selecting locations that are equal in as many subsequent parts as possible. [8] ER.DB Equality of the first part required, while differences in other parts are preferred but not required, with earlier optional differences dominating later ones. [9] EB.DB Equality of the first part is preferred, while differences in other parts are preferred but not required, with earlier optional differences dominating later ones (EB dominates DB and earlier DB differences dominate later ones). Consider the subnet.host.processor location naming scheme. + DR.NC would choose a different subnet for each replica and otherwise choose an arbitrary factory in each subnet. + EB.DB would choose the same subnet for all replicas, if possible, but if necessary would use different subnets. For locations in the same subnet, it would attempt to use different hosts and different processors, with higher priority given to using different hosts. + EB.EB.DB< would attempt to find locations that differ in the processor part but have the same host and subnet, where the processor difference has highest priority, host equality has next highest priority, and subnet equality has least priority. This would tend to cluster replicas as close together as possible, optimizing coordination cost while sacrificing some reliability. + MIN:DB< has the same effect as EB.EB.DB< : it specifies minimal DB matches (beyond 1 match) with priority given to later parts over earlier ones. MIN:DB< has the advantage that it works with locations of any length, while EB.EB.DB< is only useful for locations of length 3. Resolution: Revised Text: Actions taken: September 28, 2000: received issue Discussion: This issue was determined to be out-of-scope of the Fault Tolerant CORBA Finalization Task Force. End of Annotations:===== From: "Robert E. Gruber" To: , , "Juergen Boldt" Cc: "Robert E. Gruber" Subject: FT-FTF Issue: Intelligent factory selection Date: Thu, 28 Sep 2000 17:39:19 -0400 Message-ID: <001501c02994$8eadfe40$c216cf87@pong.research.att.com> MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Priority: 3 (Normal) X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook 8.5, Build 4.71.2173.0 Importance: Normal X-MimeOLE: Produced By Microsoft MimeOLE V4.72.3110.3 Content-Type: text/plain; charset="iso-8859-1" X-UIDL: =[(e9[&$e9bWRd9=ABe9 An FT-FTF (Fault Tolerance Finalization Task Force) Issue: GOAL: Introduce intelligent factory selection. On a single machine (perhaps an N-way multiprocessor, but even for a uniprocessor) one might want to have N factories, corresponding to N processes that will have replicas created in them. Ideally, only one replica for a given group should be started for the entire machine. Similarly, if one has several subnets, one might have factories on all machines, but ideally only one replica should be started per subnet, if appropriate factories are available. If the only factories available for a given type happen to be on the same subnet or same machine, then it should be possible to specify either that it is OK to go ahead with replicas on the same subnet or same machine or it is not OK. Alternatively, I might want all replicas to be on the same subnet, if possible, to reduce coordination costs, while still wanting a different hosts requirement. How to extend the specification to enable this feature? One proposal is to take advantage of the fact that location names are structured. While any structuring is allowed, we could declare that if you want to use an intelligent factory selection policy you must use names that capture the hierarchical nature of fault domains. E.g., for my scenario I could use names that capture subnet/host/processor distinctions: sA.h1.p1, sA.h1.p2, sA.h2.p1, sA.h2.p2, ... sA.hJ.p1, sA.hJ.p2 sB.h1.p1, sB.h1.p2, sB.h2.p1, sB.h2.p2, ... sB.hK.p1, sB.hK.p2 I believe there should be a LocationHints property for types or groups that is distinct from the issue of how many actual locations have available factories, where hints are like location names but can have wildcards. Thus, I could specify sA.*.* and sB.*.* as LocationHints for type T to indicate that I prefer replicas for type T to be started on machines on subnets sA and sB. Note that this is very different from giving a list of specific locations. (I certainly do not want to specify which processor number to use!) While the set of available factories might change frequently, the hints should be relatively stable. Assume that as factories are created at specific locations (such as a new factory F1 at location sA.h3.p1) they could be registered with a FactoryManager. This manager knows all the location names that have factories registered for a given group or object type. One algorithm to select a location, given a set of existing replica locations and possibly some location hints, is to choose a location name that matches one of the hints and has the greatest difference from the existing names, where a difference in the i'th part of a name dominates a difference in the j'th part of the name. Alternative algorithms are possible, e.g., one might prefer to keep replica groups in the same subnet but on different machines, which corresponds to a rule that says equality of the first part of the name is the primary determinant, while for positions 2 and on, use the greatest difference rule above. We could have a QoS property called FactorySelectionPolicy which is a string and have some predefined algorithms (+ algorithm names). Vendors could define additional algorithms. An alternative to having a fixed number of predefined algorithms is to introduce a means of describing a whole class of algorithms. Here is one approach. For a given part, one of 5 requirements holds: . NC : no constraint . EB : equality best, inequality allowed . ER : equality required . DB : difference best, equality allowed . DR : difference required A policy string is a sequence of specs separated by dots ("."). Each requirement applies to the part at the given location, while the final applies to the part at its location and all subsequent locations. E.g., the spec ER.DB.DR requires equality for part 1, prefers difference for part 2 (but not required), and requires difference for all remaining parts (3, 4, ... ). DR/ER constraints have higher priority than DB/EB constraints (all DR/ER constraints must be met). When there are optional constraints, a solution that satisfies an earlier optional constraint has priority over a solution that satisfies a later optional constraint. This is true regardless of how many optional constraints can be satisfied, e.g., satisfying the first optional constraint but not the second or third has priority over satisfying both the second and third optional constraint but not the first. The reverse ordering (favoring later optional constraints over earlier ones) can be selected by adding a less-than ("<") sign at the end of the policy string. For solutions that satisfy the same earliest (or latest in the case of "<") optional constraint, solutions that satisfy more optional constraints have priority over solutions that satisfy fewer optional constraints. This rule can be overridden by adding "MIN:" as a prefix to the policy string (indicating that the minimal number of optional constraints should be met --- i.e., at least one optional constraint should be met, if possible, but beyond this, solutions that satisfy the fewest additional optional constraints are favored). The resulting location selection policy implicitly includes a final global constraint: the locations chosen for a given group must be unique. N.B. When locations have a different number of parts, EB and DB requirement are ignored for missing part locations, while if one location has a part but another does not, this satisfies the DR requirement and fails the ER requirement. Some example selection policies: [1] NC No part is constrained. Due to the implicit global constraint, NC selects unique locations, but selection is otherwise random. [2] DR *Every* part must differ. This policy is not often used; it is more common to follow one or more DR constraints with some optional constraints or with NC, as in the next example. [3] DR.NC The first part must differ, while there are no constraints on the other parts. [4] DB A difference is best for each part, but not required for any given part. The result is a selection algorithm that attempts to find a difference in the earliest possible part. When several locations differ starting at the same earliest part, the algorithm favors selecting locations that differ in as many subsequent parts as possible. [5] MIN:DB Like DB, except when several locations differ starting at the same earliest part, the algorithm favors selecting locations that differ in as few subsequent parts as possible. [6] DB< Like DB, except the algorithm favors locations that differ in the latest possible part. [7] EB Equality is best for every part, but not required for any part. The result is a selection algorithm that attempts to find equality in the earliest possible part. When several locations are equal starting at the same earliest part, the algorithm favors selecting locations that are equal in as many subsequent parts as possible. [8] ER.DB Equality of the first part required, while differences in other parts are preferred but not required, with earlier optional differences dominating later ones. [9] EB.DB Equality of the first part is preferred, while differences in other parts are preferred but not required, with earlier optional differences dominating later ones (EB dominates DB and earlier DB differences dominate later ones). Consider the subnet.host.processor location naming scheme. + DR.NC would choose a different subnet for each replica and otherwise choose an arbitrary factory in each subnet. + EB.DB would choose the same subnet for all replicas, if possible, but if necessary would use different subnets. For locations in the same subnet, it would attempt to use different hosts and different processors, with higher priority given to using different hosts. + EB.EB.DB< would attempt to find locations that differ in the processor part but have the same host and subnet, where the processor difference has highest priority, host equality has next highest priority, and subnet equality has least priority. This would tend to cluster replicas as close together as possible, optimizing coordination cost while sacrificing some reliability. + MIN:DB< has the same effect as EB.EB.DB< : it specifies minimal DB matches (beyond 1 match) with priority given to later parts over earlier ones. MIN:DB< has the advantage that it works with locations of any length, while EB.EB.DB< is only useful for locations of length 3.