Methods and systems for data storage

• US 20100217948A1
• Filed: 02/04/2010
• Published: 08/26/2010
• Est. Priority Date: 02/06/2009
• Status: Abandoned Application

• Current Assignee: OSR Open Systems Resources, Inc.
• Original Assignee: OSR Open Systems Resources, Inc.
• Inventors: Mason, W. Anthony, Widdowson, Roderick David Wolfe
• Application Number:
  US12/658,209
• Publication Number:
  US 20100217948A1
• Time in Patent Office: Days
• US Class Current: 711/171
• CPC Class Codes: G06F 11/1464 for networked environments
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache

Abstract

In one general aspect, various embodiments are directed to a method of writing a data block to a memory comprising receiving an electronic write request from an application. A content address of a first data block considering the value for the first data block. A mapping of the first data block to the content address may be written to a logical end of the local block map. The mapping may also be written to a remote block map. If the content address is not present at a local data storage, the value of the first data block may be written to the local data storage at a first location and metadata associating the content address with the first location may be written to the local data storage.

Claims

1. A system for remote storage of data, the system comprising:

a processor circuit comprising at least one processor;

a local data storage device in electronic communication with the processor circuit, wherein the local data storage device comprises;

a local block map, wherein the local block map comprises a plurality of mappings, wherein each mapping maps an identifier of a data block to a corresponding content address; and

a log-structured local data storage comprising data units organized by content address; and

a memory circuit operatively associated with the processor circuit, wherein the memory circuit comprises instructions that, when executed by the processor circuit, cause the processor circuit to;

receive an electronic write request from an application, wherein the write request comprises an identifier of a first data block and a value for the first data block;

derive a content address of the first data block considering the value for the first data block;

write a mapping to a logical end of the local block map, wherein the mapping maps the identifier of the first data block to the content address;

write the mapping to a remote block map;

determine if the content address is present at the local data storage;

conditioned upon the content address not being present at the local data storage;

write the value of the first data block to the local storage at a first location; and

write to the local storage metadata associating the content address with the first location.

2. The system of claim 1, wherein the plurality of mappings are logically arranged in the local block map in chronological order based on when each mapping was written to the local block map.

3. The system of claim 1, wherein deriving the content address comprises applying a hash algorithm to the value for the first data block.

4. The system of claim 3, wherein the hash algorithm is selected from the group consisting of SHA-0, SHA-1, SHA-2, SHA-3 and MD5.

5. The system of claim 1, wherein the first data block is at least one size selected from the group consisting of 512 bytes, 520 bytes, 1024 bytes, 2048 bytes and 4096 bytes.

6. The system of claim 1, wherein the local block map is organized according to a log-structured format.

7. The system of claim 1, wherein the remote block map is organized according to a log-structured format.

8. The system of claim 1, further comprising marking the mapping as un-pushed when a remote data storage comprising the remote block data map is unavailable.

9. The system of claim 1, wherein the memory circuit further comprises instructions that, when executed by the processor circuit, cause the processor circuit to, conditioned upon the content address not being present at the local data storage:

determine whether the content address is present at a remote storage;

write the value of the first data block to the remote storage at a first location; and

write to the remote storage metadata associating the content address with the first location.

10. A method for remote storage of data, the method comprising:

receiving an electronic write request from an application, wherein the write request comprises an identifier of a first data block and a value for the first data block;

deriving a content address of the first data block considering the value for the first data block;

writing a mapping to a logical end of a local block map, wherein the mapping maps the identifier of the first data block to the content address, wherein the local block map comprises a plurality of mappings, wherein each of the plurality of mappings maps an identifier of a data block to a corresponding content address;

writing the mapping to a remote block map;

determining if the content address is present at a local data storage, wherein the local data storage is log-structured and comprises data units organized by content address;

conditioned upon the content address not being present at the local data storage;

writing the value of the first data block to the local storage at a first location; and

writing to the local storage metadata associating the content address with the first location.

11. A portable data storage device for re-creating a client device on a computer machine, the device comprising a computer readable medium having written thereon:

a local block map, wherein the local block map comprises a plurality of mappings, wherein each mapping maps an identifier of a data block to a corresponding content address;

a log-structured local data storage comprising data units organized by content address; and

instructions that, when executed by a processor circuit, cause the processor circuit to;

receive an electronic write request from an application, wherein the write request comprises an identifier of a first data block and a value for the first data block;

derive a content address of the first data block considering the value for the first data block;

write a mapping to a logical end of the local block map, wherein the mapping maps the identifier of the first data block with the content address;

write the mapping to a remote block map;

determine if the content address is present at the local data storage;

conditioned upon the content address not being present at the local data storage;

write the value of the first data block to the local storage at a first location; and

write to the local storage metadata associating the content address with the first location.

12. A computer readable medium comprising instructions thereon that, when executed by at least one processor, cause the at least one processor to:

upon receipt of a write request comprising an identifier of a data block and a value of the data block, derive a content address for the data block based on the value of the data block;

update a local block map to associate the identifier with the content address;

update a remote block map to associate the identifier with the content address;

determine whether a log-structured local data log comprises the content address;

conditioned upon the local data log not comprising the content address;

write the value of the data block to the local data log at a first location; and

write to the local data log metadata associating the content address with the first location;

determine whether a remote data log comprises the content address;

conditioned upon the remote data log not comprising the content address;

write the value of the data block to the remote data log at a first remote location; and

write to the remote data log metadata associating the content address with the first remote location.

13. The computer readable medium of claim 12, wherein the remote data log is log-structured.

14. The computer readable medium of claim 12, wherein the remote data log is organized according to at least one of a hierarchal storage structure and an indexed storage structure.

15. The computer readable medium of claim 12, wherein updating the local block map comprises writing a mapping to a logical end of the local block log, wherein the mapping maps the identifier of the data block with the content address.

16. The computer readable medium of claim 12, wherein updating the remote block map comprises writing a mapping to a logical end of the remote block log, wherein the mapping maps the identifier of the data block with the content address.

17. A computer system comprising:

a processor circuit comprising at least one processor;

a local data storage device in electronic communication with the processor circuit, wherein the local data storage device comprises;

a local block map, wherein the local block map comprises a plurality of mappings, wherein each mapping maps an identifier of a data block to a corresponding content address; and

a log-structured local data storage comprising data units organized by content address; and

a memory circuit operatively associated with the processor circuit, wherein the memory circuit comprises instructions that, when executed by the processor circuit, cause the processor circuit to;

receive an electronic read request from an application, wherein the read request comprises an identifier of a first data block;

determine if the local block map comprises a content address associated with the identifier of the first data block;

conditioned upon the local block map comprising a content address associated with the identifier of the first data block, retrieving the content address from the local block map;

conditioned upon the local block map not comprising the content address, retrieving the content address from a remote block map;

determine whether the content address appears in the local data storage;

conditioned upon the content address appearing in the local data storage, retrieving a value associated with the content address in the local storage and returning the value to the application as a value for the first data block; and

conditioned upon the content address not appearing in the local data storage, retrieving a value associated with the content address in the remote storage and returning the value to the application as an identifier of a value for the first data block.

18. The system of claim 17, wherein the memory circuit comprises instructions that, when executed by the processor circuit, cause the processor circuit to, conditioned upon the content address not appearing in the local data storage, write the value associated with the content address in the remote storage to the local data storage.

19. The system of claim 17, wherein the plurality of mappings are logically arranged in the local block map in chronological order based on when each mapping was written to the local block map.

20. A computer-implemented method comprising:

receiving by a processor circuit an electronic read request from an application, wherein the read request comprises an identifier of a first data block, and wherein the processor circuit comprises at least one processor and is in communication with a local data storage;

determining by the processor circuit if a local block map at the local data storage comprises a content address associated with the identifier of the first data block;

conditioned upon the local block map comprising a content address associated with the identifier of the first data block, retrieving the content address from the local block map by the processor circuit;

conditioned upon the local block map not comprising the content address, retrieving the content address from a remote block map by the processor circuit;

determining by the processor circuit whether the content address appears in the local data storage;

conditioned upon the content address appearing in the local data storage, retrieving by the processor circuit a value associated with the content address in the local data storage and returning the value to the application as a value for the first data block; and

conditioned upon the content address not appearing in the local data storage, retrieving a value associated with the content address in the remote storage and returning the value to the application as an identifier of a value for the first data block.