Garbage collection in a large, distributed object store
Umesh Maheshwari, Barbara H. Liskov · DSpace@MIT (Massachusetts Institute of Technology) · 1997
Systems that store a large number of persistent objects over many sites in a network pose new challenges to storage management.This thesis presents a comprehensive design for collecting garbage objects in such systems.The design achieves scalability by partitioning the system at two levels: Each site traces its objects independently of other sites, and the disk space at each site is divided into partitions that are traced one at a time in main memory.To trace a site independently of other sites, and a partition independently of other partitions, objects reachable from other partitions or other sites must be treated as roots.This introduces two problems.First, maintaining up-todate information about inter-site and inter-partition references can stall applications and increase usage of disk, memory, and the network.Second, treating these references as roots does not allow collection of cycles of garbage objects spanning multiple sites or multiple partitions.Solutions to these problems have been proposed in single-site or distributed systems, but they do not scale to many partitions or many sites.This thesis presents scalable solutions to these problems.The thesis provides new techniques to organize and update a potentially large amount of interpartition information such that the information is recoverable after a crash and disk time is used efficiently.It also provides efficient techniques to record inter-site references in a system with client caches and multi-server transactions.A client might cache a large number of references to server objects; therefore, we identify a minimal subset of these references that must be recorded for safe collection at servers.We use a new protocol to manage inter-server references created by distributed transactions.This protocol sends messages in the background to avoid delaying transaction commits.We use another new protocol to handle client crashes; the protocol allows servers to safely discard information about clients that appear to have crashed but might be live.The thesis provides different schemes to collect inter-partition and inter-site garbage cycles.Inter-partition cycles are collected using a site-wide marking scheme; unlike previous such schemes, it is piggybacked on partition traces, does not delay the collection of non-cyclic garbage, and terminates correctly in the presence of modifications.Inter-site cycles, on the other hand, are collected using a scheme that minimizes inter-site dependence.It is the first practically usable scheme that can collect an inter-site garbage cycle by involving only the sites containing the cycle.The scheme has two parts: the first finds objects that are highly likely to be cyclic garbage, and the second checks if they are in fact garbage.The first part uses a new heuristic based on inter-site distances of objects.It has little overhead and it can be made arbitrarily accurate at the expense of delay in identifying garbage.We provide two alternatives for the second part.The first migrates a suspected garbage cycle to a single site, but unlike previous such schemes, it avoids migration as much as possible.The second traces backwards from a suspect to check if it is reachable from a root.We provide the first practical technique for back tracing in the presence of modifications.