At 09:56 AM 8/23/2001 -0400, you wrote:
>If you combined Rob's ideas about segmenting object memory using
>Sentinel objects with that of ImageSegments, would that be a good
>solution to large scale, persistent GC?

Yes!

I've been thinking of building a Squeak-based OODBMS using similar techniques
for a while now.

While there is some similarity with distributed GC, this approach is simpler,
since pointer manipulation happens within a single environment and intermachine
communication isn't necessary to manipulate references.

As you realize, macroGC only needs to consider top-level segments and their
outpointers.  Note also that microGC need only be performed before persisting
a modified segment.

To the best of my knowledge, no one's built a system with quite these 
properties,
though I've experimented with a similar approach to partitioning object memory.

Some background:

For a large Gemstone based application, I built framework support for 
partitioning
the object model by "aggregate".  An aggregate is essentially an image segment,
1 exposed root encapsulating internal objects.  In that implementation, nesting
is not supported, and attempts to store persistent references to encapsulated
objects are detected and raise exceptions. If I follow what you've written 
below,
you're thinking of dynamically creating new Sentinels if such a reference 
occurs;
I think more control is necessary.

As an object modelling approach, this design was very successful in reducing
complexity.  Given the experience, I now favor supporting nested segments, too.

The application's now in use by ~1100 concurrent users.

As you may be aware, Gemstone has an address space limit; in the version
we used only 1 billion objects can be stored in a database.

In the interests of conserving object ids, I later built a primitive that
compacted segments -- the storage format is now an array of outpointers
to other segments and a compressed byte representation of the encapsulated
objects. Segments are transparently expanded on reference.

In effect, then, I achieved the kind of persistent garbage collection 
you're describing,
though in a very heavy handed way.

The other key issue in building a multiuser OODBMS is transactional shared 
memory,
so that many VMs could read and execute the same copies of segments.
For this to work, read and write semantics on shared segments need to change.
Depending on the transaction model and the history of the shared segment, 
writing a
shared segment may need to copy on write, wait for a lock, or cause a 
transaction abort.
Reading a reference to a shared segment may require waiting for a lock or 
locating
the correct version of that segment for the current transaction.

I've been thinking of having alternate implementations of specific 
bytecodes, so that
when you traverse a Sentinel into a shared segment, you switch in the shared
implementation of bytecodes, when you traverse back to a private segment, you
switch in the ordinary implementation of bytescodes.

While there's a lot more that needs to be done to create a real OODBMS,
especially a high performance one, I think shared segmented memory
is the critical foundation.

-dms

>Using Sentinels, all roots of an image segment would be inward pointing
>Sentinels, outpointers would be outward pointing Sentinels to some other
>image segment(s).  Bringing image segments into an image, or dumping one
>out of an image would no longer require full garbage collects or memory
>scans because (a) the root Sentinels match their target object's
>protocol 100% (note: this won't work entirely in the currect Squeak) so
>a become is not required and (b) a full GC is not required when dumping
>an image segment out of memory because the sentinels always protect new
>references into an image segment (creating new sentinels if necessary).
>
>If we have a very large virtual image (on disk let's say), fully garbage
>collecting that image may be prohibitively expensive, however, if the
>image is segmented using this technique, we could have several
>alternatives:
>
>1) "Macro GC" - We scan from the root segment, but "hop" over other
>image segments (we can do this because we know all of the inward and
>outward sentinels.
>
>2) "Micro GC" - We scan within an image segment, and only that image
>segment (skipping over nested image segments and stopping at the
>outbound Sentinels)
>
>Image segments could be nested within other image segments, allowing for
>arbitrarily deep nesting of this scheme.  Using this scheme, if you were
>running low on disk space, you could start GC at the root segment, and
>if you clean up an acceptable amount of space, you stop, if not, you
>drill down into an image segment and GC that, and so on.
>
>Would this work?  Has it been done before?
>
>- Stephen
>
>