Patent Publication Number: US-6212578-B1

Title: Method and apparatus for managing dependencies in a distributed computing environment for ensuring the safety of remote procedure calls

Description:
FIELD OF THE INVENTION 
     The present invention relates to distributed computing environments, and more specifically, to a method and apparatus for ensuring the safety of remote procedure calls in a distributed computing environment. 
     BACKGROUND OF THE INVENTION 
     In distributed computing environments where procedure calls are being made between remote sites, software compatibility problems can arise when the software at one or more of the sites is changed without a corresponding change in the software at the other sites. This typically occurs when procedures are changed and recompiled at one site but applications at other sites which depend upon those procedures are not recompiled. When this occurs, the application which depends upon the now updated procedure will often not work correctly or, under some circumstances, not at all. Throughout this application, the term “procedure” is used generically to refer to any form of software, such as units, modules, functions, subroutines or any other type of software, and is not meant to be limiting. 
     For example, consider FIG. 1 which illustrates a simple distributed environment with two remote sites, SITE 1  and SITE 2 . CALLER 1   100  is a procedure at SITE 1  which calls TARGET 1   102 , a procedure at SITE 2 . Since this is a distributed environment, CALLER 1   100  or TARGET 1   102  may change at any time without a corresponding change to the other procedure, creating software incompatibilities. For example, TARGET 1   102  may have been written to receive two integer values and CALLER 1   100  written to pass two integer values. If TARGET 1   102  is later changed to receive two character strings and then recompiled, the next time CALLER 1   100  calls TARGET 1   102 , TARGET 1   102  will most likely execute incorrectly or not at all. 
     Although the present problem has been presented in the context of software tasks running on different or remote physical sites, software incompatibilities also occur when remote procedure calls are made between different tasks running at the same site and even on the same processor. 
     Historically, several approaches have been used to manage dependencies in distributed computing environments to ensure compatibility during remote procedure calls. Four of these include (1) synchronized installation; (2) time stamps; (3) self-describing data; and (4) data type encoding. 
     The synchronized installation approach involves simultaneously installing software at all sites to ensure that all software dependencies between sites match. Typically, this is achieved through the implementation of strict software configuration management, and among the four approaches is most likely to ensure software compatibility between the sites. Moreover, synchronized installation does not adversely affect software performance since software overhead is unaffected. However, as the number of sites increases, it becomes significantly more difficult to maintain up-to-date object level compatibility between software at multiple sites. Consequently, this approach is only suited for a distributed environment with a limited number of sites. 
     The use of time stamps involves recording an actual creation time or “actual time stamp” of each top-level compilation unit and then checking that actual time stamp against an expected time stamp maintained by the calling procedure. Each time a compilation unit is compiled, the new actual creation time is stored as an actual time stamp. Similarly, each time a calling procedure is recompiled, the stored creation times for each compilation unit called are stored by the calling procedure as expected time stamps. Upon execution of a remote procedure call, the expected time stamp is then passed, usually in the parameter list, from the calling procedure to the target procedure and compared by the target procedure to the actual time stamp previously stored by the target procedure. 
     For example, referring again to FIG. 1, CALLER 1   100  maintains an expected time stamp and passes it to TARGET 1   102  each time it calls TARGET 1   102 . The expected time stamp is compared to the actual time stamp previously stored by TARGET 1   102 . If the expected time stamp passed by CALLER 1   100  does not match the actual time stamp maintained by TARGET 1   102 , the call fails and CALLER 1   100  is marked as needing to be recompiled. The next time an execution of CALLER 1   100  is attempted, CALLER 1   100  will automatically be recompiled if a compiler is available at SITE 1 . If a compiler is not available, then the execution of CALLER 1   100  will be prohibited. 
     The time stamp approach has a high probability of detecting software incompatibilities because of the very low probability that two incompatible versions of a particular compilation unit would be compiled at the exact same time. Moreover, the time stamp approach has little adverse effects on performance since the time stamp only adds a few bytes (typically 8) to each remote procedure call. 
     However, the use of time stamps has several disadvantages. First, the time stamp approach requires that a compiler be available at each site. Second, the time stamp approach is very strict and inflexible and does not readily provide for evolutionary software development. This is because any change to a compilation unit upon which a calling procedure depends, will require the recompilation of all calling procedures which depend on that particular target procedure. This is true even if the change occurred in target procedures in the compilation unit not called by the calling procedure. These problems are exacerbated as the number of sites increase, making the use of this approach frustrating and cumbersome. Consequently, as with the synchronized installation approach, the time stamp approach is only practical for distributed environments having a limited number of sites. 
     Perhaps the most widely used approach for ensuring the safety of remote procedure calls in distributing computing environments is the use of self-describing data. With this approach, additional data is included in each remote procedure call which fully describes each parameter. This data typically includes type, mode, constraints, and any other meta-data required to fully describe the parameter and ensure correctness. 
     During execution, the self describing data is compared to the target procedure data types and if either the calling procedure or the target procedure has changed, the call will only be completed if the change is compatible, or if a valid conversion can be applied by the target procedure. This inherent flexibility is particularly helpful if the change is limited in scope and relatively benign. For example, a parameter in a target procedure may have changed from an integer value to a double precision real value. Although the calling procedure continues to pass an integer, the target procedure can easily convert the integer to a double precision real and then continue executing. In addition to providing the flexibility of data conversion, the self-describing data approach does not require a compiler at each site and is well suited for distributed environments with a large number of sites. 
     However, the self-describing data approach adversely affects performance in two ways. First, the self-describing data greatly increases the amount of data being passed in each remote procedure call. Secondly, the data type information is typically interleaved with the parameters, requiring that all of the parameters be checked before compatibility can be confirmed. Consequently, a difference in the last parameter will not be detected until all of the other parameters have been checked. 
     The last approach involves encoding the data type information of the formal parameters into a number which is then included in each remote procedure call as an additional parameter. The effectiveness of this approach depends upon the encoding scheme selected and how many bytes are used for the encoding. The encoding approach does not add much remote procedure call overhead and provides for data type conversions between compatible data types if the encoding scheme is sophisticated enough. 
     One common encoding method, “hashing”, has the disadvantage that it lacks fine-grained control, yielding only a “compatible” or “not compatible” answer when comparing the expected hash number with the actual hash number. For example, assume a hash function “Hash”, applied to a procedure “X”, with two parameters of types “A” and “B”, yields a single number “N”. Change the prototype of “X” to have types “C” and “D” as its parameters. A good hash would assure with a high probability that given N=Hash (X(A,B)) and M=Hash (X(C,D)), that N does not equal M. 
     Using this functionality, one could quickly and easily determine whether a remote call is compatible with the current state of the target. However, it would be very difficult, if not impossible, to apply type-conversions, then redetermine compatibility. 
     Finally, hashes and other encoding schemes tend to be less extensible, since it is much easier to create an efficient, correct encoding when the entire data-set to be encoded is known. Adding a new element to the data-set can invalidate the entire hash. 
     In view of the problems created by software incompatibilities and the inherent limitations in each of the solutions described above, a method of managing dependencies in a distributed computing environment to ensure the safety of remote procedure calls which is easy to maintain, allows compatible changes with a minimal impact on overhead and which works well with many sites is highly desirable. 
     SUMMARY OF THE INVENTION 
     A method and apparatus are provided for managing dependencies in a distributed computing environment to ensure the safety of remote procedure calls between a calling procedure and a target procedure. 
     According to one aspect of the invention, each remote procedure call includes both an expected time stamp and an expected signature. The expected time stamp contains the creation time of the target procedure at the time the calling procedure was last compiled. The expected signature contains data type and passing mode information of the target procedure formal parameters at the time the calling procedure was last compiled. 
     Upon execution, the target procedure first compares the expected time stamp from the calling procedure to the actual time stamp stored by the target procedure when it was last compiled. If they match, then the target procedure has not been recompiled since the calling procedure was last compiled and execution of the target procedure continues normally. On the other hand, if the time stamps do not match, then the target procedure has been recompiled since the last time the calling procedure was last compiled and may have actually been changed. Therefore, the target procedure compares the expected signature to an actual signature stored by the target procedure. If the signatures match, then although the target procedure was recompiled, no change was made to the data types or parameter passing mode (in, out, in/out) of the formal parameters and execution of the target procedure continues normally. Otherwise, if the signatures do not match, then the target procedure determines whether a data type conversion can be applied to the incompatible formal parameters to convert them to the type required by the target procedure. If a data type conversion can be successfully applied, then it is applied and execution of the target procedure continues normally. However, if a data type conversion cannot be successfully applied, then execution of the target procedure is halted. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The present invention is illustrated by way of example, and not by way of limitation, in the figures of the accompanying drawings and in which like reference numerals refer to similar elements and in which: 
     FIG. 1 is a block diagram illustrating a conventional distributed computing environment; 
     FIG. 2 is a block diagram of a computer system on which the present invention may be implemented; 
     FIG. 3 illustrates the contents of a remote procedure call according to an embodiment of the present invention; 
     FIG. 4A illustrates the expected signature of the contents of the remote procedure call illustrated in FIG. 3; 
     FIG. 4B illustrates one of the parameter descriptors illustrated in FIG. 4A; 
     FIG. 4C illustrates an example of the expected signature illustrated in FIG. 4A; and 
     FIG. 5 is a flow chart illustrating a method for managing dependencies in a distributed computing environment to ensure the safety of remote procedure calls according to an embodiment of the present invention. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
     A method and apparatus for managing dependencies in a distributed computing environment to ensure the safety of remote procedure calls is described. In the following description, for the purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the present invention. It will be apparent, however, to a person of ordinary skill in the art that the present invention may be practiced without these specific details. In other instances, well-known structures and devices are illustrated shown in block diagram form in order to avoid unnecessarily obscuring the present invention. 
     Hardware Overview 
     FIG. 2 illustrates a block diagram of a computer system  200  upon which an embodiment of the present invention may be implemented. Computer system  200  includes a bus  201  or other communication mechanism for communicating information, and a processor  202  coupled with bus  201  for processing information. Computer system  200  further comprises a random access memory (RAM) or other dynamic storage device  204  (referred to as main memory), coupled to bus  201  for storing information and instructions to be executed by processor  202 . Main memory  204  also may be used for storing temporary variables or other intermediate information during execution of instructions by processor  202 . Computer system  200  also includes a read only memory (ROM) and/or other static storage device  206  coupled to bus  201  for storing static information and instructions for processor  202 . A data storage device  207 , such as a magnetic disk or optical disk, is coupled to bus  201  for storing information and instructions. 
     Computer system  200  may also be coupled via bus  201  to a display device  221 , such as a cathode ray tube (CRT), for displaying information to a computer user. An alphanumeric input device  222 , including alphanumeric and other keys, is typically coupled to bus  201  for communicating information and command selections to processor  202 . Another type of user input device is cursor control  223 , such as a mouse, a trackball, or cursor direction keys for communicating direction information and command selections to processor  202  and for controlling cursor movement on display  221 . This input device typically has two degrees of freedom in two axes, a first axis (e.g., x) and a second axis (e.g., y), which allows the device to specify positions in a plane. 
     Alternatively, other input devices such as a stylus or pen may be used to interact with the display. A displayed object on a computer screen may be selected by using a stylus or pen to touch the displayed object. The computer detects the selection by implementing a touch sensitive screen. Similarly, a light pen and a light sensitive screen may be used for selecting a displayed object. Such devices may thus detect selection position and the selection as a single operation instead of the “point and click,” as in a system incorporating a mouse or trackball. Stylus and pen based input devices as well as touch and light sensitive screens are well known in the art. Such a system may also lack a keyboard such as  222  wherein all interface is provided via the stylus as a writing instrument (like a pen) and the written text is interpreted using optical character recognition (OCR) techniques. 
     The present invention is related to the use of computer system  200  to manage dependencies in a distributed environment to ensure compatibility during remote procedure calls. According to one embodiment, the management of dependencies is performed by computer system  200  in response to processor  202  executing sequences of instructions contained in memory  204 . Such instructions may be read into memory  204  from another computer-readable medium, such as data storage device. Execution of the sequences of instructions contained in memory  204  causes processor  202  to perform the process steps that will be described hereafter. In alternative embodiments, hard-wired circuitry may be used in place of or in combination with software instructions to implement the present invention. Thus, the present invention is not limited to any specific combination of hardware circuitry and software. 
     Functional Overview 
     According to one embodiment of the invention, a method is provided for managing dependencies in a distributed computing environment to ensure the safety of remote procedure calls between a calling procedure and a target procedure. 
     Generally, this is accomplished by providing both an expected time stamp and an expected signature in each remote procedure call. The expected time stamp contains the creation time of the target procedure and is stored by the calling procedure each time it is compiled. The expected signature contains data type information of the target procedure formal parameters at the time the calling procedure was last compiled. 
     FIG. 3 illustrates the information included in a remote procedure call according to an embodiment of the present invention. This information includes an expected time stamp  300 , expected signature  302 , parameter 1   304 , and parameter 2   306  through parameterN  308 . As indicated by the  1 , 2  . . . N nomenclature, the remote procedure call may contain any number of parameters,  304 ,  306 ,  308 , of any type, such as integer, floating point, character strings, data structures or any other data type. 
     As illustrated in FIG. 4A, to fully describe the data type information of the target procedure formal parameters, the expected signature  302  includes several fields. The first field is a signature version number  400  which specifies the signature version being used so that different software throughout the distributed environment may properly decode the signature information. The second field is the signature length  402  which designates the length of the expected signature. 
     Following the signature length  402  is the number of parameter descriptors  404  included in the expected signature  302 . Immediately following this field are the actual parameter descriptors including parameter descriptor  1   406  and parameter descriptor  2   408  through parameter descriptor N  410 . Each of the parameter descriptors  406 ,  408 ,  410  corresponds to one of the call parameters  304 ,  306 ,  308  (FIG. 3) contained in the remote procedure call. However, any number of parameter descriptors may be provided depending upon the number and data types of the parameters passed in the remote procedure call. For example, an index table may have two parameter descriptors. The first parameter descriptor may define the index table itself, while the second parameter descriptor may define the individual index table elements. 
     As illustrated in FIG. 4B, each of the parameter descriptors  406 ,  408 ,  410  includes a data type field  412 , an extra information field  414  and a parameter mode field  416 . The data type field  412  indicates the data type such as integer, floating point, character or other data structure of the parameter that corresponds to the parameter descriptor. The extra information field  414  stores any additional information about the parameter that corresponds to the parameter descriptor. Finally, the parameter mode field  416  indicates whether the parameter is used locally in the target procedure, returned to the calling procedure, or both. 
     In one particular embodiment of the present invention, the data type field  412  is an eight bit integer, the extra information field  414  is comprised of 20 bits of data and the parameter mode field  416  is comprised of four bits of data. However, the number of bits allocated to each field may vary depending on the particular application, without departing from the scope of the present invention. 
     Referring back to FIG. 4A, the expected signature  308  also provides information for any formal parameters which are data structures. Specifically, the expected signature  308  includes a number of data structure descriptors  418  followed by data structure descriptor  1   420 , data structure descriptor  2   422  through data structure descriptor N  424 . These fields contain information on any data structures included in the remote procedure call. 
     Turning now to FIG. 4C which illustrates an example of a signature for a target procedure defined by the pseudo code statement “procedure TARGET 1  (p 1  IN binary_integer, p 2  IN OUT char)”. Target procedure TARGET 1  is expecting to receive two parameters from a calling procedure. These include P 1 , an input binary integer and P 2 , an input/output character. The table provides an example of how this information is represented in a signature according to one particular embodiment of the present invention. Of course, other encoding schemes may be used depending upon the specific application. 
     The unique approach to ensuring the safety of remote procedure calls in a distributed computing environment according to an embodiment of the present invention includes two levels of dependency checking for providing tight dependency checking or looser dependency checking. A user selectable dependency switch indicates whether tight dependency checking is to be applied using time stamps or whether a looser level of dependency checking is to be applied using signatures. The dependency switch may be implemented in hardware, firmware, software or any combination thereof. The operation of the dependency switch is described in more detail below. 
     FIG. 5 illustrates a flow chart of the steps performed to manage dependencies in a distributed computing environment to ensure the safety of remote procedure calls according to an embodiment of the present invention. After entering in step  500 , in step  502  the execution of a calling procedure, CALLER 1  is initiated at SITE 1  and a remote procedure call is made to a target procedure TARGET 1  at SITE 2 . The remote procedure call includes an expected time stamp, stored by CALLER 1 , which contains the creation time of TARGET 1  at the time CALLER 1  was last compiled. The remote procedure call also includes an expected signature, stored by CALLER 1 , which contains data type and passing mode information of the formal parameters for TARGET 1  at the time CALLER 1  was last compiled. 
     In step  504  TARGET 1  begins execution at SITE 2  in response to the remote procedure call from CALLER 1 . In step  506  the expected time stamp from CALLER 1  is compared to the actual time stamp stored by TARGET 1 . If the expected time stamp matches the actual time stamp, then TARGET 1  has not been recompiled since CALLER 1  was last recompiled and the execution of TARGET 1  continues in step  508 . If, on the other hand, in step  506  the expected time stamp does not match the actual time stamp stored by TARGET 1 , then TARGET 1  has been recompiled since CALLER 1  was last recompiled and a dependency switch setting is read in step  510 . 
     In step  512  the dependency switch setting is evaluated to determine whether it is set to time stamp or signature checking. If the dependency switch is set to time stamp checking then execution of both TARGET 1  and CALLER 1  is halted in step  514  and in step  516  CALLER 1  is marked as needing to be recompiled. Processing of the remote procedure call is then completed in step  524 . 
     If, on the other hand, in step  512  the dependency switch is set to signature checking, then in step  518  the expected signature sent by CALLER 1  is compared to the actual signature stored by TARGET 1 . If the signatures match, then even though TARGET 1  has been recompiled since CALLER 1  was last recompiled, the data types and passing modes of the formal parameters of CALLER 1  and TARGET 1  are still compatible and execution of TARGET 1  continues normally in step  508 . If, on the other hand, in step  518 , it is determined that the expected signature sent by CALLER 1  does not match the actual signature stored by TARGET 1 , then in step  520  TARGET 1  compares the data types and passing modes of the parameters passed from CALLER 1  to the data types and passing modes expected by TARGET 1  to determine whether the data received can be converted to the correct type. If the data can be successfully converted, then the data is converted in step  522  and the execution of TARGET 1  continues normally in step  508 . For example, if CALLER 1  sends an integer value and for that particular parameter TARGET 1  expects a double precision value, then the data type conversion from integer to double precision value would be successful. If, on the other hand, in step  520  the data type conversion is not possible, then the execution of TARGET 1  and CALLER 1  is halted in step  514  followed by the marking of CALLER 1  as needing to be recompiled in step  516 . Processing of the remote procedure call is then completed in step  524 . 
     The method and apparatus for managing dependencies in a distributed computing environment to ensure the safety of remote procedure calls according to the present invention has significant advantages over the prior solutions. First, the present method guarantees the safety of remote procedure calls through the use of time stamp and signature matching. In addition, the adverse effects on performance are minimal because of the relatively small amount of additional overhead added to each remote procedure call to include the time stamp and signature information. Moreover, the compatibility checks are performed before any of the parameters are processed. This is particularly useful if the time stamps match exactly or if signature checking is selected and the signatures match exactly. On the other hand, the signature checking option allows data type conversions to be attempted and applied if successful. This becomes particularly important when a site does not have a compiler and the change made to the target procedure is a benign change, such as a change in comment statement or an internal statement to the procedure which does not effect the parameter protocol. 
     The approach described herein also provides significant advantages in the area of maintainability over prior solutions. Specifically, since the signature field may be left blank, the remote procedure calls remain compatible with older target procedures which just use time stamp checking. Similarly, if an older calling procedure does not provide the signature, the target procedure simply shift protocols and require that the time stamps match. Finally, the remote procedure call protocol is somewhat divorced from the meta-data. Specifically, if the semantics of the given type change, the remote procedure call protocol does not have to change. Rather, only the signature changes. 
     Although the present invention has been illustrated in the context of software running at different physical sites, the solution provided by the approach described herein is equally effective for different software tasks running at the same site. 
     In the foregoing specification, the invention has been described with reference to specific embodiments thereof. It will, however, be evident that various modifications and changes may be made thereto without departing from the broader spirit and scope of the invention. The specification and drawings are, accordingly, to be regarded in an illustrative rather than a restrictive sense.