File system having transaction record coalescing

• US 7,873,683 B2
• Filed: 06/09/2006
• Issued: 01/18/2011
• Est. Priority Date: 07/01/2005
• Status: Active Grant

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: QNX Software Systems Company (Blackberry Limited)
• Inventors: Dodge, Dan
• Primary Examiner(s): Ali; Mohammad
• Assistant Examiner(s): Smith; Brannon W
• Application Number:
  US11/450,141
• Publication Number:
  US 20070005627A1
• Time in Patent Office: 1,684 Days
• Field of Search: 707/200, 707/999.2, 707/824, 707/826, 711/104
• US Class Current: 707/824
• CPC Class Codes: G06F 16/50 of still image data

Abstract

An electronic data system comprises memory storage having stored data, file system software, and a transaction file. The transaction file is maintained by the file system software, and includes a plurality of transaction records corresponding to transactions that have been or are to be executed on one or more files and/or the or more directories of the file system. The file system software operates to organize and maintain the stored data in the files and directories and also to coalesce multiple transaction records meeting one or more criteria into fewer coalesced transaction records. The physical memory space required by the transaction file is reduced by the transaction record coalescing. The coalesced transaction records may be constructed so that they represent a logical result of applying each transaction record of a transaction record set in chronological order. Once the coalesced transaction records have been committed in the file system, the physical memory used by the original transaction records in the set may be reclaimed for further use (e.g., to store further transaction records) or may be otherwise removed from further use (e.g., when the physical memory is located in a block of memory in a flash-like memory device that has reached its maximum number of write and/or erase cycles).

Claims

1. An electronic data system comprising:

a flash memory having a stored data;

a file system code executable to organize and maintain the stored data in one or more files and one or more directories;

a transaction file maintained by the file system code in the flash memory, the transaction file comprising a plurality of transaction records stored on the flash memory, where the plurality of transaction records correspond to a plurality of transactions that have been, or are to be executed, on the one or more files and/or the one or more directories, where each transaction record of the plurality of transaction records comprises a header section and a data section, where each header section identifies a file of the one or more files and/or a directory of the one or more directories associated with each data section; and

where the file system code coalesces the plurality of transaction records stored on the flash memory by;

scanning each header section of each transaction record of the plurality of transaction records to identify a first subset of the plurality of transaction records directed to a same file, a second subset of the plurality of transaction records directed to a same logical portion of a file, and/or a third subset of the plurality of transaction records directed to a same directory, and

combining the first subset of the plurality of transaction records identified during the scanning as directed to the same file into one or more first coalesced transaction records and releasing one or more transaction records of the first subset of the plurality of transaction records identified as directed to the same file as a free memory to thereby reduce an amount of memory used by the transaction file,

combining the second subset of the plurality of transaction records identified during the scanning as directed to the same logical portion of the file into one or more second coalesced transaction records and releasing one or more transaction records of the second subset of the plurality of transaction records identified as directed to the same logical portion of the file as the free memory to thereby reduce the amount of memory used by the transaction file, and/or

combining the third subset of the plurality of transaction records identified during the scanning as directed to the same directory into one or more third coalesced transaction records and releasing one or more transaction records of the third subset of the plurality of transaction records identified as directed to the same directory as the free memory to thereby reduce the amount of memory used by the transaction file;

and where each header section of each transaction record of the plurality of transaction records further comprises a first field used to determine the starting address at which the data section is to be written into the identified file of the one or more files and/or the identified directory of the one or more directories, and a second field used to determine an amount of the identified file of the one or more files and/or the identified directory of the one or more directories that is to be overwritten.

2. The electronic data system of claim 1 where the file system code is executable to assign one or more transaction identifiers to the one or more first coalesced transaction records, the one or more second coalesced transaction records and/or the one or more third coalesced transaction records.

3. The electronic data system of claim 1 where the file system code further coalesces the plurality of transaction records stored on the flash memory by:

generating a first transaction record set comprising the first subset of the plurality of transaction records directed to the same file,

generating a second transaction record set comprising the second subset of the plurality of transaction records directed to the same logical portion of the file, and/or

generating a third transaction record set comprising the third subset of the plurality of transaction records directed to the same directory pursuant to coalescing the plurality of transaction records.

4. The electronic data system of claim 3 where the first, the second, and/or the third transaction record sets comprise a plurality of pointers to a plurality of locations in the transaction file of the first, the second, and/or the third subset of the plurality of transaction records, respectively.

5. The electronic data system of claim 3 where the first, the second, and/or the third transaction record sets are formatted in a same manner as a manner in which a corresponding transaction record of the plurality of transaction records is formatted in the transaction file.

6. The electronic data system of claim 3 where the file system code is further executable to:

apply, pursuant to generating the first transaction record set, the first subset of the plurality of transaction records directed to the same file in a first chronological sequence corresponding to a first time order in which each transaction record of the first subset of the plurality of transaction records directed to the same file originally occurred;

apply, pursuant to generating the second transaction record set, the second subset of the plurality of transaction records directed to the same logical portion of a file in a second chronological sequence corresponding to a second time order in which each transaction record of the second subset of the plurality of transaction records directed to the same logical portion of the file occurred; and

/or

apply, pursuant to generating the third transaction record set, the third subset of the plurality of transaction records directed to the same directory in a third chronological sequence corresponding to a third time order in which each transaction record of the second subset of the plurality of transaction records directed to the same directory occurred.

7. The electronic data system of claim 3 where file system code is executable to:

combine the plurality of transaction records of the first transaction record set to reduce a first number of transaction records directed to the same file;

combine the plurality of transaction records of the second transaction record set to reduce a second number of transaction records directed to the same logical portion of a file; and

/or

combine the plurality of transaction records of the third transaction record set to reduce a third number of transaction records directed to the same directory.

8. The electronic data system of claim 1 where the file system code is executable to reclaim a residual physical storage space that results from coalescing the plurality of transaction records for use in storing additional transaction records.

9. The electronic data system of claim 1 where each header section of each transaction record of the plurality of transaction records further comprises a status field which is indicative of whether each transaction record of the plurality of transaction records has been committed.

10. A computer readable storage medium having a plurality of computer- executable instructions for performing a method comprising:

organizing and maintaining a plurality of files and a plurality of directories stored on a flash memory device;

maintaining, on the flash memory device, a transaction file comprising a plurality of transaction records where each transaction record comprises a header section and a data section, where each header section identifies a file of the plurality of files and/or a directory of the plurality of directories associated with each data section;

coalescing the plurality of transaction records stored on the flash memory device by;

scanning each header section of each transaction record of the plurality of transaction records to identify a first subset of the plurality of transaction records directed to a same file, a second subset of the plurality of transaction records directed to a same logical portion of a file, and/or a third subset of the plurality of transaction records directed to a same directory,

combining the first subset of the plurality of transaction records identified during the scanning as directed to the same file into one or more first coalesced transaction records and releasing one or more transaction records of the first subset of the plurality of transaction records identified as directed to the same file to thereby reduce an amount of memory used by the transaction file,

combining the second subset of the plurality of transaction records identified during the scanning as directed to the same logical portion of the file into one or more second coalesced transaction records and releasing one or more transaction records of the second subset of the plurality of transaction records identified as directed to the same logical portion of the file to thereby reduce the amount of memory used by the transaction file, and/or

combining the third subset of the plurality of transaction records identified during the scanning as directed to the same directory into one or more third coalesced transaction records and releasing one or more transaction records of the third subset of the plurality of transaction records identified as directed to the same directory to thereby reduce the amount of memory used by the transaction file;

and where each header section of each transaction record of the plurality of transaction records further comprises a first field used to determine the starting address at which the data section is to be written into the identified file of the one or more files and/or the identified directory of the one or more directories, and a second field used to determine an amount of the identified file of the one or more files and/or the identified directory of the one or more directories that is to be overwritten.

11. The computer readable storage medium of claim 10 where the method further comprises assigning one or more transaction identifiers to the one or more first coalesced transaction records, the one or more second coalesced transaction records, and/or the one or more third coalesced transaction records.

12. The computer readable storage medium of claim 10 where the method further comprises:

generating, pursuant to coalescing the plurality of transaction records, a first transaction record set from the first subset of the plurality of transaction records directed to the same file;

generating, pursuant to coalescing the plurality of transaction records, a second transaction record set from the second subset of the plurality of transaction records directed to the same logical portion of the file, and/or

generating, pursuant to coalescing the plurality of transaction records, a third transaction record set from the third subset of the plurality of transaction records directed to the same directory.

13. The computer readable storage medium of claim 12 where the method further comprises:

combining the plurality of transaction records of the first transaction record set to reduce a first number of transaction records directed to the same file;

combining the plurality of transaction records of the second transaction record set to reduce a second number of transaction records directed to the same logical portion of the file; and

/or

combining the transaction records of the third transaction record set to reduce a third number of transaction records directed to the same directory.

14. The computer readable storage medium of claim 12 where the method further comprises:

combining the plurality of transaction records of the first transaction record set to generate a first single record directed to the same file;

combining the plurality of transaction records of the second transaction record set to generate a second single record directed to the same logical portion of the file; and

/or

combining the plurality of transaction records of the third transaction record set to generate a third single record directed to the same directory.

15. The computer readable storage medium of claim 10 where each header section of each transaction record of the plurality of transaction records further comprises a first verification field to verify and correct the header section of each transaction record of the plurality of transaction records and a second verification field to verify and correct the data section of each transaction record of the plurality of transaction records.

16. The computer readable storage medium of claim 10 where each header section of each transaction record of the plurality of transaction records further comprises a first status field indicative of a condition of a memory location in which each transaction record of the plurality of transaction records is stored.