In-place garbage collection for state machine replication

Abstract

Garbage collection processing in a distributed shared log system includes a client identifying obsoleted log entries for a shared data object. The client sends information associated with the identified obsoleted log entries to a shared log server. The shared log server receives information associated with obsoleted log entries from all clients in the distributed shared log system and uses the information to delete the obsoleted log entries. The shared log server can update a snapshot mark to indicate the earliest time that a snapshot of the shared log can be taken. The snapshot mark can be updated based on the information associated with obsoleted log entries.

1 . A method comprising:
 receiving, by a server system from each of a plurality of clients, a list of obsoleted log entries for a data object, wherein the list comprises log entries in a log maintained by the server system that are obsolete in view of a current global state of the data object, and wherein the log is composed of a plurality of files;   for each obsoleted log entry in the list:
 identifying, by the server system, a file in the plurality of files that contains the obsoleted log entry; and 
 updating, by the server system, a garbage size value associated with the file based on a size of the obsoleted log entry, the garbage size value indicating a total size of all obsoleted log entries in the file; 
   determining, by the server system, that a compaction cycle with respect to the plurality of files should be executed; and   in response to the determining:
 selecting one or more files in the plurality of files based on their respective garbage size values; and 
 compacting the selected files. 
   
     
     
         2 . The method of  claim 1  wherein the list includes locator information corresponding to locations of the obsoleted log entries in the log, and wherein the identifying is performed based on the locator information. 
     
     
         3 . The method of  claim 1  wherein the size of the obsoleted log entry is included in the list. 
     
     
         4 . The method of  claim 1  wherein the determining comprises:
 computing, for each of the plurality of files, a garbage ratio value based on the garbage size value associated with the file, the garbage ratio value indicating a ratio of obsoleted log entries to non-obsoleted log entries in the file; and 
 identifying at least one file in the plurality of files whose garbage ratio value exceeds a threshold. 
 
     
     
         5 . The method of  claim 4  wherein the one or more files selected for compaction correspond to files whose garbage ratio value exceeds the threshold. 
     
     
         6 . The method of  claim 1  wherein the determining comprises:
 determining that a total disk usage for the plurality of files exceeds a threshold. 
 
     
     
         7 . The method of  claim 1  wherein the compacting comprises, for each selected file:
 reading each log entry in the selected file; and 
 writing the read log entry to a new file if the read log entry is not an obsoleted log entry. 
 
     
     
         8 . A non-transitory computer-readable storage medium having stored thereon computer executable instructions that, when executed by a computer system, cause the computer system to:
 receive, from each of a plurality of clients, a list of obsoleted log entries for a data object, wherein the list comprises log entries in a log maintained by the computer system that are obsolete in view of a current global state of the data object, and wherein the log is composed of a plurality of files;   for each obsoleted log entry in the list:
 identify a file in the plurality of files that contains the obsoleted log entry; and 
 update a garbage size value associated with the file based on a size of the obsoleted log entry, the garbage size value indicating a total size of all obsoleted log entries in the file; 
   determine that a compaction cycle with respect to the plurality of files should be executed; and   in response to the determining:
 select one or more files in the plurality of files based on their respective garbage size values; and 
 compact the selected files. 
   
     
     
         9 . The non-transitory computer-readable storage medium of  claim 8  wherein the list includes locator information corresponding to locations of the obsoleted log entries in the log, and wherein the identifying is performed based on the locator information. 
     
     
         10 . The non-transitory computer-readable storage medium of  claim 8  wherein the size of the obsoleted log entry is included in the list. 
     
     
         11 . The non-transitory computer-readable storage medium of  claim 8  wherein the computer executable instructions that cause the computer system to determine that the compaction cycle should be executed comprises computer executable instructions that cause the computer system to:
 compute, for each of the plurality of files, a garbage ratio value based on the garbage size value associated with the file, the garbage ratio value indicating a ratio of obsoleted log entries to non-obsoleted log entries in the file; and 
 identify at least one file in the plurality of files whose garbage ratio value exceeds a threshold. 
 
     
     
         12 . The non-transitory computer-readable storage medium of  claim 11  wherein the one or more files selected for compaction correspond to files whose garbage ratio value exceeds the threshold. 
     
     
         13 . The non-transitory computer-readable storage medium of  claim 8  wherein the computer executable instructions that cause the computer system to determine that the compaction cycle should be executed comprises computer executable instructions that cause the computer system to:
 determine that a total disk usage for the plurality of files exceeds a threshold. 
 
     
     
         14 . The non-transitory computer-readable storage medium of  claim 8  wherein the computer executable instructions that cause the computer system to compact the selected files comprises computer executable instructions that cause the computer system to, for each selected file:
 read each log entry in the selected file; and 
 write the read log entry to a new file if the read log entry is not an obsoleted log entry. 
 
     
     
         15 . A computer system comprising:
 a processor; and   a computer-readable storage medium comprising instructions that, when executed by the processor, cause the processor to:
 receive, from each of a plurality of clients, a list of obsoleted log entries for a data object, wherein the list comprises log entries in a log that are obsolete in view of a current global state of the data object, and wherein the log is composed of a plurality of files; 
 for each obsoleted log entry in the list:
 identify a file in the plurality of files that contains the obsoleted log entry; and 
 update a garbage size value associated with the file based on a size of the obsoleted log entry, the garbage size value indicating a total size of all obsoleted log entries in the file; 
 
 determine that a compaction cycle with respect to the plurality of files should be executed; and 
 in response to the determining:
 select one or more files in the plurality of files based on their respective garbage size values; and 
 compact the selected files. 
 
   
     
     
         16 . The computer system of  claim 15  wherein the list includes locator information corresponding to locations of the obsoleted log entries in the log, and wherein the identifying is performed based on the locator information. 
     
     
         17 . The computer system of  claim 15  wherein the size of the obsoleted log entry is included in the list. 
     
     
         18 . The computer system of  claim 15  wherein the instructions that cause the processor to determine that the compaction cycle should be executed comprises instructions that cause the processor to:
 compute, for each of the plurality of files, a garbage ratio value based on the garbage size value associated with the file, the garbage ratio value indicating a ratio of obsoleted log entries to non-obsoleted log entries in the file; and 
 identify at least one file in the plurality of files whose garbage ratio value exceeds a threshold. 
 
     
     
         19 . The computer system of  claim 18  wherein the one or more files selected for compaction correspond to files whose garbage ratio value exceeds the threshold. 
     
     
         20 . The computer system of  claim 15  wherein the instructions that cause the processor to determine that the compaction cycle should be executed comprises instructions that cause the processor to:
 determine that a total disk usage for the plurality of files exceeds a threshold. 
 
     
     
         21 . The computer system of  claim 15  wherein the instructions that cause the processor to compact the selected files comprises instructions that cause the processor to, for each selected file:
 read each log entry in the selected file; and 
 write the read log entry to a new file if the read log entry is not an obsoleted log entry.