Data processing

• US 8,095,678 B2
• Filed: 06/29/2007
• Issued: 01/10/2012
• Est. Priority Date: 06/30/2006
• Status: Active Grant

• Current Assignee: Data Equation Limited
• Original Assignee: Data Equation Limited
• Inventors: Worrall, David Tom
• Primary Examiner(s): Ibrahim, Mohamed
• Application Number:
  US11/824,611
• Publication Number:
  US 20080016107A1
• Time in Patent Office: 1,656 Days
• Field of Search: 709/201, 709/205, 709/231, 709/232, 707/791, 707/797, 707/821, 707/822, 707/825, 707/828, 707/830
• US Class Current: 709/231
• CPC Class Codes: G06F 11/1464 for networked environments
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 3/0638 Organizing or formatting or addressing of data
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

Data is stored in streams of varying size, a plurality of data streams are linked by references to form an application file such that each data stream is a portion of an application file, and an operating system transfers said application file between storage and a client application. Data streams that are below a predetermined size are identified as data fragments, wherein a plurality of data fragments are written to storage in a data block. Each data fragment is analysed to determine whether it is related in content to a first set of data fragments or to a second set of data fragments, the first set of data fragments is placed in a first block and the second set of data fragments is placed in a second block.

Claims

1. A method comprising storing data streams in data blocks wherein:

data is stored in said data streams, which are of varying size, and at least one of said data streams includes a reference to another one of said data streams,

a plurality of said data streams, linked to each other by references, form an application file such that each one of said plurality of data streams is a portion of an application file, and

an operating system transfers said application file between storage and a client application;

said method comprising steps of;

identifying a set of said data blocks as fragment blocks;

identifying data streams that are below a predetermined size as data fragments, thereby defining sets of data fragments, wherein said sets of data fragments are stored in said fragment blocks;

receiving an instruction from said operating system to write a first one of said data fragments to storage;

analysing said first one of said data fragments to determine that it is related in content to a first one of said sets of data fragments or that it is related to a second one of said sets of data fragments, wherein said first one of said sets of data fragments is stored in a first one of said fragment blocks and said second one of said sets of data fragments is stored in a second one of said fragment blocks;

in response to determining that said first one of said data fragments is related in content to said first one of said sets of data fragments, storing said first one of said data fragments in said first one of said fragment blocks;

in response to determining that said first one of said data fragments is related in content to said second one of said sets of data fragments, storing said first one of said data fragments in said second one of said fragment blocks.

2. A method according to claim 1, wherein said data fragments are considered to be related if they are portions of application files stored within the same application directory.

3. A method according to claim 1, wherein said first one of said data fragments is considered to be related to a second one of said data fragments if the first one of said data fragments contains a reference to the second one of said data fragments.

4. A method according to claim 1, wherein said data streams are part of an index having a parent-child tree structure, and wherein a first one of said data fragments and a second one of said data fragments are considered to be related if the first one of said data fragments is the parent of the second one of said data fragments.

5. A method according to claim 1, wherein said data blocks are stored within operating system files.

6. A method according to claim 4, wherein each operating system file contains 1000 data blocks.

7. A method according to claim 1, wherein fragment blocks are grouped into sets of fragment blocks, thereby defining fragment sets, and related data fragments are stored within fragment sets.

8. A method according to claim 7, wherein a data fragment may be split over two fragment blocks within one of said fragment sets.

9. A method according to claim 7, wherein one fragment block in said fragment set contains a fragment offset array that specifies a location of each data fragment within said fragment set, and each data fragment is referenced by an offset within said fragment offset array of its location.

10. A method according to claim 7, wherein one of said fragment sets has a child fragment set, and wherein related data fragments are stored within said child fragment set if one of said fragment sets is full.

11. A non-transitory computer-readable medium having computer-readable instructions executable by a computer such that when executing said instructions a computer will perform steps of:

storing data streams in data blocks, wherein;

data is stored in said data streams, which are of varying size, and at least one of said data streams includes a reference to another one of said data streams,

a plurality of said data streams, linked to each other by references, form an application file such that each one of said plurality of data streams is a portion of an application file, and

an operating system transfers said application file between storage and a client application;

identifying a set of said data blocks as fragment blocks;

identifying data streams that are below a predetermined size as data fragments, thereby defining sets of data fragments, wherein said sets of data fragments are stored in said fragment blocks;

receiving an instruction from said operating system to write a first one of said data fragments to storage;

analysing said first one of said data fragments to determine that it is related in content to a first one of said sets of data fragments or that it is related to a second one of said sets of data fragments, wherein said first one of said sets of data fragments is stored in a first one of said fragment blocks and said second one of said sets of data fragments is stored in a second one of said fragment blocks;

in response to determining that said first one of said data fragments is related in content to said first one of said sets of data fragments, storing said first one of said data fragments in said first one of said fragment blocks;

in response to determining that said first one of said data fragments is related in content to said second one of said sets of data fragments, storing said first one of said data fragments in said second one of said fragment blocks.

12. A non-transitory computer-readable medium according to claim 11, wherein said data fragments are considered to be related if they are portions of application files stored within the same application directory.

13. A non-transitory computer-readable medium according to claim 11, wherein said first one of said data fragments is considered to be related to a second one of said data fragments if the first one of said data fragments contains a reference to the second one of said data fragments.

14. A non-transitory computer-readable medium according to claim 11, wherein said data streams are part of an index having a parent-child tree structure, and wherein a first one of said data fragments and a second one of said data fragments are considered to be related if the first one of said data fragments is the parent of the second one of said data fragments.

15. A non-transitory computer-readable medium according to claim 11, wherein said data blocks are stored within operating system files.

16. A non-transitory computer-readable medium according to claim 11, wherein fragment blocks are grouped into sets of fragment blocks, thereby defining fragment sets, and related fragments are stored within fragment sets.

17. A non-transitory computer-readable medium according to claim 16, wherein a data fragment may be split over two fragment blocks within one of said fragment sets.

18. A non-transitory computer-readable medium according to claim 16, wherein one fragment block in said fragment set contains a fragment offset array that specifies a location of each data fragment within said fragment set, and each data fragment is referenced by an offset within said fragment offset array of its location.

19. A non-transitory computer-readable medium according to claim 16, wherein one of said fragment sets has a child fragment set, and wherein related data fragments are stored within said child fragment set if one of said fragment sets is full.

20. Data storage apparatus, comprising a data storage device and a processing device executing an operating system to facilitate transfers of application files between said storage device and a client application program, wherein:

data streams are stored in data blocks in said storage device,

data is stored in said data streams, which are of varying size, and at least one of said data streams includes a reference to another one of said data streams, and

a plurality of said data streams, linked to each other by references, form an application file; and

wherein said processing device is configured to;

identify a set of said data blocks as fragment blocks;

identify data streams that are below a predetermined size as being data fragments, thereby defining sets of data fragments, wherein said sets of data fragments are stored on said storage device in one of said fragment blocks;

receive an instruction from said operating system to write a first one of said data fragments to said storage device;

analyze said first one of said data fragments to determine that it is related in content to a data fragment of a first type or that it is related to a data fragment of a second type, wherein said data fragment of a first type are stored in a first one of said fragment blocks and said data fragment of a second type are stored in a second one of said fragment blocks;

in response to determining that said first one of said data fragments is related in content to said data fragment of a first type, storing said first one of said data fragments in said first one of said fragment blocks;

in response to determining that said first one of said data fragments is related in content to said data fragment of a second type, storing said first one of said data fragments in said second one of said fragment blocks.

21. Apparatus according to claim 20, wherein said processing device determines that data fragments are of the same type if the originate from a shared application directory, wherein the data fragments make up application files stored within applications directories under the control of the operating system.

22. Apparatus according to claim 20, wherein said processing device identifies two data fragments as being related if one references the other, wherein the originating data streams contain references to other data streams.

23. Apparatus according to claim 20, wherein said processing device determines that a data fragment is related to another if one data fragment is a parent to the other data fragment, wherein the data streams identified as data fragments are part of an index having a parent-child tree-like structure.

24. Apparatus according to claim 20, wherein said processing device writes a plurality of data blocks to a single operating system file.