3.2. Shared Variables

One of the most common data structures in space-based distributed programming is the shared variable. A space-based shared variable is the simplest of distributed data structures, since it is made up of a single entry. Like any variable, a shared variable provides storage for some value or object; however, a space-based shared variable allows multiple processes to easily access and modify its value in an atomic manner. We will return to the topic of atomic modification shortly, but let's first build a space-based shared variable.

Here is a definition of a simple shared variable:

public class SharedVar implements Entry {
  public String name;
  public Integer value;

  public SharedVar() {
  }

  public SharedVar(String name) {
    this.name = name;
  }

  public SharedVar(String name, int value) {
    this.name = name;
    this.value = new Integer(value);
  }
}

Here we've defined a SharedVar, which is really just an entry with a value (in this case an Integer). We've also provided a name field, which gives us a way to uniquely identify a particular shared variable without having to subclass SharedVar for each shared variable we need to create. To create a shared variable, we simply pass a unique name and initial value to the SharedVar constructor, and write the result to a space:

SharedVar myvar = new SharedVar("duke's counter", 0);
space.write(myvar, null, Lease.FOREVER);

The SharedVar class can be used to instantiate multiple shared variables and write them to the same space, as long as we make sure each shared variable is created with a unique name.

3.2.1. Atomic Modification

Shared variables typically support two operations, “read” and “update.” A “read” returns the current value of the variable, while “update” stores a new value. A crucial requirement of a shared variable is that its modification must be atomic—in other words, must behave as an indivisible unit.

Without an atomic means of accessing and altering shared variables, having multiple processes share access to data can lead to race conditions and corrupt values. This scenario demonstrates the problem: Suppose two bank tellers are making deposits to the same bank account at the same time. Bank teller #1 looks up the bank balance, let's say $200, and is about to deposit $100. At the same time, bank teller #2 also looks up the balance (also $200 since teller #1 hasn't completed the deposit yet) and is about to deposit $50. Next, bank teller #1 performs the deposit of $100 ($200 + $100 = $300) and records a balance of $300 for the account. Just a moment later, bank teller #2 deposits $50 ($200 + $50 = $250) and records a balance of $250 for the account. Unfortunately, the bank balance has been corrupted: the account has $250 when it should have $350.

The problem occurs because updating the bank balance is not an atomic operation, but involves the three separate operations of looking up, modifying, and setting the account's value. Concurrent bank tellers can carry out those operations in an interleaved way, interfering with each other and corrupting values. To solve the problem, updating a shared value needs to be atomic—performed as one indivisible step.

With JavaSpaces technology we get this atomicity “for free” as a key feature of the space. To see what we mean by this, let's take a look at how we atomically update a space-based shared variable:

SharedVar template = new SharedVar("duke's counter");
SharedVar result = (SharedVar)
  space.take(template, null, Long.MAX_VALUE);
result.value = new Integer(result.value.intValue() + 5);
space.write(result, null, Lease.FOREVER);

Here, we've added five to the current value of the shared variable named “duke's counter.” We didn't need to do anything special to cause the update to happen atomically; the space-based operations themselves naturally provide atomic access to entries. Any update to an entry (here, a shared variable) requires a process to “physically” remove the entry, alter its value locally, and place a copy back into a space. This means that only one process can hold the entry locally and update it at any given time, but many processes can read the entry while it is in the space.

The race condition we encountered in our bank teller example can't occur here, because no two tellers can “own” the bank balance entry at the same time. Furthermore, while the entry is being updated, the entry is not available to other processes trying to read or take it. Any process that wants to read or alter the shared variable after we've removed it must wait patiently until it is returned.

3.2.2. Additional Operations

Beyond the typical read and update operations on shared variables, other operations are sometimes defined on them, such as “increment” and “decrement.” Implementing these operations is straightforward. Let's see how increment, for instance, can be implemented.

First we'll expand our SharedVar class to include a new increment method:

public class SharedVar implements Entry {
  public String name;
  public Integer value;

  public SharedVar() {
  }

  public SharedVar(String name) {
    this.name = name;
  }

  public SharedVar(String name, int value) {
    this.name = name;
    this.value = new Integer(value);
  }

  public Integer increment() {
    value = new Integer(value.intValue() + 1);
    return value;
  }
}

The increment method gives us an easy way to increase the value of the shared variable by one.

Incrementing a shared variable is really just a special case of updating it: We first remove the shared variable from the space, increment its value by calling its increment method, and then return it to the space:

SharedVar template = new SharedVar("duke's counter");
SharedVar result = null;
result = (SharedVar)
  space.take(template, null, Long.MAX_VALUE);
result.increment();
space.write(result, null, Lease.FOREVER);

Again, the update of the shared variable happens atomically here, thanks to the nature of space operations. The entry has to be removed from the space before we can call its increment method, so only one process can increment the shared variable at any given time.

3.2.3. Creating a Web Counter

Let's put our knowledge of shared variables to use. We are going to implement a web page counter that tracks the number of visits to a web page. Web page counters typically work like this: Each time a web page is loaded in a browser, a counter for that page is incremented and displayed within the page with a message such as: “You are the 100th visitor to our site.” On the web server, this is often accomplished by a CGI script that does the following:

Now let's try to do the same with a space-based approach. Our web counter is going to be implemented with a small applet that takes a counter from a space, increments it, returns it to the space, and displays its value. To implement the counter, we use a shared variable. The name field of the shared variable will hold the URL of a web page, and the value field will hold the number of web page visits.

For our counter to work, each web page needs to have a counter, initialized to zero, that is placed in the space. We've created an “installer” application to do this, which is included in the complete source code; for now we will just give the code fragment that creates an initial counter for an URL that's passed in as a parameter to the application:

String url = args[0];
SharedVar webCounter = new SharedVar(url, 0);
try {
   space.write(webCounter, null, Lease.FOREVER);
} catch (TransactionException e) {
  e.printStackTrace();
} catch (RemoteException e) {
  e.printStackTrace();
}

This code fragment instantiates a shared variable called webCounter, setting its name field to the URL of the web page we wish to track and its initial value to zero, and then writes it into the space.

Now let's look at the code for the actual counter applet that we can embed into any web page that we want to track:

public class WebCounterClient extends Applet {
  private SharedVar counter;

  public void init() {
    JavaSpace space = SpaceAccessor.getSpace();

    String url = getDocumentBase().toString();
    System.out.println(url);

    SharedVar template = new SharedVar(url);
    try {
       counter = (SharedVar)
         space.take(template, null, Long.MAX_VALUE);
       counter.increment();
       space.write(counter, null, Lease.FOREVER);
    } catch (RemoteException e) {
       e.printStackTrace();
    } catch (TransactionException e) {
       e.printStackTrace();
    } catch (UnusableEntryException e) {
       e.printStackTrace();
    } catch (InterruptedException e) {
       e.printStackTrace();
    }
    repaint();
    setLayout(null);
    setSize(430, 270);
  }

  public void paint(java.awt.Graphics gc) {
    if (counter != null) {
       Integer count = counter.value;
       gc.drawString("Page visited " + count +
         " times before.", 20, 20);
     }
  }
}

This is a fairly simple applet. All the action takes place in the init method. Recall that an applet's init method is invoked when an applet is initially loaded, so our code will execute the first time a web page is displayed and won't be re-invoked if the user browses back to the page. This is good, because we only want to count the page hit once, even if the user visits it multiple times in a browsing session.

Let's step through the code. First we obtain a handle to a space object by calling the getSpace method of SpaceAccessor. Next we obtain the URL of the page in which our applet is embedded (the page that contains the <applet> tag for this applet) by calling the getDocumentBase method. If you are testing your code by retrieving a page from a web server, the path would be something like http://www.domain.com/path/mydocument.html. In our example, since we are most likely using appletviewer, getDocumentBase will return the pathname of the HTML file that contains our applet. The important point here is that the name of the URL returned from getDocumentBase should be the same as the name that was passed to our installer application and used to initialize the counter in the space.

Now that we have the URL of the web page, we can create a template to retrieve its corresponding counter from the space. We do this by passing the URL to SharedVar's convenience constructor that assigns it to the entry's name field.

Using this template, we take the matching counter from the space—waiting until one exists—and assign it to the applet variable counter. We then increment counter and write it back into the space. The display of the counter is handled by the paint method, which displays the counter value each time it is called (as long as the value is not null, which it is before the counter is retrieved from the space).

Let's run our applet and see how it works:

Here we've run the appletviewer once, and the applet reports that the page has been visited one time. Each time you run the applet, you will see the page count increase by one.

3.2.4. Stepping Back

Before moving on, let's take one more look at how this applet works in an environment where it is embedded in a web page that multiple browser clients access concurrently.

Our file-based CGI scenario enforces synchronization of the counter by explicitly locking and unlocking a file. A key feature of the space is that it enforces synchronized, exclusive access to an entry, because only a single process can hold it locally and modify it at one time (we will revisit synchronization in the next chapter in great detail). When a client issues a take, if the web counter entry exists in the space, it is removed, incremented, and returned. If the web counter has already been “checked out” by another client accessing the same web page, the client will have to wait patiently until the entry is written back into the space.

Note that the space also provides persistence for us. In our CGI script example, a file is used to store the counter; in our space-based web counter, the space manages the persistence for us.

Unfortunately, our applet isn't yet ready to be sold to millions yet. To make it industrial-strength, we need to address a few issues that arise in the presence of partial failure. Consider this: What would happen if our WebCounterClient removed the counter entry from the space and then failed to return it because the applet crashed or the network went down? The answer is that the counter entry would be lost forever. We'd lose track of page hits, and our applet wouldn't work correctly, because it would have to wait for a entry that didn't exist.

Don't worry, there are several things we can do to improve our code—we will return to the issues of partial failure in Chapter 9. But for now, we've seen that implementing a shared variable is quite easy. A shared variable is a fundamental distributed data structure that you are likely to use over and over again in your space-based programs.