Optimized and robust in-place data transformation

• US 7,685,186 B2
• Filed: 06/25/2007
• Issued: 03/23/2010
• Est. Priority Date: 06/25/2007
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Jansen, Ariane, Rogers, Andrew M.
• Primary Examiner(s): NGUYEN, CAM LINH T
• Application Number:
  US11/768,010
• Publication Number:
  US 20080320252A1
• Time in Patent Office: 1,002 Days
• Field of Search: 707/100, 707/101, 707/104.1, 707/200, 707/204, 711/161
• US Class Current: 707/661
• CPC Class Codes: G06F 16/16 File or folder operations, e.g. details of user interfaces specifically adapted to file systems
• CPC Class Codes: G06F 16/1865 Transactional file systems

Abstract

In-place data transformations are performed on file data by moving data blocks from a source file into a temporary file and then from the temporary file into a destination file each time in a back to front fashion enabling truncation of the source file while the temporary file is being expanded and written into. Similar read, write, and truncate operations are performed between the temporary and destination files as well resulting in optimized use of available disk and/or memory space. An initial log file with information such as source file name, size, transformation type and direction is generated for recovery from a mid-transaction interruption. Based on a state (truncation, data content) of the temporary and source files, a status of data transfer prior to interruption is determined and remaining data transferred.

Claims

1. A method to be executed at least in part in a computing device for performing in-place data transformation in a file system, the method comprising:

performing a first transfer operation by transferring data from a source file to a temporary file in individual data blocks in a back to front fashion such that the temporary file is expanded and the source file is truncated after transfer of each data block;

if a last data block of the source file is a truncated block, inserting filler data into the last data block such that the last data block becomes the same size as remaining data blocks of the source file;

deleting the source file upon completion of the first transfer operation;

performing a second transfer operation by transferring data from the temporary file to a destination file in individual data blocks in a back to front fashion such that the destination file is expanded and the temporary file is truncated after transfer of each data block; and

deleting the temporary file and removing the filler data from a last data block of the destination file upon completion of the second transfer operation, wherein the data is transformed during one of;

the first transfer operation and the second transfer operation.

2. The method of claim 1, further comprising:

creating a temporary file; and

creating a log file that includes at least one form a set of;

a name of the source file, a size of the source file, a type of the transformation, and a direction of the transformation.

3. The method of claim 1, wherein performing the first transfer includes:

reading a data block from the source file beginning at the end of the source file;

expanding the temporary file to accommodate the read data block;

writing the data block to the beginning of the temporary file;

truncating the source file by removing the read data block from the end of the file; and

repeating the reading, expanding, writing, and truncating operations for each data block in the source file such that the data blocks are written in reverse order in the temporary file until the source file is depleted.

4. The method of claim 1, wherein performing the second transfer includes:

reading a data block from the temporary file beginning at the end of the temporary file;

expanding the destination file to accommodate the read data block;

writing the data block to the beginning of the destination file;

truncating the temporary file by removing the read data block from the end of the file;

repeating the reading, expanding, writing, and truncating operations for each data block in the temporary file such that the data blocks are written in reverse order in the destination file until the temporary file is depleted; and

deleting the temporary file.

5. The method of claim 1, wherein the transformation includes at least one from a set of:

encryption, decryption, compression, decompression, format change, and copy operation.

6. The method of claim 1, further comprising:

inserting an End-Of-File (EOF) indicator to the end of the destination file upon completion of the second transfer operation.

7. The method of claim 1, wherein the filler data includes one of “

0”

bits and “

1”

bits.

8. The method of claim 1, wherein a size of the data blocks is determined by the underlying file system.

9. A system for performing in-place data transformation in a file system, the system comprising:

a data storage device;

a memory;

a processor coupled to the memory, wherein the processor is configured to execute program modules for transforming data in a file stored in the data storage device, the modules including;

a transformation module configured to;

create a log file that includes a name of a source file, a size of the source file, a type of the transformation, and a direction of the transformation;

create a temporary file;

if a last data block of the source file is a truncated block, insert filler data into the last data block such that the last data block becomes a same size as remaining data blocks of the source file;

perform a first transfer operation by transferring data from the source file to the temporary file in individual data blocks in a back to front fashion such that the temporary file is expanded and the source file is truncated after transfer of each data block and the data blocks are written in a reverse order in the temporary file;

delete the source file and remove the filler data from a last data block of the destination file upon completion of the first transfer operation;

create a destination file;

perform a second transfer operation by transferring data from the temporary file to the destination file in individual data blocks in a back to front fashion such that the destination file is expanded and the temporary file is truncated after transfer of each data block and the data blocks are written in a reverse order in the destination file; and

delete the temporary file upon completion of the second transfer operation, wherein the data is transformed during one of;

the first transfer operation and the second transfer operation.

10. The system of claim 9, further comprising:

a recovery module configured to;

read the log file and determine a number of blocks in the temporary file following a mid-transaction interruption;

determine whether the source file has been truncated following a corresponding data block transfer;

if the source file has been truncated following the corresponding transfer, continue performing a remainder of the first and second transfer operations; and

if the source file has not been truncated following the corresponding transfer, continue performing the remainder of the first and second transfer operations by overwriting a last transferred data block prior to the interruption.

11. The system of claim 10, wherein the recovery module is further configured to determine that the transfer operations to be completed if the source file does not exist and the temporary file does not contain any data following the interruption.

12. The system of claim 10, wherein the recovery module is further configured to create the destination file and perform the first and second transfer operations if the source file and the destination file do not exist and the temporary file contains data following the interruption.

13. The system of claim 10, wherein the recovery module is further configured to:

determine a number of data blocks in the destination file if the source file does not exist, the destination file does exist, and the temporary file contains data following the interruption;

determine whether the temporary file has been truncated following a corresponding data block transfer;

if the temporary file has been truncated following the corresponding transfer, continue performing a remainder of the second transfer operations; and

if the temporary file has not been truncated following the corresponding transfer, continue performing the remainder of the second transfer operations by overwriting a last transferred data block prior to the interruption.

14. The system of claim 10, wherein the recovery module is further configured to lock the data storage device against any write operations before performing recovery and unlock the data storage device upon successful completion of the recovery.

15. A computer-readable storage medium with instructions encoded thereon for performing in-place data transformation in a file system, the instructions comprising:

creating a log file that includes at least one form a set of;

a name of a source file, a size of the source file, a type of the transformation, and a direction of the transformation;

creating a temporary file;

if a last data block of the source file is a truncated block, inserting filler data into the last data block such that the last data block becomes the same size as remaining data blocks of the source file;

performing a first transfer operation by transferring data from the source file to the temporary file in individual data blocks such that an order of the data blocks is reversed in the temporary file, wherein the temporary file is expanded and the source file is truncated after the transfer of each data block;

deleting the source file upon completion of the first transfer operation;

creating a destination file;

performing a second transfer operation by transferring data from the temporary file to the destination file in individual data blocks such that an order of the data blocks is reversed in the destination file, wherein the destination file is expanded and the temporary file is truncated after the transfer of each data block; and

deleting the temporary file and removing the filler data from a last data block of the destination file upon completion of the second transfer operation, wherein the data is transformed during at least one of;

the first transfer operation and the second transfer operation.

16. The computer-readable storage medium of claim 15, wherein the instructions further comprise:

performing a data recovery operation in response to a mid-transaction interruption based on the source file size, a number of data blocks in the temporary file after the interruption, and a number of data blocks in the destination file after the interruption.

17. The computer-readable storage medium of claim 16, wherein the instructions further comprise:

overwriting a last written data block in the temporary file if the source file is not truncated after a corresponding write operation into the temporary file; and

overwriting a last written data block in the destination file if the temporary file is not truncated after a corresponding write operation into the destination file.