Distributed decentralized data storage and retrieval

• US 8,549,095 B2
• Filed: 12/21/2011
• Issued: 10/01/2013
• Est. Priority Date: 04/20/2005
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Moore, George M., Cseri, Istvan
• Primary Examiner(s): Gorney, Boris
• Application Number:
  US13/332,710
• Publication Number:
  US 20120096127A1
• Time in Patent Office: 650 Days
• Field of Search: 709/213, 709/231, 711/100, 711/112
• US Class Current: 709/213
• CPC Class Codes: G06F 16/1834 implemented based on peer-to-peer networks, e.g. gnutella p2p communication protocols H04L67/104
• CPC Class Codes: H04L 67/02 based on web technology, e.g. hypertext transfer protocol [HTTP]
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/108 characterised by resources being split in blocks or fragments
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

Systems and methods for distributed, decentralized storage and retrieval of data in an extensible SOAP environment are disclosed. Such systems and methods decentralize not only the bandwidth required for data storage and retrieval, but also the computational requirements. Accordingly, such systems and methods alleviate the need for one node to do all the storage and retrieval processing, and no single node is required to send or receive all the data.

Claims

1. A method comprising:

communicating with a distributed hash table comprising a plurality of local routing tables maintained in a plurality of processor nodes containing storage, each of the plurality of local routing tables containing hash values corresponding to node addresses of neighboring network nodes, the plurality of processor nodes comprising at least a first processor node;

receiving, by a routing service, a storage request message comprising a bit stream, the bit stream coming from a storage service;

dividing the bit stream into a plurality of chunks;

computing hash values for each of the plurality of chunks, each hash value based on a concatenation comprising a bit stream identifier and a user identifier;

consulting a local routing table of the first processor node to determine if an address of a recipient processor node corresponds to a neighboring network node of the first processor node, the recipient processor node comprising a chunk store service that divides a received chunk into a plurality of fragments, encodes a fragment into a plurality of check blocks, and transmits each check block of the plurality of check blocks to a fragment store service; and

transmitting, into a network, a plurality of chunk store messages if the address of the recipient processor node corresponds to the neighboring network node of the first processor node.

2. The method of claim 1, the fragment store service is configured to receive from the chunk store service at least one of the plurality of fragments and store the at least one of the plurality of fragments.

3. The method of claim 1, further comprising:

retrieving a portion of the stored bit stream by using an offset value associated with a chunk.

4. The method of claim 1, further comprising the chunk store service starting a timer when each check block is sent out for storage and, if the chunk store service does not receive a confirmation from the fragment store service that each check block has been stored before the timer expires, the chunk store service attempts to store the fragment elsewhere.

5. The method of claim 1, further comprising:

directing a first chunk store message to the neighboring network node when a first hash value corresponding to the neighboring network node is present in the local routing table; and

transmitting the first chunk store message for hopping through an intermediary network node when the first hash value is not present in the local routing table.

6. The method of claim 1, further comprising each of the plurality of processor nodes having a time manager that provides alterable time relative to an absolute system time.

7. The method of claim 1, the received bit stream is received from the storage service.

8. The method of claim 7, further comprising the storage service receiving a storage request message comprising a SOAP message.

9. A computer readable storage memory having stored thereon at least one executable instruction that when executed cause a processor to perform operations comprising:

communicating with a distributed hash table comprising a plurality of local routing tables maintained in a plurality of processor nodes containing storage, each of the plurality of local routing tables containing hash values corresponding to node addresses of neighboring network nodes, the plurality of processor nodes comprising at least a first processor node;

receiving, by a routing service, a storage request message comprising a bit stream, the bit stream coming from a storage service;

dividing the bit stream into a plurality of chunks;

computing hash values for each of the plurality of chunks, each hash value based on a concatenation comprising a bit stream identifier and a user identifier;

consulting a local routing table of the first processor node to determine if an address of a recipient processor node corresponds to a neighboring network node of the first processor node, the recipient processor node comprising a chunk store service that divides a received chunk into a plurality of fragments, encodes a fragment into a plurality of check blocks, and transmits each check block of the plurality of check blocks to a fragment store service; and

transmitting, into a network, a plurality of chunk store messages if the address of the recipient processor node corresponds to the neighboring network node of the first processor node.

10. The computer readable storage memory of claim 9, the fragment store service is configured to receive from the chunk store service at least one of the plurality of fragments and store the at least one of the plurality of fragments.

11. The computer readable storage memory of claim 9, the operations further comprising:

retrieving a portion of the stored bit stream by using an offset value associated with a chunk.

12. The computer readable storage memory of claim 9, the operations further comprising the chunk store service starting a timer when each check block is sent out for storage and, if the chunk store service does not receive a confirmation from the fragment store service that each check block has been stored before the timer expires, the chunk store service attempts to store the fragment elsewhere.

13. The computer readable storage memory of claim 9, the operations further comprising:

directing a first chunk store message to the neighboring network node when a first hash value corresponding to the neighboring network node is present in the local routing table; and

transmitting the first chunk store message for hopping through an intermediary network node when the first hash value is not present in the local routing table.

14. The computer readable storage memory of claim 9, the operations further comprising each of the plurality of processor nodes having a time manager that provides alterable time relative to an absolute system time.

15. The computer readable storage memory of claim 9, the received bit stream is received from the storage service.

16. The computer readable storage memory of claim 9, the operations further comprising the storage service receiving a storage request message comprising a SOAP message.

17. A system comprising:

a processor; and

a memory coupled to the processor, the memory having stored thereon executable instructions that when executed by the processor cause the processor to effectuate operations comprising;

communicating with a distributed hash table comprising a plurality of local routing tables maintained in a plurality of processor nodes containing storage, each of the plurality of local routing tables containing hash values corresponding to node addresses of neighboring network nodes, the plurality of processor nodes comprising at least a first processor node;

receiving, by a routing service, a storage request message comprising a bit stream, the bit stream coming from a storage service;

dividing the bit stream into a plurality of chunks;

computing hash values for each of the plurality of chunks, each hash value based on a concatenation comprising a bit stream identifier and a user identifier;

consulting a local routing table of the first processor node to determine if an address of a recipient processor node corresponds to a neighboring network node of the first processor node, the recipient processor node comprising a chunk store service that divides a received chunk into a plurality of fragments, encodes a fragment into a plurality of check blocks, and transmits each check block of the plurality of check blocks to a fragment store service; and

transmitting, into a network, a plurality of chunk store messages if the address of the recipient processor node corresponds to the neighboring network node of the first processor node.