[gclist] Projects that use GC

[Marc Shapiro]

 || Date: Wed, 20 Mar 96 13:05:19 EST
 || From: David Chase <chase@centerline.com>
 || 
 || Q: What are some successful products or projects which make use of 
 ||    garbage collection?

The Sprite Log File System (Sprite LFS) uses linear allocation (they call it
logging) and compacting GC (they call it cleaning).  

(It might be worthwhile including the following description in th FAQ.)

A file is represented as a set of blocks accessed indirectly via an inode.
When you write data in some block of a file, the new version of the block gets
written at the end of the log, and the pointer from the inode to the block
gets updated.  Inodes themselves are contained in files, so the same procedure
propagates all the way to the root of the data structure, which is written in
a special well-known location (instead of being logged).

Benchmarks show an impressive performance gain over standard file systems
(specifically, Berkeley FFS).  The performance benefits come from the linear
allocation and batched writes without any disk head movement.  However
cleaning can seriously degrade performance.

The disk is managed, not as a single linear log, but as a set of doubly-linked
log "segments", each 1Mb in size.  The amount of garbage in a segment is
easily determined (without reading the segment) from the metadata.  An
entirely empty segment is recycled.  An almost-empty segment is copied to the
beginning of a clean segment, or into an almost-full segment.