Concurrent, Incremental, and Generational Mark and Sweep Garbage Collection

摘要

Provided are systems and methods for garbage collection of objects in storage. An example method may include providing a monotonically increasing logical clock. Each object is associated with a first number and a second number. The second number is a minimum of the first numbers of objects in a subtree to which the object refers. When the logical clock increases, objects with the first number less than the logical clock from the storage are deleted. When a new object is added to the storage, the first number of the new object is set to a new first number. The new first number is equal to or greater than the logical clock. The first number of each object in a subtree to which the new object is referring is updated. The updated first number is a function of a previous first number and a previous logical clock.

主权项

1. A computer-implemented method for garbage collection of objects in a storage, the method comprising:
providing a logical clock, the logical clock being configured to monotonically increase; associating each of the objects with a first number; associating each of the objects with a second number, the second number being a minimum of the first numbers associated with further objects, the further objects belonging to a subtree to which the object refers; when the logical clock increases:
deleting objects with the first number less than the logical clock from the storage; and when at least one new object is added to storage:
setting the first number associated with the at least one new object to a new first number, the new first number being equal or greater to the logical clock; andupdating the first number of each object in a new subtree to which the at least one new object is referring, the updated first number being a function of the first number associated with each object and a value of the logical clock at which the first number was set.