B-file abstraction for efficiently archiving self-expiring data

• US 8,924,362 B2
• Filed: 06/30/2008
• Issued: 12/30/2014
• Est. Priority Date: 06/30/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Nath, Suman Kumar
• Primary Examiner(s): SOMERS, MARC S
• Application Number:
  US12/165,466
• Publication Number:
  US 20090327376A1
• Time in Patent Office: 2,374 Days
• Field of Search: 707/689, 707/737, 707/791, 707/819, 707/999.001, 707/999.206
• US Class Current: 707/689
• CPC Class Codes: G06F 16/901 Indexing; Data structures therefor; Storage structures for retrieval from the web G06F16/951
• CPC Class Codes: G06F 3/0613 in relation to throughput
• CPC Class Codes: G06F 3/0616 in relation to life time, e.g. increasing Mean Time Between Failures [MTBF]
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]

Abstract

Systems and methods are provided for data processing and storage management. In an illustrative implementation an exemplary computing environment comprises at least one data store, a data processing and storage management engine (B-File engine) and at least one instruction set to instruct the B-File engine to process and/or store data according to a selected data processing and storage management paradigm. In an illustrative operation, the illustrative B-File engine can generate a B-File comprising multiple buckets and store sample items in a random bucket according to a selected distribution. When the size of the B-FILE grows to reach a selected threshold (e.g., maximum available space), the B-File engine can shrink the B-File by discarding the largest bucket. Additionally, the B-File engine can append data to existing buckets and explicitly cluster data when erasing data such that data can be deleted together into the same flash block.

Claims

1. A method comprising:

receiving data items for storage on a solid state storage device having multiple storage blocks;

determining different levels for the data items, wherein the different levels determine when the data items expire and are deleted from the solid state storage device;

assigning the data items to different storage buckets of a bucket file based on the levels;

appending the data items within the different storage buckets on the solid state storage device such that individual storage buckets of data items are clustered together in corresponding blocks of the solid state storage device while maintaining corresponding numbers of the data items in the different storage buckets so that the corresponding numbers of the data items in the different storage buckets progressively decrease by level; and

periodically deleting largest storage buckets from the solid state storage device via one or more block erase operations while at least some other storage buckets remain stored on the solid state storage device, the largest storage buckets having greater numbers of the data items than the other storage buckets that remain stored on the solid state storage device.

2. The method of claim 1, further comprising:

periodically making determinations that the bucket file has reached a size threshold; and

performing the periodically deleting responsive to the determinations.

3. The method of claim 1, wherein the corresponding numbers of the data items of the different storage buckets are exponentially decreasing.

4. The method of claim 1, wherein the at least some other storage buckets that remain stored on the solid state storage device comprise a random sample from an evolving data stream, and the largest storage buckets are periodically removed from the random sample via the one or more block erase operations.

5. The method of claim 1, further comprising:

maintaining, in a memory device, in-memory portions of individual storage buckets; and

appending the data items within the individual storage buckets by writing the data items from the in-memory portions to the solid state storage device.

6. The method of claim 1, wherein the in-memory portions comprise page buffers that temporarily store pages of data items.

7. The method of claim 6, wherein the appending comprises flushing an individual page of data items responsive to determining that the individual page holds one page worth of data.

8. A system comprising:

a solid state storage device having multiple storage blocks;

a hardware processing unit; and

a memory device storing computer-readable instructions that cause the hardware processing unit to;

receive data items for storage on the solid state storage device;

determine different levels for the data items, wherein the different levels determine when the data items expire and are deleted from the solid state storage device;

assign the data items to different storage buckets of a bucket file based on the levels;

append the data items within the different storage buckets on the solid state storage device such that individual storage buckets of data items are clustered together in corresponding blocks of the solid state storage device;

maintain corresponding numbers of the data items in the different storage buckets so that the corresponding numbers of the data items in the different storage buckets progressively decrease by level; and

periodically delete largest storage buckets from the solid state storage device via one or more block erase operations while at least some other storage buckets remain stored on the solid state storage device, the largest storage buckets having greater numbers of the data items than the other storage buckets that remain stored on the solid state storage device.

9. The system of claim 8, wherein the computer-readable instructions cause the hardware processing unit to:

make periodic determinations that a size of the bucket file has reached a threshold; and

periodically delete the largest storage buckets responsive to the periodic determinations.

10. The system of claim 8, wherein the computer-readable instructions cause the hardware processing unit to:

determine the different storage buckets for the data items randomly.

11. The system of claim 8, wherein the solid state storage device is a flash storage device.

12. The system of claim 8, wherein the computer-readable instructions cause the hardware processing unit to:

append first data items in a first storage bucket of the different storage buckets without overwriting any other first data items already in the first storage bucket.

13. The system of claim 8, wherein the computer-readable instructions cause the hardware processing unit to:

buffer the data items in the memory device and periodically flush the buffered data items from the memory device to the solid state storage device.

14. The system of claim 13, wherein the computer-readable instructions cause the hardware processing unit to:

maintain a first in-memory page of first data items from a first bucket and a second in-memory page of second data items from a second bucket;

at a first time when the first in-memory page becomes full, flush the first in-memory page of first data items to the solid state storage device by appending the first data items to other first data items from the first bucket that are already stored on the solid state storage device; and

at a second time when the second in-memory page becomes full, flush the second in-memory page of second data items to the solid state storage device by appending the second data items to other second data items from the second bucket that are already stored on the solid state storage device.

15. A system comprising:

a solid state storage device having multiple storage blocks;

a solid state storage device controller; and

a hardware processing unit configured to;

receive data items for storage on the solid state storage device;

determine different levels for the data items, wherein the different levels determine when the data items expire and are deleted from the solid state storage device;

assign the data items to different storage buckets of a bucket file based on the levels;

direct the solid state storage device controller to append the data items within the different storage buckets on the solid state storage device such that individual storage buckets of data items are clustered together in corresponding blocks of the solid state storage device;

maintain corresponding numbers of the data items in the different storage buckets so that the corresponding numbers of the data items in the different storage buckets progressively decrease by level; and

direct the solid state storage device controller to periodically delete largest storage buckets from the solid state storage device via one or more block erase operations while at least some other storage buckets remain stored on the solid state storage device, the largest storage buckets having greater numbers of the data items than the other storage buckets that remain stored on the solid state storage device.

16. The system of claim 15, wherein the hardware processing unit is configured to:

make periodic determinations that a size of the bucket file has reached a threshold; and

direct the solid state storage device controller to periodically delete the largest storage buckets responsive to the periodic determinations.

17. The system of claim 15, wherein the corresponding numbers of the data items of the different storage buckets are exponentially decreasing.

18. The system of claim 17, wherein the other storage buckets that remain stored on the solid state storage device comprise a random sample of evolving, incoming data items received by the system.

19. The system of claim 15, wherein the solid state storage device is a flash storage device.