Random allocation of media storage units

• US 7,945,587 B2
• Filed: 10/10/2007
• Issued: 05/17/2011
• Est. Priority Date: 10/10/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Hardy, Edward W.
• Primary Examiner(s): Wong; Don
• Assistant Examiner(s): HO, BINH VAN
• Application Number:
  US11/973,756
• Publication Number:
  US 20090125573A1
• Time in Patent Office: 1,315 Days
• Field of Search: 707/205, 707/793
• US Class Current: 707/793
• CPC Class Codes: G06F 16/13 File access structures, e.g. distributed indices arrangements of input from, or output to, record carriers G06F3/06
• CPC Class Codes: G06F 21/6209 to a single file or object, e.g. in a secure envelope, encrypted and accessed using a key, or with access control rules appended to the object itself
• CPC Class Codes: G06F 3/0623 in relation to content
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0671 In-line storage system

Abstract

Described is a technology by which storage space in the form of allocation units (e.g., clusters of a storage volume) are intentionally allocated so as to likely be non-contiguous for a file'"'"'s data. For example, random selection of each of the allocation units will likely provide non-contiguous allocation units; on solid state storage media, such a random distribution of a file'"'"'s data does not significantly affect access times. In one aspect, a file system driver randomly allocates the allocation units, and records the allocation units in association with the file, e.g., in a master file table or similar database. Non-contiguous (e.g., random) allocation may be on demand as storage space is needed, and/or may be performed in anticipation of needing storage space for satisfying a later request. Once the storage space is no longer mapped to a file, reconstructing that file'"'"'s data in forensic analysis is more difficult.

Claims

1. A computer-readable storage medium comprising computer-executable instructions, which when executed perform acts, comprising:

allocating a primary two or more randomly selected non-contiguous allocation units of a single storage unit, the primary two or more randomly selected non-contiguous allocation units corresponding to a first file, the single storage unit not comprising a plurality of non-volatile drives, the first file associated with a predetermined file type, wherein allocating the primary two or more allocation units comprises mapping the allocation units in association with the first file;

allocating a secondary two or more allocation units of the single storage unit, the secondary two or more allocation units corresponding to a second file, the second file not associated with the predetermined file type; and

erasing the mapping without erasing data stored in the primary two or more allocation units.

2. The computer-readable storage medium of claim 1, wherein the secondary two or more allocation units are contiguous.

3. The computer-readable storage medium of claim 1, wherein at least two allocation units are selected in anticipation of a request.

4. The computer-readable storage medium of claim 1, comprising processing a file write request.

5. The computer-readable storage medium of claim 1, comprising reallocating allocation units if a predetermined number of contiguous allocation units are allocated.

6. In a computing environment, a system comprising:

a storage media that is configured as a storage volume and comprises a plurality of allocation units, the storage media comprising a single non-volatile drive; and

a file system comprising a driver component configured to allocate a plurality of allocation units of the storage volume in response to a request to allocate allocation units, the plurality of allocation units comprising a primary two or more allocation units and a secondary two or more allocation units, the primary two or more allocation units corresponding to a first file, the secondary two or more allocation units corresponding to a second file, the first file associated with a predetermined file type, the second file not associated with the predetermined file type, wherein allocating the plurality of allocation units comprises;

randomly selecting a first allocation unit of the primary two or more allocation units;

randomly selecting a second allocation unit of the primary two or more allocation units;

mapping the primary two or more allocation units in association with the first file; and

if a determination is made that the first and second allocation units are contiguous with one another, randomly selecting a third allocation unit of the plurality of allocation units and unselecting the second allocation unit; and

the file system configured to erase the mapping without erasing data stored in the primary two or more allocation units.

7. The system of claim 6, wherein the storage media comprises a single solid state drive.

8. The system of claim 6, wherein respective allocation units comprise a cluster.

9. The system of claim 8, wherein the file system comprises an NTFS-type file system.

10. The system of claim 6, comprising a randomizing mechanism coupled to the storage volume and configured to reallocate allocation units associated with a file if two or more contiguous allocation units are associated with the file.

11. The system of claim 6, wherein the driver component is configured to randomly select a fourth allocation unit based on a free space data structure.

12. The system of claim 11, wherein the free space data structure is configured to track at least one of allocation units that are free and allocation units that are already allocated.

13. The system of claim 6, comprising a randomizing mechanism coupled to the storage volume and configured to reallocate allocation units associated with the second file, wherein before reallocation, the second file was associated with substantially sequential allocation units, and wherein after reallocation, the second file is associated with randomly distributed substantially non-sequential allocation units.

14. The system of claim 6, wherein allocating the plurality of allocation units comprises randomly selecting a fourth allocation unit of the plurality of allocation units and unselecting the first allocation unit if the determination is made that the first and second allocation units are contiguous.

15. In a computing environment, a method comprising:

processing a request corresponding to a need to allocate allocation units of a single storage unit for file data of a file, the single storage unit comprising a single non-volatile drive;

allocating at least four allocation units of the single storage unit based upon the request, the at least four allocation units comprising a primary two or more non-contiguous allocation units and a secondary two or more non-contiguous allocation units, the primary two or more allocation units corresponding to a first file, the secondary two or more allocation units corresponding to a second file, the first file associated with a predetermined file type, the second file not associated with the predetermined file type, wherein allocating the at least four allocation units comprises randomly selecting a first allocation unit of the primary two or more allocation units and randomly selecting a second allocation unit of the primary two or more allocation units and mapping the primary two or more allocation units in association with the first file;

reallocating at least one of the first allocation unit and the second allocation unit associated with the first file if the first allocation unit and the second allocation unit are contiguous, and

erasing the mapping without erasing data stored in the primary two or more allocation units.

16. The method of claim 15, comprising recording at least one of the allocated and the reallocated allocation units in a set of mappings maintained in association with the storage unit, the mappings indicating which allocation units are associated with the file.

17. The method of claim 16, comprising erasing the set of mappings, wherein erasing the set of mappings does not comprise erasing data stored in the allocation units.

18. The method of claim 15, wherein processing the request comprises determining that the request is one that is to allocate one or more randomly selected allocation units.

19. The method of claim 15, comprising reallocating at least one of a third allocation unit and a fourth allocation unit associated with the second file if the third allocation unit and the fourth allocation unit are contiguous.

20. The method of claim 15, comprising mapping the secondary two or more allocation units in association with the second file.