Efficient garbage collection in a compressed journal file

• US 8,539,007 B2
• Filed: 10/17/2011
• Issued: 09/17/2013
• Est. Priority Date: 10/17/2011
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Amit, Jonathan, Koifman, Chaim, Raikhman, Rostislav, Marenkov, Sergey
• Primary Examiner(s): Trujillo, James
• Assistant Examiner(s): Spieler, William
• Application Number:
  US13/275,178
• Publication Number:
  US 20130097210A1
• Time in Patent Office: 701 Days
• Field of Search: 707/813
• US Class Current: 707/813
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 16/1727 Details of free space management performed by the file system saving storage space on storage systems G06F3/0608; management of blocks in storage devices G06F3/064
• CPC Class Codes: G06F 16/1815 Journaling file systems
• CPC Class Codes: G06F 3/06 Digital input from, or digital output to, record carriers , e.g. RAID, emulated record carriers or networked record carriers
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

Exemplary method, system, and computer program product embodiments for efficient garbage collection in a compressed journal file system are provided. In one embodiment, by way of example only, a map corresponding to data blocks with overwritten compressed journal entries is configured. Weighted conditions for each of the overwritten compressed journal entries are calculated. The weighted conditions are arranged in the map from lowest to highest. One of the weighted conditions includes a biasing variable towards selecting data blocks having free space at an end of at least one associated record. Additional system and computer program product embodiments are disclosed and provide related advantages.

Claims

1. A system for efficient garbage collection in a compressed journal file system in a computing environment, comprising:

a processor device operable in the computing storage environment, wherein the processor device is adapted for;

configuring a map corresponding to data blocks with overwritten compressed journal entries, and

calculating weighted conditions for each of the overwritten compressed journal entries, wherein the weighted conditions are arranged in the map from lowest to highest;

wherein one of the weighted conditions includes a biasing variable towards selecting data blocks having free space at an end of at least one associated record.

2. The system of claim 1, wherein the processor device is further adapted for performing the calculation for the weighted conditions according to:

(x−

w+(y/x))*(z/range), where w is a number of records in a read cache, x is a number of valid records, y is a size of data in the valid records, z is a relative position of the data block to the end of the at least one record, and range is assigned a weighted value according to a distance the range is from an origin.

3. The system of claim 1, wherein the processor device is further adapted for limiting the size of the map by the age of the data blocks to exclude the data blocks with the highest number of valid records from entering the map, wherein the age of the block is a time difference between the last overwrite operation on the data block and a current time.

4. The system of claim 1, wherein the calculating is performed each time data is overwritten on the data blocks and each time the data blocks are added to the map, wherein the weighted conditions of the data blocks are arranged in the map from lowest to highest.

5. The system of claim 1, wherein the processor device is further adapted for selecting the data blocks for garbage collection with a minimal number of valid data, minimal valid record count, and maximum size of the free space.

6. The system of claim 5, wherein the processor device is further adapted for, in conjunction with the selection, determining if the weighted conditions of the data blocks exceed a threshold value.

7. The system of claim 6, wherein the processor device is further adapted for performing the selecting for the data blocks present in a read cache with weighted conditions that are equivalent.

8. The system of claim 7, wherein the processor device is further adapted for, if one of the data blocks is not in the read cache, and if the one of the data blocks weighted conditions exceeds the threshold value, performing the selecting for one of the data blocks.

9. A computer program product for efficient garbage collection in a compressed journal file system in a computing environment by a processor device, the computer program product comprising a non-transitory computer-readable storage medium having computer-readable program code portions stored therein, the computer-readable program code portions comprising:

a first executable portion for configuring a map corresponding to data blocks with overwritten compressed journal entries; and

a second executable portion for calculating weighted conditions for each of the overwritten compressed journal entries, wherein the weighted conditions are arranged in the map from lowest to highest;

wherein one of the weighted conditions includes a biasing variable towards selecting data blocks having free space at an end of at least one associated record.

10. The computer program product of claim 9, further including a third executable portion for performing the calculation for the weighted conditions according to:

(x−

w+(y/x))*(z/range), where w is a number of records in a read cache, x is a number of valid records, y is a size of data in the valid records, z is a relative position of the data block to the end of the at least one record, and range is assigned a weighted value according to a distance the range is from an origin.

11. The computer program product of claim 9, further including a third executable portion for limiting the size of the map by the age of the data blocks to exclude the data blocks with the highest number of valid records from entering the map, wherein the age of the block is a time difference between the last overwrite operation on the data block and a current time.

12. The computer program product of claim 9, wherein the calculating is performed each time data is overwritten on the data blocks and each time the data blocks are added to the map, wherein the weighted conditions of the data blocks are arranged in the map from lowest to highest.

13. The computer program product of claim 9, further including a third executable portion for selecting the data blocks for garbage collection with a minimal number of valid data, minimal valid record count, and maximum size of the free space.

14. The computer program product of claim 13, further including a fourth executable portion for, in conjunction with the selection, determining if the weighted conditions of the data blocks exceed a threshold value.

15. The computer program product of claim 14, further including a fifth executable portion for, performing the selecting for the data blocks present in a read cache with weighted conditions that are equivalent.

16. The computer program product of claim 15, further including a sixth executable portion for, if one of the data blocks is not in the read cache, and if the one of the data blocks weighted conditions exceeds the threshold value, performing the selecting for one of the data blocks.