Transactional file system for flash memory

• US 7,139,883 B2
• Filed: 11/21/2002
• Issued: 11/21/2006
• Est. Priority Date: 02/27/2002
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Kalkman, John, Aasheim, Jered Donald, Yang, Yongqi
• Primary Examiner(s): Kim, Matthew
• Assistant Examiner(s): PATEL, HETUL B
• Application Number:
  US10/301,519
• Publication Number:
  US 20030163635A1
• Time in Patent Office: 1,461 Days
• Field of Search: 711/156, 707/204, 714/20, 714/19
• US Class Current: 711/156
• CPC Class Codes: G06F 11/1435 using file system or storage system metadata
• CPC Class Codes: G06F 11/1441 Resetting or repowering
• CPC Class Codes: G06F 11/1471 involving logging of persistent data for recovery
• CPC Class Codes: G06F 11/1474 in transactions G06F16/20 takes precedence
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 2212/7207 management of metadata or control data
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0643 Management of files
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99955 Archiving or backup

Abstract

A transactional file system developed to function with flash memory is described. The file system provides for efficient storage of file system meta-information, performs robust transaction logging, and performs other related features. In one described implementation, metadata is stored in-line with data. In another embodiment, a transaction log is maintained by storing transaction information associated with requests to perform file transactions. The transaction information is stored at arbitrary physical sector addresses on the flash medium. In still another embodiment, a transaction log is stored in a physical sector of a flash medium. The transaction log contains transaction information associated with performing a file request. Metadata is written into a spare area of the physical sector indicating that the physical sector contains transaction information.

Claims

1. In a computer having a flash medium, a method for recording a transaction log, comprising:

receiving requests to perform file transactions;

storing transaction information associated with the file transactions at arbitrary physical sectors having addresses from among all valid physical sector addresses on the flash medium; and

marking at least one of the arbitrary physical sectors containing transaction information as dirty when at least one of the file transactions corresponding to the transaction information is completed.

2. The method as recited in claim 1, wherein the arbitrary physical sector addresses include a next available free physical sector addresses on the flash medium indicated by a write pointer.

3. The method as recited in claim 1, wherein the transaction information includes transaction log data.

4. The method as recited in claim 1, wherein the transaction information includes metadata indicating that the arbitrary physical sectors contain transaction information.

5. The method as recited in claim 1, further comprising identifying the arbitrary physical sectors containing the transaction information.

6. The method as recited in claim 1, further comprising identifying the arbitrary physical sectors containing the transaction information by writing transaction log metadata into a spare area of the arbitrary physical sectors containing the transaction information.

7. The method as recited in claim 1, further comprising:

identifying the arbitrary physical sectors containing the transaction information by;

writing transaction log metadata into spare areas of each of the arbitrary physical sectors containing the transaction information; and

scanning the spare areas of the physical sectors on the flash medium for any physical sectors containing the transaction log metadata.

8. The method as recited in claim 1, further comprising:

writing a transaction log bit into spare areas of each of the arbitrary physical sectors containing the transaction information; and

scanning the spare areas of the physical sectors on the flash medium for any physical sectors containing the transaction log bit to identify those physical sectors containing transaction information.

9. A computer, comprising:

a processor;

a flash medium containing physical sectors, wherein each sector has an address; and

a file system configured to perform a file transaction, wherein the file system is configured to maintain a transaction log of the file transaction by storing transaction information associated with the file transaction at an arbitrary physical sector chosen from among all valid physical sector addresses on the flash medium, and further wherein the file system is configured to mark the chosen arbitrary physical sector containing the transaction information as dirty when the file transaction corresponding to the transaction information is completed.

10. The computer as recited in claim 9, wherein the chosen arbitrary physical sector includes a next available free physical sector address indicated by a write pointer on the flash medium.

11. The computer as recited in claim 9, wherein the transaction information includes transaction log data.

12. The computer as recited in claim 9, wherein the transaction information includes metadata indicative that the arbitrary physical sector contains transaction information.

13. The computer as recited in claim 9, wherein the file system is further configured to identify the chosen arbitrary physical sector containing the transaction information.

14. The computer as recited in claim 9, wherein the file system is further configured to identify the chosen arbitrary physical sector containing the transaction information by writing transaction log metadata into a spare area of the chosen arbitrary physical sector.

15. The computer as recited in claim 9, wherein the file system is further configured to identify the chosen arbitrary physical sector containing the transaction information by writing transaction log metadata into a spare area of the chosen arbitrary physical sector;

and scan spare areas of the physical sectors on the flash medium for the chosen arbitrary physical sector containing the transaction log metadata.

16. The computer as recited in claim 9, wherein the file system is further configured to write a transaction log bit into a spare area of the chosen arbitrary physical sector;

and scan spare areas of the physical sectors on the flash medium for the physical sector containing the transaction log bit to identify the address of the chosen arbitrary physical sector containing the transaction information.

17. One or more computer-readable media comprising computer executable instructions that, when executed, direct a computer to:

receive requests to perform file transactions;

record transaction information associated with the file transactions at arbitrary physical sectors on a flash medium, wherein the arbitrary physical sectors include physical sector addresses chosen from among all valid physical sector addresses on the flash medium; and

mark at least one of the arbitrary physical sectors containing transaction information dirty when at least one of the file transactions corresponding to the transaction information is completed.

18. One or more computer-readable media as recited in claim 17, wherein the transaction information includes transaction log data.

19. One or more computer-readable media as recited in claim 17, wherein the transaction information includes metadata indicating that the arbitrary physical sectors contain transaction information.

20. One or more computer-readable media as recited in claim 17, further comprising computer executable instructions that, when executed, direct a computer to identify the arbitrary physical sector addresses of the arbitrary physical sectors containing the transaction information.

21. One or more computer-readable media as recited in claim 17, further comprising computer executable instructions that, when executed, direct a computer to identify the arbitrary physical sector addresses of the arbitrary physical sectors containing the transaction information by writing transaction log metadata into a spare area of the physical sectors corresponding to the arbitrary physical sector addresses.

22. One or more computer-readable media as recited in claim 17, further comprising computer executable instructions that, when executed, direct a computer to identify the physical sector addresses of the arbitrary physical sectors containing the transaction information by writing transaction log metadata into spare areas of each of the arbitrary physical sectors corresponding to the physical sector addresses;

and scanning the spare areas of the physical sectors on the flash medium for any physical sectors containing the transaction log metadata.

23. One or more computer-readable media as recited in claim 17, further comprising computer executable instructions that, when executed, direct a computer to write a transaction log bit into spare areas of each of the physical sectors corresponding to the arbitrary physical sector addresses that store transaction information;

and scan the spare areas of the physical sectors on the flash medium for any physical sectors containing the transaction log bit to identify those physical sector addresses containing transaction information.

24. In a computer having a flash medium containing physical sectors to store data, a method for maintaining a transaction log on the flash medium, comprising:

storing a transaction log in an arbitrary physical sector chosen from among all valid physical sector addresses of a flash medium, the transaction log containing information associated with performing a file request;

indicating that the physical sector contains a transaction log by writing metadata into a spare area of the physical sector; and

marking the physical sector dirty, if the file request is completed.

25. The method as recited in claim 24, further comprising initializing the computer, and scanning the physical sectors for the physical sector containing the metadata indicative that the physical sector contains a transaction log.

26. The method as recited in claim 24, further comprising:

initializing the computer,

scanning the physical sectors not marked dirty for the physical sector containing the metadata indicative that the physical sector contains a transaction log; and

concluding that the file request is completed, if the physical sector containing the metadata is not located.

27. The method as recited in claim 24, further comprising:

initializing the computer,

scanning the physical sectors not marked dirty for the physical sector containing the metadata indicative that the physical sector contains a transaction log; and

concluding that the file request was not completed, if the physical sector containing the metadata is located.

28. The method as recited in claim 24, further comprising:

initializing the computer;

scanning the physical sectors not marked dirty for the physical sector containing the metadata indicative that the physical sector contains a transaction log;

concluding that the file request was not completed, if the physical sector containing the metadata is located; and

attempting to perform the file request specified by the transaction log.

29. The method as recited in claim 24, wherein information associated with performing the file request includes operation code indicating what command is associated with the file request.

30. The method as recited in claim 24, wherein the metadata is a bit in the spare area.

31. The method as recited in claim 24, wherein the physical sector containing the transaction log is located at an arbitrary physical sector address on the flash medium, wherein the arbitrary physical sector address includes any valid physical sector address not restricted to a fixed region of physical sector addresses on the flash medium.

32. One or more computer-readable media comprising computer executable instructions that, when executed, direct a computer to:

store a transaction log in an arbitrary physical sector chosen from among all valid physical sector addresses of a flash medium, the transaction log containing information associated with performing a file request;

indicate that the physical sector contains a transaction log by writing metadata into a spare area of the physical sector;

mark the physical sector dirty, if the file request is completed;

initialize the computer;

scan the physical sectors not marked dirty for the physical sector containing the metadata indicative that the physical sector contains a transaction log;

conclude that the file request was not completed after initialization, if the physical sector containing the metadata is located; and

attempt to perform the file request specified by the transaction log.

33. One or more computer-readable media as recited in claim 32, wherein the physical sector containing the transaction log is located at an arbitrary physical sector address on the flash medium, wherein the arbitrary physical sector address includes any valid physical sector address not restricted to a fixed region of physical sector addresses on the flash medium.

34. A computer, comprising:

a processor; and

a file system configured to (i) store a transaction log in an arbitrary physical sector chosen from among all valid physical sector addresses of a flash medium, the transaction log containing information associated with performing a file request;

(ii) indicate that the physical sector contains a transaction log by writing metadata into a spare area of the physical sector; and

(iii) mark the physical sector dirty, if the file request is completed.

35. The computer as recited in claim 34, wherein the physical sector containing the transaction log is located at an arbitrary physical sector address on the flash medium, wherein the arbitrary physical sector address includes any valid physical sector address not restricted to a fixed region of physical sector addresses on the flash medium.

36. The computer as recited in claim 34, wherein after the computer is initialized, the file system is further configured to scan the physical sectors for the physical sector containing the metadata indicative that the physical sector contains a transaction log.

37. The computer as recited in claim 34, wherein after the computer is initialized, the file system is further configured to scan the physical sectors not marked dirty for the physical sector containing the metadata indicative that the physical sector contains a transaction log;

and conclude that the file request is completed, if the physical sector containing the metadata is not located.

38. The computer as recited in claim 34, wherein after the computer is initialized, the file system is further configured to scan the physical sectors not marked dirty for the physical sector containing the metadata indicative that the physical sector contains a transaction log;

and conclude that the file request was not completed, if the physical sector containing the metadata is located.

39. The computer as recited in claim 34, wherein after the computer is initialized, the file system is further configured to scan the physical sectors not marked dirty for the physical sector containing the metadata indicative that the physical sector contains a transaction log;

conclude that the file request was not completed, if the physical sector containing the metadata is located; and

attempt to perform the file request specified by the transaction log.

40. The computer as recited in claim 34, wherein information associated with performing the file request includes operation code indicating what command is associated with the file request.

41. A system, comprising:

means for storing a transaction log in an arbitrary physical sector chosen from among all valid physical sector addresses of a storage device, the transaction log containing information associated with performing a file request;

means for indicating that the physical sector contains a transaction log by writing metadata into a spare area of the physical sector; and

means for marking the physical sector dirty, if the file request is completed wherein the physical sector containing the transaction log is located at an arbitrary location on the storage device, wherein the arbitrary location includes any valid address not restricted to a fixed region of addresses on the storage device.