Network coded storage with multi-resolution codes
Multi-resolution encoded files are stored on a plurality of disk drives using systematic network coded storage. In some embodiments, the stored files are used to provide video streaming services for users.
1. In a system that uses multi-resolution coding to store files at multiple different resolutions within a plurality of disk drives, a method comprising:
storing a base layer of a first file on each of a first set of disk drives in the plurality of disk drives, the base layer in non-network coded form;
generating linear combinations of the base layer of the first the and a first refinement layer of the first file using systematic network coding; and
storing a linear combination of the base layer of the first file and the first refinement layer of the first file on each of a second set of disk drives in the plurality of disk drives.
2. The method of claim 1 further comprising:
receiving a request for the first file from a user;
retrieving a first linear combination of the base layer of the first file and the first refinement layer of the first file from one of the second set of disk drives;
determine if any of the disk drives in the first set of disk drives has sufficient bandwidth available to process the request;
in response to determining that at least one the disk drives in the first set of disk drives has sufficient bandwidth available to process the request, retrieving the base layer of the first file from one of the first set of disk drives;
in response to determining that none of the disk drives in the first set of disk drives has sufficient bandwidth available to process the request, retrieving a second linear combination of the base layer of the first file and the first refinement layer of the first file from one of the second set of disk drives; and
sending data to the user based upon the retrieved data.
3. The method of claim 2 wherein receiving the request for the first file comprises receiving a request for the first file at a specified resolution.
4. The method of claim 3 wherein sending data to the user based upon the retrieved data comprises sending data to the user at the specified resolution.
5. The method of claim 3 wherein sending data to the user based upon the retrieved data comprises sending data to the user at a resolution different from the specified resolution.
6. The method of claim 1 wherein generating linear combinations of the base layer of the first file and a first refinement layer of the first file comprises generating a linear combination for each of the second set of disk drives using different random coefficients.
7. The method of claim 1 , wherein storing a linear combination of the base layer and the first refinement layer on each of the second set of disk drives includes storing the different random coefficients with each linear combination on each of the second set of disk drives.
8. A method for storing files within a plurality of disk drives in a system that uses multi-resolution coding, the method comprising:
storing a base layer of a first file on each of a first set of disk drives in the plurality of disk drives;
generating a linear combination of the base layer of the first file and at least one refinement layer of the first file using random coefficients; and
storing the linear combination of the base layer of the first file and the at least one refinement layer of the first file on each of a second set of disk drives in the plurality of disk drives.
9. The method of claim 8 wherein:
storing the base layer includes storing the base layer in non-network coded form,
generating a linear combination of the base layer of the first file and at least one refinement layer includes generating one or more linear combinations of the base layer of the first file and a first refinement layer of the first file using systematic network coding; and
storing the linear combination of the base layer of the first file and the at least one refinement layer of the first file on each of a second set of disk drives in the plurality of disk drives includes storing at least one of the one or more linear combinations of the base layer of the first file and the first refinement layer of the first file on each of a second set of disk drives in the plurality of disk drives.
10. The method of claim 9 further comprising:
receiving a request for the first file from a user;
retrieving a first linear combination of the base layer of the first file and the first refinement layer of the first file from one of the second set of disk drives;
determine if any of the disk drives in the first set of disk drives has sufficient bandwidth available to process the request;
in response to determining that at least one the disk drives in the first set of disk drives has sufficient bandwidth available to process the request, retrieving the base layer of the first file from one of the first set of disk drives;
in response to determining that none of the disk drives in the first set of disk drives has sufficient bandwidth available to process the request, retrieving a second linear combination of the base layer of the first file and the first refinement layer of the first file from one of the second set of disk drives; and
sending data to the user based upon the retrieved data.
11. The method of claim 10 wherein receiving the request for the first file comprises receiving a request for the first file at a specified resolution.
12. The method of claim 11 wherein sending data to the user based upon the retrieved data comprises sending data to the user at the specified resolution.
13. The method of claim 8 , wherein:
storing a linear combination of the base layer and the refinement layer on each of the second set of disk drives includes generating a linear combination for each of the second set of disk drives using different random coefficients.
14. The method of claim 13 , wherein storing a linear combination of the base layer and the refinement layer on each of the second set of disk drives includes storing the different random coefficients with each linear combination on each of the second set of disk drives.
15. The method of claim 8 , wherein the first set of disk drives and the second set of disk drives have no disk drives in common.
16. The method of claim 8 , further comprising:
storing a linear combination of the base layer of the first file, the refinement layer of the first file, and a second refinement layer of the first file on each of a third set of disk drives in the plurality of disk drives.
17. The method of claim 8 , wherein the method is implemented in a data center associated with a content distribution network.
18. The method of claim 8 , further comprising:
storing a base layer of a second file on each of the first set of disk drives in the plurality of disk drives; and
storing a linear combination of the base layer of the second file and a refinement layer of the second file on each of the second set of disk drives in the plurality of disk drives.
19. The method of claim 8 , wherein the first file includes a video file.
20. A system comprising:
a plurality of disk drives; and
a controller to store files on the plurality of disk drives in multiple different resolutions using a multi-resolution code, the controller being configured to:
store a base layer of a first file on each of a first group of disk drives in the plurality of disk drives;
generate a linear combination of the base layer of the first file and at least one refinement layer of the first file using random coefficients; and
store the linear combination of the base layer of the first file and the at least one refinement layer of the first file on each of a second group of disk drives in the plurality of disk drives.
21. The system of claim 20 , wherein the controller is configured to store a linear combination of the base layer of the first file, a first refinement layer of the first file, and a second refinement layer of the first file on each of a third group of disk drives in the plurality of disk drives.
22. The system of claim 20 , wherein the controller is configured to:
generate the linear combination for each of the second set of disk drives using different random coefficients; and
store the random coefficients on the each of the second set of disk drives in association with the corresponding linear combination.
23. The system of claim 20 , wherein the controller is configured to store a linear combination of the base layer of the first file, the first refinement layer of the first file, and a second refinement layer of the first file on each of a third set of disk drives in the plurality of disk drives.
24. The system of claim 20 , further comprising:
a plurality of servers for use in servicing requests from users, wherein each server in the plurality of servers is associated with a different set of disk drives within the plurality of disk drives.
25. The system of claim 20 , wherein the system is part of a data center associated with a content distribution network.
26. The system of claim 20 , wherein:
the controller is configured to retrieve files from the plurality of disk drives in response to user requests, the controller to receive a user request for the first file at a next to lowest resolution and, in response thereto, retrieve a first linear combination of the base layer associated with the first file and the first refinement layer associated with the first file from a disk drive in the second group of disk drives, and retrieve either a base layer associated with the first file from a disk drive in the first group of disk drives or a second linear combination of the base layer associated with the first file and the first refinement layer associated with the first file from another disk drive in the second group of disk drives.