Fast storage writes

• US 8,417,679 B1
• Filed: 05/21/2009
• Issued: 04/09/2013
• Est. Priority Date: 05/21/2008
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: TransLattice, Inc.
• Inventors: Lyle, Michael P., Vekhter, Daniel, Sherman, John F. II
• Primary Examiner(s): DWIVEDI, MAHESH H
• Application Number:
  US12/454,850
• Time in Patent Office: 1,419 Days
• Field of Search: 707/999.101, 707/696, 707/797
• US Class Current: 707/696
• CPC Class Codes: G06F 16/13 File access structures, e.g. distributed indices arrangements of input from, or output to, record carriers G06F3/06

Abstract

Updating an index is disclosed. An indication of one or more changes to be made to data is received. The one or more changes are written to a storage medium prior to updating one or more file name index entries. One or more file name index entries are updated prior to writing a new index tree root. A new index tree root is written.

Claims

1. A method for updating an index, comprising:

receiving an indication of one or more changes to be made to data associated with corresponding portions of an index tree;

in response to receipt of the indication, acquiring a top-level lock on a first index tree root associated with the index tree;

identifying a new location associated with a set of contiguous unused blocks from a data structure configured to store data indicating contiguous unused space associated with a storage medium, wherein the set of contiguous unused blocks is associated with an amount sufficient to support a contiguous write;

writing the one or more changes to the data to the storage medium prior to updating one or more file name index entries associated with the portions of the index tree corresponding to the changed data, wherein writing the one or more changes includes copying at least the portions of the index tree associated with the changes to be made to the set of contiguous unused blocks associated with the new location on the storage medium and writing the one or more changes to at least a copy of the portions of the index tree at the new location;

updating the data structure configured to store data indicating contiguous unused space associated with the storage medium;

updating the one or more file name index entries;

releasing the top-level lock on the first index tree root; and

writing a second index tree root over the first index tree root, wherein writing the second index tree root includes updating a version number associated with the index tree and the second index tree root is written over the first index tree root subsequent to the one or more file name index entries being updated.

2. The method of claim 1 further comprising updating one or more content groups index entries associated with the portions of the index tree corresponding to the changed data.

3. The method of claim 1 wherein updating the one or more content group index entries includes updating the one or more content group index entries associated with the portions of the index tree corresponding to the changed data prior to updating the one or more file name index entries.

4. The method of claim 1 further comprising flushing a result to the storage medium.

5. The method of claim 1 wherein the one or more changes are received from a plurality of processes.

6. The method of claim 1 wherein the one or more changes are associated with a plurality of files.

7. The method of claim 1, further comprising indicating each of those corresponding portions of the index tree as being dirty.

8. The method of claim 1, wherein the storage medium comprises a disk.

9. A system for updating an index, comprising:

a processor; and

a memory coupled with the processor, wherein the memory is configured to provide the processor with instructions which when executed cause the processor to;

receive an indication of one or more changes to be made to data associated with corresponding portions of an index tree;

in response to receipt of the indication, acquire a top-level lock on a first index tree root associated with the index tree;

identify a new location associated with a set of contiguous unused blocks from a data structure configured to store data indicating contiguous unused space associated with a storage medium, wherein the set of contiguous unused blocks is associated with an amount sufficient to support a contiguous write;

write the one or more changes to the storage medium prior to updating one or more file name index entries associated with the portions of the index tree corresponding to the changed data, wherein writing the one or more changes includes copying at least the portions of the index tree associated with the changes to be made to the set of contiguous unused blocks associated with the new location on the storage medium and writing the one or more changes to at least a copy of the portions of the index tree at the new location;

update the data structure configured to store data indicating contiguous unused space associated with the storage medium;

update the one or more file name index entries;

release the top-level lock on the first index tree root; and

write a second index tree root over the first index tree root, wherein writing the second index tree root includes updating a version number associated with the index tree and the second index tree root is written over the first index tree root subsequent to the one or more file name index entries being updated.

10. The system of claim 9 wherein the processor is further configured to update one or more content groups index entries associated with the portions of the index tree corresponding to the changed data.

11. The system of claim 9 wherein updating the one or more content group index entries includes updating the one or more content group index entries associated with the portions of the index tree corresponding to the changed data prior to updating the one or more file name index entries.

12. The system of claim 9 wherein the processor is further configured to flush a result to the storage medium.

13. The system of claim 9 wherein the one or more changes are received from a plurality of processes.

14. The system of claim 9 wherein the one or more changes are associated with a plurality of files.

15. A computer program product for updating an index, the computer program product being embodied in a non-transitory computer readable storage medium and comprising computer instructions for:

receiving an indication of one or more changes to be made to data associated with corresponding portions of an index tree;

in response to receipt of the indication, acquiring a top-level lock on a first index tree root associated with the index tree;

identifying a new location associated with a set of contiguous unused blocks from a data structure configured to store data indicating contiguous unused space associated with a storage medium, wherein the set of contiguous unused blocks is associated with an amount sufficient to support a contiguous write;

writing the one or more changes to the data to the storage medium prior to updating one or more file name index entries associated with the portions of the index tree corresponding to the changed data, wherein writing the one or more changes includes copying at least the portions of the index tree associated with the changes to be made to the set of contiguous unused blocks associated with the new location on the storage medium and writing the one or more changes to at least a copy of the portions of the index tree at the new location;

updating the data structure configured to store data indicating contiguous unused space associated with the storage medium;

updating the one or more file name index entries;

releasing the top-level lock on the first index tree root; and

writing a second index tree root over the first index tree root, wherein writing the second index tree root includes updating a version number associated with the index tree and the second index tree root is written over the first index tree root subsequent to the one or more file name index entries being updated.

16. The computer program product recited in claim 15, further comprising computer instructions for updating one or more content groups index entries associated with the portions of the index tree corresponding to the changed data.

17. The computer program product recited in claim 15 wherein updating the one or more content group index entries includes updating the one or more content group index entries prior to updating the one or more file name index entries.