Utilization of memory storage

• US 7,765,378 B1
• Filed: 12/09/2002
• Issued: 07/27/2010
• Est. Priority Date: 06/01/2001
• Status: Active Grant

• Current Assignee: Citrix Systems, Inc. (Cloud Software Group)
• Original Assignee: Sanbolic, Inc. (Cloud Software Group)
• Inventors: Georgiev, Ivan I.
• Primary Examiner(s): Kim; Matt
• Assistant Examiner(s): Birkhimer; Christopher D
• Application Number:
  US10/314,900
• Time in Patent Office: 2,787 Days
• Field of Search: 711/173
• US Class Current: 711/173
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/0671 In-line storage system

Abstract

A file storage system can include a file manager that adaptively partitions memory to accommodate the storage of fragmented data information. The fragments, potentially of varying size, can be stored in a volume of memory that is partitioned to include a group of storage segments. In the event that a particular fragment is not sized to efficiently fit in a free storage segment, the segment can be further subdivided to accommodate a fragment. In this way, a segment allotted for storage of data information can be adaptively subdivided into a smaller group of storage sub-segments. These sub-segments and yet potentially smaller storage partitions of the sub-segments can then be used to store additional fragments of a related stream of data. Based on this technique, portions of a logical stream of data information can be stored in the segments that vary in size. Meta data associated with the stored fragments can be used to facilitate reconstruction of a file or data stream.

Claims

1. A method of utilizing storage, the method comprising:

allocating, via a computer system, a portion of the storage for storage of data information;

subsequent to receiving the data information for storage, recursively partitioning storage segments of the allocated portion of the storage on an as-needed basis into successively smaller groups of storage segments that vary in size to accommodate storage of corresponding smaller fragments of related data information;

allocating at least part of the storage to store meta data information associated with the storage segments; and

maintaining the meta data in the storage to track a logical stream of fragmented data information;

wherein recursively partitioning the storage segments includes;

receiving an amount of data information to be stored in a volume;

partitioning the volume to include a group of storage segments including a first storage segment and a second storage segment, the first storage segment defined by a first range of contiguous physical addresses, the second storage segment defined by a second range of contiguous physical addresses;

storing a first sized portion of the data information in the first storage segment;

in response to detecting that a second sized portion of the data information to be stored in the volume is smaller than a storage capacity of the second storage segment, subdividing the second storage segment into multiple sub-segments including at least a first storage sub-segment and a second storage sub-segment;

wherein subdividing the second storage segment into multiple sub-segments includes subdividing the second range of contiguous physical addresses into a first sub-range of contiguous physical addresses and a second sub-range of contiguous physical addresses, the first sub-range of contiguous physical addresses defining the first storage sub-segment of the second storage segment, the second sub-range of contiguous physical addresses defining the second storage sub-segment of the second storage segment; and

in response to detecting that the second sized portion of the data information to be stored in the volume is larger than a storage capacity of the first storage sub-segment;

selecting a sub-portion of the second sized portion of the data information, the selected sub-portion equal in size to the storage capacity of the first storage sub-segment, and

storing the selected sub-portion into the first storage sub-segment.

2. A method as in claim 1 further comprising:

adaptively partitioning the storage into groups of successively smaller storage elements to accommodate the storage of fragments of related data information.

3. A method as in claim 2 further comprising:

receiving a logical data stream to be stored in the storage; and

partitioning the logical data stream into fragments that are at least partially stored in the storage elements.

4. A method as in claim 1 further comprising:

maintaining a parameter that identifies an approximate location of where a stream of logically related data information is preferably stored in the volume.

5. A method as in claim 1 further comprising:

dividing a logical data stream into fragments of varying size;

storing the fragments in corresponding storage segments of varying size; and

maintaining a parameter identifying an approximate whereabouts of at least a substantial portion of the logical data stream stored in the storage.

6. A method as in claim 1 further comprising:

reconstructing a logical stream of data information stored in the storage by;

identifying a storage segment including a fragment of the data information to be reconstructed;

retrieving the fragment of data information stored in the identified storage segment;

utilizing meta data associated with the identified storage segment to determine a location of another segment storing a following logical portion of the data stream to be reconstructed.

7. A method as in claim 1 further comprising:

for groups of contiguous storage segments of substantially similar size, allocating a similarly situated block of storage space to store meta data associated with corresponding storage segments in a group.

8. A method of storing data information, the method comprising:

receiving, in a computer system, first data information to be stored in a volume;

partitioning the volume to include a group of storage segments including a first storage segment and a second storage segment, the first storage segment defined by a first range of contiguous physical addresses, the second storage segment defined by a second range of contiguous physical addresses;

storing a first sized portion of the first data information in the first storage segment;

in response to detecting that a second sized portion of the data information to be stored in the volume is smaller than a storage capacity of the second storage segment, subdividing the second storage segment of the volume into multiple sub-segments including at least a first storage sub-segment and a second storage sub-segment;

wherein subdividing the second storage segment into multiple sub-segments includes subdividing the second range of contiguous physical addresses into a first sub-range of contiguous physical addresses and a second sub-range of contiguous physical addresses, the first sub-range of contiguous physical addresses defining the first storage sub-segment of the second storage segment, the second sub-range of contiguous physical addresses defining the second storage sub-segment of the second storage segment; and

in response to detecting that the second sized portion of the first data information to be stored in the volume is larger than a storage capacity of the first storage sub-segment;

selecting a first sub-portion of the second sized portion, the first sub-portion equal in size to the storage capacity of the first storage sub-segment, and

storing the first sub-portion in the first storage sub-segment.

9. A method as in claim 8, wherein the second storage segment is partitioned based on a power of 2.

10. A method as in claim 8 further comprising:

allocating at least a portion of the first storage segment to store meta data.

11. A method as in claim 10, wherein the meta data includes a pointer identifying a location of another segment in the volume.

12. A method as in claim 10, wherein the meta data includes information identifying a type of data stored in the first storage segment.

13. A method as in claim 8 further comprising:

reconstructing a data stream stored in the volume by;

identifying a storage segment including at least part of the data stream to be reconstructed;

retrieving data information stored in the identified storage segment;

utilizing meta data associated with the identified storage segment to identify another location of a segment in the volume including a following logical portion of the data stream to be reconstructed.

14. A method as in claim 8 further comprising:

allocating a portion of the second storage segment to include meta data identifying a weighted address indicating an approximated storage location in the volume where the data information is generally stored.

15. The method as in claim 8, wherein partitioning the volume includes:

partitioning the first storage segment to be equal in size to the second storage segment.

16. The method as in claim 15 further comprising:

receiving a second amount of related data;

storing a first portion of the second amount of related data in a third storage sub-segment, the third storage sub-segment defined by a third range of contiguous physical addresses, the third storage sub-segment being equal in size to the first sub-storage segment and the second storage sub-segment;

partitioning the second storage sub-segment to include a first sub-sub-segment and a second sub-sub-segment, the first sub-sub-segment being equal in size to the second sub-sub-segment;

storing a second sub-portion of the second sized portion of the first data information in the first sub-sub-segment; and

storing a second portion of the second amount of related data in the second sub-sub-segment.

17. The method as in claim 16, wherein the second sub-portion of the second sized portion of the first data information is a remainder portion of the second sized portion of the first data information that is not stored in the first sub-segment.

18. The method as in claim 8, wherein the first storage segment and the second storage segment are of equal size.

19. The method as in claim 8, wherein the first storage segment and the second storage segment are contiguous with respect to each other.

20. A method comprising:

receiving, in a computer system, an amount of data information to be stored in a volume;

partitioning the volume to include a group of storage segments including a first storage segment and a second storage segment, the first storage segment defined by a first range of contiguous physical addresses, the second storage segment defined by a second range of contiguous physical addresses;

storing a first sized portion of the data information in the first storage segment;

in response to detecting that a second sized portion of the data information to be stored in the volume is smaller than a storage capacity of the second storage segment, subdividing the second storage segment into multiple sub-segments including at least a first storage sub-segment and a second storage sub-segment;

wherein subdividing the second storage segment into multiple sub-segments includes subdividing the second range of contiguous physical addresses into a first sub-range of contiguous physical addresses and a second sub-range of contiguous physical addresses, the first sub-range of contiguous physical addresses defining the first storage sub-segment of the second storage segment, the second sub-range of contiguous physical addresses defining the second storage sub-segment of the second storage segment; and

in response to detecting that the second sized portion of the data information to be stored in the volume is larger than a storage capacity of the first storage sub-segment;

selecting a sub-portion of the second sized portion of the data information, the selected sub-portion equal in size to the storage capacity of the first storage sub-segment, and

storing the selected sub-portion in the first storage sub-segment.