KR20010041295A - Leasing for failure detection - Google Patents

Abstract

A system is provided that uses leases to detect failures and perform fault recovery. In using the system, the client requests a lease from the server, using the resources managed by the server for a period of time. In response to this request, the server allows the lease and the client continues to request an update of the lease. If the client fails to update the lease, the server detects that an error has occurred in the client. Similarly, if the server does not respond to the update request, the client detects that an error has occurred in the server. As part of the lease establishment, the client and server exchange fault recovery routines that call if each has failed.

Description

LISING FOR FAILURE DETECTION}

Proper resource management is an important feature for the efficient and effective use of computers. In general, resource management involves allocating resources (ie, memory) in response to a request as well as reallocating resources at a suitable time, for example, when the requestor no longer requests them. Generally, resources include data called computational entities (ie, applications, programs, applets, etc.) running a computer.

Indeed, if an application running on a computer wants to refer to a resource, the computer must first assign or assign resources so that the application can refer to them appropriately. When an application no longer references a resource, the computer can deallocate or reclaim it for reuse. Processing can be performed in a variety of ways, such as addresses, array indexes, unique values, pointers, and the like.

Resource management is relatively simple because, in the case of a single computer, an event is likely to be determined when the application no longer references the resource or when the resource is reclaimed, such as after a power failure. Resource management for distributed systems that connect multiple computers is more difficult because applications within several different computers use the same resources.

Disruption in distributed systems can result in inappropriate and premature recovery of resources or failure to recover resources. For example, multiple applications running on different computers in a distributed system may refer to resources located on different machines. If the connection between the computer where the resource is located and an application that references such a resource is interrupted, then the computer can retrieve the resource more quickly. Optionally, the computer can keep the resource permanent, despite an extended time period during which the application failed to access the resource.

This problem led to the development of a system for managing network resources called "distributed garbage collection." The term refers to a facility provided by a language or runtime system for a distributed system that automatically manages resources used by an application or a group of applications running on different computers in a network.

In general, garbage collection makes use of the concept that resources can be freed for future use when they are no longer referenced by any part of the application. Distributed garbage collection extends this concept in the area of distributed computing where resources are recovered when no application on any computer references the resource.

Distributed garbage collection must maintain the integrity between allocated resources and references to resources. In other words, when an application running on any computer in the network continues to reference the resource, the system should not be allowed to reclaim the resource or free it. Reference-to-resource binding, referred to as "referential integrity," does not guarantee that access to the resource referenced by this reference is always allowed. For example, network equipment may disable such access. However, integrity ensures that if a reference accesses any resource, the reference will be the same resource that was provided first.

Distributed systems using garbage collection must also reclaim resources that are no longer referenced at some point in the infinite future. In other words, the system should provide a guarantee of "memory leak." Memory leaks can occur when all applications give up references to resources, but the system does not reclaim resources for reuse, for example because of inaccurate determination that some applications still reference resources.

Referential integrity failures and memory leaks are often due to short circuits between applications that reference resources and garbage collection systems that manage the allocation and retrieval of such resources. For example, a short circuit in the network connection between an application referencing a resource and a garbage collection system managing this resource prevents the garbage collection system from determining when and whether resources should be reclaimed. Optionally, the garbage collection system may erroneously determine that an application could collect this resource because the application did not have access to the resource within the predetermined time. Many techniques are being used to improve distributed garbage collection mechanisms by attempting to ensure that such mechanisms maintain referential integrity without memory leaks. One prior art method is to use a form of reference counting, where counts are maintained for many applications that reference each resource. When the resource count reaches zero, the garbage collection system can retrieve the resource. This reference counting scheme is valid if the resource is generated as a corresponding resource counter. In this case, the garbage collection system increments the reference count of the resource as the secondary application references the resource and decreases the count when the application no longer references the resource.

However, reference counting is problematic because of the failures that can occur, particularly in distributed systems. Such failures may take the form of computer or application failures or network failures that prevent the delivery of a message that informs the garbage collection system that resources are no longer referenced. If the message is not delivered due to a network short circuit, the garbage collection system does not know when to reclaim the resource.

To prevent such a failure, some prior art reference counting schemes include a "keep-alive" message, also known as a "ping back." According to this scheme, an application in the network sends a message to the garbage collection system that manages the resource, indicating that the application can still communicate. Such messages prevent the garbage collection system from stopping references to resources. Not receiving such a "keep-alive" message indicates that the garbage collection system decrements the reference count for the resource, and therefore, when the count reaches zero, the garbage collection system can reclaim the resource. However, this may result in premature reclamation of resources along a reference count that reaches zero, due to a failure of the "keep-alive" message reception due to network failure. This violates the referential integrity condition.

Another way to solve the referential integrity problem in the garbage collection system is to not only maintain a reference count, but also maintain an identifier corresponding to each operation entity referencing a resource. See, for example, "Distributed Garbage Collection for Network Objects" (No. 116, digital systems research center, December 15, 1993) by A. Birrell et al. This method has the same problem as the reference counting scheme. In addition, this method requires the addition of a unique identifier for each computational entity that references each resource, so that communication and storage conditions within the distributed system (ie, an identifier that corresponds to an application that references each resource). This leads to the overhead of unnecessarily increasing the list).

The present invention relates generally to data processing systems and, more particularly, to leasing for failure detection and recovery in data processing systems.

The accompanying drawings, which are incorporated in and constitute a part of this specification, illustrate embodiments of the invention in conjunction with the description, and serve to explain the advantages and principles of the invention.

1 is a flow chart of the steps performed by an application call processor in accordance with an embodiment of the present invention.

2 is a flow chart of the steps performed by a server call processor that handles a dirty call in accordance with an embodiment of the invention.

3 is a flow chart of steps performed by a server call processor that handles a clean call in accordance with an embodiment of the invention.

4 is a flowchart of steps performed by a server call processor for initializing a garbage collection process in accordance with an embodiment of the present invention.

5 is a preferred flow diagram of a call within a distributed processing system.

6 is a block diagram of components for implementing a method invocation service in accordance with the present invention.

7 is a distributed processing system diagram that may be used in embodiments of the present invention.

8 is a separate software component diagram within a platform of a distributed processing system according to an embodiment of the present invention.

9 is a data processing system diagram for leasing storage in a distributed processing system that may be used by alternative embodiments of the present invention.

10 is a flow chart of the steps performed by a client when requesting a lease from a server according to an alternative embodiment of the present invention.

11 is a flowchart of steps performed by a server when a client requests a lease, in accordance with an alternative embodiment of the present invention.

In accordance with the present invention, a resource within a distributed system, for example, an application that maintains a reference to a resource, and a garbage collection system that manages the resource, may be responsible for ensuring that the reference to the resource and the resource is guaranteed. By leasing, referential integrity is guaranteed without expensive memory leaks. At the end of the lease period, the guarantee of continued reference to the resource has passed, allowing the garbage collection system to recover the resource. The application holding the reference to the resource and the garbage collection system managing the resource agree on an infinite guaranteed lease period, all of which know when the lease ends, and therefore when the end of guarantees ends. have. This ensures referential integrity for the duration of the reference lease and avoids the concern of not freeing resources due to network errors. In addition to memory, the leasing technique can be applied to other kinds of storage devices such as storage devices.

As illustrated and broadly described herein, in accordance with an alternative embodiment of the present invention, a leasing technique is used for fault detection and recovery. When using a lease for fault detection, the client requests a lease from the server, and after the lease is granted, the client performs various processing on the resources managed by the server. When the lease is about to expire, the client renews the lease. If for some reason this update fails, it is either because the server fails or because there is an error in the communication mechanism for transferring data between the client and the server. In either case, the client detects an error. Incidentally, if the lease expires without a client renewing or explicitly requesting the cancellation of the lease, the server knows that either the client or one of the communication mechanisms has an error. In this case, the server detects an error.

In addition to fault detection, alternative embodiments also provide for fault recovery. During establishment of the lease, the client provides the server with a crash recovery routine, and similarly, the server provides the client with a crash recovery routine. Thus, upon detection of a failure, both the client and the server each call each other's failure recovery routines to perform failure recovery with respect to each other. After performing the failover, both the client and server enter a preset state. That is, the client and the server negotiate in advance to determine a state to be entered when an error occurs, such as rolling back all the changes made to the resource. As a result, the client and servo know the state of the system after the failure and can continue processing accordingly.

Reference will now be made in detail to embodiments of the invention as illustrated in the accompanying drawings. Wherever possible, the same reference numbers will be used throughout the drawings and the following detailed description to refer to the same or like parts.

The invention can be practiced by a computer constructed of a conventional distributed processing system architecture. However, the architecture and procedure for practicing the present invention is not prior art because it provides a distributed garbage collection scheme that ensures referential integrity and eliminates memory leaks.

A. Overview

The Method Invocation (MI) component located on each of the computers in the distributed processing system implements the distributed garbage collection scheme of the present invention. The MI component may consist of many software modules, preferably written in JAVA ^™ programming language.

In general, whenever an application in a distributed processing system attempts to obtain a reference to a distributed resource and access the resource by name lookup, as a return value for some other call or other method, the application must Call the MI component that manages the resource. The MI component, referred to as the management MI component, keeps track of the number of outstanding references to the resource. If the reference count to the resource becomes zero, the management MI component can retrieve the resource. The count of reference counts to a resource is collectively referred to as a "reference count," and a call that increments the reference count may be called a "dirty call."

When an application no longer needs distributed resources, it sends different calls to the resources or to the management MI component. Upon receipt of this call, the management MI component decrements the reference count for the resource. This call to drop the reference can be called a "clean call."

According to an embodiment of the present invention, the dirty call may include a requested time interval called a lease period for each reference to the resource. Upon receipt of the dirty call, the management MI component sends a return call indicating the period during which the lease is allowed. As such, the managed MI component tracks the prominent number of references as well as the lease duration for such references. As a result, if the reference count for the resource reaches zero or the lease period for the resource ends, the management MI component may reclaim the resource.

B. Procedure

The application call processor in the MI component performs the steps of the application call procedure 100 shown in FIG. The server call processor in the management MI component performs the steps of the procedures 200, 300 and 400 shown in Figs. 2-4, respectively. The garbage collector of the management MI component performs a conventional procedure for retrieving resources already bound to a reference according to instructions from the server call processor. Therefore, the conventional procedure of the garbage collector will not be described.

1. Application Call Processor

1 is a flowchart of a procedure 100 that an application call processor of a MI component uses to process an application request for a reference to a resource managed by the same or another MI component located in a distributed processing system.

After the application obtains a reference to the resource, the application call processor sends a dirty call to the management MI component for the resource, including the requested lease duration and the reference of the resource (step 110). Dirty calls may be passed to the resource itself or to the management MI component.

The application call processor waits for and receives a return call from the management MI component (step 120). The return call includes a granted lease period in which the managed MI component ensures that the reference of the dirty call will be bound to that resource. In other words, the management MI component agrees not to collect resources corresponding to the reference of the dirty call during the grant period. If the management MI component fails to provide an allowance period or rejects a lease request, then the application call processor must send another dirty call until it receives an allowance period.

The application call processor monitors the application usage of the reference and either explicitly notifies the application call processor that the application is no longer needed, or if the application call processor makes its own decision (step 130). Sends a clean call to the management MI component (step 140). In a manner similar to the method used for dirty calls, a clean call can be directed to the referenced resource, and the management MI component will handle this clean call. Next, the application call processor removes the reference from the reference list used by the application (step 150).

If the application has not yet executed the reference (step 130), but the application call processor determines that the allowance period for the reference is about to end (step 160), then the application call processor is responsible for configuring the management MI on behalf of the application. Repeat steps 110 and 120 to ensure that they are held by the element.

2. Server Call Processor

The server call processor of the MI component has three main procedures: (1) handle dirty calls; (2) handle incoming clean calls; And (3) initiate a garbage collection cycle to recover resources at the appropriate time.

(i) Dirty Calls

2 is a flow diagram of a procedure 200 that a server call processor of a MI component uses to process a reference request for resources, that is, resources managed by the MI software component. These requests come from the application call processor of the MI component in the distributed processing system, including the application call processor of the same MI component as the server call processor processing request.

First, the server call processor receives the dirty call (step 210). The server call processor then determines an acceptable allowance period (step 220). The grant period may be the same as the requested lease period or some other time period. The server call processor determines the appropriate allowance period based on many conditions including the number of other allowance periods previously allowed for the same resource as the amount of the requested resource.

If the server call processor determines that no resource has yet been allocated for the reference of the dirty call (step 230), the server call processor allocates the requested resource (step 240).

The server call processor then increments the reference count corresponding to the reference of the dirty call (step 250), sets an acceptable allowance period for reference-to-resource binding (step 260). In step 270, a return call with the allowed duration is sent to the application call processor. As such, the server call processor, under its control, controls incoming dirty calls on references to resources.

The application can extend the lease by sending a dirty call with an extend request before the current lease ends. As shown in procedure 200, a lease extension request is treated like an initial request for a lease. Extension means that resources are not recovered for additional time intervals unless the reference count is zero.

(ii) clean calls

The server call processor of the MI component also handles clean calls from the application call processor. When an application in a distributed processing system no longer needs a resource reference, it notifies the MI component that manages the resource for that reference so that the resource can be retrieved for reuse. 3 is a flow diagram of a procedure 300 with steps that the server call processor of the MI component uses to handle clean calls.

When the server call processor receives a clean call with a reference to a resource managed by the MI component (step 310), the server call processor decrements the corresponding reference count (step 320). The clean call is sent to the resource, and the server call processor executes the procedure 300 to monitor the resource and process the call. The server call processor then sends a return call to the MI component that sent the clean call to acknowledge receipt (step 330). According to an embodiment of the invention, a clean call that breaks the reference cannot be reused, but it must be acknowledged.

(iii) garbage collection

The server call processor also initiates a garbage collection cycle to determine that no further reference has been made to the resource or that the allowed lease period for the resource has expired and is reclaimed. The procedure 400 shown in FIG. 4 includes a flowchart of the steps that the server call processor uses to initiate a garbage collection cycle.

The server call processor monitors the reference count and the allowed lease duration and determines whether the reference count is zero or the allowable duration for the reference has expired for resources managed by the MI component (step 410). If one condition exists, the server call processor initializes the garbage collector of the resource (step 420). Otherwise, the server call processor continues to monitor the reference count and allowed lease duration.

C. Call Order

5 is a diagram illustrating a call order among MI components in a distributed processing system. Management MI component 525 manages resource 530 by monitoring references to resources 530 (see garbage collect 505). Because the management MI component 525 manages resources, the server call processor of the management MI component 525 performs the operations of this call order description.

5 also shows that applications 510 and 540 have corresponding MI components 515 and 545, respectively. Each application 510 and 540 obtains a reference to one of the resources 530 and gains access to one of the resources 530 such that the reference is bound to the corresponding resource. To gain access, applications 510 and 540 call corresponding MI components 515 and 545, respectively, and send dirty calls 551 and 571 to MI component 525, respectively. MI components 515 and 545 because MI components 515 and 525 handle application requests for access to resources 530 managed by other MI components, such as management MI component 525. The application call processor of performs the operation of this call sequence description.

In response to dirty calls 551 and 571, management MI component 525 transmits return calls 552 and 572 to each of MI components 515 and 545, respectively. The dirty call includes an allowed lease period for references of dirty calls 551 and 571.

Similarly, FIG. 5 also shows MI components 515 and 545 sending clean calls 561 and 581 to management MI component 525, respectively. Clean calls 561 and 581 notify management component 525 that applications 510 and 540 no longer require access to the resources specified in clean calls 561 and 581, respectively. Management MI component 525 responds to clean calls 561 and 581 as return calls 562 and 582, respectively. The return calls 562 and 582 differ from the return calls 552 and 572 in that the return calls 562 and 582 are simply acknowledgments from the MI component 525 of the received clean calls 561 and 581. .

Both applications 510 and 540 can request access to the same resource. For example, while application 540 is allowed access to "RESOURCE (1)", application 510 may request access to the resource. MI component 525 handles this situation by making resources available to both applications 510 and 540 during the allowed lease period. Thus, the MI component 525 retrieves "RESOURCE (1)" when either of the applications 510 and 540 both stops referencing the resource, or which one first occurs until the latest allowed period expires. Will not initialize the garbage collection cycle.

By having more than one application access the same resource at the same time, the present invention also allows the application to access the resource after sending a clean call to the management MI component that breaks the reference to the resource. This occurs because the management MI component 525 has not yet reclaimed the resource because the resource is still referenced by another application or the lease of the reference has not yet expired. However, resources will be reclaimed after a finite time when no more applications have a lease or the final lease expires.

D. MI Components

6 is a block diagram of a module of MI component 600 in accordance with an embodiment of the present invention. MI component 600 may include a reference component 605, application call processor 640, server call processor 650, and garbage collector 660 for each monitored reference.

Reference component 605 preferably constitutes a table or equivalent structure having reference data portion 610, reference count 620, and tolerance period register 630. The MI component 600 determines the reference count 620 and permission for each reference specified in the corresponding reference data portion 610 to determine when to initialize the garbage collector 660 to recover the corresponding resource. Use period 630.

The application call processor 640 is a software module that performs the steps of the procedure shown in FIG. The server call processor 650 is a software module that performs the steps of the procedures 200, 300 and 400 shown in FIGS. 2-4. The garbage collector 660 is a software module that reclaims resources in response to instructions from the server call processor 650 as described above.

E. Distributed Processing System

7 illustrates a distributed processing system 50 that may be used to seal the present invention. In FIG. 7, distributed processing system 50 includes independent and heterogeneous platforms 100, 200, and 300 connected in a network configuration represented by a network cloud 55. This configuration and protocol of the network configuration represented by FIG. 7 by the cloud 55 is not critical as long as it enables communication of information between the platforms 700, 800, and 900. Incidentally, the use of these three platforms is merely exemplary and does not limit the present invention to a specific number of platforms. In addition, the specific network architecture is not critical to the present invention. For example, another network architecture that can be used in accordance with the present invention will use one platform as a network controller to which all other platforms can be connected.

In an implementation of a distributed processing system, platforms 700, 800, and 900 have processors 710, 810, and 910, and memories 750, 850, and 950, respectively. Included within each processor 710, 810, and 910 are applications 720, 820, and 920, operating systems 740, 840, and 940, and MI components 730, 830, and 930, respectively.

Applications 720, 820, and 920 may be previously written and modified to operate in accordance with the present invention, or may be specially written programs to use the services provided by the present invention. Applications 720, 820, and 920 invoke operations performed in accordance with the present invention.

The MI components 730, 830 and 930 correspond to the MI component 600 described with reference to FIG. 6.

Operating systems 740, 840 and 940 are standard operating systems coupled to corresponding processors 710, 810 and 910, respectively. Platforms 700, 800 and 900 may be heterogeneous. For example, platform 700 is UltraSpacr manufactured by Sun Microsystems, Inc. It has a microprocessor as the processor 710, Solaris An operating system 740 is used. The platform 800 has a MIPS microprocessor manufactured by Silicon Graphics Corp. as the processor 810 and uses a Unix operating system 840. Finally, the platform 900 has a Pentium microprocessor manufactured by Intel Corp. as the processor 910 and uses the Microsoft Windows 95 operating system 940. The present invention is not so limited, and can accommodate heterogeneous platforms.

Sun, Sun Microsystems, Inc. Solaris, Java, and the Sun Logo are trademarks or registered trademarks of Sun Microsystems, Inc. in the United States and other countries. UltraSpacr and all other SPARC trademarks are licensed and trademarks of SPARC Internatipnal, Inc. in the United States and other countries. Products bearing SPARC trademarks are based upon an architecture developed by Sun Microsystems, Inc.

The memories 750, 850 and 950 perform several functions, such as general purpose storage for the associated platform. Another function is to store the applications 720, 820, and 920, the MI components 730, 830, and 930, and the operating systems 740, 840, and 940 before executing by the respective processors 710, 810, and 910. In addition, some of the memories 750, 850 and 950 may constitute shared memory available to all platforms 700, 800 and 900 in the network 50.

E. MI Service

The present invention can be implemented using a client / server model. The client issues requests such as dirty calls and clean calls, and the server responds to the request.

Each MI component 730, 830 and 930 shown in FIG. 7 preferably includes both a client component and a server component. 8, which is a block diagram of the client platform 1000 and server platform 1100, applies to any two of the platforms 700, 800, and 900 of FIG. 7.

Platforms 1000 and 1100 include memories 1050 and 1150, and processors 1010 and 111, respectively. The devices in platforms 1100 and 1100 function the same as the similar devices described with reference to FIG. 7. In this example, processor 1010 executes client application 1020, and processor 1110 executes server application 1120. Processors 1010 and 1110 also execute operating systems 1040 and 1140, and MI components 1030 and 1130, respectively.

MI components 1030 and 1130 include server call processors 1031 and 1131, application call processors 1032 and 1132, and garbage collectors 1033 and 1133, respectively. Each MI component 1030 and 1130 may also have reference data portions 1034 and 1134, reference counts 1035 and 1135, and allow for each reference that each MI component 1030 and 1130 monitors. And a reference component including period registers 1036 and 1136.

The application call processors 1032 and 1132 represent client services and communicate with server call processors 1031 and 1131, respectively, representing server services. Since platforms 1000 and 1100 include a server call processor, each platform can act as a client or server because it includes an application call processor, garbage collector, and reference components.

However, for the following description, platform 1000 is designated as the client platform and platform 1100 is designated as the server platform. In this example, the client application 1020 obtains a reference to the distributed resource and uses the MI component 1030 to send a dirty call to the resource managed by the MI component of the server platform 1100.

Incidentally, the server platform 1100 may execute the server application 1120. Server application 1120 also uses MI component 1130 to allow dirty calls to be handled by MI component 1130 when resources of such dirty calls are managed by MI component 1130. Send. Optionally, server platform 1120 can use MI component 1130 to send dirty calls to resources managed by MI component 1030.

Thus, the server call processor 1031, garbage collector 1033, and reference count 1035 for the MI component 1030 of the client platform 1000 are not active and are therefore shown as shaded in FIG. 8. Similarly, the application call processor 1132 of the MI component 1130 of the server platform 1100 is shown as hatched because it is dominant.

When the client application 1020 obtains a reference corresponding to the resource, the application call processor 1032 transmits a dirty call that the server call processor 131 receives. The dirty call includes the requested lease term. The server call processor 1131 increments the reference count 1135 for reference in the dirty call, and determines the allowed period. In response, server call processor 1131 sends a return call with an allowance period to application call processor 1030. The application call processor 1032 uses the permission period to update the recorded permission period 1035 and determine when the resource corresponding to the reference of the dirty call is retrieved.

The server call processor 1131 also monitors the reference count and the allow period corresponding to the reference to the resource to be managed. If one of the reference counts 1135 is zero or the allowance period 1135 for the reference ends, and if any event occurs first, the server call processor 1131 initializes the garbage collector 1133 to zero reference. The resource corresponding to the reference with the count or expired allowed period may be recovered.

A leased reference scheme in accordance with an embodiment of the present invention does not require the clocks on the platforms 1000 and 1100 included in the protocol to be synchronized. This scheme only needs to have a significant increase period. A lease does not expire at a certain time, but rather expires after reaching a certain time. As long as there is an approximate agreement on arrival, platforms 1100 and 1000 will have an approximate agreement on the allowed lease term. In addition, since the timing of the lease is quite long in computer terms, even slight differences in clocks will have little or no effect.

The transmission time of the dirty call can affect the protocol. If the MI component 1030 holds a lease for a reference and immediately before the lease requesting the update ends, wait for the lease to terminate before the MI component 1130 receives the request. . If so, MI component 1130 may reclaim the resource before receiving the update request. Thus, when sending a dirty call, the sender must determine the time factor for the requested lease period, taking into account the transmission time to the platform handling the resource of the dirty call so that an update dirty call can be made before the lease period for the resource ends. Must be added.

F. Conclusion

According to the present invention, a distributed garbage collection scheme ensures referential integrity by providing an allowed lease period corresponding to a reference to a resource in the distributed processing system, to provide a reference to the resource when the allowed lease period expires, Remove memory leaks. This resource can then be collected. This resource may also be collected when a reference to the counter is no longer referenced by a process in the distributed processing system assigned to the reference to the resource.

Alternative embodiment of the present invention

The aforementioned leasing technique relates to garbage collection. However, alternative embodiments of the present invention can be used to detect failures and perform error recovery as described below.

Many systems are used to detect failures in client-server environments, such as heartbeats or timeouts. Using heartbeats, the client sends messages at periodic intervals to the server indicating that the client is alive. If the server does not receive a message in one of the intervals, the server knows that a failure has occurred in the client or communication mechanism (i.e. network) that transfers data between the client and the server. Using the timeout, a predetermined amount of time is set and if the server does not receive any communication from the client within that time period, the server knows that either the client or the communication mechanism has failed.

Although such prior art systems properly indicate when a failure has occurred, both the client and server may not be aware of the state of the system after the failure. For example, when the client is a program and the server is a file system manager, the client may need to perform a write operation on a particular file managed by the server. Although the prior art failure detection system detects a failure when a failure occurs, the client does not know whether the failure occurred before or after the write operation was performed on the file. In such a situation, the client will not be able to determine the state of the system.

Alternative embodiments of the present invention solve this problem by using a leasing technique for fault detection and recovery. When using a lease for fault detection, the client requests a lease from the server and performs various processing on the resources managed by the server during the allowed lease period. If for any reason the update fails, it is because the server has failed or the communication mechanism has failed. In either case, the client detects a failure. On the server side, if the lease expires without a client renewing or performing an explicit cancellation, the server knows that the client or communication mechanism has failed, and therefore the server detects the failure.

Upon detection of a failure, the client and server proceed with the predetermined state to perform recovery. In other words, the client and server negotiate in advance a condition that will fail or enter upon detection. For example, in the file system example above, the client and server may negotiate to perform a rollback if a failure is detected. "Roll back" refers to putting any related entities, such as clients, servers, and files, into the state they were in before the failure occurred. Thus, in this example, if the server has already performed the write operation, the server restores this file to the state just before the write operation is performed, and the client knows that the write operation was not performed after the failure was detected, This allows the client to continue its processing.

In general, clients and servers can roll back more. For example, whenever an error occurs during a file operation, the client and server can negotiate in advance by rolling back the client and server to the state they were in just before the client and server took lease (that is, before the file was created). Can be. Another way is to roll back to the left checkpoint in the file operation. Such negotiations between the client and the server determining the system state after a failure may include a handshake, reading a selected file, or a server and client that can be instructed to always return to the system state after a predetermined failure in deployment. It can be done by the method.

Incidentally, during the establishment of the lease, the client may provide a failure recovery routine to the server, and similarly, the server may provide a failure recovery routine to the client. Therefore, upon detecting a failure, both the client and the server call each other's failure recovery routines to perform failure recovery. In this situation, if the server fails, once the client detects the failure, the client invokes the server's recovery routine to perform the recovery for the server. For example, the recovery routine can restart the server and send a message to the system administrator. Similarly, if a client fails, the server calls the client's recovery routine to perform a crash recovery for the client.

Because the client and server recover from each other, system administrators are performed on a distributed basis. That is, instead of a central administrator performing system management, as in some conventional systems, by using a leasing technique for failure detection and recovery, an alternative embodiment is that the client may perform recovery for the server, and the server may Distribute system management processing to allow recovery to clients.

Alternate embodiments may be used in any client-server relationship, including operation in a distributed system where the client and server communicate over a network or where the client and server reside on the same machine. . Such a distribution system suitable for use in alternative embodiments is an exemplary distribution system described in US Patent Application No. entitled "Dynamic Lookup Service in a Distributed System", which is incorporated by reference of the present invention. However, for the sake of clarity, an alternative embodiment will be described below in connection with a server, which is a file system administrator that leases storage on auxiliary storage.

Summary to lease storage

Storage devices have a number of storage locations that contain various logical groupings of data that can be used by one or more programs. These logical groupings may take the form of files, databases or documents. Leasing of storage allows access to the storage (ie, read and write access) for a predetermined amount of time. What kind of data is contained in a storage location or whether the storage location contains all of the data is important in the storage of storage. In addition, storage leasing can be applied to different levels of storage, such as database files, fields, blocks of storage, or actual storage.

In computer systems or distributed systems, many programs can compete for files stored in various groups of storage. Thus, groups of storage locations can have many programs competing for access. Leasing techniques can be used to mediate the use of storage in such circumstances.

When using a lease for a group of storage containing data for a file, the program ("client") leases from the file system administrator ("server") to access the group of storage for a period of time ("lease period"). Ask. Depending on availability, priority, and other factors, the server denies the request or allows a lease term. The permitted lease term may be the entire lease term requested or a portion thereof. Once the client receives the lease, the client can access the group of storage for the lease term.

When requesting a lease term, the client can request the exact lease term. In this situation, only the server allows a lease if the lease term is the opposite of a part of the requested total lease term.

While the lease is active, the client is guaranteed access to the group of storage, and can perform read and write operations thereon. And similarly, the server will maintain the integrity of the storage location during the active lease. For example, during the lease period, the server will not allow the leased file to be deleted or written, or will not be damaged by any other entity other than the client, unless the entity also has a lease. However, after the lease expires, the server no longer guarantees the integrity of the file to the client, so the server can delete the file, or otherwise, physically change it or do it to another client to do the same. Will allow lease. Storage areas that do not have any outstanding leases are retrieved by the server.

Each store may have an associated limiting parameter, such as an access parameter or a privilege parameter. The access parameter determines what kind of access the server supports for the storage location. For example, the storage location can be defined only by read access. In this case, only the server will allow read access for the next authorized lease for a particular storage location. Conversely, an attempt by the client to write to that storage location would not be allowed by the server. Other potential storage access parameters may include write access, allocation access, reallocation access, and subblock access (ie, if it is a large block of storage).

The associated privilege parameter specifies the privilege level the client must have before the lease is allowed. The server may use privilege parameters to prioritize competing lease requests. In other words, when a server has multiple outstanding lease requests for the same store, it can prioritize these requests based on the requesting client's privilege level.

Alternative embodiments also support parallel access to groups of storage locations by allowing multiple concurrent leases to the same storage location. For example, if a parameter of a particular storage location specifies "read" access, the server may allow multiple parallel leases to the storage location without violating the integrity of the storage location. Parallel lease can also be applied to large files, for example. The server can again lease smaller subblocks of the file without compromising the integrity of the larger file.

Once a client requests a lease, the server returns to the client an object containing methods for determining the duration of the lease, renewing the lease, canceling the lease, and performing crash recovery. This object is an instance of a class that can be extended in a way that provides more functionality, but the basic class is defined in the Java programming language as follows:

interface Lease {

obj FileHandle;

public long gerDuration ();

public void cancel () throws UnknownLeaseException,

RemoteException;

public void renew (long renewDrration) throws

LeaseDeniedException,

UnknownLeaseException,

RemoteException;

}

This class contains a number of methods, including the getDuration method, the cancel method, the renew method, and the recover method. The "getDuration" method gives the client the length of the lease allowed. This period represents the most recent lease allowed by the server. However, it is the client's responsibility to determine the amount of time remaining in the lease.

The "renew" method allows the client to request more time to renew the lease without having to reinitialize the original lease request. A situation in which a client may want to update a lease is when the original lease proves insufficient (i.e. when the client needs an additional use of storage) or only a partial lease (ie Less than a lease).

The client may use the update method to request an additional lease period, or the client may continue to call the update method multiple times until many additional lease periods are allowed. This update method also has no return value: If an update is allowed, the new lease duration will be reflected in the lease object that invoked it. If the server cannot or does not want to update the lease, the reason is specified in the calling lease object.

The client calls the "cancel" method when the client wants to cancel the lease. Thus, the call to cancel allows the server to retrieve the storage location so that other programs can access the storage location. Thus, the cancel method allows the server to optimize the use of storage in distributed systems. If the lease terminates without explicit cancellation by the client, the server assumes that an error has been issued.

The "recover" method is provided by the server so that the client can perform crash recovery on the server. For example, such error recovery may include restarting the server.

Leasing of a storage location is described in detail in US Patent Application No. entitled "Method and System for Leasing Storage", which is incorporated herein by reference.

Details of implementation

9 illustrates a data processing system 9000 suitable for use by alternative embodiments of the present invention. Data processing system 9000 includes a computer system 9001 connected to the Internet 9002. Computer system 9001 includes a memory 9003, auxiliary storage 9004, a central processing unit (CPU) 9006, an input device 9008, and a video display 9010. The memory 9003 further includes an operating system 9012 and a program 9014 that is a client. Operating system 9012 includes a file system manager 9016 that is a server that manages files 9018 on auxiliary storage 9004. Client 9014 requests access to one or more files 9018 by requesting a lease from server 9016. In response, server 9016 may choose to allow or deny the lease, as described below.

JavaSpace 9019 is an object store used by a program in data processing system 9000 to store objects. Programs use JavaSpace 9019 to make objects persistent as well as accessible to other devices on the network. JavaSpace is incorporated as a reference to the present invention and described in detail in U.S. Patent No. 08 / 971,529 (filed Nov. 17, 1997) entitled "Database System Employing Polymorphic Entry and Entry Mathcing" as applicants of the present invention. It is. Those skilled in the art will appreciate that the computer 9000 may include additional or different computers.

Although the features of alternative embodiments have been described as being stored in memory 9003, those skilled in the art will also appreciate that such features may also include auxiliary storage such as hard disks, floppy disks, or CD-ROMs; Carrier from the Internet; Or it may be stored in or read from other computer readable media, such as other forms of RAM or ROM. Incidentally, those skilled in the art will appreciate that alternative embodiments may be used to lease other types of data in auxiliary storage, such as databases, spreadsheets and documents.

10 shows a flowchart of the steps performed by a client when requesting a lease from a server. The first step performed by the client is to send a lease request to the server (step 10002). This request includes (1) the requested storage location that the client wishes to lease, (2) a given lease duration, (3) the exact lease indicator, (4) the type of access the client wants, (5) the client's authority, (6) A function call with multiple parameters, including an object containing a recovery method. This method contains code to perform error recovery on the client.

The requested storage location includes an indication of the storage location to be leased. The predetermined lease period includes the amount of time the client wants to use the storage location. The exact lease request includes an indication of whether the correct lease request is being made or if less than the requested amount is sufficient. The type of access requested indicates the type of storage access requested by the client. Types of access include read access, write access, allocation access, reallocation access, and subblock access (i.e., large blocks of storage). The privilege field indicates the privilege level of the user or client. In order to form a valid request, the client request must include the requested storage location and a predetermined lease period.

There are two common scenarios for issuing lease requests to storage. The first scenario occurs when a file is created. The "create" command used to create a file is used to create a file, and also to issue a lease request to the server to access the file. The second scenario occurs when a client wants to access a file that already has an existing storage location or already an existing lease (in the case of a parallel lease).

After sending the request, the client receives a lease object from the server (step 10004). This lease object contains a variety of information, including a file handle, a getDuration method, an update method, a cancel method, and a recovery method, as described above.

After receiving the lease object, the client uses the file (step 10005). Next, the client determines whether the use of the file has been completed (step 10006). If so, the client invokes a cancel method on the lease object to explicitly cancel the lease (step 10007). By calling this method, the server does not assume that a failure has occurred and the lease is canceled by the server.

If the client has not completed using the file, the client determines whether the lease is about to expire (step 10008). The client performs this step by calling the getDuration method and determining whether the remaining time is within a predetermined threshold. If the lease does not expire, processing proceeds to step 10005. However, if the lease is about to expire, the client sends a new request to the server (step 10009). In this step, the client invokes an update method on the lease object. After calling the update method, the client determines whether the update request was successful (step 10010). In this step, the client determines whether the update request was successful by whether the update method returned successfully. If so, processing proceeds to step 10005. However, if the update method did not complete successfully, the client invokes the recovery method on the lease object (step 10012). Since the update request did not complete successfully, the client knows that a failure has occurred, and therefore needs to perform error recovery by calling the recovery method. The recovery method then performs a recovery to the server.

11 shows a flowchart of steps performed by a server in accordance with an alternative embodiment of the present invention. The first step performed by the server is to access JavaSpace 9019 (step 11002). The server maintains a JavaSpace that stores all the objects received during the lease request. These objects are stored in JavaSpace so that when the server detects a failure, it can perform the recovery by accessing JavaSpace and calling the recovery method on the object. In addition, the objects are stored continuously so that if the server crashes, when the server restarts, it will be able to invoke the restore method on each object in JavaSpace, reflecting all outstanding leases in the event of a server crash. In step 1102, the server accesses a JavaSpace containing all objects received from the client as part of the lease request, if present. If any object exists in JavaSpace, a failure must occur during server processing.

Next, the server invokes a recovery method of each object in JavaSpace (step 11004). At this stage, if an object exists in JavaSpace, this indicates that the server has terminated the process due to a high risk and should perform a recovery. The server performs this recovery by invoking a recovery method for each client that has a lease. These recovery methods can cause the client to restart and restore to a predetermined state, such as the state just before requesting the lease. After calling all recovery methods, the server deletes all objects from JavaSpace (step 11006). After the recovery is performed, the object is no longer needed.

After deleting the object, the server receives a lease request from one of the clients (step 11008). After receiving the lease request, the server stores the object received in the request in JavaSpace (step 11010). By storing the object in a JavaSpace that constantly stores the object, if a failure occurs, the server can access the JavaSpace and call a recovery method on the object to perform error recovery for the client.

After storing the object in JavaSpace, the server grants the lease request by returning an object with the aforementioned method, including a recovery method for the server (step 11012). After some point in the server's processing, the server determines whether an update request from the client has been received (step 11014). If an update request has been received, the server updates the lease (step 11017). However, if no update has been received, the server determines whether a cancel request has been received by the client invoking the cancel method (step 11015). If the client called the cancel method, the server cancels the lease by deleting the object stored in Java 1 1010 from JavaSpace, and if this is the last lease on the file, the server deletes the file (step 11016).

If no cancellation request is received, the server determines whether the lease has expired (step 11018). If the lease has not expired, processing proceeds to step 11014. However, if the lease has expired, the server knows that a failure has occurred and thus invokes a repair method on the object in JavaSpace for the client with the expired lease (step 11020). After calling the recovery method, the server deletes this object because it is no longer needed (step 11022).

Although the method and system according to the present invention have been described with reference to specific embodiments thereof, those skilled in the art will recognize that the present invention may be variously modified without departing from the spirit and scope of the present invention as defined in the claims. Could be.

Claims (3)

In a method in a data processing system having a client and a server, The client requesting a lease from the server, using a resource managed by the server, the lease request including a first recovery routine; The server granting the lease and sending a second recovery routine to the client so that the client can use the resource for a period of time; The client using the resource; The client determining when the time period is about to expire; Updating the lease by sending a request to the server when the client determines that the lease is about to expire; Determining whether the update request is successful; The client invoking the second recovery routine to perform crash recovery for the server when the client determines that the lease has expired; Determining, by the server, whether the lease has expired; And The server invoking the first recovery routine when the lease expires performing a crash recovery for the client. In the failure detection method for a distributed system, Providing a lease for accessing a machine in the distributed system; Determining whether the lease requires an extension; Sending an update request to extend the lease; And Detecting an event to prevent access to the machine based on a failure to receive an update lease in response to the update request. The method of claim 2, Performing recovery routine detection upon detection of said event preventing access to said machine.