Some informal thoughts on
Shared State in Distributed Systems
Michael L. Scott
Professor and Chair
Computer Science Department
University of Rochester
Rochester, NY 14627-0226
phone (585) 275-7745, 5478; fax 461-2018
Many distributed applications devote significant effort to maintaining
consistent copies of dynamic information at multiple sites. Examples include
conventional web pages being read by multiple clients
``push'' style web pages being sent to multiple clients
blackboards in computer-supported collaborative work
cached copies of open files in a distributed file system
file replicas in a fault-tolerant or highly-available file system
pages in a software distributed shared memory system
frames in a distributed virtual memory
records in an on-line transaction-processing system
video windows in a tele-conferencing system
These applications differ in
operations on the shared object required by the application
degree of sharing
level of performance required (bandwidth, latency, predictability)
level of fault-tolerance required
All, however, share the notion of an object (call it a ``segment'') that is
read and/or written at multiple sites. I suggest that we recognize this
commonality, and embed it in a standard set of mechanisms for binding to
shared segments. If we do it right, we'll make it easier to re-use code and
run experiments, and we'll defer to the standard on a lot of extraneous
issues (e.g. naming and access control).
The standardization task would draw on work in several areas, including
- network protocols
- Just as one specifies a communication protocol
when binding to a socket, one ought to be able to specify a sharing
protocol when binding to a segment. It probably makes sense to
leverage the set-up conventions of the message-passing world wherever
- distributed file systems
- DFSes already deal with caching and
consistency. In many cases, it probably makes sense to think of a
shared segment as a memory-mapped file. Among other things, the
DFS system community knows how to do access control.
- software distributed shared memory
- Distributed file systems don't
deal much with fine-grain access or with concurrency control
among multiple writers. S-DSM systems do.
- distributed databases
- Like S-DSM, distributed databases deal with
fine-grain access and concurrency control. The database community
knows how to handle replication, resilience, and nested transactions.
They have a very structured view of data, however, which isn't
appropriate for all applications.
Protocols and Programming Models
The S-DSM community uses the word ``protocol'' somewhat loosely, to encompass
both the user interface and consistency model on the one hand (let's call
this the ``programming model''), and the underlying implementation on the
other (let's call this the ``underlying protocol''). Examples of programming
Associate reader-writer locks with segments. Read and write a segment
with ordinary loads and stores, but only when in posession of the
Read and write a segment with explicit put and get operations; assume
that synchronization is handled independently by the applications.
Read and write with explicit put and get operations, in conjunction with
nested commit-abort style transactions.
Treat the segment as a heap, with automatic distributed garbage
Identify acquire and release operations in the program, and refrain from
data races (permitting the implementation of release consistency).
These models are not necessarily mutually exclusive (garbage collection,
for example, is compatible with several of the other models). Several of
them (the last one in particular) admit multiple underlying protocols.
I don't believe it will be possible (or even desirable) to standardize on a
single model. Some applications, for example, will want complete control
over the timing of state dissemination. A friend in the CSCW community tells
me he doesn't want any state distributed until the human user says so.
In principle, an application that conforms to a given programming model
should be able to work on top of any compatible underlying protocol. All
that matters is that the application invoke the appropriate ``hooks'' in a
library that conforms to the underlying protocol. It may even be possible
for two appliations that share a segment to use different underlying
protocols, though I doubt this will often be the case. Possible hooks
synchronization operations that bracket a critical section in which a
segment is accessed (e.g. reader-writer lock acquires and releases)
acquires and releases of synchronization objects, without respect to
particular segments (for release consistency)
page faults (for VM-based software DSM)
put, get, commit, abort
allocate, make_ref, and drop_ref routines for a garbage-collected heap
A binding operation would need to install hooks for implicitly-activated
protocol operations (page fault handlers) and return pointers to
application-activated operations (put and get, commit and abort,
critical-section brackets). I'm not sure how to classify things like
allocate, make_ref, drop_ref, acquire, and release.
Segments should perhaps be named with URLs:
(dsbp = distributed sharing binder protocol)
When creating a segment, one would have to specify the protocol(s) via
which it could be accessed. When binding to a segment, one would have to
specify a matching protocol. In some cases protocol code (in Java, for
example) could be returned by the DSBP server. This is dicey, however, for
operations that need to make non-trivial changes to local system state (e.g.
changing page protections).
How do we deal with heterogeneous data representations?
How do we integrate long-distance sharing protocols with local-area
protocols? Imagine, for example, a simulation running on a
local S-DSM cluster, with a remote front end that needs to read, or
even write, simulation data structures.
If we embed pointer-rich data structures in segments, they need to be
mapped at the same address in every user. How do we parcel out
addresses to prevent conflicts? 64-bit address spaces help, but
probably don't solve the problem.
To Michael Scott's home page
To the URCS Home Page
Last Change: 18 July 1997 /