Asynchronous and Distributed Storage of Data

• US 20090182939A1
• Filed: 01/11/2008
• Published: 07/16/2009
• Est. Priority Date: 01/11/2008
• Status: Active Grant

• Current Assignee: Akamai Technologies, Inc.
• Original Assignee: Verivue Incorporated (Akamai Technologies, Inc.)
• Inventors: Hluchyj, Michael G., Lawler, Christopher, Krishnan, Santosh, Reddy, Uma, Pai, Ganesh
• Granted Patent: US 8,364,892 B2
• Time in Patent Office: Days
• US Class Current: 711/114
• CPC Class Codes: G06F 3/0613 in relation to throughput
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD
• CPC Class Codes: H04N 21/23103 using load balancing strategies, e.g. by placing or distributing content on different disks, different memories or different servers storage management G06F3/0604; allocation of resources considering the load in multiprogramming arrangements G06F9/505; techniques for rebalancing the load in a distributed system G06F9/5083; access to distributed or replicated servers, e.g. load balancing, in data networks H04L67/1001
• CPC Class Codes: H04N 21/2318 using striping
• CPC Class Codes: H04N 21/26208 the scheduling operation being performed under constraints
• CPC Class Codes: H04N 21/26216 involving the channel capacity, e.g. network bandwidth admission control, resource allocation in open networks H04L12/5692; flow control in packet networks H04L47/10; establishing a schedule or organising the servicing of application requests taking into account QoS H04L67/61

Abstract

In one example, multimedia content is requested from a plurality of storage modules. Each storage module retrieves the requested parts, which are typically stored on a plurality of storage devices at each storage module. Each storage module determines independently when to retrieve the requested parts of the data file from storage and transmits those parts from storage to a data queue. Based on a capacity of a delivery module and/or the data rate associated with the request, each storage module transmits the parts of the data file to the delivery module. The delivery module generates a sequenced data segment from the parts of the data file received from the plurality of storage modules and transmits the sequenced data segment to the requester.

Claims

1. A method associated with asynchronous and distributed storage of data, the method comprising:

receiving, at each storage module in a plurality of storage modules, a data file request from a delivery module;

determining, at each of the storage modules, a start location for a part of a data file associated with the data file request;

determining asynchronously, at each of the storage modules, a queue location within a scheduling queue to associate with the data file request; and

adding asynchronously, at each of the storage modules, the part of the data file to a data queue based on the queue location within the scheduling queue, a capacity of the data queue, a transmission rate associated with the data file, or any combination thereof.

2. The method of claim 1, further comprising removing, at a first storage module in the plurality of storage modules, the queue location from within the scheduling queue.

3. The method of claim 2, further comprising:

determining, at the first storage module, a second queue location within the scheduling queue; and

adding, at the first storage module, the second part of the data file to the data queue based on the second queue location within the scheduling queue, the capacity of the data queue, the transmission rate associated with the data file, or any combination thereof.

4. The method of claim 3, wherein the determining, at the first storage module, the second queue location within the scheduling queue further comprises determining, at the first storage module, the second queue location within the scheduling queue based on the first queue location.

5. The method of claim 1, further comprising transmitting, at each of the storage modules, the part of the data file in the data queue based on a capacity of the delivery module, the transmission rate associated with the data file, a request from the delivery module, or any combination thereof.

6. The method of claim 5, wherein the capacity of the delivery module comprises a transmission capacity for a network associated with the delivery module, a storage capacity of the delivery module, a storage capacity of a computing device associated with the data file request, or any combination thereof.

7. The method of claim 1, wherein the determining asynchronously, at each of the storage modules, the queue location within the scheduling queue comprises determining asynchronously, at each of the storage modules, the queue location within the scheduling queue based on the start location.

8. The method of claim 1, further comprising:

receiving, at the delivery module, a plurality of parts of the data file from the plurality of storage modules; and

assembling the plurality of parts of the data file into a sequenced data segment.

9. The method of claim 8, further comprising transmitting the sequenced data segment to a computing device associated with the data file request.

10. The method of claim 9, wherein the transmitting the sequenced data segment comprises employing a real-time transport protocol, a hypertext transfer protocol, a file transfer protocol, a transmission control protocol, an internet protocol (IP), a user datagram protocol, a video streaming over IP, an audio streaming over IP, or any combination thereof

11. The method of claim 8, further comprising:

receiving, at the delivery module, a second plurality of parts of the data file or a second data file from the plurality of storage modules; and

assembling the second plurality of parts of the data file or the second data file into a second sequenced data segment.

12. The method of claim 1, wherein the scheduling queue is a first scheduling queue, the queue location is a first queue location, and the method further comprising:

determining asynchronously, at each of the storage modules, a second queue location within a second scheduling queue.

13. The method of claim 12, wherein the determining asynchronously, at each of the storage modules, the second queue location within the second scheduling queue further comprises determining asynchronously, at each of the storage modules, the second queue location within the second scheduling queue based on a second data file request.

14. The method of claim 12, wherein the first scheduling queue is associated with a different rate than the second scheduling queue.

15. The method of claim 1, further comprising:

determining asynchronously, at each of the storage modules, a second start location for a second part of the data file associated with a second data file request;

determining asynchronously, at each of the storage modules, a second queue location within the scheduling queue; and

adding asynchronously, at each of the storage modules, the second part of the data file to the data queue based on the second queue location within the scheduling queue, the capacity of the data queue, the transmission rate associated with the data file, or any combination thereof.

16. The method of claim 15, further comprising:

removing, at each of the storage modules, the parts of the data file within the data queue based on the second data file request; and

removing, at the delivery module, a sequenced data stream based on the second data file request.

17. The method of claim 1, wherein the determining, at each of the storage modules, the start location for the part of the data file associated with the data file request further comprises determining, at each of the storage modules, the start location for the part of the data file associated with the data file request based on index information.

18. The method of claim 17, further comprising receiving the index information from the delivery module.

19. The method of claim 1, further comprising storing, at a first storage device within a first storage module, the part of the data file and a second part of the data file in a same block within the first storage device.

20. The method of claim 1, further comprising:

storing, at a first storage device within a first storage module, the part of the data file; and

storing, at a second storage device within the first storage module, a second part of the data file.

21. The method of claim 1, further comprising:

storing, at a first storage device within a first storage module, the part of the data file; and

storing, at a second storage device within a second storage module, a second part of the data file.

22. The method of claim 1, further comprising storing, at a first storage device within a first storage module, the part of the data file and a second part of a second data file in a same block within the first storage device, the part of the data file being different than and associated with the second part of the second data file.

23. The method of claim 22, further comprising determining an association between the part of the data file and the second part of the second data file, the association comprising a content program association, a program time association, or both, the part of the data file being associated with a first content program and the second part of the second data file being associated with a second content program.

24. The method of claim 22, further comprising removing, at the first storage device within the first storage module, the block from the first storage device thereby removing the part of the data file and the second part of the second data file.

25. The method of claim 22, wherein a size of the block is a predetermined size based on a memory device used as the first storage device.

26. The method of claim 1, further comprising determining asynchronously, at each of the storage modules, a plurality of queue locations within the scheduling queue for the data file request based on the start location, the capacity of the data queue, the transmission rate associated with the data file, or any combination thereof.

27. The method of claim 1, wherein the data file comprises a plurality of multimedia content files which are delineated by the parts of the data file.

28. The method of claim 1, wherein the scheduling queue comprises a linked list of queue locations, a table of queue locations, a template of queue locations, a plurality of sub-queues, or any combination thereof.

29. The method of claim 1, wherein the scheduling queue comprises a table of queue locations, the table comprises a plurality of queue locations associated with a maximum number of multimedia segments a storage module is capable of retrieving from storage.

30. The method of claim 1, wherein the scheduling queue comprises a plurality of sub-queues, each sub-queue is associated with an individual storage device and comprises a linked list of queue locations.

31. The method of claim 1, wherein the queue location is associated with a video stream segment.

32. A method associated with asynchronous and distributed storage of data, the method comprising:

receiving, at a first storage module, a data file request from a delivery module;

determining, at the first storage module, a first start location for a first part of a data file associated with the data file request;

determining, at the first storage module, a first location within a first scheduling queue to associate with the data file request;

adding, at the first storage module, the first part of the data file to a first output data queue based on the first location within the first scheduling queue, a capacity of the first output data queue, a transmission rate associated with the data file, or any combination thereof;

receiving, at a second storage module, the data file request from the delivery module, the second storage module being different than the first storage module;

determining, at the second storage module, a second start location for a second part of the data file associated with the data file request;

determining, at the second storage module, a second location to associate with the data file request, the second location being located within a second scheduling queue which is independent from the first scheduling queue; and

adding, at the second storage module, the second part of the data file to a second output data queue based on the second location within the second scheduling queue, a capacity of the second output data queue, the transmission rate associated with the data file, or any combination thereof.

33. A computer program product, tangibly embodied in an information carrier, the computer program product including instructions being operable to cause a data processing apparatus to:

receive, at each storage module in a plurality of storage modules, a data file request from a delivery module;

determine, at each of the storage modules, a start location for a part of a data file associated with the data file request;

determine asynchronously, at each of the storage modules, a queue location within a scheduling queue to associate with the data file request; and

add asynchronously, at each of the storage modules, the part of the data file to a data queue based on the queue location within the scheduling queue, a capacity of the data queue, a transmission rate associated with the data file, or any combination thereof.

34. A system associated with asynchronous and distributed storage of data, the system comprising:

a plurality of storage modules, each storage module comprising;

a plurality of storage devices, each storage device configured to store a part of a data file; and

a storage controller module connected to each of the plurality of storage devices independently and comprising;

a storage queue controller module configured to determine a queue location within a scheduling queue to associate with the data file request, the scheduling queue being configured by each storage module asynchronously, and

a storage device read controller module configured to;

determine a start location on one of the storage devices for a part of a data file associated with the data file request, and

add the part of the data file to a data queue based on a queue location within the scheduling queue, a capacity of the data queue, a transmission rate associated with the data file, or any combination thereof.

35. The system of claim 34, further comprising a delivery module configured to receive a plurality of parts of the data file from the plurality of storage modules and assemble the plurality of parts of the data file into a sequenced data segment.

36. The system of claim 34, further comprising substantially simultaneously reading data from a plurality of storage devices in a first storage module.

37. The system of claim 34, wherein the storage controller module further comprises:

the storage queue controller further configured to determine a write queue location within the scheduling queue to associate with the data file request; and

a storage device write controller configured to;

receive a second part of the data file from an input data queue, and

store the second part of the data file in a storage device selected from the plurality of storage devices based on the write queue location within the scheduling queue, a capacity of the storage device, a data storage request associated with the data file, or any combination thereof.

38. A system associated with asynchronous and distributed storage of data, the system comprising:

a means for storage of data comprising;

a plurality of means for storing data, each means for storing data stores a part of a data file;

a means connected to each of the plurality of means for storing data independently and comprising;

a means for determining a queue location within a scheduling queue to associate with the data file request, the scheduling queue being configured by each storage module asynchronously,

a means for determining a start location on one of the storage devices for a part of a data file associated with the data file request, and

a means for adding the part of the data file to a data queue based on a queue location within the scheduling queue, a capacity of the data queue, a transmission rate associated with the data file, or any combination thereof.