Abstracting programmatic representation of data storage systems

• US 8,375,227 B2
• Filed: 02/02/2009
• Issued: 02/12/2013
• Est. Priority Date: 02/02/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Terek, Soner, Sadovsky, Vladimir, Verma, Surendra, Geiger, Avi R.
• Primary Examiner(s): Zand, Kambiz
• Assistant Examiner(s): SHAIFER HARRIMAN, DANT B
• Application Number:
  US12/364,022
• Publication Number:
  US 20100199109A1
• Time in Patent Office: 1,471 Days
• Field of Search: 713/194
• US Class Current: 713/194
• CPC Class Codes: G06F 12/00 Accessing, addressing or allocating within memory systems or architectures digital input from, or digital output to record carriers, e.g. to disk storage units, G06F3/06
• 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/0626 Reducing size or complexity of storage systems
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0671 In-line storage system

Abstract

Providing for a paradigm shift in block-level abstraction for storage devices is described herein. At a block-level, storage is characterized as a variable size data record, rather than a fixed size sector. In some aspects, the variable size data record can comprise a variable binary key-data pair, for addressing and identifying a variable size block of data, and for dynamically specifying the size of such block in terms of data storage. By changing the key or data values, the location, identity or size of block-level storage can be modified. Data records can be passed to and from the storage device to facilitate operational commands over ranges of such records. Block-level data compression, space management and transactional operations are provided, mitigating a need of higher level systems to characterize underlying data storage for implementation of such operations.

Claims

1. A data storage device, comprising:

a set of physical data storage blocks;

a processing circuit coupled to the storage blocks that directly maps subsets of the physical data storage blocks to corresponding variable data records that include key-value pairs and that represent information stored on the subsets;

an atomic record component that dynamically updates the mapping based on changes to the key-value pairs of the variable data records; and

an aggregation component that re-allocates at least some of the stored information to different ones of the subsets of the physical storage blocks based at least on the changes to the key-value pairs of the variable data records.

2. The data storage device of claim 1, further comprising a transport component that receives the external input indicating the changes from a system that is external to the data storage device.

3. The data storage device of claim 2, wherein the transport component outputs the information stored by the subsets of the storage blocks in response to data call comprising corresponding ones of the variable data records.

4. The data storage device of claim 1, further comprising a compression component that employs data record prefix compression for information stored in adjacent storage blocks.

5. The data storage device of claim 1, further comprising a protection component that implements block-level data security.

6. The data storage device of claim 5, wherein the protection component executes an encryption algorithm for a range of key values of a plurality of variable data records marked for encryption by a host application or device.

7. The data storage device of claim 1, further comprising an operations component that processes one or more of insertion, update, deletion, and read commands for a range of key values of a plurality of variable data records based on external input.

8. The data storage device of claim 1, wherein the atomic record component implements one or more of an error detection operation, an error correction operation, a data decryption operation, or a data de-fragmentation operation.

18. The data storage device of claim 1, wherein the aggregation component re-allocates at least some of the stored information to different ones of the subsets of the physical storage blocks further based at least on binary comparisons of the key-value pairs of the variable data records.

19. The data storage device of claim 18, wherein the physically adjacent subsets of storage blocks are allocated information that is associated with variable data records having similar key-data pairs as determined by the binary comparisons.

9. A method for abstracting data storage, comprising:

characterizing, by a processing circuit of a storage device, a set of physical storage blocks of a data storage device;

mapping, by the processing circuit, variable data records to subsets of the physical storage blocks of the data storage device based on the characterization, the variable data records usable to distinguish the subsets from one another;

facilitating, by an atomic record unit of the storage device, external assignment of key-data values of the variable data records to provide external control of storage operations for the subsets of the physical storage blocks;

re-allocating, by an aggregation component, the variable data records to different ones of the subsets of the physical storage blocks based on the external assignment of the key-data pairs of the variable data records; and

storing, by the processing circuit, the variable data records in a portion of the storage device that are different from the subsets of the physical storage blocks.

10. The method of claim 9, wherein the key-data pairs include variable-sized key values and variable-sized data values.

11. The method of claim 10, wherein:

the variable-sized data values comprise a variable length binary fields that define sizes of the subsets of the storage blocks mapped to the data records; and

the variable-sized key values comprise second variable length binary fields that distinguish the subsets of the storage blocks from one another.

12. The method of claim 9, wherein the re-allocating is based at least on a degree of similarity between the variable data records.

13. The method of claim 9, further comprising compressing the variable data records prior to the storing of the variable data records.

14. The method of claim 13, wherein the compressing includes employing prefix compression on adjacent variable data records.

15. The method of claim 9, further comprising receiving a request from an external host to execute one of encryption, insertion, deletion, update, or read on a range of the variable data records.

16. The method of claim 9, further comprising providing semantic clustering of adjacent data records.

17. A system that manages data operations for a data storage device, comprising:

memory;

one or more processors;

a memory interface that communicatively couples the system to a data storage device;

a retrieval component, stored on the memory and executable by the one or more processors, to employ the memory interface to obtain a set of variable data records from the storage device, the variable data records comprising respective variable size key-data pairs, modifications to the variable size key-data pairs usable to re-allocate information to different ones of the physical storage blocks of the storage device;

an input component, stored on the memory and executable by the one or more processors, to facilitate user modification of variable length binary fields associated with the respective variable size key-data pairs;

an application component, stored on the memory and executable by the one or more processors, to generate an abstracted data object for information represented by the data records; and

a command component, stored on the memory and executable by the one or more processors, to return modified variable data records to the data storage device, the modified variable data records comprising modified binary field values consistent with the abstracted data object.