Scalable segment cleaning for a log-structured file system

Abstract

Scalable segment cleaning for log-structured file systems (LFSs) includes determining counts of segment cleaners and virtual nodes, with each virtual node being associated with a plurality of objects. Each virtual node is assigned to a selected segment cleaner. Based at least on the assignments, performing, for each virtual node, segment cleaning of the objects by the assigned segment cleaner. A portion, less than all, of the virtual nodes are reassigned to a newly selected segment cleaner based on a change of the count of the segment cleaners and/or a change of the count of the virtual nodes. Based at least on the reassignments, segment cleaning of the objects is performed, for each reassigned virtual node, by the reassigned segment cleaner. In some examples, the objects comprise virtual machine disks (VMDKs) and the segment cleaning uses a segment usage table (SUT) to track segment usage and identify segment cleaning candidates.

What is claimed is: 
     
         1 . A method of segment cleaning, the method comprising:
 determining a first count of a plurality of segment cleaners;   determining a first count of a plurality of virtual nodes, wherein each virtual node is associated with a plurality of objects;   assigning each virtual node of the plurality of virtual nodes to a selected one of the plurality of segment cleaners;   determining an occurrence of one or more of the following reassignment conditions:   the first count of the plurality of segment cleaners changing to a second count of the plurality of segment cleaners, the first count of the plurality of virtual nodes changing to a second count of the plurality of virtual nodes;   for a portion, less than all, of the plurality of virtual nodes, reassigning each virtual node of the portion to a newly selected segment cleaner; and   performing segment cleaning according to the reassignment.   
     
     
         2 . The method of  claim 1 , wherein the first count of the plurality of segment cleaners is more than the second count of the plurality of segment cleaners, wherein the reassignment comprises reassigning only one or more of the plurality of virtual nodes, that were mapped to one or more of the plurality of segment cleaners that have ceased operation, to one or more of the plurality of segment cleaners that remain in operation. 
     
     
         3 . The method of  claim 1 , wherein the first count of the plurality of segment cleaners is less than the second count of the plurality of segment cleaners, wherein the reassignment comprises reassigning only one or more of the plurality of virtual nodes to one or more new segment cleaners that have been spawned. 
     
     
         4 . The method of  claim 3 , the method further comprising:
 monitoring a workload of the plurality of segment cleaners;   based on the monitoring, determining that one or more of the plurality of segment cleaners are overloaded; and   based on determining that the one or more of the plurality of segment cleaners are overloaded, spawning the one or more new segment cleaners.   
     
     
         5 . The method of  claim 1 , wherein the first count of the plurality of virtual nodes is more than the second count of the plurality of virtual nodes, wherein the reassignment comprises reassigning only one or more of the plurality of virtual nodes that have ceased operation from the plurality of segment cleaners. 
     
     
         6 . The method of  claim 1 , wherein the first count of the plurality of virtual nodes is less than the second count of the plurality of virtual nodes, wherein the reassignment comprises reassigning only one or more new virtual nodes to the plurality of segment cleaners. 
     
     
         7 . The method of  claim 1 , further comprising:
 summarizing, in a segment usage table (SUT), an amount of live space left in each of a plurality of log segments;   identifying one or more of the plurality of log segments for segment cleaning;   determining, by checking each block of the identified one or more of the plurality of log segments, whether a content addressable storage (CAS) points to one of the plurality of log segments;   upon determining that the CAS points to the one of the plurality of log segments, identifying those blocks as live blocks;   rewriting the live blocks in one or more new log segments; and   adjusting the CAS to point to the one or more new log segments and removing the one of the plurality of log segments.   
     
     
         8 . The method of  claim 7 , further comprising:
 determining, for each of the plurality of log segments, a count of the live blocks as a live block count;   identifying at least one of the plurality of log segments for which the live block count is zero; and   over-writing the identified at least one of the plurality of log segments without moving any block from the identified at least one of the plurality of log segments.   
     
     
         9 . A computer system for segment cleaning, the computer system comprising:
 a processor; and   a non-transitory computer readable medium having stored thereon program code that upon execution causes the processor to:
 determine a first count of a plurality of segment cleaners; 
 determine a first count of a plurality of virtual nodes, wherein each virtual node is associated with a plurality of objects; 
 assign each virtual node of the plurality of virtual nodes to a selected one of the plurality of segment cleaners; 
 determine an occurrence of one or more of the following reassignment conditions: the first count of the plurality of segment cleaners changing to a second count of the plurality of segment cleaners, the first count of the plurality of virtual nodes changing to a second count of the plurality of virtual nodes; 
 upon determining the occurrence, for a portion, less than all, of the plurality of virtual nodes, reassign each virtual node of the portion to a newly selected segment cleaner; and 
 perform segment cleaning according to the reassignment. 
   
     
     
         10 . The computer system of  claim 9 , wherein the first count of the plurality of segment cleaners is more than the second count of the plurality of segment cleaners, wherein the reassignment comprises reassigning only one or more of the plurality of virtual nodes, that were mapped to one or more of the plurality of segment cleaners that have ceased operation, to one or more of the plurality of segment cleaners that remain in operation. 
     
     
         11 . The computer system of  claim 9 , wherein the first count of the plurality of segment cleaners is less than the second count of the plurality of segment cleaners, wherein the reassignment comprises reassigning only one or more of the plurality of virtual nodes to one or more new segment cleaners that have been spawned. 
     
     
         12 . The computer system of  claim 11 , the program code upon executing further causing the processor to:
 monitor a workload of the plurality of segment cleaners;   based on the monitoring, determine that one or more of the plurality of segment cleaners are overloaded; and   based on determining that the one or more of the plurality of segment cleaners are overloaded, spawn the one or more new segment cleaners.   
     
     
         13 . The computer system of  claim 9 , wherein the first count of the plurality of virtual nodes is more than the second count of the plurality of virtual nodes, wherein the reassignment comprises reassigning only one or more of the plurality of virtual nodes that have ceased operation from the plurality of segment cleaners. 
     
     
         14 . The computer system of  claim 9 , wherein the first count of the plurality of virtual nodes is less than the second count of the plurality of virtual nodes, wherein the reassignment comprises reassigning only one or more new virtual nodes to the plurality of segment cleaners. 
     
     
         15 . A non-transitory computer readable storage medium having stored thereon program code executable by a processor, the program code embodying a method comprising:
 determining a first count of a plurality of segment cleaners;   determining a first count of a plurality of virtual nodes, wherein each virtual node is associated with a plurality of objects;   assigning each virtual node of the plurality of virtual nodes to a selected one of the plurality of segment cleaners;   determining an occurrence of one or more of the following reassignment conditions: the first count of the plurality of segment cleaners changing to a second count of the plurality of segment cleaners, the first count of the plurality of virtual nodes changing to a second count of the plurality of virtual nodes;   upon determining the occurrence, for a portion, less than all, of the plurality of virtual nodes, reassigning each virtual node of the portion to a newly selected segment cleaner; and   performing segment cleaning according to the reassignment.   
     
     
         16 . The non-transitory computer readable storage medium of  claim 15 , wherein the first count of the plurality of segment cleaners is more than the second count of the plurality of segment cleaners, wherein the reassignment comprises reassigning only one or more of the plurality of virtual nodes, that were mapped to one or more of the plurality of segment cleaners that have ceased operation, to one or more of the plurality of segment cleaners that remain in operation. 
     
     
         17 . The non-transitory computer readable storage medium of  claim 15 , wherein the first count of the plurality of segment cleaners is less than the second count of the plurality of segment cleaners, wherein the reassignment comprises reassigning only one or more of the plurality of virtual nodes to one or more new segment cleaners that have been spawned. 
     
     
         18 . The non-transitory computer readable storage medium of  claim 17 , wherein the program code further comprises:
 monitoring a workload of the plurality of segment cleaners;   based on the monitoring, determining that one or more of the plurality of segment cleaners are overloaded; and   based on determining that the one or more of the plurality of segment cleaners are overloaded, spawning the one or more new segment cleaners.   
     
     
         19 . The non-transitory computer readable storage medium of  claim 15 , wherein the first count of the plurality of virtual nodes is more than the second count of the plurality of virtual nodes, wherein the reassignment comprises reassigning only one or more of the plurality of virtual nodes that have ceased operation from the plurality of segment cleaners. 
     
     
         20 . The non-transitory computer readable storage medium of  claim 15 , wherein the first count of the plurality of virtual nodes is less than the second count of the plurality of virtual nodes, wherein the reassignment comprises reassigning only one or more new virtual nodes to the plurality of segment cleaners.