Method for data storage organization

• US 6,434,678 B1
• Filed: 06/21/1999
• Issued: 08/13/2002
• Est. Priority Date: 02/12/1999
• Status: Expired due to Fees

• Current Assignee: GTP, Inc.
• Original Assignee: GTP, Inc.
• Inventors: Menzel, Uwe
• Primary Examiner(s): Kim, Mathew
• Assistant Examiner(s): CHACE, CHRISTIAN
• Application Number:
  US09/337,305
• Time in Patent Office: 1,149 Days
• Field of Search: 711/154, 711/165, 711/153, 711/156, 711/170, 711/173, 711/141, 711/159, 711/161, 707/200, 707/205
• US Class Current: 711/156
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0673 Single storage device

Abstract

A method for fast, high-density data storage in a data storage device having plural storage sections that includes overwriting and reformatting of entire storage sections, each having a large storage capacity. New or changed data is written continuously on free storage sites of a particular storage section until it is filled. Data from the newly-filled section is restructured and copied to a target section. Additional data is then stored onto a second storage section while the first storage section is restructured and copied. The previously-filled section may be reformatted to store new data after the second storage section is filled with data. The process may be repeated to allow for continuous data storage.

Claims

1. A method of data storage in a device including a storage medium having at least two storage sections, comprising:

writing data in a first storage section until said first storage section is filled to a predetermined capacity;

writing data in a second storage section after said first storage section is filled to said predetermined capacity;

determining occurrences of distinct data files within said data in said first storage section and evaluating said occurrences to eliminate non-unique occurrences of each distinct data file within said data of said first storage section; and

ascertaining a most recently updated occurrence of each data file and copying said most recently updated occurrence as a first restructured data to a target storage section, as a function of said filling of said first storage section to said predetermined capacity.

2. The method as recited in claim 1, wherein said target storage section is said second storage section, and said first restructured data is copied into said second storage section, and wherein said method further comprises:

initializing said first storage section;

writing said data in said second storage section in a first direction, wherein said first direction is one of top-to-bottom and bottom-to-top, until said second storage section is filled to said predetermined capacity;

determining occurrences of distinct data files within said data in said second storage section and evaluating said occurrences to eliminate non-unique occurrences of each distinct file of said data of said second storage section;

ascertaining a most recently updated occurrence of said data and copying said most recently updated occurrence as second restructured data when said second storage section is filled to said predetermined capacity, and copying said second restructured data into said first storage section in a second predetermined direction, wherein said second direction is one of bottom-to-top and top-to-bottom, while new and modified data is stored in said first storage section in said first predetermined direction.

3. The method as recited in claim 2, wherein said first predetermined direction is from a top to a bottom of a respective storage section, and wherein said second predetermined direction is from said bottom to said top of said respective storage section.

4. The method as recited in claim 2, further comprising initializing said second storage section and repeating said method of data storage to store additional data.

5. The method as recited in claim 1, wherein individual bits comprising said data in a storage section are not overwritten when data is modified or deleted.

6. The method as recited in claim 1, wherein said target storage section comprises a third storage section, and said method further comprises:

initializing said first storage section;

writing data in said second storage section until said second storage section is filled to said predetermined capacity;

determining, evaluating, ascertaining and copying said data in said second storage section into second restructured data when said second storage section is filled to said predetermined capacity, and copying said second restructured data to said third storage section while data is written to said first storage section.

7. The method as recited in claim 6, further comprising initializing said second storage section and repeating said method of data storage to store additional data.

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

initializing said second storage section;

determining, evaluating, ascertaining and copying, at specified times, said first restructured data and said second restructured data in said third storage section into third restructured data and copying said third restructured data to said second storage section;

initializing said second third section; and

exchanging the designations of said third storage section and said second storage section in said method and repeating said method of data storage to store additional data.

9. The method as recited in claim 6, further comprising:

initializing said second storage section;

determining, evaluating, ascertaining and copying, at specified times, said first restructured data and said second restructured data in said third storage section into third restructured data and copying said third restructured data to said first storage section;

initializing said third storage section; and

exchanging the designations of said first storage section and said third storage section in said method and repeating said method of data storage to store additional data.

10. The method as recited in claim 6, further comprising:

initializing said second storage section;

determining, evaluating, ascertaining and copying, at specified times, said first restructured data and said second restructured data in said third storage section into third restructured data and copying said third restructured data to a fourth storage section;

initializing said third storage section;

exchanging the designations said fourth storage section and said third storage section in said method and repeating said method of data storage to store additional data.

11. The method as recited in claim 1, wherein said steps of determining, evaluating, ascertaining and copying said data of said first storage section into first restructured data and copying said first restructured data into said target storage section comprises:

reading information contained in a table of contents of said first storage section;

determining occurrences of files stored in said first storage section and an operation performed on said files;

determining a type of operation performed on a particular file of said files; and

copying said particular file to said target storage section in accordance with said type of operation.

12. The method as recited in claim 11, wherein said determining a type of operation for each of said files comprises determining if said operation is one of a modify, create or a delete operation.

13. The method as recited in claim 12, wherein if said operation is a delete or modify operation, then said copying is not performed.

14. The method as recited in claim 13, wherein if said operation is a create operation and no modify operations are associated with subsequent occurrences of said particular file, then said copying is performed.

15. The method as recited in claim 13, wherein if said operation is a modify, then said method further comprises determining if subsequent modify operations were performed on said particular file, and if so, performing said copying for only the most recent version of said particular file.

16. The method as recited in claim 1, wherein said data is accessed in individual blocks.

17. The method as recited in claim 1, wherein said predetermined capacity is approximately 100 percent of an available capacity of a respective storage section at the point in time when data is initially written to said respective storage section.

18. A method of determining, evaluating, ascertaining and copying data stored in a first storage section into first restructured data and copying said first restructured data into a target storage section comprising:

triggering said restructuring of data by reaching a predetermined capacity in a first storage section;

reading information contained in a table of contents of said first storage section;

determining occurrences of files and evaluating said occurrences to eliminate non-unique occurrences of each distinct file of said data of said first storage section, and determining a most recently updated occurrence of said files stored in said first storage section and an operation performed on said files;

ascertaining a type of operation performed on the most recently updated occurrence of a particular file of said files; and

copying said particular file to said target storage section in accordance with said type of operation.

19. The method as recited in claim 18, wherein said determining a type of operation for each of said files comprises determining if said operation is one of a modify, create or a delete operation.

20. The method as recited in claim 19, wherein if said operation is a delete or modify operation, then said copying is not performed.

21. The method as recited in claim 20, wherein if said operation is a create operation and no modify operations are associated with subsequent occurrences of said particular file, then said copying is performed.

22. The method as recited in claim 20, wherein if said operation is a modify, then said method further comprises determining if subsequent modify operations were performed on said particular file, and if so, performing said copying for only the most recent version of said particular file.