Shared Computation

Project Sitemap

Project Homepage

Features and Capabilities

This project demonstrates the use of GigaSpaces XAP and OpenSpaces to ensure that multiple requests for the same expensive computation share the result of a single execution of that computation rather than causing multiple executions to occur.

Consider a service that executes an expensive computation. In this case, "expensive" means that it takes on the order of 10 to 15 seconds to process a request. The system is configured to have a certain number of instances of this service running simultaneously. Communication with the service instances is via the the space: clients write requests to the space and retrieve the results when they are available. Either blocking read or notification can be used to get the result.

Many clients will be making requests nearly concurrently. Some requests from different clients will be identical. The result for a particular request is valid through the end of the day.

The primary requirement of this system is that the service should not be invoked unnecessarily. This means that results, once computed, should be available for as long as they are valid and that requests that arrive while an identical request is being processed should not cause a second service invocation.

An additional requirement is that any mechanism for meeting the processing requirements should be transparent to the clients. Clients should simply write requests and read results.

The first requirement, that results should be available for as long as they are valid, is trivially easy with GigaSpaces XAP. When the service computes a result, it writes it into the space with a lease of the appropriate length. From then on the result is available immediately to any client making an identical request.

The second requirement, not processing identical requests even when the result is not yet available, is more technically interesting. The basic technique, unsurprisingly, uses a mutex. When a request is written to the space, it is picked up by a worker that is responsible for invoking the service. Before that invocation, the worker checks for an exiting result. If one exists, the worker moves on to another request. If no result is found, the worker attempts to write a mutex, based on the unique identifiers of the request, into the space. If an identical mutex already exists, the worker moves on to another request. If the mutex write succeeds, the worker invokes the service and, when it completes, writes the result to the space. That is:

  take request
  if no result exists
    try to write mutex
    if write succeeds
      invoke service
      write result

The operations involved in taking the request from the space and writing the result are executed in the same transactional context. If the worker fails for any reason, the transaction will abort and the request will reappear in the space.

The implementation of the mutex takes advantage of GigaSpaces' unique UID to cause the write to fail if an identical mutex is already in the space. The code to create this UID is in the constructor of the mutex class:

  // The symbol and price fields constitute a unique identifier.
  __setEntryInfo(
    new EntryInfo(
      ClientUIDHandler.createUIDFromName(new String(symbol + ":" + price),
                                         Mutex.class.getName()),
      0));

If the worker (or the machine on which the worker is running) fails after writing the mutex but before invoking the service, processing of the request could block indefinitely. Leasing, the second technically interesting GigaSpaces XAP feature in this solution, addresses this problem.

Entries in the space, like many components of the GigaSpaces XAP Space Based Architecture (SBA) have an associated lease. This is the period of time that the space agrees to hold the entry. When the lease expires, the entry is removed from the space.

Leases can be renewed before they expire. This is the feature that allows a mutex to be maintained only so long as the worker that wrote it is running. The worker first writes the mutex with a lease considerably shorter than the expected service execution time. It then creates a lease renewal manager to renew the lease periodically while the service is executing. If the worker or service fail for any reason, the mutex' lease will not be renewed and it will disappear from the space. This will allow another worker to process the request.

To eliminate the possibility of a worker not finding a result that is about to be written and therefore invoking the service unnecessarily, when the result in written to the space, the mutex' lease is updated to overlap slightly with the lifetime of the result.

To get the source code for this example, create a directory called org/openspaces, make it your working directory, and use Subversion:

The README file contains this description. Instructions for building and deploying the example are in INSTALL.