A method for performing free space collection in an information storage system and an information storage system (104) are described. The information storage system (104) is a log structured system having storage units (106) in which information segments (202, 204) are located. Free space collection is carried out in the storage units by using a fitness value to evaluate segments (204). The fitness value is determined as the product of the amount of free space in a segment (204) and the expected time the free space will last (310). Segments (204) are chosen for free space collection if they have the maximum fitness value (312). The segments (204) are sorted into groups by the amount of used data in each segment (204) and the fitness value is determined for one segment from each group.