VAXclusters: A Closely-Coupled
Distributed System
NANCY P. KRONENBERG, HENRY M. LEVY, and WILLIAM D. STRECKER
Digital Equipment Corporation

A VAXcluster is a highly available and extensible configuration
of VAX computers that operate as asingle system. To achieve performance in a multicomputer
environment,a new communications
architecture, communications hardware, and distributed software were jointly designed. The software
is a distributed version of the VAX/VMS
operating system that uses a distributed lock manager tosynchronize access to shared resources. The communications
hardware includes a 70 megabit per
second message-oriented interconnect and an interconnect port that performs communications tasks
traditionallyhandled by software. Performancemeasurements show this structure to be highly
efficient, for example, capable of sending and receiving 3000 messages per second on a VAX-11/780.

Networks]: Local NetCategories and Subject Descriptors: C.2.5 [Computer Communications
works-buses;
D.4.3 [Operating
Systems]: File Systems Management-distributed
file systems;
D.4.4 [Operating Systems]: Communications
Management; D.4.5 [Operating Systems]: Reliability-fault-tolerance;
D.4.7 [Operating Input/Output
Systems]: Organization and Design-performance
General Terms: Design, Performance,

Reliability

Additional
Key Words and Phrases: Device control protocols, distributed
intersystem communication protocols, network protocols, resource locking

database management,

1. INTRODUCTION
Contemporary multicomputer systems typically lie at the ends of the spectrum
delimited by tightly-coupled multiprocessors and loosely-coupled distributed
systems. Loosely-coupled systems are characterized by physical separation ofprocessors, low-bandwidth message-oriented inter-processor communication, andindependent operating systems [l, 2, 5, 131. Tightly-coupled systems are characterized by close physical proximity of processors, high-bandwidth communication through shared memory, and a single copy of the operating system[7,9, 151.
An intermediate approach taken at Digital Equipment Corporation was tobuild a “closely-coupled” structure of standard VAX computers [16], called
VAXc1uster.s.By closely-coupled, we imply that a VAXcluster has characteristics
of both loosely- and tightly-coupled systems. On one hand, a VAXcluster has
separate processors and memories connected by a message-oriented interconnect,
running separate copies of a distributed VAX/VMS operating system. On the
Authors’ addresses: N. P. Kronenberg and W. D. Strecker, Digital Equipment Corporation, 295 Foster
Street, Littleton, MA 01460; H. M. Levy, Department of Computer Science, University of Washington,
Seattle, WA 98195.
Permission to copy without fee all or part of this material is granted provided that the copies are notmade or distributed for direct commercial advantage, the ACM copyright notice and the title of the
publication and its date appear, and notice is given that copying is by permission of the Association
for Computing Machinery.
To copy otherwise, or to republish, requires a fee and/or specificpermission.
0 1986 ACM 0734-0261/86/0500-0130$00.75
ACM Transactions on Computer Systems, Vol. 4, No. 2, May 1986, Pages 130-146.

VAXclusters: A Closely-Coupled Distributed System

131

other hand, the cluster relies on close physical proximity, a single (physical andlogical) security domain, shared physical access to disk storage, and high-speed
memory-to-memory block transfers between nodes.
The goals of the VAXcluster multicomputer system are high availability andeasy extensibility to a large number of processors and device controllers. In
contrast to other highly available systems [3,4, 10, 111, VAXcluster is built fromgeneral-purpose, off-the-shelf processors and a general-purpose operating system.
A key concern in this approach is system performance. Two important factors in
the performance of a multicomputer system are the software overhead of thecommunications architecture and the bandwidth of the computer interconnect.
To address these issues, several developments were undertaken, including:(1) A simple, low-overhead communications architecture whose functions are
tailored to the needs of highly available, extensible systems. This architecture
is called SCA (System Communication Architecture).
(2) A very high speed message-oriented computer interconnect, termed the CI(Computer Interconnect).
(3) An intelligent hardware interface to the CI, called the CI Port, that implements part of SCA in hardware.
(4) An intelligent, message-oriented mass storage controller that uses both the
CI and the CI Port interface.
This paper describes the new communications hardware developed for VAXclusters, the hardware-software interface, and the structure of the distributed VAX/VMS operating system. The developments described in this paper are part ofDigital’s VAXcluster product; there are, as of early 1985, approximately 2000
VAXcluster systems in operation.
2. VAXcluster

HARDWARE STRUCTURE

Figure 1 shows the topology of an example VAXcluster. The components of a
VAXcluster include the CI, VAX hosts, CI Ports, and HSC-50 mass storage(i.e., disk and tape) controllers. For high reliability applications, a cluster must
contain a minimum of two VAX processors and two mass storage controllers
with dual-ported devices. The preferred method of attaching terminals is througha Local Area Terminal server (not shown in the figure), which allows a terminal
to connect to any host in a VAXcluster.
The CI is a dual path serial interconnect with each path supporting a 70
Mbit/s transfer rate. The primary purpose of the dual paths is to provide
redundancy in the case of path failure, but when both paths are available they
are usable concurrently. Each path is implemented in two coaxial cables: one fortransmitted and one for received signals. Baseband signaling with Manchester
encoding is employed.
While the CI is logically a bus, it is physically organized as a star topology. A
central hub called the Star Coupler connects all of the nodes through radial CI
paths of up to 45 meters. The current coupler is a passive device that supports a
maximum of 16 nodes; node addresses are 8 bits providing an architectural limitof 256 nodes.
The selection of a star topology was chosen over a conventional linear topology
for several reasons. First, the efficiency of a serial bus is related to the longest
ACM Transactions on Computer
Systems, Vol. 4, No. 2, May 1986.

132

l

N. P. Kronenberg, H. M. Levy, and W. D. Strecker

I

I

VAX

44
CI PortCI

Fig. 1. VAXcluster
topology.

--I

CI Porthardware
CI PortCI Port

HSC-50
Disk
System

HSC-50
Disk
SystemStorageconuollers

transit time between nodes. The star permits nodes to be located within a 45
meter radius (about 6400 square meters) with a maximum node separation of 90
meters. Typically, a linear bus threaded through 16 nodes in the same area would
greatly exceed 90 meters. Second, the central coupler provides simple, electricallyand mechanically safe addition andremoval of nodes.
The CI port is responsible for arbitration, path selection, and data transmission. Arbitration uses carrier sense multiple access (CSMA) but is different fromthe arbitration used by Ethernet [12]. Each CI port has a node-specific delay
time. When wishing to transmit, a port waits until the CI is quiet and then waits
its specific delay time. If the CI is still quiet the node has won its arbitration andmay send its packet. This scheme gives priority to nodes with short delay times.
To ensure fairness, nodes actually have two delay times-one relatively shortand one relatively long. Under heavy loading, nodes alternate between short andlong delays. Thus, under light loading the bus is contention driven and underheavy loading it is round robin.
When a port wins an arbitration, it sends a data packet and waits for receipt
of an acknowledgement. If the data packet is correctly received, the receiving
port immediately returns an acknowledgement packet without rearbitrating the
CI. This is possible because the CI port can generate an acknowledgement in lesstime than the smallest node-specific delay. Retries are performed if the sending
CI port does not receive an acknowledgement.
To distribute transmissions across both paths of the dual-path CI, the CI port
maintains a path status table indicating which paths to each node are currently
ACM Transactions on Computer Systems, Vol. 4, No. 2, May 1986.

VAXclusters: A Closely-Coupled Distributed Systeml133

good or bad. Assuming that both paths are marked good, the CI port chooses one
randomly. This provides statistical load sharing and early detection of failures.
Should repeated retries fail on one path, that path is marked bad in the status
table and the other path is tried.
3. THE Cl PORT ARCHITECTURE
Each cluster host or mass storage controller connects to the CI through a CI
port. CI ports are device specific and have been implemented for the HSC-50
mass storage controller and the VAX 11/750, VAX 11/780, VAX 11/782, VAX
11/785, and VAX/8600 hosts. All CI ports implement a common architecture,
whose goals are to:(1) Offload much of the communications
overhead typically performed by nodes
in distributed systems.
(2) Provide a standard, message-oriented software interface for both interprocessor communication and device control.
The design of the CI port is based on the needs of the VMS System Communications Architecture.
SCA is a software layer that provides efficient communications services to low-level distributed applications (e.g., device drivers, fileservices, and network managers). SCA supports three communications
services:
datagrams, messages, and block data transfers.
SCA datagrams and messages are information units of less than 4 kbytes sent
over a connection. They differ only in reliability.
Delivery of datagrams is notguaranteed; they can be lost, duplicated, or delivered out of order. Delivery of
messages is guaranteed, as is their order of arrival. Datagrams are used for status
and information messages whose loss is not critical, and by applications such as
DECNET that have their own high-level reliability protocols. Messages are used,
for example, to carry disk read and write requests.
To simplify buffer allocation, hosts must agree on the maximum size of
messages and datagrams that they will transmit. VAXcluster hosts use standard
sizes of 576 bytes for datagrams and 112 bytes for messages. These sizes are
keyed to the needs of DECNET and the lock management protocol, respectively.
To ensure delivery of messages without duplication
or loss, each CI port
maintains a virtual circuit with every other cluster port. A virtual circuit descriptor table in each port indicates the status of its port-to-port
virtual circuits.
Included in each virtual circuit descriptor are sending and receiving sequencenumbers. Each transmitted message carries a sequence number enabling duplicate
packets to be discarded.
Block data is any contiguous data in a process’ virtual address space. There isno size limit except that imposed by the virtual and physical memory constraintsof the host. CI ports are capable of copying block data directly from process
virtual memory on one node to process virtual memory on another node.
Delivery of block data is guaranteed. The sending and receiving ports cooperate
in breaking up the transfer into data packets and ensuring that all packets arecorrectly transmitted, received, and placed in the appropriate destination buffer.
Virtual circuit sequence numbers are used on the individual packets, as withmessages. Thus, the major differences between block data and messages are the
ACM Transactions

on Computer

Systems, Vol. 4, No. 2, May 1986.

134

l

N. P. Kronenberg, H. M. Levy, and W. D. Strecker

size of the transfer and the fact that block data does not need to be copied by
the host operating system. Block data transfers are used, for example, by disk
subsystems to move data associated with disk read and write requests.
3.1 Cl Port Interface

The VAX CI Port interface is shown in Figure 2. The interface consists of a setof seven queues: four command queues, a response queue, a datagram free queue,
and a message free queue. The queues and queue headers are located in hostmemory. When the port is initialized, host software loads a port register with theaddress of a descriptor for the queue headers.
Host software and the port communicate through queued command andresponse packets. To issue a port command, port driver software queues acommand packet to one of the four command queues. The four queues allow for
four priority levels; servicing is FIFO within each queue. An opcode within thepacket specifies the command to be executed. The response queue is used by the
port to enqueue incoming messages and datagrams, while the free queues are asource of empty packets for incoming messages and a sink for transmitted
messagepackets.
For example, to send a datagram, software queues a SEND DATAGRAM packet
onto one of the command queues. The packet contains an opcode field specifying
SEND DATAGRAM, a port field containing the destination port number, thedatagram size, and the text of the datagram. The packet is doubly linked throughits first two fields. This structure is shown in Figure 3.
If host software needs confirmation when the packet is sent, it sets a response
queue bit in the packet. This bit causes the port to place the packet in the
response queue after the packet has been transmitted. The response packet is
identical to the SEND DATAGRAM packet, except that the status field indicates
whether the send was successful. Had the response queue flag bit been clear in
the SEND DATAGRAM command (as it typically is), the port would instead place
the transmitted command packet on the datagram free queue.
When a CI port receives a datagram, it takes a packet from its datagram freequeue. Should the queue be empty, the datagram is discarded. Otherwise, theport constructs a DATAGRAM RECEIVED packet that contains the datagram text
and the port number of the sending port. This packet is then queued on the
response queue.
Messages operate in a similar fashion, except that they have a different opcodeand message buffers are dequeued from the message free queue. If the message
free queue is empty when a message arrives, the port generates an error interrupt
to the host. High level SCA flow control ensures that the message free queue
does not become empty.
Block transfer operations are somewhat more complicated. Each port has adata structure called a buffer descriptor table. Before performing a block transfer,host software creates a buffer descriptor that defines the virtual memory buffer
to be used. The descriptor contains a pointer to the first VAX page table entry
mapping the virtually contiguous buffer. In addition, the descriptor contains theoffset (within the first page) of the first byte of the buffer, the length of thebuffer, and a 16-bit key. The data structures for a block transfer are illustrated
in Figure 4.
ACM Transactions

on Computer

Systems, Vol. 4, No. 2, May 1986.

VAXclusters: A Closely-Coupled Distributed System

135

command queue 0bcommand queue 3

b

I I I

VAX
Port
Softwareresponse queue- c:+---TEE-b PO:

datagramfkequeuet3

message free queueb

BufferDescriptor
Table

l

VAX Memory
Fig. 2.

CI Port interface.

Fig. 3.

Example CI Port command packet.

Datagram Text

Each buffer has a 32-bit name. The name consists of a 16-bit buffer descriptor
table index and the 16-bit buffer key. The key is used to prevent danglingreferences and is modified whenever a descriptor is released. To transfer block
data, the initiating
software must have the buffer names of the source anddestination buffers. The buffer names are exchanged through a high level message
protocol. A host can cause data to be moved either to another node (SEND DATA)
orfromanothernode(REQUESTDATA).
A SENDDATAO~REQUESTDATA~O~~~~~
packet contains the names of both buffers and the length of the transfer. In
ACM Transactions on Computer Systems, Vol. 4, No. 2, May 1986.

136

N. P. Kronenberg, H. M. Levy, and W. D. Strecker

l

I
I I
CI

CI PortCommand
Queue
/

F

Page
Table

\

queue links
flags opcodc
port no. statustrans.size
sourcebuffer namedest.buffername

descriptor

I

i
Pages

Block Transfer
Port Command

Host Memory
Fig. 4. CI Port block data memory mapping.

either case (send or request), a single command packet causes the source anddestination ports to perform the block transfer. When the last packet has beensuccessfully received, the initiating port places a response packet on its response
queue indicating that the transfer is complete.
The goal of reducing VAX host interrupts is met through several strategies
and mechanisms. First, the block transfer mechanism minimizes the number ofinterrupts necessary to transfer large amounts of data. Second, at the sending
port, DATAGRAM SENT/MESSAGE
SENT confirmation
packets are typically generated only when a failure occurs. Third, a receiving port interrupts the VAX only
when it queues a received packet on an empty response queue. Thus, whensoftware dequeues a packet in response to an interrupt, it always checks for more
packets before dismissing the interrupt.
4. MASS STORAGE

CONTROL

The move from Control and Status Register activated storage devices to messageoriented storage devices offers several advantages, including:(1) Sharing is simplified. Several hosts can queue messages to a single controller.
In addition, device control messages can be transmitted to and executed byhosts with local disks.
ACM Transactions

on Computer

Systems, Vol. 4, No. 2, May 1986.

VAXclusters: A Closely-Coupled Distributed System

137(2) Ease of extension to new devices. In contrast to conventional systems, where
there is a different driver for every type of disk and disk interface, a single
disk class driver simply builds message packets and transmits them using acommunications
interface. The disk class driver is independent of drive
specifics (e.g., cylinders and sectors). New disk and tape devices and controllers can be added with little or no modification to host software.
(3) Improved performance. The controller can maintain a queue of requests frommultiple hosts and can optimize disk performance in real time. The controller
can also handle error recovery and bad block replacement.
The HSC-50 (Hierarchical Storage Controller), shown in Figure 1, is the firstCI-based controller for both disks and tapes. A single HSC controller can handle
up to 24 disk drives. Multiple HSCs with dual-ported disks provide redundancy
in case of failures.
The protocol interpreted by the HSC is called the Mass Storage Control
Protocol (MSCP). The MSCP model separates the flow of control and status
informationfrom the flow of data. This distinction
has been used in othersystems to achieve efficient file access [6] and corresponds to the CI port’s
message and block data mechanisms; messages are used for device control
commands while block transfers are used for data.
For example, to perform a disk read, the disk class driver transmits an MSCPREAD message to the controller using a CI port SEND MESSAGE command. The
read request contains the device type and unit number, the device media address(e.g., the disk logical block number), the 32-bit buffer name of the requester’s
buffer, and the length of the transfer. To process the request, the controller reads
the specified data from disk and transmits it directly to host memory using a CI
port SEND DATA command. When the data is successfully transferred, thecontroller sends a message to the host driver indicating the completion status of
the request.
The same control protocol is used to provide cluster-wide access to CI-based
controllers such as the HSC, and to Unibus or Massbus disks connected privately
to a VAX node. Messages are routed from the disk class driver in the requestingnode to an MSCP server on the node with the private disk. This server thenparses the MSCP message, issues requests to its local disk, and initiates theblock transfer through its SCA interface.
5. VAXcluster SOFTWARE
From a user’s point of view, a VAXcluster is a set of nodes cooperating through
VAX/VMS distributed operating system software to provide sharing of resourcesamong users on all nodes. Shared resources include devices, files, records, andbatch and print services. Typically,user account and password information
resides in a single file shared by all cluster nodes. A user obtains the sameenvironment (files, default directory, privileges, etc.) regardless of the node towhich he or she is logged in. In many respects the VAXcluster feels like a single
system to the user.
Figure 5 shows an example of a small VAXclusterand some of the major
software components. At the highest level, multiple user processes on each node
ACM Transactions

on Computer

Systems, Vol. 4, No. 2, May 1986.

138

N. P. Kronenberg, H. M. Levy, and W. D. Strecker

l

HSCJO

,+izs-lFig. 5.

VAXc1ust.m software

structure.

execute in separate address spaces. File and record management services are
implemented as procedure-based code within each process.
The file and record services rely on lower level primitives such as the lock
manager and disk class driver. The lock manager is the foundation of all resource
sharing in both clustered and single-node VMS systems. It provides services fornaming, locking, and unlocking cluster-wide resources. The disk class driver,
mentioned earlier, uses MSCP to communicate with disk servers. The disk classdriver runs in both clustered and nonclustered environments and contains noknowledge of the VAXcluster. SCA software below the driver is responsible forrouting driver messagesto the correct device controller.
Cluster connection rnunagers are responsible for coordinating the cluster.
Connection managers on all cluster nodes collectively decide upon cluster membership, which varies as nodes leave and join the cluster. Connection managers
recognize recoverable failures in remote nodes; they provide date transfer services
that handle such failures transparently to higher software levels.
ACM Transactions

on Computer

Systems, Vol. 4, No. 2, May 1986.

VAXclusters: A Closely-Coupled Distributed Systeml

139

5.1 Forming a Cluster

A VAXcluster is formed when a sufficient set of VAX nodes and mass storage
resources become available. New nodes may boot and join the cluster, andmembers may fail or shut down and leave the cluster. When a node leaves or
joins, the process of reforming the cluster is called a cluster transition. Clustertransitions are managed by the connection managers.
In an operating cluster, each connection manager has a list of all member
nodes. The list must be agreed upon by all members. A single node can be amember of only one VAXcluster; in particular, the same resource (such as a disk
controller) cannot be shared by two clusters or the integrity of the resources
could not be guaranteed. Therefore, connection managers must prevent thepartitioning of a cluster into two or more clusters attempting to share the same
resources.
To prevent partitioning, VMS uses a quorum voting scheme. Each cluster nodecontributes a number of votes and the connection managers dynamically computethe total votes of all members. The connection managers also maintain a dynamic
quorum value. As transitions occur, the cluster continues to run as long as thetotal votes present equals or exceeds the quorum. Should the total votes fall
below the quorum, the connection managers suspend process activity throughout
the cluster. When a node joins and brings the total votes up to the quorum,processes continue.
Initial vote and quorum values are set for each node by a system manager, andcan be used to determine the smallest set of resources needed to operate as a
VAXcluster. In order to start the cluster, each node contains an initial estimateof what the quorum should be. However, as nodes join, connection managers
increase the quorum value, if necessary, so it is at least (V + 2)/2, where V is thecurrent vote total.
A cluster member may have a recoverable error in its communications, that is,
one that leaves the node’s memory intact and allows the operating system tocontinue running after the error condition has disappeared. Such errors cancause termination of a virtual circuit and a corresponding loss in communication.
When cluster members detect the loss of communication with a node, they wait
for a short period for the failing member to reestablish contact. The waiting
period is called the reconnect interval and the system manager sets it, usually toabout a minute. If the failing member recovers within the reconnect interval, it
rejoins the cluster. During the time the failing member is recovering, someprocesses experience a delay in service. If the failing member does not rejoin
within the reconnect interval, surviving members remove it from the cluster andcontinue if sufficient votes are present. A node that recovers after it has been
removed from the cluster is told to reboot by other connection managers.
5.2 Shared Files

The VAXcluster provides a cluster-wide shared file system to its users. Cluster
accessible files can exist on CI-based disk controllers or on disks local to any of
the cluster nodes (e.g., connected via Unibus or Massbus). Each cluster disk has
a unique name. A complete cluster file name includes the disk device name, thedirectory name, and the file name. Using the device name for a file, cluster
ACM Transactions

on Computer

Systems, Vol. 4, No. 2, May 1986.

140

l

N. P. Kronenberg, H. M. Levy, and W. D. Strecker

software can locate the node (either CPU or disk controller) on which the file
resides.
Cluster file activity requires synchronization:
exclusive-write
file opens, coordination of tile system data structures, and management of file system caches
are a few examples. However, despite the fact that files can be shared cluster
wide, file management services are largely unaware of whether they are executing
in a clustered environment.
The file managers synchronize through the VMS
lock manager, to be described below. It is the lock manager that handles locking
and unlocking of resources across the cluster. At the level of the file manager,
then, cluster file sharing is similar to single-node file sharing. Lower levels handle
cluster-wide synchronization
and routing of physical-leveldisk requests to thecorrect device.
5.3 Distributed

Lock Manager

As previously described, the VMS lock manager is the basis for cluster-wide
synchronization.
Several goals influenced the design of the lock manager for a
distributed environment.
First, programs using the lock manager must run inboth single node and cluster configurations.
Second, lock services must be
efficient to support system-level software that makes frequent requests. Therefore, in a VAXcluster,
the lock manager must minimize the number of SCA
messages needed to manage locks. In a single node configuration,
the lockmanager must recognize the simpler environmentand bypass cluster-specificoverhead. Finally, the lock manager must recover from failures of nodes holding
locks so that surviving nodes can continue to access shared resources in aconsistent manner.
The VMS lock manager services allow cooperating processes to define sharedresources and synchronize access to those resources. A resource can be any object
an application cares to define. Each resource has a user-defined name by which
it is referenced. The lock manager provides basic synchronization
services torequest a lock and release a lock. Each lock request specifies a locking mode,such as exclusive access, protected read, concurrent read, concurrent write, null,
etc. If a process requests a lock that is incompatible
with existing locks, therequest is queued until the resource becomes available.
The lock manager provides a lock conversion service to change the locking
mode on an existing lock. Conversions are faster than new lock requests because
the database representing the lock already exists. For this reason, applications
frequently hold a null lock (a no access place holder) on a resource and thenconvert it to a more restricted access mode later.
In many applications resources may be subdivided into a resource tree, as
illustrated in Figure 6. In this example, the resource Disk Volume contains
resources File 1 through File 3; resource File 3 contains resources Record 1 andRecord 2, and so on. The first locking request for a resource can specify theparent of the resource, thereby defining its relationshipin a tree. A process
making several global changes can hold a high-level lock (e.g., the root) and makethem all very efficiently; a process making a small low-level change (e.g., a leaf)
can do so while still permitting concurrent access to other parts of the tree [8].
ACM Transactions

on Computer

Systems, Vol. 4, No. 2, May 1986.

VAXclusters: A Closely-Coupled Distributed Systeml141

Disk Volume
Fii2/-A
RCUlIdl

Fig. 6.

FiIc3

VAXcluster

locking structure.

Record2

The lock manager’s implementation is intended to distribute the overhead oflock management throughout the cluster, while still minimizing the inter-nodetraffic needed to perform lock services. The database is therefore divided into
two parts-the resource lock descriptions and the resource lock directory system-both of which are distributed. Each resource has a master node responsible
for granting locks on the resource; the master maintains a list of granted locks
and a queue of waiting requests for that resource. The master for all operations
for a single tree is the node on which the lock request for the root was made.
While the master maintains the lock data for its resource tree, any node holding
a lock on a resource mastered by another node keeps its own copy of the resource
and lock descriptions.
The second part of the database, the resource directory system, maps a resource
name into the name of the master node for that resource. The directory databaseis distributed among nodes willing to share this overhead. Given a resource name,a node can trivially compute the responsible directory as a function of the namestring and the number of directory nodes.
In order to lock a resource in a VAXcluster, the lock manager sends a lock
request messagevia SCA to the directory for the resource. The directory respondsin one of three ways:(1) If the directory is located on the master node for the resource, it performs
the lock request and sends a confirmation response to the requesting system.
(2) If the directory is not on the master node but finds the resource defined, it
returns a response containing the identity of the master node.
(3) If the directory finds the resource to be undefined, it returns a response
telling the requesting node to master the resource itself.
In the best cases (1 and 3) two messagesare required to request a lock, whereascase 2 takes four messages.An unlock is executed with one message. If the lock
request is for a subresource in a resource tree, the requesting process will either
be located on the master node (i.e., the request is local) or will know who themaster for its parent is, allowing it to bypass the directory lookup. In all cases,
the number of messages required is independent of the number of nodes in the
VAXcluster.
In addition to standard locking services, the lock manager supports datacaching in a distributed environment. Depending on the frequency of modifications, caching of shared data in a distributed system can substantially reduce the
I/O and communications workload.
A 16-byte block of information, called a value block, can be associated with aresource when the resource is defined to the lock manager. The value in the value
block can be modified by a process releasing a lock on the resource, and read by
ACM Transactions

on Computer

Systems, Vol. 4, No. 2, May 1986.

142

l

N. P. Kronenberg, H. M. Levy, and W. D. Strecker

a process when it acquires ownership. Thus, this information can be passed alongwith the resource ownership.
As an example, assume two processes are sharing some disk data and use thevalue block as a version number of the data. Each process caches the data in a
local buffer and holds the version number of the cached data. To modify thedata, a process locks it and compares the latest version returned with the lockwith the version of the cached data. If they agree, the cache is valid, if theversions disagree, then the cache must be reloaded from disk. After modifying
the data, the process writes the modified data back to disk and releases the lock.
Releasing the lock increments the version number.
Another mechanism useful for caching data with deferred writeback is a
software interrupt option. This is similar to the Mesa file system call-backmechanism [ 141, but is used for a different purpose. When requesting an exclusive
lock, a process can specify that it should be notified by software interrupt if
another lock request on the resource is forced to block. Continuing the exampleof cached disk data, a process owning the lock can cache and repeatedly modify
the data. It writes the data back to disk and releases the lock when notified that
it is blocking another process.
In the case of cluster transitions (e.g., failure of a node), the connection
manager notifies the lock manager that a transition has started. Each lock
manager performs recovery action, and all lock managers must complete thisactivity before cluster operation can continue.
As the first step in handling transitions, a lock manager deallocates all locks
acquired on behalf of other systems. Only local lock and resource information isretained. Temporarily, there are no resource masters or directory nodes. In thesecond step, each lock manager reacquires each lock it had when the clustertransition began. This establishes new directory nodes based on a new set of
eligible cluster members and rearranges the assignment of master nodes. If anode has left the cluster, the net result is to release locks held by that node. If
no node has left the cluster but nodes have joined, this recovery is not necessary
from an integrity point of view. However, it is performed to distribute directoryand lock mastering overhead more fairly.
Some resources, depending on how they are modified, can be left in aninconsistent state by a cluster transition. One method of handling this problem
would be to mark the locks for such resources to prevent access following atransition. A special process can then search for such locks and perform needed
consistency checks before releasing them.
5.4 Batch And Print Services

In a VAXcluster, users may either submit a batch job to a queue on a particular
node (not necessarily their own node), or submit a job to a cluster-wide batchqueue. Jobs on the cluster-wide queue are routed to queues attached to specificnodes for execution. The algorithm for assigning jobs to specific nodes is a simple
one based on the ratio of executing jobs compared to the job limit of the queue.
Management of batch jobs is the responsibility of a VMS process called thejob controller. Each VMS node runs a job controller process. The process acquires
work from one or more batch queues. Batch queues are stored in a disk file that
ACM Transactions

on Computer

Systems, Vol. 4, No. 2, May 1986.

VAXclusters:

A Closely-Coupled

Distributed Systeml143

may be shared by all nodes. Synchronization of queue manipulation is handledwith lock manager services.
Print queues are similar to batch queues. Users may queue a request for a
specific printer (not necessarily physically attached to their own node) or may
let the operating system choose an available printer from those in the cluster.
Both batch and print jobs can be declared restartable. If a node fails, restartablejobs are either requeued to complete on another node in the cluster, or will
execute when the failed node reboots (for jobs that required to execute on a
specific node).
6. TERMINALSUPPORT

The optimum method for connecting users’ terminals to a VAXcluster is throughthe Local Area Terminal Server (LAT). Terminals are connected to LAT, which
is attached to VAXs by Ethernet. Users command LAT to connect them to a
specific node or to any node in the cluster. The ease of switching nodes leads
users to find and use the least busy node. It also allows users to quickly movefrom a failed node to one that is still running. If LAT is directed to select a node,
it attempts to find the least busy node. Its choice is based on node CPU type(a measure of processing power) and recent idle time.
7. PERFORMANCE

Performance of the system communications architecture (SCA) and the underlying hardware interconnect was measured using operating system processes
running on clustered VAX nodes. By operating system processes, we mean thatthese programs run at the same level as the connection manager shown in Figure
5. These processes measured the datagram, message,and block transfer throughput for various messagesizes. All numbers are approximate, as performance mayvary due to different command options.
Table I shows the CPU time used on a VAX 11/780 to send and receive a reply
to a 576-byte datagram and a 96-byte message. These sizes were used because
they were representative of the sizes used by VMS. The CPU time to initiate ablock transfer and receive the response is the same as that for a sequenced
message (i.e., 320 ps) independent of the transfer size. Round trip elapsed timeis also shown. In general, for a given transfer size the performance of datagrams
and messagesis approximately the same. The results also depend on the amountof buffering and the number of messagesqueued to the port before waiting for a
response.
Table II shows the number of message round trips per second achieved on acluster with between 2 and 12 communicating nodes. Each node was communicating with one other node; for example, in the 12 node case there were 6 pairsof communicating nodes, each pair engaged in sending and receiving a single
stream of 112-byte messages.These experiments were run on VAX 11/785 nodes.
As can be seen from Table II, the total number of messages increases nearlylinearly. Once again, performance depends on the number of messagesqueued ata time. While one message was queued at a time in this experiment, previous
experiments have shown that by queueing four messagesat a time, it is possible
to achieve 3000 message round trips per second on two VAX 11/78Os.
ACM Transactions

on Computer

Systems, Vol. 4, No. 2, May 1986.

144

-

N. P. Kronenberg,

H. M. Levy, and W. D. Strecker
Table I
Datagram

Message

Send/receive
CPU time

290 ps(576 byte)

320 ps(96 byte)

Send/receive
Round trip
Elapsed time1500 /Is(576 byte)

1000 ps(96 byte)

Table II
Numberof nodesCluster round-trip(messages/s)

2
4
6
8
10
12

1090
2170
3250
4330
5420
6480

Table III
Numberof nodesCluster block transfer
thruput (mbytes/s)

2
4
6

2.65
5.28
7.70

Table IV

Request lock
Convert lockRelease lockSingle-CPU
systemClusteredsystem

400 ps
250 ps300 ps3000 ps1000-2300 ps
700 /.ls

Throughput results are shown in Table III. In this experiment, 4 streams of
64-kbyte block transfers were initiated between 2, 4, and 6 VAX 11/785 nodes.
Again, throughput
increases almost linearly. Throughput
measurements fordatagrams and messages show that a throughput of about 2.4 Mbytes per second
can be achieved between two VAX 11/780 nodes sending 900-byte messages ordatagrams.
These throughputs do not represent real workloads, which produce less traffic
than the contrived test programs. It is clear that the 8.75 Mbyte per second (perpath) CI is not the bottleneck. For this test, we believe that the limiting factor
is the speed of the CI port and the memory bandwidth of the host. Of course, thereason for having a high-speed interconnect is to provide bandwidth for multiple
hosts.
This performance provides a basis for efficient execution of higher level
distributed
services, such as the lock manager. Table IV lists approximate
ACM Transactions

on Computer

Systems, Vol. 4, No. 2, May 1986.

VAXclusters: A Closely-Coupled Distributed Systeml145

performance values for lock operations in both clustered and nonclusteredenvironments. As previously stated, lock conversions are faster than new lock
requests because the database already exists. The measured elapsed time for aconversion depends upon the existing mode and new mode.
8. CONCLUSIONSA principal goal of VAXclusters
was the development of an available andextensible multicomputer
system built from standard processors and a generalpurpose operating system. Much was gained by the joint design of distributed
software, communications protocols, and hardware aimed to meet this goal. For
example:(1) The CI interconnect supports fast message transfer needed by system software.
(2) The CI port implements many of the functions needed by SCA software.
(3) The HSC-50 with its message protcol and request queueing optimization
logic provides direct network access to a large pool of disks for multiple hosts.
Designing hardware and software together allows for system-level tradeoffs; thesoftware interface and protocols can be tuned to the hardware devices.
An important simplifying
aspect of the VAXcluster
design is the use of a
distributed lock manager for resource synchronization.
In this way, higher levelservices such as the file system do not require special code to handle sharing ina distributed environment. However, performance of the lock manager becomesa crucial factor. Distributed lock manager performance has been attacked withthe design of a locking protocol requiring a fixed number of messages, independentof the number of cooperating nodes.
Finally, we believe that the performance measurements presented show theextent to which the VAXcluster
system has succeeded in implementing
anefficient communications
architecture. These numbers are particularly
impressive when considering that VMS is a large, general-purpose operating system.
ACKNOWLEDGMENTS

VAXclusters are the result of work done by many individuals in several engineering groups at Digital Equipment Corporation. We would particularly like toacknowledge the contributionsof Richard I. Hustvedt.
We wish to thank Bill Laing, Steve Neupauer, and Stan Amway for performance measurements reported in this paper, and Steve Beckhardt, Liz Hunt,
Jim Krycka, Christian Saether, and Dave Thiel for reviews of earlier versions of
the paper.
REFERENCES
1. ALMES, G. T., BLACK, A. P., LAZOWSKA, E. D., NOE, J. D. The eden system: A technicalreview. IEEE Trans. Softw. Eng. SE-l 1, 1 (Jan. 1985), 43-59.
2. APOLLO COMPUTER CORP. Apollo domain architecture. Tech. Rep. Apollo Computer Corporation, North Billerica, Mass., 1981.
3. BARTLETT, J. F. A nonstop kernel. In Proceedings of the 8th Symposium on Operating Systems
Principles (Pacific Grove, Calif., Dec. 14-l@, ACM, New York, 1981, pp. 22-29.
ACM Transactions on Computer Systems, Vol. 4, No. 2, May 1986.

146

-

N. P. Kronenberg,

H. M. Levy, and W. D. Strecker

4. BORG, A., BAUMBACH, J., AND GLAZER, S. A message system supporting fault tolerance. In
Proceedings of the 9th Symposium on Operating Systems Principles (Bretton Woods, N.H., Oct.
ll-13), ACM, New York, 1983, pp. 90-99.
5. BROWNBIRDGE,A., MARSHALL, A., AND RANDELL, A. The newcastle connection or unixes of
the world unite! So@.-Pratt.
Exp. 12 (1982), 1147-1162.
6. CHERITON,D., AND ZWAENEPOEL,W. The distributed V kernel and its performance for disklessworkstations. In Proceedings of the 9th Symposium on Operating Systems Principles (Bretton
Woods, N.H., Oct. ll-13), ACM, New York, 1983, pp. 129-140.
7. FIELLAND, G., AND RODGERS,D. 32-bit computer system shares load equally among up to 12
processors. Elect. Des. (Sept. 1984), 153-168.
8. GRAY, J. N., LORIE, R. A., PUTZOLU, G. R., AND TRAIGER, I. L. Granularity of locks anddegrees of consistency in a shared data base. In Modelling in Data Base Management Systems.
Nijssen, G. M., Ed., North Holland, Amsterdam, 1976.
9. HWANG, K., AND BRIGGS, F. A. Computer Architecture and Parallel Processing. McGraw-Hill,
New York, 1984.
10. KATSUKI, D., ELSAM, E. S., MANN, W. F., ROBERTS,E. S., ROBINSON, J. G., SKOWRONSKI,
F. S., WOLF, E. W. Pluribus-An operational fault-tolerant multiprocessor. In Proceedings ofthe IEEE 66,10 (Oct. 1978), 1146-1159.
11. KATZMAN, J. A. The Tandem 16: A fault-tolerant computing system. In Computer Structures:
Principles and Examples, Siewiorek, D. P., Bell, C. G., and Newell, A., Eds., McGraw-Hill, New
York, 1982, pp. 470-480.
12. METCALFE,R. M., AND BOGGS,D. R. Ethernet: Distributed packet switching for local computer
networks. Commun. ACM Z9,7 (July 1976), 395-404.
13. POPEK, G., WALKER, B., CHOW,J., EDWARDS,D., KLINE, C., RUDISIN, G., THIEL, G. LOCUS:
A network transparent, high reliability distributed system. In Proceedings of the 8th Symposium
on Operating Systems Principles (Pacific Grove, Calif., Dec. 14-16), ACM, New York, 1981,
pp. 169-177.
14. REID, L. G., AND KARLTON, P. L. A file system supporting cooperation between programs. In
Proceedings of the 9th Symposium on Operating Systems Principles (Bretton Woods, N.H., Oct.
II-13), ACM, New York, 1983, pp. 20-29.
15. SATYANARAYANAN,M. Multiprocessors: A Comparatiue Study. Prentice-Hall, EnglewoodCliffs,
N.J., 1980.
16. STRECKER,W. D. VAX-11/780: A virtual address extension to the DEC PDP-11 family. In
Proceedings of AFZPS NCC, 1978, pp. 967-980.
Received July 1985; revised December 1985; accepted December 1985

ACM Transactionson ComputerSystems,Vol. 4, No. 2, May 1986.