InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Online Space Reclamation from the Middle of a Free-space Map

IP.com Disclosure Number: IPCOM000019528D
Original Publication Date: 2003-Sep-17
Included in the Prior Art Database: 2003-Sep-17
Document File: 1 page(s) / 38K

Publishing Venue



A transactionally consistent algorithm for space reclamation in a distributed cluster environment. The reclamation can occur at any location in the free-space map while allowing concurrent space allocation.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 67% of the total text.

Page 1 of 1

Online Space Reclamation from the Middle of a Free-space Map

  Many applications manage available disk space by utilizing bitmaps within a free-space manager. The problem with this method is the difficulty in reclaiming space with the middle of the free-space map. Many applications can trim space from the end of a free space map or utilize a defragmenter to compress the used space down before trimming the freed space at the end of the map. A defragmenter utility is generally pervasive to the system and consumes valuable CPU and IO resources.

This solution allows for free-space reclamation in the middle of a free-space map within a distributed environment where a master node maintains the transactionally consistent state of the available free-space. Our approach allows for the transactionally consistent reclamation of logically consecutive blocks from anywhere in the free-space map. The atomic unit of work is at the partition level. The process is initiated from the master node.

The details of the logic follows:

The master node sends the subordinate a message requesting a candidate list of

free partitions. The subordinate checks its free-space map for any logically consecutive free space

in its map and returns a candidate list to the master. The master node inserts a redo record of the reclamation action and marks the

partition as locked persistently within the master's meta-data tables. The master sends a message to the subordinate to check if the specified partiti...