BLOB MANIPULATION IN AN INTEGRATED STRUCTURED STORAGE SYSTEM

• US 20100106734A1
• Filed: 10/24/2008
• Published: 04/29/2010
• Est. Priority Date: 10/24/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: CALDER, BRADLEY GENE, NILAKANTAN, NIRANJAN, WANG, JU, SRIVASTAV, SHASHWAT, BHARDWAJ, DEEPALI, WU, XINRAN, NAGY, ALEXANDER FELSOBUKI
• Granted Patent: US 8,495,036 B2
• Time in Patent Office: Days
• US Class Current: 707/758
• CPC Class Codes: G06F 16/215 Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors
• CPC Class Codes: G06F 16/40 of multimedia data, e.g. slideshows comprising image and additional audio data retrieval of still image data G06F16/50; retrieval of audio data G06F16/60; retrieval of video data G06F16/70
• CPC Class Codes: G06F 16/93 Document management systems

Abstract

Embodiments of the present invention relate to systems, methods and computer storage media for facilitating the structured storage of binary large objects (Blobs) to be accessed by an application program being executed by a computing device. Generally, the manipulation of Blobs in a structured storage system includes receiving a request for a Blob, which may be located by way of a Blob pointer. The Blob pointer allows for the data, such as properties, of the Blob to be identified and located. Expired properties are garbage collected as a manipulation of the Blob data within a structured storage system. In an embodiment, the Blob is identified by a key that is utilized within a primary structured index to located the requested Blob. In another embodiment, the requested Blob is located utilizing a secondary hash index. In an additional embodiment, the Blob is locate utilizing a file table.

Claims

1. One or more computer storage media having computer-executable instructions embodied thereon for performing a method for retrieving data of a Binary Large Object (Blob) in a structured storage system, the method comprising:

receiving a request for a Blob from an application;

identifying a Blob pointer associated with the Blob;

identifying data associated with the Blob, wherein the data is identified, in part, by the Blob pointer; and

communicating the data to the application.

2. The method of claim 1, wherein identifying data further comprising:

identifying a Committed Block List (CBL) from the Blob pointer;

identifying one or more blocks of a Blob stream, wherein the one or more blocks are identified by the CBL; and

retrieving data from at least one of the one or more blocks.

3. The method of claim 1, wherein identifying the Blob pointer further comprises searching at least one of a memory table, a secondary hash index, and a file table of the structured storage system.

4. The method of claim 3, wherein the memory table is searched first, the secondary hash index is searched second, and the file table is searched third until the Blob pointer is identified.

5. The method of claim 4, wherein the secondary hash index is searched if a key is not found in the memory table.

6. The method of claim 1, wherein identifying the Blob pointer further comprises:

determining a key for the Blob is unavailable in a memory table and a secondary hash index; and

identifying the Blob pointer for the Blob in a file table.

7. The method of claim 1, wherein identifying data of the Blob further comprises:

identifying a key in a secondary hash index;

identifying that one or more dirty bits are not associated with the Blob; and

retrieving the data from a Blob header of the Blob.

8. The method of claim 1, further comprising

identifying a key associated with the Blob pointer, wherein the key includes a reference to a particular row of an index;

locating the Blob pointer in a secondary hash index, wherein the Blob pointer is located utilizing the key;

utilizing the Blob pointer to identify a Committed Block List (CBL) that identifies one or more blocks of a Blob data stream; and

reading data from at least one of the one or more blocks identified in the CBL.

9. One or more computer storage media having computer-executable instructions embodied thereon for performing a method of garbage collection in a structured storage system, the method comprising:

scanning a primary structured index for one or more expired Blobs;

deleting the one or more expired Blobs from the primary structured index;

identifying one or more extents of a stream that include an active region, wherein an active region is a region of an extent referenced by the primary structured index;

identifying one or more extents of the stream to be collected;

collecting the at least one extent from the stream; and

checkpointing a list of extents reclaimed.

10. The method of claim 9, wherein one or more extents to be collected is based, in part, on a utilization ratio, wherein the utilization ratio is a ratio between active regions of an extent and inactive regions of the extent.

11. The method of claim 9, wherein collecting the at least one extent further comprises moving at least a portion of the active region of at least one of the one or more extents to be collected.

12. The method of claim 11 further comprising an atomic operation including creating a new stream, hard-linking extents from an old stream to the new stream, deleting the old stream, and renaming the new stream to the old stream.

13. The method of claim 12 further comprising clearing one or more dirty bits from the primary structured index when a secondary index or a Blob header are updated to be consistent with the primary structured index.

14. A structured storage system that facilitates the seamless integration of one or more Binary Large Objects (Blobs), the structured storage system comprising:

a primary structured index for indexing one or more Blobs in a structured storage system, wherein the primary structured storage index has at least a memory table and a row store, wherein the row store includes at least an update log stream and a file checkpoint stream; and

a secondary hash index, wherein the secondary hash index facilitates in-memory lookup of one or more Blobs indexed in the primary structured index.

15. The media of claim 14, wherein the memory table is checkpointed in preparation of an offload of an associated partition.

16. The media of claim 15, wherein the secondary hash index is checkpointed in preparation of an offload of an associated partition.

17. The media of claim 14 further comprising a sequence number allocator, wherein the sequence number allocator generates sequence numbers that are assigned to structured storage system.

18. The media of claim 17, wherein the sequence number allocator maintains an indication of a last acknowledged sequence, which is the highest sequence number completed, further wherein, during replay of a Blob log stream, transaction with a sequence number less than the last acknowledged sequence are allowed to replay from the Blob log stream.

19. The media of claim 14, wherein the secondary hash index is maintained consistent with the primary structured index by loading of the secondary hash index from a last checkpoint and utilizing at least one of:

1) a file table and the memory table, and

2) a hash index delta log and memory table changes.

20. The media of claim 14 further comprising a Blob store, wherein the Blob store allows for multiple Blob properties per row of the Blob store, further wherein a key is associated with each Blob property of the Blob store, the key is comprised of a primary row key associated with the row of the Blob property and a Blob property name associated with the Blob property.