Introducing SimulEdit, a distributed text editor
Louis, Sean, and Adam are associated with the California Institute of Technology and can be contacted at [email protected], [email protected], and [email protected], respectively.
Increasingly, electronic documents are being created by groups of people. Because few programs are designed to accommodate group editing, however, people usually end up sitting around a computer sharing a keyboard. Other times, people modify copies of a document, then laboriously merge them together. The more changes made, the more difficult the merge is.
To address such problems, we wrote a text editor that lets groups of people edit the same file at the same time. Changes made by one person are immediately visible to everyone. This text editor was created as a true peer-to-peer application -- the document data belongs to the entire network of editors, not an individual editor. This means that if any editor suddenly drops from the network, the rest easily recover. Enabling this application are generic network data objects (NDOs) shared among multiple processes communicating over a network, existing only as long as those processes exist. Data in an NDO may be manipulated or read by any process sharing the NDO. Changes made by one process are immediately visible to other processes. The data disappears when all of the processes disappear, although a process may save a copy before exiting.
In this article, we'll present both the SimulEdit distributed editing program and the Java package that supports peer-to-peer communications over the Internet. SimulEdit is made up of nine classes, while the NDO package consists of about 34 classes. The code utilizes the Infospheres package for which the source is also available. Source code and related files for all of these packages are available electronically; see "Resource Center," page 3.
Network Data Objects
NDOs are collections of data shared across processes connected by a network. From the standpoint of the processes, this is almost like having these variables stored in shared memory. In our implementation, shared data is stored in types derived from the base class SharedVar. No stand-alone SharedVar exists; every SharedVar in an application is contained within an NDO. Using an NDO instead of traditional networking methods (like message passing) simplifies distributed-application development. Instead of thinking of the program as communicating data between multiple computers, think of programming with NDOs as more like writing a multithreaded, nonnetworked application. Any Java primitive type or class can be stored in a SharedVar, and the NDO will determine what messages need to be sent to keep all of the communicating processes up to date. Because NDOs are lightweight -- meaning that interface compilers, skeletons, or stubs are not needed -- you deal with less complexity.
The NDO system has three base classes -- NDO, SharedVar, and SharedContainer (see Figure 1). Other classes are included for convenience and example code. To create objects for specific applications, you add functionality by subclassing these base classes.
The NDO class handles global networking issues and maintains the list of processes sharing information. SharedVar objects are contained within an NDO, the class at the root of the information-sharing system. Any information shared across the network should be stored in a SharedVar. SharedVars also extend the java.util.Observable class, so that processes can track changes to the data through a callback. SharedVar is an abstract class. It must be extended to store data. Methods like set() or get() may be added to encapsulate modification events, and SharedVar's abstract methods readData() and writeData() must be overridden so that the data can be transferred from process to process. The SharedInt class (see Listing One) illustrates how to make new shared data types.
SharedContainer allows for structured data; see Figure 2. A SharedContainer can contain any number of SharedVars, including other SharedContainers. You can extend SharedContainer so that the application can conveniently access the fields of a SharedContainer. For example, SharedVector is implemented using SharedContainer, and is more appropriate for common use because it allows access to the contained fields in an array-like fashion.
SharedContainer uses a unique index for each new field added; these indexes are never reused. To store the references to the child SharedVars, the SharedContainer uses a java.util.Hashtable object to associate the integer indexes with the SharedVars.
Working with NDOs
When launched, applications create an instance of a subclass of the NDO object that has been extended to be appropriate for the application. One of the NDO's two constructors must be used. The first, which takes no arguments, creates an NDO without contacting any other computers. The other constructor takes one argument (a location on the network) and joins an already existing group of processes. During these constructor calls, the abstract method makeFields() (overridden in the subclass of the NDO) is called to create the basic fields that this NDO requires. After the NDO sets up all the fields and is communicating with other processes, all fields are unlocked, the constructor completes, and the application begins its main loop.
To modify a field, an application must have a lock on it. After obtaining the lock, an application can modify the data, and then must call setModified() on the SharedVar. (In the example classes in the package, the call to setModified() is encapsulated in the set() method.) If the application wants to read the field value, it does so whether or not the field is locked. If the field is not locked, the value that is read is not guaranteed to be the latest one; once the field is locked, the application is guaranteed to have the latest copy of the data. Furthermore, an application is guaranteed that once it sees some version of a variable, it will never see an earlier version.
To write to a SharedVar or to ensure it has the most recent version of data, an application must obtain a lock on the SharedVar. To do this, an application first calls the startLock() method of the NDO; see Listing Two. The application then calls the lock() method of the SharedVars it wants to modify or update. This registers that the application wants to lock that field, but it does not actually lock it. Finally, an application must call NDO.completeLock() to lock the fields. All of the interprocess communication is handled by completeLock() in a specific order to prevent deadlock, which is why completeLock() must be a separate operation. Only after the call to completeLock() returns can the application modify the SharedVar. As soon as the application no longer needs a lock, it should release it by calling unlock() on the SharedVar.
New fields can be added by obtaining a lock on a SharedContainer and constructing the new field with the SharedContainer as the value for the parent argument in the SharedVar constructor. The new field will be initially locked, so that its value can be set by the application.
A field can be deleted only when both the field and its container are locked. Once the locks are obtained, the removeField() method of the container can be called with the index of the field to be deleted as the argument.
An important design consideration was to ensure that, when fields were being added and removed from the containers, old fields would not be confused with new fields. Imagine a scenario in which one process deletes the last field in a container, then adds a new one. If another process knows about only the old version of the container (without the deletion and addition), it might request a lock on the old last field. Instead of giving a lock on the newly added field, an error is reported. This is done by assigning a unique index that is never reused to every field added to a container. When an application requests a lock on a given field, it is guaranteed not to be confused with any other field for the entire existence of the NDO. SharedContainers are not arrays of SharedVars -- that is delegated to SharedVector, which reuses indexes like the Java built-in type java.util.Vector.
To access a given field of a SharedContainer, an application can call the field() method with the field's index as the argument. Alternatively, you may want to store local references to the SharedVars that you most commonly use to avoid lookup overhead.
How NDOs Work
Every SharedVar is owned by exactly one process. The owner of a SharedVar has the most recent copy of the data, and is responsible for giving the SharedVar to any process requesting a lock on it. Whenever a process obtains a lock on a SharedVar, it is then the owner. When a process unlocks a SharedVar, it remains the owner until some other process requests a lock on that SharedVar.
A process remembers to whom it gives the SharedVar. This is the process's best guess as to the current owner of the SharedVar. Each process has its own best guess as to who currently owns every SharedVar. When a process wants a lock on a SharedVar, it sends a request message to the process it thinks owns the SharedVar. If that process is not the owner, that process forwards the request to whomever it thinks may own it. It is guaranteed that a request following this chain will eventually reach the true owner. When the message gets to the process that actually owns the SharedVar, several things can happen:
- If the process does not have the lock on the SharedVar, it immediately gives up ownership to the requesting process.
- If it does have the lock, it places the lock request in a queue.
- When the process unlocks the SharedVar, a response is made to the first request in the queue. The rest of the queue is transferred along with the SharedVar.
Individual ownership of every SharedVar makes most operations straightforward -- except for leave. When a process wishes to gracefully disconnect from the group of processes that are sharing the NDO, it must ensure that it is not the owner of any SharedVars and that nobody thinks it is the owner of any SharedVars. When NDO.leave() is called, the process first obtains a lock on the NDO object. It then removes itself from the NDO's list of workers. If there are no other workers, nothing else must be done; the program can simply exit. Otherwise, a worker is selected from the list, and is given ownership of all of the SharedVars that the departing process owns. Then a message is sent out to every worker indicating that the departing process is leaving. Each worker must check to see if it has the departing process as its best guess for the ownership of any SharedVars. If a worker thinks the departing process owns a SharedVar, it sends a message asking who the departing process thinks owns the SharedVar. The departing process responds with who it thinks owns the SharedVar. When the worker is satisfied, it tells the departing process. When the departing process knows that all the other workers are satisfied, it transfers ownership of the NDO object to the worker (to which it gave all of its other SharedVars). Finally, the departing process can exit, since no other process will ever need to communicate with it again.
NDOs and Distributed Applications
Making an application distributed involves identifying which variables are parts of the shared state, then moving them into a common location. Since the NDO package defines types similar to the basic Java types, conversion of individual data items is straightforward. Still, two issues that must be addressed are synchronization and granularity.
The synchronization problem is similar to what you encounter when writing a multithreaded, nonnetworked application. NDOs simplify matters by reordering the lock requests of the fields by their indexes so that deadlock conditions cannot occur. You simply have to ensure that the application unlocks things once it is done with them. Since frequent passing of a lock reduces performance, data should be structured so that multiple processes are unlikely to need a lock on the same object at the same time.
Granularity is primarily a design issue. Remember that all data stored in a single SharedVar is retransmitted every time it is changed. If it is common for only a small part of the data to be changed, it is appropriate to make a SharedContainer, which will contain individual SharedVars. Remember that SharedContainers need only be transmitted when their data changes, which primarily occurs when a field is added or removed. For example, in the SimulEdit application, every line is a SharedString, and all lines are contained within a SharedVector. We could have implemented the application by making the entire buffer one SharedVar, but that would have required that each process get a lock on the entire buffer each time they want to modify anything. We could also have gone the other way, toward fine granularity, by having each line consist of a SharedVector of SharedChars. At the top level would be another SharedVector, which would contain the individual lines. Not only would that waste space, but it would also be inefficient in terms of transmission time, considering that editors are rarely used to modify characters. Instead, users delete old characters, then insert new ones, which means that a lock on the entire line would be required anyway. For SimulEdit, proper granularity was easy; other applications might require more thought.
The SimulEdit Application
SimulEdit is a text editor that lets users edit a single file at a time, à la the Windows Notepad. Cut-and-paste and search-and-replace are not implemented. However, SimulEdit does have a cursor that remembers what column it is supposed to be on, even if it is moved between lines of varying length.
Users can create new files, read files from disk, or join an already existing editing session. Users can save a copy of the current file to disk. Other people are not prevented from modifying the file while one user is saving it, so users are not guaranteed to have the most up-to-date version of the file. The process can leave the NDO at any time if users close the file or quit the application.
The editor screen has a menu bar, text grid (with its associated scroll bars), and status bar. The status bar, which displays messages, is important because it displays the address of the editor, which other people need to join in the editing session.
The editor consists of about nine classes -- 2800 lines, 75 KB of source code, 50 KB of compiled bytecode. Most of our difficulty was in getting the Java Abstract Window Toolkit (AWT) to work consistently on multiple platforms. We first developed the editor for a single machine, then modified it to be distributed by using an NDO to store the data. It took only an hour or two to modify the editor to use the full NDO. When we ran a second editor and joined it to the first, things worked almost as expected, with most of the bugs being in the NDO rather than in the editor or the interface between the editor and the NDO. This is a testament to the simplicity of converting single-user applications to distributed ones using NDOs.
The Role of the NDO Package
We chose to store each line of text in the editor as a SharedString, and to store all of the strings in one SharedVector; see Listing Three. Next, we had to decide how we would represent the cursors. A cursor has an integer for its line, an integer for its column, and other information (such as color). Since it was unlikely that the editor would ever lock a cursor's line without locking its column (or vice versa), we decided that all of the information relevant to one cursor should be stored in a single SharedVar. We accordingly subclassed SharedVar to create a SimulEdit Shared Cursor (SEditSCursor). We then created an NDO (SEditNDO) that would represent an editable file. It contains the list of lines, list of cursors, and a SharedString for the file name. This is a reasonable way to lay out data for any editor that wishes to keep each file as a separate object, regardless of whether the editor is networkable.
The NDO model makes the networking decisions straightforward. We no longer have to worry about deadlock, and ensuring that the application has the latest copy of the data is as simple as locking the field. There is a price, however, for not having to worry about deadlock: The application cannot lock one variable, then lock another without unlocking the first. This means that the application cannot lock one variable on the basis of the value of another. For example, when a user presses a key, that character should be inserted into the line the cursor is on. The application cannot know the location of the cursor for sure until it locks the cursor. Once the cursor is locked, the application knows which line to lock, but nothing else can be locked without first releasing the lock on the cursor. Once the application releases the lock on the cursor, the cursor may move to another line. The application cannot assume that the line the cursor was originally on is still the correct one -- perhaps another user inserted a line and all the line numbers have been shifted up by one. If the application naively inserts a character into the line where the cursor used to be, it would seem to the user as if the character was inserted into the line above the cursor! Our solution is to look at the current cursor position for a guess of which line to lock. Then, the application locks both the cursor and the line corresponding to this guess of the cursor position. If the cursor is not on the locked line, this process can be repeated with the cursor's new position as the guess of the current line. Fortunately, the NDO handles data in such a way that this kind of locking and relocking will usually be fast. Success is not guaranteed with this method, since every time the application releases the cursor to try again, another user could insert a new line, moving the cursor. This is not likely to happen in a text editor. If this were a serious problem, the application could lock all lines, which would be expensive, but would guarantee success.
The greatest difficulty we experienced when converting the application to a distributed one was that in a single-user editor, only one user can modify the data. When the editor becomes networked, however, other users may modify the data. Our application was not updating the screen properly when remote users made a change. We solved this by updating the screen on any change to the data, instead of just on actions by the local user.
In the current implementation, some major improvements could be made in how the screen is updated. Currently, the NDO sends an update notification any time a SharedVar is changed. However, there is currently no way of finding out how the SharedVar has changed. This is a bit of a problem in a SharedContainer, since we have no way of knowing what variables were added or deleted, or even how many. Thus, the entire screen must be redrawn every time the editor gets a notification that a line may have been inserted or deleted.
Lessons Learned
We learned a lot about writing distributed applications and the pitfalls of the Java AWT. Not surprisingly, the largest cross-platform inconsistencies in the Java environment are those that interface with the hardware. We had difficulties with differences in implementation in both the java.net and java.awt packages. When you write a Java program that is intended to run on more than the development machine, careful testing is necessary on a variety of platforms and Java Virtual Machine implementations.
Because of the peculiarities of focus on different platforms (especially Win32), we manually manage the focus in the Join dialog box. Instead of assuming that the AWT will give the focus to the appropriate component, the application saves, in a member variable of the dialog named m_compCurrentFocus, a reference to the component that should have the focus. To ensure that the proper component has the focus, we call m_compCurrentFocus.requestFocus();. The application gives the focus to the first TextField as soon as the dialog is shown, so that users can begin typing immediately. Any time the focus changes to a component that the application doesn't believe is correct (such as the dialog frame or one of the panels used to organize the components), the application explicitly gives the focus to the correct component. When users click in a component that can receive the focus, m_compCurrentFocus is set to point to that component. If, however, users click on a component that cannot have the focus (such as the dialog background), the focus stays put.
Java components do not have the concept of a tab ring -- the mechanism that Windows uses to allow presses of the Tab key to move between dialog box fields. Since we are keeping track of focus, we can also catch Tab and Shift-Tab presses and switch the focus to the next, or previous, component.
There is a bug in some Win32 implementations where clicking in a TextField does not produce the GOT_FOCUS event as it should. Therefore, any time a key is pressed in a TextField, we also update m_compCurrentFocus.
Another "feature" in some Win32 implementations is that a peer's handleEvent() is not called until after the parent's handleEvent(). Unfortunately, the Java specification does not say when a peer's handleEvent() is called. This makes it important for your handleEvent() methods to check not only the event's ID, but also the event's target. Since the TextField's peer has to get the KEY_PRESS event to actually add a letter, the KEY_PRESS event must travel not only through the dialog's handleEvent() but also through the dialog's parent frame's handleEvent(). This was a problem when our editor frame was handling all key presses (and just eating them when there was no open file). We had to modify the editor frame's handleEvent() so that it passed on KEY_PRESS events when the event's target was a TextField.
When presenting users with a modal dialog, we want the main loop to wait for users to dismiss the dialog, then take further action based on what users entered. We cannot block the event-handling thread to wait for the dialog box, since that will lock up some implementations of the Java AWT. (An exception is the FileDialog, whose show() method does block until the dialog is dismissed.) One solution is to pass the dialog a reference to its parent, then have the dialog invoke a callback when it is dismissed. A better solution, which we used in SimulEdit, is to have the dialog post an event to the parent. This is good since the dialog doesn't have to know anything about the parent, and the parent doesn't have to implement any special interfaces. All event processing remains in the event loop instead of scattered around in extra functions, and the parent gets a convenient reference to the dialog (in the target of the event) that it can use to extract the user's input from the dialog. Since the Join dialog handles all events targeted at itself, the parent frame knows that any events it receives are messages from the dialog. When the dialog is dismissed, it posts an ACTION_EVENT to the parent with itself as the target. The parent frame can then act upon the user's response to the dialog; see Listing Four.
The StatusBar often tells users when the application is busy. Since repaint() requests are not acted upon immediately, the message may never appear if the VM is kept busy in another thread. What good is a "busy" message if it never appears? We would like the StatusBar to be repainted immediately. Calling update() on a component will make it immediately paint itself, which is what we want. To call update(), we must pass a Graphics object as the argument. We can usually get a component's Graphics by calling getGraphics(). Unfortunately, this call sometimes fails: If a component's peer does not exist, the call to getGraphics() will return null. In this case, there is nothing more we can do but wait, so we call repaint() instead; see Listing Five.
Another component that must worry about its peer is the TextGrid. To create an off-screen image, the peer must exist. Otherwise, the call to createImage() will return null. Until the off-screen image is created, any characters placed in the text grid must be stored in a less convenient way. We want to know as soon as possible when we can create the off-screen image, which means we want to know when the peer is created. The solution is to override addNotify(). addNotify() is called to add the peer to a Component. It is important that we call super.addNotify() so the peer actually does get created. Once the peer exists, we can successfully create the off-screen image; see Listing Six.
When we were creating the SEditNDO, we wanted to create an NDO that held an entire file and all of its associated information. We also tried to encapsulate some of the NDO-specific tasks into the class.
First, we created a class that extended NDO. This gave us all the network functionality. Since the default constructor and the joining constructor had to do similar initialization, we separated this common code into another method, init(). In the joining constructor, the NDO requires a Place. Since the users think of Places as Strings, we decided that the SEditNDO constructor should take a String and convert it into a Place for use by the superclass NDO.
Next, we implemented makeFields(), the one abstract method in class NDO. We added the name, the cursor list, and the line list to the NDO, and added one line to the line list to create an empty file. Once this step has been completed, we have a usable (though not useful) NDO.
The init() method adds a new cursor to the cursor list. We do this for both constructors because every editor needs its own cursor. Overriding NDO.leave() is not usually necessary, but since we added a cursor when we started editing, we need to remove it when we stop editing. Overriding leave() ensures that our cursor will be removed at the right time. To create a cursor, we first lock the cursor list. Then we construct a new SEditSCursor with the cursor list as its parent, saving a reference to the new cursor for later use. Finally, we unlock the new cursor, since SharedVars are always created in a locked state, and we unlock the cursor list.
The SEditNDO has many accessor methods to make life easier for the editor. For example, the editor will often want to get the user's cursor. The user's cursor is one of many stored in a list. To make things faster, reference to the user's cursor is saved so we don't have to look it up every time. The cursor() method of the SEditNDO returns the user's cursor without requiring that the editor know anything about the list of cursors.
Finally, readFile() and writeFile() were written as part of SEditNDO to make loading and saving easy operations for the editor. readFile() locks all the lines and cursors in the SEditNDO. All of the cursors are repositioned to the start of the document, and all lines currently in the document are removed. Then lines are read one at a time from the InputStream passed into the readFile() method by the editor. For each line, a SharedString is constructed and added to the list of lines in the SEditNDO. Once all of the lines in the file have been read, all of the SharedVars (lines and cursors) are unlocked, and all the other processes find out what happened. writeFile() is simpler. Every line in the line list is written to an OutputStream passed in as an argument. Since it doesn't lock the lines, other users may make changes while the write is occurring. In an editor, however, this is not likely to happen, and the savings in overhead is large.
Acknowledgments
We used the info.net package for our message transport layer. The info.net package is part of the Infospheres Project, a study of the systematic composition ("plugging together") of persistent active objects, being developed under Dr. Mani Chandy at the California Institute of Technology. This work was supported in part by NSF grant CCR-9527130.
DDJ
Listing One
Class SharedVar
</p>
</p>
import java.io.DataOutputStream;
import java.io.DataInputStream;
import java.io.IOException;
</p>
public class SharedInt extends SharedVar {
int _data;
SharedInt() {
super();
_data = 0;
}
public SharedInt(SharedContainer parent) {
super(parent);
_data=0;
}
public synchronized void readData(DataInputStream dis) throws IOException {
_data=dis.readInt();
}
public synchronized void writeData(DataOutputStream dos) throws IOException {
dos.writeInt(_data);
}
public synchronized void set(int data) {
if (!locked()) throw new FieldNotLockedException("SharedInt not locked.");
if (_data != data) {
_data=data;
setModified();
}
public synchronized int get() {
return _data;
}
}
Listing Two
Locking fieldspublic class MyProgram {
private MyNDO ndo;
void doSomething() throws FieldDeletedException {
ndo.startLock();
ndo.field(0).lock();
ndo.completeLock(); //This call will throw the FieldDeletedException if
// field 0 of the NDO no longer exists
((SharedInt)ndo.field(0)).set(10);
//SharedInt.set() calls setModified()
ndo.field(0).unlock();
}
}
Listing Three
boolean bRetry;do {
bRetry=false;
</p>
// Lock what we need
int nLine=0;
SharedString sszLine=null;
while (true) {
nLine=sscMyCursor.getLine();
sszLine=m_seNDO.getLineObject(nLine);
m_seNDO.startLock();
scCursorList.lockAll();
sszLine.lock();
try {
m_seNDO.completeLock();
break;
} catch (FieldDeletedException e) {
// That's OK, try again.
}
}
// make sure we get the line that the cursor is ACTUALLY on.
int nCursLine=sscMyCursor.getLine();
if (nCursLine!=nLine){
bRetry=true;
} else {
// Do whatever you want to with the line and the cursors
}
scCursorList.unlockAll();
sszLine.unlock();
} while (true==bRetry);
Listing Four
//-----------------------------------------------// Clean up ASAP - inform parent that we've been dismissed
private void quit() {
hide();
dispose();
getParent().postEvent(
new Event(this, Event.ACTION_EVENT, null));
}
Listing Five
// update as soon as possibleGraphics g=getGraphics();
if (null==g) {
repaint();
} else {
update(g);
}
Listing Six
//------------------------------------------------------------------// (override) When this is called, we can finally create the buffer.
public void addNotify() {
super.addNotify();
if (null==m_imOffscreen) {
createOffScreenBuffer();
}
}
//------------------------------------------------------------------
// We can't create an image until peer has been created
private void createOffScreenBuffer() {
Assert.isNull(m_imOffscreen);
// Create the image
m_imOffscreen=createImage(m_dCanv.width, m_dCanv.height);
if (m_imOffscreen==null) {
throw new RuntimeException(
"TextGrid can't create offscreen image.");
}
// ... initialize, etc.
}
Copyright © 1998, Dr. Dobb's Journal