Distributed garbage collection for information spaces on the Internet.
Sung-Wook Ryu · University of Southern California Digital Library · 2014
A critical problem for large scale distributed systems which manage distributed object spaces, is deciding when information is not reachable by any clients. This process, called garbage collection, is important because manual garbage collection by clients is error-prone, and this causes dangling links and memory leaks. Many solutions about distributed garbage collection have been suggested. However, they are not suitable for large scale distributed systems because their target systems are small in scale or they cannot collect cyclic garbage. As part of an improved solution for distributed garbage collection, this dissertation presents a practical and efficient garbage collection mechanism which eventually collects all cyclic garbage in large scale distributed object spaces. The primary method used for collection is timeouts, which collects acyclic garbage. For cyclic garbage collection, objects likely to be cyclic garbage are detected by last referenceable timestamp propagation, and backward inquiry is performed from them to see if they are reachable by any clients. Since objects can get information about inverse references using timeouts, our mechanism can perform back-tracing without explicit backward reference lists. Moreover, messages necessary for backward inquiry are bundled with the messages used for timeouts, so no additional communication overhead is required for cyclic garbage collection. In order to reduce computation and communication overheads, three optimization techniques are introduced. First, messages are gathered and sent on a host-to-host basis rather than an object-to-object basis. Second, garbage collection frequency of each object is controlled by the likelihood of being garbage. Third, our mechanism supports four types of garbage collection methods, so that owners can select different degrees of referential integrity based on the characteristics of their objects and links. We proved the correctness of our mechanism, and implemented and evaluated the mechanism on the Prospero directory service. The performance results show that the mechanism works well for large scale distributed object spaces.